第六章 存储管理精选文档.ppt

第六章 存储管理本讲稿第一页，共六十七页进程与外存对应关系进程与外存对应关系n界地址界地址n每进程占一组外存连续块；每进程占一组外存连续块；n每进程占二组外存连续块（双对界）。每进程占二组外存连续块（双对界）。n页式页式n内存一页，外存一块。内存一页，外存一块。n段式段式n每段占外存若干连续块。每段占外存若干连续块。n段页式段页式n内存一页，外存一块。内存一页，外存一块。本讲稿第二页，共六十七页6.5 虚拟存储系统虚拟存储系统n无虚拟问题无虚拟问题n不能运行比内存大的程序；不能运行比内存大的程序；n进程全部装入内存，浪费空间（进程活动具有局部性进程全部装入内存，浪费空间（进程活动具有局部性)。n单控制流的进程需要较少部分在内存；单控制流的进程需要较少部分在内存；n多控制流的进程需要较多部分在内存。多控制流的进程需要较多部分在内存。n虚拟存储虚拟存储n进程部分装入内存，部分（或全部）装入外存，运行时访问进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。在外存部分动态调入，内存不够淘汰。本讲稿第三页，共六十七页6.5.1 虚拟页式存储系统虚拟页式存储系统n基本原理基本原理n进程运行前：进程运行前：n全部装入外存，部分装入内存。全部装入外存，部分装入内存。n进程运行时：进程运行时：n访问页不在内存，发生缺页中断，中断处理程序：访问页不在内存，发生缺页中断，中断处理程序：n找到访问页在外存的地址；找到访问页在外存的地址；n在内存找一空闲页面；在内存找一空闲页面；n如没有，按淘汰算法淘汰一个；如没有，按淘汰算法淘汰一个；n如需要，将淘汰页面写回外存，修改页表和总页表；如需要，将淘汰页面写回外存，修改页表和总页表；n读入所需页面（切换进程）；读入所需页面（切换进程）；n重新启动中断指令。重新启动中断指令。本讲稿第四页，共六十七页对页表的改进：对页表的改进：对快表的改进：对快表的改进：逻辑页号逻辑页号 p .页框号页框号 外存块号外存块号 内外标识内外标识 访问权限访问权限 修改标志修改标志 f b (0,1)r,w,e (0,1).逻辑页号逻辑页号 页框号页框号 访问权限访问权限 修改标志修改标志 p f r,w,e (0,1).本讲稿第五页，共六十七页6.5.1.2 内存页框分配策略（静态策略）内存页框分配策略（静态策略）1.平均分配平均分配 如内存如内存128页，进程页，进程25个，每个进程个，每个进程5个页架个页架 2.按进程按进程长度长度比例分配比例分配 pi共共si个页面；个页面；S=si；内存共；内存共m个页架个页架 ai=(si/S)m 3.按进程按进程优先级优先级比例分配比例分配 4.按进程按进程长度和优先级别长度和优先级别比例分配比例分配 静态策略没有反映：静态策略没有反映：(1)程序结构；程序结构；(2)程序在不同时刻的行为特性。程序在不同时刻的行为特性。本讲稿第六页，共六十七页6.5.1.3 外存块的分配策略外存块的分配策略 1.静态分配静态分配 外存保持进程的全部页面：外存保持进程的全部页面：优点：速度快优点：速度快-淘汰时不必写回淘汰时不必写回(未修改情况未修改情况)缺点：外存浪费缺点：外存浪费 2.动态分配动态分配 外存仅保持进程不在内存的页面：外存仅保持进程不在内存的页面：优点：节省外存优点：节省外存 缺点：速度慢缺点：速度慢-淘汰时必须写回淘汰时必须写回本讲稿第七页，共六十七页6.5.1.4 页面调入时机页面调入时机 1.请调请调(demand paging)upon page fault,发生缺页中断时调入。发生缺页中断时调入。2.预调预调(prepaging)before page fault,将要访问时调入将要访问时调入(根据程序顺序行为，根据程序顺序行为，不一定准）不一定准）预调必须辅以请调。预调必须辅以请调。本讲稿第八页，共六十七页 用于：页淘汰、段淘汰、快表淘汰。用于：页淘汰、段淘汰、快表淘汰。Objective:lowest page-fault rate.1.最佳淘汰算法最佳淘汰算法(OPT-optimal)淘汰将来最长时间以后才用到的。淘汰将来最长时间以后才用到的。效率最高，效率最高，not feasible。6 6 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 6 6 0 0 1 16 6 6 6 6 6 2 22 22 22 22 26 60 0 0 0 0 00 04 40 00 00 01 1 1 13 33 33 31 11 1 6.5.1.5 淘汰算法淘汰算法(replacement algorithm)本讲稿第九页，共六十七页2.先进先出先进先出(FIFO)淘汰最先调入的。淘汰最先调入的。依据依据:先进入的可能已经使用完毕。先进入的可能已经使用完毕。实现：队列实现：队列 negative case:有些代码和数据可能整个程序运行中用到。有些代码和数据可能整个程序运行中用到。Belady异常异常:例子：例子：1，2，3，4，1，2，5，1，2，3，4，5 内存内存3个物理页面：页故障率个物理页面：页故障率=9/12 内存内存4个物理页面：页故障率个物理页面：页故障率=10/12 本讲稿第十页，共六十七页FIFO淘汰算法淘汰算法(belady异常异常)12 3 4 1 2 5 1 2 3 4511 1 4 4 4 55 52 2 2 1 1 13 33 3 3 2 22 41 2 3 4 1 2 5 1 2 3 4 51 1 1 15 5 5 5 4 42 2 22 1 1 1 1 53 33 3 2 2 2 244 4 4 3 3 3页故障率页故障率=10/12页故障率页故障率=9/12访问序列访问序列:访问序列访问序列:内存页面内存页面:内存页面内存页面:本讲稿第十一页，共六十七页3.使用过最久的先淘汰（使用过最久的先淘汰（LRU）淘汰最近一次访问距当前时间最长的。淘汰最近一次访问距当前时间最长的。Replace page that hasnt been used for the longest period of time.实现：实现：stack 当一页面被访问时当一页面被访问时,从栈中取出压到栈顶从栈中取出压到栈顶,栈底是栈底是:LRU page.例子：例子：reference string:4,7,0,7,1,0,1,2,1,2,7,1,2 2107472104Stack before aStack before b a b本讲稿第十二页，共六十七页nLRU算法6 6 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 6 6 0 0 1 16 6 6 6 6 6 2 22 24 4 4 4 4 4 0 01 11 11 10 0 0 0 0 00 00 0 0 0 3 3 3 33 30 00 01 1 1 13 33 3 2 2 2 2 2 22 22 26 6 本讲稿第十三页，共六十七页4.最近不用的先淘汰最近不用的先淘汰(not used recently)淘汰最近一段时间未用到的。淘汰最近一段时间未用到的。实现：每页增加一个访问标志，实现：每页增加一个访问标志，访问置访问置1，定时清，定时清0，淘汰时取标志为淘汰时取标志为0的。的。LRU算法的近似：算法的近似：Reference string:2,3,5,6,4,2,5,6,7,5,6,8,标志清标志清0选择淘汰选择淘汰LRU：3NUR：2，3，4任意任意本讲稿第十四页，共六十七页5.最不经常使用的先淘汰最不经常使用的先淘汰(LFU)淘汰使用次数最少的。淘汰使用次数最少的。依据依据:活跃访问页面应有较大的访问次数活跃访问页面应有较大的访问次数.Suffer:(1)前期使用多，但以后不用，难换出；前期使用多，但以后不用，难换出；(2)刚调入的页面，引用少，被换出可能大。刚调入的页面，引用少，被换出可能大。实现：记数器，调入清实现：记数器，调入清0，访问增，访问增1，淘汰选取最小者。，淘汰选取最小者。6.最经常使用的先淘汰最经常使用的先淘汰(MFU)淘汰使用次数最多的。淘汰使用次数最多的。依据依据:使用多的可能已经用完了。使用多的可能已经用完了。Suffer:程序有些成分是在整个程序运行中都使用的。程序有些成分是在整个程序运行中都使用的。本讲稿第十五页，共六十七页7.二次机会二次机会(second chance)n淘汰装入最久且最近未被访问的页面。淘汰装入最久且最近未被访问的页面。n实现时：采用拉链数据结构实现时：采用拉链数据结构。6/13/14/08/05/19/00/01/13/14/08/05/19/00/01/16/04/08/05/19/00/01/16/03/08/05/19/00/01/16/03/02/1本讲稿第十六页，共六十七页8.时钟算法时钟算法(clock algorithm)n将页面组织成环形，有一个指针指向当前位置。每次需要将页面组织成环形，有一个指针指向当前位置。每次需要淘汰页面时，从指针所指的页面开始检查。如果当前页面淘汰页面时，从指针所指的页面开始检查。如果当前页面的访问位为的访问位为0，即从上次检测到目前，该页没有访问过，则将该，即从上次检测到目前，该页没有访问过，则将该页替换。如果当前页面的访问位为页替换。如果当前页面的访问位为1，则将其清，则将其清0，并顺时针，并顺时针移动指针到下一个位置。重复上述步骤直至找到一个访问位移动指针到下一个位置。重复上述步骤直至找到一个访问位为为0的页面。的页面。n可以看出，时钟算法与二次机会算法的淘汰效果是基本相同的，可以看出，时钟算法与二次机会算法的淘汰效果是基本相同的，差别在于二者所采用的数据结构不同，二次机会使用的是链表，差别在于二者所采用的数据结构不同，二次机会使用的是链表，需要额外存储空间，且摘链入链速度很慢。而时钟算法可直接利需要额外存储空间，且摘链入链速度很慢。而时钟算法可直接利用页表中的引用位，外加一个指针，速度快且节省空间。用页表中的引用位，外加一个指针，速度快且节省空间。本讲稿第十七页，共六十七页页页6/r=1页页3/r=1页页4/r=0页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第18页页时钟算法时钟算法本讲稿第十八页，共六十七页页页6/r=0页页3/r=1页页4/r=0页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第18页页时钟算法时钟算法本讲稿第十九页，共六十七页页页6/r=1页页3/r=0页页4/r=0页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第18页页时钟算法时钟算法本讲稿第二十页，共六十七页页页6/r=0页页3/r=0页页18/r=1页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5替换第替换第4页页时钟算法时钟算法本讲稿第二十一页，共六十七页改进的时钟算法改进的时钟算法n考虑修改标志考虑修改标志mnr=0,m=0：最佳淘汰页面：最佳淘汰页面nr=0,m=1：淘汰前回写：淘汰前回写nr=1,m=0：不淘汰：不淘汰nr=1,m=1：不淘汰：不淘汰本讲稿第二十二页，共六十七页改进的时钟算法改进的时钟算法n步骤步骤1：n由指针当前位置开始扫描，选择最佳淘汰页面，不改变由指针当前位置开始扫描，选择最佳淘汰页面，不改变引用位，将第一个遇到的引用位，将第一个遇到的r=0且且m=0的页面作为淘汰页的页面作为淘汰页面；面；n步骤步骤2：n如步骤如步骤1失败，再次从原位置开始，找失败，再次从原位置开始，找r=0且且m=1的页面，的页面，将第一个满足上述要求的页面作为淘汰页面，同时将扫描过将第一个满足上述要求的页面作为淘汰页面，同时将扫描过页面的页面的r位清位清0；n步骤步骤3：n若步骤若步骤2失败，指针再次回到原位置，重新执行步骤失败，指针再次回到原位置，重新执行步骤1。若还失败再次执行步骤若还失败再次执行步骤2，此时定能找到。，此时定能找到。本讲稿第二十三页，共六十七页页页6/r=1 m=1页页3/r=1 m=1页页18/r=1 m=0页页8/r=1 m=0页页10/r=1 m=0页页9/r=0 m=1页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第15页页改进的时钟算法改进的时钟算法本讲稿第二十四页，共六十七页页页6/r=1 m=1页页3/r=1 m=1页页18/r=1 m=0页页8/r=0 m=0页页10/r=1 m=0页页9/r=0 m=1页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第15页页改进的时钟算法改进的时钟算法本讲稿第二十五页，共六十七页页页6/r=1 m=1页页3/r=1 m=1页页18/r=1 m=0页页8/r=0 m=0页页10/r=0 m=0页页9/r=0 m=1页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第15页页时钟算法时钟算法本讲稿第二十六页，共六十七页页页6/r=1 m=1页页3/r=1 m=1页页18/r=1 m=0页页8/r=0 m=0页页10/r=0 m=0页页15/r=1 m=0页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5时钟算法时钟算法本讲稿第二十七页，共六十七页2010年考研试题n某虚拟页式系统，进程空间和内存空间都是64k，页长1K，某进程6个页，内存分配4个页框，采用局部置换，280时刻页表和Clock数据结构如下：逻辑页号 页框号 装入时间 访问标志 0 5 110 1 1 -2 12 160 1 3 8 230 1 4 -5 3 80 10页2页3页5页框5框12框8框3(顺时针)本讲稿第二十八页，共六十七页2010年考研试题n(1)280时刻访问13B7H，逻辑页号是多少？n(2)采用FIFO置换算法，物理页框号是多少？物理地址是多少？n(3)采用CLOCK置换算法，页框号是多少？物理地址是多少？本讲稿第二十九页，共六十七页2010年考研试题n（1）逻辑地址13B7H化为二进制数为0001001110110111，其中后10位为页内地址，前6位为逻辑页号，即逻辑页号为4。n（2）4号页不在内存，发生缺页中断，按FIFO置换算法，应置换第5页，所得页框号3，形成物理地址0000111110110111，划成16进制为0FB7H。n（3）采用CLOCK置换算法，淘汰第0页，得页框5，形成物理地址为0001011110110111，划成16进制为17B7H。本讲稿第三十页，共六十七页6.5.1.6 颠簸颠簸(thrashing)页面在内存与外存之间频繁换入换出。页面在内存与外存之间频繁换入换出。原因：原因：(1)分给进程物理页架过少；分给进程物理页架过少；(2)淘汰算法不合理。淘汰算法不合理。处理：处理：(1)增加分给进程物理页架数；增加分给进程物理页架数；(2)改进淘汰算法。改进淘汰算法。思考题：思考题：在某些虚拟页式存储管理系统中，内存中总保持一个空闲的在某些虚拟页式存储管理系统中，内存中总保持一个空闲的物理页架，这样做有什么好处？物理页架，这样做有什么好处？本讲稿第三十一页，共六十七页6.5.1.7 工作集模型工作集模型(working set model)工作集工作集(working set):进程在一段时间内所访问页面的集合。进程在一段时间内所访问页面的集合。WS(t,)=5,7,1,6,22 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 (page reference)t：称为窗口尺寸：称为窗口尺寸(window size)。Denning 认为：为使程序有效运行，工作集应能放入内存。认为：为使程序有效运行，工作集应能放入内存。T本讲稿第三十二页，共六十七页WS(t1,)=5,7,1,6,22 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 4 4 4 3 4 3 4 4 4 1 3 4.WS(t2,)=2,3,4 t1t2工作集与时间有关：工作集与时间有关：工作集与窗口尺寸有关：工作集与窗口尺寸有关：程序大小程序大小 WS本讲稿第三十三页，共六十七页窗口尺寸确定：窗口尺寸确定：过小：活动页面不能全部装入，页故障率高；过小：活动页面不能全部装入，页故障率高；过大：内存浪费。过大：内存浪费。Madnick,Donovan建议：建议：1万次访内。万次访内。实现：页表中增加访问位：实现：页表中增加访问位：访问位访问位页表：页表：开始时，全部开始时，全部清清0,访问：置访问：置1,结束时结束时(新新 开始时开始时)访问标志为访问标志为1的，为该的，为该 期间工作集，期间工作集，n+1=wn+(1-)n本讲稿第三十四页，共六十七页6.5.1.8 页故障率反馈模型页故障率反馈模型PFFB(Page Fault Feed Back)页故障率高页故障率高(达到某上界阈值达到某上界阈值)：内存页面少，增加。：内存页面少，增加。页故障率低页故障率低(达到某下界阈值达到某下界阈值)：内存页面多，减少。：内存页面多，减少。本讲稿第三十五页，共六十七页6.5.2 虚拟段式存储系统虚拟段式存储系统n进程运行前，全部装入外存，部分装入进程运行前，全部装入外存，部分装入内存，访问段不再内存时，发生缺段中内存，访问段不再内存时，发生缺段中断。断。本讲稿第三十六页，共六十七页6.5.2 虚拟段式存储系统虚拟段式存储系统基本原理：基本原理：修改过修改过TF缺段中断缺段中断在外存找到所缺段在外存找到所缺段内存够用内存够用选一段淘汰选一段淘汰写回外存写回外存修改段表修改段表F移入移入修改段表修改段表T本讲稿第三十七页，共六十七页.段号段号 s .段长段长 内存首址内存首址 外存首址外存首址 权限权限 内外标识内外标识 修改标志修改标志 l b b”rwe (0,1)(0,1).(1)段表的改进：段表的改进：()快表的改进：快表的改进：.段号段号 段长段长 内存首址内存首址 访问权限访问权限 修改标志修改标志 s l b rwe (0,1).本讲稿第三十八页，共六十七页6.5.2.2 段的动态连接段的动态连接(dynamic linking)n动态连接动态连接 vs.静态连接静态连接n静态连接：运行前连接，由静态连接：运行前连接，由link完成；完成；n动态连接：运行时连接，由动态连接：运行时连接，由OS完成完成.n静态连接的缺点静态连接的缺点n连接时间长；连接时间长；n目标代码长；目标代码长；n连接段可能并不执行连接段可能并不执行(未用到未用到)。本讲稿第三十九页，共六十七页动态连接的实现动态连接的实现(Multics为例为例)段名段名-段号对照表：每进程一个段号对照表：每进程一个段名段名 段号段号sname snum .符号名符号名 段内位移段内位移 func 150 .符号表：每段一个符号表：每段一个段形式：段形式：符号表符号表目标代码目标代码或者数据或者数据 静态连接由静态连接由link使用使用连接完不再需要连接完不再需要本讲稿第四十页，共六十七页(1)编译编译(汇编汇编)时：时：遇到访问外段指令，采用间接寻址，指向一个间接字：遇到访问外段指令，采用间接寻址，指向一个间接字：LD1:未连接未连接0:已连接已连接符号地址：符号地址：“X|”逻辑地址：逻辑地址：(段号段号,段内地址段内地址)(2)执行时：执行时：遇到间接指令，且遇到间接指令，且L=1,发生链接中断，处理程序：发生链接中断，处理程序：(a)由由D取出符号地址；取出符号地址；(b)由段名查段名由段名查段名-段号对照表，是否分配段号。段号对照表，是否分配段号。本讲稿第四十一页，共六十七页 已分配段号：取出该段号，查段表找到该段已分配段号：取出该段号，查段表找到该段(内存或内存或 外存外存)，由入口名查符号表得段内地址；，由入口名查符号表得段内地址；(段号，段内地址段号，段内地址)D,0 L 未分配段号：找到该段所在文件，读入内存，读入未分配段号：找到该段所在文件，读入内存，读入 外存，分配段号，填写段名外存，分配段号，填写段名-段号对照表，填写段段号对照表，填写段 表，转表，转(b)例子：汇编前：例子：汇编前：.Load 1,X|Load 2,X|.W段段X段段12345678.Y:Z:本讲稿第四十二页，共六十七页汇编后，连接前：汇编后，连接前：100:Load*1,2|100;Load*2,2|150;“7X|”.“7X|”1 2 2001 2 250150:200:250:W段（段号段（段号=2)X段段 300 40012345678300400段表段表 段首址段首址 .段号段号 0 1 2 3 .段名段名 段号段号Main 0A 1W 2段段名名-段段号号对对照照表表本讲稿第四十三页，共六十七页第一次连接后：第一次连接后：100:Load*1,2|100;Load*2,2|150;“7X|”.“7X|”1 2 2001 2 250150:200:250:W段（段号段（段号=2)X段段 300 40012345678300400段表段表 段首址段首址 .段号段号 0 1 2 3 .段名段名 段号段号Main 0A 1W 2段段名名-段段号号对对照照表表X 3本讲稿第四十四页，共六十七页第一次连接后：第一次连接后：100:Load*1,2|100;Load*2,2|150;“7X|”.“7X|”0 3 3001 2 250150:200:250:W段（段号段（段号=2)X段段 300 40012345678300400段表段表 段首址段首址 .段号段号 0 1 2 3 .段名段名 段号段号Main 0A 1W 2段段名名-段段号号对对照照表表X 3本讲稿第四十五页，共六十七页100:Load*1,2|100;Load*2,2|150;“7X|”.“7X|”0 3 3000 3 400150:200:250:W段（段号段（段号=2)X段段 300 40012345678300400段表段表 段首址段首址 .段号段号 0 1 2 3 .段名段名 段号段号Main 0A 1W 2段段名名-段段号号对对照照表表X 3第二次连接后：第二次连接后：本讲稿第四十六页，共六十七页动态连接问题动态连接问题n动态连接与共享的矛盾动态连接与共享的矛盾n动态连接：修改连接字（代码）动态连接：修改连接字（代码）n段的共享：要求纯代码（段的共享：要求纯代码（pure code)n解决方法解决方法n共享代码分为共享代码分为“纯段纯段”和和“杂段杂段”n纯段共享，纯段共享，n杂段私用。杂段私用。本讲稿第四十七页，共六十七页6.5.3 虚拟段页式存储系统虚拟段页式存储系统n考虑考虑n段的动态连接段的动态连接n段的共享段的共享n段长度的动态变化段长度的动态变化本讲稿第四十八页，共六十七页所需表目：所需表目：(1)段表：每进程一个段表：每进程一个页表长度页表长度 页表首址页表首址 访问权限访问权限 扩展标志扩展标志 共享段入口共享段入口 段号段号(2)页表：每段一个页表：每段一个内存页号内存页号 外存块号外存块号 内外标志内外标志 修改标志修改标志 .逻辑页号逻辑页号(3)共享段表：系统一个共享段表：系统一个段名段名 页表长度页表长度 页表首址页表首址 扩充标志扩充标志 共享计数共享计数 本讲稿第四十九页，共六十七页(4)段名段名-段号对照表：每进程一个段号对照表：每进程一个对应关系：对应关系：私用段私用段共享段共享段共享段表共享段表P1段表：段表：P2段表：段表：本讲稿第五十页，共六十七页共享段表共享段表P1段表：段表：P2段表：段表：15 16 17 18 19 20 21 22 23 24 25 .页表页表页表页表存储空间：存储空间：sisjsk本讲稿第五十一页，共六十七页所需寄存器：所需寄存器：(1)段表长度寄存器：保存正运行进程段表长度段表长度寄存器：保存正运行进程段表长度(2)段表首址寄存器：保存正运行进程段表首址段表首址寄存器：保存正运行进程段表首址(3)快表快表段号段号 逻辑页号逻辑页号 页架号页架号 访问权限访问权限 修改标志修改标志 地址映射：地址映射：:(s,p,d)(f,d)逻辑地址逻辑地址(s,p,d)物理地址物理地址(f,d)本讲稿第五十二页，共六十七页由由(s,p)查快表得查快表得f查到查到访问合法访问合法形成物理地址形成物理地址(f,d)是间址是间址有障碍位有障碍位继续继续0 s l-10 p l-1由由(s,b)查段表得查段表得b,l越界中断越界中断越界中断越界中断由由b和和p查页表得查页表得f该页在内存该页在内存缺页中断缺页中断(s,p,f)快表快表越权中断越权中断TFTF连接中断连接中断TFTFTFTFTl:段表长度段表长度b:段表首地址段表首地址l:页表长度页表长度b:页表首地址页表首地址形成物理地址形成物理地址(f,d)本讲稿第五十三页，共六十七页中断处理：中断处理：1.连接中断连接中断(1)所有进程均未连接所有进程均未连接(共享段表、段名共享段表、段名-段号对照表均无段号对照表均无)建立页表，由文件读入外存建立页表，由文件读入外存swap，部分页读入内存，分配，部分页读入内存，分配 段号，填段名段号，填段名-段号对照表，如是共享段填共享段表，填段号对照表，如是共享段填共享段表，填 段表段表，形成逻辑地址。，形成逻辑地址。(2)其它进程连接过，本进程未连接过其它进程连接过，本进程未连接过(共享段表有，段名共享段表有，段名-段段 号对照表无号对照表无)分配段号，填段名分配段号，填段名-段号对照表，填段表段号对照表，填段表(指向共享段表指向共享段表)，共享记数加共享记数加1,形成逻辑地址。形成逻辑地址。(3)本进程连接过本进程连接过(段名段名-段号对照表有，共享段表有或无段号对照表有，共享段表有或无)形成逻辑地址。形成逻辑地址。本讲稿第五十四页，共六十七页2.缺页中断缺页中断 调入所需页面，更新页表和总页表。调入所需页面，更新页表和总页表。3.越界中断越界中断 (1)段号越界：错误处理。段号越界：错误处理。(2)页号越界：如可扩展，扩展该段页号越界：如可扩展，扩展该段(增加页增加页)，修改页表和段，修改页表和段 表表(页表长度页表长度);如不可扩展，错误处理。如不可扩展，错误处理。4.越权中断越权中断 错误处理。错误处理。本讲稿第五十五页，共六十七页6.6 系统举例nLinux存储管理nWindows2000/XP存储管理本讲稿第五十六页，共六十七页6.6.1 Linux存储管理nPhysical memory-management（物理存储管理）（物理存储管理）nThree level page table（三级页表）（三级页表）nBuddy heap algorithm for managing memory pages(frames)（伙伴堆算法管理内存）（伙伴堆算法管理内存）nVirtual Memory management（虚拟存储管理）（虚拟存储管理）nDemand paging（请求调页）（请求调页）nno pre-paging,（无预调）（无预调）nno working set.（无工作集）（无工作集）本讲稿第五十七页，共六十七页6.6.1 Linux存储管理Page replacementlpage daemon:kswapd,runs once a second,keep enough free pages in memory.（页守护进程）（页守护进程）lflush daemon:bdflush,wakes up periodically,“dirty page out”.（刷新守护进程）（刷新守护进程）本讲稿第五十八页，共六十七页Managing Physical MemorynAllocate ranges of physically-contiguous pages on request.（为进程分配连续存储区）（为进程分配连续存储区）nThe allocator uses a buddy-heap algorithm to keep track of available physical pages.(Buddy heap算法记载可用存储区）算法记载可用存储区）nEach allocatable memory region is paired with an adjacent partner.（每个可用存储区有一个伙伴）（每个可用存储区有一个伙伴）本讲稿第五十九页，共六十七页Managing Physical MemorynWhenever two allocated partner regions are both freed up they are combined to form a larger region.（两个相邻的伙伴被释放时，合（两个相邻的伙伴被释放时，合并为一个大空闲区）并为一个大空闲区）nIf a memory request cannot be satisfied by allocating an existing small free region,then a larger free region will be subdivided into two partners to satisfy the request.（小区域不能满足（小区域不能满足时，分割大区域）时，分割大区域）本讲稿第六十页，共六十七页Buddy heap存储分配存储分配 6432323216163216888321688-req(8)8req(8)-req(4)rel(8)32844164rel(8)83288832448888844328本讲稿第六十一页，共六十七页10(29)9(28)8(27)4(23)3(22)2(21)1(20)数据结构：数据结构：组号（空闲块数组号（空闲块数）：链头指针）：链头指针Buddy Heap Implementation249681632256相同长度的空闲块相同长度的空闲块构成一组构成一组512本讲稿第六十二页，共六十七页10(29)9(28)8(27)4(23)3(22)2(21)1(20)申请长度为申请长度为128，在第，在第8组中取一块。若第组中取一块。若第8组组已空，在第已空，在第9组取一块，分配其中的组取一块，分配其中的128页，页，并将剩余的并将剩余的128页记入第页记入第8组。若第组。若第9组也空，组也空，在第在第10组取一块，进行两次分割，分配组取一块，进行两次分割，分配128页，剩余的页，剩余的128页和页和256页分别记入第页分别记入第8组组和第和第9组。组。释放是上述操作的逆过程，考虑伙伴的合并。释放是上述操作的逆过程，考虑伙伴的合并。两个块为伙伴的条件是两个块为伙伴的条件是:（1）两个块的大小相）两个块的大小相同，如同，如b个页面；（个页面；（2）两个块的物理地址连）两个块的物理地址连续；（续；（3）位于后面块的最后页面编号必）位于后面块的最后页面编号必须是须是2b的整数倍。的整数倍。Buddy Heap Implementation本讲稿第六十三页，共六十七页Buddy Heap ImplementationI unit blockhead2 unit blockhead4 unit blockhead8 unit blockheadI6 unit blockhead32 unit blockhead.Problem:internal fragmentationeg:req(17)second memory allocationcarves slabs(small units)and manage them separatelythird memory allocationfor allocation of no-contiguous memory本讲稿第六十四页，共六十七页作业总结：P109，#17Var B:Array0.k-1Of object;i,j:0.k-1;(0,k-1)S1,S2,S3,S4,S5,mutex:semaphore;(k,0,0,k-2,k-1,1);W1:Cycle Produce a frame;P(S4);P(S1);P(mutex);BI:=frame;i:=i+1;V(mutex);V(S2);End;W2:Cycle Produce a cycle;P(S5);P(S1);P(mutex);Bj:=cycle;j:=j-1;V(mutex);V(S3);End;W3:Cycle P(S2);P(mutex);I:=I-1;f:=BI;V(mutex);V(S4);V(S1);P(S3);P(S3);P(mutex);j:=j+1;c1:=Bj;j:=j+1;c2:=Bj;V(mutex);V(S5);V(S5);V(S1);V(S1);make a bikeEnd;本讲稿第六十五页，共六十七页Readers and writers problem,Ada solution.task body readers_writers isrcount,wcount:integer;begin rcount:=0;wcount:=0;loop select when wcount=0=accept start_read do rcount:=rcount+1;end start_read or when rcount0 accept finish_read do rcount:=rcount-1;end finish_read本讲稿第六十六页，共六十七页 or when wcount=0=accept start_write do while rcount0 do accept finish_read do rcount:=rcount-1;end finish_read end while end start_write or when wcount0=accept finish_write do wcount:=wcount-1 end finish_write end select end loopend readers_writers;本讲稿第六十七页，共六十七页