第四章 存储管理_new

1、存储管理存储器的层次结构存储器的层次结构寄存器寄存器高速缓存高速缓存主存主存磁盘缓存磁盘缓存磁盘磁盘可移动存储介质可移动存储介质第四章第四章 存储管理存储管理存储管理第四章第四章 存储管理存储管理l存储管理主要研究进程如何占用主存资源。存储管理主要研究进程如何占用主存资源。l设计操作系统的重要目标之一是提高计算机设计操作系统的重要目标之一是提高计算机资源的利用率，而提高计算机资源利用率的资源的利用率，而提高计算机资源利用率的根本途径是采用多道程序设计技术。因此，根本途径是采用多道程序设计技术。因此，必须合理地管理主存储空间，使尽可能多的必须合理地管理主存储空间，使尽可能多的进程能够同时存放于主

2、存以竞争进程能够同时存放于主存以竞争CPU，保证，保证CPU和和I/O设备足够繁忙。设备足够繁忙。存储管理第四章第四章 存储管理存储管理l存储管理所研究的内容主要包括三个方面：存储管理所研究的内容主要包括三个方面：l取：将哪个进程（或进程的某些部分）从辅存调入主存取：将哪个进程（或进程的某些部分）从辅存调入主存l放：研究将取来的进程按何种方式放在主存的什么地方放：研究将取来的进程按何种方式放在主存的什么地方l替换：研究将哪个进程（或进程的某部分）暂时从主存替换：研究将哪个进程（或进程的某部分）暂时从主存移到辅存，以腾出主存空间供其他进程占用。移到辅存，以腾出主存空间供其他进程占用。l这三方面中

3、，这三方面中，“放放”是存储管理的基础。是存储管理的基础。l目前，目前，“放放”的技术可归结成两类：一类是连续的，的技术可归结成两类：一类是连续的，即运行的程序和数据必须放在主存的一片连续空间即运行的程序和数据必须放在主存的一片连续空间中；另一类是不连续的，即运行的程序和数据可以中；另一类是不连续的，即运行的程序和数据可以放在主存的多个不相邻的块中。放在主存的多个不相邻的块中。存储管理第四章第四章 存储管理存储管理4.1 连续空间分配连续空间分配单道连续分配单道连续分配多道固定划分法（固定分区分配）多道固定划分法（固定分区分配）多道连续可变划分法（动态分区分配）多道连续可变划分法（动态分区分配

4、）4.2 不连续空间分配不连续空间分配页式管理页式管理段式管理段式管理段页式管理段页式管理4.3 虚拟内存管理虚拟内存管理存储管理4.1 连续空间分配连续空间分配在早期的操作系统设计中，都是采用连续在早期的操作系统设计中，都是采用连续空间分配的策略。早期操作系统中还没有空间分配的策略。早期操作系统中还没有引入进程概念，主存分配还是以作业（相引入进程概念，主存分配还是以作业（相当于进程）为单位进行的。当于进程）为单位进行的。存储管理内存空间安排内存空间安排4.1.14.1.1单道连续分配单道连续分配特点：任一时刻内存只有一道作业，该任一时刻内存只有一道作业，该作业连续存放于内存中。作业连续存放于

5、内存中。一、空间划分与保护操作系统操作系统用户程序用户程序0a aa+1a+1n n界地址寄存器界地址寄存器存储管理界地址寄存器界地址寄存器主存主存A a?A a?cpucputruetruefalsefalse地址地址A A终止程序运行终止程序运行越界检查机构：用户程序每次执行访存指用户程序每次执行访存指令，硬件越界检查机构将访问的地址与界令，硬件越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止地址寄存器中的值比较。若越界，则终止其执行。其执行。存储管理二、覆盖（overlay） 因内存小于作业的程序空间而引入覆盖。将用户因内存小于作业的程序空间而引入覆盖。将用户空间划分成一

6、个固定区和多个覆盖区。主程序放空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。固定区，依次调用的子程序则放在同一个覆盖区。首先将那些即将要用的段放在覆盖区，其他段放首先将那些即将要用的段放在覆盖区，其他段放在辅存，在需要调用前通过特定系统调用将其调在辅存，在需要调用前通过特定系统调用将其调入占用覆盖区，替换覆盖区中原有的段。入占用覆盖区，替换覆盖区中原有的段。操作系统提供覆盖系统调用函数，操作系统提供覆盖系统调用函数，由用户编程序由用户编程序时考虑调用。时考虑调用。存储管理例如：某作业各过程间关系如下：例如：某作业各过程间关系如下：操作系统操作系统固定区固

