操作系统概念ch9-虚拟内存

《操作系统概念ch9-虚拟内存》由会员分享，可在线阅读，更多相关《操作系统概念ch9-虚拟内存（48页珍藏版）》请在金锄头文库上搜索。

1、操作系统概念第九章：虚拟内存2本章主要内容背景请求页面调度进程创建页面置换帧分配系统颠簸其他考虑39.1 背景虚拟内存将内存抽象成一个巨大的、统一的存 储数组，进而将用户看到的逻辑内存与物理内 存分开。只要部分程序需要放在内存中就能使程序执行逻辑地址空间可以比物理地址空间大。允许地址空间被多个进程共享允许更多进程被创建 虚拟内存可以用以下方式来实现请求页式调度请求段式调度4虚拟内存大于物理内存的示意图59.2 请求页面调度只在页面需要时，才把它们载入内存需要更少的输入输出更小的内存更快的响应更多的用户6分页的内存与邻接的磁盘空间之间 的传递7有效-无效位页表中的每一条目与一有效无效位与之关联。

2、 （1表示该页在内存中，0表示不在内存）有效无效位初始为0当进程试图访问那些尚未调入到内存的页时， 对标记为无效的页面的访问会产生页错误陷阱 （page-fault trap）8当有些页不在内存中时的页表9页错误1.检查进程的页表，以确定该引用是合法还是非法的地 址访问。2.如果引用非法，那么终止进程。如果引用有效但是尚 未调入页面，那么现在应调入。3.找到一个空闲帧（从空闲帧链表中取一个）4.调度一个磁盘操作，以便将所需要的页调入刚分配的 帧5.当磁盘读操作完成后，修改进程的内部表和页表，以 表示该页已在内存中。6.重新开始因非法地址陷阱而中断的指令。进程现在能 访问所需的页，就好像它似乎总

3、在内存中。10处理页错误的步骤11没有空闲帧时该如何处理？页替换 在内存中找到一些不在使用的页， 将它换出。算法性能：希望找到一个算法导致最小的的页错误 的发生一些页可能被多次载入到内存12请求页式调度的性能设P为页错误的概率（0P 1）如果P等于0，则不存在页错误如果等于，则每次访问都存在页错误 有效访问时间 （1P） 内存访问时间 + P页错 误时间 设内存访问时间为100ns，平均错误页处理为 25ms，则EAT为EAT = (1-P) 100ns + P 25ms= 100 + 24999900P ns139.3 进程创建虚拟内存也能在进程创建时，提供其他好处：写时拷贝内存映射文件14

4、写时拷贝(Copy on write)写时拷贝允许父进程和子进程开始时共享同一 页面。这些页面标记为写时复制，即如果任何一个进 程需要对页进行写操作，那么就创建一个共享 页的拷贝。采用写时拷贝技术，很显然只有被进程所修改 的页才会复制，因此创建进程更有效率。写时拷贝时所需的空闲页来自一个空闲缓冲池。 该缓冲池中的页在分配之前先填零，以清除以 前的页内容。15内存映射文件内存映射文件I/O将文件I/O作为普通内存访问， 它允许一部分虚拟内存与文件逻辑相关联开始的文件访问按普通请求页面调度来进行， 会产生页面错误。这样，一页大小的部分文件 从文件系统读入物理页，以后文件的读写就按 通常的内存访问来

5、处理。 通过内存的文件操作而不是使用系统调用read 和write，简化了文件访问和使用。多个进程可以允许将同一文件映射到各自的虚 拟内存中，以允许数据共享。16内存映射文件179.4 页面置换给原有的页错误服务程序增加页置换，可以防 止内存的过度分配过度分配（over-allocating）。使用修改位（脏位）来降低页传输的开销 只有被修改过的页才写回至磁盘。页置换分开了逻辑内存与物理内存 采用这 种机制，小的物理内存能为程序员提供巨大的 虚拟内存。18需要页置换的情况19页置换的基本方法1.查找所需页在磁盘上的位置 2.查找一空闲帧如果有空闲帧，那么就使用它如果没有空闲帧，那么就使用页置换

6、算法以选 择一个“牺牲”帧（victim frame）。将“牺牲”帧的内容写到磁盘上；改变页表和 帧表。 3.将所需页读入（新）空闲帧；改变页表和帧 表 4.重启用户进程。20页置换21页置换算法追求最低的页错误率通过运行一特殊字符串（引用串，reference string）来检验算法，计算其页错误率针对某一特定引用串和页转换算法，为了确定 页错误的数量，还需要知道可用帧的数量。为了讨论页转换算法，将采用以下引用串，而 可用帧的数量为37, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 122页错误与帧数量关系图23FIFO页置换

