第五章 存储管理_new

《第五章 存储管理_new》由会员分享，可在线阅读，更多相关《第五章 存储管理_new（94页珍藏版）》请在金锄头文库上搜索。

1、存储管理第五章第五章 存储管理存储管理l存储管理主要研究进程如何占用主存资源。存储管理主要研究进程如何占用主存资源。l设计操作系统的重要目标之一是提高计算机设计操作系统的重要目标之一是提高计算机资源的利用率，而提高计算机资源利用率的资源的利用率，而提高计算机资源利用率的根本途径是采用多道程序设计技术。因此，根本途径是采用多道程序设计技术。因此，必须合理地管理主存储空间，使尽可能多的必须合理地管理主存储空间，使尽可能多的进程能够同时存放于主存以竞争进程能够同时存放于主存以竞争CPU，保证，保证CPU和和I/O设备足够繁忙。设备足够繁忙。存储管理第五章第五章 存储管理存储管理l存储管理所研究的内容

2、主要包括三个方面：存储管理所研究的内容主要包括三个方面：l取：将哪个进程（或进程的某些部分）从辅存调入主存取：将哪个进程（或进程的某些部分）从辅存调入主存l放：研究将取来的进程按何种方式放在主存的什么地方放：研究将取来的进程按何种方式放在主存的什么地方l替换：研究将哪个进程（或进程的某部分）暂时从主存替换：研究将哪个进程（或进程的某部分）暂时从主存移到辅存，以腾出主存空间供其他进程占用。移到辅存，以腾出主存空间供其他进程占用。l这三方面中，这三方面中，“放放”是存储管理的基础。是存储管理的基础。l目前，目前，“放放”的技术可归结成两类：一类是连续的，的技术可归结成两类：一类是连续的，即运行的程

3、序和数据必须放在主存的一片连续空间即运行的程序和数据必须放在主存的一片连续空间中；另一类是不连续的，即运行的程序和数据可以中；另一类是不连续的，即运行的程序和数据可以放在主存的多个不相邻的块中。放在主存的多个不相邻的块中。存储管理第五章第五章 存储管理存储管理5.1连续空间分配连续空间分配单道连续分配单道连续分配多道固定划分法多道固定划分法多道连续可变划分法多道连续可变划分法5.2不连续空间分配不连续空间分配页式管理页式管理段式管理段式管理段页式管理段页式管理5.3虚拟内存管理虚拟内存管理存储管理5.1连续空间分配连续空间分配在早期的操作系统设计中，都是采用连续在早期的操作系统设计中，都是采用

4、连续空间分配的策略。早期操作系统中还没有空间分配的策略。早期操作系统中还没有引入进程概念，主存分配还是以作业（相引入进程概念，主存分配还是以作业（相当于进程）为单位进行的。当于进程）为单位进行的。存储管理内存空间安排内存空间安排5.1.15.1.1单道连续分配单道连续分配特点：任一时刻内存只有一道作业，该任一时刻内存只有一道作业，该作业连续存放于内存中。作业连续存放于内存中。一、空间划分与保护操作系统操作系统用户程序用户程序0a aa+1a+1n n界界地址寄存器地址寄存器存储管理界地址寄存器界地址寄存器主存主存A a?A a?cpucputruetruefalsefalse地址地址A A终止

5、程序运行终止程序运行越界检查机构：用户程序每次执行访存指用户程序每次执行访存指令，硬件越界检查机构将访问的地址与界令，硬件越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止地址寄存器中的值比较。若越界，则终止其执行。其执行。存储管理二、覆盖（overlay） 因内存小于作业的程序空间而引入覆盖。将用户因内存小于作业的程序空间而引入覆盖。将用户空间划分成一个固定区和多个覆盖区。主程序放空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。固定区，依次调用的子程序则放在同一个覆盖区。首先将那些即将要用的段放在覆盖区，其他段放首先将那些即将要用的段放在覆

6、盖区，其他段放在辅存，在需要调用前通过特定系统调用将其调在辅存，在需要调用前通过特定系统调用将其调入占用覆盖区，替换覆盖区中原有的段。入占用覆盖区，替换覆盖区中原有的段。操作系统提供覆盖系统调用函数，操作系统提供覆盖系统调用函数，由用户编程序由用户编程序时考虑调用。时考虑调用。存储管理例如：某作业各过程间关系如下：例如：某作业各过程间关系如下：操作系统操作系统固定区固定区(4k)(4k)覆盖区覆盖区(6k)(6k)覆盖区覆盖区(10k)(10k)A(4k)A(4k)E(10k)E(10k)D(6k)D(6k)C(4k)C(4k)B(6k)B(6k)F(8k)F(8k)存储管理覆盖技术的主要特点

7、是打破了必须将一个作业的覆盖技术的主要特点是打破了必须将一个作业的全部信息装入主存后才能运行的限制。在一定程全部信息装入主存后才能运行的限制。在一定程度上解决了小主存运行大作业的矛盾。度上解决了小主存运行大作业的矛盾。采用覆盖技术是把解决空间不足的问题交给了用采用覆盖技术是把解决空间不足的问题交给了用户。操作系统提供帮助用户将覆盖段调入主存的户。操作系统提供帮助用户将覆盖段调入主存的系统调用，但用户自己必须说明覆盖段，并安排系统调用，但用户自己必须说明覆盖段，并安排调入覆盖段，由此可见覆盖技术用户参与过多，调入覆盖段，由此可见覆盖技术用户参与过多，会给用户带来麻烦。会给用户带来麻烦。存储管理基

8、本思想：将处于等待状态将处于等待状态( (等等I/O)I/O)或就绪或就绪( (等等CPU)CPU)状态的进程从主存换出到辅存，把将状态的进程从主存换出到辅存，把将要执行的进程移入主存。要执行的进程移入主存。三、交换交换要花费较长的时间。比如，辅存采用磁交换要花费较长的时间。比如，辅存采用磁鼓，平均延迟时间为鼓，平均延迟时间为8ms，传输速度为，传输速度为250000b/s，用户空间为，用户空间为20K，则一次交换活，则一次交换活动需要动需要2（8+100020/250000）=179ms。存储管理当作业处于等待状态而准备换出时，应注意该当作业处于等待状态而准备换出时，应注意该作业是否满足换出

