清华大学操作系统讲义第10讲_存储管理_3

1第十讲操作系统与系统编程谌卫军清华大学软件学院2004年春季25.时钟页面置换算法时钟页面置换算法，对FIFO的一种改进；基本思路：–需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问（读/写）则把该位置为1；–把各个页面组织成环形链表（类似钟表面）把指针指向最老的页面（最先进来）；–当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。3001100110001页面访问位页面置换前000000110001页面置换后M4LRU算法和FIFO本质上都是先进先出的思路，只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）；而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以各页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就退化为FIFO算法。例如：给进程分配3个物理页面，逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3…LRU、FIFO和Clock的比较5LRU算法性能较好，但系统开销较大；FIFO算法系统开销较小，但可能会发生Belady现象。因此，折衷的办法就是Clock算法，在每一次页面访问时，它不必去动态地调整该页面在链表当中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再把它移动到链表末尾。对于内存当中那些未被访问的页面，Clock算法的表现和LRU算法一样好；而对于那些曾经被访问过的页面，它不能象LRU算法那样，记住它们的准确位置。64.5.5工作集模型前面介绍的各种页面置换算法，都是基于一个前提,即程序的局部性原理。但是此原理是否成立？如果局部性原理不成立，那么各种页面置换算法就没有什么分别，也没有什么意义。例如：假设进程对逻辑页面的访问顺序是1、2、3、4、5、6、7、8、9…，即单调递增，那么在物理页面数有限的前提下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断。如果局部性原理是成立的，那么如何来证明它的存在，如何来对它进行定量地分析？这就是工作集模型！7工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元函数W(t,)来表示：t是当前的执行时刻；称为工作集窗口（working-setwindow），即一个定长的页面访问窗口；W(t,)＝在当前时刻t之前的窗口当中的所有页面所组成的集合（随着t的变化，该集合也在不断地变化）；|W(t,)|指工作集的大小，即页面数目。1.工作集8261577775162341234443434441327如果窗口的长度为10，那么：W(t1,)={1,2,5,6,7}W(t2,)={3,4}一个例子页面访问顺序：t1t29工作集大小的变化：进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。工作集大小过渡阶段时间稳定阶段102.常驻集常驻集是指在当前时刻，进程实际驻留在内存当中的页面集合。工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法；如果一个进程的整个工作集都在内存当中，即常驻集（＝）工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）；当进程常驻集的大小达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降。113.抖动问题(thrashing)如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为“抖动”。产生抖动的原因：随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以OS要选择一个适当的进程数目，以便在并发水平和缺页率之间达到一个平衡。124.5.6虚拟页式的设计问题1.页面的分配策略如何来确定常驻集的大小？固定分配与可变分配。固定分配策略：常驻集大小固定。例如：各进程平均分配，或根据程序大小按比例分配等。采用局部页面置换的方式，当发生一个缺页中断时，被置换的页面局限在本进程内部。缺点：分配的物理页面数难以确定。进程在运行过程中，工作集的大小可能会不断地变化，若分配的页面数太少，则发生抖动；若分配的页面数太多，则浪费内存资源，降低进程间的并发水平。13可变分配策略：常驻集大小可变。例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小。可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其它进程当中，各个并发进程竞争地使用物理页面。优缺点：性能较好，但增加了系统开销。具体实现：可以使用缺页率算法(PFF,pagefaultfrequency)来动态调整常驻集的大小。14缺页率缺页率表示“缺页次数/内存访问次数”(比率)或“缺页的平均时间间隔的倒数”。影响缺页率的因素：页面置换算法分配给进程的物理页面数目页面本身的大小程序的编制方法15若进程的缺页率过高，则分配更多的物理页面；若进程的缺页率过低，则减少它的物理页面数，力图使每个进程的缺页率保持在一个合理的范围内。缺页率算法16程序的编写方法对缺页率的影响：例子：页面大小为4K，分配给每个进程的物理页面数为1。在一个进程中，定义了如下的二维数组intA[1024][1024]，该数组按行存放在内存，每一行放在一个页面中。程序编制方法1：for(j=0;j1024;j++)for(i=0;i1024;i++)A[i][j]=0;程序编制方法2：for(i=0;i1024;i++)for(j=0;j1024;j++)A[i][j]=0;17a0,0a0,1a0,2……………………..a0,10231a1,0a1,1a1,2……………………..a1,10232…………………………….…………………………….a1023,0a1023,1…………………..a1023,10231024访问页面的序列为：解法1：1，2，3，………1024，1，2，………，共1024组共发生了1024×1024次缺页中断解法2：1，1，1，………，2，2，………，3，3，…….共发生了1024次缺页中断182.页面大小页面大小的选择需要平衡各种相互竞争的因素，没有一个全局性的最优解。有的因素要求较小的页面大小：页面越小，内碎片越少（最后一页有内碎片）;页面越小，内存中暂不使用的程序部分越少；有的因素要求较大的页面大小：页面越大，页表就越小；页面越大，在内存与磁盘间传送相同大小的内容时，所需的I/O开销越小。193.页表结构页表的功能是把逻辑页面号映射为物理页面号，但是在虚拟存储技术当中，虚拟内存空间往往大于实际的物理内存，现代计算机所使用的虚拟地址至少为32位，如果每个页面的大小为4K，那么逻辑页面的个数为220，这就意味着在页表里有220个页表项，而每一个进程都有自己的虚拟地址空间，都需要自己的页表，因而占用了大量的内存空间。为解决此问题，需提出新的页表结构：多级页表(MultilevelPageTables)；反置页表(InvertedPageTables)。204.多级页表由于不是所有的虚拟地址都会用到，所以不必把所有的页表项都保存在内存当中。以二级页表为例：假设逻辑地址为32位，页面大小为4K。把逻辑地址划分为两个部分：逻辑页面号为20位；页内偏移地址为12位；把逻辑页面号再进一步地划分为两个部分：10位的字段PT1，用来指向第一级页表当中所对应的页表项；10位的字段PT2，用来指向第二级页表当中所对应的页表项。21第一级页表第二级页表逻辑地址Stack…DataCode04M8M4G2232位逻辑地址、二级页表结构当中的地址映射过程。（本图摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）一级页表二级页表235.反置页表以前的页表方案都是根据进程的逻辑页面号来组织，以逻辑页面号来作为访问页表的索引。如果逻辑地址位数较多，如64位，那么逻辑地址空间将是264字节，如果页面大小为4K，那么每个进程的页表项的个数为252。一种解决方案是反置页表，即根据内存中的物理页面号来组织页表，用物理页面号来作为访问页表的索引。页表项的个数仅与物理内存的大小和页面大小有关，与逻辑空间大小和进程数无关。每个页表项记录了在相应的物理页面中，保存的是哪个进程的哪一个逻辑页面。反置页表节省了大量内存空间，但逻辑页面号到物理页面号的转换变得更复杂，一种方法是Hash表。24（本图摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）反置页表示意图254.5.7虚拟段式存储管理•需要在进程的段表中添加若干项：–标志位：驻留位(presentbit),修改位(modified/dirtybit),增长位（该段是否增长过，在虚拟页式中没有该位）–访问统计：如访问位(usebit)–存取权限：如读R，写W，执行X•缺段中断处理：当发生缺段中断时，首先检查内存中是否有足够的空闲空间，若有，则装入该段，并修改有关数据结构；若没有，则采用内存紧缩技术或淘汰一些段，然后再装入该段。在简单段式存储管理的基础上，增加请求调段和段置换功能。264.6Windows2000的存储管理4.6.1基本概念每个用户进程都有自己的逻辑（虚拟）地址空间，地址长度为32位，地址空间大小为4G；地址空间低端的2G（减去至少192KB）用于存放进程的代码和数据，地址空间高端的2G则被操作系统占用。Windows2000的AdvancedServer版和DatacenterServer版允许3G的用户空间；Windows2000采用虚拟页式存储管理技术，页面的大小为4KB。271.地址空间布局64KWhy2G-2G?282.逻辑页面的状态每一个逻辑页面可能处于三种状态之一：空闲状态(free)：该逻辑页面未被使用，此时若访问该页面，将导致页面访问错误；占用状态(committed)：该逻辑页面中保存有进程的代码或数据。此时若访问该页面，MMU将把它映射为相应的物理页面，若映射失败，则产生缺页中断，从磁盘把该页面装入内存；预留状态(reserved)：该逻辑页面尚未存储信息，但已被预定，不能再分配出去。29页面文件(pagingfile)：用来存放一些修改过的页面，这些页面仍被进程所使用，但需暂时保存在磁盘上。这些文件中的页面称为原页面的影子页面；只有处于占用状态的逻辑页面才需要影子页面，而且只有在该页面被置换出内存时，才为它分配磁盘空间，所有影子页面被组织在一个或多个文件中；操作系统负责记录哪一个逻辑页面被保存在哪一个页面文件的哪一部分；为避免磁盘空间的浪费，对于只可执行的代码页面，它的影子页面包含在相应的可执行文件(.exe或.dll文件)中；对于数据页面，才使用页面文件。3.页面文件304.内存映射文件Windows2000允许将磁盘文件映射到进程逻辑地址空间的某个连续区域（连续的逻辑页面），然后可以使用通常的内存访问方法来读写该文件，这种文件称为内存映射文件（memory-mappedfile）。内存映射文件的实现机制与影子页面相似，即把影子页面直接放在用户文件中，而不是页面文件中；当一个磁盘文件被映射到内存