第8章-虚拟内存

第八章虚拟内存2本章主要内容背景请求页面调度写时复制进程创建页面置换帧分配系统颠簸内存映射文件内核内存的分配其他考虑38.1背景虚拟内存将用户看到的逻辑内存与物理内存分开；只要部分程序放在内存中就能使程序执行；逻辑地址空间可以比物理地址空间大。许多情况下，整个程序不是必需的：错误代码；数组、链表和表分配的空间比实际所需要的大；程序的某些选项或功能很少使用。48.1背景（cont.）优点程序能够比实际内存空间大程序员不必关心内存空间限制允许地址空间被多个进程共享所需I/O更少，程序运行更快多个进程之间共享文件更加容易允许更多进程被创建虚拟内存可以用以下方式来实现请求页式调度（按需调页）请求段式调度5虚拟内存大于物理内存的示意图6虚拟地址空间进程如何在内存中存放的逻辑视图稀地址空间(holes)7使用虚拟地址的共享库LibrarycanbesharedCommunicationFork()systemcall88.2按需调页（demandpaging）只在页面需要时，才载入内存需要更少的输入输出更小的内存更快的响应更多的用户懒惰交换（Lazyswapper）只有到需要时，才把它调入内存；调页程序（pager）处理单个页的交换。9分页的内存到连续的磁盘空间之间的传递10有效/无效位页表中的每一条目与一有效/无效位与之关联。（v表示该页在内存中，i表示不在内存）有效/无效位初始为i当进程试图访问那些尚未调入到内存的页时，对标记为无效的页面的访问会产生页错误陷阱（faulttrap）vvvvii….Frame#valid-invalidbitpagetable11当有些页不在内存中时的页表12页错误第一次引用页将陷入操作系统检查进程的页表，如果引用非法，那么终止进程如果引用有效但是尚未调入页面，那么现在应调入。找到一个空闲帧（从空闲帧链表中取一个）调度一个磁盘操作，以便将所需要的页调入刚分配的帧当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中。重新开始因非法地址陷阱而中断的指令。13处理页错误的步骤14页错误（cont.）重启指令C=A+B获取并编译指令（ADD）提取A提取BA与B相加将和存储到C中 (C不在内存中)可以忽略的问题重复一条指令导致N个页错误15页错误（cont.）一条指令修改N个位置例.MVC(movecharacter),能够移动256B块可能跨越页边界；移动部分字符后出现页错误；如果源和目的块有重叠；源块可能已被修改解决方案试图存取两个块的两端；使用临时寄存器保存被覆盖位置的值。16按需调页的性能设P为页错误的概率（0≤P≤1）如果P等于0，则不存在页错误如果Ｐ等于１，则每次访问都存在页错误，纯粹按需调页（puredemandpaging）有效访问时间ＥＡＴ＝（1－P）×内存访问时间+P×页错误时间（页错误准备时间+页换出时间（可选）+页换入时间+重启指令时间）17按需调页的例子内存存取时间=200纳秒；平均页错误服务时间=8毫秒；EAT=(1–p)x200+p(8milliseconds) =(1–px200+px8,000,000=200+px7,999,800如果每1000次访问中有1次页错误，则EAT=8.2微秒即因按需调页而慢40倍。如果需要性能降低不超过10%，则220〉200+px7,999,800，即p<0.0000025188.3进程创建虚拟内存也能在进程创建时，提供其他好处：写时复制内存映射文件19写时复制(Copyonwrite)写时复制父进程和子进程开始时共享同一页面，这些页面标记为写时复制。任何一个进程需要对页进行写操作，那么就创建一个共享页的副本。只标记那些能够被修改的页；创建进程更有效率；写时复制时所需的空闲页来自一个空闲缓冲池。按需填零（zero-fill-on-demand）。20进程2修改页C之前21进程2修改页C之后22没有空闲帧时该如何处理？页替换：在内存中找到一些不使在用的页，将它换出。算法性能：希望找到一个算法导致最小的的页错误的发生一些页可能被多次载入到内存238.4页面置换防止内存的过度分配（over-allocating）给原有的页错误服务程序增加页置换。修改位（脏位）降低页传输的开销－只有被修改过的页才写回至磁盘。分开了逻辑内存与物理内存小的物理内存能为程序员提供巨大的虚拟内存。页帧分配和页置换算法是实现按需调页的基础。24需要页置换的情况25页置换的基本方法查找所需页在磁盘上的位置查找一空闲帧如果有空闲帧，那么就使用它如果没有空闲帧，那么就使用页置换算法以选择一个“牺牲”帧（victimframe）。将“牺牲”帧的内容写到磁盘上；改变页表和帧表。将所需页读入（新）空闲帧；改变页表和帧表重启用户进程。26页置换27页置换算法标准：最低的页错误率通过运行一特殊字符串（引用串，referencestring）来检验算法，计算其页错误率针对某一特定引用串和页转换算法，为了确定页错误的数量，还需要知道可用帧的数量。为了讨论页转换算法，将采用以下引用串，而可用帧的数量为37,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,128页错误与帧数量关系图29FIFO页置换引用页：1,2,3,4,1,2,5,1,2,3,4,5。3个帧（每个进程最多只有3个页面同时在内存）1234125349pagefaults21342151324512330FIFO页置换（cont.）引用页：1,2,3,4,1,2,5,1,2,3,4,5。4个帧Belady异常：帧越多，页错误越多。10pagefaults1235124543213421513245123431FIFO页置换（cont.）32一个采用FIFO置换引用串的页错误曲线33最优页置换（OptimalAlgorithm）置换那些在最长时间中不会被使用的页。4个页帧问题：如何获得页的引用情况？用途：评估页置换算法的优劣。6pagefaults45213421513245432134最优页置换（cont.）35LRU页置换使用离过去最近作为不远将来的近似，置换最长时间没有使用的页。引用页：1,2,3,4,1,2,5,1,2,3,4,5。4个页帧5123412512342134215132458Pagefaults36LRU页置换（cont.）计数器实现每页入口有一个计数器，每次引用页都通过该入口，把时钟值拷到计数器；每次需要换页时，检查计数器决定换出相应的页。37LRU页置换（cont.）栈实现维护一个用双向链表实现的栈。页被引用时：将它移到栈顶；最坏情形下需要修改6个指针；每次更新可能有些费时；但是置换不需要搜索。38用堆栈来记录最近使用的页39LRU近似页置换算法引用位每页关联一个引用位，初始为0当页被引用时，该位设为1替换引用位为0的页（如果存在）不知道使用顺序，只知道是否使用过40LRU近似页置换算法41LRU近似页置换算法二次机会算法当要选择一个页时，检查其引用位。如果其值为0那么就直接置换该页。如果该引用位为1,那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。42二次机会（时钟）页置换算法43基于计数的页置换算法为每个页保留一个用于记录其引用次数的计数器。最不经常使用页置换算法（leastfrequentlyusedpagereplacementalgorithm,LFU）置换引用次数最少的页；问题：开始使用很多，以后再也不使用。定期将计数器的值减半。最常使用页置换算法（mostfrequentlyusedreplacementalgorithm,MFU）具有最小次数的页可能刚调入，且还没有使用448.5帧分配每个进程需要最低数量的页例如：IBM370至少需要6页用来处理MVC指令指令是6字节指令，可能跨越2页；要移动的字符的块，可能跨越2页；要移动到目的区域也可能要跨2页。两种主要的分配方案固定分配优先级分配45固定分配平均分配：如100帧，5个进程，则给每个进程20帧比例分配：根据进程的大小按比例分配。46固定分配特点每个进程所分配的数量会随着多道程序的级别而有所变化。多道程序程度增加，那么每个进程会失去一些帧以提供给新来进程使用。反之，原来分配给离开进程的帧可以分配给剩余进程。高优先级进程与低优先级进程在这种分配方式下没有任何区别。47优先级分配按优先级比例而非进程的大小来分配如果进程Pi产生了一个页错误，那么从自身的帧中选择用于替换从比自身优先级低的进程中选取帧用于替换48全局分配与局部分配全局置换允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程；一个进程可以从另一个进程中取帧。问题：进程不能控制其页错误率局部置换要求每个进程仅从其自己的分配帧中进行选择问题：内存页更少被使用。498.6系统颠簸（Thrashing）如果一个进程没有足够的页，这会导致页错误率就会非常高；CPU使用率低；这时OS认为必须提高多道程序的程度；因此，新的进程会加入到系统中来。颠簸：进程一直忙于将页面换进换出。花更多的时间用于换页，而不是用于执行任务。50颠簸51按需调页和颠簸为什么要进行按需调页？局部模型（localitymodel）进程“需要”多少帧？从一个局部移向另一个局部；一个程序通常由多个不同局部组成，它们可能重叠。为什么会出现颠簸？所有局部的总合>内存的大小等价于活动页面>分配的帧。52内存引用模式中的局部性53工作集模型工作集窗口（Workingsetwindow）：最近Δ个页面引用最近Δ个引用的页集合称为工作集合（Workingset）WSSi(进程Pi的工作集)=最近所引用的所有页面的总数（不同时刻值不同）如果Δ太小，则不能包含整个局部；如果Δ太大，则可能包含多个局部；如果Δ=∞，则包含了整个程序。54工作集模型（cont.）D＝∑WSSi表示总的帧需求量m=可分配的页帧如果D大于m，那么有的进程就得不到足够帧，从而会出现颠簸策略：可以悬挂某些进程，以消除颠簸现象55跟踪工作集（困难）通过固定定时器中断和引用位，能近似工作集模型例：假设Δ＝10,000每5000个引用会产生定时中断。每个页在内存中保留2位。当出现定时中断时，先复制再清除所有页的引用位。如果在内存中有一位为1,那么就可以认为处于工作集中。56跟踪工作集（困难）这种计算并不完全准确，这是因为并不知道在5000个引用的什么位置出现了引用。通过增加历史位的位数和中断频率，能够降低这一不确定性。如，10位，1000个引用就产生中断57页错误频率建立可接受的页错误率如果错误率太低，则进程可能有太多的帧，因此应丢弃一些帧如果错误率太高，则为进程分配更多帧588.7内存映射文件内存映射文件将磁盘块映射成内存页；将文件I/O作为普通内存访问；机制最初采用按需调页读入文件；文件按页大小比例读入物理页；随后的读/写作为普通的内存访问。598.7内存映射文件（cont.）简化文件访问和使用。写内存映射文件的方式同步写异步写多个进程可以同时映射同一个文件允许内存页共享；一个进程的写可以看成是多个进程的写；支持写时复制。608.7内存映射文件（cont.）61Windows中使用内存映射I/O共享内存进程1创建文件映射，并建立视图进程2在自己的虚拟空间中打开并创建文件视图628.8内核内存的分配处理方式与用户态内存不同。通常从空闲内存池中获取内核需要为不同大小的数据结构分配内存。许多OS的内核代码和数据不受分页系统控制。一些内核内存需要连续分配有的硬件要直接与物理内存打交道，而不需要经过虚拟内存接口。63Buddy系统从物理上连续的大小固定的段上进行分配内存按2的幂的大小进行分配满足单元为2的幂的请求；需要调整到下一个更大的2的幂；当需要分配的小于可利用的内存块时将当前块均分成两块；将其中的一块类似进行直到大小合适为止。聚合相邻的伙伴可以很快聚合起来。64Buddy系统分配65Slab分配Slab由一个或多个物理上连续的页组成Cache含有一个或多个slab每个内核数据结构都有一个cache每个cache含有内核数据结构的对象实例，如,信号量，文件对象等；创建cache时包含若干个标记为“空闲”的对象存储内核数据结构的对象时，对象标记为“使用”；如果slab中所有对象标记为“使用”，则下一个对象从空的slab开始如果没有空slab，则分配新的slab。66Slab分配（cont.）优点没有碎片；内存请求可以快速满足。67Slab分配（cont.）688.9其他考虑预调页减少进程初启时页错误的次数；在页被引用前，预先调入全部/部分页面；如果预调入的页是没用的，则造成I/O和内存的浪费；假设预调入s页，其中使用率为α节省s*α页错误的成本是大于还是小于预调入其他s*(1-α)页不必要的页面开销?α

接近于0预调页是失败的；α

接近于1预调页是成功的。698.9其他考虑（cont.）页大小的选择（有许多因素影响页面大小）碎片需要小页页表大小需要大页I/O开销需要大页局部性更小页？更大页？（矛盾）更小的页应用导致更少的I/O和更少的总的分配内存为了降低页错误数量，需要大页。708.9其他考虑（cont.）TLB范围：指通过TLB可访问的内存量TLBReach=(TLBSize)×(PageSize)理想状况下，一个进程所有的工作集合应位于TBL中，否则会带来较高的页错误率增加TLB范围的两种方法增加TBL大小代价较大增加页的大小或提供多种页大小增加页的大小，可能导致碎片的增加提供多种页，要求OS管理TLB718.9其他考虑（cont.）程序结构假设页大小为128个字，分配给进程一个帧intA[][]=newint[128][128];每一行存