操作系统课件6_3

1、第六章第六章 存储管理存储管理l6.1 存储管理功能存储管理功能l6.2 内存资源管理内存资源管理l6.3 存储管理方式存储管理方式l6.4 外存空间管理外存空间管理l6.5 虚拟存储系统虚拟存储系统 16.4 外存资源管理外存资源管理l外存空间指磁盘等存储型设备上的存储区域外存空间指磁盘等存储型设备上的存储区域l逻辑上划分为四个部分：输入井、输出井、文逻辑上划分为四个部分：输入井、输出井、文件空间、交换空间件空间、交换空间l输入井和输出井用于实现作业的预输入和作业的缓输输入井和输出井用于实现作业的预输入和作业的缓输出出l文件空间用于保存文件文件空间用于保存文件l交换空间或对换空间用于实现虚拟

2、存储的外存空间交换空间或对换空间用于实现虚拟存储的外存空间, 在分级存储体系中在分级存储体系中, 可看成是内存的扩充可看成是内存的扩充Swap空间空间File空间空间输入输入井井输出输出井井26.4.1 外存空间划分外存空间划分 l存储空间可看成是物理块所构成的有序存储空间可看成是物理块所构成的有序序列序列l所有块的长度相同所有块的长度相同, 通常为通常为2i, 如如256字节、字节、512字节、字节、1024字节等字节等l这些块由这些块由0开始依次地编号开始依次地编号, 称作称作块号块号l块是外存分配的基本单位块是外存分配的基本单位, 也是也是I/O传输的基传输的基本单位本单位 36.4.2

3、 外存空间分配外存空间分配l外存的分配可采用与内存相仿的方法外存的分配可采用与内存相仿的方法l唯一差别在于内存分配的基本单位是单元唯一差别在于内存分配的基本单位是单元, 外外存分配的基本单位是块存分配的基本单位是块l如果需求不足一个完整的块如果需求不足一个完整的块, 则可能形成块内则可能形成块内“零头零头”。l外存空间分配采用如下三种方法之一外存空间分配采用如下三种方法之一: l空闲块链空闲块链(慢慢)l空闲块表空闲块表(UNIX)l字位映像图字位映像图46.4.2 外存空间分配外存空间分配l空闲块链空闲块链(与空闲页链相似，速度慢与空闲页链相似，速度慢)：所：所有空闲块连成一个链有空闲块连成

4、一个链l空闲块表空闲块表Unix(与空闲页表相似与空闲页表相似)：相连的：相连的空闲块记录在同一栏目中空闲块记录在同一栏目中l字位映象图：用一位代表一块的状态，这字位映象图：用一位代表一块的状态，这些与内存空间管理相仿些与内存空间管理相仿5进程与外存对应关系进程与外存对应关系l界地址存储管理外存空间分配界地址存储管理外存空间分配 l每进程占一组外存连续块每进程占一组外存连续块l每进程占二组外存连续块（双对界）每进程占二组外存连续块（双对界）l页式页式l内存页面的长度与外存块的长度相同内存页面的长度与外存块的长度相同l内存一页，外存一块内存一页，外存一块l进程在外存占有若干个块进程在外存占有若干

5、个块, 块的编号可以不连续块的编号可以不连续 l段式段式l每段占外存若干连续块每段占外存若干连续块l进程的多个段之间在外存中可不连续进程的多个段之间在外存中可不连续 6进程与外存对应关系进程与外存对应关系l段页式段页式l内存页面长度与外存块长度相同内存页面长度与外存块长度相同l内存一页，外存一块内存一页，外存一块l段内多个页所对应的外存块可不连续段内多个页所对应的外存块可不连续l一个进程的多个段可分散在外存不同区域中一个进程的多个段可分散在外存不同区域中76.5 虚拟存储系统虚拟存储系统l无虚拟存储问题无虚拟存储问题l不能运行比内存大的程序不能运行比内存大的程序l进程全部装入内存，浪费空间（进

6、程活动具有局部进程全部装入内存，浪费空间（进程活动具有局部性性)。l虚拟存储虚拟存储l一种借助于外存空间一种借助于外存空间, 允许一个进程在其运行过程允许一个进程在其运行过程中部分地装入内存的技术中部分地装入内存的技术l将内存与外存有机结合将内存与外存有机结合, 得到一个容量相当于外存得到一个容量相当于外存, 速度接近于内存的存储体系速度接近于内存的存储体系 l进程部分装入内存，部分（或全部）装入外存，运进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。行时访问在外存部分动态调入，内存不够淘汰。86.5 虚拟存储系统虚拟存储系统l6.5.1 虚拟页式存储系统

7、虚拟页式存储系统 l6.5.2 虚拟段式存储系统虚拟段式存储系统 l6.5.3 虚拟段页式存储系统虚拟段页式存储系统 96.5.1 虚拟页式存储系统虚拟页式存储系统l基本原理基本原理l进程运行前：进程运行前：l全部装入外存，部分装入内存。全部装入外存，部分装入内存。l进程运行时：进程运行时：l访问页不在内存，发生访问页不在内存，发生缺页中断缺页中断，中断处理程序：，中断处理程序：l找到访问页在外存的地址；找到访问页在外存的地址；l在内存找一空闲页面；在内存找一空闲页面；l如没有，按淘汰算法淘汰一个；如没有，按淘汰算法淘汰一个；l如需要，将淘汰页面写回外存，修改页表和总页表；如需要，将淘汰页面写

