操作系统第七章 主存管理

1、第七章 主存管理 在多道批处理系统或分时系统中，要求在主存中同时存放多个作业或用户程序，这就需要引入存储管理。7.2主存管理的功能主存管理的功能 为方便用户使用，系统必须为每个用户提供0n-1的一组逻辑地址，即用户编译时，程序访问的地址为虚地址或逻辑地址，而主存单元的地址为实地址或物理地址。如图所示：0 Mov r1,500 : :500 01EFH : :逻辑地址程序1物理地址物理地址mMov r1,500: 01EFH:内存 m+500思考：为什么用户编程时不直接使用物理地址？主存管理的主要功能：1. 逻辑地址到物理地址的映射2. 主存的分配和回收3. 存储保护：保护进入主存的各道作业都在

2、自己的存储空间内运行，互不干扰，防止一道作业由于发生错误而破坏其他作业或系统程序。4. 提高主存利用率：使多道程序能动态共享主存中的信息。如段式系统中，代码段是可共享的。5. “扩大”主存容量：借助虚拟存储技术，为用户提供比主存空间大的地址空间。7.3分区存储管理 分区：是指主存的某一连续空间 分区存储管理是将内存划分为若干分区，除OS占用一个分区外，其余每一个分区容纳一个作业或进程。1. 固定分区：将内存用户区划分为若干固定大小的区域，每个区域中驻留一道程序。2. 动态分区：根据用户程序的大小，动态的对内存进行划分，可以提高内存的利用率。作业1作业2作业3作业1作业2作业3固定分区活动分区7

3、.3.1 分区存储管理概述可以从一下几个方面讨论分区存储管理技术：1. 存储保护上、下界限保护 基址、限长保护作业作业 （4KB）20K 24K-1 20K下界寄存器24K-1上界寄存器当物理地址D应该满足：20K D 24K或20K D 24K-1上、下界限保护7.3.1 分区存储管理概述可以从一下几个方面讨论分区存储管理技术：1. 存储保护上、下界限保护 基址、限长保护作业作业 （4KB）20K 24K-1 20K基址寄存器4K限长寄存器当物理地址D应该满足：20K D 20K+4K或20K D 20K+4K-1基址、限长保护2、地址映射（基址寄存器）+逻辑地址物理地址其中（基址寄存器）存

4、放一个作业在主存所占分区的首地址。0 Mov r1,500 : :500 01EFH : :逻辑地址程序1物理地址物理地址mMov r1,500: 01EFH:内存 m+500逻辑地址(500)+ 基址寄存器（m） 物理地址 m+5007.3.3分区的分配和回收 空闲区队列（自由主存队列）可以按照某种分类方法进行排序。1. 按分区地址的大小排序2. 按空闲区的大小排序1、首次适应算法 空闲区队列中空闲区按地址从小到大排序。例如：OS空闲区（30KB）作业1空闲区（20KB）作业2空闲区（5KB）作业3空闲区（46KB）作业A 申请18KB自由主存队列（空闲区队列）如下：每个结点记录空闲区的大小

5、和下一个空闲区的首地址（指针）。head30KB5KB20KB46KB12KB1、分配一个空闲区：分配一个空闲区：扫描空闲区队列； If 申请块所有空闲块，则无法分配（或拼接）； If 申请块某一空闲块 则从空闲块的底部向上分配空闲区； /可以只修改空闲区的大小，而不修改空闲区队列的指针如果分配之后剩余的空闲块门限值，则将整个空闲块分配出去；2、回收一个空闲块：回收一个空闲块：设r为回收区,f为空闲区上邻空闲区下邻空闲区上、下邻空闲区上、下不相邻空闲区fr作业作业作业rff1rf2作业作业1r作业2空闲区总数不变：空闲区总数-1：空闲区总数+1：2、最佳适应算法空闲区队列中空闲区按大小从小到大

