操作系统第4章存储管理

1、1第第4 4章章 存储管理存储管理 重要内容重要内容0存储器存储器0连续存储空间管理连续存储空间管理0分页存储管理分页存储管理0分段存储管理分段存储管理0虚拟存储管理虚拟存储管理0Intel x86Intel x86分段和分页存储结构分段和分页存储结构0LinuxLinux虚拟存储管理虚拟存储管理0Windows 2003Windows 2003虚拟存储管理虚拟存储管理2存储管理的功能存储管理的功能 分配和去配分配和去配0请求和释放主存空间请求和释放主存空间 抽象和映射抽象和映射0抽象成一维数组或二维地址空间抽象成一维数组或二维地址空间0地址转换地址转换 隔离和共享隔离和共享0隔离实现存储保护

2、功能隔离实现存储保护功能0超越隔离机制，提高主存利用率超越隔离机制，提高主存利用率 存储扩充存储扩充0虚拟，允许进程虚拟地址空间大于主存空间虚拟，允许进程虚拟地址空间大于主存空间34.1 4.1 存储器存储器4.1.1 4.1.1 存储器的层次存储器的层次 4.1.2 4.1.2 地址转换与存储保护地址转换与存储保护 44.1.1 4.1.1 存储器的层次存储器的层次寄存器寄存器高速缓存高速缓存主存储器主存储器磁盘缓存磁盘缓存固定磁盘固定磁盘可移动存储介质可移动存储介质54.1.2 4.1.2 地址空间与地址转换地址空间与地址转换(1)(1)链接链接动态动态重定重定位位静态静态重定重定位位源程

3、序源程序模块模块1 1源程序源程序模块模块2 2源程序源程序模块模块n n目标目标代码代码1 1目标目标代码代码2 2目标目标代码代码n n可重定位可重定位目标代码目标代码( (装载代装载代码码)()(辅存辅存) )编译编译装入装入执行执行程序名字程序名字空间空间逻 辑 地逻 辑 地址址空间空间物理地址物理地址空间空间可执行可执行二进代二进代码码( (主存主存) )库代码库代码可执行可执行二进代二进代码码( (主存主存) ) 程序的编译、链接、装入和执行程序的编译、链接、装入和执行6地址空间与地址转换地址空间与地址转换 逻辑地址（虚地址或相对地址）：逻辑地址（虚地址或相对地址）：CPUCPU所

4、生成的所生成的地址地址 物理地址（实地址或绝对地址）：内存单元所看物理地址（实地址或绝对地址）：内存单元所看到的地址到的地址 逻辑地址空间：由程序所生成的所有逻辑地址的逻辑地址空间：由程序所生成的所有逻辑地址的集合集合 物理地址空间：由逻辑地址所对应的所有物理地物理地址空间：由逻辑地址所对应的所有物理地址的集合址的集合 地址转换或重定位：把逻辑地址转换为物理地址地址转换或重定位：把逻辑地址转换为物理地址7 静态重定位静态重定位0地址转换工作在进程执行前一次完成；地址转换工作在进程执行前一次完成；0无须硬件支持，易于实现，但不允许程序在执行过程无须硬件支持，易于实现，但不允许程序在执行过程中移动

5、位置。中移动位置。0早期单用户单任务系统早期单用户单任务系统 动态重定位动态重定位0地址转换推迟到最后的可能时刻，即进程执行时才完地址转换推迟到最后的可能时刻，即进程执行时才完成；成；0允许程序在主存中移动、便于主存共享、主存利用率允许程序在主存中移动、便于主存共享、主存利用率高。高。地址空间与地址转换地址空间与地址转换8例：使用重定位寄存器的动态重定位例：使用重定位寄存器的动态重定位9存储保护存储保护 问题：保护操作系统不受用户进程所影响，保护用户进程问题：保护操作系统不受用户进程所影响，保护用户进程不受其他用户进程所影响不受其他用户进程所影响 方法方法1)1)存储键保护存储键保护v系统将主

6、存划分成大小相等的若干存储块，并给每个存系统将主存划分成大小相等的若干存储块，并给每个存储块都分配一个单独的保护键（锁）；在程序状态字储块都分配一个单独的保护键（锁）；在程序状态字PSWPSW中设置有保护键字段，对不同的作业赋予不同的代中设置有保护键字段，对不同的作业赋予不同的代码（钥匙）；钥匙和锁相配才允许访问码（钥匙）；钥匙和锁相配才允许访问2)2)界限寄存器（下页图）界限寄存器（下页图）v上、下界防护上、下界防护：硬件为分给用户作业的连续的主存空间：硬件为分给用户作业的连续的主存空间设置一对上、下界，分别指向该存储空间的上、下界设置一对上、下界，分别指向该存储空间的上、下界v基址、限长防

7、护基址、限长防护：基址寄存器存放当前正执行者的程序：基址寄存器存放当前正执行者的程序地址空间所占分区的始址，限长寄存器存放该地址空间地址空间所占分区的始址，限长寄存器存放该地址空间的长度的长度存储保护存储保护10下限寄存器下限寄存器20002000上限寄存器上限寄存器35003500基址寄存器基址寄存器20002000限长寄存器限长寄存器15001500进程进程idid下限下限+ +上限寄存器上限寄存器基址基址+ +限长寄存器限长寄存器1 11000+19991000+19991000+9991000+9992 22000+35002000+35002000+15002000+15003 34

