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

《操作系统第六章存储管理2.ppt》由会员分享，可在线阅读，更多相关《操作系统第六章存储管理2.ppt（69页珍藏版）》请在三一文库上搜索。

1、6.4 外存资源管理,外存空间划分 静态等长，2i, 称为一块(block)，块是外存分配的基本单位，也是IO传输的基本单位。 外存空间分配 空闲块链(慢) 空闲块表(UNIX) 字位映像图,Swap 空间,File 空间,输入井,输出井,进程与外存对应关系,界地址 每进程占一组外存连续块； 每进程占二组外存连续块（双对界）。 页式 内存一页，外存一块。 段式 每段占外存若干连续块。 段页式 内存一页，外存一块。,6.5 虚拟存储系统,无虚拟问题 不能运行比内存大的程序； 进程全部装入内存，浪费空间（进程活动具有局部性)。 单控制流的进程需要较少部分在内存； 多控制流的进程需要较多部分在内存。

2、 虚拟存储 进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。,6.5.1 虚拟页式存储系统,基本原理 进程运行前： 全部装入外存，部分装入内存。 进程运行时： 访问页不在内存，发生缺页中断，中断处理程序： 找到访问页在外存的地址； 在内存找一空闲页面； 如没有，按淘汰算法淘汰一个； 如需要，将淘汰页面写回外存，修改页表和总页表； 读入所需页面（切换进程）； 重新启动中断指令。,6.5.1 虚拟页式存储管理(Cont.),虚拟页式存储管理地址映射,指令给出逻辑地址(p,d),由p查快表得到 f,查到,f、d合并得物理地址,0pl-1,越界中断,由b、p查找页