6、排序例如：OS空闲区（30KB）作业1空闲区（20KB）作业2空闲区（5KB）作业3空闲区（46KB）作业A 申请18KB自由主存队列（空闲区队列）如下：head5KB30KB20KB46KB2KB5KB3、最坏适应算法空闲区队列中空闲区按大小从大到小排序。例如：OS空闲区（30KB）作业1空闲区（20KB）作业2空闲区（5KB）作业3空闲区（46KB）作业A 申请18KB自由主存队列（空闲区队列）如下：head46KB20KB30KB5KB28KB三种算法到底哪一种最好不能一概而论，应针对具体的作业序列来分析。习题7.7 7.87.3.5碎片问题及拼接技术 碎片问题：空闲区之和大于申请块，但

7、任一空闲区小于申请块 拼接技术：移动存储器中某些已分配区中的信息，使本来分散的空闲区连接成一个大的空闲区。拼接时机： 回收一个分区时立即拼接，这样主存中总是只有一个连续的空闲区而无碎片，开销大。 当找不到足够大的空闲区，而空闲区总和可以满足作业需求时拼接，开销小，但空闲区管理复杂。拼接技术的缺点：1. 拼接程序花费CPU时间；2. 拼接时，必须停止所有的其他工作，对于交互用户，导致响应时间不规律；对于实时用户，由于不能及时响应而可能造成严重后果。3. 有时为拼接所花费的系统开销要大于拼接技术的效益4. 当所有空闲区之和无法满足某一作业需求时，该作业永远无法运行。虚拟存储器是存储管理的核心虚拟存

8、储器是存储管理的核心: 对大量的典型程序运行情况的分析表明，在t内，CPU对局部范围的存储器地址访问频繁，而对此地址之外的地址访问很少，这种现象称为程序局部性原理（包括时间局部性和空间局部性）。 依据此原理，可将程序要执行的部分装入内存，不执行的部分放在外存，需要执行时再调入主存，这样，就可以在较小的内存运行较大的用户程序。主函数主函数子函数1子函数2子函数n程序t虚拟存储器的定义：虚拟存储器的定义：1.主存辅存在OS 的管理下，能为用户提供一个比主存大的多的存储器，这个存储器称为虚拟存储器。2.能在较小的内存运行较大用户程序的存储系统。 当引入虚拟存储器后，用户只需在自己的虚存上编制程序，这

9、就给用户带来极大的方便，而虚实地址的映射由OS自动完成。 虚存技术分为：页式虚拟存储器、段式虚拟存储器、段页式虚拟存储器7.4页式存储管理页式存储管理 在页式存储管理中，主存被等分成一系列的块，程序的地址空间被分成一系列的页面，块和页面的大小相等，程序以块为单位装入内存，这样，就解决了分区存储管理中的碎片问题。例如： 内存256KB，2KB/块，内存可分为128块，某程序6.8KB，可以分为6.8KB/2KB=4页。：块号 内存01127页号 程序01230.8KB2KB内零头7.4页式存储管理页式存储管理 另外，在分区存储管理中，当作业的地址空间大于主存空间时，该作业无法运行。但页式存储管理

10、只需把当前将要执行的一部分页面装入主存即可，“扩大”了主存容量，实现了虚拟存储管理。7.4.1页式存储管理应解决的问题1. 页式系统的地址映射2. 请调策略：当所访问的页面不在主存时，系统必须从辅存调入请求的页面。3. 放置策略：确定程序的各个页面分配到主存的哪些块中，以及用什么原则挑选主存块，即空闲块如何组织？4. 淘汰策略：当需要调入一页，而主存块已全部用完时，需要确定哪个页面应从主存中淘汰。7.4.2页式地址变换1.页表 在页式系统中，实现地址变换的机构称为页面映像表，简称页表。页号页号块号块号页表7.4.2页式地址变换2.虚地址结构 例如：当CPU给出虚地址32位，4KB/页时，虚地址

11、的结构如下：页号页号P页内偏移量页内偏移量w20位24K=12位32位7.4.2页式地址变换页式地址变换3.页式地址变换设逻辑地址为A，页面大小为L，则逻辑页号P=int(A/L)， 页内偏移量w=A mod L。例如：操作数地址2500B，页面大小为1KB，P=int(2500/1024)=2 w=2500 mod 1024=4522452虚地址页号页号块号块号041227页表a页表基址寄存器 a a+1 a+2+7452物理地址虚拟存储器的大小受以下因素限制：1. 一定容量的主存；2. 大容量的辅存，存放多道程序；3. 地址变换机构，如虚地址要放入地址寄存器，如果地址寄存器为32位，则虚存

