操作系统讲义-第四章

1、2022-6-28操作系统讲义1第四章第四章 存储器管理存储器管理2022-6-28第四章 存储器管理2主要内容主要内容 4.1 存储器管理的层次结构存储器管理的层次结构 4.2 程序的装入和链接程序的装入和链接 4.3 连续分配方式连续分配方式 4.4 基本分页存储管理方式基本分页存储管理方式 4.5 基本分段存储管理方式基本分段存储管理方式 4.6 虚拟存储器的基本概念虚拟存储器的基本概念 4.7 请求分页存储管理方式请求分页存储管理方式 4.8 页面置换算法页面置换算法 4.9 请求分段存储管理方式请求分段存储管理方式2022-6-28第四章 存储器管理3存储器管理概述存储器管理概述 存

2、储器是计算机系统的重要组成部分，随着存储器是计算机系统的重要组成部分，随着计算机技术的发展，系统软件和应用软件在种类、计算机技术的发展，系统软件和应用软件在种类、功能及其所需存储空间等方面，都在急剧地膨胀，功能及其所需存储空间等方面，都在急剧地膨胀，虽然存储器的容量也不断扩大，但是仍不能满足虽然存储器的容量也不断扩大，但是仍不能满足现在软件发展的需要，它仍然是一种紧俏的资源，现在软件发展的需要，它仍然是一种紧俏的资源，所以如何有效地管理存储器，不仅影响到存储器所以如何有效地管理存储器，不仅影响到存储器的利用率，而且还对系统性能有重大的影响。的利用率，而且还对系统性能有重大的影响。 存储器管理的

3、主要对象：内存内存。 2022-6-28第四章 存储器管理4存储器管理概述存储器管理概述 有的作业很大，所要求的内存空间超过内存总容量，有的作业很大，所要求的内存空间超过内存总容量，作业不能全部装入，致使该作业无法运行；作业不能全部装入，致使该作业无法运行； 有大量作业要求运行，但内存不足以容纳所有的作有大量作业要求运行，但内存不足以容纳所有的作业，只能让少数作业装入内存先运行，而将大量作业，只能让少数作业装入内存先运行，而将大量作业留在外存等待。业留在外存等待。 显而易见，一种解决办法就是从物理上增加内存的容量，显而易见，一种解决办法就是从物理上增加内存的容量，另一种方法就是从逻辑上扩充内存

4、的容量，也就是利用另一种方法就是从逻辑上扩充内存的容量，也就是利用虚拟存储技术解决。虚拟存储技术解决。 如果某存储器管理方式要求一个作业全部装入内存才能够运行，那么就会出现两种情况：2022-6-28第四章 存储器管理54.1 存储器管理的层次结构存储器管理的层次结构 速度非常快，能跟上处理机的速度速度非常快，能跟上处理机的速度 容量非常大，能容纳所有要运行的作业容量非常大，能容纳所有要运行的作业 价格很便宜，不需要花费额外的钱价格很便宜，不需要花费额外的钱 存储器的理想状态：存储器的理想状态：1. 多级存储结构多级存储结构 计算机存储层次至少应具有三级：CPU寄存器，主存，辅存。 注意注意：

5、存储层次越往上，存储介质的访问速度越快，价：存储层次越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。格也越高，相对存储容量也越小。CPU存储器主存辅存2022-6-28第四章 存储器管理64.1 存储器管理的层次存储器管理的层次2. 主存储器和寄存器主存储器和寄存器 主存储器（简称内存或主存）：主存储器（简称内存或主存）：计算机的主要部件，用于保存进程运行时的程序和数据，可称为可执行存储器；微机和大中型机：数十MB到数GB；嵌入式计算机：数十KB到几MB；CPU和外围设备交换信息的依托；访问速度远低于CPU执行指令的速度。2022-6-28第四章 存储器管理74.1 存储器管理