8、回外存，修改页表和总页表；l读入所需页面（切换进程）；读入所需页面（切换进程）；l启动进程，重新执行被中断的指令。启动进程，重新执行被中断的指令。106.5.1.1 基本原理基本原理l页面调度需要执行通道传输操作页面调度需要执行通道传输操作, 时间较长时间较长l被中断进程进入等待状态被中断进程进入等待状态, 处理机转去运行其它处理机转去运行其它进程进程l待待I/O传输完成后硬件发出中断信号，将缺页进传输完成后硬件发出中断信号，将缺页进程唤醒程唤醒l为实现虚拟页式存储管理为实现虚拟页式存储管理, 页表中需要增加如下页表中需要增加如下栏目：栏目：l外存页号外存页号l内外标志内外标志l修改标志等修改

9、标志等 11对页表的改进：对页表的改进：对快表的改进：对快表的改进：逻辑页号逻辑页号 p . . . . . 页架号页架号 外存页号外存页号 内外标识内外标识 访问权限访问权限 修改标志修改标志 f p (0,1) r,w,e (0,1) . . . . . . . 逻辑页号逻辑页号 页架号页架号 访问权限访问权限 修改标志修改标志 p f r,w,e (0,1) . . . 126.5.1.2 内存页面分配策略内存页面分配策略 l平均分配平均分配l如内存如内存128页，进程页，进程25个，每个进程个，每个进程5个页面个页面l按进程长度比例分配按进程长度比例分配l按程序大小比例确定分配内存物理

10、页面个数按程序大小比例确定分配内存物理页面个数l设设si为进程为进程pi逻辑空间页面数逻辑空间页面数, 定义定义: Ssil设设m为物理页面总数为物理页面总数, 分配给进程分配给进程pi的内存物的内存物理页面数理页面数 aisi /(Sm)l需对需对ai进行调整使之不低于程序运行所需的进行调整使之不低于程序运行所需的最少物理页面数并且不高于最少物理页面数并且不高于m136.5.1.2 内存页面分配策略内存页面分配策略l按进程优先级比例分配按进程优先级比例分配l为加速高优先级进程的执行速度为加速高优先级进程的执行速度, 可为其分配可为其分配较多的内存页面较多的内存页面l按进程长度和优先级别比例分

11、配按进程长度和优先级别比例分配l这是方法这是方法2和方法和方法3的结合的结合l方法方法2中的中的si为进程为进程pi逻辑页面数与优先级之逻辑页面数与优先级之和和 146.5.1.3 外存块的分配策略外存块的分配策略 l静态分配静态分配l 外存保持进程的全部页面外存保持进程的全部页面l 优点：速度快优点：速度快-淘汰时不必写回淘汰时不必写回(未修改情况未修改情况)l 缺点：外存浪费缺点：外存浪费l动态分配动态分配l外存仅保持进程不在内存的页面外存仅保持进程不在内存的页面l某一外存页面被调入内存时某一外存页面被调入内存时, 释放所占用的外存页面释放所占用的外存页面l当该页面被淘汰时当该页面被淘汰时

12、, 无论是否被修改无论是否被修改, 必需重新为其必需重新为其申请外存页面申请外存页面, 然后将该页写回外存然后将该页写回外存 l优点：节省外存优点：节省外存l缺点：速度慢缺点：速度慢-淘汰时必须写回淘汰时必须写回156.5.1.4 页面调入时机页面调入时机l有两种方法有两种方法: 请调和预调请调和预调l 请调请调(demand-paging)l当页故障发生时进行调度当页故障发生时进行调度l即当访问某一页面而该页面不在内存时由动态调即当访问某一页面而该页面不在内存时由动态调页系统将其调入内存页系统将其调入内存l预调预调(pre-paging)l 也称先行调度：当页故障发生前进行调度也称先行调度：

13、当页故障发生前进行调度l即当一个页面即将被访问之前由动态调页系统将即当一个页面即将被访问之前由动态调页系统将其调入内存其调入内存l预调必须辅以请调预调必须辅以请调166.5.1.5 置换算法置换算法(Replacement Algorithm)l用于：页淘汰、段淘汰、快表淘汰用于：页淘汰、段淘汰、快表淘汰l当要访问页面不在内存时当要访问页面不在内存时, 需将其调入内需将其调入内存存l如果内存中无空闲页面如果内存中无空闲页面, 需将内存中某一页面需将内存中某一页面移至外存移至外存, 被移出的页面称作被移出的页面称作淘汰页面淘汰页面 l选择被淘汰页面的算法称作选择被淘汰页面的算法称作置换算法置换算