12、最大为232=4G。11.已知一个进程有三页，页号为0,1,2，分别对应内存块号为2,3,6，页面的大小为1KB，其中某一指令的虚地址为1000，则对应的物理地址为多少？要求画出地址变换过程。解：P=int(1000/1024)=0 W=1000 mod 1024=1000物理地址为： 块号块内偏移量21000 或为：21024+1000=30487.4.2页式地址变换页式地址变换4.联想存储器（相联存储器） 当页表的全部放入主存时，要取一个数据或指令至少要访问2次主存，一次访问页表，一次访问主存，这样，会使指令的执行速度下降。 为了提高查表速度，可以将页表放入Cache，或部分放入cache

13、。 放入页表部分内容的cache称为联想存储器或相联存储器。 联想存储器中的部分页表称为快表。 联想存储器时按内容查找的存储器，用来存放正在运行的进程的当前最常用的页号和相应的块号。例：采用快表和页表相结合的页式地址变换1. 当快表中查到，停止查页表2. 当快表中没有查到，则根据页表查找，同时，将该页表项装入快表3. 如快表已满，则淘汰最先装入的页面2452页号页号块号块号041227页号页号块号块号:27虚地址页表（内存）快表（Cache）例：有一页式系统，其页表存放在主存 如果对主存的一次存取需要1.5S ，试问一次页面访问的存取时间是多少？ 如果系统加有快表，平均命中率h为85%，当页表

14、项在快表中时，其查找时间忽略为0，试问此时的一次页面访问的存取时间是多少？解：第一次访内由逻辑地址转化为相应的物理地址；第二次访内由物理地址在内存中存取数据或指令t=1.5S2=3S平均访问时间t=（tm+tm）（1-h）+（tc+ tm）h =1.725S7.4.3请调策略 进程在运行过程中可能遇到所需代码或数据不在内存的情况，这样系统必须解决以下两个问题：一怎样发现所访问页面不在内存？二所访问页面不在主存时如何处理？一一怎样发现所访问页面不在内存？怎样发现所访问页面不在内存？解决方法：扩充页表功能页号页号块号块号中断位中断位i辅存地址辅存地址 中断位：用来标示该页是否在内存 i=0,此页在

15、主存; i=1,此页不在主存，请求调入； 辅存地址：表示该页在辅存的位置页表二二.所访问页面不在主存时如何处理？所访问页面不在主存时如何处理？解决方法：该进程产生缺页中断，请求调入此页缺页中断与一般中断的区别：1. 缺页中断发生在指令的执行过程中，一般中断发生在指令周期之后。2. 一条指令的执行可能有多次缺页中断。执行等待就绪OS调度缺页中断页面传送完成被唤醒例：某计算机系统一条指令执行需10ns，一次缺页需要额外的20ms，如果每106条指令发生一次缺页，则指令的平均执行时间是多少？解：（10ns106+20ms）/106=30ns可见，缺页后从辅存请调会影响指令的执行速度。缺页中断算法：缺

16、页中断算法：缺页中断有空闲块？从辅存读入所需页面Y调整页表和存储分配表唤醒等待页面的阻塞进程，转OS进程调度程序选择一页淘汰调整页表和存储分配表要重写入？该页写入外存NYN如中断位=0如中断位=1，主存块号取消 为了给页面置换提供依据，页表的功能还需扩充，增加“引用位”、“改变位”。页号页号块号块号中断位中断位i辅存地址辅存地址改变位改变位引用位引用位扩充后的页表“引用位”=0，表示该页最近没有被访问过“引用位”=1，表示该页最近已被访问过在“clock算法”中要使用“改变位”=0，表示该页最近未被修改过；淘汰时，该页不写回辅存。“改变位”=1，表示该页最近被修改过；淘汰该页时，该页需要写回辅