6、的层次存储器管理的层次2. 主存储器和寄存器主存储器和寄存器寄存器：寄存器：能够与CPU协调工作的计算机部件；微机和大中型机：数十到上百个Word；嵌入式计算机：几个到几十个Word；访问速度快；价格十分昂贵；容量很小。2022-6-28第四章 存储器管理84.1 存储器的层次结构存储器的层次结构3. 高速缓存和磁盘缓存高速缓存和磁盘缓存高速缓存：高速缓存：是计算机中的一个重要部件，其容量大于或远大于寄存器，而比内存小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器； （1）程序执行的局部性原理； （2）速度越高价格越贵，计算机系统中经常设置两级或多级高速缓存； （3）紧靠内存的一

7、级高速缓存速度最高，容量最小，二级缓存容量稍大，速度也稍低。2022-6-28第四章 存储器管理94.1 存储器的层次结构存储器的层次结构3. 高速缓存和磁盘缓存高速缓存和磁盘缓存磁盘缓存：磁盘缓存：并不是实际的存储介质，依托于固定磁盘，提供对主存储器存储空间的扩充。 （1）磁盘的I/O速度远低于主存的访问速度； （2）主存也可以看做是辅存的高速缓存； （3）大容量的辅存常常使用磁盘，磁盘数据经常备份到磁带或者可移动的磁盘中，以防止硬盘故障时丢失数据。2022-6-28第四章 存储器管理104.2 程序的装入和链接程序的装入和链接 一个用户源程序要变成一个可在内存中执行的程序都要经一个用户源程

8、序要变成一个可在内存中执行的程序都要经过以下几个步骤：过以下几个步骤： 编译：将用户源代码编译成目标代码；编译：将用户源代码编译成目标代码； 链接：将目标模块及它们所需要的库函数链接在一起；链接：将目标模块及它们所需要的库函数链接在一起； 装入：将装入模块装入内存。装入：将装入模块装入内存。库库链接链接程序程序编译编译程序程序产生产生的目的目标模标模块块装入模块装入模块装入装入程序程序内存内存第一步第一步第二步第二步第三步第三步2022-6-28第四章 存储器管理114.2 程序的装入和链接程序的装入和链接绝对装入方式（绝对装入方式（Absolute Loading Mode） 编译时，知道程

9、序所驻留内存的具体位置，编译程序将产生绝对地址的目标代码，这个绝对地址可以在编译或者汇编时给出，也可由程序员赋予。 1. 程序的装入程序的装入可重定位装入方式（可重定位装入方式（Relocation Loading Mode） 多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存何处，所以目标模块的起始地址通常从0开始，而程序中的其他地址则相对于起始地址计算而成。2022-6-28第四章 存储器管理124.2 程序的装入和链接程序的装入和链接 1. 程序的装入程序的装入动态运行时装入方式（动态运行时装入方式（Dynamic Run-time Loading Mode） 装入程序把装入模

10、块装入内存，并不立即把相对地址转换为绝对地址，而是把地址转换推迟到程序真正运行时再执行。0LOAD 1,2500100025005000365LOAD 1,2500365100001100012500150002022-6-28第四章 存储器管理134.2程序的装入和链接程序的装入和链接 2. 程序的链接程序的链接静态链接方式（静态链接方式（Static Linking Mode） (1)对相对地址进行修改；（2）变换外部调用符号模块ACALL B；Return；0L-1模块BCALL C；Return；0M-1模块C Return；0N-1模块ACALL B；Return；0L-1模块BCA

11、LL C；Return；L+M-1模块C Return；L+M+N-1LL+M目标模块装入模块2022-6-28第四章 存储器管理144.2程序的装入和链接程序的装入和链接 2. 程序的链接程序的链接装入时动态链接方式（装入时动态链接方式（Load-time Dynamic Linking Mode） 用户源程序编译后所得的目标模块，在装入内存时边装入边链接的，这种方式（1）便于修改和更新（2）便于实现对目标模块的共享。运行时动态链接方式（运行时动态链接方式（ Run-time Dynamic Linking Mode） 许多情况下，应用程序每次要运行的模块可能不相同，如果把所有模块都装入非常