7、24一个采用FIFO置换引用串的页错误 曲线25最优页置换（Optimal Algorithm）置换那些在最长时间中不会被使用的页。然而，最优页置换算法难于实现，因为需要引 用串的未来知识26LRU页置换使用离过去最近作为不远将来的近似，置换最 长时间没有使用的页。27LRU实现计数器为每个页表项关联一个使用时间域，并为CPU 增加一个逻辑时钟或计数器。对每次内存引用， 计数器都会增加。每次内存引用时，时钟寄存 器的内容会复制到相应页所对应页表项的使用 时间域内。置换具有最小时间的页。页码堆栈每次引用一个页，该页就从堆栈中删除并放在 顶部。这样，堆栈顶部总是最近使用的页，堆 栈底部总是LRU页

8、。28用堆栈来记录最近使用的页29LRU近似页置换算法附加引用位算法每页关联一个引用位，初始为0当页被引用时，该位设为1替换引用位为0的页（如果存在）二次机会算法当要选择一个页时，检查其引用位。如果其值 为0那么就直接置换该页。如果该引用位为1,那 么就给该页第二次机会，并选择下一个FIFO页。 当一个页获得第二次机会时，其引用位清零， 且其到达时间设为当前时间。30二次机会（时钟）页置换算法31基于计数的页置换算法为每个页保留一个用于记录其引用次数的计数 器。最不经常使用页置换算法（least frequently used page replacement algorithm, LFU）最

9、常使用页置换算法（most frequently used page-replacement algorithm, MFU）329.5 帧分配每个进程需要最低数量的页例如：IBM 370至少需要6页用来处理SS MOVE指令指令是6字节指令，可能跨越2页要移动的字符的块和要移动到目的的区域也可 能都要跨页。两种主要的分配方案固定分配优先级分配33固定分配平均分配：如100帧，5个进程，则给每个进程 20帧 比例分配：根据进程的大小按比例分配 特点每个进程所分配的数量会随着多道程序的级别 而有所变化。多道程序程度增加，那么每个进 程会失去一些帧以提供给新来进程使用。反之， 原来分配给离开进程的帧

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

11、。37颠簸38如何防止颠簸？为了防止颠簸，必须提供进程所需的足够多的 帧。但是如何知道进程“需要”多少帧呢？工作集合策略检查进程真正需要多少帧。这种 方法定义了进程执行的局部模型（locality model）。当进程执行时，它从一个局部移向另一个局部。局 部是一个经常使用页的集合。一个程序通常由多个 不同局部组成，它们可能重叠。39内存引用模式中的局部性40工作集合模型工作集合窗口（Working set window）：最近 个页面引用这最近 个引用的页集合称为工作集合 （Working set） WSSi(进程Pi的工作集) = 最近所引用的所有 页面的总数（不同时刻值不同） D WSS

12、i表示总的帧需求量 如果 D 大于可用帧数量，那么有的进程就得不 到足够帧，从而会出现颠簸这时可以悬挂某些进程，以消除颠簸现象这时可以悬挂某些进程，以消除颠簸现象41工作集模型42跟踪工作集（困难）通过固定定时器中断和引用位，能近似工作集模型例：假设 10,000每5000个引用会产生定时中断当出现定时中断时，先复制再清除所有页的引用位。因 此，当出现页错误时，可以检查当前引用位和位于内存 内的两个位，从而确定在过去的10000到15000个引用之 间该页是否被引用过。如果没引用过，那么所有这3个位 均为0,只要有一个位为1,那么就可以认为处于工作集中。 这种计算并不完全准确，这是因为并不知道

13、在5000个 引用的什么位置出现了引用。 通过增加历史位的位数和中断频率，能够降低这一不 确定性。43页错误频率建立可接受的页错误率 如果错误率太低，则进程可能有太多的帧，因此应 丢弃一些帧 如果错误率太高，则为进程分配更多帧449.9 其他考虑预约式页面调度试图阻止进程开始时出现的大量页错误。在进程开始运行或重启运行的时候，将所需要的页所需要的页一起调入内存中。 页大小的选择（有许多因素影响页面大小）碎片 需在小页页表大小 需要大页I/O开销 需要大页局部性 更小页？更大页？（矛盾）更小的页应用导致更少的I/O和更少的总的分配内存为了降低页错误数量，需要大页。 TLB范围：指通过TLB可访问

14、的内存量TLB Reach = (TLB Size) (Page Size)理想状况下，一个进程所有的工作集合应位于TBL中，否则会带来较高 的页错误率增加TLB范围的两种方法增加TBL Size增加Page Size45增加TLB范围的大小增加页的大小。这样可能导致碎片的增加提供多种页大小。46程序结构假设页大小为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次页错误47I/O互锁有时需要允许某些页在 内存中被锁住。从设备上复制文件时用 到的页必须被锁住，以 防在页面置换上被选中 作为换出的页面。48作业P314 P3169.29.39.59.69.99.109.139.149.15