8、000+50004000+50004000+10004000+1000内存映像内存映像进程1进程2进程3100019992000350040005000正运行的进程是进程正运行的进程是进程2 211存储空间管理策略存储空间管理策略连续存储空间管理连续存储空间管理固定分区存储管理固定分区存储管理 可变分区存储管理可变分区存储管理 非连续存储空间管理非连续存储空间管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理虚拟存储空间管理虚拟存储空间管理虚拟页式存储管理虚拟页式存储管理虚拟段式存储管理虚拟段式存储管理虚拟段页式存储管理虚拟段页式存储管理124.2 4.2

9、 连续存储空间管理连续存储空间管理4.2.1 4.2.1 固定分区存储管理固定分区存储管理 4.2.2 4.2.2 可变分区存储管理可变分区存储管理 4.2.3 4.2.3 伙伴系统伙伴系统4.2.4 4.2.4 主存不足的存储管理技术主存不足的存储管理技术134.2.1 4.2.1 固定分区存储管理固定分区存储管理1.1. 固定分区存储管理的基本思想固定分区存储管理的基本思想0 主存空间被分成数目固定不变的分区，各分主存空间被分成数目固定不变的分区，各分区的大小不等，每个分区只装入一个作业。区的大小不等，每个分区只装入一个作业。2.2. 固定分区存储管理的数据结构固定分区存储管理的数据结构0

10、 主存分配表：指出各分区的起始地址和长度主存分配表：指出各分区的起始地址和长度；0 占用标志：指示此分区是否被使用。占用标志：指示此分区是否被使用。143 3、固定分区存储管理的地址转换和存储保护、固定分区存储管理的地址转换和存储保护 B B下限寄存器下限寄存器逻辑地址逻辑地址CPUCPU绝对地址绝对地址操作系统区操作系统区用户分区用户分区1 1用户分区用户分区2 2用户分区用户分区3 3B+L2B+L2上限寄存器上限寄存器B+L2B+L2越界中断越界中断用户分区用户分区4 4用户分区用户分区5 5用户分区用户分区6 6154 4、固定分区的优缺点、固定分区的优缺点 优点优点0能够解决单道程序

11、运行在并发环境下不能与能够解决单道程序运行在并发环境下不能与CPUCPU速度匹速度匹配的问题配的问题0解决了单道程序运行时主存空间利用率低的问题解决了单道程序运行时主存空间利用率低的问题0实现简单实现简单 缺点缺点0大作业可能无法装入大作业可能无法装入0主存空间利用率不高，会出现内碎片（已分配给某作主存空间利用率不高，会出现内碎片（已分配给某作业剩余的太小而无法利用的内存）业剩余的太小而无法利用的内存）0扩充困难扩充困难0限制多道运行程序的个数限制多道运行程序的个数164.2.2 4.2.2 可变分区存储管理可变分区存储管理 1 1、基本思想：、基本思想：可变分区存储管理是按作业的实际大小来划

12、可变分区存储管理是按作业的实际大小来划分分区，且分区个数也是随机的分分区，且分区个数也是随机的, ,实现多个实现多个作业对主存的共享，进一步提高主存资源利作业对主存的共享，进一步提高主存资源利用率。用率。 17可变分区方式主存分配示例可变分区方式主存分配示例操作系统操作系统作业作业1 1空闲区空闲区作业作业2 2空闲区空闲区4KB4KB10KB10KB46KB46KB52KB52KB128KB128KB操作系统操作系统作业作业1 1空闲区空闲区作业作业2 2空闲区空闲区4KB4KB10KB10KB40KB40KB46KB46KB52KB52KB128KB128KB作业作业3 3操作系统操作系统

13、作业作业1 1空闲区空闲区4KB4KB10KB10KB40KB40KB128KB128KB作业作业3 3182 2、可变分区存储管理数据结构、可变分区存储管理数据结构 可变分区主存分配表可由两张表格组成，可变分区主存分配表可由两张表格组成， 已分配区表已分配区表 未分配区表未分配区表193 3、分配与去配去配算法、分配与去配去配算法A AX XA AX XB BX XB BA AX XA AB BB B将作业占用的存储空间回收，并与上下空闲分区合并，同时修改已分配区表和未分配区表20链表空闲区管理方法链表空闲区管理方法 空闲区开头单元存放本空闲区长度及下个空闲区开头单元存放本空闲区长度及下个空

14、闲区起始地址空闲区起始地址, ,把所有空闲区都链接起来把所有空闲区都链接起来, ,设置第一块空闲区地址指针设置第一块空闲区地址指针, ,让它指向第让它指向第一块空闲区地址。一块空闲区地址。 申请空闲区：沿链查找并取一个长度能满申请空闲区：沿链查找并取一个长度能满足要求的空闲区；足要求的空闲区； 归还空闲区：把此空闲区链入空闲区链表归还空闲区：把此空闲区链入空闲区链表的相应位置。的相应位置。213 3、分配与去配分配算法、分配与去配分配算法1 1）最先适应分配算法（）最先适应分配算法（FFFF）空闲区通常按空闲区通常按地址地址从小到大排列，分配第从小到大排列，分配第一个满足长度要求的空闲区；一个

15、满足长度要求的空闲区；优点：分配从低地址开始，使高地址部分优点：分配从低地址开始，使高地址部分比较少用，以保持一个大空闲区，有利于比较少用，以保持一个大空闲区，有利于大作业的装入；大作业的装入；缺点：分区利用不均衡，回收分区比较麻缺点：分区利用不均衡，回收分区比较麻烦。烦。 222 2）下次适应分配算法（）下次适应分配算法（NFNF）1 1）的变种，每次分配时从未分配区的上次扫描）的变种，每次分配时从未分配区的上次扫描结束处顺序查找。结束处顺序查找。可以解决可以解决1 1）的缺点。）的缺点。3) 3) 最优适应分配算法（最优适应分配算法（BFBF）分配能满足要求的最小区。分配能满足要求的最小区