9、条件。如果一个作业正在进作业是否满足换出条件。如果一个作业正在进行行I/OI/O活动则不能换出，否则该作业的活动则不能换出，否则该作业的I/OI/O数据数据区将被新换出的作业占用，导致错误。应在区将被新换出的作业占用，导致错误。应在I/OI/O活动结束后才能换出。活动结束后才能换出。存储管理特点：任一时刻内存可有多道作业，每道作任一时刻内存可有多道作业，每道作业连续存放于内存业连续存放于内存. .操作系统操作系统U1U1.UnUn5.1.2 5.1.2 多道固定划分法多道固定划分法一、空间划分及保护 将用户内存将用户内存空间分成长度空间分成长度固定的若干块固定的若干块。用用户户空空间间存储管理

10、常用的基本概念1.物理地址空间和逻辑地址空间 物物理理地地址址空空间间（也也称称内内存存空空间间、绝绝对对地地址址空空间间或或实实空空间间或或存存储储空空间间）：是是指指主主存存中中物物理理单单元元的的集集合合。这这些些单单元元的的编编号号称称为为物物理理地地址址或绝对地址。或绝对地址。 逻逻辑辑地地址址空空间间（也也称称相相对对地地址址空空间间、虚虚空空间间或或地地址址空空间间）：当当对对源源程程序序进进行行编编译译时时，编编译译后后一一个个目目标标程程序序所所限限定定的的地地址址范范围围称称为为该该作业的逻辑地址空间。作业的逻辑地址空间。作作业业运运行行时时不不能能按按其其逻逻辑辑地地址址

11、访访问问内内存存单单元元，而而应应按按相相应应的的物物理理地地址址访访问问，需需要要进进行行逻逻辑辑地址到物理地址的转换。地址到物理地址的转换。存储管理存储管理2.地址重定位 当当一一个个地地址址装装入入与与其其地地址址空空间间不不一一致致的的存存储储空空间间中中，就就得得要要地地址址变变换换。也也就就是是说说将将逻逻辑辑地地址址映映射射为为物物理理地地址址，把把这这种作法叫做地址重定位。种作法叫做地址重定位。存储管理 根根据据对对地地址址变变换换进进行行的的时时间间及及采采用用的的技技术术手手段段的的不不同同，可可把把地地址址重重定定位位分分为为静静态态重重定定位位和和动动态态重重定位两类。

12、定位两类。静静态态重重定定位位：是是指指在在程程序序运运行行之之前前由由装装入入程程序序完完成成的的重重定定位位过过程程。在在装装入入一一个个作作业业时时，把把作作业业中中的的指指令令地地址址全全部部转转换换为为绝绝对对地地址址（地地址址转转换换工工作作是是在在作作业业执执行行前前集集中中一一次次完完成成的的）在在作作业业执执行行过过程程中中就就无无须须再再进进行行地地址址转转换换工工作作。 原原地地址址+ +目标代码所在主存起始地址目标代码所在主存起始地址 动动态态重重定定位位：是是在在程程序序执执行行过过程程中中，需需要要硬硬件件地地址址转转换换机机制制实实现现，在在执执行行访访存存指指令

13、令时时将将“原原地址地址+ +目标代码所在主存起始地址目标代码所在主存起始地址”后进行访问。后进行访问。 存储管理利用一个重定位寄存器。该寄存器的值由调度程序根据作业利用一个重定位寄存器。该寄存器的值由调度程序根据作业分配到的存储空间的起始地址来设定。在具有这种地址变换分配到的存储空间的起始地址来设定。在具有这种地址变换机构的计算机系统中，当作业执行时，不是根据机构的计算机系统中，当作业执行时，不是根据CPUCPU给出的给出的逻辑地址去访问主存，而是将逻辑地址与重定位寄存器中的逻辑地址去访问主存，而是将逻辑地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。内容相加后得到的地址作为访

14、问主存的地址。存储管理静态地址重定位静态地址重定位主要优点：无需增加硬件地址变换机构，因而可在一主要优点：无需增加硬件地址变换机构，因而可在一般计算机上实现般计算机上实现 主要缺点：要求给每个作业分配一个连续的存储空间，主要缺点：要求给每个作业分配一个连续的存储空间，且在作业的整个执行期间不能再移动，因而也就不能且在作业的整个执行期间不能再移动，因而也就不能实现重新分配主存。实现重新分配主存。动态地址重定位动态地址重定位主要优点有：主要优点有：用户作业不要求分配连续的存储空间。用户作业不要求分配连续的存储空间。用户作业在执行过程中，可以动态申请存储空用户作业在执行过程中，可以动态申请存储空间和

15、在主存中移动。间和在主存中移动。主要缺点有：主要缺点有：需要附加的硬件支持。需要附加的硬件支持。实现存储管理的软件算法比较复杂实现存储管理的软件算法比较复杂。存储管理1.上下界寄存器和地址检查机构。当作业当作业被调度运行时，作业在内存中的上下界地被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次执行访存指令时，址送上下界寄存器，每次执行访存指令时，地址检查机构作越界检查。作业程序要是地址检查机构作越界检查。作业程序要是绝对地址或静态重定位的。绝对地址或静态重定位的。CPUCPU主存主存下界寄存器下界寄存器上界寄存器上界寄存器 TrueTrueTrueTrue地址地址A AF F F F

16、程序性异常程序性异常地址访问保护有两种方式：地址访问保护有两种方式：存储管理2.基址寄存器、长度寄存器和动态地址转换机构。当作业被调度运行时，将作业所当作业被调度运行时，将作业所占内存基址及长度送基址、长度寄存器，占内存基址及长度送基址、长度寄存器，每次执行访存指令时，先看访问地址是否每次执行访存指令时，先看访问地址是否小于长度，然后小于长度，然后+ +基址进行访存。用户程基址进行访存。用户程序代码是动态重定位的。序代码是动态重定位的。CPUCPU主存主存基地址寄存器基地址寄存器长度寄存器长度寄存器 + +TrueTrue地址地址A AF F 程序性异常程序性异常存储管理二、作业存储调度在多道

