操作系统第六章存储管理2

6.4 外存资源管理外存资源管理n外存空间划分外存空间划分n静态等长，静态等长，2i,称为一块称为一块(block)，块是外存，块是外存分配的基本单位，也是分配的基本单位，也是IO传输的基本单位。传输的基本单位。n外存空间分配外存空间分配n空闲块链空闲块链(慢慢)n空闲块表空闲块表(UNIX)n字位映像图字位映像图Swap空间空间File空间空间输入输入井井输出输出井井进程与外存对应关系进程与外存对应关系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重新启动中断指令。重新启动中断指令。6.5.1 虚拟页式存储管理虚拟页式存储管理(Cont.)虚拟页式存储管理地址映射虚拟页式存储管理地址映射指令给出逻辑地址指令给出逻辑地址(p,d)由由p查快表得到查快表得到 f查到查到 f、d合并得物理地址合并得物理地址0pl-1越界中断越界中断由由b、p查找页表得查找页表得f该页在内存该页在内存缺页中断缺页中断保存现场保存现场有空闲页框有空闲页框选一页面淘汰选一页面淘汰该页面修改过该页面修改过写回外存写回外存读入所需页面读入所需页面更新页表和快表更新页表和快表恢复现场恢复现场FFFTTT(f,d)快表快表如快表满，淘如快表满，淘汰一表项汰一表项硬硬件件完完成成软软件件完完成成T f、d合并得合并得物理地址物理地址对页表的改进：对页表的改进：对快表的改进：对快表的改进：逻辑页号逻辑页号 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 66 6 0 06 60 0 1 16 60 01 1 2 22 20 01 1 0 0 3 32 20 03 3 0 0 4 42 24 43 3 2 2 3 3 0 02 20 03 3 3 3 2 2 1 12 20 01 1 2 2 0 0 1 1 6 66 60 01 1 0 0 1 16.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 bnLRU算法6 66 6 0 06 60 0 1 16 60 01 1 2 22 20 01 1 0 0 3 32 20 03 3 0 0 4 44 40 03 3 2 24 40 02 2 3 34 43 32 2 0 00 03 32 2 3 3 2 2 1 11 13 32 2 2 2 0 01 10 02 2 1 1 6 61 10 06 6 0 0 1 14.最近不用的先淘汰最近不用的先淘汰(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/18.时钟算法时钟算法(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=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 认为：为使程序有效运行，工作集应能放入内存。认为：为使程序有效运行，工作集应能放入内存。TWS(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-)n6.5.1.8 页故障率反馈模型页故障率反馈模型PFFB(Page Fault Feed Back)页故障率高页故障率高(达到某上界阈值达到某上界阈值)：内存页面少，增加。：内存页面少，增加。页故障率低页故障率低(达到某下界阈值达到某下界阈值)：内存页面多，减少。：内存页面多，减少。6.5.2 虚拟段式存储系统虚拟段式存储系统n进程运行前，全部装入外存，部分装入进程运行前，全部装入外存，部分装入内存，访问段不再内存时，发生缺段中内存，访问段不再内存时，发生缺段中断。断。6.5.2 虚拟段式存储系统虚拟段式存储系统(Cont.)虚拟段式存储管理地址映射虚拟段式存储管理地址映射指令确定逻辑地址指令确定逻辑地址(s,d)由由s查快表得到查快表得到b 和和 l查到查到 b+d 得到物理地址得到物理地址0sl-1越界中断越界中断由由b、s查找段表查找段表该段在内存该段在内存缺段中断缺段中断保存现场保存现场内存可满足内存可满足选一段淘汰选一段淘汰该段修改过该段修改过写回外存写回外存读入读入该段该段修改段表和快表修改段表和快表恢复现场恢复现场FFFTTT(s,b,l)快表快表如快表满，淘如快表满，淘汰一表项汰一表项硬硬件件完完成成软软件件完完成成T0dl-1T越界中断越界中断F0dl-1越界越界中断中断 b+d 得物得物理地址理地址找到该段在外存的位置找到该段在外存的位置紧凑够紧凑够紧凑紧凑TTF修改段表修改段表.段号段号 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 3100: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存储管理lPhysical memory-management（物理存储管理）（物理存储管理）Three level page table（三级页表）（三级页表）Buddy heap algorithm for managing memory pages(frames)（伙伴堆算法管理内存）（伙伴堆算法管理内存）lVirtual Memory management（虚拟存储管理）（虚拟存储管理）Demand paging（请求调页）（请求调页）lno pre-paging,（无预调）（无预调）lno working set.（无工作集）（无工作集）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 MemorylAllocate ranges of physically-contiguous pages on request.（为进程分配连续存储区）（为进程分配连续存储区）lThe allocator uses a buddy-heap algorithm to keep track of available physical pages.(Buddy heap算法记载可用存储区）算法记载可用存储区）Each allocatable memory region is paired with an adjacent partner.（每个可用存储区有一个伙伴）（每个可用存储区有一个伙伴）Whenever two allocated partner regions are both freed up they are combined to form a larger region.（两个相邻的伙伴被释放时，（两个相邻的伙伴被释放时，合并为一个大空闲区）合并为一个大空闲区）If 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.（小区域（小区域不能满足时，分割大区域）不能满足时，分割大区域）6432323216163216888321688-req(8)8req(8)-req(4)rel(8)32844164rel(8)8328883244888884432810(29)9(28)8(27)4(23)3(22)2(21)1(20)数据结构：数据结构：组号（空闲块数组号（空闲块数）：链头指针）：链头指针249681632256相同长度的空闲块相同长度的空闲块构成一组构成一组51210(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的整数倍。的整数倍。I 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;