14、法l置换算法的设计即要考虑效果置换算法的设计即要考虑效果, 又要考虑开销又要考虑开销 l页面置换有页面置换有局部与全局局部与全局之分之分l局部置换：在当前缺页进程的页架集中选择淘汰局部置换：在当前缺页进程的页架集中选择淘汰页面页面l全局置换：在内存所有页架集中选择淘汰页面全局置换：在内存所有页架集中选择淘汰页面 17最佳淘汰算法最佳淘汰算法(Optimal，OPT) l淘汰以后不再需要的淘汰以后不再需要的, 或者在最长时间以或者在最长时间以后才会用到的页面后才会用到的页面 l缺点：缺点： 无法准确预期页面无法准确预期页面“将来将来”的访问情的访问情况。况。l优点：效率最高优点：效率最高l有如下

15、页面访问序列有如下页面访问序列 6,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1l内存中为该进程分配内存中为该进程分配3个物理页架个物理页架, 开始时开始时内存页架为空内存页架为空, 缺页故障次数为缺页故障次数为9 18最佳淘汰算法最佳淘汰算法(Optimal，OPT)19先进先出淘汰算法先进先出淘汰算法(First-In First-Out，FIFO) l淘汰最先进入内存的页面淘汰最先进入内存的页面l实现时实现时, 每个页面有一个调入时间每个页面有一个调入时间, 该时间可该时间可在内存中用软件记录在内存中用软件记录, 最好设在寄存器中并由最好设在寄存器中并由硬件

16、记录硬件记录l当内存空间紧张时当内存空间紧张时, 调入时间最早的页面将被调入时间最早的页面将被淘汰淘汰l该算法也可以这样实现该算法也可以这样实现l将所有页面按照进入内存的次序排成一个队将所有页面按照进入内存的次序排成一个队列列l当一个页面由外存调入内存时排入队尾当一个页面由外存调入内存时排入队尾l当需要淘汰时取队头的页面当需要淘汰时取队头的页面20先进先出淘汰算法先进先出淘汰算法(First-In First-Out，FIFO)21先进先出淘汰算法先进先出淘汰算法(First-In First-Out，FIFO)l如：如：1，2，3，4，1，2，5，1，2，3，4，5l内存内存3个物理页面：页

17、故障率个物理页面：页故障率=9/12内存内存4个物理个物理页面：页面：页故障率页故障率=10/12 22使用过最久的先淘汰使用过最久的先淘汰(Least Recently Used，LRU) l淘汰最后一次访问时间距当前时间间隔最淘汰最后一次访问时间距当前时间间隔最长的页面长的页面 23使用过最久的先淘汰使用过最久的先淘汰(Least Recently Used，LRU)lLRU的两个实现方法的两个实现方法:l记时法记时法: l每一页面增设一个每一页面增设一个访问时间记时器访问时间记时器l当一个页面被访问时当一个页面被访问时, 当时的绝对时钟内容被拷贝当时的绝对时钟内容被拷贝到对应的访问时间记

18、时器中到对应的访问时间记时器中l系统记录了内存中所有页面最后一次被访问的时系统记录了内存中所有页面最后一次被访问的时间间l淘汰时淘汰时, 选取访问时间记时器中值最小者所对应的选取访问时间记时器中值最小者所对应的页面页面24使用过最久的先淘汰使用过最久的先淘汰(Least Recently Used，LRU)l栈法栈法: l按照页面最后一次访问的时间次序将页面号依次按照页面最后一次访问的时间次序将页面号依次地排列到栈中地排列到栈中l当一个页面被访问时当一个页面被访问时, 其对应的页面号由栈内取出其对应的页面号由栈内取出送入栈顶送入栈顶l淘汰时淘汰时, 取栈底页面号所对应的页面取栈底页面号所对应的

19、页面l这里的这里的“栈栈”不是通常所定义的不是通常所定义的LIFO栈栈l使用双向链来构造，其链头和链尾各需一个指针使用双向链来构造，其链头和链尾各需一个指针25栈法栈法设有访问序列：设有访问序列： 4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 7, 1, 2 07470417044740174107421074120742107472104172042170426使用过最久的先淘汰使用过最久的先淘汰(Least Recently Used，LRU)lLRU算法的实现开销很大算法的实现开销很大l必须有硬件的支持必须有硬件的支持l完全由软件实现其速度至少会降低完全由软件实现其速度至少

20、会降低10倍倍 27最近不用的先淘汰最近不用的先淘汰(Not Used Recently，NUR) l淘汰最近一段时间内未用过的页面淘汰最近一段时间内未用过的页面l根据程序一般的行为特性根据程序一般的行为特性l一个在最近一段时间内未被用到的页面在以一个在最近一段时间内未被用到的页面在以后也不大可能会被用到后也不大可能会被用到l它们可以被淘汰它们可以被淘汰l这是一种流行的、低开销的、接近于这是一种流行的、低开销的、接近于LRU效效果的淘汰算法果的淘汰算法 28最近不用的先淘汰最近不用的先淘汰(Not Used Recently，NUR)l实现时实现时, 为每一个页面增加两个硬件位为每一个页面增加

