《操作系统第9章ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统第9章ppt课件.ppt（74页珍藏版）》请在三一办公上搜索。
1、操作系统概念,第九章：虚拟内存,2,本章主要内容,背景按需调页写时复制页面置换帧分配系统颠簸内存映射文件其他考虑,3,9.1 背景,常规存储方器管理方式的特征：一次性驻留性,4,程序执行的局部性原理虚拟存储的理论依据,程序执行时，除了少部分的转移和过程调用外，在大多数情况下仍是顺序执行的过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但研究发现，过程调用的深度在大多数情况下都不超过5。即程序将会在一段时间内局限在这些过程的范围内运行。程序中存在很多循环结构，这些虽然只是少数指令构成，但是他们将多次执行。程序中还包括许多对数据结构的处理，比如数组，他们往往都局限于很小的范围内,5,局限
2、性又表现在下述两个方面,时间局限性如果程序中某条指令一旦执行，则不久后该指令可能再次执行；如果某数据被访问过，则不久后该数据可能再次被访问产生时间局限性的典型原因是由于在程序中存在着大量的循环操作空间局限性一个程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围之内典型原因就是程序的顺序执行,6,在许多情况下，（加载）整个程序是没必要的允许程序部分加载即可运行会有许多好处：A program would no longer be constrained by the amount of physical memory.More p
3、rograms 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-pagerSwapper(交换程序)vs Pager(调页程序)A pager never swaps a page into memory unless that page will be needed.A swapper manipulates entire processes.,1
6、3,分页的内存与邻接的磁盘空间之间的传递,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理论上，某些程序每次执行指令可能访问多个新内存页one page for the instruction and many for datapossib
8、ly 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)100ns+P 25ms=100+24999900P ns,21,Page-fault service time,A page fa
9、ult caused the following sequence to occur:Trap to the OSSave the user registers and process stateDetermine that the interrupt was a page faultCheck that the page reference was legal and determine the location of the page on the diskIssue a read from the disk to free frameWhile waiting,allocate the
10、CPU to some other userReceive an interrupt from the disk I/O(I/O completed)Save the registers and process state for the other userDetermine that the interrupt was from the diskCorrect the page table and other tables to show that the desired page is now in memoryWait for the CPU to be allocated to th
11、is process againRestore the user registers,process state,and new page table,and then resume the interrupted instruction,22,三个主要的页错误处理时间,处理页错误中断读入页重新启动进程,23,ExampleMemory access time=100 nanosecondsAn average page-fault service time=25 millisecondsEAT(in nanoseconds)=(1 p)x ma+p x Page-fault service
12、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,000 x p p 0.0000004请求页面调度中，降低页错误率是非常重要的请求页面调度的另一个重要方面是交换空间的处理和使用,24,9.3 写时复制(Copy on write),写时拷贝允许父进程和子进程开始时共
13、享同一页面。这些页面标记为写时复制，即如果任何一个进程需要对页进行写操作，那么就创建一个共享页的拷贝。采用写时拷贝技术，很显然只有被进程所修改的页才会复制，因此创建进程更有效率。写时拷贝时所需的空闲页来自一个空闲缓冲池。该缓冲池中的页在分配之前先填零，以清除以前的页内容。,25,26,9.4 页面置换,给原有的页错误服务程序增加页置换，可以防止内存的过度分配（over-allocating）。,27,需要页置换的情况,28,9.4.1 页置换的基本方法,查找所需页在磁盘上的位置查找一空闲帧如果有空闲帧，那么就使用它如果没有空闲帧，那么就使用页置换算法以选择一个“牺牲”帧（victim fram
14、e）。将“牺牲”帧的内容写到磁盘上；改变页表和帧表。将所需页读入（新）空闲帧；改变页表和帧表重启用户进程。,29,页置换,30,如果没有空闲帧，那么需要两个页传输，将页错误处理时间加倍，相应地增加了有效访问时间使用修改位（脏位）来降低页传输的开销 只有被修改过的页才写回至磁盘。页置换分开了逻辑内存与物理内存 采用这种机制，小的物理内存能为程序员提供巨大的虚拟内存。,31,实现按需调页需要解决的问题,帧分配算法决定为每个进程各分配多少帧页置换算法需要页置换时，选择要置换的帧,32,页置换算法,追求最低的页错误率通过运行一特殊字符串（引用串，reference string）来检验算法，计算其页错
15、误率针对某一特定引用串和页转换算法，为了确定页错误的数量，还需要知道可用帧的数量。为了讨论页转换算法，将采用以下引用串，而可用帧的数量为37,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,33,页错误与帧数量关系图,34,页置换算法,FIFO页置换最优置换LRU页置换近似LRU页置换基于计数的页置换,35,FIFO页置换,基本思想最简单的页置换算法。FIFO为每个页记录着进入内存的时间，当必须置换一页时，将选择最旧的页并不需要记录调入一页的确切时间，可以创建一个FIFO对列来管理内存中的所有页,36,FIFO Page Replacement,7,0,1,2,0,
16、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,53 frames(3 pages can be in memory at a time per process)4 framesFIFO Replacement Beladys Anomalymore frames less page faults(not always true),38,一个采用FIFO置换引用串的页错误曲线,39,FIFO是最简单的，但其性能并总是很好，所替代的也可能是很久以前使用的，现已不在使用的初始化模块，也可能包含一个以前初
17、始化的并且不断使用的常用变量FIFO算法有Belady异常现象对有的置换算法，页错误率可能会随着所分配的帧数的增加而增加原期望为进程增加内存会改善其性能，但看来这种推测并不总是正确的,40,最优页置换（Optimal 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,然而，最优页
18、置换算法难于实现，因为需要引用串的未来知识,43,LRU页置换,使用离过去最近作为不远将来的近似，置换最长时间没有使用的页。,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,44,LRU实现,计数器为每个页表项关联一个使用时间域，并为CPU增加一个逻辑时钟或计数器。对每次内存引用，计数器都会增加。每次内存引用时，时钟寄存器的内容会复制到相应页所对应页表项的使用时间域内。置换具有最小时间的页。页码堆栈每次引用一个页，该页就从堆栈中删除并放在顶部。这样，堆栈顶部总是最近使用的页，堆栈底部总是LRU页。,45,用堆栈来记录最近使用的页,46,很少有计算机系统能提供足够
19、的硬件来支持真正LRU页置换算法。然而很多系统都通过引用位来提供一定的支持页表中的每项都关联着一个引用位，每当引用一个页时，相应页的引用位就被硬件置位(为1)通过检查引用位，能确定那些页使用过哪些页未使用过附加引用位算法二次机会算法增强型二次机会算法,LRU近似页置换算法,47,附加引用位算法,附加引用位算法为位于内存中的每个表中的页保留一个8位的字节在规定的时间间隔内，OS把每个页的引用位转移到8位的高位，而将其他位向右移这些8位移位寄存器包含该页在最近8个周期内的使用情况0000000表示该页在8个周期内没有使用过11111111表示该页在每个周期内都至少使用过一次11000100要比01
20、110111的页更为最近使用如果将这8位字节作为无符号整数，那么具有最小值的页尾LRU页这些数字并以唯一，可以置换所有具有最小值的页或采用FIFO来选择置换,48,LRU近似页置换算法,二次机会算法当要选择一个页时，检查其引用位。如果其值为0那么就直接置换该页。如果该引用位为1,那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。,49,二次机会（时钟）页置换算法,50,增强型二次机会算法,增强型二次机会算法通过将引用位和修改位作为一个有序对来考虑，可得到四种可能类型1类(0,0)最近没有使用且也没有修改，用于置换的最佳页2类(0,
21、1)最近没有使用但修改过，不是很好，因为在置换之前需要将页写出到磁盘3类(1,0)最近使用过但没有修改，可能很快又要被使用4类(1,1)最近使用过且修改过，它可能很快又要被使用，且置换之前需要将页写出到磁盘当页需要置换时，每个页都属于这四种类型之一。可以检查页属于哪个类型，置换在最低非空类型中所碰到的页在找到要置换页之前，可能要多次搜索整个循环队列,51,基于计数的页置换算法,为每个页保留一个用于记录其引用次数的计数器。最不经常使用页置换算法（least frequently used page replacement algorithm,LFU）最常使用页置换算法（most frequent
22、ly used page-replacement algorithm,MFU）,52,7.页缓冲算法,除了特定页置换算法外，还经常采用其他措施系统通常保留一个空闲帧缓冲池当出现页错误时，会像以前一样选择一个牺牲帧。然而，在牺牲帧写出之前，所需要的页就从缓冲池中读到空闲内存。这种方法运行进程尽可能快地重启，而无需等待牺牲帧的写出。当牺牲帧在以后写出时，它再加入到空闲池。,53,维护一个已修改页的列表每当调页设备空闲时，就选择一个修改页以写到磁盘上，接着重新设置其修改位。增加了选择置换时干净页的概率。保留一个空闲帧池，但要记住哪些页在哪些帧中。由于当帧写到磁盘上时其内容并没有修改，所以在该帧被重用
23、之前如果需要使用原来的页，那么原来的页可直接从空闲池中取出以直接使用。这时并不需要I/O.,7.页缓冲算法,54,9.5 帧分配,如何在各进程之间分配一定的空闲内存？每个进程需要最低数量的页由体系结构决定例如：IBM 370至少需要6页用来处理SS MOVE指令指令是6字节指令，可能跨越2页要移动的字符的块和要移动到目的的区域也可能都要跨页。两种主要的分配方案平均分配比例分配优先级分配,55,平均分配：如100帧，5个进程，则给每个进程20帧比例分配：根据进程的大小按比例分配,56,平均及比例分配特点每个进程所分配的数量会随着多道程序的级别而有所变化。多道程序程度增加，那么每个进程会失去一些帧
24、以提供给新来进程使用。反之，原来分配给离开进程的帧可以分配给剩余进程高优先级进程与低优先级进程在这种分配方式下没有任何区别优先级分配按优先级比例而非进程的大小来分配如果进程 Pi 产生了一个页错误，那么从自身的帧中选择用于替换从比自身优先级低的进程中选取帧用于替换,57,全局分配与局部分配,全局置换允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程；一个进程可以从另一个进程中取帧。局部置换要求每个进程仅从其自己的分配帧中进行选择,58,9.6 系统颠簸,如果一个进程没有足够的页，那么页错误率就会非常高。这会导致CPU使用率低这时OS认为必须提高多道程序的程度因此，新的进程
25、会加入到系统中来。颠簸：进程一直忙于将页面换进换出。,59,颠簸,60,如何防止颠簸？,为了防止颠簸，必须提供进程所需的足够多的帧。但是如何知道进程“需要”多少帧呢？工作集合策略检查进程真正需要多少帧。这种方法定义了进程执行的局部模型（locality model）。当进程执行时，它从一个局部移向另一个局部。局部是一个经常使用页的集合。一个程序通常由多个不同局部组成，它们可能重叠。,61,内存引用模式中的局部性,62,工作集模型,工作集窗口：最近个页面引用这最近个引用的页集合称为工作集合if too small will not encompass entire locality.if too
26、 large will encompass several localities.if=will encompass entire program.WSSi(进程Pi的工作集)=最近所引用的所有页面的总数（不同时刻值不同）D WSSi 表示总的帧需求量如果 D 大于可用帧数量，那么有的进程就得不到足够帧，从而会出现颠簸这时可以悬挂某些进程，以消除颠簸现象,63,工作集模型,64,页错误频率,建立可接受的页错误率如果错误率太低，则进程可能有太多的帧，因此应丢弃一些帧如果错误率太高，则为进程分配更多帧,65,思考题,考虑一个请求调页系统，它采用全局置换策略和平均分配内存块的算法。如果在系统中测得如
27、下的CPU和对换空间利用率，请问能否用增加多道程序的度数来增加CPU的利用率？为什么？(1)CPU利用率为13%，盘利用率为97%；(2)CPU利用率为87%，盘利用率为3%；(3)CPU利用率为13%，盘利用率为3%；,66,9.7 内存映射文件,内存映射文件I/O将文件I/O作为普通内存访问，它允许一部分虚拟内存与文件逻辑相关联开始的文件访问按普通请求页面调度来进行，会产生页面错误。这样，一页大小的部分文件从文件系统读入物理页，以后文件的读写就按通常的内存访问来处理。通过内存的文件操作而不是使用系统调用read和write，简化了文件访问和使用。多个进程可以允许将同一文件映射到各自的虚拟内
28、存中，以允许数据共享。,67,内存映射文件,68,Solaris系统中不管文件是否说明为内存映射，都选择对文件进行内存映射如果一个文件说明为内存映射，那么Solaris将文件映射到进程的地址空间中如果一个文件采用普通系统调用如open()、read等来打开和访问，Solaris仍然对文件进行内存映射，不过是将其映射到内核地址空间多个进程可以允许将同一文件映射到各自的虚拟内存中，以允许数据共享内存映射文件很多方面类似于共享内存,69,9.9 其他考虑,预约式页面调度试图阻止进程开始时出现的大量页错误。在进程开始运行或重启运行的时候，将所需要的页一起调入内存中。预约式页面调度有时可能比较好。关键问
29、题是采用预约式页面调度的成本是否小于处理相应页错误的成本。页大小的选择（有许多因素影响页面大小）碎片 需在小页页表大小 需要大页I/O开销(寻道、延迟和传输时间)需要大页局部性 更小页？更大页？（矛盾）更小的页应用导致更少的I/O和更少的总的分配内存为了降低页错误数量，需要大页。,70,增加TLB范围的大小,TLB命中率TLB范围：指通过TLB可访问的内存量TLB Reach=(TLB Size)(Page Size)理想状况下，一个进程所有的工作集合应位于TLB中，否则会带来较高的页错误率增加TLB范围的两种方法增加TLB Size增加Page Size增加页的大小。这样可能导致碎片的增加提
30、供多种页大小。,71,程序结构,假设页大小为1024个字，分配给进程一个帧int A=new int10241024;每一行存储在一页中程序1for(j=0;j A.length;j+)for(i=0;i A.length;i+)Ai,j=0;共10241024次页错误程序2for(i=0;i A.length;i+)for(j=0;j A.length;j+)Ai,j=0;1024次页错误,72,I/O互锁,有时需要允许某些页在内存中被锁住。从设备上复制文件时用到的页必须被锁住，以防在页面置换上被选中作为换出的页面。,73,锁住位有很多用途操作系统内核的有些或所有页通常都锁在内存中。绝大多数OS不能容忍由内核引起的页错误另一用途涉及普通页置换高优先级进程置换是否可以置换低优先级进程刚刚调入的、还未执行的页使用锁住位可以锁住某页，直到该页至少被执行一次锁住位的危险之处：锁住位可能被打开，但从未被关闭,74,存储管理小结,