16、。可以将空闲区按照可以将空闲区按照大小大小从小到大排列，查找第一从小到大排列，查找第一个满足要求的。个满足要求的。优点：主存利用率好。优点：主存利用率好。缺点：分割剩下的空闲区比较小，难以利用；查缺点：分割剩下的空闲区比较小，难以利用；查找时间比较长。找时间比较长。234 4）最坏适应分配算法（）最坏适应分配算法（WFWF）分配能满足要求的最大区；分配能满足要求的最大区；可以将空闲区按照可以将空闲区按照大小大小从大到小排列，查找第一从大到小排列，查找第一个满足要求的。个满足要求的。效率大致等同于最先适应法。效率大致等同于最先适应法。5) 5) 快速适应分配算法快速适应分配算法为经常用到的长度的

17、空闲区设置单独的链表。为经常用到的长度的空闲区设置单独的链表。优点：查找快速；优点：查找快速；缺点：归还时与相邻空闲区的合并即复杂又费时缺点：归还时与相邻空闲区的合并即复杂又费时。 24下表为某系统中的空闲分区表，系统采用可变式分区存储管下表为某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：理策略。现有以下作业序列：96KB96KB，20KB20KB，200KB200KB，分别使，分别使用首次适应、最佳适用和最坏适用算法来处理这个作业序列用首次适应、最佳适用和最坏适用算法来处理这个作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？，试问哪一种算法可以满足该作业序

18、列的请求，为什么？分区号分区号大小大小起始地址起始地址1 132KB32KB100KB100KB2 210KB10KB150KB150KB3 35KB5KB200KB200KB4 4218KB218KB220KB220KB5 596KB96KB530KB530KB例题：例题：FF(N)FF(N)BF(Y)BF(Y)WF(N)WF(N)2/20/122/20/122/20/122/20/121/96/1221/96/122 3/200/183/200/181/96/1221/96/1222/20/1022/20/1021/96/01/96/025可变分区地址转换与存储保护可变分区地址转换与存储保

19、护 基址基址基址寄存器基址寄存器逻辑地址逻辑地址CPUCPU绝对地址绝对地址操作系统区操作系统区空闲分区空闲分区1 1用户作业用户作业1 1空闲分区空闲分区2 2限长限长限长寄存器限长寄存器 限长限长越界中断越界中断26多对基址多对基址/ /限长寄存器限长寄存器 进程进程B B虚虚CPUCPU进程进程A A虚虚CPUCPU物理主存物理主存进程进程A A私有空间私有空间进程进程B B私有空间私有空间共享区共享区重定位寄存器重定位寄存器1 1限长寄存器限长寄存器1 1重定位寄存器重定位寄存器2 2限长寄存器限长寄存器2 2重定位寄存器重定位寄存器1 1限长寄存器限长寄存器1 1重定位寄存器重定位寄

20、存器2 2限长寄存器限长寄存器2 2 多对重定位寄存器支持主存共享多对重定位寄存器支持主存共享274.2.4 4.2.4 主存不足的存储管理技术主存不足的存储管理技术 操作系统操作系统作业作业1 1空闲区空闲区作业作业2 2空闲区空闲区作业作业3 3空闲区空闲区操作系统操作系统作业作业1 1作业作业2 2作业作业3 3空闲区空闲区操作系统操作系统作业作业1 1作业作业2 2作业作业3 3空闲区空闲区作业作业4 41.1.移动技术移动技术: :将分散的空闲区汇集成片，以装入作业将分散的空闲区汇集成片，以装入作业28有关移动问题讨论有关移动问题讨论 移动条件移动条件0在可变分区算法中，随着进程不断

21、的装入和撤销，导致在可变分区算法中，随着进程不断的装入和撤销，导致主存中常常出现分散的小空闲区，称为主存中常常出现分散的小空闲区，称为碎片碎片。0当在未分配区中找不到足够大的空闲区来装入新进程时当在未分配区中找不到足够大的空闲区来装入新进程时，可采用移动技术，将分散的空闲空闲区汇集成片。，可采用移动技术，将分散的空闲空闲区汇集成片。 移动时机移动时机0进程撤销之后释放分区时，如果它不与空闲区邻接，立进程撤销之后释放分区时，如果它不与空闲区邻接，立即实施移动。即实施移动。0进程装入分区时，如果它不与空闲区邻接，立即实施引进程装入分区时，如果它不与空闲区邻接，立即实施引动。动。开销非常大，极少使用

22、开销非常大，极少使用292.2.对换技术对换技术 对换的作用对换的作用0通过将主存和磁盘的进程移出移入，解决主存通过将主存和磁盘的进程移出移入，解决主存容量不足的问题。容量不足的问题。 对换进程的选择对换进程的选择0选择哪个进程换出；选择哪个进程换出；0决定把进程的哪些信息移出去；决定把进程的哪些信息移出去；0需要确定对换时机。需要确定对换时机。30在任何时候只在内存中保留所需的指令和数据在任何时候只在内存中保留所需的指令和数据由用户实现，由用户实现，让不会同时调用的子模块共同使用让不会同时调用的子模块共同使用同一内存区同一内存区F20KD22KE24KB12KC15KA30K常驻常驻A A（