21、两个硬件位, 它它们是们是: 引用位引用位 0, 此页未被访问过此页未被访问过 1, 此页曾被访问过此页曾被访问过 修改位修改位 0, 此页未被修改过此页未被修改过 1, 此页曾被修改过此页曾被修改过29最近不用的先淘汰最近不用的先淘汰(Not Used Recently，NUR)l一个页面由外存调入内存时一个页面由外存调入内存时, 其引用位和修改位其引用位和修改位均为均为0l对某页面执行写操作对某页面执行写操作, 其修改位和引用位由硬件其修改位和引用位由硬件置为置为1l对某页面执行读操作对某页面执行读操作, 其引用位由硬件置为其引用位由硬件置为1l每隔固定时间将所有引用位都清每隔固定时间将所

22、有引用位都清0l要淘汰某一页面时要淘汰某一页面时, 按照下面次序选择按照下面次序选择:l(1) 引用位引用位0, 修改位修改位0: 直接淘汰直接淘汰;(2) 引用位引用位0, 修改位修改位1: 淘汰之前写回外存淘汰之前写回外存;(3) 引用位引用位1, 修改位修改位0: 直接淘汰直接淘汰;(4) 引用位引用位1, 修改位修改位1: 淘汰之前写回外存淘汰之前写回外存30最不经常使用者先淘汰最不经常使用者先淘汰(Least Frequently Used，LFU) l淘汰访问次数最少的页面淘汰访问次数最少的页面 l实现时实现时, 为每一个页面设一个访问次数计为每一个页面设一个访问次数计数器数器l当

23、一个页面由外存移到内存时当一个页面由外存移到内存时, 对应计数器清对应计数器清0l当一个页面被访问时当一个页面被访问时, 对应计数器加对应计数器加1l当需要淘汰时当需要淘汰时, 取计数值最小的页面取计数值最小的页面 31最不经常使用者先淘汰最不经常使用者先淘汰(Least Frequently Used，LFU)l算法的依据算法的依据l活动的页面其计数值大活动的页面其计数值大, 应当将其留在内存应当将其留在内存l不足不足l以前曾经多次使用的页面虽目前不用也会留在内以前曾经多次使用的页面虽目前不用也会留在内存存l刚刚移入内存的页面因其访问计数值很小反而会刚刚移入内存的页面因其访问计数值很小反而会

24、被淘汰被淘汰l一种弥补方法是定时将计数值右移一种弥补方法是定时将计数值右移, 形成按时间指形成按时间指数衰减的平均使用计数值数衰减的平均使用计数值32使用最频繁者先淘汰使用最频繁者先淘汰(Most Frequently Used，MFU) l淘汰使用次数最多的淘汰使用次数最多的l认为计数值最小的页面很可能刚刚调入内认为计数值最小的页面很可能刚刚调入内存存, 正待被使用，不应淘汰。正待被使用，不应淘汰。l依据：使用多的可能已经用完了依据：使用多的可能已经用完了lLFU和和MFU都有缺点都有缺点, 而且实现开销较大而且实现开销较大 336.5.1.6 颠簸颠簸(Thrashing)l颠簸又译抖动颠

25、簸又译抖动, 指页面在内存与外存之间指页面在内存与外存之间频繁地换入换出频繁地换入换出l原因原因 l分给进程物理页架过少分给进程物理页架过少 l淘汰算法不合理淘汰算法不合理l程序结构问题：滥用转移指令、分散的全局程序结构问题：滥用转移指令、分散的全局变量都会破坏程序的局部性变量都会破坏程序的局部性, 从而增加页故障从而增加页故障率率, 甚至引起颠簸甚至引起颠簸 346.5.1.6 颠簸颠簸(Thrashing)l处理：处理：l增加分给进程物理页架数增加分给进程物理页架数l改进淘汰算法：改进淘汰算法：l首先可考虑首先可考虑LRU算法算法l如开销过大或硬件支持不够如开销过大或硬件支持不够, 可选择

26、可选择NUR算法算法, 通通常问题可以得到解决常问题可以得到解决 356.5.1.6 颠簸颠簸(Thrashing)l为描述颠簸为描述颠簸, 引入页故障率的概念引入页故障率的概念l设进程访问内存成功的次数为设进程访问内存成功的次数为S, 故障的次数为故障的次数为F,则总访问次数则总访问次数A： ASF， 页故障率页故障率f：fFAl系统用于调度页面所需时间比进程实际运行所系统用于调度页面所需时间比进程实际运行所占用的时间要多占用的时间要多l颠簸是由于页故障率过高的结果颠簸是由于页故障率过高的结果, 它将严重地影它将严重地影响系统的效率，甚至可能使系统全面崩溃响系统的效率，甚至可能使系统全面崩溃

27、366.5.1.6 颠簸颠簸(Thrashing)l思考题：思考题：l在某些虚拟页式存储管理系统中，内存中总在某些虚拟页式存储管理系统中，内存中总保持一个空闲的物理页面，这样做有什么好保持一个空闲的物理页面，这样做有什么好处？处？376.5.1.7 工作集模型工作集模型(working set model)l工作集模型由工作集模型由Denning提出提出l工作集工作集(working set)是进程在一段时间之是进程在一段时间之内活跃地访问页面的集合内活跃地访问页面的集合lDenning认为认为, 为使程序有效地运行为使程序有效地运行, 它的它的工作集页面必须能够放到内存中工作集页面必须能够放