17、固定划分法下，作业调度一般分为多队列法在多道固定划分法下，作业调度一般分为多队列法和单队列法。和单队列法。多队列法是指每个存储区对应一个作业队列，在作多队列法是指每个存储区对应一个作业队列，在作业到达后，按作业的大小在对应队列中排队。业到达后，按作业的大小在对应队列中排队。单队列法是指系统中仅保持一个作业队列。单队列法是指系统中仅保持一个作业队列。例如：总存储量为例如：总存储量为32KB，操作系统占，操作系统占10KB，用户，用户空间被划分成长度为空间被划分成长度为4KB、6KB、12KB三块。作业三块。作业要求的存储量若未超过这三个存储量，则分别进入要求的存储量若未超过这三个存储量，则分别进

18、入相应的队列相应的队列1、队列、队列2、队列、队列3。存储管理二、作业存储调度OS4k6k12kOS4k6k12k.7k3k4k5k.3k4k3k2k.5k6k.7k10k11k8k多多队队列列法法单单队队列列法法存储管理三、存储碎片 内部碎片：内部碎片：内存某存储区间大于其存放作内存某存储区间大于其存放作 业空间的部分。业空间的部分。 外部碎片：外部碎片：内存某存储区间容不下要运行内存某存储区间容不下要运行 的作业时。的作业时。OS12k4k3K内部碎片内部碎片OSOS4k4k6k6k12k12k作业长度：作业长度：5K5K、8K8K、12K12K外部碎片外部碎片存储管理一、管理方法5.1.

19、3 5.1.3 多道连续可变划分法多道连续可变划分法特点：多道、连续、但不固定划分内存。多道、连续、但不固定划分内存。 系统设置一个空闲块队列，初始状态时队系统设置一个空闲块队列，初始状态时队列中只有一个连续的空闲块。作业到达后，列中只有一个连续的空闲块。作业到达后，以某种策略分配空间。作业撤离时，将释放以某种策略分配空间。作业撤离时，将释放的空间加入空闲队列。的空间加入空闲队列。存储管理举例：假设任一时间段内，内存中每一作业举例：假设任一时间段内，内存中每一作业的运行时间片相等。的运行时间片相等。作业到来次序作业到来次序 所需存储量所需存储量 运行时间运行时间 1 60 10 2 100 5

20、 3 30 20 4 70 8 5 50 15OS0 40 256J1J2J3J4J5存储管理分配：调度程序为选中的作业分配存储空间，则在可用块集合中按某种策略选择一个大小满足该用户作业要求的可用可分配给用户。分配策略包括分配策略包括首次满足法首次满足法/ /最佳满足法最佳满足法/ /最大满足最大满足法法，在找到合适的空闲块后，从其中将作业大小，在找到合适的空闲块后，从其中将作业大小的空间分给作业，而剩余部分挂入空闲队列。的空间分给作业，而剩余部分挂入空闲队列。下面下面F F是空闲块集合是空闲块集合; size(k); size(k)为块为块k k的大小的大小; size(v); size(v

21、)为为用户所需空间。用户所需空间。1.1.if if 所有属于所有属于F F的的k k，均有均有size(k)size(v),size(k)size(v),则失败。则失败。2.2.否则按某一策略选出否则按某一策略选出k k，使得使得size(k)size(v).size(k)size(v).3.3.F = F k;F = F k;分配与回收存储空间的算法：分配与回收存储空间的算法：存储管理回收： 当作业结束时，收回作业所占空间，当作业结束时，收回作业所占空间，将此块链入空闲队列。将此块链入空闲队列。 若空闲队列中原来有与此块的相邻块，若空闲队列中原来有与此块的相邻块，则把这些块合并成一个大连续

22、块。则把这些块合并成一个大连续块。（续分配）（续分配）4. if size(k)-size(v)4. if size(k)-size(v)1.=1.顺顺序序查查找找各各个个空空闲闲区区，把把第第一一个个找找到到能能容容纳纳申申请请要要求求的的内内存存区区分分配配给给申申请请者者. .（若若空空闲闲区区比比作作业业长长度度大大，则则分分割割该该空闲区。一部分分配给作业一部分空闲。）空闲区。一部分分配给作业一部分空闲。）=2.=2.调调整相应的空闲表和已分配表。整相应的空闲表和已分配表。评评价价：性性能能一一般般但但实实现现比比较较简简单单直直接接，易易于于释释放放时时合合并并相相邻邻空空间间分分

23、区区。比比较较容容易易的的满满足足大大作作业业的的需需要要。完完成成一一次次分分配平均需要的搜索次数较大，影响了工作效率。配平均需要的搜索次数较大，影响了工作效率。存储管理 最佳满足算法：最佳满足算法：搜索整个空闲区以找出满足要求的最小空闲区。思想：思想：先使用小的空闲区，将大的空闲区留给大作先使用小的空闲区，将大的空闲区留给大作 业，所以它总是试图找出最接近实际需要的业，所以它总是试图找出最接近实际需要的 空闲区。空闲区。评价：评价：尽可能的保留了较大的空间。尽可能的保留了较大的空间。 产生大量的不用被使用的很小的空闲区。产生大量的不用被使用的很小的空闲区。 存储管理最大满足算法最大满足算法

24、 总是搜索整个链表以找到够用的最大的空闲区，使分裂出来的小空闲区比较大，因而可以继续使用。评价：评价：分割后产生的空闲区一般仍可以供以后分配使用。分割后产生的空闲区一般仍可以供以后分配使用。 工作一段时间后，不能满足大作业对空闲区的请求。工作一段时间后，不能满足大作业对空闲区的请求。存储管理例题：分区存储管理算法题假定主存中按地址顺序依次有五个空闲区。空假定主存中按地址顺序依次有五个空闲区。空闲区大小依次为：闲区大小依次为：15k,28k,10k,226k,110k.现有五个作业现有五个作业J1,J2,J3,J4,J5。他们各需要主存他们各需要主存10k,15k,102k,26k,180k。判