12、低效，所以要在运行过程中动态装入所需模块。2022-6-28第四章 存储器管理154.3 连续分配方式连续分配方式 这是一种最简单的存储管理方式，只能用于单用户单任务的操作系统，内存分成系统区和用户区，系统区提供给OS使用，而用户区指除了系统区以外的全部内存空间，提供给用户使用。 1. 单一连续分配单一连续分配 这是一种最简单的可运行多道程序的存储管理方式，它将内存划为固定大小的区域，每个分区装入一道作业。 2. 固定分区分配固定分区分配2022-6-28第四章 存储器管理164.3 连续分配方式连续分配方式 2. 固定分区分配固定分区分配分区的划分方法分区大小相等：所有分区大小相等，缺点是缺

13、乏灵活性，程序太小时空间浪费，程序太大时无法运行；分区大小不等：克服了大小相等而缺乏灵活性的缺点，把内存分成多个较小的分区、适量的中等分区及少量的大分区。内存分配：将分区按照大小进行排队，并为之建立一张分区使用表，其各表项包括每个分区的起始地址、大小以及状态。2022-6-28第四章 存储器管理174.3 连续分配方式连续分配方式 3. 动态分区分配动态分区分配分区分配中的数据结构分区分配中的数据结构空闲分区表；空闲分区链。分区分配算法分区分配算法首次适应算法：首次适应算法：找到第一个大小能满足要求的空闲空间；循环首次适应算法：循环首次适应算法：从上次找到的空闲分区的下一个开始查找，找到一个能

14、满足要求的空闲分区；最佳适应算法：最佳适应算法：找到一个满足要求、又是最小的空闲分区分配给作业；最坏适应算法：最坏适应算法：挑选一个最大的空闲分区分割给作业；快速适应算法：快速适应算法：将空闲分区根据其容量大小分类，然后根据进程的长度，寻找到能容纳它的最小空闲分区链表，取下第一块进行分配。2022-6-28第四章 存储器管理184.3 连续分配方式连续分配方式分区分配操作分区分配操作 1）分配内存：分配内存：系统利用某种分配算法，从空闲分区链（表）系统利用某种分配算法，从空闲分区链（表）中找到所需大小的分区。中找到所需大小的分区。从头开始查表检索完否？m.sizeu.size？m.size-u

15、.sizesize？从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN2022-6-28第四章 存储器管理194.3 连续分配方式连续分配方式分区分配操作分区分配操作 2）回收内存：回收内存：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链（表）中找到相应的插入点。 a）回收区与插入点的前一个空闲分区F1相邻接，将回收区与插入点前的分区合并，不必为回收分区分配表项，修改前一分区F1的大小； b）回收区与插入点的后一空闲分区F2相邻接，此时可将两分区合并，形成新的空闲分区，回收区的首址作为新空闲区的首址，大小

16、为两者之和;F1回收区回收区F2(a)(b)2022-6-28第四章 存储器管理204.3 连续分配方式连续分配方式分区分配操作分区分配操作 2）回收内存回收内存 c）回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和首址，取消F2表项，大小为三者之和； d）回收区既不与F1邻接，又不与F2邻接，这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据首址插入到空闲链中的适当位置；F1回收区回收区F2(c)(d)2022-6-28第四章 存储器管理214.3 连续分配方式连续分配方式固定分区方式的不足：固定分区方式的不足：限制了活动进程的数目，当进程大小和空闲分

17、区大小不匹配时，空间利用率很低。动态分区方式的不足：动态分区方式的不足：算法复杂，回收空闲分区时需要进行分区合并等，系统开销大。伙伴系统：伙伴系统：上面两种内存方式的一种折衷，伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，lkm，其中 是分配的最小分区的大小， 表示分配的最大分区的大小，通常 是整个可分配内存的大小。 4. 伙伴系统伙伴系统伙伴系统的优点：算法在回收空闲分区时，需要对空闲分区进行合伙伴系统的优点：算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面分类搜索算法差，但比顺序搜索算法好，并，所以其时间性能比前面分类搜索算法差，但比顺序搜索算法好，而其空