28、到内存中386.5.1.7 工作集模型工作集模型(working set model)l准确地说准确地说, 一进程从时刻一进程从时刻(t-)到时刻到时刻t之间所访之间所访问页面的集合问页面的集合WS(t,)称作该进程的工作集称作该进程的工作集l如图如图 6-41 所示，所示，称作窗口尺寸称作窗口尺寸(windows size)396.5.1.7 工作集模型工作集模型(working set model)l工作集是随时间而变化的工作集是随时间而变化的l下图所示的页面访问轨迹，下图所示的页面访问轨迹，WS(t1,)5,7,1,6,2, WS(t2,)2,3,4WS(t1, )=5,7,1,6,22

29、 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,4t1t2406.5.1.7 工作集模型工作集模型(working set model)l工作集大小与窗口尺寸工作集大小与窗口尺寸密切相关密切相关, 程序大小程序大小 WS416.5.1.7 工作集模型工作集模型(working set model)l工作集模型的精确度与工作集模型的精确度与密切相关密切相关l过小过小, 程序活动页面不能全部装入内存程序活动页面不能全部装入内存, 页故障率高页故障率高l过大过大, 允许同时并发执行进程的个数降低允许同时并发执行

30、进程的个数降低lMadnick和和Donovan建议建议大约为大约为10,000次访问内存次访问内存l实现：页表中增加访问位：实现：页表中增加访问位： l开始时，全部清开始时，全部清0, 访问：置访问：置1,l结束时结束时(新新开始时开始时)访问标志为访问标志为1的，为该的，为该期间工作期间工作集，调整集，调整(增加或减少增加或减少)该进程在内存页面数为该工作该进程在内存页面数为该工作集大小。集大小。426.5.1.8 页故障率反馈模型页故障率反馈模型l工作集模型能够非常成功地指导页面的分工作集模型能够非常成功地指导页面的分配配, 从而防止发生颠簸从而防止发生颠簸l它的实现开销较大它的实现开销

31、较大, 使用存在困难。使用存在困难。l颠簸是由于页故障率高而引起颠簸是由于页故障率高而引起l系统利用页故障率的反馈信息来动态地调系统利用页故障率的反馈信息来动态地调整页面的分配整页面的分配, 这就是页故障率反馈模型这就是页故障率反馈模型的思想的思想436.5.1.8 页故障率反馈模型页故障率反馈模型PFFB(Page Fault Feed Back)页故障率高页故障率高(达到某上界阈值达到某上界阈值)：内存页面少，增加。：内存页面少，增加。页故障率低页故障率低(达到某下界阈值达到某下界阈值)：内存页面多，减少。：内存页面多，减少。446.5.2 虚拟段式存储系统虚拟段式存储系统l6.5.2.1

32、 基本原理基本原理 l6.5.2.2 段的动态连接段的动态连接456.5.2.1 基本原理基本原理l思想与虚拟页式相似思想与虚拟页式相似, 只是将页变化为段只是将页变化为段l进程运行前将主程序段装入内存进程运行前将主程序段装入内存, 其它段其它段装入外存装入外存l运行时所需的段如不在内存运行时所需的段如不在内存, 将其动态调将其动态调入入, 内存没有足够空间采取两种方法内存没有足够空间采取两种方法l紧凑：将内存中所有空闲区合并紧凑：将内存中所有空闲区合并l淘汰：将内存中某段移出至外存淘汰：将内存中某段移出至外存, 段的淘汰可段的淘汰可采用与页式相似的算法采用与页式相似的算法466.5.2.1

33、基本原理基本原理 修改过修改过TF缺段中断缺段中断在外存找到所缺段在外存找到所缺段内存够用内存够用选一段淘汰选一段淘汰写回外存写回外存修改段表修改段表F移入移入修改段表修改段表T476.5.2.1 基本原理基本原理l段表的改进段表的改进 . . . .段号段号 s . 段长段长 内存首址内存首址 外存首址外存首址 权限权限 内外标识内外标识 修改标志修改标志 l b b” rwe (0,1) (0,1) . . . .48 . . . . 段号段号 段长段长 内存首址内存首址 访问权限访问权限 修改标志修改标志 s l b rwe (0,1) . . . .6.5.2.1 基本原理基本原理l快

34、表的改进快表的改进496.5.2.2 段的动态连接段的动态连接(dynamic linking)l动态连接动态连接 vs. 静态连接静态连接l静态连接：运行前连接，由静态连接：运行前连接，由link完成完成l动态连接：运行时连接，由动态连接：运行时连接，由OS完成完成l静态连接的缺点静态连接的缺点l连接时间长；连接时间长；l目标代码长；目标代码长；l连接段可能并不执行连接段可能并不执行(未用到未用到)50动态连接的实现动态连接的实现 l在静态连接中在静态连接中, 程序共有多少个段是确定的程序共有多少个段是确定的, 连连接装配程序为每个段分配一个段号接装配程序为每个段分配一个段号, 即即段名到段

