《西安交通大学操作系统原理幻灯片第九章》由会员分享，可在线阅读，更多相关《西安交通大学操作系统原理幻灯片第九章（83页珍藏版）》请在金锄头文库上搜索。
1、Chapter 9 Virtual Memory,Background（背景） Demand Paging（请求页式） Performance of Demand Paging（请求页式的性能） Page Replacement（页置换） Page-Replacement Algorithms（页置换算法） Allocation of Frames （页框的分配） Thrashing（颠簸） Other Considerations（其他考虑）,9.1 Background,为了在内存空间运行超过内存总容量的大作业 或者同时运行大量作业 解决的方法是从逻辑上扩充内存容量 这就是虚拟存储技术所要
2、解决的主要问题,9.1 Background,实现虚拟存储器要解决: 程序部分运行可以吗? 发现程序不在内存时,如何将其装入后继续运行? 内存无空间时怎么办?,9.1 Background,Virtual memory is a technique that allows the execution of processes that may not be completely in memory.（虚拟内存是一种允许进程部分装入内存就可以执行的技术） principle of locality局部性原理 : 时间局部性，空间局部性 Only part of the program needs
3、 to be in memory for execution （只有运行的部分程序需要在内存中）.,程序的局部性原理,在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。 程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。 子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。 程序中存在许多循环结构，循环体中的指令被多次执行。 程序中还包括许多对数据结构的处理，如对连续的存储空间数组的访问，往往局限于很小的范围内。,时间局部性： 由于程序中存在着大量的循环操作 某条指令一旦执行，则不久该
4、指令可能再次被执行； 某个存储单元被访问，则不久该存储单元可能再次被访问。 空间局部性： 由于程序的顺序执行 一旦程序访问了某个存储单元，则其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内,局部性表现,9.1 Background,Logical address space can therefore be much larger than physical address space（逻辑地址空间能够比物理地址空间大）. Need to allow pages to be swapped in and out（必须允许页面能够被换入和换出）.,Vir
5、tual Memory That is Larger Than Physical Memory,9.1 Background,Virtual memory can be implemented via（虚拟内存能够通过以下方法来实现）: Demand paging （请求页式） Demand segmentation（请求段式）,虚拟存储器的特征,离散性:在内存分配时采用离散的分配方式，是虚拟存储器的最基本的特征。 多次性:一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。是虚拟存储器最重要的特征。 对换性:作业运行过程中信息在
6、内存和外存的对换区之间换进、换出。 虚拟性:从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。,在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储系统 需解决: 取页-将哪部分装入内存 置页-将调入的页放在什么地方 淘汰-内存不足时，将哪些页换出内存,9.2 Demand Paging,9.2 Demand Paging,Bring a page into memory only when it is needed（只有在一个页需要的时候才把它装入内存）. Less I/O needed（需要很少的I/O） Less memory needed （需要很少的内存
7、） Faster response（快速响应） More users（多用户） Hardware Support invalid reference（无效的访问） abort（中止） not-in-memory（不在内存） bring to memory（换入内存）,9.2.1 Page table for demand paging,在分页的页表机制上形成 增加若干信息项，供程序(数据)在换进、换出时参考,状态位（存在位P）：指示该页是否已调入内存。 访问字段A：记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。 修改位M：表示该页在调入内存后是
8、否被修改过。 外存地址：指出该页在外存上的地址，供调入该页时使用。,9.2.1 Page table for demand paging,9.2.2 Page fault,每当所要访问的页面不在内存时，便产生一缺页中断(page fault)，请求OS将所缺页调入内存。 与一般中断的主要区别在于： 缺页中断机构在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。 缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。 一条指令在执行期间，可能产生多次缺页中断。,9.2.3 Address translation,在分页系统地址变换机构的
9、基础上，增加了: 产生和处理缺页中断 页面置换功能等,Steps in Handling a Page Fault,Steps in handling a page fault,查找页表来确定此次地址访问是否合法 如果不合法,则中止该进程; 否则如果是发生了缺页,则需要将其调入内存 找到一个空闲物理块 启动磁盘,把该页读入内存 读磁盘结束后,修改页表以指出该页已在内存中 重新开始执行刚才发生缺页中断的指令,这时它可以访问刚才调入的页,What happens if there is no free frame?,Page replacement find some page in memory
10、, but not really in use, swap it out（页置换找到内存中并没有使用的某个页，换出）. Algorithm（算法） Performance（性能） want an algorithm which will result in minimum number of page faults（找出一个导致最小缺页数的算法）.,Need For Page Replacement,Basic Page Replacement,Find the location of the desired page on disk Find a free frame: - If there
11、 is a free frame, use it - If there is no free frame, use a page replacement algorithm to select a victim frame Bring the desired page into the (newly) free frame; update the page and frame tables,Page Replacement,页面调入策略,为能使进程运行，事先需将一部分要执行的程序和数据调入内存 调入页面的时机 预调页策略： 主动的页面调入策略，即把那些预计很快会被访问的程序或数据所在的页面，预
12、先调入内存。 预测的准确率不高（50%），主要用于进程的首次调入。也有的系统将预调页策略用于请求调页,页面调入策略(续),请求调页策略： 当进程在运行中发生缺页时，由系统将缺页调入内存。 目前虚拟存储器系统大多采用此策略。 在调页时须花费较大的系统开销，如需频繁启动磁盘I/O。,页面调入策略(续),从何处调入页面 在虚拟存储系统中，外存（硬盘）被分成两部分:文件区和对换区。 对换区（连续分配）的磁盘I/O速度比文件区（离散分配）要高。,页面调入策略(续),UNIX系统: 对于从未运行过的页面，都从硬盘文件区(可执行文件)调入 对于被换出的页面，从对换区调入； 对于共享页面，该页面可能已由其它进
13、程调入内存，此时就无须再从对换区调入。 每个作业有一个页表,还有一个与之对应的磁盘描述项:,9.2.4 Performance of Demand Paging,发生缺页时会导致以下步骤的发生: 陷入OS 保存该用户寄存器和进程状态 确定该中断是一个缺页中断 检查该页面引用是合法的并确定该页在磁盘上的位置 将该页从磁盘读入一个空闲物理块: 在磁盘等待队列中等待直到该请求被处理 等待设备寻道延迟 将该块从磁盘传送至内存 为了提高CPU利用率，将CPU分派给其他进程使用,9.2.4 Performance of Demand Paging (Cont.),磁盘I/O完成，产生中断 保存正在执行进程
14、的现场信息（如果第6步执行了） 确定中断来自于磁盘 修改页表以示所缺的页已进入内存 等待CPU再次分派给这个进程 恢复该进程的现场信息，包括寄存器、进程状态、页表等，恢复执行,9.2.4 Performance of Demand Paging (Cont.),以上步骤并不是在任何情况下都会发生的 这里主要的动作是： 处理缺页中断 从磁盘读入所需的页 重新开始被中断的进程 其中最大的一部分时间开销为从磁盘读入所需的页,缺页率,假定作业Ji共有m页，系统分配给它的主存块为n块，这里mn。 如果作业Ji执行过程中总的内存访问次数为A, 成功访问的次数为S，不成功的访问次数为F(产生缺页中断的次数)
15、,则: A=S+F 缺页率: f=F/A,9.2.4 Performance of Demand Paging,Page Fault Rate 0 p 1.0（缺页率0 p 1.0） if p = 0 no page faults （如果p = 0 ，没有缺页） if p = 1, every reference is a fault（每次访问都缺页） Effective Access Time (EAT)（有效存取时间） EAT = (1 p) x memory access + p (page fault overhead + swap page out + swap page in +
16、restart overhead),9.2.5 Page-Replacement Algorithms,在进程运行过程中，如果发生缺页,而内存中又无空闲块时，怎么办? 将内存中的某一页换到磁盘的对换区 将哪个页面调出? 根据页面置换算法来确定,9.2.5 Page-Replacement Algorithms,置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生“抖动”（Thrashing)。 抖动:刚被换出的页很快又被访问，需重新调入，导致系统频繁地交换页面，以致大部分CPU时间花费在完成页面置换的工作上。,9.2.5 Page-Replacement Algorithms,Goal: Want lowest page-fault rate Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page fau