18、间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。l2l2m2m22022-6-28第四章 存储器管理224.3 连续分配方式连续分配方式哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表。l2 5. 哈希算法哈希算法 6. 可重定位分区分配可重定位分区分配动态可重定位：动态可重定位：它的引入是为了解决系统中只有若干个小分区，即使它们容量之和大于要装入的程序，但由于这些分区不相邻接，无法装入该程序的情况。2022-6-28第四章 存储器管理234.3 连

19、续分配方式连续分配方式 6. 可重定位分区分配可重定位分区分配操作系统用户程序110KB用户程序330KB用户程序614KB用户程序926KB操作系统用户程序1用户程序3用户程序6用户程序980KB采用的方法：采用的方法：将内存中的所有作业进行移动，使它们全部相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可以把作业装入该区。定义：通过移动内存中作业的位置，把原来多个分散的小定义：通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法，称为分区拼接成一个大分区的方法，称为“拼接拼接”或或“紧凑紧凑”。2022-6-28第四章 存储器管理244.3 连续分配方式连

20、续分配方式 6. 可重定位分区分配可重定位分区分配动态重定位的实现：动态重定位的实现：作业装入内存后的所有地址仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时运行。LOAD 1,250036550002500 100 0作业作业J250010000相对地址重定位寄存器+LOAD 1,25003651500012500 1010010000主存主存2022-6-28第四章 存储器管理254.3 连续分配方式连续分配方式 6. 可重定位分区分配可重定位分区分配动态重定位分区分配算法：动态重定位分区分配算法：类似于动态分区分配算法，不过是在算法中增加了紧凑功能，通常在找不

21、到足够大的空闲分区来满足用户需求时进行紧凑。请求分配u.size分区检索空闲分区链（表）找到大于u.size的可用分区否？按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size？无法分配返回紧凑形成连续空闲区修改有关的数据结构否是是否2022-6-28第四章 存储器管理264.3 连续分配方式连续分配方式 7. 对换（对换（Swapping） 对换引入的原因：对换引入的原因：多道程序环境下，内存中的一些进程因某事件而被阻塞运行，却占用大量内存空间，甚至可能所有进程阻塞而迫使CPU停止下来等待的情况；另一方面，许多作业在外存上等待，因无内存而不能运行。对换的定义：对换的

22、定义：是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出内存上，以便腾出足够的内存空间，再把具备运行条件的进程或进程所需的程序和数据调入内存。2022-6-28第四章 存储器管理274.3 连续分配方式连续分配方式 7. 对换（对换（Swapping）对换空间的管理：对换空间的管理：通常把外存分为文件区和对换区，其中文件区用于存放文件，对换区用于存放从内存换出的进程。进程的换出与换入进程的换出与换入进程的换出：进程的换出：首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将进程的程序和数据传送到磁盘的对换区上；进程的换入：进程的换入：系统应定时查看所有进程的状态，找出“

23、就绪”状态但已经换出的进程，将其中换出时间最久的进程作为换入进程，将之换入，直至已无可换入和无可换出进程为止。2022-6-28第四章 存储器管理284.4 基本分页存储管理方式基本分页存储管理方式页面 1）页面和物理块）页面和物理块:页面是指将进程的逻辑空间分成若干大小相等的片，物 理块是指将内存空间分成与页面相同大小的若干存储块； 2）页面大小）页面大小:页面大小应该适中，太小会使页表过长，太大会使碎片增大。 1. 页面和页表页面和页表地址结构：分页地址中的地址结构包括两部分：前一部分是页号P，后一部分为位移量W（或称为页内地址）。LAINTPLAdmod位移量W页号P3112 110页表