25、断用首次满足算法，最大满足算法算法，最判断用首次满足算法，最大满足算法算法，最佳满足算法能否将这五个作业顺序装入？佳满足算法能否将这五个作业顺序装入？存储管理OS15K28K10K226K110K内内存存空空闲闲区区示示意意图：图：OS28K10K226K110K装装入入J1后，后，内内存存空空闲闲区区示示意意图：图：J15k结论：只有最佳结论：只有最佳满足算法可以。满足算法可以。存储管理v紧致空间方法消除了固定分区管理造成的消除了固定分区管理造成的“内碎片内碎片”，但是但是“外碎片外碎片”仍然存在。仍然存在。采用移动（紧致）技术。定时的或在内存采用移动（紧致）技术。定时的或在内存紧张时，将内

26、存中所有作业移到内存的一紧张时，将内存中所有作业移到内存的一端，使其相邻。端，使其相邻。存储管理经过紧缩后的进程在内存中的位置发生了经过紧缩后的进程在内存中的位置发生了变化，若不对程序和数据的地址进行修改，变化，若不对程序和数据的地址进行修改，在进程就无法运行。在进程就无法运行。要使其运行，必须进行要使其运行，必须进行“动态重定位动态重定位”存储管理连续空间分配小结：连续空间分配小结：连续存储分配容易出现大段的连续空间因连续存储分配容易出现大段的连续空间因不能容纳作业或进程而不可用。不能容纳作业或进程而不可用。存在许多的存储碎片和空间管理较复杂的存在许多的存储碎片和空间管理较复杂的问题，主要原

27、因在于连续分配要求把作业问题，主要原因在于连续分配要求把作业或进程放在主存的一片连续区域中。或进程放在主存的一片连续区域中。因此，为充分利用存储空间资源，引入了因此，为充分利用存储空间资源，引入了不连续空间分配策略。不连续空间分配策略。存储管理分页存储管理是解决存储零头的一种方法。分页存储管理是解决存储零头的一种方法。动态重定位是解决存储器零头问题的一种途动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间径，但要移动大量信息花去不少处理机时间,代价比较高代价比较高,这是因为这种分配要求把作业必这是因为这种分配要求把作业必须安置在一连续存储区内的缘故须安置在一连续存储区

28、内的缘故,而分页存储而分页存储管理正是要避开这种连续性要求。管理正是要避开这种连续性要求。5.2 5.2 不连续空间分配不连续空间分配5.2.15.2.1页式管理页式管理存储管理一、空间安排 用户编程时所设想的空间和所用的地址叫用户编程时所设想的空间和所用的地址叫逻逻辑空间辑空间( (地址地址) ) 内存空间内存空间( (地址地址) )叫叫物理空间物理空间( (地址地址) )， 用相同长度为单位对逻辑空间等分出的每个用相同长度为单位对逻辑空间等分出的每个区域叫区域叫页页，对物理空间等分出的区域叫，对物理空间等分出的区域叫页帧页帧，辅存所划分出的每个区域叫辅存所划分出的每个区域叫块块。5.2 5

29、.2 不连续空间分配不连续空间分配5.2.15.2.1页式管理页式管理特点：作业作业( (进程进程) )分成页面，内存也划分成分成页面，内存也划分成页面，将作业页面，将作业( (进程进程) )页面不连续地分布到内页面不连续地分布到内存页面。存页面。存储管理回收：当进程结束时，系统回收它的所有物理当进程结束时，系统回收它的所有物理页帧放入空闲队列。页帧放入空闲队列。二、动态地址转换机构 因因页页式式方方法法中中逻逻辑辑地地址址与与物物理理地地址址之之间间失失去去自自然然联联系系，故故要要通通过过页页表表，并并由由硬硬件件动动态态地地址址转转换换机机构构将将逻逻辑辑地地址址映映射射成成物物理理地地

30、址址才才能能正正确访存。确访存。分配：系统初始时，所有页帧都在空闲初始时，所有页帧都在空闲队列中，当用户进程被创建时，系统按队列中，当用户进程被创建时，系统按需要量从空闲队列获得相应量的页帧。需要量从空闲队列获得相应量的页帧。存储管理(一)页表由于逻辑地址和物理地址不一致，因此必须把由于逻辑地址和物理地址不一致，因此必须把逻辑地址所对应的物理地址登记在一张称为页逻辑地址所对应的物理地址登记在一张称为页表的表中，逻辑空间若有表的表中，逻辑空间若有n n页，页表就应该有页，页表就应该有n n项。项。页表放在系统空间的页表区，存放逻辑页与物页表放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。理

31、页帧的对应关系。PCBPCB表中有指针指向页表。表中有指针指向页表。存储管理页表的第页表的第i项描述第项描述第i页，比如某作业由页，比如某作业由5页组成，分页组成，分别放在第别放在第1号、号、8号、号、5号、号、3号、号、0号页帧中。号页帧中。18530498765432103210逻辑空间页表页表页页号号物理空间存储管理(二)地址结构 分页逻辑地址分页逻辑地址 = P(= P(页号页号).d().d(页内位移页内位移) ) 分页物理地址分页物理地址 = f(= f(页帧号页帧号).d().d(页帧内位移页帧内位移) ) P = P = 线性逻辑地址线性逻辑地址 / / 页面大小；页面大小；

32、d = d = 线性逻辑地址线性逻辑地址 - p*- p*页面大小。页面大小。在求解逻辑地址对应的物理地址时，首先应分在求解逻辑地址对应的物理地址时，首先应分解逻辑地址的页号和页内位移，然后按页号查解逻辑地址的页号和页内位移，然后按页号查找对应的页表项找对应的页表项43210页页号号存储管理因此，从逻辑地址转换为物理地址可以这因此，从逻辑地址转换为物理地址可以这样计算：样计算：通过逻辑地址求出通过逻辑地址求出P P和和d d将页表始地址加上将页表始地址加上P P得到页表项地址；得到页表项地址；从页表项中获得该页所驻留的页帧号从页表项中获得该页所驻留的页帧号f f；再将再将f f乘页面大小加乘页