3、表得f,该页在内存,缺页中断,保存现场,有空闲页框,选一页面淘汰,该页面修改过,写回外存,读入所需页面,更新页表和快表,恢复现场,F,F,F,T,T,T,( f,d) 快表 如快表满，淘汰一表项,硬 件 完 成,软 件 完 成,T,f、d合并得物理地址,对页表的改进：,对快表的改进：,. . .,逻辑页号 页框号 访问权限 修改标志,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、例分配 4. 按进程长度和优先级别比例分配 静态策略没有反映： (1)程序结构； (2)程序在不同时刻的行为特性。,6.5.1.3 外存块的分配策略 1. 静态分配 外存保持进程的全部页面： 优点：速度快-淘汰时不必写回(未修改情况) 缺点：外存浪费 2. 动态分配 外存仅保持进程不在内存的页面： 优点：节省外存 缺点：速度慢-淘汰时必须写回,6.5.1.4 页面调入时机 1. 请调(demand paging) upon page fault, 发生缺页中断时调入。 2. 预调(prepaging) before page fault, 将要访问时调入(根据程序顺序行为， 不一定准） 预调必

5、须辅以请调。,用于：页淘汰、段淘汰、快表淘汰。 Objective: lowest page-fault rate. 1. 最佳淘汰算法(OPT-optimal) 淘汰将来最长时间以后才用到的。 效率最高，not feasible。,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个物理页面：

6、页故障率=10/12,FIFO淘汰算法(belady异常),页故障率=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,Stack before a,Stac

7、k before b,a b,LRU算法,4. 最近不用的先淘汰(not used recently) 淘汰最近一段时间未用到的。 实现：每页增加一个访问标志， 访问置1，定时清0， 淘汰时取标志为0的。 LRU算法的近似： Reference string: 2, 3, 5, 6, 4, 2, 5, 6, 7, 5, 6, 8,标志清0,选择淘汰 LRU：3 NUR：2，3，4任意,5. 最不经常使用的先淘汰(LFU) 淘汰使用次数最少的。 依据: 活跃访问页面应有较大的访问次数. Suffer: (1) 前期使用多，但以后不用，难换出； (2) 刚调入的页面，引用少，被换出可能大。 实现：

8、记数器，调入清0，访问增1，淘汰选取最小者。 6. 最经常使用的先淘汰(MFU) 淘汰使用次数最多的。 依据: 使用多的可能已经用完了。 Suffer: 程序有些成分是在整个程序运行中都使用的。,7. 二次机会(second chance),淘汰装入最久且最近未被访问的页面。 实现时：采用拉链数据结构。,8. 时钟算法(clock algorithm),将页面组织成环形，有一个指针指向当前位置。每次需要淘汰页面时，从指针所指的页面开始检查。如果当前页面的访问位为0，即从上次检测到目前，该页没有访问过，则将该页替换。如果当前页面的访问位为1，则将其清0，并顺时针移动指针到下一个位置。重复上述步骤

9、直至找到一个访问位为0的页面。 可以看出，时钟算法与二次机会算法的淘汰效果是基本相同的，差别在于二者所采用的数据结构不同，二次机会使用的是链表，需要额外存储空间，且摘链入链速度很慢。而时钟算法可直接利用页表中的引用位，外加一个指针，速度快且节省空间。,页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

10、,框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页,时钟算法,改进的时钟算法,考虑修改标志m r=0, m=0：最佳淘汰页面 r=0, m=1：淘汰前回写 r=1, m=0：不淘汰 r=1, m=1：不淘汰,改进的时钟

11、算法,步骤1： 由指针当前位置开始扫描，选择最佳淘汰页面，不改变引用位，将第一个遇到的r=0且m=0的页面作为淘汰页面； 步骤2： 如步骤1失败，再次从原位置开始，找r=0且m=1的页面，将第一个满足上述要求的页面作为淘汰页面，同时将扫描过页面的r位清0； 步骤3： 若步骤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,访

12、问第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=

13、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年考研试题,某虚拟页式系统，进程空间和内存空间都是64k，页长1K，某进程6个页，内存分配4个页框，采用局部

14、置换，280时刻页表和Clock数据结构如下：,0页,2页,3页,5页,框5,框12,框8,框3,(顺时针),2010年考研试题,(1)280时刻访问13B7H，逻辑页号是多少？ (2)采用FIFO置换算法，物理页框号是多少？物理地址是多少？ (3)采用CLOCK置换算法，页框号是多少？物理地址是多少？,2010年考研试题,（1）逻辑地址13B7H化为二进制数为0001001110110111，其中后10位为页内地址，前6位为逻辑页号，即逻辑页号为4。 （2）4号页不在内存，发生缺页中断，按FIFO置换算法，应置换第5页，所得页框号3，形成物理地址0000111110110111，划成16进制

15、为0FB7H。 （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,

16、7,1,6,2,2 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 (page reference),t,：称为窗口尺寸(window size)。 Denning 认为：为使程序有效运行，工作集应能放入内存。,T,工作集与时间有关：,工作集与窗口尺寸有关：,程序大小,WS,窗口尺寸确定： 过小：活动页面不能全部装入，页故障率高； 过大：内存浪费。 Madnick, Donovan建议： 1万次访内。 实现：页表中增加访问位：,开始时，全部清0, 访问：置1, 结束时(新开始时)访问标志为1的，为该期间工作集， n+1=wn+(1-) n,6.5.1.8 页故障率反馈模型,PFFB

17、(Page Fault Feed Back) 页故障率高(达到某上界阈值)：内存页面少，增加。 页故障率低(达到某下界阈值)：内存页面多，减少。,6.5.2 虚拟段式存储系统,进程运行前，全部装入外存，部分装入内存，访问段不再内存时，发生缺段中断。,6.5.2 虚拟段式存储系统(Cont.),虚拟段式存储管理地址映射,指令确定逻辑地址(s,d),由s查快表得到b 和 l,查到,b+d 得到物理地址,0sl-1,越界中断,由b、s查找段表,该段在内存,缺段中断,保存现场,内存可满足,选一段淘汰,该段修改过,写回外存,读入 该段,修改段表和快表,恢复现场,F,F,F,T,T,T,( s, b,l)

18、 快表 如快表满，淘汰一表项,硬 件 完 成,软 件 完 成,T,0dl-1,T,越界中断,F,0dl-1,越界 中断,b+d 得物理地址,找到该段在外存的位置,紧凑够,紧凑,T,T,F,修改段表,. . . . ,(1)段表的改进：,()快表的改进：,6.5.2.2 段的动态连接(dynamic linking),动态连接 vs. 静态连接 静态连接：运行前连接，由link完成； 动态连接：运行时连接，由OS完成. 静态连接的缺点 连接时间长； 目标代码长； 连接段可能并不执行(未用到)。,动态连接的实现(Multics为例) 段名-段号对照表：每进程一个,符号表：每段一个,段形式：,符号表

19、,目标代码 或者数据,静态连接由link使用 连接完不再需要,(1) 编译(汇编)时： 遇到访问外段指令，采用间接寻址，指向一个间接字：,L,D,(2) 执行时： 遇到间接指令，且L=1, 发生链接中断，处理程序： (a) 由D取出符号地址； (b) 由段名查段名-段号对照表，是否分配段号。, 已分配段号：取出该段号，查段表找到该段(内存或 外存)，由入口名查符号表得段内地址； (段号，段内地址)D, 0 L 未分配段号：找到该段所在文件，读入内存，读入 外存，分配段号，填写段名-段号对照表，填写段 表，转(b),例子：汇编前：,. Load 1, X| Load 2, X| .,W段,X段,

20、 1234 5678 .,Y:,Z:,汇编后，连接前：,第一次连接后：,X 3,第一次连接后：,X 3,段表, 段首址, .,段号 0 1 2 3 .,Main 0,A 1,W 2,段名-段号对照表,X 3,第二次连接后：,动态连接问题,动态连接与共享的矛盾 动态连接：修改连接字（代码） 段的共享：要求纯代码（pure code) 解决方法 共享代码分为“纯段”和“杂段” 纯段共享， 杂段私用。,6.5.3 虚拟段页式存储系统,考虑 段的动态连接 段的共享 段长度的动态变化,所需表目：,(1) 段表：每进程一个,段号,(2) 页表：每段一个,逻辑页号,(3) 共享段表：系统一个,段名 页表长度