35、段名到段号的转换由连接装配程序完成号的转换由连接装配程序完成l在动态连接中在动态连接中, 一个程序共有多少个段是不定的一个程序共有多少个段是不定的, 段名到段号的转换由操作系统来完成段名到段号的转换由操作系统来完成l由于同一个段只分配一个段号由于同一个段只分配一个段号, 操作系统需为每操作系统需为每一个进程保持一个用于记录当前已连接段的表一个进程保持一个用于记录当前已连接段的表目目l该表称作该表称作段名段名段号对照表段号对照表, 其形式如图其形式如图 644 所示所示51动态连接的实现动态连接的实现段名段名-段号对照表：每进程一个段号对照表：每进程一个段名段名 段号段号sname snum .

36、 .52动态连接的实现动态连接的实现l将一个外段中的符号名转换为对应的段内地址将一个外段中的符号名转换为对应的段内地址, 每个段在编译每个段在编译(汇编汇编)时时, 需生成一个符号表需生成一个符号表, 放在放在一个段的前面一个段的前面, 作为段的一个组成部分作为段的一个组成部分l符号表如图所示符号表如图所示符号名符号名 段内位移段内位移 func 150 . .53动态连接的实现动态连接的实现l一个段由符号表和目标程序一个段由符号表和目标程序(或者数据或者数据)两两部分构成部分构成, 如图所示如图所示段形式：段形式：符号表符号表目标代码目标代码或者数据或者数据54动态连接需要经过的步骤动态连接

37、需要经过的步骤:l编译编译(汇编汇编)时：遇到访问外段指令时：遇到访问外段指令, 采用间采用间接寻址接寻址, 即指向一个间接字，间接字的形即指向一个间接字，间接字的形式如图所示式如图所示 LD1: 未连接未连接0: 已连接已连接符号地址：符号地址：“X|”逻辑地址：逻辑地址：(段号段号,段内地址段内地址)55编译编译(汇编汇编)时时lL=1, 表示尚未连接表示尚未连接, D为符号地址为符号地址l“X|” 表示表示X段段单元单元lL=0, 表示连接完毕表示连接完毕, D为逻辑地址为逻辑地址, 由段号与段内地址构由段号与段内地址构成成l初始时初始时, L均为均为1lL为为1, 表示需要进行动态连接

38、表示需要进行动态连接, 否则为一般的间接指令否则为一般的间接指令LD1: 未连接未连接0: 已连接已连接符号地址：符号地址：“X|”逻辑地址：逻辑地址：(段号段号,段内地址段内地址)56执行时执行时l遇到间址指令且遇到间址指令且L=1时时, 硬件产生连接中硬件产生连接中断断, 由连接中断处理程序进行动态连接由连接中断处理程序进行动态连接, 具具体做法如下体做法如下:la)由由D处取出符号地址中段名部分处取出符号地址中段名部分;lb)由段名查段名由段名查段名段号对照表看该段是否已分段号对照表看该段是否已分配段号配段号, 有两种情形有两种情形:57执行时执行时lc)该段已分配段号该段已分配段号,

39、该段以前曾连接过该段以前曾连接过l将该段号由段名将该段号由段名段号对照表中取出段号对照表中取出l由段号查段表找到该段由段号查段表找到该段l由单元名查该段的符号表从中取出段内地址由单元名查该段的符号表从中取出段内地址l将段号和段内地址送入将段号和段内地址送入D, 0送送L; ld)该段未分配段号该段未分配段号, 说明该段以前未连接过说明该段以前未连接过l将该段由文件系统中调入内存将该段由文件系统中调入内存, 分配一个段号分配一个段号l填写段名填写段名段号对照表段号对照表l转转(b)58实例实例1 汇编前：汇编前：设有两个段设有两个段, 段名分别为段名分别为W和和X指令指令LOAD 1, X|表示

40、：表示：将将X段段单元中的内容取来送入单元中的内容取来送入1号寄存器号寄存器这是一条访问外段的指令这是一条访问外段的指令 59实例实例1 l汇编后：假设汇编后：假设W段已连接并在内存段已连接并在内存, 段号段号为为 2; X段尚未连接段尚未连接, 保存在文件系统中保存在文件系统中, 进程空间各段进程空间各段, 以及各表目如图以及各表目如图 6-49所示所示l符号地址是一个字符串符号地址是一个字符串, 可能很长可能很长, D处存处存放不下放不下, 所以所以D处实际存了一个指向该符号处实际存了一个指向该符号串的首地址串的首地址l7X| 中的数字中的数字7是符号串是符号串X|的长度的长度 6061汇

41、编后连接后汇编后连接后 lW段段: 已连接已连接在内存在内存 X段段: 已连接已连接在内存在内存l进程空间各段进程空间各段, 以及各表形式如图以及各表形式如图 650 所示所示6263实例实例2: .Load 1, X|Load 2, X|.W段X段12345678.Y:Z:64汇编后，连接前：汇编后，连接前：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 .段名段名 段号段号Ma

42、in 0A 1W 2段名段名-段号对照表段号对照表65第一次连接后：第一次连接后：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 366100:Load *1, 2|100;Load *2, 2|150;“7X|”.“7X|”0 3 3000 3 400150:200:250:W段（段号段（段号=2)X段