23、30KB30KB）覆盖区覆盖区0 0（15KB15KB）覆盖区覆盖区1 1（24KB24KB）A占用占用BC共用共用DEF共用共用3.3.覆盖技术覆盖技术31碎片碎片连续存储管理的缺点：主存空间利用率低，易产生碎片连续存储管理的缺点：主存空间利用率低，易产生碎片 外部碎片外部碎片：存在分区外，所有内存之和可以满足请求，但：存在分区外，所有内存之和可以满足请求，但不连续不连续 内部碎片内部碎片：存在分区内，但已不能满足任何请求：存在分区内，但已不能满足任何请求 解决外部碎片问题的方法解决外部碎片问题的方法0移动（移动（compactioncompaction）：移动内存内容，以便所有空闲空间合并

24、成）：移动内存内容，以便所有空闲空间合并成一整块一整块0允许物理地址空间为非连续允许物理地址空间为非连续x 分页分页x 分段分段324.3 4.3 分页式存储管理分页式存储管理4.3.1 4.3.1 分页式存储管理的基本原理分页式存储管理的基本原理 4.3.2 4.3.2 快表快表4.3.3 4.3.3 分页式存储空间的分配和去配分页式存储空间的分配和去配4.3.4 4.3.4 分页式存储空间的页面共享和保护分页式存储空间的页面共享和保护4.3.5 4.3.5 多级页表多级页表4.3.6 4.3.6 反置页表反置页表334.3.1 4.3.1 分页式存储管理分页式存储管理l为什么要引进分页技术

25、为什么要引进分页技术? ?l基本原理基本原理 页面：进程逻辑地址空间分成大小相等的区；页面：进程逻辑地址空间分成大小相等的区； 页框（帧、块）：主存物理地址空间分成大小页框（帧、块）：主存物理地址空间分成大小相等的区，其大小跟页面大小相等；相等的区，其大小跟页面大小相等； 装入：页面与面框对应的装入，有几个页面，装入：页面与面框对应的装入，有几个页面，就分配几个页框，但地址不一定连续。就分配几个页框，但地址不一定连续。 逻辑地址形式：页号页内位移逻辑地址形式：页号页内位移 页表和地址转换（后面图）页表和地址转换（后面图） 基本原理基本原理(1)34基本原理基本原理(2)(2)l作业的页面与分给

26、的页框如何建立联系呢？作业的页面与分给的页框如何建立联系呢？l逻辑地址如何变换成物理地址逻辑地址如何变换成物理地址( (页框页框) )呢？呢？l作业的物理地址空间由连续变成分散后，如作业的物理地址空间由连续变成分散后，如何保证程序正确执行呢？何保证程序正确执行呢？使用动态重定位技术，给每个页面设立重定使用动态重定位技术，给每个页面设立重定位寄存器，重定位寄存器的集合便称位寄存器，重定位寄存器的集合便称页表页表。页表是操作系统为每个用户作业建立的，用页表是操作系统为每个用户作业建立的，用来记录程序页面和主存对应页框的对照表。来记录程序页面和主存对应页框的对照表。同时建立作业表，记录每个作业的页表

27、信息同时建立作业表，记录每个作业的页表信息35页页0 0页页1 1页页2 2页页3 31 14 43 37 70 1 2 3页页0 0页页2 2页页1 1页页3 30 1 2 3 4 5 6 7逻辑内存逻辑内存页表页表物理内存物理内存页号页号 帧号帧号帧号帧号物理内存和逻辑内存的分页模型物理内存和逻辑内存的分页模型作业作业页表地址页表地址页表长度页表长度J1J1XXXXXX4 4J2J2XXXXXX6 6作业表作业表36逻辑地址到物理地址的转换逻辑地址到物理地址的转换逻辑地址形式：页号页内位移逻辑地址形式：页号页内位移转换公式：转换公式：物理地址物理地址= =页框号页框号页框长页内位移页框长页

28、内位移37逻辑地址到物理地址的转换逻辑地址到物理地址的转换56120 1 2 3页表页表例：例：说明：页大小为说明：页大小为4B4B，页表如图所示，页表如图所示，将逻辑地址，将逻辑地址0 0、3 3、4 4、1313转换为相转换为相应物理地址应物理地址提示：先计算出页号及页位移提示：先计算出页号及页位移0/4=00/4=00 50 54+0=204+0=203/4=03/4=03 53 54+3=234+3=234/4=14/4=10 60 64+0=244+0=2413/4=313/4=31 21 24+1=94+1=9答案：答案：20、23、24、938练习：逻辑地址到物理地址的转换练习：

29、逻辑地址到物理地址的转换 说明：页大小为说明：页大小为1024B1024B，页表如图所示，页表如图所示，将逻辑地址，将逻辑地址10111011、21482148、30003000、40004000、50125012转换为相应物理地址转换为相应物理地址23160 1 2 3页表页表 答案：答案：30593059、11241124、19761976、70727072、逻、逻辑地址非法辑地址非法1011/1024=01011/1024=01011 21011 21024+1011=30591024+1011=30592148/1024=22148/1024=2100 1100 11024+100=1

