操作系统存储器管理

1、寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存库目标程序块1目标程序块2第一步链接程序装入模块第二步装入程序第三步用户源程序编译程序作业地址空间内存地址空间模块ACALL B;RETURN;模块BCALL C;RETURN;模块CRETURN;0L-10M-10N-10L-1LL+M-1L+ML+M+N-1目标模块装入模块0KB32KB96KB256KB-1分配给用户的空间空闲分区表空闲分区表(2)该算法分配后的空闲分区表该算法分配后的空闲分区表0k20k52k60k180k511k(1)内存分配图内存分配图50K59K160K380K空闲分区表空闲分区表(2)该算法分配后的

2、空闲分区表该算法分配后的空闲分区表 0k 20k 52k 60k180k511k(1)内存分配图内存分配图27K52K160K210K 0k 20k 52k 60k180k511k2134分配前的空闲分区表分配前的空闲分区表内存分区内存分区作业作业100K分配后的空闲分区表分配后的空闲分区表 作业作业30K分配后的空闲分区表分配后的空闲分区表作业作业7K分配后的空闲分区表分配后的空闲分区表(2)该算法分配后的空闲分区表该算法分配后的空闲分区表 0k 20k 52k 60k180k511k(1)内存分配图内存分配图50K59K160K180K空闲分区表空闲分区表作业作业100K分配后的空闲分区表

3、分配后的空闲分区表 作业作业30K分配后的空闲分区表分配后的空闲分区表作业作业7K分配后的空闲分区表分配后的空闲分区表E A释放初始状态A申请200B申请120C申请240D申请100 B释放 E申请60 C释放 D释放 E释放512K256KAA512K128KBAB256KCAB256KCDA256KCD128KA256KCD64E256KCD64E256KD64256K512KE64256K512K128K128K动态重定位分区分配算法流程图动态重定位分区分配算法流程图有大于x的空闲分区吗？返回分区号空闲分区总和大于x吗？拼接并修改相应数据结构返回修改有关数据结构按动态分区分配方式进行分

4、配YYNN无法分配，返回请求分配一个大小为x的分区2. 动态重定位的实现动态重定位的实现 地址变换过程是在程序执行过程期间，随着对地址变换过程是在程序执行过程期间，随着对每条指令的访问自动进行的，称为每条指令的访问自动进行的，称为动态重定位动态重定位。mov r1,500 123 mov r1 , 500 123010050059901000256k-1作业地址空间作业地址空间存储空间存储空间重定位寄存器重定位寄存器110015001600500 1000相对地址相对地址+对换的引入对换的引入多道程序环境下存在的问题：多道程序环境下存在的问题： 阻塞进程占据大量内存空间阻塞进程占据大量内存空间

5、 许多作业在外存而不能进入内存运行许多作业在外存而不能进入内存运行对换是提高内存利用率的有效措施对换是提高内存利用率的有效措施 在系统中设置相应的数据结构以记录外存的使在系统中设置相应的数据结构以记录外存的使用情况；对换空间的分配与回收，与动态分区方式用情况；对换空间的分配与回收，与动态分区方式时的内存分配与回收雷同。时的内存分配与回收雷同。Logical memoryphysical memoryFramenumber01234567Page table页内碎片页内碎片注：需要CPU的硬件支持（地址变换机构）。Page table页号 块号 作业的地址空间01234567内存空间页表31 1

6、2 11 021 12 11 0AMODLdLAINTP页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址3图4-14具有快表的地址变换机构 页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址有效访问内存的时间有效访问内存的时间 T=PTLB*（TTLB+TM）+ （1-PTLB ）*（ TTLB + 2TM ） 其中,PTLB为快表的命中率,TTLB为快表的访问时间, TM为内存的访问时间具有快表的地址变换机构具有快表的地址变换机构+ 指示该页是指示该页是否在内存否在内存记录本页被访问记录本页被

