《操作系统第9章课件》由会员分享，可在线阅读，更多相关《操作系统第9章课件（74页珍藏版）》请在金锄头文库上搜索。
1、操作系统概念,第九章：虚拟内存,2,本章主要内容,背景 按需调页 写时复制 页面置换 帧分配 系统颠簸 内存映射文件 其他考虑,3,9.1 背景,常规存储方器管理方式的特征： 一次性 驻留性,4,程序执行的局部性原理虚拟存储的理论依据,程序执行时，除了少部分的转移和过程调用外，在大多数情况下仍是顺序执行的 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但研究发现，过程调用的深度在大多数情况下都不超过5。即程序将会在一段时间内局限在这些过程的范围内运行。 程序中存在很多循环结构，这些虽然只是少数指令构成，但是他们将多次执行。 程序中还包括许多对数据结构的处理，比如数组，他们往往都局限
2、于很小的范围内,5,局限性又表现在下述两个方面,时间局限性 如果程序中某条指令一旦执行，则不久后该指令可能再次执行；如果某数据被访问过，则不久后该数据可能再次被访问 产生时间局限性的典型原因是由于在程序中存在着大量的循环操作 空间局限性 一个程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围之内 典型原因就是程序的顺序执行,6,在许多情况下，（加载）整个程序是没必要的 允许程序部分加载即可运行会有许多好处： A program would no longer be constrained by the amount of phy
3、sical memory. More programs could be run at the same time, with a corresponding increase in CPU utilization and throughput. Less I/O would be needed to load or swap each user program into memory, so each user program would run faster.,7,虚拟存储用户逻辑存储与物理存储分离 仅部分程序必须在内存，以使其运行 从而逻辑地址空间远大于物理地址空间 使得编程更加容易，程
4、序员只需关心所要解决的问题 采用虚拟内存的系统几乎用不到覆盖 允许更有效的进程创建(写时拷贝) 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统,8,虚拟内存大于物理内存的示意图,9,虚拟存储可通过以下方式实现: Demand paging 请求分页管理方式 Demand segmentation 请求分段管理方式式 但是，段的替换算法比页替换算法复杂，因为段的大小不同 paged segmentation 请求段页式管理方式,10,其逻辑容量是由内存容量和外存容量之和所决定的，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储器是
5、一个性能非常优越的存储管理技术，故被广泛应用于大、中、小型机器和微型机中 虚拟存储器的实现都毫无例外地建立在离散分配的存储管理方式的基础上 虚拟存储器的特征：多次性、对换性、虚拟性,11,9.2 按需调页,一个执行程序如何从磁盘载入内存？ 将整个程序载入内存 在需要时调入相应的页按需调页,12,按需调页系统类似于分页系统对换 But we use a lazy swapper-pager Swapper(交换程序) vs Pager(调页程序) A pager never swaps a page into memory unless that page will be needed. A s
6、wapper manipulates entire processes.,13,分页的内存与邻接的磁盘空间之间的传递,14,9.2.1 基本概念,只在页面需要时，才把它们载入内存 需要更少的输入输出 更小的内存 更快的响应 更多的用户,15,有效-无效位,页表中的每一条目与一有效无效位与之关联。（1表示该页在内存中，0表示不在内存） 有效无效位初始为0 当进程试图访问那些尚未调入到内存的页时，对标记为无效的页面的访问会产生页错误陷阱（page-fault trap）,16,当有些页不在内存中时的页表,17,页错误的处理,检查进程的页表，以确定该引用是合法还是非法的地址访问。 如果引用非法，那么
7、终止进程。如果引用有效但是尚未调入页面，那么现在应调入。 找到一个空闲帧（从空闲帧链表中取一个） 调度一个磁盘操作，以便将所需要的页调入刚分配的帧 当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中。 重新开始因非法地址陷阱而中断的指令。进程现在能访问所需的页，就好像它似乎总在内存中。,18,处理页错误的步骤,19,纯粹按需调页 Never bring a page into memory until it is required. Start executing a process with no pages in memory 理论上，某些程序每次执行指令可能访问多个新内存页
8、 one page for the instruction and many for data possibly causing multiple page faults per instruction. Fortunately, programs tend to have locality of reference（引用的局部性）,20,请求页式调度的性能,设P为页错误的概率（0P 1） 如果P等于0，则不存在页错误 如果等于，则每次访问都存在页错误 有效访问时间 （1P） 内存访问时间 + P页错误时间 设内存访问时间为100ns，平均错误页处理为25ms，则EAT为 EAT = (1-P
9、) 100ns + P 25ms = 100 + 24999900P ns,21,Page-fault service time,A page fault caused the following sequence to occur: Trap to the OS Save the user registers and process state Determine that the interrupt was a page fault Check that the page reference was legal and determine the location of the page
10、on the disk Issue a read from the disk to free frame While waiting, allocate the CPU to some other user Receive an interrupt from the disk I/O (I/O completed) Save the registers and process state for the other user Determine that the interrupt was from the disk Correct the page table and other table
11、s to show that the desired page is now in memory Wait for the CPU to be allocated to this process again Restore the user registers, process state, and new page table, and then resume the interrupted instruction,22,三个主要的页错误处理时间,处理页错误中断 读入页 重新启动进程,23,Example Memory access time = 100 nanoseconds An ave
12、rage page-fault service time=25 milliseconds EAT(in nanoseconds) = (1 p) x ma + p x Page-fault service time = (1 p) x 100 + p x 25,000,000 =100+24,999,900 x p The EAT is directly proportional to the page-fault rate. If we want less than 10-percent degradation,we need 110 100+25,000,000 x p 10 25,000
13、,000 x p p 0.0000004 请求页面调度中，降低页错误率是非常重要的 请求页面调度的另一个重要方面是交换空间的处理和使用,24,9.3 写时复制(Copy on write),写时拷贝允许父进程和子进程开始时共享同一页面。 这些页面标记为写时复制，即如果任何一个进程需要对页进行写操作，那么就创建一个共享页的拷贝。 采用写时拷贝技术，很显然只有被进程所修改的页才会复制，因此创建进程更有效率。 写时拷贝时所需的空闲页来自一个空闲缓冲池。该缓冲池中的页在分配之前先填零，以清除以前的页内容。,25,26,9.4 页面置换,给原有的页错误服务程序增加页置换，可以防止内存的过度分配（over
14、-allocating）。,27,需要页置换的情况,28,9.4.1 页置换的基本方法,查找所需页在磁盘上的位置 查找一空闲帧 如果有空闲帧，那么就使用它 如果没有空闲帧，那么就使用页置换算法以选择一个“牺牲”帧（victim frame）。 将“牺牲”帧的内容写到磁盘上；改变页表和帧表。 将所需页读入（新）空闲帧；改变页表和帧表 重启用户进程。,29,页置换,30,如果没有空闲帧，那么需要两个页传输，将页错误处理时间加倍，相应地增加了有效访问时间 使用修改位（脏位）来降低页传输的开销 只有被修改过的页才写回至磁盘。 页置换分开了逻辑内存与物理内存 采用这种机制，小的物理内存能为程序员提供巨大
15、的虚拟内存。,31,实现按需调页需要解决的问题,帧分配算法 决定为每个进程各分配多少帧 页置换算法 需要页置换时，选择要置换的帧,32,页置换算法,追求最低的页错误率 通过运行一特殊字符串（引用串，reference string）来检验算法，计算其页错误率 针对某一特定引用串和页转换算法，为了确定页错误的数量，还需要知道可用帧的数量。 为了讨论页转换算法，将采用以下引用串，而可用帧的数量为3 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1,33,页错误与帧数量关系图,34,页置换算法,FIFO页置换 最优置换 LRU页置换
16、 近似LRU页置换 基于计数的页置换,35,FIFO页置换,基本思想 最简单的页置换算法。 FIFO为每个页记录着进入内存的时间，当必须置换一页时，将选择最旧的页 并不需要记录调入一页的确切时间，可以创建一个FIFO对列来管理内存中的所有页,36,FIFO Page Replacement,7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1,37,Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process) 4 frames FIFO Replacement Beladys Anomaly more frames less page faults(not always true),38,一个采用FIFO置换引用串的页错误曲线,39,FIFO是最简单的，但其性能并总是很好，所替代的也可能是
