操作系统第9章课件.ppt

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

17、 time per process) 4 frames FIFO Replacement Beladys Anomaly more frames less page faults(not always true),38,一个采用FIFO置换引用串的页错误曲线,39,FIFO是最简单的，但其性能并总是很好，所替代的也可能是很久以前使用的，现已不在使用的初始化模块，也可能包含一个以前初始化的并且不断使用的常用变量 FIFO算法有Belady异常现象 对有的置换算法，页错误率可能会随着所分配的帧数的增加而增加 原期望为进程增加内存会改善其性能，但看来这种推测并不总是正确的,40,最优页置换（Opti

18、mal Algorithm）,4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5,基本思想 最优页置换算法是所有算法中产生也错误率最低的，且绝对没有Belady异常的问题 它置换那些在最长时间内不会被使用的页,41,Optimal Page Replacement,7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1,42,然而，最优页置换算法难于实现，因为需要引用串的未来知识,43,LRU页置换,使用离过去最近作为不远将来的近似，置换最长时间没有使用的页。,7 0 1 2 0

19、3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,44,LRU实现,计数器 为每个页表项关联一个使用时间域，并为CPU增加一个逻辑时钟或计数器。对每次内存引用，计数器都会增加。每次内存引用时，时钟寄存器的内容会复制到相应页所对应页表项的使用时间域内。置换具有最小时间的页。 页码堆栈 每次引用一个页，该页就从堆栈中删除并放在顶部。这样，堆栈顶部总是最近使用的页，堆栈底部总是LRU页。,45,用堆栈来记录最近使用的页,46,很少有计算机系统能提供足够的硬件来支持真正LRU页置换算法。然而很多系统都通过引用位来提供一定的支持 页表中的每项都关联着一个引用位，每当引用一个页时，相应页的引用位

20、就被硬件置位(为1) 通过检查引用位，能确定那些页使用过哪些页未使用过 附加引用位算法 二次机会算法 增强型二次机会算法,LRU近似页置换算法,47,附加引用位算法,附加引用位算法 为位于内存中的每个表中的页保留一个8位的字节 在规定的时间间隔内，OS把每个页的引用位转移到8位的高位，而将其他位向右移 这些8位移位寄存器包含该页在最近8个周期内的使用情况 0000000表示该页在8个周期内没有使用过 11111111表示该页在每个周期内都至少使用过一次 11000100要比01110111的页更为最近使用 如果将这8位字节作为无符号整数，那么具有最小值的页尾LRU页 这些数字并以唯一，可以置换

21、所有具有最小值的页或采用FIFO来选择置换,48,LRU近似页置换算法,二次机会算法 当要选择一个页时，检查其引用位。如果其值为0那么就直接置换该页。如果该引用位为1,那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。,49,二次机会（时钟）页置换算法,50,增强型二次机会算法,增强型二次机会算法 通过将引用位和修改位作为一个有序对来考虑，可得到四种可能类型 1类 (0,0)最近没有使用且也没有修改，用于置换的最佳页 2类 (0,1)最近没有使用但修改过，不是很好，因为在置换之前需要将页写出到磁盘 3类 (1,0)最近使用过但没有

22、修改，可能很快又要被使用 4类 (1,1)最近使用过且修改过，它可能很快又要被使用，且置换之前需要将页写出到磁盘 当页需要置换时，每个页都属于这四种类型之一。 可以检查页属于哪个类型，置换在最低非空类型中所碰到的页 在找到要置换页之前，可能要多次搜索整个循环队列,51,基于计数的页置换算法,为每个页保留一个用于记录其引用次数的计数器。 最不经常使用页置换算法（least frequently used page replacement algorithm, LFU） 最常使用页置换算法（most frequently used page-replacement algorithm, MFU）,

23、52,7. 页缓冲算法,除了特定页置换算法外，还经常采用其他措施 系统通常保留一个空闲帧缓冲池 当出现页错误时，会像以前一样选择一个牺牲帧。然而，在牺牲帧写出之前，所需要的页就从缓冲池中读到空闲内存。这种方法运行进程尽可能快地重启，而无需等待牺牲帧的写出。当牺牲帧在以后写出时，它再加入到空闲池。,53,维护一个已修改页的列表 每当调页设备空闲时，就选择一个修改页以写到磁盘上，接着重新设置其修改位。增加了选择置换时干净页的概率。 保留一个空闲帧池，但要记住哪些页在哪些帧中。 由于当帧写到磁盘上时其内容并没有修改，所以在该帧被重用之前如果需要使用原来的页，那么原来的页可直接从空闲池中取出以直接使用