7、访问的情况（如访问的情况（如访问次数、未被访问次数、未被访问的时间等）的时间等）指示该页在内存时指示该页在内存时是否被修改过。是否被修改过。0未未改（换出时不需回改（换出时不需回写到外存），写到外存），1已改已改指示该页在指示该页在外存中的地外存中的地址，常为盘址，常为盘块号块号 v 保护现场保护现场 中断处理中断处理 恢复现场恢复现场v 1 1）一般中断是指令完成后中断，缺）一般中断是指令完成后中断，缺页中断在指令执行时中断。页中断在指令执行时中断。v 2）一条指令执行期间可能会有多次）一条指令执行期间可能会有多次缺页中断。缺页中断。 B:A:Copy ATo B指令 涉及涉及6次缺页中断的

8、指令次缺页中断的指令 当要访问的页不在内存时，产生一缺页中断。当要访问的页不在内存时，产生一缺页中断。OS接到此中断信号后，调用缺页中断处理程序，将该页调入接到此中断信号后，调用缺页中断处理程序，将该页调入内存，更新页表，完成重定位。期间可能调用置换程序。内存，更新页表，完成重定位。期间可能调用置换程序。OS命令命令CPU从外存读缺页从外存读缺页修改页表修改页表将一页从外存读到内存将一页从外存读到内存将该页写回外存将该页写回外存启动启动I/O硬件硬件选择一页换出选择一页换出从外存中找到缺页从外存中找到缺页保留保留CPU现场现场该页被修改否？该页被修改否？内存满否？内存满否？是是否否是是否否修改

9、访问位和修改位修改访问位和修改位访问页表访问页表修改快表修改快表形成物理地址形成物理地址CPU检索快表检索快表开始开始地址变换结束地址变换结束页表项在快表中吗？页表项在快表中吗？页号页号页表长度页表长度越界中断越界中断页在内存？页在内存？程序请求访问一页程序请求访问一页是是否否是是是是否否 n 固定分配：固定分配：指为每个进程分配固定物理块数，进程指为每个进程分配固定物理块数，进程在整个运行期间不变。在整个运行期间不变。n 局部置换：局部置换：指进程运行过程中若发生缺页，只能从指进程运行过程中若发生缺页，只能从进程本身所拥有的物理块中选择一页换出，再调入所需进程本身所拥有的物理块中选择一页换出

10、，再调入所需页。页。n 缺点：缺点：进程所需的内存大小难确定；太少，频繁缺进程所需的内存大小难确定；太少，频繁缺页中断；太多，内存中进程数目减少。页中断；太多，内存中进程数目减少。系统中所有可供分配的物理块，平均分配给各进程。系统中所有可供分配的物理块，平均分配给各进程。根据进程大小按比例分配物理块。根据进程大小按比例分配物理块。niSi1若各进程页面总数为：若各进程页面总数为：S=物理块总数为：物理块总数为：m则每进程所得物理块数为：则每进程所得物理块数为：Bi= mSSi把把，v 一部分用于一部分用于；v 另一部分另一部分，适当增加相应份额后再分配给各进程。，适当增加相应份额后再分配给各进

11、程。 或完或完全按优先权分配物理块。全按优先权分配物理块。注：注：Si为每个进程页面数。为每个进程页面数。Bi应大于最小物理块数。应大于最小物理块数。 外存要分为外存要分为和和。对换区为取得较快的速度，。对换区为取得较快的速度，采用连续分配方式，且对换区所规定盘块较大。采用连续分配方式，且对换区所规定盘块较大。则可全部从则可全部从对换区调入所需页面。要求运行前，将其所有页面复制到对换区。对换区调入所需页面。要求运行前，将其所有页面复制到对换区。开始都从开始都从文件区调入。对未被修改的页面，每次都从文件区调入（换出时不文件区调入。对未被修改的页面，每次都从文件区调入（换出时不需回写）；被修改的页

12、面换出到对换区，以后从对换区调入。需回写）；被修改的页面换出到对换区，以后从对换区调入。n 未运行过的，从文件区调入；运行后换出时，放到对未运行过的，从文件区调入；运行后换出时，放到对换区。因此对于曾运行过而又被换出的页面，从对换区调入。换区。因此对于曾运行过而又被换出的页面，从对换区调入。保留CPU现场内存满吗？将一页从外存换入内存OS命令CPU从外存读缺页启动I/O硬件Y从外存中找到缺页选择一页换出该页被修改否？将该页写回外存修改页表NYN整个页面的调入过整个页面的调入过程对用户是透明的。程对用户是透明的。140例：例：设页面请求次序设页面请求次序 7,0,1,2,0,3,0,4,2,3,