33、面大小加d d就得到所要的物理地址就得到所要的物理地址存储管理 (三)页面大小的考虑将页面大小取成将页面大小取成2 2的的k k次幂次幂(k(k是正整数是正整数),),获取获取p p和和d d的除、乘法只要通过位移实现的除、乘法只要通过位移实现. .页面大小为页面大小为2 2的的k k次幂的地址转换原理如下：次幂的地址转换原理如下：P d页表始地fn k-10f dn k-10+页表存储管理CPUCPU有一个用于有一个用于页号页号页帧号页帧号转换的联想存储器。将页转换的联想存储器。将页表存入联想存储器的地址转换原理如下：表存入联想存储器的地址转换原理如下：l联想存储器是一种高速存储体，每一项主

34、要由两部分联想存储器是一种高速存储体，每一项主要由两部分构成：关键字和值。构成：关键字和值。l当输入信息到达后，便同时与联想存储器中各项的关当输入信息到达后，便同时与联想存储器中各项的关键字进行比较，如果某项关键字与输入信息相同，则输键字进行比较，如果某项关键字与输入信息相同，则输出该项的值。如所有项的关键字与输入信息不匹配，则出该项的值。如所有项的关键字与输入信息不匹配，则输出一个特殊信号表示匹配不成功。输出一个特殊信号表示匹配不成功。l把页式系统中的页表项放在联想存储器，则其页号为把页式系统中的页表项放在联想存储器，则其页号为关键字，对应的页帧号为值。将待转换的逻辑地址的页关键字，对应的页

35、帧号为值。将待转换的逻辑地址的页号作为输入，与联想存储器的每一项进行匹配，若匹配号作为输入，与联想存储器的每一项进行匹配，若匹配成功，输出页帧号。成功，输出页帧号。(四)联想存储器（快速存储器）存储管理P dn k-10f dn k-10P2f2P1f1.Pf.Pmfm关键字关键字 值值存储管理联想存储器价格昂贵，一般只将一部分页联想存储器价格昂贵，一般只将一部分页表项放在其中。表项放在其中。地址转换：首先把页号送到联想存储器中地址转换：首先把页号送到联想存储器中匹配，若匹配成功，形成物理地址，否则匹配，若匹配成功，形成物理地址，否则到主存页表中查找页表项来形成物理地址。到主存页表中查找页表项

36、来形成物理地址。存储管理地址转换的一般过程地址转换的一般过程( (联想存储器可以看成是页表的联想存储器可以看成是页表的cache)cache)P dn k-10f dn k-10P2f2P1f1.Pf.Pmfmf页表始地址+页表联想存储器存储管理命中率：命中率：选用选用8-128-12项组成的联想存储器，项组成的联想存储器，并采用适当的替换策略，在联想存储器中并采用适当的替换策略，在联想存储器中匹配成功的可能性可达匹配成功的可能性可达80-90%80-90%。存储管理 三、可用空间管理 可用可用bitmapbitmap数组或空闲页帧链来管理可用数组或空闲页帧链来管理可用页帧页帧。（1 1）若可

37、用页帧总数小于作业（进程）总页）若可用页帧总数小于作业（进程）总页数，则拒绝分配，结束。数，则拒绝分配，结束。（2 2）否则，取作业（进程）的下一页）否则，取作业（进程）的下一页P P，分配，分配一可用页帧一可用页帧f f，将，将P P的内容抄到的内容抄到f f中。中。（3 3）将）将f f抄到页抄到页P P的页表项中。的页表项中。（4 4）若所有页都处理完，则结束，否则转向）若所有页都处理完，则结束，否则转向2 2。存储管理 四、共享与保护l在操作系统中，很多代码是可以共享的，如命在操作系统中，很多代码是可以共享的，如命令解释程序、编译程序、编辑程序等。在连续令解释程序、编译程序、编辑程序等

38、。在连续分配存储空间模式下，共享是不可能的，因为分配存储空间模式下，共享是不可能的，因为一个作业运行时只能访问一片连续的区域，多一个作业运行时只能访问一片连续的区域，多个作业显然不能与被共享程序都保持连续。个作业显然不能与被共享程序都保持连续。l在页式系统中便可实现共享。通过页表可以使在页式系统中便可实现共享。通过页表可以使几个逻辑空间指向同一个物理空间，实现程序几个逻辑空间指向同一个物理空间，实现程序共享。共享。存储管理 举例举例：有有3 3个进程共享编辑程序个进程共享编辑程序EDITEDIT，EDITEDIT长度为长度为3 3页，分别驻留在主存的页，分别驻留在主存的3 3、4 4、6 6号

39、页号页帧中。帧中。EDIT1EDIT2EDIT3DATA1EDIT1EDIT2EDIT3DATA2EDIT1EDIT2EDIT3DATA33461346734610OSDATA1EDIT10 1 2 3 4 5 6 7 8 9 10 11EDIT2EDIT3 DATA2DATA3P1 P2P3页表存储管理每个进程在运行时由自己的页表来进行地每个进程在运行时由自己的页表来进行地址映射，从而实现了多个进程对一个址映射，从而实现了多个进程对一个EDIT程序的共享。程序的共享。存储管理 存储保护引入页式不连续分配以后，由于共享的出现对存引入页式不连续分配以后，由于共享的出现对存储保护也提出了新的要求。

40、除了仍需要越界保护储保护也提出了新的要求。除了仍需要越界保护以外，对共享页还要进行特殊的保护。以外，对共享页还要进行特殊的保护。 越界保护：设置页表长度寄存器，查页表前，越界保护：设置页表长度寄存器，查页表前，先检查页号是否越界。先检查页号是否越界。 操作访问保护：在每个页表项中增设一存储保操作访问保护：在每个页表项中增设一存储保护域，用于说明对该页的访问权限，每一个对该护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先要比照是否满足该页访问权页存储的访问都首先要比照是否满足该页访问权限的说明，满足则访问，否则报错。限的说明，满足则访问，否则报错。存储管理设为每一页表项增加三位，设为

41、每一页表项增加三位，R R位表示读权位表示读权限，限，W W位表示写权限，位表示写权限，E E位表示执行权限。位表示执行权限。R RW WE E0 00 00 0 不可进行任何操作不可进行任何操作0 00 01 1 可以执行可以执行, ,不可以读写不可以读写0 01 10 0 只可以写只可以写0 01 11 11 10 00 01 10 01 11 11 10 01 11 11 1存储管理5.2.2 5.2.2 段式管理段式管理页式页式管理管理：对用户而言不自然，用户看待对用户而言不自然，用户看待程序是以自然段为单位的。程序是以自然段为单位的。 0 1 2 3 4 5 程程序序段段数数据据段段