7、定区(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)存储管理覆盖技术的主要特点是打破了必须将一个作业的覆盖技术的主要特点是打破了必须将一个作业的全部信息装入主存后才能运行的限制。在一定程全部信息装入主存后才能运行的限制。在一定程度上解决了小主存运行大作业的矛盾。度上解决了小主存运行大作业的矛盾。采用覆盖技术是把解决空间不足的问题交给了用采用覆盖技术是把解决空间不足的问题交给了用户。操作系统提供帮助用户将覆盖段调入主存的户。操作系统提供帮助用户将

8、覆盖段调入主存的系统调用，但用户自己必须说明覆盖段，并安排系统调用，但用户自己必须说明覆盖段，并安排调入覆盖段，由此可见覆盖技术用户参与过多，调入覆盖段，由此可见覆盖技术用户参与过多，会给用户带来麻烦。会给用户带来麻烦。存储管理基本思想：将处于等待状态将处于等待状态( (等等I/O)I/O)或就绪或就绪( (等等CPU)CPU)状态的进程从主存换出到辅存，把将状态的进程从主存换出到辅存，把将要执行的进程移入主存。要执行的进程移入主存。三、交换进程的换出：系统首先选择处于阻塞状态且优先进程的换出：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将级最低的进程作为换出进程，然

9、后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上，回该进程的程序和数据传送到磁盘的对换区上，回收内存。收内存。 进程的换入：系统定时查看所有进程的状态，从进程的换入：系统定时查看所有进程的状态，从中找出就绪状态但已换出的进程，将其中换出时中找出就绪状态但已换出的进程，将其中换出时间最久的进程换入。间最久的进程换入。存储管理程序的装入和链接程序的装入和链接如何将一个用户源程序变成一个可在内如何将一个用户源程序变成一个可在内存中执行的程序？存中执行的程序？ 对用户程序的处理步骤对用户程序的处理步骤 存储管理常用的基本概念1.物理地址空间和逻辑地址空间 物理地址空间物理地址空间（也称内存空间、绝

10、对地址空间或实（也称内存空间、绝对地址空间或实空间或存储空间）：是指主存中物理单元的集合。空间或存储空间）：是指主存中物理单元的集合。这些单元的编号称为物理地址或绝对地址。这些单元的编号称为物理地址或绝对地址。 逻辑地址空间逻辑地址空间（也称相对地址空间、虚空间或地址（也称相对地址空间、虚空间或地址空间）空间）：当对源程序进行编译时，编译后一个目标当对源程序进行编译时，编译后一个目标程序所限定的地址范围称为该作业的逻辑地址空间。程序所限定的地址范围称为该作业的逻辑地址空间。通常所得的目标程序起始地址是从通常所得的目标程序起始地址是从0 0开始的。开始的。作业运行时不能按其逻辑地址访问内存单元，

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

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

13、在执行访存指令时将件地址转换机制实现，在执行访存指令时将“原原地址地址+ +目标代码所在主存起始地址目标代码所在主存起始地址”后进行访问。后进行访问。 存储管理静态地址重定位静态地址重定位主要优点：无需增加硬件地址变换机构，因而可在一主要优点：无需增加硬件地址变换机构，因而可在一般计算机上实现般计算机上实现 主要缺点：要求给每个作业分配一个连续的存储空间，主要缺点：要求给每个作业分配一个连续的存储空间，且在作业的整个执行期间不能再移动，因而也就不能且在作业的整个执行期间不能再移动，因而也就不能实现重新分配主存。实现重新分配主存。动态地址重定位动态地址重定位主要优点有：主要优点有：用户作业不要求

14、分配连续的存储空间。用户作业不要求分配连续的存储空间。 用户作业在执行过程中，可以动态申请存储空间和用户作业在执行过程中，可以动态申请存储空间和在主存中移动。在主存中移动。 主要缺点有：主要缺点有：需要附加的硬件支持。需要附加的硬件支持。 实现存储管理的软件算法比较复杂实现存储管理的软件算法比较复杂。存储管理利用一个重定位寄存器。该寄存器的值由调度程序根据作业利用一个重定位寄存器。该寄存器的值由调度程序根据作业分配到的存储空间的起始地址来设定。在具有这种地址变换分配到的存储空间的起始地址来设定。在具有这种地址变换机构的计算机系统中，当作业执行时，不是根据机构的计算机系统中，当作业执行时，不是根