24、。这时并不需要I/O.,7. 页缓冲算法,54,9.5 帧分配,如何在各进程之间分配一定的空闲内存？ 每个进程需要最低数量的页由体系结构决定 例如：IBM 370至少需要6页用来处理SS MOVE指令 指令是6字节指令，可能跨越2页 要移动的字符的块和要移动到目的的区域也可能都要跨页。 两种主要的分配方案 平均分配 比例分配 优先级分配,55,平均分配：如100帧，5个进程，则给每个进程20帧 比例分配：根据进程的大小按比例分配,56,平均及比例分配特点 每个进程所分配的数量会随着多道程序的级别而有所变化。多道程序程度增加，那么每个进程会失去一些帧以提供给新来进程使用。反之，原来分配给离开进程

25、的帧可以分配给剩余进程 高优先级进程与低优先级进程在这种分配方式下没有任何区别 优先级分配 按优先级比例而非进程的大小来分配 如果进程 Pi 产生了一个页错误，那么 从自身的帧中选择用于替换 从比自身优先级低的进程中选取帧用于替换,57,全局分配与局部分配,全局置换 允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程；一个进程可以从另一个进程中取帧。 局部置换 要求每个进程仅从其自己的分配帧中进行选择,58,9.6 系统颠簸,如果一个进程没有足够的页，那么页错误率就会非常高。这会导致 CPU使用率低 这时OS认为必须提高多道程序的程度 因此，新的进程会加入到系统中来。 颠

26、簸：进程一直忙于将页面换进换出。,59,颠簸,60,如何防止颠簸？,为了防止颠簸，必须提供进程所需的足够多的帧。但是如何知道进程“需要”多少帧呢？ 工作集合策略检查进程真正需要多少帧。这种方法定义了进程执行的局部模型（locality model）。 当进程执行时，它从一个局部移向另一个局部。局部是一个经常使用页的集合。一个程序通常由多个不同局部组成，它们可能重叠。,61,内存引用模式中的局部性,62,工作集模型,工作集窗口：最近个页面引用 这最近个引用的页集合称为工作集合 if too small will not encompass entire locality. if too larg

27、e will encompass several localities. if = will encompass entire program. WSSi (进程Pi的工作集) = 最近所引用的所有页面的总数（不同时刻值不同） D WSSi 表示总的帧需求量 如果 D 大于可用帧数量，那么有的进程就得不到足够帧，从而会出现颠簸 这时可以悬挂某些进程，以消除颠簸现象,63,工作集模型,64,页错误频率,建立可接受的页错误率 如果错误率太低，则进程可能有太多的帧，因此应丢弃一些帧 如果错误率太高，则为进程分配更多帧,65,思考题,考虑一个请求调页系统，它采用全局置换策略和平均分配内存块的算法。如果

28、在系统中测得如下的CPU和对换空间利用率，请问能否用增加多道程序的度数来增加CPU的利用率？为什么？ (1) CPU利用率为13%，盘利用率为97%； (2) CPU利用率为87%，盘利用率为3%； (3) CPU利用率为13%，盘利用率为3%；,66,9.7 内存映射文件,内存映射文件I/O将文件I/O作为普通内存访问，它允许一部分虚拟内存与文件逻辑相关联 开始的文件访问按普通请求页面调度来进行，会产生页面错误。这样，一页大小的部分文件从文件系统读入物理页，以后文件的读写就按通常的内存访问来处理。 通过内存的文件操作而不是使用系统调用read和write，简化了文件访问和使用。 多个进程可以允许将同一文件映射到各自的虚拟内存中，以允许数据共享。,67,内存映射文件,68,Solaris系统中不管文件是否说明为内存映射，都选择对文件进行内存映射 如果一个文件说明为内存映射，那么Solaris将文件映射到进程的地址空间中 如果一个文件采用普通系统调用如open()、read等来打开和