21、 页表首址 扩充标志 共享计数 ,(4) 段名-段号对照表：每进程一个 对应关系：,共享段表,P1段表：,P2段表：,15,16,17,18,19,20,21,22,23,24,25,.,.,页表,页表,存储空间：,si,sj,sk,所需寄存器： (1) 段表长度寄存器：保存正运行进程段表长度 (2) 段表首址寄存器：保存正运行进程段表首址 (3) 快表,地址映射：,: (s,p,d) (f,d) 逻辑地址(s,p,d)物理地址(f,d),由(s,p)查快表得f,查到,访问合法,形成物理地址(f,d),是间址,有障碍位,继续,0sl-1,0pl-1,由(s,b)查段表得b,l,越界中断,越界中

22、断,由b和p查页表得f,该页在内存,缺页中断,(s,p,f)快表,越权中断,T,F,T,F,连接中断,T,F,T,F,T,F,T,F,T,l:段表长度 b:段表首地址 l: 页表长度 b: 页表首地址,形成物理地址(f,d),中断处理： 1. 连接中断 (1) 所有进程均未连接(共享段表、段名-段号对照表均无) 建立页表，由文件读入外存swap，部分页读入内存，分配 段号，填段名-段号对照表，如是共享段填共享段表，填 段表 ，形成逻辑地址。 (2) 其它进程连接过，本进程未连接过(共享段表有，段名-段 号对照表无) 分配段号，填段名-段号对照表，填段表(指向共享段表)， 共享记数加1, 形成逻

23、辑地址。 (3) 本进程连接过(段名-段号对照表有，共享段表有或无) 形成逻辑地址。,2. 缺页中断 调入所需页面，更新页表和总页表。 3. 越界中断 (1) 段号越界：错误处理。 (2) 页号越界：如可扩展，扩展该段(增加页)，修改页表和段 表(页表长度); 如不可扩展，错误处理。 4. 越权中断 错误处理。,6.6 系统举例,Linux存储管理 Windows2000/XP存储管理,6.6.1 Linux存储管理,Physical memory-management（物理存储管理） Three level page table（三级页表） Buddy heap algorithm for

24、managing memory pages (frames) （伙伴堆算法管理内存） Virtual Memory management（虚拟存储管理） Demand paging（请求调页） no pre-paging, （无预调） no working set.（无工作集）,6.6.1 Linux存储管理,Page replacement page daemon: kswapd, runs once a second , keep enough free pages in memory. （页守护进程） flush daemon: bdflush, wakes up periodicall

25、y, “dirty page out”.（刷新守护进程）,Managing Physical Memory,Allocate ranges of physically-contiguous pages on request.（为进程分配连续存储区） The 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.（每

26、个可用存储区有一个伙伴）,Managing Physical Memory,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

27、partners to satisfy the request.（小区域不能满足时，分割大区域）,Buddy heap存储分配,64,32,16 16,32,16,8,32,16,-req(8),8,req(8),-req(4),rel(8),16,4,rel(8),8,32 8,32,4,4,8,8,8,4,4,32,8,数据结构： 组号（空闲块数 ）：链头指针,Buddy Heap Implementation,24,96,8,16,32,256,相同长度的空闲块构成一组,512,申请长度为128，在第8组中取一块。若第8组已空，在第9组取一块，分配其中的128页，并将剩余的128页记入第

28、8组。若第9组也空，在第10组取一块，进行两次分割，分配128页，剩余的128页和256页分别记入第8组和第9组。 释放是上述操作的逆过程，考虑伙伴的合并。两个块为伙伴的条件是:（1）两个块的大小相同，如b个页面；（2）两个块的物理地址连续；（3）位于后面块的最后页面编号必须是2b的整数倍。,Buddy Heap Implementation,Buddy Heap Implementation,Problem: internal fragmentation eg: req(17) second memory allocation carves slabs (small units) and m

29、anage them separately third memory allocation for allocation of no-contiguous memory,作业总结：P109， #17 Var B:Array0k-1Of object; i, j: 0k-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 Pr

30、oduce 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 bike End;,Readers and writers problem, Ada solution.

31、task body readers_writers is rcount, 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 loop end readers_writers;,