15、据CPUCPU给出的给出的逻辑地址去访问主存，而是将逻辑地址与重定位寄存器中的逻辑地址去访问主存，而是将逻辑地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。内容相加后得到的地址作为访问主存的地址。 存储管理特点：任一时刻内存可有多道进程，每个进任一时刻内存可有多道进程，每个进程连续存放于内存程连续存放于内存. .操作系统操作系统U1U1.UnUn4.1.2 4.1.2 多道固定划分法（固定分区分配）多道固定划分法（固定分区分配）一、空间划分及保护 将用户内存空将用户内存空间分成长度固定间分成长度固定的若干块的若干块。用户空间用户空间存储管理1.上下界寄存器和地址检查机构。当作业当

16、作业被调度运行时，作业在内存中的上下界地被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次执行访存指令时，址送上下界寄存器，每次执行访存指令时，地址检查机构作越界检查。作业程序要是地址检查机构作越界检查。作业程序要是绝对地址或静态重定位的。绝对地址或静态重定位的。CPUCPU主存主存下界寄存器下界寄存器上界寄存器上界寄存器 TrueTrueTrueTrue地址地址A AF F F F程序性异常程序性异常地址访问保护有两种方式：地址访问保护有两种方式：存储管理2.基址寄存器、长度寄存器和动态地址转换机构。当作业被调度运行时，将作业所当作业被调度运行时，将作业所占内存基址及长度送基址、长度

17、寄存器，占内存基址及长度送基址、长度寄存器，每次执行访存指令时，先看访问地址是否每次执行访存指令时，先看访问地址是否小于长度，然后小于长度，然后+ +基址进行访存。用户程基址进行访存。用户程序代码是动态重定位的。序代码是动态重定位的。CPUCPU主存主存基地址寄存器基地址寄存器长度寄存器长度寄存器 + +TrueTrue地址地址A AF F 程序性异常程序性异常存储管理二、作业存储调度在多道固定划分法下，作业调度一般分为多队列法在多道固定划分法下，作业调度一般分为多队列法和单队列法。和单队列法。多队列法是指每个存储区对应一个作业队列，在作多队列法是指每个存储区对应一个作业队列，在作业到达后，按

18、作业的大小在对应队列中排队。业到达后，按作业的大小在对应队列中排队。单队列法是指系统中仅保持一个作业队列。单队列法是指系统中仅保持一个作业队列。例如：总存储量为例如：总存储量为32KB，操作系统占，操作系统占10KB，用户空，用户空间被划分成长度为间被划分成长度为4KB、6KB、12KB三块。作业要求三块。作业要求的存储量若未超过这三个存储量，则分别进入相应的存储量若未超过这三个存储量，则分别进入相应的队列的队列1、队列、队列2、队列、队列3。存储管理二、作业存储调度OS4k6k12kOS4k6k12k.10k3k4k5k.3k4k3k2k.5k6k.7k10k11k8k多队列法多队列法单队列

19、法单队列法存储管理三、存储碎片 内部碎片：内部碎片：内存某存储区间大于其存放作内存某存储区间大于其存放作 业空间的部分。业空间的部分。 外部碎片：外部碎片：内存某存储区间容不下要运行内存某存储区间容不下要运行 的作业时。的作业时。OS12k4k3K内部碎片内部碎片OSOS4k4k6k6k12k12k作业长度：作业长度：5K5K、8K8K、12K12K外部碎片外部碎片存储管理一、管理方法4.1.34.1.3多道连续可变划分法（动态分区分配）多道连续可变划分法（动态分区分配）特点：多道、连续、但不固定划分内存。多道、连续、但不固定划分内存。 系统设置一个空闲块队列，初始状态时队系统设置一个空闲块队

20、列，初始状态时队列中只有一个连续的空闲块。作业到达后，列中只有一个连续的空闲块。作业到达后，以某种策略分配空间。作业撤离时，将释放以某种策略分配空间。作业撤离时，将释放的空间加入空闲队列。的空间加入空闲队列。存储管理举例：假设任一时间段内，内存中每一作举例：假设任一时间段内，内存中每一作业的运行时间片相等。业的运行时间片相等。作业到来次序作业到来次序 所需存储量所需存储量 运行时间运行时间 1 60 10 2 100 5 3 30 20 4 70 8 5 50 15OS040255J1J2J3J4J5存储管理分配：调度程序为选中的作业分配存储空间，则在可用分配：调度程序为选中的作业分配存储空间

