吉林大学操作系统课件 第六章 存储管理2讲解.ppt

6.4 外存资源管理 外存空间划分 静态等长，2i, 称为一块(block)，块是外存分配的基本单位，也是IO传输的基本单位。 外存空间分配 空闲块链(慢) 空闲块表(UNIX) 字位映像图 进程与外存对应关系 界地址 每进程占一组外存连续块； 每进程占二组外存连续块（双对界）。 页式 内存一页，外存一块。 段式 每段占外存若干连续块。 段页式 内存一页，外存一块。 6.5 虚拟存储系统 无虚拟问题 不能运行比内存大的程序； 进程全部装入内存，浪费空间（进程活动具有局部性)。 单控制流的进程需要较少部分在内存； 多控制流的进程需要较多部分在内存。 虚拟存储 进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。 6.5.1 虚拟页式存储系统 基本原理 进程运行前： 全部装入外存，部分装入内存。 进程运行时： 访问页不在内存，发生缺页中断，中断处理程序： 找到访问页在外存的地址； 在内存找一空闲页面； 如没有，按淘汰算法淘汰一个； 如需要，将淘汰页面写回外存，修改页表和总页表； 读入所需页面（切换进程）； 重新启动中断指令。 6.5.1 虚拟页式存储管理(Cont.) 6.5.1.5 置换算法(replacement algorithm) FIFO淘汰算法(belady异常) LRU算法例子 12/20=60% 7. 二次机会(second chance) 淘汰装入最久且最近未被访问的页面。 实现时：采用拉链数据结构。 8. 时钟算法(clock algorithm) 将页面组织成环形，有一个指针指向当前位置。每次需要淘汰页面时，从指针所指的页面开始检查。如果当前页面的访问位为0，即从上次检测到目前，该页没有访问过，则将该页替换。如果当前页面的访问位为1，则将其清0，并顺时针移动指针到下一个位置。重复上述步骤直至找到一个访问位为0的页面。 可以看出，时钟算法与二次机会算法的淘汰效果是基本相同的，差别在于二者所采用的数据结构不同，二次机会使用的是链表，需要额外存储空间，且摘链入链速度很慢。而时钟算法可直接利用页表中的引用位，外加一个指针，速度快且节省空间。 时钟算法 时钟算法 时钟算法 改进的时钟算法 考虑修改标志m r=0, m=0：最佳淘汰页面 r=0, m=1：淘汰前回写 r=1, m=0：不淘汰 r=1, m=1：不淘汰 改进的时钟算法 步骤1： 由指针当前位置开始扫描，选择最佳淘汰页面，不改变引用位，将第一个遇到的r=0且m=0的页面作为淘汰页面； 步骤2： 如步骤1失败，再次从原位置开始，找r=0且m=1的页面，将第一个满足上述要求的页面作为淘汰页面，同时将扫描过页面的r位清0； 步骤3： 若步骤2失败，指针再次回到原位置，重新执行步骤1。若还失败再次执行步骤2，此时定能找到。 2010年考研试题 某虚拟页式系统，进程空间和内存空间都是64k，页长1K，某进程6个页，内存分配4个页框，采用局部置换，280时刻页表和Clock数据结构如下： 2010年考研试题 (1)280时刻访问13B7H，逻辑页号是多少？ (2)采用FIFO置换算法，物理页框号是多少？物理地址是多少？ (3)采用CLOCK置换算法，页框号是多少？物理地址是多少？ 2010年考研试题 （1）逻辑地址13B7H化为二进制数为0001001110110111，其中后10位为页内地址，前6位为逻辑页号，即逻辑页号为4。 （2）4号页不在内存，发生缺页中断，按FIFO置换算法，应置换第5页，所得页框号3，形成物理地址0000111110110111，划成16进制为0FB7H。 （3）采用CLOCK置换算法，淘汰第0页，得页框5，形成物理地址为0001011110110111，划成16进制为17B7H。 6.5.1.7 工作集模型(working set model) 6.5.1.8 页故障率反馈模型 6.5.2 虚拟段式存储系统 进程运行前，全部装入外存，部分装入内存，访问段不再内存时，发生缺段中断。 6.5.2.2 段的动态连接(dynamic linking) 动态连接 vs. 静态连接 静态连接：运行前连接，由link完成； 动态连接：运行时连接，由OS完成. 静态连接的缺点 连接时间长； 目标代码长； 连接段可能并不执行(未用到)。 动态连接问题 动态连接与共享的矛盾 动态连接：修改连接字（代码） 段的共享：要求纯代码（pure code) 解决方法 共享代码分为“纯段”和“杂段” 纯段共享， 杂段私用。 6.5.3 虚拟段页式存储系统 考虑 段的动态连接 段的共享 段长度的动态变化 6.6 系统举例 Linux存储管理 Windows2000/XP存储管理 6.6.1 Linux存储管理 Pa