24、：在分页系统中，允许各个页离散地存储在内存不同的物理块内，但系统要保证进程的正确执行，所以系统又为每个进程建立了一张页面映射表。若给定一个逻辑地址空间中的地址为若给定一个逻辑地址空间中的地址为A，页面的大小为，页面的大小为L，则页，则页号号P和页内地址和页内地址d可按下式求得：可按下式求得：2022-6-28第四章 存储器管理294.4 基本分页存储管理方式基本分页存储管理方式基本的地址变换机构基本的地址变换机构 2. 地址变换机构地址变换机构页表长度页表首址当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址（相对地址）分为页号和页内地址两部分，再以页号为索引去检索页表。页

25、表寄存器+页内地址页号（3）逻辑地址L1 b 页表物理地址块号页号0123越界中断2022-6-28第四章 存储器管理304.4 基本分页存储管理方式基本分页存储管理方式具有快表的地址变换机构具有快表的地址变换机构 2. 地址变换机构地址变换机构页表长度页表首址在CPU给出有效地址后，由地址变换机构自动将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若找到匹配的页号，就表示要访问的页表项在快表中。页表寄存器+页内地址页号逻辑地址Lb 页表db物理地址块号页号越界中断输入寄存器b 快表块号页号 2022-6-28第四章 存储器管理314.4 基本分页存储管理方式基本分页存储

26、管理方式两级页表两级页表 3. 两级和多级页表两级和多级页表P2P1对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，可以支持2的64次方（1884744TB）规模的物理存储空间，一般可以利用三级页表结构来实现。外部页号+ 页表db物理地址 外部页表 d外部页表寄存器+外部页内地址页内地址逻辑地址多级页表多级页表2022-6-28第四章 存储器管理324.5 基本分段存储管理方式基本分段存储管理方式方便编程方便编程 通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0开始编址，并且有自己的名字和长度。 1. 分段存储管理方式的引入分段存储管理方式的引入信息共享信息共享

27、 在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分页系统中的“页”只是存放信息的物理块，并无完整的意义，不便于实现共享，而段却是信息的逻辑单位。信息保护信息保护 信息保护同样是对信息的逻辑单位进行保护，因此，分段管理方式能更有效和方便地实现信息保护功能。动态增长动态增长 实际应用中，往往有些段，特别是数据段，在使用过程中会不断增长，而事先无法确切地知道数据段会增长到多大，这时候其它存储管理方式无法解决这个问题。动态链接动态链接 在作业运行之前，并不把几个目标程序段链接起来，而是在运行过程中需要调用某段时，才将该段调入内存进行链接。2022-6-28第四章 存储器管理334.5 基本分

28、段存储管理方式基本分段存储管理方式分段分段 在这里，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如出程序段MAIN、子程序段X、数据段D和栈段S等。 2. 分段系统的基本原理分段系统的基本原理段表段表 在分段式存储管理系统中，为每个分段分配一个连续的分区，而进程中的每个段可以离散地移入内存中不同的分区中，像分页系统一样，在系统中为每个进程建立一张映射表，称为“段表”。作业空间作业空间（MAIN）=0030K（X）=1020K（D）=2015K（S）=3010K30K20K15K10K40K80K120K150K段段 表表段号 段长 基址0123（MAIN）=030K（X）=12

29、0K（D）=215K（S）=310K内存空间内存空间40K80K120K150K2022-6-28第四章 存储器管理344.5 基本分段存储管理方式基本分段存储管理方式分段系统的地址变换过程分段系统的地址变换过程 在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。在进行地址变换时，将逻辑地址中的段号和段表长度TL进行比较。若STL，表示段号太大，访问越界，产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，进而将该段基址d与段内地址相加，得到要访问的内存物理地址。 2. 分段系统的基本原理分段系统的基本原理段表长度段表长

30、度段表首址段表首址控制寄存器控制寄存器+1002 段号段号S 位移量位移量W主存主存越界中断越界中断6K4K 8K 9200基址基址段长段长1K600500200段号段号0123+82928K829286922022-6-28第四章 存储器管理354.5 基本分段存储管理方式基本分段存储管理方式分段和分页的主要区别分段和分页的主要区别 分段和分页都采用离散分配方式，且都要通过地址映射机构来实现地址变换，这是它们的相似之处，但是在概念上两者完全不同，主要表现在： 2. 分段系统的基本原理分段系统的基本原理分页分页分段分段目的提高内存的利用率更好地满足用户需求形式信息的物理单位信息的逻辑单位大小页