21、，则在可用块集合中按某种策略选择一个大小满足该用户作业要求块集合中按某种策略选择一个大小满足该用户作业要求的可用分配给用户。的可用分配给用户。分配策略包括分配策略包括首次满足法首次满足法/ /最佳满足法最佳满足法/ /最大满足最大满足法法，在找到合适的空闲块后，从其中将作业大小，在找到合适的空闲块后，从其中将作业大小的空间分给作业，而剩余部分挂入空闲队列。的空间分给作业，而剩余部分挂入空闲队列。下面下面F F是空闲块集合是空闲块集合; size(k); size(k)为块为块k k的大小的大小; size(v); size(v)为为用户所需空间。用户所需空间。1.1.if if 所有属于所有属

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

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

24、分配使用。 工作一段时间后，不能满足大作业对空闲区的请求。工作一段时间后，不能满足大作业对空闲区的请求。存储管理例题：分区存储管理算法题假定主存中按地址顺序依次有五个空闲区。空假定主存中按地址顺序依次有五个空闲区。空闲区大小依次为：闲区大小依次为：15k,28k,10k,226k,110k.现有五个作业现有五个作业J1,J2,J3,J4,J5。他们各需要主存他们各需要主存10k,15k,102k,26k,180k。判断用首次满足算法，最大满足算法，最佳满判断用首次满足算法，最大满足算法，最佳满足算法能否将这五个作业顺序装入？足算法能否将这五个作业顺序装入？存储管理OS15K28K10K226K

25、110K内内存存空空闲闲区区示示意意图：图：OS28K10K226K110K装装入入J1后，后，内内存存空空闲闲区区示示意意图：图：J15k结论：只有最佳结论：只有最佳满足算法可以。满足算法可以。存储管理v紧致空间方法消除了固定分区管理造成的消除了固定分区管理造成的“内碎片内碎片”，但是但是 “外碎片外碎片”仍然存在。仍然存在。采用移动（紧致）技术。定时的或在内存采用移动（紧致）技术。定时的或在内存紧张时，将内存中所有作业移到内存的一紧张时，将内存中所有作业移到内存的一端，使其相邻。端，使其相邻。存储管理经过紧缩后的进程在内存中的位置发生了经过紧缩后的进程在内存中的位置发生了变化，若不对程序和

26、数据的地址进行修改，变化，若不对程序和数据的地址进行修改，在进程就无法运行。在进程就无法运行。要使其运行，必须进行要使其运行，必须进行“动态重定位动态重定位”存储管理连续空间分配小结：连续空间分配小结：连续存储分配容易出现大段的连续空间因连续存储分配容易出现大段的连续空间因不能容纳作业或进程而不可用。不能容纳作业或进程而不可用。存在许多的存储碎片和空间管理较复杂的存在许多的存储碎片和空间管理较复杂的问题，主要原因在于连续分配要求把作业问题，主要原因在于连续分配要求把作业或进程放在主存的一片连续区域中。或进程放在主存的一片连续区域中。因此，为充分利用存储空间资源，引入了因此，为充分利用存储空间资

27、源，引入了不连续空间分配策略。不连续空间分配策略。存储管理l1某基于动态分区分配的系统中，其主存某基于动态分区分配的系统中，其主存可用容量为可用容量为55MB（初始状态）。采用最佳（初始状态）。采用最佳适配分配算法，分配和释放的顺序为：分适配分配算法，分配和释放的顺序为：分配配15MB,分配分配30MB,释放释放15MB，分配，分配8MB,此时主存中最大空闲分区大小是此时主存中最大空闲分区大小是( )。A7MB B9MB C.10MB D.15MB 存储管理2. 在把装入模块装入内存后，并不立即把在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，装入模块中的相对地址转换为绝

28、对地址，而是把地址转换推迟到程序真正要执行时而是把地址转换推迟到程序真正要执行时才进行，称为（才进行，称为（ ）。）。A.编译编译 B.连接连接 C.动态重定位动态重定位 D.重定位重定位存储管理分页存储管理是解决存储零头的一种方法。分页存储管理是解决存储零头的一种方法。动态重定位是解决存储器零头问题的一种途动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间径，但要移动大量信息花去不少处理机时间,代价比较高代价比较高,这是因为这种分配要求把作业必这是因为这种分配要求把作业必须安置在一连续存储区内的缘故须安置在一连续存储区内的缘故,而分页存储而分页存储管理正是要避开这种

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

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

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

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

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

34、页面大小加乘页面大小加d d就得到所要的物理地址就得到所要的物理地址存储管理 (三)页面大小的考虑将页面大小取成将页面大小取成2 2的的k k次幂次幂(k(k是正整数是正整数),),获取获取p p和和d d的除、乘法只要通过位移实现的除、乘法只要通过位移实现. .页面大小为页面大小为2 2的的k k次幂的地址转换原理如下：次幂的地址转换原理如下：P d页表始地fnk-10f dnk-10+页表存储管理 练习练习在页式存储管理中，某作业的逻辑地址空在页式存储管理中，某作业的逻辑地址空间为间为4页（页大小为页（页大小为1KB），作业的页面映），作业的页面映像为像为0-2#,1-4#,2-6#,3-

