第十章虚拟内存-《操作系统概念》课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,操作系统概念,第十章：虚拟内存,1,本章主要内容,背景,请求页面调度,进程创建,页面置换,帧分配,系统颠簸,其他考虑,2,10.1 背景,虚拟内存将内存抽象成一个巨大的、统一的存储数组，进而将用户看到的逻辑内存与物理内存分开。,只要部分程序需要放在内存中就能使程序执行,逻辑地址空间可以比物理地址空间大。,允许地址空间被多个进程共享,允许更多进程被创建,虚拟内存可以用以下方式来实现,请求页式调度,请求段式调度,3,虚拟内存大于物理内存的示意图,4,分页的内存与邻接的磁盘空间之间的传递,6,有效-无效位,页表中的每一条目与一有效无效位与之关联。（1表示该页在内存中，0表示不在内存）,有效无效位初始为0,当进程试图访问那些尚未调入到内存的页时，对标记为无效的页面的访问会产生页错误陷阱（page-fault trap）,7,当有些页不在内存中时的页表,8,处理页错误的步骤,10,没有空闲帧时该如何处理？,页替换 在内存中找到一些不在使用的页，将它换出。,算法,性能：希望找到一个算法导致最小的的页错误的发生,一些页可能被多次载入到内存,11,10.3 进程创建,虚拟内存也能在进程创建时，提供其他好处：,写时拷贝,内存映射文件,13,内存映射文件,内存映射文件I/O将文件I/O作为普通内存访问，它允许一部分虚拟内存与文件逻辑相关联,开始的文件访问按普通请求页面调度来进行，会产生页面错误。这样，一页大小的部分文件从文件系统读入物理页，以后文件的读写就按通常的内存访问来处理。,通过内存的文件操作而不是使用系统调用read和write，简化了文件访问和使用。,多个进程可以允许将同一文件映射到各自的虚拟内存中，以允许数据共享。,15,内存映射文件,16,需要页置换的情况,18,页置换的基本方法,查找所需页在磁盘上的位置,查找一空闲帧,如果有空闲帧，那么就使用它,如果没有空闲帧，那么就使用页置换算法以选择一个“牺牲”帧（,victim frame,）。,将“牺牲”帧的内容写到磁盘上；改变页表和帧表。,将所需页读入（新）空闲帧；改变页表和帧表,重启用户进程。,19,页置换,20,页置换算法,追求最低的页错误率,通过运行一特殊字符串（引用串，reference string）来检验算法，计算其页错误率,针对某一特定引用串和页转换算法，为了确定页错误的数量，还需要知道可用帧的数量。,为了讨论页转换算法，将采用以下引用串，而可用帧的数量为3,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,21,页错误与帧数量关系图,22,一个采用FIFO置换引用串的页错误曲线,24,最优页置换（Optimal Algorithm）,置换那些在最长时间中不会被使用的页。,然而，最优页置换算法难于实现，因为需要引用串的未来知识,25,LRU页置换,使用离过去最近作为不远将来的近似，置换最长时间没有使用的页。,26,用堆栈来记录最近使用的页,28,LRU近似页置换算法,附加引用位算法,每页关联一个引用位，初始为0,当页被引用时，该位设为1,替换引用位为0的页（如果存在）,二次机会算法,当要选择一个页时，检查其引用位。如果其值为0那么就直接置换该页。如果该引用位为1,那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。,29,基于计数的页置换算法,为每个页保留一个用于记录其引用次数的计数器。,最不经常使用页置换算法（least frequently used page replacement algorithm,LFU）,最常使用页置换算法（most frequently used page-replacement algorithm,MFU）,31,10.5 帧分配,每个进程需要最低数量的页,例如：IBM 370至少需要6页用来处理SS MOVE指令,指令是6字节指令，可能跨越2页,要移动的字符的块和要移动到目的的区域也可能都要跨页。,两种主要的分配方案,固定分配,优先级分配,32,固定分配,平均分配：如100帧，5个进程，则给每个进程20帧,比例分配：根据进程的大小按比例分配,特点,每个进程所分配的数量会随着多道程序的级别而有所变化。多道程序程度增加，那么每个进程会失去一些帧以提供给新来进程使用。反之，原来分配给离开进程的帧可以分配给剩余进程,高优先级进程与低优先级进程在这种分配方式下没有任何区别,33,优先级分配,按优先级比例而非进程的大小来分配,如果进程,P,i,产生了一个页错误，那么,从自身的帧中选择用于替换,从比自身优先级低的进程中选取帧用于替换,34,全局分配与局部分配,全局置换,允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程；一个进程可以从另一个进程中取帧。,局部置换,要求每个进程仅从其自己的分配帧中进行选择,35,10.6 系统颠簸,如果一个进程没有足够的页，那么页错误率就会非常高。这会导致,CPU使用率低,这时OS认为必须提高多道程序的程度,因此，新的进程会加入到系统中来。,颠簸：进程一直忙于将页面换进换出。,36,颠簸,37,如何防止颠簸？,为了防止颠簸，必须提供进程所需的足够多的帧。但是如何知道进程“需要”多少帧呢？,工作集合策略检查进程真正需要多少帧。这种方法定义了进程执行的局部模型（locality model）。,当进程执行时，它从一个局部移向另一个局部。局部是一个经常使用页的集合。一个程序通常由多个不同局部组成，它们可能重叠。,38,内存引用模式中的局部性,39,工作集模型,工作集窗口（Working set window）：最近,个页面引用,这最近个引用的页集合称为工作集合（Working set）,WSS,i,(进程,P,i,的工作集)=最近所引用的所有页面的总数（不同时刻值不同）,D WSS,i,表示总的帧需求量,如果 D 大于可用帧数量，那么有的进程就得不到足够帧，从而会出现颠簸,这时可以悬挂某些进程，以消除颠簸现象,40,工作集模型,41,跟踪工作集（困难）,通过固定定时器中断和引用位，能近似工作集模型,例：假设,10,000,每5000个引用会产生定时中断,当出现定时中断时，先复制再清除所有页的引用位。因此，当出现页错误时，可以检查当前引用位和位于内存内的两个位，从而确定在过去的10000到15000个引用之间该页是否被引用过。如果没引用过，那么所有这3个位均为0,只要有一个位为1,那么就可以认为处于工作集中。,这种计算并不完全准确，这是因为并不知道在5000个引用的什么位置出现了引用。,通过增加历史位的位数和中断频率，能够降低这一不确定性。,42,页错误频率,建立可接受的页错误率,如果错误率太低，则进程可能有太多的帧，因此应丢弃一些帧,如果错误率太高，则为进程分配更多帧,43,10.7 其他考虑,预约式页面调度,试图阻止进程开始时出现的大量页错误。,在进程开始运行或重启运行的时候，将,所需要的页,一起调入内存中。,页大小的选择（有许多因素影响页面大小）,碎片,需在小页,页表大小,需要大页,I/O开销,需要大页,局部性,更小页？更大页？（矛盾）,更小的页应用导致更少的I/O和更少的总的分配内存,为了降低页错误数量，需要大页。,TLB范围：指通过TLB可访问的内存量,TLB Reach=(TLB Size)(Page Size),理想状况下，一个进程所有的工作集合应位于TBL中，否则会带来较高的页错误率,增加TLB范围的两种方法,增加TBL Size,增加Page Size,44,增加TLB范围的大小,增加页的大小。这样可能导致碎片的增加,提供多种页大小。,45,程序结构,假设页大小为1024个字，分配给进程一个帧,int A =new int10241024;,每一行存储在一页中,程序1,for(j=0;j A.length;j+),for(i=0;i A.length;i+),Ai,j=0;,共10241024次页错误,程序2,for(i=0;i A.length;i+),for(j=0;j A.length;j+),Ai,j=0;,1024次页错误,46,I/O互锁,有时需要允许某些页在内存中被锁住。,从设备上复制文件时用到的页必须被锁住，以防在页面置换上被选中作为换出的页面。,47,作业,P268 P270,10.2,10.3,10.5,10.6,10.9,10.10,10.16,48,