42、比如某段只能读，另一段可执行。分页可能把不属于同比如某段只能读，另一段可执行。分页可能把不属于同一段的两块分到一页中。一段的两块分到一页中。第第4页中放入程序段（可执行）和数据段（可读写）各半，页中放入程序段（可执行）和数据段（可读写）各半，从而无法对其进行保护。从而无法对其进行保护。存储管理 段式管理的特点：按作业的自然段将其逻辑按作业的自然段将其逻辑空间分成若干段，作业以段为单位分配内存。空间分成若干段，作业以段为单位分配内存。 一、空间安排 例如，某用户作业（进程）由主程序、两个例如，某用户作业（进程）由主程序、两个子程序、栈和一段数据组成。于是可将这个作子程序、栈和一段数据组成。于是可

43、将这个作业划分为业划分为5 5个段，每段从零开始编址。个段，每段从零开始编址。 逻辑地址：段号逻辑地址：段号. .段内偏移，记作段内偏移，记作S,dS,d。编译编译及装配时把所有地址记成及装配时把所有地址记成(S,d)(S,d)的形式。若作业的形式。若作业正在运行主程序，则地址形式为（正在运行主程序，则地址形式为（0 0，d d）；一）；一旦调用子程序旦调用子程序1 1，地址变为（，地址变为（1 1，d d）；若访问数）；若访问数据段，地址变为（据段，地址变为（4 4，d d）。）。存储管理 物理内存空间管理：与多道可变划分法物理内存空间管理：与多道可变划分法一样，系统以段为单位分配物理内存。

44、一样，系统以段为单位分配物理内存。 主程序 子程序1 子程序2栈数据逻辑空间 子程序2主程序栈数据OS 子程序1物理空间存储管理二、动态地址转换保护码段长 本段在内存始地址由于作业在逻辑空间连续但主存空间不连续，由于作业在逻辑空间连续但主存空间不连续，故运行时需要进行地址转换。故运行时需要进行地址转换。段表：由如下格式的段表项组成，作业每段由由如下格式的段表项组成，作业每段由一个段表项表示一个段表项表示. .作业被划分成作业被划分成n n段，段表就应段，段表就应该有该有n n项项段表放于系统空间，进程段表放于系统空间，进程PCBPCB表中存有段表始表中存有段表始地址、段表长度。系统还设置段表始

45、地址寄存地址、段表长度。系统还设置段表始地址寄存器、段表长度寄存器。器、段表长度寄存器。存储管理段号 保护码 段长 段内存始址.保护码 段长 段内存始址.Sd段表始址段表长度+PA越界地址转换过程地址转换过程LA联想存储器联想存储器存储管理 对于用户而言对于用户而言，段页式管理与段式相同，用户，段页式管理与段式相同，用户逻辑地址只涉及段号与段内位移。逻辑地址只涉及段号与段内位移。 对于物理内存管理而言对于物理内存管理而言，它与页式系统相同。，它与页式系统相同。系统内的逻辑地址系统内的逻辑地址：段号：段号 段内位移段内位移 - - 段号段号页号页号页内位移。记作：页内位移。记作：S S，P P，

46、d.d.5.2.35.2.3段页式管理段页式管理特点：将作业分成若干段，每段用页式管将作业分成若干段，每段用页式管理实现内存分配理实现内存分配。一、空间安排存储管理作业空间的内部表示主程序子程序数据保护码 长度 页表始地OS段表页表主存作业段表段表+ +页表页表存储管理二、动态地址转换段号页号保护码页帧号.Spd段表始址段表长度+越界+ f f d段表段表页表页表存储管理三、保护与共享保护与段式管理相同。保护与段式管理相同。共享则可以以共享则可以以页页为单位，也可以共享页表。为单位，也可以共享页表。等效访问时间：等效访问时间：设访存时间为设访存时间为750ns750ns，搜索搜索联想存储器的时

47、间为联想存储器的时间为50ns50ns，命中率为命中率为95%95%，则则95% *(50+750) + 5% *(50+750+750+750)95% *(50+750) + 5% *(50+750+750+750) = 875ns = 875ns存储管理段表主程序子程序数据作业1主程序子程序数据作业2段表页表OS主存存储管理总结总结“放放” 连续存放连续存放 单道连续划分单道连续划分 多道连续固定划分多道连续固定划分 多道连续可变划分多道连续可变划分 不连续存放不连续存放 页式存储页式存储 段式存储段式存储 段页式存储段页式存储存储管理5.3.1虚存的基本思想5.3 5.3 虚存管理虚存管

48、理目的：提供用户进程一个巨大的虚拟存储空间提供用户进程一个巨大的虚拟存储空间. .手段：通过统一管理主存、辅存，利用辅存实通过统一管理主存、辅存，利用辅存实现此虚空间现此虚空间. .系统为进程提供一个比物理内存大得多的系统为进程提供一个比物理内存大得多的虚拟存储空间，虚拟空间大小不受物理内虚拟存储空间，虚拟空间大小不受物理内存大小的限制。存大小的限制。 虚拟空间的容量由系统的有效地址长度决虚拟空间的容量由系统的有效地址长度决定。假设地址长度为定。假设地址长度为3232，按字节寻址，则，按字节寻址，则虚拟存储空间大小为虚拟存储空间大小为2 23232个字节。个字节。存储管理实现页式虚空间的基本方

49、法是： 在页式管理的基础上，仅将进程的一部在页式管理的基础上，仅将进程的一部分页放于主存。页表项中注明该页是否在分页放于主存。页表项中注明该页是否在主存。程序执行时，如果访问的页不存主主存。程序执行时，如果访问的页不存主存，根据页表项的指示，将其从辅存调入存，根据页表项的指示，将其从辅存调入主存，如果此时无可用的内存空间，则先主存，如果此时无可用的内存空间，则先淘汰若干页帧。淘汰若干页帧。存储管理一、页表项结构:合法位修改位页类型保护码辅存块号页帧号合法位：合法位：置上表示该页在内存置上表示该页在内存. .修改位：修改位：置上表示该页被修改过，在释放或淘汰时应回写置上表示该页被修改过，在释放或