43、段 300 40012345678300400段表段表 段首址 .段号 0 1 2 3 .段名 段号Main 0A 1W 2段名段名-段号对照表段号对照表X 3第二次连接后：第二次连接后：67动态连接问题动态连接问题l动态连接与共享的矛盾动态连接与共享的矛盾l动态连接：修改连接字（代码）动态连接：修改连接字（代码）l段的共享：要求纯代码（段的共享：要求纯代码（pure code)l解决方法解决方法l共享代码分为共享代码分为“纯段纯段”和和“杂段杂段”l纯段共享，纯段共享，l杂段私用。杂段私用。686.5.3 虚拟段页式存储系统虚拟段页式存储系统l虚拟页式：将存储空间静态地划分为长度虚拟页式：将

44、存储空间静态地划分为长度相同的区域相同的区域, l优点：简化存储分配优点：简化存储分配, 消除消除“碎片碎片”问题问题. l缺点：只提供一维地址缺点：只提供一维地址, 进程空间不能动态扩进程空间不能动态扩充充, 无法实现程序段的动态连接无法实现程序段的动态连接. l页式存储管理也能实现存储的共享和保护页式存储管理也能实现存储的共享和保护l由于以页为基本单位由于以页为基本单位, 页面长度与程序基本单页面长度与程序基本单位长度不等位长度不等, 实现起来比较麻烦实现起来比较麻烦696.5.3 虚拟段页式存储系统虚拟段页式存储系统l虚拟段式：将存储空间动态地划分为长度虚拟段式：将存储空间动态地划分为长

45、度不同的区域不同的区域, 一个区域恰好对应一个程序一个区域恰好对应一个程序单位。单位。l优点：提供二维地址优点：提供二维地址, 方便存储共享和存储保方便存储共享和存储保护，可实现段长度的动态变化护，可实现段长度的动态变化, 以及段间动态以及段间动态连接连接. l 缺点：存储空间的分配和去配比较复杂缺点：存储空间的分配和去配比较复杂, 可可能形成能形成“碎片碎片”706.5.3 虚拟段页式存储系统虚拟段页式存储系统l虚拟段页式考虑：虚拟段页式考虑：l段的动态连接段的动态连接l段的共享段的共享l段长度的动态变化段长度的动态变化l6.5.3.1 基本原理基本原理l6.5.3.2 中断处理中断处理71

46、6.5.3.1 基本原理基本原理l所需表目所需表目l总页表：即位示图，内存和外存各一个总页表：即位示图，内存和外存各一个, 其形其形式与非虚拟存储管理相同式与非虚拟存储管理相同. l段表段表: 每个进程一个每个进程一个, 该表长度动态变化该表长度动态变化, 每连每连接一个新的段时接一个新的段时, 增加一个新的项目增加一个新的项目页表长度页表长度 页表首址页表首址 访问权限访问权限 扩展标志扩展标志 共享段入口共享段入口 段号段号72所需表目所需表目l页表页表: 每个段一个每个段一个, 进程开始运行时只为主进程开始运行时只为主程序段建立一个程序段建立一个, 其它段的页表在段连接其它段的页表在段连

47、接时建立时建立l共享段表共享段表: 整个系统一个整个系统一个, 记录所有共享段记录所有共享段逻辑页号逻辑页号内存页号内存页号 外存页号外存页号 内外标志内外标志 修改标志修改标志 .段名段名 页表长度页表长度 页表首址页表首址 扩充标志扩充标志 共享计数共享计数 73所需表目所需表目l段名段名段号对照表：每个进程一个段号对照表：每个进程一个74私用段私用段共享段共享段共享段表共享段表P1段表段表：P2段表：段表：各表之间联系各表之间联系 75共享段表共享段表P1段表：P2段表： 15 16 17 18 19 20 21 22 23 24 25 . .页表页表页表页表存储空间：存储空间：sisj

48、sk76所需寄存器所需寄存器 l段表首址寄存器段表首址寄存器 b：整个系统一个：整个系统一个, 保存保存正在运行进程段表首址正在运行进程段表首址l段表长度寄存器段表长度寄存器 l：整个系统一个：整个系统一个, 保存正保存正在运行进程段表长度在运行进程段表长度l在进程运行过程中可能动态变化在进程运行过程中可能动态变化l每连接一个新的段时其值加每连接一个新的段时其值加1l快表快表：每个进程一个：每个进程一个段号段号 逻辑页号逻辑页号 物理页号物理页号 访问权限访问权限 修改标志修改标志 77地址映射地址映射 l逻辑地址的形式为逻辑地址的形式为: (段号段号,逻辑页号逻辑页号,页内地址页内地址)(s

49、,p,d)l物理地址的形式为物理地址的形式为: (页架号页架号,页内地址页内地址)(f,d)78由由(s,p)查快表得查快表得f查到查到访问合法访问合法形成物理地址形成物理地址(f,d)是间址是间址有障碍位有障碍位继续继续0 s l-10 p l-1由由(s,b)查段表得查段表得b,l越界中断越界中断越界中断越界中断由由b和和p查页表得查页表得f该页在内存该页在内存缺页中断缺页中断(s,p,f)快表快表越权中断越权中断TFTF连接中断连接中断TFTFTFTFT796.5.3.2 中断处理中断处理 l连接中断：由段名查本进程的段名连接中断：由段名查本进程的段名段号对照表及共享段号对照表及共享段表