13、0,3,2,1,2,0,1,7,0,1存储块为存储块为3(驻留集为驻留集为3)，假定最初存储块为空，采，假定最初存储块为空，采用用OPT。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1从上面的演示知，利用从上面的演示知，利用OPT，发生了，发生了6次页面置换。次页面置换。问：发生了几次缺页中断？缺页率多少？问：发生了几次缺页中断？缺页率多少？710432发生了发生了9次缺页中断，次缺页中断，缺页率缺页率=缺页次数缺页次数/访问次数访问次数=9/20=0.45142例：例：设页面请求次序设页面请求次序 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,

14、0,1,7,0,1存储块为存储块为3(驻留集为驻留集为3)，假定最初存储块为空，采，假定最初存储块为空，采用用FIFO。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1从上面的演示知，利用从上面的演示知，利用FIFO，发生了，发生了12次页面置换。问：次页面置换。问：发生了几次缺页中断？缺页率多少？发生了几次缺页中断？缺页率多少？701 2 3 0发生了发生了15次缺页中断，次缺页中断，缺页率缺页率=缺页次数缺页次数/访问次数访问次数=15/20=0.7542 30 12BeladyBelady现象：现象：当一个进程需要的页面不能全部分配时，尽管可能差一页，将当

15、一个进程需要的页面不能全部分配时，尽管可能差一页，将有可能导致进程执行过程中调入和调出频繁发生，影响系统效率。有可能导致进程执行过程中调入和调出频繁发生，影响系统效率。举例：举例：假设某进程假设某进程P P有有5 5页，且访问页的顺序为：页，且访问页的顺序为： 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 51, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5；如果该进程固定分配如果该进程固定分配3 3个物理块，则缺页情个物理块，则缺页情况如下：况如下：1212次访问中有缺页次访问中有缺页9 9次；次；如果在内存中分配如果在内存中分配4 4个页面，则缺页情况

16、如下：个页面，则缺页情况如下：1212次访问中有缺页次访问中有缺页1010次；次；思考思考：为什么为什么FIFOFIFO算法会出现算法会出现BeladyBelady现象？现象？FIFO算法的置换特征与进程访算法的置换特征与进程访问内存的动态特征是矛盾的问内存的动态特征是矛盾的,即即被置换的页面并不是进程不会被置换的页面并不是进程不会访问的访问的 146例：例：设页面请求次序设页面请求次序 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1存储块为存储块为3(驻留集为驻留集为3)，假定最初存储块为空，采，假定最初存储块为空，采用用LRU。 7 0 1 2 0 3 0

17、4 2 3 0 3 2 1 2 0 1 7 0 1从上面的演示知，利用从上面的演示知，利用LRU，发生了，发生了9次页面置换。次页面置换。问：发生了几次缺页中断？缺页率多少？问：发生了几次缺页中断？缺页率多少？712 3 0 4发生了发生了12次缺页中断，次缺页中断，缺页率缺页率=缺页次数缺页次数/访问次数访问次数=12/20=0.60032图4-29某进程具有8个页面时的LRU访问情况 R 实 页 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5

18、1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 150图图 4-30 用栈保存当前使用页面时栈的变化情况用栈保存当前使用页面时栈的变化情况 假定现有一进程所访问的页面的页面号序列为：假定现有一进程所访问的页面的页面号序列为：4 4，7 7，0 0，7 7，1 1，0 0，1 1，2 2，1 1，2 2，6 6随着进程的访问，栈中页面号的变化情况如图随着进程的访问，栈中页面号的变化情况如图4-30所示。所示。 4 7 0 7 1 0 1 2 1 2 6 4在访问页面在访问页面6时发生了缺页，此时页面时发生了缺页，此时页面4是最近最是最近最久未被访问的页，应将它置换出去。久未被访问的页，应将它置换出去。图4-31简单Clock置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访