31、的大小固定且由系统决定段的长度不固定，由用户编写的程序决定地址空间 一维，单一的线性空间二维，包括段名和段内地址 3. 信息共享信息共享分段系统的优点：允许多个进程共享一个或多个分段。可重入代码可重入代码是一种允许多个进程同时访问的代码，不允许可重入代码在执行中有任何改变。2022-6-28第四章 存储器管理364.5 基本分段存储管理方式基本分段存储管理方式基本原理：是分段和分页原理的结合，即先将用户程序分成若干个基本原理：是分段和分页原理的结合，即先将用户程序分成若干个段，然后再把每个段分成若干个页，并为每个段赋予一个段名。段，然后再把每个段分成若干个页，并为每个段赋予一个段名。 4. 段

32、页式存储管理方式段页式存储管理方式段表始址段表大小段表寄存器主存段号状态页表大小页表始址0111213041页号状态存储块#0111213041页表操作系统2022-6-28第四章 存储器管理374.5 基本分段存储管理方式基本分段存储管理方式地址变换过程地址变换过程 4. 段页式存储管理方式段页式存储管理方式段表长度段表首址段表寄存器+页号P段号S段超长页表始址页表长度段表0123+页内地址块内地址块号bb页表01232022-6-28第四章 存储器管理384.6 虚拟存储器的基本概念虚拟存储器的基本概念常规存储器管理方式的特征常规存储器管理方式的特征一次性：作业在运行前要一次性装入内存；驻

33、留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。 1. 虚拟存储器的引入虚拟存储器的引入局部性原理局部性原理 1968年Denning.P指出：程序在执行时将呈现出局部性规律，即在较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域，他提出几个论点： （1）除了少部分转移和过程调用指令，程序大多数情况下是顺序执行的； （2）过程调用会让程序的执行由一部分区域移至另一部分区域； （3）程序中存在许多循环结构，虽然由少数指令构成，但是要多次执行； （4）程序中许多对数据结构（如数组）的操作，往往局限于很小的范围内。2022-6-28第四章 存储器管理39

34、4.6 虚拟存储器的基本概念虚拟存储器的基本概念 1. 虚拟存储器的引入虚拟存储器的引入局限性表现局限性表现时间局限性：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行，数据访问也是类似；空间局限性：一旦程序访问了某个存储单元，不久以后，其附近的存储单元也将被访问，即程序某一段时间访问的地址可能集中在一定范围内。虚拟存储器的定义：是指具有请求调入功能和置换功能，能从逻虚拟存储器的定义：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。辑上对内存容量加以扩充的一种存储器系统。 2. 虚拟存储器的特征虚拟存储器的特征（1）多次性）多次性 （2）对换性）对换性 （

35、3）虚拟性）虚拟性2022-6-28第四章 存储器管理404.6 虚拟存储器的基本概念虚拟存储器的基本概念 虚拟存储器中，允许将一个作业分多次调入内存，它的实现毫无例外地建立在离散分配的存储管理方式的基础上。（1）请求分页系统）请求分页系统 在基本分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。硬件支持包括(a)请求分页的页表机制 (b)缺页中断机构 (c)地址变换机构；软件支持：包括用于请求调页的软件和实现页面置换的软件。（2）请求分段系统）请求分段系统 在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。硬件支持包括(a)请求分段的段表机

36、制 (b)缺段中断机构 (c)地址变换机构软件支持：包括用于请求调段的软件和实现段面置换的软件。 3. 虚拟存储器的实现方法虚拟存储器的实现方法2022-6-28第四章 存储器管理414.7 请求分页存储管理方式请求分页存储管理方式页表机制页表机制 在请求分页系统中所需要的主要数据结构是页表，其基本作用是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。 1. 请求分页中的硬件支持请求分页中的硬件支持缺页中断机构缺页中断机构 当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存，它和一般中断的区别主要表现在：（1）在指令执行期间产生和处理中断信号；（2）一条指令在执行期

