《操作系统：06第六章 存储管理（2）》由会员分享，可在线阅读，更多相关《操作系统：06第六章 存储管理（2）（51页珍藏版）》请在金锄头文库上搜索。
1、6.4 外存资源管理外存资源管理n外存空间划分外存空间划分n静态等长，静态等长，2i, 称为一块称为一块(block)，块是外存块是外存分配的基本单位，也是分配的基本单位，也是IO传输的基本单位。传输的基本单位。n外存空间分配外存空间分配n空闲块链空闲块链(慢慢)n空闲块表空闲块表(UNIX)n字位映像图字位映像图Swap空间空间File空间空间输入输入井井输出输出井井进程与外存对应关系进程与外存对应关系n界地址界地址n每进程占一组外存连续块；每进程占一组外存连续块；n每进程占二组外存连续块（双对界）。每进程占二组外存连续块（双对界）。n页式页式n内存一页，外存一块。内存一页，外存一块。n段式
2、段式n每段占外存若干连续块。每段占外存若干连续块。n段页式段页式n内存一页，外存一块。内存一页，外存一块。6.5 虚拟存储系统虚拟存储系统n无虚拟问题无虚拟问题n不能运行比内存大的程序；不能运行比内存大的程序；n进程全部装入内存，浪费空间（进程活动具有局部进程全部装入内存，浪费空间（进程活动具有局部性性)。n单控制流的进程需要较少部分在内存；单控制流的进程需要较少部分在内存；n多控制流的进程需要较多部分在内存。多控制流的进程需要较多部分在内存。n虚拟存储虚拟存储n进程部分装入内存，部分（或全部）装入外存，运进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。行
3、时访问在外存部分动态调入，内存不够淘汰。6.5.1 虚拟页式存储系统虚拟页式存储系统n基本原理基本原理n进程运行前：进程运行前：n全部装入外存，部分装入内存。全部装入外存，部分装入内存。n进程运行时：进程运行时：n访问页不在内存，发生缺页中断，中断处理程序：访问页不在内存，发生缺页中断，中断处理程序：n找到访问页在外存的地址；找到访问页在外存的地址；n在内存找一空闲页面；在内存找一空闲页面；n如没有，按淘汰算法淘汰一个；如没有，按淘汰算法淘汰一个；n如需要，将淘汰页面写回外存，修改页表和总页表；如需要，将淘汰页面写回外存，修改页表和总页表；n读入所需页面（切换进程）；读入所需页面（切换进程）；
4、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. 按进程按进程
5、长度长度比例分配比例分配 pi共共si个页面；个页面；S= si；内存共内存共m个页架个页架 ai=(si/S) m 3. 按进程按进程优先级优先级比例分配比例分配 4. 按进程按进程长度和优先级别长度和优先级别比例分配比例分配 静态策略没有反映：静态策略没有反映：(1)程序结构；程序结构；(2)程序在不同时刻的行为特性。程序在不同时刻的行为特性。6.5.1.3 外存块的分配策略外存块的分配策略 1. 静态分配静态分配 外存保持进程的全部页面：外存保持进程的全部页面： 优点：速度快优点：速度快-淘汰时不必写回淘汰时不必写回(未修改情况未修改情况) 缺点：外存浪费缺点：外存浪费 2. 动态分配动
6、态分配 外存仅保持进程不在内存的页面：外存仅保持进程不在内存的页面： 优点：节省外存优点：节省外存 缺点：速度慢缺点：速度慢-淘汰时必须写回淘汰时必须写回6.5.1.4 页面调入时机页面调入时机 1. 请调请调(demand paging) upon page fault, 发生缺页中断时调入。发生缺页中断时调入。 2. 预调预调(prepaging) before page fault, 将要访问时调入将要访问时调入(根据程序顺序行为，根据程序顺序行为， 不一定准）不一定准） 预调必须辅以请调。预调必须辅以请调。 用于：页淘汰、段淘汰、快表淘汰。用于：页淘汰、段淘汰、快表淘汰。 Object
7、ive: 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 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 6 6 6 6 6 60 0 0 0 0 0 0 0 0 0 0 0 4 4 4
8、 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6.5.1.5 淘汰算法淘汰算法(replacement algorithm)2. 先进先出先进先出(FIFO) 淘汰最先调入的。淘汰最先调入的。 依据依据: 先进入的可能已经使用完毕。先进入的可能已经使用完毕。 实现：队列实现：队列 negative case: 有些代码和数据可能整个程序运行中用有些代码和数据可能整个程序运行中用到。到。 Belady异常异常
9、: 例子：例子：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访问序列访问序列:
10、访问序列访问序列:内存页面内存页面:内存页面内存页面: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 2107472104Stac
11、k before aStack before b a bnLRU算法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 2 2 2 2 2 2 2 4 4 4 4 4 4 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 3 3 3 3 3 3 2 2 2 2 2
12、 2 2 2 2 2 2 2 2 2 2 2 2 2 6 6 6 6 6 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. 最不经常使用的先淘汰最不经常使用的先淘汰(L
13、FU) 淘汰使用次数最少的。淘汰使用次数最少的。 依据依据: 活跃访问页面应有较大的访问次数活跃访问页面应有较大的访问次数. Suffer: (1) 前期使用多，但以后不用，难换出；前期使用多，但以后不用，难换出； (2) 刚调入的页面，引用少，被换出可能大。刚调入的页面，引用少，被换出可能大。 实现：记数器，调入清实现：记数器，调入清0，访问增，访问增1，淘汰选取最小者。，淘汰选取最小者。6. 最经常使用的先淘汰最经常使用的先淘汰(MFU) 淘汰使用次数最多的。淘汰使用次数最多的。 依据依据: 使用多的可能已经用完了。使用多的可能已经用完了。 Suffer: 程序有些成分是在整个程序运行中都
14、使用的。程序有些成分是在整个程序运行中都使用的。6.5.1.6 颠簸颠簸(thrashing) 页面在内存与外存之间频繁换入换出。页面在内存与外存之间频繁换入换出。 原因：原因：(1) 分给进程物理页架过少；分给进程物理页架过少； (2) 淘汰算法不合理。淘汰算法不合理。 处理：处理：(1) 增加分给进程物理页架数；增加分给进程物理页架数；(2) 改进淘汰算法。改进淘汰算法。思考题：思考题：在某些虚拟页式存储管理系统中，内存中总保持一个在某些虚拟页式存储管理系统中，内存中总保持一个空闲的物理页架，这样做有什么好处？空闲的物理页架，这样做有什么好处？6.5.1.7 工作集模型工作集模型(work
15、ing 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(t
16、2, )=2,3,4 t1t2工作集与时间有关：工作集与时间有关：工作集与窗口尺寸有关：工作集与窗口尺寸有关：程序大小程序大小 WS窗口尺寸确定：窗口尺寸确定： 过小：活动页面不能全部装入，页故障率高；过小：活动页面不能全部装入，页故障率高； 过大：内存浪费。过大：内存浪费。Madnick, Donovan建议：建议： 1万次访内。万次访内。实现：页表中增加访问位：实现：页表中增加访问位： 访问访问位位页表：页表： 开始时，全部开始时，全部清清0,访问：置访问：置1, 结束时结束时(新新 开始时开始时)访问标志为访问标志为1的，为该的，为该 期间工作集，期间工作集， n+1=wn+(1-) n
17、6.5.1.8 页故障率反馈模型页故障率反馈模型PFFB(Page Fault Feed Back)页故障率高页故障率高(达到某上界阈值达到某上界阈值)：内存页面少，增加。：内存页面少，增加。页故障率低页故障率低(达到某下界阈值达到某下界阈值)：内存页面多，减少。：内存页面多，减少。6.5.2 虚拟段式存储系统虚拟段式存储系统n进程运行前，全部装入外存，部分装入进程运行前，全部装入外存，部分装入内存，访问段不再内存时，发生缺段中内存，访问段不再内存时，发生缺段中断。断。6.5.2 虚拟段式存储系统虚拟段式存储系统基本原理：基本原理：修改过修改过TF缺段中断缺段中断在外存找到所缺段在外存找到所缺
18、段内存够用内存够用选一段淘汰选一段淘汰写回外存写回外存修改段表修改段表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. 静态连接静态连
19、接n静态连接：运行前连接，由静态连接：运行前连接，由link完成；完成；n动态连接：运行时连接，由动态连接：运行时连接，由OS完成完成.n静态连接的缺点静态连接的缺点n连接时间长；连接时间长；n目标代码长；目标代码长；n连接段可能并不执行连接段可能并不执行(未用到未用到)。动态连接的实现动态连接的实现(Multics为例为例)段名段名-段号对照表：每进程一个段号对照表：每进程一个段名段名 段号段号sname snum . .符号名符号名 段内位移段内位移 func 150 . .符号表：每段一个符号表：每段一个段形式：段形式：符号表符号表目标代码目标代码或者数据或者数据 静态连接由静态连接由l
20、ink使用使用连接完不再需要连接完不再需要(1) 编译编译(汇编汇编)时：时： 遇到访问外段指令，采用间接寻址，指向一个间接字：遇到访问外段指令，采用间接寻址，指向一个间接字：LD1: 未连接未连接0: 已连接已连接符号地址：符号地址：“X|”逻辑地址：逻辑地址：(段号段号,段内地址段内地址)(2) 执行时：执行时： 遇到间接指令，且遇到间接指令，且L=1, 发生链接中断，处理程序：发生链接中断，处理程序：(a) 由由D取出符号地址；取出符号地址；(b) 由段名查段名由段名查段名-段号对照表，是否分配段号。段号对照表，是否分配段号。 已分配段号：取出该段号，找到该段已分配段号：取出该段号，找到
21、该段(内存或外存内存或外存) 由入口名查符号表得段内地址；由入口名查符号表得段内地址； (段号，段内地址段号，段内地址)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)
22、X段段 300 40012345678300400段表段表 段首段首址址 .段号段号 0 1 2 3 .段名段名 段号段号Main 0A 1W 2段段名名-段段号号对对照照表表第一次连接后：第一次连接后：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
23、*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纯段共享
24、，纯段共享，n杂段私用。杂段私用。6.5.3 虚拟段页式存储系统虚拟段页式存储系统n考虑考虑n段的动态连接段的动态连接n段的共享段的共享n段长度的动态变化段长度的动态变化所需表目：所需表目：(1) 段表：每进程一个段表：每进程一个页表长度页表长度 页表首址页表首址 访问权限访问权限 扩展标志扩展标志 共享段入口共享段入口 段号段号(2) 页表：每段一个页表：每段一个内存页号内存页号 外存块号外存块号 内外标志内外标志 修改标志修改标志 .逻辑页号逻辑页号(3) 共享段表：系统一个共享段表：系统一个段名段名 页表长度页表长度 页表首址页表首址 扩充标志扩充标志 共享计数共享计数 (4) 段名段名
25、-段号对照表：每进程一个段号对照表：每进程一个对应关系：对应关系：私用段私用段共享段共享段共享段表共享段表P1段表：段表：P2段表：段表：共享段表共享段表P1段表：段表：P2段表：段表： 15 16 17 18 19 20 21 22 23 24 25 . .页表页表页表页表存储空间：存储空间：sisjsk所需寄存器：所需寄存器：(1) 段表长度寄存器：保存正运行进程段表长度段表长度寄存器：保存正运行进程段表长度(2) 段表首址寄存器：保存正运行进程段表首址段表首址寄存器：保存正运行进程段表首址(3) 快表快表段号段号 逻辑页号逻辑页号 页架号页架号 访问权限访问权限 修改标志修改标志 地址映
26、射：地址映射： : (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)中
27、断处理：中断处理：1. 连接中断连接中断(1) 所有进程均未连接所有进程均未连接(共享段表、段名共享段表、段名-段号对照表均无段号对照表均无) 建立页表，由文件读入外存建立页表，由文件读入外存swap，部分页读入内存，分配部分页读入内存，分配 段号，填段名段号，填段名-段号对照表，如是共享段填共享段表，填段号对照表，如是共享段填共享段表，填 段表段表 ，形成逻辑地址。，形成逻辑地址。(2) 其它进程连接过，本进程未连接过其它进程连接过，本进程未连接过(共享段表有，段名共享段表有，段名-段段 号对照表无号对照表无) 分配段号，填段名分配段号，填段名-段号对照表，填段表段号对照表，填段表(指向共享
28、段表指向共享段表)， 共享记数加共享记数加1, 形成逻辑地址。形成逻辑地址。(3) 本进程连接过本进程连接过(段名段名-段号对照表有，共享段表有或无段号对照表有，共享段表有或无) 形成逻辑地址。形成逻辑地址。2. 缺页中断缺页中断 调入所需页面，更新页表和总页表。调入所需页面，更新页表和总页表。3. 越界中断越界中断 (1) 段号越界：错误处理。段号越界：错误处理。 (2) 页号越界：如可扩展，扩展该段页号越界：如可扩展，扩展该段(增加页增加页)，修改页表和，修改页表和段段 表表(页表长度页表长度); 如不可扩展，错误处理。如不可扩展，错误处理。4. 越权中断越权中断 错误处理。错误处理。6.
29、6 系统举例nLinux存储管理nWindows2000/XP存储管理6.6.1 Linux存储管理lPhysical memory-management（物理存储管理）物理存储管理）Three level page table（三级页表）三级页表）Buddy heap algorithm for managing memory pages (frames) （伙伴堆算法管理内存）伙伴堆算法管理内存）lVirtual Memory management（虚拟存储管理）虚拟存储管理）Demand paging（请求调页）请求调页）lno pre-paging, （无预调）无预调）lno work
30、ing 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 MemorylAllocate ranges of physically-contiguous pages on reques
31、t.（为进程分配连续存储区）为进程分配连续存储区）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.（每个可用存储区有一个伙伴）每个可用存储区有一个伙伴）Managing Physical MemoryWhenever two allocated partner regions a
32、re 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.（小区域小区域不能满足时，分割大区域）不能满足时
33、，分割大区域）Buddy heap存储分配存储分配 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)数据结构：数据结构：组号组号（空闲块数空闲块数 ）：链头指针）：链头指针Buddy Heap Implementation249681632256相同长度的空闲块相同长度的空闲块构成一组构成一组51210(29)9(28) 8(27)4(23)3(22)2(21)1(20)申请长度为申请长度为128
34、，在第，在第8组中取一块。若组中取一块。若第第8组已空，在第组已空，在第9组取一块，分配其中组取一块，分配其中的的128页，并将剩余的页，并将剩余的128页记入第页记入第8组。组。若第若第9组也空，在第组也空，在第10组取一块，进行组取一块，进行两次分割，分配两次分割，分配128页，剩余的页，剩余的128页页和和256页分别记入第页分别记入第8组和第组和第9组。组。释放是上述操作的逆过程，考虑伙伴的释放是上述操作的逆过程，考虑伙伴的合并。两个块为伙伴的条件是合并。两个块为伙伴的条件是:（1）两）两个块的大小相同，如个块的大小相同，如b个页面；（个页面；（2）两）两个块的物理地址连续；（个块的物
35、理地址连续；（3）位于后面块）位于后面块的最后页面编号必须是的最后页面编号必须是2b的整数倍。的整数倍。Buddy Heap ImplementationBuddy 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 ma
36、nage 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
37、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 read
38、ers_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;