30、1241024+100=11243000/1024=23000/1024=2952 1952 11024+952=19761024+952=19764000/1024=34000/1024=3928 6928 61024+928=70721024+928=70725012/1024=45012/1024=4916 916 页号页号4 4不存在不存在394.3.24.3.2相联存储器和相联存储器和快表快表 页表存放在主存中。页表存放在主存中。 当要按给定的逻辑地址进行读当要按给定的逻辑地址进行读/ /写时，必须写时，必须访问两次主存。第一次按页号读出页表中访问两次主存。第一次按页号读出页表中相应

31、栏内容的块号及页内位移，第二次根相应栏内容的块号及页内位移，第二次根据计算出来的绝对地址进行读据计算出来的绝对地址进行读/ /写，降低了写，降低了运算速度，这比通常执行指令的速度慢了运算速度，这比通常执行指令的速度慢了一倍。一倍。 404.3.24.3.2相联存储器和相联存储器和快表快表 为了提高运算速度，通常设置一个专用的为了提高运算速度，通常设置一个专用的高速缓冲存储器，用来存放最近访问的部高速缓冲存储器，用来存放最近访问的部分页表。这种高速存储器称为相联存储器分页表。这种高速存储器称为相联存储器（associative memoryassociative memory）, ,也称也称(

32、(翻译后备翻译后备缓冲：缓冲：translation lookaside translation lookaside buffer,TLBbuffer,TLB) )，它成为分页式存储管理的一，它成为分页式存储管理的一个重要组成部分。个重要组成部分。 存放在相联存储器中的页表称快表。存放在相联存储器中的页表称快表。 41采用相联存储器的地址转换采用相联存储器的地址转换假定访问主存时间为假定访问主存时间为100100毫微秒，访问相联存储器毫微秒，访问相联存储器时间为时间为2020毫微秒，相联存储器为毫微秒，相联存储器为3232个单元时快表个单元时快表命中率可达命中率可达90%90%，按逻辑地址存取

33、的平均时间为：，按逻辑地址存取的平均时间为：（2020100100）90%90%(20+100+100)(20+100+100)(1-90%)(1-90%)130130比两次访问主存的时间比两次访问主存的时间1001002 2200200下降了三成多下降了三成多。424.3.3 4.3.3 分页式存储空间的分配和去配分页式存储空间的分配和去配(1)(1) 位示图法位示图法0每位与一帧相对应，用每位与一帧相对应，用0/10/1表示对应块为空闲表示对应块为空闲/ /已占用，用另一专门字记录当前空闲块数。已占用，用另一专门字记录当前空闲块数。 链表方法链表方法0每个表项包含：每个表项包含：x进程占用

34、区（进程占用区（P P）还是空闲区（）还是空闲区（H H）x起始地址起始地址x长度长度x指向下一表项的指针指向下一表项的指针43主存分配的位示图和链表方法主存分配的位示图和链表方法444.3.4 4.3.4 分页存储空间的页面共享和保护分页存储空间的页面共享和保护(1)(1) 数据共享数据共享0允许不同进程对共享的数据页用不同的页号，允许不同进程对共享的数据页用不同的页号，只要让各自页表中的有关表项指向共享的数据只要让各自页表中的有关表项指向共享的数据页框；页框； 标志位保护方法标志位保护方法0在页表中增加标志位，指出此页的信息只读在页表中增加标志位，指出此页的信息只读/ /读写读写/ /只可

35、执行只可执行/ /不可访问等。不可访问等。45 分页技术分页技术不会不会产生产生外部碎片外部碎片，但，但会会产生产生内内部碎片部碎片 分页的重要特点是用户观点的内存和实际分页的重要特点是用户观点的内存和实际的物理内存的分离的物理内存的分离 分页可以共享共同代码分页可以共享共同代码分页内存管理方案小结分页内存管理方案小结464.4 4.4 分段式存储管理分段式存储管理4.4.1 4.4.1 程序的分段结构程序的分段结构4.4.2 4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理4.4.3 4.4.3 段的共享和保护段的共享和保护4.4.4 4.4.4 分段和分页的比较分段和分页的比较

36、474.4.1 4.4.1 程序的分段结构程序的分段结构 分段存储管理引入的主要原因分段存储管理引入的主要原因0满足用户（程序员）编程和使用上的要求。满足用户（程序员）编程和使用上的要求。即将程序的逻辑地址空间按用户程序特点划分即将程序的逻辑地址空间按用户程序特点划分成段，为作业的每一段分配一个连续的主存空成段，为作业的每一段分配一个连续的主存空间，而各段之间不一定连续。间，而各段之间不一定连续。 模块化程序设计的分段结构（下页图）模块化程序设计的分段结构（下页图） 分页存储管理分页存储管理-一维地址结构一维地址结构 分段存储管理分段存储管理-二维地址结构二维地址结构48模块化程序设计的分段结

37、构模块化程序设计的分段结构 子程序段子程序段X X数组段数组段A Acall Xcall X( (调用调用X X段的入口段的入口E)E)call Ycall Y( (调用调用Y Y段的入口段的入口F)F)load 1,Aload 1,A ( (调用数组段调用数组段AG)AG)主程序段主程序段E E：F F：子程序段子程序段Y YG G：工作区段工作区段494.4.2 4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理(1)(1)l两维逻辑地址两维逻辑地址l段表段表l段表指出主存中各分段的段号、段起始地址段表指出主存中各分段的段号、段起始地址和段长度，起到基址和段长度，起到基址/ /限