37、间，可能产生多次缺页中断。（1）状态位P：标识本页的存取属性是只执行，只读，还是允许读/写;（2）访问字段A：用于记录该页被访问的频繁程度；（3）修改位M：用于表示该页进入内存后是否被修改过；（4）外存始址：指示本页在外存中的起始地址，即起始盘块号。页号物理块号访问字段A修改位M状态位P外存始址2022-6-28第四章 存储器管理424.7 请求分页存储管理方式请求分页存储管理方式 1. 请求分页中的硬件支持请求分页中的硬件支持地址变换机构地址变换机构 开始页号页表长度？CPU检索快表否是访问页表页表项在快表中？页在内存？修改快表修改访问位和修改位形成物理地址地址变换结束保留CPU现场从外存中

38、找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表越界中断否是否是是否是产生缺页中断请求调页程序请求访问一页2022-6-28第四章 存储器管理434.7 请求分页存储管理方式请求分页存储管理方式 2. 内存分配策略和分配算法内存分配策略和分配算法最小物理块数的确定最小物理块数的确定 最小物理块数是只能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。物理块的分配策略物理块的分配策略 1）固定分配局部置换：）固定分配局部置换：为每个进程分配一定数目的物理块，在整个运行期间不再改变

39、； 2）可变分配全局置换：）可变分配全局置换：为每个进程分配一定数目的物理块，OS自身也保持一个空闲物理块队列，用于分配给缺页进程； 3）可变分配局部置换：）可变分配局部置换：为每个进程分配一定数目的物理块，当缺页时，只允许该进程从内存的页面中选出一页换出，这样不会影响其他进程。2022-6-28第四章 存储器管理444.7 请求分页存储管理方式请求分页存储管理方式 2. 内存分配策略和分配算法内存分配策略和分配算法物理块的分配算法物理块的分配算法 1）平均分配法：平均分配法：将系统中所有可供分配的物理块平均分配给各个进程； 2）按比例分配法：按比例分配法：按照进程的大小按比例分配物理块； 3

40、）考虑优先级的分配法：考虑优先级的分配法：通常把内存中可供分配的物理块分成两部分，一部分按比例分配给各进程，另一部分则根据各进程的优先级，适当增加其份额，分配给各进程。 3. 调页策略调页策略调入页面的时机调入页面的时机 1）预调页策略 2）请求调页策略2022-6-28第四章 存储器管理454.7 请求分页存储管理方式请求分页存储管理方式 3. 调页策略调页策略确定从何处调入页面确定从何处调入页面 请求分页系统中的外存分成两部分：文件区（用于存放文件）和对换区（用户存放对换页面），缺页请求调页时分下列三种情况： 1）系统拥有足够的兑换空间，此时可全部从对换区调入所需页面； 2）系统缺少足够的

41、对换区空间，此时不会被修改的文件从文件区调入； 3）UNIX方式：凡是未运行过的页面都应从文件区调入，曾经运行过的页面都从对换区调入。页面调入过程页面调入过程 当程序要访问的页面未在内存时，便向CPU发出缺页中断，中断处理程序会保留CPU环境，分析中断原因并转入中断处理程序，在外存中找到缺页的物理块，如果内存能容纳，则将之调入，否则根据算法选择一页换出，并修改相应的数据结构。2022-6-28第四章 存储器管理464.8 页面置换算法页面置换算法 1. 先进先出（先进先出（FIFO）页面置换算法）页面置换算法最早出现的置换算法，总是淘汰最先进入内存的页面。 2. 最佳（最佳（Optimal）页

42、面置换算法）页面置换算法1966年由Belady提出的，选择的被淘汰的页面都是以后永不使用或者在最长（未来）时间内。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 123 12304304204230230130127127027017 70 70 120 1缺页次数为缺页次数为15次，缺页率次，缺页率: 15/20=75%7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 70 70 120 120 3243203201701缺页次数为缺页次数为9次，次， 缺页率缺页率: 9/20=45%2022-6-28第四章 存储器管理474.8