17、存。 在“写回策略”中使用：1. 全写法2. 写回法3. 写一次法CPU主存辅存辅存页面i辅存页面i 为保证主存的页面与辅存页面数据的一致，减少CPU对辅存的访问，只在主存中的页面被淘汰时，才写回辅存。8.某进程的页表部分如下：页号中断位引用位修改位物理块号0010410117210030002410050010下列虚地址对应的物理地址是多少？（虚地址为十进制，页面大小为1KB）5499 2221解：p=int(5499/1024)=5 , w=5499 mod 1024=379,中断位为0，物理地址=01024379=379；p=int(2221/1024)=2 , w=2221 mod 1

18、024=173, 中断位为1，该页没有装入内存，会产生缺页中断。缺页中断处理程序将当前进程阻塞，并将该页从辅存读入内存后，唤醒因缺页阻塞的进程就绪。存储分配表 存储分配表表示内存中的各主存块是否分配出去。1. 用位示图表示2. 用空闲块链表表示1、用位示图表示用位示图表示 每1个bit表示一个主存块，“1”表示已分配，“0”表示未分配 。如图：例如：内存为8MB，1KB/块，求存储分配表的大小？解：内存块数=8MB/1KB=8K， 存储分配表大小=8K1bit=1KB空闲块空闲块空闲块空闲块10101100位示图2、用空闲块链表表示用空闲块链表表示空闲块 3空闲块 6空闲块 7空闲块 块号01

19、2345671headhead 1 3 67 方法二：方法一：空闲块的最后一个字做为指针，指向下一个空闲块号。7.4.5几种置换算法1. 最佳算法（optimal算法）2.先进先出算法（FIFO算法）3.LRU算法（Least Recently Used4.LRU近似算法（clock算法）1.最佳算法（最佳算法（optimal算法）算法）思想：所选择被淘汰的页面将是永不使用，或者是在最长时间内不再被访问的页面。例：假定系统为某进程分配了3个物理块，进程将引用以下页面：7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0， 1，7， 0， 1 主存7707

20、01201 203 243 203 201 701 缺页中断率f=f/a，f为缺页次数，a为总的访问次数， f=9/20。 OPT算法是无法实现的，因为在程序以下的过程中无法对后面要使用的页面作出精确的断言，但是可以用来作为衡量各种具体算法优劣的标准。2.先进先出算法（FIFO算法） 思想：总是选择在主存中居留时间最长的一页淘汰。 方法一：方法一： 当为进程分配m个主存块时，每当调入新页时（缺页并且 主存块分配完时），执行以下语句：Pk=新的页号；K=(k+1) mod m ；k为替换指针，k的初值为07， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0

21、， 1，7， 0， 1 主存770701201 231 2 3 043042 0423023 013012 712702701缺页中断率f=f/a，f为缺页次数，a为总的访问次数， f=15/20。 方法二：方法二： 当计算缺页率时可以用寄存器压栈的方法做。注意：替换出栈的页号的主存块。 主存块中的数据是不移动的。7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0， 1，7， 0， 1 寄存器栈707107210 321 0 3 240324 0324032 103210 721072107缺页中断率f=f/a，f为缺页次数，a为总的访问次数， f=1

22、5/20。3. LRU算法（Least Recently Used） 思想：当需要淘汰一页时，选择最长时间未被使用的那一页淘汰掉。1.计数器法：计数器法： 每块需要设置一个计数器count，每访问一页时，该块的count值置“0”，其它块的count+1，当淘汰一页时，选择count值最大的页淘汰。例：假定系统为某进程分配了3个物理块，进程将引用以下页面：7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0， 1，7， 0， 1 主存707100720110200211 21 00 1222013023 003140013241 0220 42 30 2

23、1003122 103221 12 0021 110270 缺页中断率f=f/a，f为缺页次数，a为总的访问次数， f=12/20。2.堆栈法：堆栈法： 每当进程访问页面时，便将该页面的页号从栈中移出，将它压入栈顶，因此，栈顶始终是最新被访问页面的编号，而栈底则是最近未使用页面的页面号。例：假定系统为某进程分配了3个物理块，进程将引用以下页面：7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0， 1，7， 0， 1 堆栈707107210 0 2 13020324032403240323 02 2 3 0 1232 130211 0 2 710 缺页中

