1、操作系统概念第九章：虚拟内存2本章主要内容n背景n按需调页n写时复制n页面置换n帧分配n系统颠簸n内存映射文件n其他考虑39.1 背景n常规存储方器管理方式的特征：n一次性n驻留性4程序执行的局部性原理程序执行的局部性原理虚拟存储的虚拟存储的理论依据理论依据n程序执行时，除了少部分的转移和过程调用外，在大多数情况下仍是顺序执行的n过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但研究发现，过程调用的深度在大多数情况下都不超过5。即程序将会在一段时间内局限在这些过程的范围内运行。n程序中存在很多循环结构，这些虽然只是少数指令构成，但是他们将多次执行。n程序中还包括许多对数据结构的处理，
2、比如数组，他们往往都局限于很小的范围内5局限性又表现在下述两个方面n时间局限性n如果程序中某条指令一旦执行，则不久后该指令可能再次执行；如果某数据被访问过，则不久后该数据可能再次被访问n产生时间局限性的典型原因是由于在程序中存在着大量的循环操作n空间局限性n一个程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围之内n典型原因就是程序的顺序执行6n在许多情况下，（加载）整个程序是没必要的在许多情况下，（加载）整个程序是没必要的n允许程序部分加载即可运行会有许多好处：允许程序部分加载即可运行会有许多好处：nA program wou
3、ld no longer be constrained by the amount of physical memory.nMore programs could be run at the same time, with a corresponding increase in CPU utilization and throughput.nLess I/O would be needed to load or swap each user program into memory, so each user program would run faster.7n 用户逻辑存储与物理存储分离用户
4、逻辑存储与物理存储分离n仅部分程序必须在内存，以使其运行仅部分程序必须在内存，以使其运行n 从而逻辑地址空间远大于物理地址空间从而逻辑地址空间远大于物理地址空间 使得编程更加容易，程序员只需关心所要解决的问题使得编程更加容易，程序员只需关心所要解决的问题 采用虚拟内存的系统几乎用不到覆盖采用虚拟内存的系统几乎用不到覆盖n 允许更有效的进程创建允许更有效的进程创建(写时拷贝写时拷贝)n所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统89n虚拟存储可通过以下方式实现虚拟存储可通过以下方式实现: 请求分页管理方式 请求分段管理方式式n但是，段的替换算法比页
5、替换算法复杂，因为段的大小不同 请求段页式管理方式10n其逻辑容量是由内存容量和外存容量之和所决定的，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储器是一个性能非常优越的存储管理技术，故被广泛应用于大、中、小型机器和微型机中n虚拟存储器的实现都毫无例外地建立在离散分配的存储管理方式的基础上n虚拟存储器的特征：多次性、对换性、虚拟性119.2 按需调页n一个执行程序如何从磁盘载入内存？n将整个程序载入内存n在需要时调入相应的页按需调页12n按需调页系统类似于按需调页系统类似于nBut we use a nSwapper(交换程序交换程序) vs Pager(调页程序调页程序
6、)pager never swaps a page into memory unless that page will be needed.swapper manipulates entire processes.13分页的内存与邻接的磁盘空间之间的传递149.2.1 基本概念n只在页面需要时，才把它们载入内存n需要更少的输入输出n更小的内存n更快的响应n更多的用户15有效-无效位n页表中的每一条目与一有效无效位与之关联。（1表示该页在内存中，0表示不在内存）n有效无效位初始为0n当进程试图访问那些尚未调入到内存的页时，对标记为无效的页面的访问会产生页错误陷阱（page-fault trap）
7、16当有些页不在内存中时的页表17页错误的处理1.检查进程的页表，以确定该引用是合法还是非法的地址访问。2.如果引用非法，那么终止进程。如果引用有效但是尚未调入页面，那么现在应调入。3.找到一个空闲帧（从空闲帧链表中取一个）4.调度一个磁盘操作，以便将所需要的页调入刚分配的帧5.当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中。6.重新开始因非法地址陷阱而中断的指令。进程现在能访问所需的页，就好像它似乎总在内存中。18处理页错误的步骤19nNever bring a page into memory until it is required.nStart executing a
8、 process with no pages in memoryn理论上，某些程序每次执行指令可能访问多理论上，某些程序每次执行指令可能访问多个个新新内存页内存页none page for the instruction and many for datanpossibly causing multiple page faults per instruction.nFortunately, programs tend to have 20请求页式调度的性能n设P为页错误的概率（0P 1）n如果P等于0，则不存在页错误n如果等于，则每次访问都存在页错误n有效访问时间n （1P） 内存访问时间 +
9、 P页错误时间n设内存访问时间为100ns，平均错误页处理为25ms，则EAT为nEAT = (1-P) 100ns + P 25msn = 100 + 24999900P ns21nA page fault caused the following sequence to occur:nTrap to the OSnSave the user registers and process statenDetermine that the interrupt was a page faultnCheck that the page reference was legal and determin
10、e the location of the page on the disknIssue a read from the disk to free framenWhile waiting, allocate the CPU to some other usernReceive an interrupt from the disk I/O (I/O completed)nSave the registers and process state for the other usernDetermine that the interrupt was from the disknCorrect the
11、 page table and other tables to show that the desired page is now in memorynWait for the CPU to be allocated to this process againnRestore the user registers, process state, and new page table, and then resume the interrupted instruction22三个主要的页错误处理时间n处理页错误中断n读入页n重新启动进程23nExamplenMemory access time
12、= 100 nanosecondsnAn average page-fault service time=25 millisecondsnEAT(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 nThe EAT is directly proportional to the page-fault rate.nIf we want less than 10-percent degradation,we needx p x p
13、p 0.0000004n请求页面调度中，降低页错误率是非常重要的请求页面调度中，降低页错误率是非常重要的n请求页面调度的另一个重要方面是交换空间的处理和使用请求页面调度的另一个重要方面是交换空间的处理和使用249.3 写时复制(Copy on write)n写时拷贝允许父进程和子进程开始时共享同一页面。n这些页面标记为写时复制，即如果任何一个进程需要对页进行写操作，那么就创建一个共享页的拷贝。n采用写时拷贝技术，很显然只有被进程所修改的页才会复制，因此创建进程更有效率。n写时拷贝时所需的空闲页来自一个空闲缓冲池。该缓冲池中的页在分配之前先填零，以清除以前的页内容。25physical memo
14、ryphysical memory269.4 页面置换n给原有的页错误服务程序增加页置换，可以防止内存的过度分配过度分配（over-allocating）。27需要页置换的情况289.4.1 页置换的基本方法1.查找所需页在磁盘上的位置2.查找一空闲帧n如果有空闲帧，那么就使用它n如果没有空闲帧，那么就使用页置换算法以选择一个“牺牲”帧（victim frame）。n将“牺牲”帧的内容写到磁盘上；改变页表和帧表。3.将所需页读入（新）空闲帧；改变页表和帧表4.重启用户进程。29页置换30n如果没有空闲帧，那么需要两个页传输，将页错误处理时间加倍，相应地增加了有效访问时间n使用修改位（脏位）来降
15、低页传输的开销 只有被修改过的页才写回至磁盘。n页置换分开了逻辑内存与物理内存 采用这种机制，小的物理内存能为程序员提供巨大的虚拟内存。31实现按需调页需要解决的问题n帧分配算法n决定为每个进程各分配多少帧n页置换算法n需要页置换时，选择要置换的帧32页置换算法n追求最低的页错误率n通过运行一特殊字符串（引用串，reference string）来检验算法，计算其页错误率n针对某一特定引用串和页转换算法，为了确定页错误的数量，还需要知道可用帧的数量。n为了讨论页转换算法，将采用以下引用串，而可用帧的数量为3n7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2
16、, 0, 1, 7, 0, 133页错误与帧数量关系图34页置换算法nFIFO页置换n最优置换nLRU页置换n近似LRU页置换n基于计数的页置换35FIFO页置换n基本思想n最简单的页置换算法。nFIFO为每个页记录着进入内存的时间，当必须置换一页时，将选择最旧的页n并不需要记录调入一页的确切时间，可以创建一个FIFO对列来管理内存中的所有页36FIFO Page Replacement7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 137nReference string: 1, 2, 3, 4, 1, 2, 5, 1, 2,
17、 3, 4, 5n3 frames (3 pages can be in memory at a time per process)n4 framesnFIFO Replacement Beladys Anomalynmore frames less page faults(not always true)1231234125349 page faults1231235124510 page faults44338一个采用FIFO置换引用串的页错误曲线39nFIFO是最简单的，但其性能并总是很好，所替代的也可能是很久以前使用的，现已不在使用的初始化模块，也可能包含一个以前初始化的并且不断使用的
18、常用变量nFIFO算法有Belady异常现象n对有的置换算法，页错误率可能会随着所分配的帧数的增加而增加n原期望为进程增加内存会改善其性能，但看来这种推测并不总是正确的40最优页置换（Optimal Algorithm）n4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 512346 page faults45n 基本思想基本思想n最优页置换算法是所有算法中产生也错误率最低的，且绝对没有最优页置换算法是所有算法中产生也错误率最低的，且绝对没有Belady异常的问题异常的问题n它置换那些在最长时间内不会被使用的页它置换那些在最长时间内不会被使用的
19、页41Optimal Page Replacement7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 142n然而，最优页置换算法难于实现，因为需要引用串的未来知识43LRU页置换n使用离过去最近作为不远将来的近似，置换最长时间没有使用的页。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 144LRU实现n计数器n为每个页表项关联一个使用时间域，并为CPU增加一个逻辑时钟或计数器。对每次内存引用，计数器都会增加。每次内存引用时，时钟寄存器的内容会复制到相应页所对应页表项的使用时间域内。置换具有最小时间
20、的页。n页码堆栈n每次引用一个页，该页就从堆栈中删除并放在顶部。这样，堆栈顶部总是最近使用的页，堆栈底部总是LRU页。45用堆栈来记录最近使用的页46n很少有计算机系统能提供足够的硬件来支持真正LRU页置换算法。然而很多系统都通过引用位来提供一定的支持n页表中的每项都关联着一个引用位，每当引用一个页时，相应页的引用位就被硬件置位(为1)n通过检查引用位，能确定那些页使用过哪些页未使用过n附加引用位算法n二次机会算法n增强型二次机会算法LRU近似页置换算法47附加引用位算法n附加引用位算法n为位于内存中的每个表中的页保留一个8位的字节n在规定的时间间隔内，OS把每个页的引用位转移到8位的高位，而
21、将其他位向右移n这些8位移位寄存器包含该页在最近8个周期内的使用情况n0000000表示该页在8个周期内没有使用过n11111111表示该页在每个周期内都至少使用过一次n11000100要比01110111的页更为最近使用n如果将这8位字节作为无符号整数，那么具有最小值的页尾LRU页n这些数字并以唯一，可以置换所有具有最小值的页或采用FIFO来选择置换48LRU近似页置换算法n二次机会算法n当要选择一个页时，检查其引用位。如果其值为0那么就直接置换该页。如果该引用位为1,那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。49二次机
22、会（时钟）页置换算法50增强型二次机会算法n增强型二次机会算法n通过将引用位和修改位作为一个有序对来考虑，可得到四种可能类型n1类 (0,0)最近没有使用且也没有修改，用于置换的最佳页n2类 (0,1)最近没有使用但修改过，不是很好，因为在置换之前需要将页写出到磁盘n3类 (1,0)最近使用过但没有修改，可能很快又要被使用n4类 (1,1)最近使用过且修改过，它可能很快又要被使用，且置换之前需要将页写出到磁盘n当页需要置换时，每个页都属于这四种类型之一。n可以检查页属于哪个类型，置换在最低非空类型中所碰到的页n在找到要置换页之前，可能要多次搜索整个循环队列51基于计数的页置换算法n为每个页保留
23、一个用于记录其引用次数的计数器。n最不经常使用页置换算法（least frequently used page replacement algorithm, LFU）n最常使用页置换算法（most frequently used page-replacement algorithm, MFU）527. 页缓冲算法n除了特定页置换算法外，还经常采用其他措施n系统通常保留一个空闲帧缓冲池n当出现页错误时，会像以前一样选择一个牺牲帧。然而，在牺牲帧写出之前，所需要的页就从缓冲池中读到空闲内存。这种方法运行进程尽可能快地重启，而无需等待牺牲帧的写出。当牺牲帧在以后写出时，它再加入到空闲池。 53n维护
24、一个已修改页的列表n每当调页设备空闲时，就选择一个修改页以写到磁盘上，接着重新设置其修改位。增加了选择置换时干净页的概率。n保留一个空闲帧池，但要记住哪些页在哪些帧中。n由于当帧写到磁盘上时其内容并没有修改，所以在该帧被重用之前如果需要使用原来的页，那么原来的页可直接从空闲池中取出以直接使用。这时并不需要I/O.7. 页缓冲算法549.5 帧分配n如何在各进程之间分配一定的空闲内存？n每个进程需要最低数量的页由体系结构决定n例如：IBM 370至少需要6页用来处理SS MOVE指令n指令是6字节指令，可能跨越2页n要移动的字符的块和要移动到目的的区域也可能都要跨页。n两种主要的分配方案n平均分
25、配n比例分配n优先级分配55n平均分配：如100帧，5个进程，则给每个进程20帧n比例分配：根据进程的大小按比例分配mSspamsSpsiiiiii for allocation frames of number total process of size 5964137127564137101271064212aassmi56n平均及比例分配特点n每个进程所分配的数量会随着多道程序的级别而有所变化。多道程序程度增加，那么每个进程会失去一些帧以提供给新来进程使用。反之，原来分配给离开进程的帧可以分配给剩余进程n高优先级进程与低优先级进程在这种分配方式下没有任何区别n优先级分配n按优先级比例而非
26、进程的大小来分配n如果进程 Pi 产生了一个页错误，那么n从自身的帧中选择用于替换n从比自身优先级低的进程中选取帧用于替换57全局分配与局部分配n全局置换n允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程；一个进程可以从另一个进程中取帧。n局部置换n要求每个进程仅从其自己的分配帧中进行选择589.6 系统颠簸n如果一个进程没有足够的页，那么页错误率就会非常高。这会导致nCPU使用率低n这时OS认为必须提高多道程序的程度n因此，新的进程会加入到系统中来。n颠簸：进程一直忙于将页面换进换出。59颠簸60如何防止颠簸？n为了防止颠簸，必须提供进程所需的足够多的帧。但是如何知道
27、进程“需要”多少帧呢？n工作集合策略检查进程真正需要多少帧。这种方法定义了进程执行的局部模型（locality model）。n当进程执行时，它从一个局部移向另一个局部。局部是一个经常使用页的集合。一个程序通常由多个不同局部组成，它们可能重叠。61内存引用模式中的局部性62工作集模型n工作集窗口：最近个页面引用n这最近个引用的页集合称为工作集合nif too small will not encompass entire locality.nif too large will encompass several localities.nif = will encompass entire pr
28、ogram.nWSSi (进程Pi的工作集) = 最近所引用的所有页面的总数（不同时刻值不同）nD WSSi 表示总的帧需求量n如果 D 大于可用帧数量，那么有的进程就得不到足够帧，从而会出现颠簸n这时可以悬挂某些进程，以消除颠簸现象这时可以悬挂某些进程，以消除颠簸现象63工作集模型64页错误频率n建立可接受的页错误率n如果错误率太低，则进程可能有太多的帧，因此应丢弃一些帧n如果错误率太高，则为进程分配更多帧65思考题n考虑一个请求调页系统，它采用全局置换策略和平均考虑一个请求调页系统，它采用全局置换策略和平均分配内存块的算法。如果在系统中测得如下的分配内存块的算法。如果在系统中测得如下的CP
29、UCPU和对和对换空间利用率，请问能否用增加多道程序的度数来增换空间利用率，请问能否用增加多道程序的度数来增加加CPUCPU的利用率？为什么？的利用率？为什么？n(1) CPU(1) CPU利用率为利用率为13%13%，盘利用率为，盘利用率为97%97%；n(2) CPU(2) CPU利用率为利用率为87%87%，盘利用率为，盘利用率为3%3%；n(3) CPU(3) CPU利用率为利用率为13%13%，盘利用率为，盘利用率为3%3%； 669.7 内存映射文件n内存映射文件I/O将文件I/O作为普通内存访问，它允许一部分虚拟内存与文件逻辑相关联n开始的文件访问按普通请求页面调度来进行，会产生
30、页面错误。这样，一页大小的部分文件从文件系统读入物理页，以后文件的读写就按通常的内存访问来处理。n通过内存的文件操作而不是使用系统调用read和write，简化了文件访问和使用。n多个进程可以允许将同一文件映射到各自的虚拟内存中，以允许数据共享。67内存映射文件68nSolaris系统中不管文件是否说明为内存映射，都选择对文件进行内存映射n如果一个文件说明为内存映射，那么Solaris将文件映射到进程的地址空间中n如果一个文件采用普通系统调用如open()、read等来打开和访问，Solaris仍然对文件进行内存映射，不过是将其映射到内核地址空间n多个进程可以允许将同一文件映射到各自的虚拟内存
31、中，以允许数据共享n内存映射文件很多方面类似于共享内存699.9 其他考虑n预约式页面调度n试图阻止进程开始时出现的大量页错误。n在进程开始运行或重启运行的时候，将所需要的页所需要的页一起调入内存中。n预约式页面调度有时可能比较好。关键问题是采用预约式页面调度的成本是否小于处理相应页错误的成本。n页大小的选择（有许多因素影响页面大小）n碎片 需在小页n页表大小 需要大页nI/O开销(寻道、延迟和传输时间) 需要大页n局部性 更小页？更大页？（矛盾）n更小的页应用导致更少的I/O和更少的总的分配内存n为了降低页错误数量，需要大页。70增加TLB范围的大小nTLB命中率nTLB范围：指通过TLB可
32、访问的内存量nTLB Reach = (TLB Size) (Page Size)n理想状况下，一个进程所有的工作集合应位于TLB中，否则会带来较高的页错误率n增加TLB范围的两种方法n增加TLB Sizen增加Page Size 增加页的大小。这样可能导致碎片的增加 提供多种页大小。71程序结构n假设页大小为1024个字，分配给进程一个帧nint A = new int10241024;n每一行存储在一页中n程序1for (j=0; j A.length; j+)for (i=0; i A.length; i+)Ai, j = 0;共10241024次页错误n程序2for (i=0; i A.length; i+)for (j=0; j A.length; j+)Ai, j = 0;1024次页错误72I/O互锁 n有时需要允许某些页在内存中被锁住。 n从设备上复制文件时用到的页必须被锁住，以防在页面置换上被选中作为换出的页面。73n锁住位有很多用途n操作系统内核的有些或所有页通常都锁在内存中。绝大多数OS不能容忍由内核引起的页错误n另一用途涉及普通页置换n高优先级进程置换是否可以置换低优先级进程刚刚调入的、还未执行的页n使用锁住位可以锁住某页，直到该页至少被执行一次n锁住位的危险之处：锁住位可能被打开，但从未被关闭74n存储管理小结