38、长寄存器的作用。限长寄存器的作用。段号段号段内地址段内地址504.4.2 4.4.2 分段式存储管理的数据结构分段式存储管理的数据结构段号始址长度第0段XXXXXX第一段XXXXXX作业名段表地址段表长度AXXXXXBXXXXX段表：作业表：51段表：将二维的逻辑地址映射为一维物理地址段表：将二维的逻辑地址映射为一维物理地址段基地址：包含该段在内存中的开始物理地址段基地址：包含该段在内存中的开始物理地址段界限：指定该段的长度段界限：指定该段的长度逻辑地址：段号逻辑地址：段号s s段内偏移段内偏移d d逻辑地址到物理地址的转换逻辑地址到物理地址的转换1)1) 段号与段表长度进行比较，若段号超过了

39、段表长度段号与段表长度进行比较，若段号超过了段表长度，则越界（非法地址），否则转，则越界（非法地址），否则转2 2）2)2) 根据段表始址和段号计算出该段对应段表项的位置根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址，检查段内地址，从中读出该段在内存的起始地址，检查段内地址是否超过该段的段长，若超过则越界（非法地址）是否超过该段的段长，若超过则越界（非法地址），否则转，否则转3 3）3)3) 将该段的起始地址与段内位移相加，从而得到要访将该段的起始地址与段内位移相加，从而得到要访问的物理地址问的物理地址逻辑地址到物理地址转换逻辑地址到物理地址转换52段式存储管理的地

40、址转换和存储保护段式存储管理的地址转换和存储保护 段控制寄存器段控制寄存器 段表始址段表始址 段表长度段表长度 段号段号s s 位移位移d d 段长段长 基址基址 物理地址物理地址越界越界? ? 段表段表53逻辑地址到物理地址转换例逻辑地址到物理地址转换例说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻辑地址转换为相应物理地址物理地址答案：见表答案：见表3 3段号段号 内存起始内存起始地址地址段长段长0 02192196006001 12300230014142 290901001003 3132713275805804 4195219529696段段号

41、号段内位段内位移移2 288884 4100100178178非法非法 表表1 表表2 表表390+881009654说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻辑地址转换为相应物理地址物理地址答案：见表答案：见表3 3逻辑地址到物理地址转换练习逻辑地址到物理地址转换练习段号段号段内位移段内位移0 04304301 110102 25005003 34004004 41121125 53232段号段号内存起始地址内存起始地址段长段长0 02102105005001 12350235020202 210010090903 313501350590590

42、4 4193819389595 表表1 表表264064023602360非法非法17501750非法非法非法非法表表3210+4302350+10500901350+40011295段号段号5不存在不存在554.4.3 4.4.3 段的共享段的共享 多对基址多对基址/ /限长寄存器限长寄存器 段的共享，是通过不同作业段表中的项指段的共享，是通过不同作业段表中的项指向同一个段基址来实现。向同一个段基址来实现。 几道作业共享的例行程序就可放在一个段几道作业共享的例行程序就可放在一个段中，只要让各道作业的共享部分有相同的中，只要让各道作业的共享部分有相同的基址基址/ /限长值。限长值。 对共享段的

43、信息必须进行保护。对共享段的信息必须进行保护。 564.4.4 4.4.4 分段和分页的比较分段和分页的比较 分段是信息的逻辑单位，由源程序的逻辑分段是信息的逻辑单位，由源程序的逻辑结构所决定，用户可见，分页是信息的物结构所决定，用户可见，分页是信息的物理单位，与源程序的逻辑结构无关，用户理单位，与源程序的逻辑结构无关，用户不可见。不可见。 段长可根据用户需要来规定，段起始地址段长可根据用户需要来规定，段起始地址可从任何主存地址开始。页长由系统确定可从任何主存地址开始。页长由系统确定，页面只能以页大小的整倍数地址开始。，页面只能以页大小的整倍数地址开始。 分段方式中，源程序分段方式中，源程序(

44、 (段号，段内位移段号，段内位移) )经经连结装配后地址仍保持二维结构。分页方连结装配后地址仍保持二维结构。分页方式中，源程序式中，源程序( (页号，页内位移页号，页内位移) )经连结装经连结装配后地址变成了一维结构。配后地址变成了一维结构。574.5 4.5 虚拟存储管理虚拟存储管理4.5.1 4.5.1 虚拟存储管理的概念虚拟存储管理的概念4.5.2 4.5.2 请求分页虚拟存储管理请求分页虚拟存储管理4.5.3 4.5.3 请求分段虚拟存储管理请求分段虚拟存储管理4.5.4 4.5.4 请求段页式虚拟存储管理请求段页式虚拟存储管理584.5.1 4.5.1 虚拟存储管理的概念虚拟存储管理

45、的概念常规存储器管理方式的特征常规存储器管理方式的特征 一次性一次性 ：即作业在运行前需一次性地全部装入：即作业在运行前需一次性地全部装入 内存内存 驻留性：作业装入内存后，便一直驻留在内存中驻留性：作业装入内存后，便一直驻留在内存中 直至作业运行结束直至作业运行结束 缺点：缺点：由于一次性装入及驻留性，使许多在程序运行中由于一次性装入及驻留性，使许多在程序运行中不用或暂不用的程序（数据）占据了大量的内存不用或暂不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业无法装入运行。空间，而一些需要运行的作业无法装入运行。 594.5.1 4.5.1 虚拟存储管理的概念虚拟存储管理的概念解决