24、断率f=f/a，f为缺页次数，a为总的访问次数， f=12/20。这种方法计算缺页率比较方便。4、LRU近似算法（近似算法（clock算法）算法） 页表中每个主存块号有一个“引用位”。当某块中的页面被访问时，“引用位”置“1”，而页面管理程序周期性（设周期为T）地将所有“引用位”重新置“0”。页号页号块号块号中断位中断位i辅存地址辅存地址改变位改变位引用位引用位1001 这样，在T时间内，被访问页面的“引用位”为“1”，未被访问页面的“引用位”为“0”，当需要置换一页时，选择“引用位”为“0”的页淘汰掉。缺点：1. T太大，可能所有块的为“1”；2. T太小，可能“引用位”为“0”的块相当多；

25、3. 若缺页中断发生在页面管理程序将所有“引用位”清零时，有可能将常用的页面淘汰掉。页式系统面临的问题及解决的方法：7.4.4淘汰策略（2）颠簸（thrashion）或抖动 如果选择的置换算法不好，可能会出现这样的现象：刚被淘汰的页，过后不久又要访问它，因而又要把它调入，而调入不久又再次淘汰，再访问再调入，如此反复，使得整个系统的页面置换非常频繁，以致大部分的CPU时间花费在来回进行页面调度上，只有一小部分时间用于程序的实际运行，从而直接影响系统的效率。 简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现象称为抖动。另外，抖动与多道程序度（内存中的作业数）有关。 当缺页时，进程阻塞

26、，OS为了提高CPU的利用率，又引入新的进程，这样，内存中的空闲块变少，缺页的可能性加大，如果新进程再缺页，再阻塞，如此产生恶性循环，使缺页率急剧上升，CPU利用率下降。CPU利用率多道程序度峰值抖动的预防抖动的预防1、采用局部置换策略 当进程发生缺页后，仅在自己的内存空间范围内置换页面，不允许从其它进程获得新的物理块。缺点：不能从根本上防止抖动的发生；该进程发生抖动后，会长期处于磁盘I/O的等待队列，从而影响了其它进程的缺页中断的处理时间。抖动的预防抖动的预防2、当多道程序度偏高时，挂起一些进程如：优先级低的缺页进程；剩余执行时间较大的进程等抖动的预防抖动的预防3、在调度程序中引入工作集算法

27、工作集又称驻留集：在某段时间间隔内，进程要访问的页面的集合。仅在每个进程在内存中都有足够大的驻留集时，才能从外存调入新的作业，这样，才不致因新作业的调入而导致缺页率的增加。例如：某进程的页面走向为：2,5,1,6,3,3,7,8,9,1,6,2, 3,4,3,4,3,4,3,4,3,4,3窗口尺寸=10 t1时刻的工作集为1,2,3,6,7,8,9 t2时刻的工作集为3,4ttt1t2抖动的预防抖动的预防4、L=S准则 它用于调整多道程序的道数。 使产生缺页的平均时间L 等于处理缺页的平均时间S，此时，CPU的利用率最大。多级页表机制 假设逻辑地址32位，4KB/页，则每个进程的页表项最多可达

28、232/4KB=220=1M，若每个页表项为8B，则一级页表的大小为8MB且要求连续，这样显然是不现实的。解决方法：1. 只将页表的一部分页表项调入内存，其余驻留在磁盘上，需要时调入内存。这样不要求页表在内存连续存放，但会影响指令的执行速度。2. 采用多级页表机制。可以采用离散的方式将页表放在多个不连续的内存空间。例如：二级页表机制页表目录号页表目录号p1页号页号p2页内偏移量页内偏移量w逻辑地址页表目录号页表目录号页表在内存块号页表在内存块号:p1:页号页号块号块号P2bbw页表目录（内存）页表（内存）+物理地址 在页式系统中，若采用FIFO页面淘汰算法，会产生一种奇怪的现象，分配给作业的内

29、存块越多，进程执行时的缺页率反而越高。例如：某进程的页面走向为：432143543215堆栈M=3432143521432143524321435缺页率 f=9/12 在页式系统中，若采用FIFO页面淘汰算法，会产生一种奇怪的现象，分配给作业的内存块越多，进程执行时的缺页率反而越高。例如：某进程的页面走向为：432143543215堆栈M=34321 543215432 15432143 2154324321543缺页率 f=10/12由Belady提出，也称为“Belady现象”。假定在页式系统中，主存容量为4M，被分成1024块，块号为0,1，1023。某作业的地址空间占8页，其页号为0,