35、8# ，求出逻辑，求出逻辑地址地址2075所对应的物理地址。所对应的物理地址。 存储管理CPUCPU有一个用于有一个用于页号页号页帧号页帧号转换的联想存储器。将页转换的联想存储器。将页表存入联想存储器的地址转换原理如下：表存入联想存储器的地址转换原理如下：l联想存储器是一种高速存储体，每一项主要由两部分联想存储器是一种高速存储体，每一项主要由两部分构成：关键字和值。构成：关键字和值。l当输入信息到达后，便同时与联想存储器中各项的关当输入信息到达后，便同时与联想存储器中各项的关键字进行比较，如果某项关键字与输入信息相同，则键字进行比较，如果某项关键字与输入信息相同，则输出该项的值。如所有项的关键

36、字与输入信息不匹配，输出该项的值。如所有项的关键字与输入信息不匹配，则输出一个特殊信号表示匹配不成功。则输出一个特殊信号表示匹配不成功。l把页式系统中的页表项放在联想存储器，则其页号为把页式系统中的页表项放在联想存储器，则其页号为关键字，对应的页帧号为值。将待转换的逻辑地址的关键字，对应的页帧号为值。将待转换的逻辑地址的页号作为输入，与联想存储器的每一项进行匹配，若页号作为输入，与联想存储器的每一项进行匹配，若匹配成功，输出页帧号。匹配成功，输出页帧号。(四)联想存储器（快表）存储管理Pdnk-10fdnk-10P2f2P1f1.Pf.Pmfm关键字关键字 值值存储管理联想存储器价格昂贵，一般

37、只将一部分页联想存储器价格昂贵，一般只将一部分页表项放在其中。表项放在其中。地址转换：首先把页号送到联想存储器中地址转换：首先把页号送到联想存储器中匹配，若匹配成功，形成物理地址，否则匹配，若匹配成功，形成物理地址，否则到主存页表中查找页表项来形成物理地址。到主存页表中查找页表项来形成物理地址。存储管理地址转换的一般过程地址转换的一般过程( (联想存储器可以看成是页表的联想存储器可以看成是页表的cache)cache)Pdnk-10fdnk-10P2f2P1f1.Pf.Pmfmf页表始地址+页表联想存储器存储管理命中率：命中率：选用选用8-128-12项组成的联想存储器，项组成的联想存储器，并

38、采用适当的替换策略，在联想存储器中并采用适当的替换策略，在联想存储器中匹配成功的可能性可达匹配成功的可能性可达80-90%80-90%。存储管理 三、可用空间管理可用可用bitmapbitmap数组或空闲页帧链来管理可用页帧数组或空闲页帧链来管理可用页帧。（1 1）若可用页帧总数小于作业（进程）总页数，）若可用页帧总数小于作业（进程）总页数，则拒绝分配，结束。则拒绝分配，结束。（2 2）否则，取作业（进程）的下一页）否则，取作业（进程）的下一页P P，分配一，分配一可用页帧可用页帧f f，将，将P P的内容抄到的内容抄到f f中。中。（3 3）将）将f f抄到页抄到页P P的页表项中。的页表项

39、中。（4 4）若所有页都处理完，则结束，否则转向）若所有页都处理完，则结束，否则转向2 2。存储管理 四、共享与保护l在操作系统中，很多代码是可以共享的，如在操作系统中，很多代码是可以共享的，如命令解释程序、编译程序、编辑程序等。在连命令解释程序、编译程序、编辑程序等。在连续分配存储空间模式下，共享是不可能的，因续分配存储空间模式下，共享是不可能的，因为一个作业运行时只能访问一片连续的区域，为一个作业运行时只能访问一片连续的区域，多个作业显然不能与被共享程序都保持连续。多个作业显然不能与被共享程序都保持连续。l在页式系统中便可实现共享。通过页表可以在页式系统中便可实现共享。通过页表可以使几个逻