46、方法：解决方法： 在许多情况下不需要将整个程序放到内存中，可在许多情况下不需要将整个程序放到内存中，可以先放在辅存中，等到用时再调入主存以先放在辅存中，等到用时再调入主存 虚拟内存（虚拟内存（virtual memoryvirtual memory）：允许进程的执行）：允许进程的执行不必完全在内存中，程序的逻辑地址空间可以比不必完全在内存中，程序的逻辑地址空间可以比物理地址空间大。物理地址空间大。60虚拟存储器虚拟存储器虚拟存储器的定义：虚拟存储器的定义：采用自动实现部分装入和部分对换功能，采用自动实现部分装入和部分对换功能，为用户提供一个比物理主存容量大得多的为用户提供一个比物理主存容量大得

47、多的，可寻址的一种，可寻址的一种“主存储器主存储器”。特征：特征： 多次性、对换性、虚拟性多次性、对换性、虚拟性 61虚拟存储器的概念图虚拟存储器的概念图 逻辑地址空间逻辑地址空间处理器处理器虚地址虚地址存储存储管理管理部件部件实地址实地址主存主存辅存辅存物理地址空间物理地址空间62程序的局部性原理程序的局部性原理 早在早在19681968年，年，Denning.PDenning.P就曾指出：程序在执行时就曾指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问序的执行仅局限于某个部分；相应地，它所访问的

48、存储空间也局限于某个区域，这一规律称为局的存储空间也局限于某个区域，这一规律称为局部性原理。部性原理。 局部性体现在两个方面：局部性体现在两个方面：时间局部性：最近访问过的程序代码和数据很时间局部性：最近访问过的程序代码和数据很快又被访问。快又被访问。空间局部性：某存储单元被使用之后，其相邻空间局部性：某存储单元被使用之后，其相邻的存储单元也很快被使用。的存储单元也很快被使用。63实现虚拟存储器须解决的问题实现虚拟存储器须解决的问题l 主存辅存统一管理问题主存辅存统一管理问题l 逻辑地址到物理地址的转换问题逻辑地址到物理地址的转换问题l 部分装入和部分对换问题部分装入和部分对换问题64虚拟存储

49、管理实现技术虚拟存储管理实现技术l 请求分页虚拟存储管理请求分页虚拟存储管理l 请求分段虚拟存储管理请求分段虚拟存储管理l 请求段页式虚拟存储管理请求段页式虚拟存储管理654.5.2 4.5.2 请求分页虚拟存储系统请求分页虚拟存储系统1.1.请求分页虚拟存储系统的硬件支撑请求分页虚拟存储系统的硬件支撑(1)(1)主存管理单元主存管理单元MMUMMU（主存管理部件）完成逻（主存管理部件）完成逻辑地址到物理地址的转换功能，它接受虚辑地址到物理地址的转换功能，它接受虚拟地址作为输入，物理地址作为输出，直拟地址作为输入，物理地址作为输出，直接送到总线上，对主存单元进行寻址。接送到总线上，对主存单元进

50、行寻址。 66分页式虚拟存储系统的硬件支撑分页式虚拟存储系统的硬件支撑(2)(2) CPUCPUMMUMMU内内存存CPUCPU把逻辑地把逻辑地址送至址送至MMUMMUMMUMMU把物理地址送至主存把物理地址送至主存 MMU MMU的位置、功能和的位置、功能和1616个个4KB4KB页页面情况下面情况下MMUMMU的内部操作的内部操作CPUCPU送入的送入的逻辑地址逻辑地址(8196)(8196) 1 1 0 0 0 0 0 0 0 0 0 0 1 0 01 1 0 0 0 0 0 0 0 0 0 0 1 0 0MMUMMU送出的物理地址送出的物理地址0 010 10 010 11 001 1

51、1 001 12 110 12 110 13 000 13 000 14 100 14 100 15 011 15 011 16 000 06 000 07 000 07 000 08 101 18 101 19 000 09 000 0页号页号 页框号页框号 在主存否在主存否0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 00 0 1 0 0 0 0 0 0 0 0 0 0 1 0 067MMUMMU主要功能主要功能(1)(1)管理硬件页表基址寄存器。管理硬件页表基址寄存器。(2)(2)分解逻辑地址。分解逻辑地址。(3)(3)管理快管理快表表TLBTLB。(4)(4)访问页表。访

52、问页表。(5)(5)发出缺页中断或越界中断，并将控制权交给内发出缺页中断或越界中断，并将控制权交给内核存储管理处理。核存储管理处理。(6)(6)设置和检查页表中各个特征位。设置和检查页表中各个特征位。682.2.请求分页虚拟存储系统的基本原理请求分页虚拟存储系统的基本原理 分页式虚存不把作业信息分页式虚存不把作业信息( (程序和数据程序和数据) )全部装入全部装入主存，仅装入立即使用的页面，在执行过程中访主存，仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再从磁问到不在主存的页面时，产生缺页中断，再从磁盘动态地装入盘动态地装入 。 怎样才能发现页面不在主存中呢怎样才能

53、发现页面不在主存中呢? ?怎样处理这种怎样处理这种情况呢情况呢? ?0采用的办法是：扩充页表的内容采用的办法是：扩充页表的内容, ,增加驻留标志位和页增加驻留标志位和页面辅存的地址等信息面辅存的地址等信息。69页式虚拟存储管理页表扩展页式虚拟存储管理页表扩展其它标志：其它标志： 访问权限位访问权限位 修改位（修改位（ModifiedModified） 引用位（引用位（RenferencedRenferenced）页号页号页框号页框号驻留标志驻留标志辅存地址辅存地址其它标志其它标志70分解分解地址地址命命中中访访问问有快表，查快表有快表，查快表没没命命中中页表命中页表命中未命中发缺页中断未命中发