43、 页面置换算法页面置换算法 3. 最近最久未使用（最近最久未使用（LRU）页面置换算法）页面置换算法地址变换机构地址变换机构 LRU算法选择最近最久未使用的页面予以淘汰。LRU的硬件支持的硬件支持 1）寄存器：为了记录某个进程在内存中各页的使用情况，需要为每个内存中的页面设置一个寄存器。 2）栈：每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。20 34034024320321321021077 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 70 70 120 1缺页次数为缺页次数为12次，缺页率次，缺页率: 12/20=60% 4. 其他页面

44、置换算法其他页面置换算法最少使用置换算法和页面缓冲算法。2022-6-28第四章 存储器管理484.9 请求分段存储管理方式请求分段存储管理方式 1. 请求分段中的硬件支持请求分段中的硬件支持段表机制段表机制 请求分段式管理中所需的主要数据结构是段表。段表项中，除了段名（号）、段长、段在内存中的起始地址外，增加了：（1）存取方式：标识本段的存取属性是只执行，只读，还是允许读/写;（2）访问字段A：用于记录该段被访问的频繁程度；（3）修改位M：用于表示该段进入内存后是否被修改过；（4）存在位P：指示本段是否已调入内存；（5）增补位：用于表示本段在运行过程中是否做过动态增长；（6）外存始址：指示本

45、段在外存中的起始地址，即起始盘块号。段名段名段的段的基址基址段长段长存取存取方式方式访问访问字段字段A修改修改位位M存在存在位位P增补位增补位外存外存始址始址2022-6-28第四章 存储器管理494.9 请求分段存储管理方式请求分段存储管理方式 1. 请求分段中的硬件支持请求分段中的硬件支持缺段中断机构缺段中断机构 在请求分段系统中，当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生缺段中断信号，进入OS后由缺段中断处理程序将所需的段调入内存。虚段S不在内存内存中有合适的空闲区吗？修改段表及内存空区链唤醒请求进程返 回阻塞请求进程淘汰一个或几个实段，以形成一个合适空区空区拼接，以

46、形成一个合适的空区是否否是空区容量总和能满足要求？从外存读入段S2022-6-28第四章 存储器管理504.9 请求分段存储管理方式请求分段存储管理方式 1. 请求分段中的硬件支持请求分段中的硬件支持地址变换机构地址变换机构 请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的，地址变幻时，如果要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能利用段表进行地址变换。访问sww段长？符合存取方式？段S在主存？修改访问字段，如写访问，置修改位=1形成访问主存地址(A)=(主存地址)+(位移量w)返 回分段越界中断处理分段保护中断处理缺段中断处理是否否否是是2022-6

47、-28第四章 存储器管理514.9 请求分段存储管理方式请求分段存储管理方式 2. 分段的共享与保护分段的共享与保护共享段表：为了实现分段共享，可在系统中配置一张共享段表，所共享段表：为了实现分段共享，可在系统中配置一张共享段表，所有共享段都在共享段表中占有一表项。有共享段都在共享段表中占有一表项。.共享段表共享段表段名段名段长段长段长段长内存始址内存始址外存始址外存始址状态状态 进程名进程名段号段号进程号进程号存取控制存取控制共享进程计数共享进程计数count 共享进程计数共享进程计数count：为了记录有多少个进程需要共享该分段；存取控制字段：存取控制字段：为了给不同的进程设置不同的存取权限；段号：段号：不同的进程可以用不同的段号去共享该段。2022-6-28第四章 存储器管理524.9 请求分段存储管理方式请求分段存储管理方式 2. 分段的共享与保护分段的共享与保护共享段的分配与回收共享段的分配与回收 共享段的分配：共享段的分配：共享段内存的分配方法与非共享段的不同，对请求共享段的进程，要系统首先分配