40、辑空间指向同一个物理空间，实现程使几个逻辑空间指向同一个物理空间，实现程序共享。序共享。存储管理 举例举例：有有3 3个进程共享编辑程序个进程共享编辑程序EDITEDIT，EDITEDIT长度为长度为3 3页，分别驻留在主存的页，分别驻留在主存的3 3、4 4、6 6号页号页帧中。帧中。EDIT1EDIT2EDIT3DATA1EDIT1EDIT2EDIT3DATA2EDIT1EDIT2EDIT3DATA33461346734610OSDATA1EDIT101234567891011EDIT2EDIT3 DATA2DATA3P1P2P3页表存储管理每个进程在运行时由自己的页表来进行地每个进程在运

41、行时由自己的页表来进行地址映射，从而实现了多个进程对一个址映射，从而实现了多个进程对一个EDIT程序的共享。程序的共享。存储管理 存储保护引入页式不连续分配以后，由于共享的出现对存引入页式不连续分配以后，由于共享的出现对存储保护也提出了新的要求。除了仍需要越界保护储保护也提出了新的要求。除了仍需要越界保护以外，对共享页还要进行特殊的保护。以外，对共享页还要进行特殊的保护。 越界保护：设置页表长度寄存器，查页表前，越界保护：设置页表长度寄存器，查页表前，先检查页号是否越界。先检查页号是否越界。 操作访问保护：在每个页表项中增设一存储保操作访问保护：在每个页表项中增设一存储保护域，用于说明对该页的

42、访问权限，每一个对该护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先要比照是否满足该页访问权页存储的访问都首先要比照是否满足该页访问权限的说明，满足则访问，否则报错。限的说明，满足则访问，否则报错。存储管理设为每一页表项增加三位，设为每一页表项增加三位，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 1

43、1 10 01 11 11 1存储管理五、两级页表 现代的大多数计算机系统，都支持非常大的逻辑地址空间现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有大的内存空间。例如，对于一个具有32位逻辑地址空间的分页位逻辑地址空间的分页系统，规定页面大小为系统，规定页面大小为4KB即即212B，则在每个进程页表中的页，则在每个进程页表中的页表项可达表项可达1兆个之多。又因为每个页表项占用一个字节，兆个之多。又因为每个页表项占用一个字节， 故每故每个进程仅仅其页表就

44、要占用个进程仅仅其页表就要占用1MB的内存空间，而且还要求是连的内存空间，而且还要求是连续的。续的。 可以采用这样两个方法来解决这一问题：可以采用这样两个方法来解决这一问题： 采用离散采用离散分配方式来解决难以找到一块连续的大内存空间的问题：分配方式来解决难以找到一块连续的大内存空间的问题： 只将当前需要的部分页表项调入内存，只将当前需要的部分页表项调入内存， 其余的页表项仍驻留其余的页表项仍驻留在磁盘上，需要时再调入。在磁盘上，需要时再调入。 存储管理1. 两级页表两级页表(Two-Level Page Table) 逻辑地址结构可描述如下：逻辑地址结构可描述如下： 存储管理图4-14两级页

45、表结构存储管理图图 4-15 具有两级页表的地址变换机构具有两级页表的地址变换机构 存储管理 练习：练习：某使用二级页表的系统的虚地址是某使用二级页表的系统的虚地址是32位。位。地址的后地址的后9位是一级页表的索引，中间位是一级页表的索引，中间11位位指定二级页表项。试问：指定二级页表项。试问：(1)页的大小是多少个字节？页的大小是多少个字节？(2)一级页表的长度是多少？一级页表的长度是多少？(3)二级页表的长度是多少？二级页表的长度是多少？(4)虚地址空间中有多少个页？虚地址空间中有多少个页？存储管理4.2.2 4.2.2 段式管理段式管理页式管理页式管理：对用户而言不自然，用户看待对用户而

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

47、配内存。 一、空间安排 例如，某用户作业（进程）由主程序、两个例如，某用户作业（进程）由主程序、两个子程序、栈和一段数据组成。于是可将这个作子程序、栈和一段数据组成。于是可将这个作业划分为业划分为5 5个段。个段。 逻辑地址：段号逻辑地址：段号. .段内偏移，记作段内偏移，记作S,dS,d。编译。编译及装配时把所有地址记成及装配时把所有地址记成(S,d)(S,d)的形式。若作业的形式。若作业正在运行主程序，则地址形式为（正在运行主程序，则地址形式为（0 0，d d）；一）；一旦调用子程序旦调用子程序1 1，地址变为（，地址变为（1 1，d d）；若访问数）；若访问数据段，地址变为（据段，地址变