54、缺页中断调页调页装入装入、改表、改表无无快快表表则则查查页页表表装入快表装入快表请求分页虚存地址转换过程请求分页虚存地址转换过程(1)(1) 逻辑空间地址逻辑空间地址主存主存( (用户区用户区) )CPUCPU逻辑地址逻辑地址快表快表主存主存( (系统区系统区) )运行进程页运行进程页表表辅存辅存缺页中断处理缺页中断处理MMUMMU运行进程页表基址运行进程页表基址运行进运行进程映象程映象进程切换时装入进程切换时装入物理地址物理地址页框页框 页内地址页内地址页号页号 页内地址页内地址主存主存71请求分页虚存地址转换过程请求分页虚存地址转换过程(2)(2)查快表查快表有登记有登记无登记无登记查页表

55、查页表登记入快表登记入快表发缺页中断发缺页中断在主存在主存在辅存在辅存形成绝对地址形成绝对地址继续执行指令继续执行指令重新执行重新执行被中断指令被中断指令恢复现场恢复现场调整页表和调整页表和主存分配表主存分配表装入所需页面装入所需页面主存有空闲块主存有空闲块保护现场保护现场有有选择调出页面选择调出页面该页是否修改该页是否修改未修改未修改已修改已修改把该页写回把该页写回辅存相应位置辅存相应位置操作系统操作系统硬件硬件逻辑地址逻辑地址无无72请求页式虚拟存储系统优缺点请求页式虚拟存储系统优缺点l优点：作业的程序和数据可按页分散存放优点：作业的程序和数据可按页分散存放在主存中，减少移动开销，有效解决

56、了碎在主存中，减少移动开销，有效解决了碎片问题片问题; ;既有利于改进主存利用率，又有利既有利于改进主存利用率，又有利于多道程序运行。于多道程序运行。l缺点：要有硬件支持，要进行缺页中断处缺点：要有硬件支持，要进行缺页中断处理，机器成本增加，系统开销加大。理，机器成本增加，系统开销加大。733.3.页面装入策略和页面清除策略页面装入策略和页面清除策略l页面装入主存页面装入主存, ,有两种策略：有两种策略：l请页式调度：仅调入所需页面请页式调度：仅调入所需页面l预调式调度：使用前预先调入若干页预调式调度：使用前预先调入若干页l何时把一个修改过的页面写回辅存储器，何时把一个修改过的页面写回辅存储器

57、，有两种策略：有两种策略：l请页式清除：仅当一页被选中进行替换且被请页式清除：仅当一页被选中进行替换且被修改过，才写回磁盘。修改过，才写回磁盘。l预清除：成批进行，所有预清除：成批进行，所有 被更改过的页面，被更改过的页面，在需要替换前把它们都写回磁盘。在需要替换前把它们都写回磁盘。744.4.页面分配策略页面分配策略 系统为进程分配主存系统为进程分配主存, ,需考虑因素需考虑因素: :分给进程的空间越小分给进程的空间越小, ,同一时间处于主存的进程同一时间处于主存的进程就越多，至少有一个进程处于就绪态的可能性就就越多，至少有一个进程处于就绪态的可能性就越大越大如果进程只有小部分在主存里如果进

58、程只有小部分在主存里, ,即使局部性很好即使局部性很好, ,缺页中断率还会相当高缺页中断率还会相当高因程序的局部性原理，分给进程的主存超过一定因程序的局部性原理，分给进程的主存超过一定限度后，再增加主存空间限度后，再增加主存空间, ,不会明显降低进程的不会明显降低进程的缺页中断率缺页中断率。75页面分配策略：固定分配页面分配策略：固定分配 进程保持页框数固定不变进程保持页框数固定不变, ,称固定分配称固定分配; ; 进程创建时进程创建时, ,根据进程类型和程序员的要求根据进程类型和程序员的要求决定页框数决定页框数, ,只要有一个缺页中断产生只要有一个缺页中断产生, ,进进程就会有一页被替换。程

59、就会有一页被替换。76页面分配策略：可变分配页面分配策略：可变分配 进程分得的页框数可变进程分得的页框数可变, , 称可变分配称可变分配; ; 进程执行的某阶段缺页率较高进程执行的某阶段缺页率较高, ,说明目前说明目前局部性较差，系统可多分些页框以降低缺局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前的局部性较好页率，反之说明进程目前的局部性较好, ,可减少分给进程的页框数可减少分给进程的页框数775.5.缺页中断率缺页中断率l页面替换页面替换l当主存空间已满又必须装入新页时，选择主存当主存空间已满又必须装入新页时，选择主存中某页淘汰。中某页淘汰。l页面淘汰算法页面淘汰算法l选择哪页

60、被淘汰的算法。选择哪页被淘汰的算法。l“抖动抖动”(Thrashing)(Thrashing)现象现象l刚被淘汰的页面立即又要调用，调入不久又被刚被淘汰的页面立即又要调用，调入不久又被淘汰，淘汰不久再被调入淘汰，淘汰不久再被调入如此反复，整个系如此反复，整个系统频繁调页，使得几乎无时间进行计算任务。统频繁调页，使得几乎无时间进行计算任务。78影响缺页中断率的因素影响缺页中断率的因素(1) 假定作业假定作业p p共计共计n n页，系统分配给它的主存页，系统分配给它的主存块只有块只有m m块（块（mnmn）。如果作业）。如果作业p p在运在运行中成功的访问次数为行中成功的访问次数为S S， 不成功