50、段表, 分三种情形分三种情形:l所有进程都未连接过（共享段表、段名所有进程都未连接过（共享段表、段名-段号对照表均无）段号对照表均无） 建立页表，由文件全部读入外存建立页表，由文件全部读入外存swap，部分页读入内存，分配，部分页读入内存，分配段号，填段名段号，填段名-段号对照表，如是共享段填共享段表，填段段号对照表，如是共享段填共享段表，填段表表 ，形成逻辑地址。，形成逻辑地址。l其它进程连接过但本进程未连接过其它进程连接过但本进程未连接过(共享段表有共享段表有, 段名段名-段号对照段号对照表无表无) 分配段号，填段名分配段号，填段名-段号对照表，填段表段号对照表，填段表(指向共享段表指向共

51、享段表)，共享，共享记数加记数加1, 形成逻辑地址。形成逻辑地址。l本进程已连接过本进程已连接过(共享段表无共享段表无, 段名段名-段号对照表有段号对照表有),形成逻辑地形成逻辑地址。址。806.5.3.2 中断处理中断处理l缺页中断缺页中断l调入所需页面，更新页表和总页表。调入所需页面，更新页表和总页表。l越界中断越界中断l段号越界：错误处理。段号越界：错误处理。l页号越界：如可扩展，扩展该段页号越界：如可扩展，扩展该段(增加页增加页)，修，修改页表和段表改页表和段表(页表长页表长); 如不可扩展，错误处如不可扩展，错误处理。理。l越权中断越权中断l违反段的访问权限违反段的访问权限, 程序将

52、被中止程序将被中止 81三种虚拟存储系统的优点和缺点三种虚拟存储系统的优点和缺点 826.6 系统举例系统举例lLinux存储管理存储管理lWindows2000/XP存储管理存储管理83Linux存储管理存储管理l页式存储管理不要求一个进程的页面在物页式存储管理不要求一个进程的页面在物理上连续理上连续lDMA传输在没有地址映射条件下进行，跨传输在没有地址映射条件下进行，跨页的页的DMA传输要求页面物理上连续传输要求页面物理上连续l连续物理页面分配的问题是可能产生外碎连续物理页面分配的问题是可能产生外碎片片(external fragmentation)l伙伴算法是针对外碎片问题而提出的一种伙

53、伴算法是针对外碎片问题而提出的一种稳定、高效的分配策略稳定、高效的分配策略 84Linux存储管理存储管理l伙伴堆伙伴堆(buddy heap)内存分配算法内存分配算法l将所有空闲页面分为将所有空闲页面分为10个块组，块组编号为个块组，块组编号为i (i=09)l块组块组i中记载长度为中记载长度为2i个页面连续区域个页面连续区域l第第1组中块的大小均为组中块的大小均为20(1页页)，第，第2组中块的大小组中块的大小均为均为21(2页页),第第10组中块的大小均为组中块的大小均为29(512页页). l同组中所有块以链表形式组织同组中所有块以链表形式组织85l申请长度为申请长度为128，在第，在

54、第8组中取一块。组中取一块。l若第若第8组已空，在第组已空，在第9组取一块，分配其中的组取一块，分配其中的128页，并页，并将剩余的将剩余的128页记入第页记入第8组。组。l若第若第9组也空，在第组也空，在第10组取一块，进行两次分割，分配组取一块，进行两次分割，分配128页，剩余的页，剩余的128页和页和256页分别记入第页分别记入第8组和第组和第9组组l释放是上述操作的逆过程，两个块为伙伴的条件释放是上述操作的逆过程，两个块为伙伴的条件是是:l两个块的大小相同，如两个块的大小相同，如b个页面；个页面；l两个块的物理地址连续；两个块的物理地址连续；l位于后面块的最后页面编号必须是位于后面块的

55、最后页面编号必须是2b的整数倍的整数倍8610(29)9(28) 8(27)4(23)3(22)2(21)1(20)Linux存储管理存储管理87buddy heap)内存分配算法内存分配算法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

56、算法记载可用存储区）算法记载可用存储区） 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

57、 by allocating an existing small free region, then a larger free region will be subdivided into two partners to satisfy the request.（小区域（小区域不能满足时，分割大区域）不能满足时，分割大区域）Linux存储管理存储管理l虚拟存储管理虚拟存储管理 l页表分为三级页表分为三级l无预调页功能无预调页功能l未采用工作集模型未采用工作集模型l系统守护进程系统守护进程kswapd每秒运行一次，动态调每秒运行一次，动态调整页面分配，保持内存有一定数量的空闲页整页面分配，保持内存有一定数量的空闲页面面lBdflush进程周期性醒来并刷新进程周期性醒来并刷新“脏页脏页” 906.6.2 Windows2000/XP存储管理存储管理 lWin32提供一组与存储管理相关的调用，提供一组与存储管理相关的调用，核心中有核心中有6个专门负责存储管理的线程个专门负责存储管理的线程l6.6.2.1 进程地址空间进程地址空间l6.6.2.2 存储管理方式存储管理方