48、为（4 4，d d）。）。存储管理 物理内存空间管理：与多道可变划分法物理内存空间管理：与多道可变划分法一样，系统以段为单位分配物理内存。一样，系统以段为单位分配物理内存。 主程序主程序 子程序子程序1 子程序子程序2栈栈数据数据逻辑空间逻辑空间 子程序子程序2主程序主程序栈栈数据数据OS 子程序子程序1物理空间物理空间存储管理二、动态地址转换保护码段长 本段在内存始地址由于作业在逻辑空间连续但主存空间不连续，由于作业在逻辑空间连续但主存空间不连续，故运行时需要进行地址转换。故运行时需要进行地址转换。段表：由如下格式的段表项组成，作业每段由由如下格式的段表项组成，作业每段由一个段表项表示一个段

49、表项表示. .作业被划分成作业被划分成n n段，段表就应段，段表就应该有该有n n项项段表放于系统空间。系统还设置段表始地址寄段表放于系统空间。系统还设置段表始地址寄存器、段表长度寄存器。存器、段表长度寄存器。存储管理段号 保护码 段长 段内存始址.保护码 段长 段内存始址.Sd段表始址段表长度+PA越界地址转换过程地址转换过程LA联想存储器联想存储器存储管理 对于用户而言对于用户而言，段页式管理与段式相同，用户，段页式管理与段式相同，用户逻辑地址只涉及段号与段内位移。逻辑地址只涉及段号与段内位移。 对于物理内存管理而言对于物理内存管理而言，它与页式系统相同。，它与页式系统相同。4.2.34.

50、2.3段页式管理段页式管理特点：将作业分成若干段，每段用页式管将作业分成若干段，每段用页式管理实现内存分配理实现内存分配。一、空间安排存储管理作业空间的内部表示主程序子程序数据保护码长度页表始地OS段表页表主存作业段表段表+ +页表页表存储管理段表主程序子程序数据作业1主程序子程序数据作业2段表页表OS主存存储管理在段页式管理中，逻辑地址由段号、段内页号以及页内位移三部分组成。 存储管理存储管理总结总结“放放” 连续存放连续存放 单道连续划分单道连续划分 多道连续固定划分多道连续固定划分 多道连续可变划分多道连续可变划分 不连续存放不连续存放 页式存储页式存储 段式存储段式存储 段页式存储段页

51、式存储存储管理 练习练习在页式存储管理中，某作业的逻辑地址空在页式存储管理中，某作业的逻辑地址空间为间为4页（页大小为页（页大小为1KB），作业的页面映），作业的页面映像为像为0-3#,1-2#,2-8#,3-6# ，求出逻辑，求出逻辑地址地址3047所对应的物理地址。所对应的物理地址。 存储管理 练习：练习：某使用二级页表的系统的虚地址是某使用二级页表的系统的虚地址是32位。位。地址的后地址的后9位是一级页表的索引，中间位是一级页表的索引，中间10位位指定二级页表项。试问：指定二级页表项。试问：(1)页的大小是多少个字节？页的大小是多少个字节？(2)一级页表的长度是多少？一级页表的长度是多少

52、？(3)二级页表的长度是多少？二级页表的长度是多少？(4)虚地址空间中有多少个页？虚地址空间中有多少个页？存储管理 练习：练习：在某段页式系统中，虚地址空间包含了在某段页式系统中，虚地址空间包含了8个个段，段长为段，段长为229B。硬件把每个段分成大小。硬件把每个段分成大小为为256B的页，问虚地址中有多少位用于指的页，问虚地址中有多少位用于指定：定：（1）段号；）段号；（2）页号；）页号；（3）页内偏移量；）页内偏移量；（4）整个虚地址。）整个虚地址。存储管理假定某操作系统存储器采用页式存储管理假定某操作系统存储器采用页式存储管理，页的大小为，页的大小为64字节，假定一进程的代码字节，假定一

53、进程的代码段长度为段长度为702个字节，页表如左表所示。个字节，页表如左表所示。现进程有如下的访问序列现进程有如下的访问序列：其逻辑地址为八进制的：其逻辑地址为八进制的105105、217217、567567、11201120、25002500。试问给定的这些地址。试问给定的这些地址能否进行转换？若能，请说能否进行转换？若能，请说明地址转换过程及相应的物明地址转换过程及相应的物理地址。若不能，则说明理理地址。若不能，则说明理由。由。存储管理4.3.1虚存的基本思想4.3 4.3 虚存管理虚存管理目的：提供用户进程一个巨大的虚拟存储空间提供用户进程一个巨大的虚拟存储空间. .手段：手段：通过统一