50、淘汰时应回写辅存。辅存。页类型页类型: :1 1、零页时：表示该页在分配物理页帧时应清零页时：表示该页在分配物理页帧时应清0 0页页帧空间帧空间;2;2、回写、回写swapswap区页时区页时: :表示在回写时必须分配表示在回写时必须分配swapswap区，并回写到区，并回写到swapswap空间中。没有设置页类型时，表示按正空间中。没有设置页类型时，表示按正常方式处理。常方式处理。保护码：保护码：R R、W W、E E保护说明。保护说明。辅存块号：辅存块号：该页所在辅存的块号。该页所在辅存的块号。页页 帧帧 号：号：当合法位置上时代表该页所在内存的页帧号。当合法位置上时代表该页所在内存的页帧

51、号。5.3.2 页式虚存管理存储管理交换区（交换区（SWAPSWAP）：）：进程刚建立时，进程页进程刚建立时，进程页面所在的辅存即程序文件所在的辅存位置。程面所在的辅存即程序文件所在的辅存位置。程序文件中一般包含有程序的二进制目标码及数序文件中一般包含有程序的二进制目标码及数据初始值和初值为据初始值和初值为0 0的工作区。的工作区。l程序在进程的运行过程中，数据的初始值页程序在进程的运行过程中，数据的初始值页面被调入主存使用，而且存放初始值的主存单面被调入主存使用，而且存放初始值的主存单元可能被修改。这时，系统不能将修改过的页元可能被修改。这时，系统不能将修改过的页面回写到执行程序文件中去，因

52、为执行程序中面回写到执行程序文件中去，因为执行程序中的初始值不能被改变。因此引入了交换区用于的初始值不能被改变。因此引入了交换区用于存放那些可读写的页面。存放那些可读写的页面。存储管理 l还有一种页面，在执行程序文件中被说明是还有一种页面，在执行程序文件中被说明是初值为初值为0 0的工作区，我们称为零页，表示该页的的工作区，我们称为零页，表示该页的初值为初值为0 0。这种页面分配主存页帧时不必从辅存。这种页面分配主存页帧时不必从辅存获得初始数据，只要在分配页帧时，将页帧清获得初始数据，只要在分配页帧时，将页帧清0 0即可。当回写时，也需要分配交换空间，然后即可。当回写时，也需要分配交换空间，然