30、1,2,3被分配到主存的第28,46,12,57块中（OS为该作业分配4个物理块）。（1）主存地址应该用多少位来表示？（2）作业每页长度为多少？该作业的逻辑地址中的页内地址应用多少位表示？（3）完成以下页表：页号块号起始地址028284096=114688146464096=188416212124096=49152357574096=233472（4）以后当进程访问的页面走向为3,0,1,2,3,0,5,6时，采用LRU算法，计算缺页次数，写出计算过程。解：（1）物理地址共24M=22位，块号=21024=10位块号（10位）块内偏移量（12位）（2）页的大小块的大小，页内地址应用12位表示

31、，每页的长度为212=4K。页面号栈 30123056301230562301230512301230012301233210（4）缺页次数为2次。7.5段式系统 页式系统存在抖动，页表项可能较大等问题，而且不同进程之间共享公用子程序或数据变得非常困难，为此，提出段式存储管理技术。7.5.1段式系统的特点段式系统的特点基本思想：把作业按逻辑分段，如图所示（8088汇编）：代码段代码段数据段堆栈段段名 段内偏移量 0 0 l1-1 1 0 l2-1 2 0 l3-1 段长L1L2L3 每个段有自己的名字，每个段从逻辑地址0处开始编址，分段是一组逻辑意义完整的信息集合。7.5.1段式系统的特点段式

32、系统的特点主函数（段主函数（段0）子函数1（段1）子函数2（段2）：子函数n（段n）子函数子函数2（段（段2）主函数（段0）内存程序 段式系统以段（大小不固定）为单位分配内存，然后通过地址映射结构把段式虚地址转换为物理地址。 段式系统可以将经常访问的段驻留内存，而把暂时不访问的段放入外存，待需要时调入内存的办法实现虚拟存储的思想。7.5.2段式地址变换段式地址变换 地址变换由段表实现。段表至少应包括：段号、段长、段首址（该段在内存的起始地址）。段式虚地址变换结构（基本变换过程）：段号段号s段内位移量段内位移量w段式虚地址段表基址寄存器段号段号段长段长段首址段首址:sLb:+ b+w为物理地址段

33、式系统地址变换完整过程：段式系统地址变换完整过程： 开始访问虚地址: sw段s在内存？0 w L ?符合存取方式保护？修改段表字段，如引用位=1物理地址=b+w缺段中断处理段越界分段保护中断处理YYYNNN返回例：在一个段式系统中，其段表为：试求下列逻辑地址对应的物理地址是什么？段号段号段在内存起始地址段在内存起始地址段长段长02105012350202100903135059041938950420110250034004112532 430 500 物理地址=210+420=64010 20 物理地址=2350+10=2360500 90 段越界400 590 物理地址=1350+400=

34、1750112 90 段越界不存在第5段逻辑地址非法缺段中断算法：缺段中断算法：段s不在内存(i=1)阻塞当前进程从外存读入段S内存有合适空闲区？修改段表和内存空闲链表唤醒阻塞进程返回空闲区容量之和能否满足？拼接淘汰若干实段以形成一个合适的空闲区NYYN7.5.3扩充段表功能扩充段表功能段号段号段长段长段首址段首址中断位中断位引用位引用位改变位改变位RWEA其它其它存取方式保护中断位i=1，段在外存；i=0，段在内存；引用位、修改位的作用同页式管理R表示读权 W表示写权 E（execute）执行权 A（append）表示可添加7.5.3扩充段表功能扩充段表功能1.段的共享 如果每个用户进程都在内存保留它们共享程序和数据的副本，会极大地浪费内存空间。 在内存中只保留一个程序和数据的副本，供多个用户使用，称为共享共享。例如：若两个作业共享一个程序分段，则只要在作业段表的相应表目的段首址一项填入相同的主存地址即可。段号段号段起址段起址：ia：段号段号段起址段起址：ja：进程1的段表进程2的段表：共享段：