54、管理主存、辅存，利用辅存实通过统一管理主存、辅存，利用辅存实现此虚空间现此虚空间. .系统为进程提供一个比物理内存大得多的系统为进程提供一个比物理内存大得多的虚拟存储空间，虚拟空间大小不受物理内虚拟存储空间，虚拟空间大小不受物理内存大小的限制。存大小的限制。 虚拟空间的容量由系统的有效地址长度决虚拟空间的容量由系统的有效地址长度决定。假设地址长度为定。假设地址长度为3232，按字节寻址，则，按字节寻址，则虚拟存储空间大小为虚拟存储空间大小为2 23232个字节。个字节。存储管理实现页式虚空间的基本方法是： 在页式管理的基础上，仅将进程的一部在页式管理的基础上，仅将进程的一部分页放于主存。页表项

55、中注明该页是否在分页放于主存。页表项中注明该页是否在主存。程序执行时，如果访问的页不在主主存。程序执行时，如果访问的页不在主存，根据页表项的指示，将其从辅存调入存，根据页表项的指示，将其从辅存调入主存，如果此时无可用的内存空间，则先主存，如果此时无可用的内存空间，则先淘汰若干页帧。淘汰若干页帧。存储管理虚拟内存是把一个程序所需要的存储空间虚拟内存是把一个程序所需要的存储空间分成若干页，程序运行用到页就放在内存分成若干页，程序运行用到页就放在内存里，暂时不用就放在外存中。当用到外存里，暂时不用就放在外存中。当用到外存中的页时，就把它们调到内存，反之就把中的页时，就把它们调到内存，反之就把它们送到

56、外存中。它们送到外存中。存储管理一、页表项结构:合法位修改位页类型保护码辅存块号页帧号合法位：合法位：置上表示该页在内存置上表示该页在内存. .修改位：修改位：置上表示该页被修改过，在释放或淘汰时应回写置上表示该页被修改过，在释放或淘汰时应回写辅存。辅存。页类型页类型: :1 1、零页时：表示该页在分配物理页帧时应清零页时：表示该页在分配物理页帧时应清0 0页页帧空间帧空间;2;2、回写、回写swapswap区页时区页时: :表示在回写时必须分配表示在回写时必须分配swapswap区，并回写到区，并回写到swapswap空间中。没有设置页类型时，表示按正空间中。没有设置页类型时，表示按正常方式

57、处理。常方式处理。保护码：保护码：R R、W W、E E保护说明。保护说明。辅存块号：辅存块号：该页所在辅存的块号。该页所在辅存的块号。页页 帧帧 号：号：当合法位置上时代表该页所在内存的页帧号。当合法位置上时代表该页所在内存的页帧号。4.3.2 页式虚存管理存储管理交换区（交换区（SWAPSWAP）：）：进程刚建立时，进程页进程刚建立时，进程页面所在的辅存即程序文件所在的辅存位置。程面所在的辅存即程序文件所在的辅存位置。程序文件中一般包含有程序的二进制目标码及数序文件中一般包含有程序的二进制目标码及数据初始值和初值为据初始值和初值为0 0的工作区。的工作区。l程序在进程的运行过程中，数据的初

58、始值页面程序在进程的运行过程中，数据的初始值页面被调入主存使用，而且存放初始值的主存单元被调入主存使用，而且存放初始值的主存单元可能被修改。这时，系统不能将修改过的页面可能被修改。这时，系统不能将修改过的页面回写到执行程序文件中去，因为执行程序中的回写到执行程序文件中去，因为执行程序中的初始值不能被改变。因此引入了交换区用于存初始值不能被改变。因此引入了交换区用于存放那些可读写的页面。放那些可读写的页面。存储管理l还有一种页面，在执行程序文件中被说明是初还有一种页面，在执行程序文件中被说明是初值为值为0 0的工作区，我们称为零页，表示该页的初的工作区，我们称为零页，表示该页的初值为值为0 0。

59、这种页面分配主存页帧时不必从辅存获。这种页面分配主存页帧时不必从辅存获得初始数据，只要在分配页帧时，将页帧清得初始数据，只要在分配页帧时，将页帧清0 0即即可。当回写时，也需要分配交换空间，然后回可。当回写时，也需要分配交换空间，然后回写到交换空间中。写到交换空间中。存储管理 在执行虚存访问指令时在执行虚存访问指令时, ,由硬件合成物理地由硬件合成物理地址。首先若能在联想存储器中获得该虚页的物址。首先若能在联想存储器中获得该虚页的物理页帧号，则访问之。若要查当前进程页表，理页帧号，则访问之。若要查当前进程页表，须先检查该页页表项的合法位，若置上，则从须先检查该页页表项的合法位，若置上，则从页表

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