53、后回写到交换空间中。回写到交换空间中。存储管理二、页表建立 分配分配pidpid给子进程，分配给子进程，分配PCBPCB空间空间; ; 初始化初始化PCBPCB（进程标识，调度信息进程标识，调度信息）; ; 分配子进程页表空间分配子进程页表空间; ; 拷贝父进程的程序区页表项，使程序共享拷贝父进程的程序区页表项，使程序共享; ;部分复制父进程页表 (如UNIX的fork()初始化页表方法：在进程创建时建立页表，页表项在初始时，在进程创建时建立页表，页表项在初始时，合法位、修改位及页帧号都未置上合法位、修改位及页帧号都未置上. .存储管理复制父进程的数据区和栈区，为数据区复制父进程的数据区和栈区

54、，为数据区和栈区分配和栈区分配swapswap空间，复制并修改数据空间，复制并修改数据区和栈区页表项内容区和栈区页表项内容; ;继承父进程对其他资源的访问现场继承父进程对其他资源的访问现场; ;用父进程用父进程PCBPCB中现场区初始化子进程的中现场区初始化子进程的现场区，且保证子进程恢复现场运行从现场区，且保证子进程恢复现场运行从forkfork（）（）返回处开始，且返回处开始，且fork()fork()返回值为零返回值为零; ;将子进程挂到就绪队列将子进程挂到就绪队列; ;返回子进程返回子进程pidpid给父进程给父进程. .存储管理为执行程序页面建页表项，保护码为可执行，辅为执行程序页面

55、建页表项，保护码为可执行，辅存块号即该页所在的文件的辅存块号。（不必存块号即该页所在的文件的辅存块号。（不必回写）回写）为所有初始数据页建页表项，保护码为可读写，为所有初始数据页建页表项，保护码为可读写，页类型说明成回写页类型说明成回写swapswap页，辅存块号即该页所页，辅存块号即该页所在文件的物理块号，待该页回写时，再分配在文件的物理块号，待该页回写时，再分配swapswap区空间，改辅存块号栏并清区空间，改辅存块号栏并清0 0页类型页类型。为所有临时数据页建页表项，保护码为可读写，为所有临时数据页建页表项，保护码为可读写，页类型说明成零页，辅存块号栏空，当第一次页类型说明成零页，辅存块

56、号栏空，当第一次访问该页时，分配页帧并清访问该页时，分配页帧并清0 0页帧，回写时，再页帧，回写时，再分配分配swapswap区空间，填外存块号栏并清区空间，填外存块号栏并清0 0页类型。页类型。用一个可执行的程序文件来初始化页表存储管理 在执行虚存访问指令时在执行虚存访问指令时, ,由硬件合成物理地由硬件合成物理地址。首先若能在联想存储器中获得该虚页的物址。首先若能在联想存储器中获得该虚页的物理页帧号，则访问之。若要查当前进程页表，理页帧号，则访问之。若要查当前进程页表，须先检查该页页表项的合法位，若置上，则从须先检查该页页表项的合法位，若置上，则从页表项中获得页帧号，否则要发一个页故障页表

57、项中获得页帧号，否则要发一个页故障(page fault)(page fault)或叫缺页异常，当缺页异常处理或叫缺页异常，当缺页异常处理完后，重新执行访存指令完后，重新执行访存指令. .联想存储器中的页表项都是合法页的页表项联想存储器中的页表项都是合法页的页表项. .三、硬件动态地址转换存储管理1 1、根据发生页故障的虚地址得到页表项；、根据发生页故障的虚地址得到页表项；2 2、申请一个可用的页帧、申请一个可用的页帧( (根据所采用的替换策略根据所采用的替换策略可能需要引起淘汰某一页可能需要引起淘汰某一页););3 3、检查页类型，若为零页，则将页帧清、检查页类型，若为零页，则将页帧清0 0

58、，将页，将页帧号填入页表项的页帧号一栏，置合法位为帧号填入页表项的页帧号一栏，置合法位为1 1。若非零页，则调用若非零页，则调用I/OI/O子系统将辅存块号所指子系统将辅存块号所指的数据读到可用页帧，将页帧号填入页表项的数据读到可用页帧，将页帧号填入页表项中，合法位置中，合法位置1 1，结束，结束. .四、缺页处理当硬件执行访存指令产生一个缺页异常时当硬件执行访存指令产生一个缺页异常时进入缺页异常处理程序：进入缺页异常处理程序：存储管理 五、页淘汰 页淘汰可以发生在申请页帧时，而现代页淘汰可以发生在申请页帧时，而现代OSOS一一般都定时进行页淘汰。如何选取被淘汰的页是由般都定时进行页淘汰。如何

59、选取被淘汰的页是由页面替换策略决定的，若已决定淘汰页页面替换策略决定的，若已决定淘汰页P P，则淘汰则淘汰一页的主要工作有：一页的主要工作有：1 1、查查P P页表项的修改位，若未修改，则清页表项的修改位，若未修改，则清0 0合法位，合法位，将页帧送回空闲页帧队列。将页帧送回空闲页帧队列。2 2、若已修改，则检查类型栏。若已修改，则检查类型栏。3 3、若是零页或回写若是零页或回写swapswap区页，则申请一块区页，则申请一块swapswap区区空间，将空间，将P P的辅存块号置上并清的辅存块号置上并清0 0页类型。页类型。4 4、调用调用I/0I/0子系统将页帧上的数据写到辅存块号子系统将页

60、帧上的数据写到辅存块号所指的辅存空间。清所指的辅存空间。清0 0合法位，将页帧送回空闲页合法位，将页帧送回空闲页帧队列。帧队列。存储管理5.3.3 页面替换策略页面替换策略虚存的作用：虚存的作用： 解决主存空间不足解决主存空间不足 让更多的进程并发运行，提高系统的让更多的进程并发运行，提高系统的吞吐率吞吐率页页故障引发如下操作故障引发如下操作： Page Out / Page In(Page Out / Page In(访问辅存访问辅存) )必须防止系统发生抖动（控制页故障频度）必须防止系统发生抖动（控制页故障频度）存储管理页面替换策略中基本概念页面替换策略中基本概念 驻留集驻留集( (工作集

61、工作集) )：进程的合法页集合进程的合法页集合 访问串：访问串：进程访问虚空间的地址踪迹。进程访问虚空间的地址踪迹。 举例：某进程依次访问如下地址，举例：某进程依次访问如下地址，01000100，04320432，01010101，06120612，01020102，01030103， 页式虚存管理以页为基本单位，只需页号即可。页式虚存管理以页为基本单位，只需页号即可。设页面大小为设页面大小为100100，上述访问串可简化为，上述访问串可简化为1 1，4 4，1 1，6 6，1 1，1 1，若访问第若访问第i i页，则紧随该页第一次访问后再对第页，则紧随该页第一次访问后再对第i i页的访问一般

62、不会造成页故障。页的访问一般不会造成页故障。存储管理页面替换策略分成两类：页面替换策略分成两类： 驻留集大小固定的替换策略驻留集大小固定的替换策略 驻留集大小可变的替换策略驻留集大小可变的替换策略 设驻留集大小为设驻留集大小为m m，s(t)s(t)为为t t时刻的驻留集，时刻的驻留集，r(t)r(t)为为t t时刻访问的页号。时刻访问的页号。t t取取0,1,t0,1,t，指指访存指令执行时刻。访存指令执行时刻。存储管理驻留集与驻留集与paging in/outpaging in/out的关系：的关系： 进程刚创建时，驻留集为空。即进程刚创建时，驻留集为空。即s(0)=s(0)=空。空。 若

63、若t+1t+1时刻访问的页在时刻访问的页在s(t)s(t)中时，访问之。中时，访问之。 即若即若r(t+1)s(t)r(t+1)s(t)，则，则s(t+1)= s(t)s(t+1)= s(t)。 若若t+1t+1时刻访问的页不在时刻访问的页不在s(t)s(t)中时，且驻留中时，且驻留 集大小小于集大小小于m m，则，则paging inpaging in。即。即若若 r(t+1)!s(t)r(t+1)!s(t)，且且|s(t)|m|s(t)|，则淘汰之。，则淘汰之。(二) SWS(Sampled Working Set)定时检查计数器，淘汰计数器值大于等定时检查计数器，淘汰计数器值大于等于于的

64、页面。这样硬件消耗仍很大。的页面。这样硬件消耗仍很大。存储管理 (三) VMIN(Variable Minimal replacement)若某页距下次访问的距离大于若某页距下次访问的距离大于则将其淘则将其淘汰。汰。( (不能实用不能实用) )相同时，相同时，VMINVMIN与与WSWS的故障数相同，但的故障数相同，但VMINVMIN的平均驻留集要小。的平均驻留集要小。存储管理练习某程序大小为某程序大小为760个字。考虑如下访问序列：个字。考虑如下访问序列：10，11，104，170，73，633，512，189，172，645，732，711，309，589，445，449，366，245，

65、299，277，534，558，页帧大小为，页帧大小为100个字，驻留集大小为个字，驻留集大小为3个个页面。页面。（1）给出访问串。）给出访问串。（2）分别求出采用）分别求出采用FIFO和和LRU页面调度算页面调度算法，它们的页面调度次序和页故障数。法，它们的页面调度次序和页故障数。存储管理练习设某作业占有设某作业占有7个页面，如果在主存中只允个页面，如果在主存中只允许装入许装入4个工作页面，作业运行时，实际访个工作页面，作业运行时，实际访问页面的顺序是问页面的顺序是1，2，3，6，4，7，3，2，1，4，7，5，6，3。试用。试用FIFO与与LRU页面调度算法，列出各自的页面调度页面调度算法，列出各自的页面调度次序和页故障数。次序和页故障数。