1、Chapter 9 Virtual MemorylBackground（背景）背景）lDemand Paging（请求页式）请求页式）Performance of Demand Paging（请求页式的性能）请求页式的性能）Page Replacement（页置换）页置换）Page-Replacement Algorithms（页置换算法）页置换算法）Allocation of Frames（页框的分配）页框的分配）Thrashing（颠簸）颠簸）Other Considerations（其他考虑）其他考虑）9.1 Backgroundl为了在内存空间运行超过内存总容量的大作业为了在内存空间运
2、行超过内存总容量的大作业l或者同时运行大量作业或者同时运行大量作业l解决的方法是从逻辑上扩充内存容量解决的方法是从逻辑上扩充内存容量l这就是虚拟存储技术所要解决的主要问题这就是虚拟存储技术所要解决的主要问题9.1 Backgroundl实现虚拟存储器要解决实现虚拟存储器要解决:程序部分运行可以吗程序部分运行可以吗?发现程序不在内存时发现程序不在内存时,如何将其装入后继续运行如何将其装入后继续运行?内存无空间时怎么办内存无空间时怎么办?9.1 BackgroundlVirtual memory is a technique that allows the execution of process
3、es that may not be completely in memory.（虚拟内存是一种允许进程部分装入内存就虚拟内存是一种允许进程部分装入内存就可以执行的技术）可以执行的技术）principle of locality局部性原理局部性原理:时间局部性，空间时间局部性，空间局部性局部性 Only part of the program needs to be in memory for execution （只有运行的部分程序需要在内存中）只有运行的部分程序需要在内存中）.程序的局部性原理程序的局部性原理l在一段时间内，程序的执行仅局限于某个部分；相应地，它所访在一段时间内，程序的执行
4、仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。问的存储空间也局限于某个区域内。程序在执行时，除了少部分的转移和过程调用指令外，程序在执行时，除了少部分的转移和过程调用指令外，大多大多数仍是顺序执行数仍是顺序执行的。的。子程序调用子程序调用将会使程序的执行由一部分内存区域转至另一部将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过分区域。但在大多数情况下，过程调用的深度都不超过5 5。程序中存在许多程序中存在许多循环结构，循环结构，循环体中的指令被多次执行。循环体中的指令被多次执行。程序中还包括许多对程序中还包括许多对数据结构的处理数据结
5、构的处理，如对连续的存储空间，如对连续的存储空间数组的访问，往往局限于很小的范围内。数组的访问，往往局限于很小的范围内。l时间局部性：时间局部性：由于程序中存在着由于程序中存在着大量的循环操作大量的循环操作某条指令一旦执行，则不久该指令可能再次被执行；某条指令一旦执行，则不久该指令可能再次被执行；某个存储单元被访问，则不久该存储单元可能再次被访问。某个存储单元被访问，则不久该存储单元可能再次被访问。l空间局部性：空间局部性：由于由于程序的顺序执行程序的顺序执行一旦程序访问了某个存储单元，则其附近的存储单元也最有可一旦程序访问了某个存储单元，则其附近的存储单元也最有可能被访问。能被访问。即程序在
6、一段时间内所访问的地址，可能集中在即程序在一段时间内所访问的地址，可能集中在一定的范围内一定的范围内局部性表现局部性表现9.1 BackgroundlLogical address space can therefore be much larger than physical address space（逻辑地址空（逻辑地址空间能够比物理地址空间大）间能够比物理地址空间大）.Need to allow pages to be swapped in and out（必须允许页面能够被换入和换出）（必须允许页面能够被换入和换出）.Virtual Memory That is Larger Tha
7、n Physical Memory9.1 BackgroundlVirtual memory can be implemented via（虚拟内（虚拟内存能够通过以下方法来实现）存能够通过以下方法来实现）:Demand paging（请求页式）（请求页式）Demand segmentation（请求段式）（请求段式）虚拟存储器的特征虚拟存储器的特征l离散性离散性:在内存分配时采用离散的分配方式，是虚拟存储器的最基在内存分配时采用离散的分配方式，是虚拟存储器的最基本的特征。本的特征。l多次性多次性:一个作业被分成多次调入内存运行，即在作业运行时没有一个作业被分成多次调入内存运行，即在作业运行时
8、没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。是虚拟存储器最重要的特征。存即可。是虚拟存储器最重要的特征。l对换性对换性:作业运行过程中信息在内存和外存的对换区之间换进、换作业运行过程中信息在内存和外存的对换区之间换进、换出。出。l虚拟性虚拟性:从逻辑上扩充内存容量，使用户所看到的内存容量远大于从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。实际内存容量。l在分页系统的基础上，增加了请求调页功能、页面置在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储系统换功能所形成的虚拟存储系
9、统l需解决需解决:取页取页-将哪部分装入内存将哪部分装入内存 置页置页-将调入的页放在什么地方将调入的页放在什么地方 淘汰淘汰-内存不足时，将哪些页换出内存内存不足时，将哪些页换出内存9.2 Demand Paging9.2 Demand PaginglBring a page into memory only when it is needed（只有在一个页需要的时候才把它装入内存）只有在一个页需要的时候才把它装入内存）.Less I/O needed（需要很少的需要很少的I/O）Less memory needed（需要很少的内存）需要很少的内存）Faster response（快速响应）
10、快速响应）More users（多用户）多用户）lHardware Support invalid reference（无效的访问）无效的访问）abort（中止）中止）not-in-memory（不在内存）不在内存）bring to memory（换入内存）换入内存）9.2.1 Page table for demand pagingl在分页的页表机制上形成在分页的页表机制上形成l增加若干信息项，供程序增加若干信息项，供程序(数据数据)在换进、换出时参考在换进、换出时参考页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M 外存地址外存地址l状态位（存在位状态位（存在
11、位P）：指示该页是否已调入内存。指示该页是否已调入内存。l访问字段访问字段A：记录本页在一段时间内被访问的次数，或记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。页面时参考。l修改位修改位M：表示该页在调入内存后是否被修改过。表示该页在调入内存后是否被修改过。l外存地址：外存地址：指出该页在外存上的地址，供调入该页时使指出该页在外存上的地址，供调入该页时使用。用。9.2.1 Page table for demand paging9.2.2 Page faultl每当所要访问的页面不在内存时，便产生
12、一缺页中断每当所要访问的页面不在内存时，便产生一缺页中断(page fault)，请求请求OS将所缺页调入内存。将所缺页调入内存。l与一般中断的主要区别在于：与一般中断的主要区别在于：缺页中断机构在指令执行期间产生和处理中断信号，而一般缺页中断机构在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。一条指令在执行期间，可
13、能产生多次缺页中断。9.2.3 Address translation l在分页系统地址变换机构的基础上，增加了在分页系统地址变换机构的基础上，增加了:产生和处理缺页中断产生和处理缺页中断 页面置换功能等页面置换功能等Steps in Handling a Page FaultSteps in handling a page faultl查找页表来确定此次地址访问是否合法查找页表来确定此次地址访问是否合法l如果不合法如果不合法,则中止该进程则中止该进程;否则如果是发生了缺页否则如果是发生了缺页,则则需要将其调入内存需要将其调入内存l找到一个空闲物理块找到一个空闲物理块l启动磁盘启动磁盘,把该页
14、读入内存把该页读入内存l读磁盘结束读磁盘结束后后,修改页表以指出该页已在内存中修改页表以指出该页已在内存中l重新开始执行刚才发生缺页中断的指令重新开始执行刚才发生缺页中断的指令,这时它可以访问这时它可以访问刚才调入的页刚才调入的页What happens if there is no free frame?lPage replacement find some page in memory,but not really in use,swap it out（页置换页置换找到内找到内存中并没有使用的某个页，换出）存中并没有使用的某个页，换出）.Algorithm（算法）算法）Performanc
15、e（性能）性能）want an algorithm which will result in minimum number of page faults（找出一个导致最小缺页数的算法找出一个导致最小缺页数的算法）.Need For Page ReplacementBasic Page ReplacementlFind the location of the desired page on disklFind a free frame:-If there is a free frame,use it -If there is no free frame,use a page replacemen
16、t algorithm to select a victim framelBring the desired page into the(newly)free frame;update the page and frame tables Page Replacement页面调入策略页面调入策略l为能使进程运行，事先需将一部分要执行的程序和数为能使进程运行，事先需将一部分要执行的程序和数据调入内存据调入内存l调入页面的时机调入页面的时机 预调页策略：预调页策略：主动的页面调入策略，即把那些预计很快会被访问的程序主动的页面调入策略，即把那些预计很快会被访问的程序或数据所在的页面，预先调入内存。或数
17、据所在的页面，预先调入内存。预测的准确率不高（预测的准确率不高（50%），主要用于进程的首次调入。），主要用于进程的首次调入。也有的系统将预调页策略用于请求调页也有的系统将预调页策略用于请求调页页面调入策略页面调入策略(续续)l请求调页策略：请求调页策略：当进程在运行中发生缺页时，由系统将缺页调入内存。当进程在运行中发生缺页时，由系统将缺页调入内存。目前虚拟存储器系统大多采用此策略。目前虚拟存储器系统大多采用此策略。在调页时须花费较大的系统开销，如需频繁启动磁盘在调页时须花费较大的系统开销，如需频繁启动磁盘I/O。页面调入策略页面调入策略(续续)l从何处调入页面从何处调入页面 在虚拟存储系统中
18、，外存（硬盘）被分成两部分在虚拟存储系统中，外存（硬盘）被分成两部分:文件区和对换区。文件区和对换区。对换区（连续分配）的磁盘对换区（连续分配）的磁盘I/O速度比文件区（速度比文件区（离散分配）要高。离散分配）要高。页面调入策略页面调入策略(续续)lUNIX系统系统:对于从未运行过的页面，都从硬盘文件区对于从未运行过的页面，都从硬盘文件区(可执行文件可执行文件)调入调入对于被换出的页面，从对换区调入；对于被换出的页面，从对换区调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。从对换区调入。每个作业有一个页表每
19、个作业有一个页表,还有一个与之对应的磁盘描述项还有一个与之对应的磁盘描述项:9.2.4 Performance of Demand Pagingl发生缺页时会导致以下步骤的发生发生缺页时会导致以下步骤的发生:1.陷入陷入OS2.保存该用户寄存器和进程状态保存该用户寄存器和进程状态3.确定该中断是一个缺页中断确定该中断是一个缺页中断4.检查该页面引用是合法的并确定该页在磁盘上的位置检查该页面引用是合法的并确定该页在磁盘上的位置5.将该页从磁盘读入一个空闲物理块将该页从磁盘读入一个空闲物理块:在磁盘等待队列中等待直到该请求被处理在磁盘等待队列中等待直到该请求被处理等待设备寻道延迟等待设备寻道延迟将
20、该块从磁盘传送至内存将该块从磁盘传送至内存6.为了提高为了提高CPU利用率，将利用率，将CPU分派给其他进程使用分派给其他进程使用9.2.4 Performance of Demand Paging(Cont.)7.磁盘磁盘I/O完成，产生中断完成，产生中断8.保存正在执行进程的现场信息（如果第保存正在执行进程的现场信息（如果第6步执行了）步执行了）9.确定中断来自于磁盘确定中断来自于磁盘10.修改页表以示所缺的页已进入内存修改页表以示所缺的页已进入内存11.等待等待CPU再次再次分派分派给这个进程给这个进程12.恢复该进程的现场信息，包括寄存器、进程状态、页恢复该进程的现场信息，包括寄存器、
21、进程状态、页表等，恢复执行表等，恢复执行9.2.4 Performance of Demand Paging(Cont.)l以上步骤并不是在任何情况下都会发生的以上步骤并不是在任何情况下都会发生的l这里主要的动作是：这里主要的动作是：处理缺页中断处理缺页中断 从磁盘读入所需的页从磁盘读入所需的页 重新开始被中断的进程重新开始被中断的进程l其中最大的一部分时间开销为从磁盘读入所需的页其中最大的一部分时间开销为从磁盘读入所需的页 缺页率缺页率l假定作业假定作业Ji共有共有m页，系统分配给它的主存块为页，系统分配给它的主存块为n块，块，这里这里mn。l如果作业如果作业Ji执行过程中总的内存访问次数为
22、执行过程中总的内存访问次数为A,成功成功访问的次数为访问的次数为S，不成功的访问次数为，不成功的访问次数为F(产生缺页中产生缺页中断的次数断的次数),则则:A=S+F 缺页率缺页率:f=F/A9.2.4 Performance of Demand PaginglPage Fault Rate 0 p 1.0（缺页率缺页率0 p 1.0）if p=0 no page faults（如果如果p=0，没有缺页）没有缺页）if p=1,every reference is a fault（每次访问都缺页）每次访问都缺页）lEffective Access Time(EAT)（有效存取时间）有效存取时间
23、）EAT=(1 p)x memory access+p(page fault overhead+swap page out+swap page in +restart overhead)9.2.5 Page-Replacement Algorithmsl在进程运行过程中，如果发生缺页在进程运行过程中，如果发生缺页,而内存中又无空而内存中又无空闲块时，怎么办闲块时，怎么办?将内存中的某一页换到磁盘的对换区将内存中的某一页换到磁盘的对换区l将哪个页面调出将哪个页面调出?根据页面置换算法来确定根据页面置换算法来确定9.2.5 Page-Replacement Algorithmsl置换算法的好坏将直
24、接影响系统的性能，不适当的算法置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生可能会导致进程发生“抖动抖动”（Thrashing)。l抖动抖动:刚被换出的页很快又被访问，需重新调入，导致系刚被换出的页很快又被访问，需重新调入，导致系统频繁地交换页面，以致大部分统频繁地交换页面，以致大部分CPU时间花费在完成页时间花费在完成页面置换的工作上。面置换的工作上。9.2.5 Page-Replacement AlgorithmslGoal:Want lowest page-fault ratelEvaluate algorithm by running it on a particu
25、lar string of memory references(reference string)and computing the number of page faults on that string（通过运行一个内通过运行一个内存访问的特殊序列（访问序列），计算这个序列的存访问的特殊序列（访问序列），计算这个序列的缺页次数）缺页次数）.9.2.5 Page-Replacement Algorithmsl从理论上讲，应将那些以后不再被访问的页面换从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访问的页面出，或把那些在较长时间内不会再被访问的页面换出。换出。l存在
26、多种置换算法存在多种置换算法,都是试图更接近理论上的目标都是试图更接近理论上的目标9.2.5 Page-Replacement Algorithmsl最佳算法最佳算法(OPT:optimal)l先进先出算法先进先出算法(FIFO)BeLady现象现象l最近最久未使用算法最近最久未使用算法(LRU:Least Recently Used)lLRU的近似算法的近似算法9.2.5 Page-Replacement Algorithmsl最佳（最佳（Optimal）置换算法置换算法 选择那些永不使用的，或者是在最长时间内不再被访问的页面置选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。
27、换出去。要确定哪一个页面是未来最长时间内不再被访问的，很难要确定哪一个页面是未来最长时间内不再被访问的，很难 是一种理想化的算法，性能最好，但在实际上难于实现。是一种理想化的算法，性能最好，但在实际上难于实现。通常用来评价其它算法。通常用来评价其它算法。最佳（最佳（Optimal）置换算法）置换算法Page fault:9Page replacement:6 先进先出（先进先出（FIFO）置换算法置换算法Page fault:15Page replacement:12Graph of Page Faults Versus The Number of FramesFIFO Illustratin
28、g Beladys Anomaly 先进先出（先进先出（FIFO）置换算法置换算法BELADY 异常现象：对页面访问序列1 2 3 4 1 2 5 1 2 3 4 5，物理块从3 块增加到4块，缺页次数增加。页面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 4 4 4 5 5 5 2 2 2 1 1 1 3 3 物理块 3 3 3 2 2 2 4 缺页 x x x x x x x x x 发生了6次页面置换，缺页次数9次。页面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 5 5 5 5 4 4 2 2 2 2 1 1 1 1 5 3 3 3 3 2
29、2 2 2 物理块 4 4 4 4 3 3 3 缺页 x x x x x x x x x x Least Recently Used(LRU)AlgorithmPage fault:12Page replacement:9Least Recently Used(LRU)AlgorithmlCounter implementation（计数器实现）计数器实现）Every page entry has a counter;every time page is referenced through this entry,copy the clock into the counter（每一个页表项每一
30、个页表项 有一个时间域，给有一个时间域，给CPU增加一个计数器，每次访问内存，该计数器值加增加一个计数器，每次访问内存，该计数器值加1。如果某一页被访问，则把计数器值拷贝到该页的时间域中）如果某一页被访问，则把计数器值拷贝到该页的时间域中）.When a page needs to be changed,look at the counters to determine which are to change（当需要进行页面置换时，查看页表中当需要进行页面置换时，查看页表中每一页的时间域，选择该值最小的页面换出去每一页的时间域，选择该值最小的页面换出去.）特点特点：每次内存访问时需增加一次写内
31、存（写页表中某一页的时间域）每次内存访问时需增加一次写内存（写页表中某一页的时间域）页面替换时需检索页表以找到时间域最小的页面。页面替换时需检索页表以找到时间域最小的页面。LRU Algorithm(Cont.)lStack implementation keep a stack of page numbers in a double link form（栈实现栈实现用一个双向用一个双向链表实现一个记录页号的栈）链表实现一个记录页号的栈）:Page referenced（被访问的页移到栈顶）被访问的页移到栈顶）栈底的页是最近最少被访问的栈底的页是最近最少被访问的 No search for r
32、eplacement（不用为置换进行查找）不用为置换进行查找）每次把一个页号从栈中移动到栈顶，需修改几个指针每次把一个页号从栈中移动到栈顶，需修改几个指针Use Of A Stack to Record The Most Recent Page References LRU Approximation Algorithms(1)l在页表中设一个在页表中设一个“引用位引用位”，当某一页被访问时，该位由，当某一页被访问时，该位由硬件自动置硬件自动置1l由页面管理软件周期性把所有引用位置由页面管理软件周期性把所有引用位置0l在一个周期在一个周期T内，某些被访问过的页面其引用位为内，某些被访问过的页面
33、其引用位为1，而未，而未被访问过的页面其引用位为被访问过的页面其引用位为0。l当需要置换一页面时，选择其引用位为当需要置换一页面时，选择其引用位为0的页的页LRU Approximation Algorithms(2)lSecond chance 其基本算法是其基本算法是FIFO 实现：实现：FIFO的循环队列的循环队列 Need reference bit.（页表中每一项设置访问位）页表中每一项设置访问位）If page to be replaced has reference bit=1.Then（如果某页的访问位是如果某页的访问位是1，则），则）:set reference bit 0（
34、把访问位设把访问位设为为0）.leave page in memory（把页留在内存中）把页留在内存中）.replace next page subject to same rules（以同样的以同样的规则，处理下一个页）规则，处理下一个页）.如果所有页的访问位都为如果所有页的访问位都为1，则此算法退化为，则此算法退化为FIFO算法算法 LRU Approximation Algorithms(2)Second-Chance(clock)Page-Replacement AlgorithmEnhanced Second chance Algorithml不仅考虑页面的使用情况，还考虑置换代价不
35、仅考虑页面的使用情况，还考虑置换代价 选择淘汰页面时，既要是未被访问的，还要是未被修选择淘汰页面时，既要是未被访问的，还要是未被修改的页面。改的页面。l实现：设置两位实现：设置两位 访问位（访问位（A），），修改位（修改位（M）启动一个进程时，启动一个进程时，A、M置置0 A被定期清零被定期清零Enhanced Second chance Algorithml内存中的所有页面被分成为四类内存中的所有页面被分成为四类:第第0类：无访问，无修改类：无访问，无修改(A=0,M=0)第第1类：无访问，有修改类：无访问，有修改(A=0,M=1)第第2类：有访问，无修改类：有访问，无修改(A=1,M=0)
36、第第3类：有访问，有修改类：有访问，有修改(A=1,M=1)Enhanced Second chance Algorithml算法首先寻找第算法首先寻找第0类页面，将找到的第一个页面淘汰类页面，将找到的第一个页面淘汰l若没找到，则找第若没找到，则找第1类页面，将找到的第一个页面淘类页面，将找到的第一个页面淘汰，并将扫描过的页面的汰，并将扫描过的页面的A位全部置为位全部置为0；l若没找到，则指针回到开始位置，将所有的若没找到，则指针回到开始位置，将所有的A位置为位置为0。然后重复第一步。然后重复第一步。Counting-Based AlgorithmslKeep a counter of the
37、 number of references that have been made to each page.（用一个计数器记录用一个计数器记录对每一个页的访问次数。）对每一个页的访问次数。）LFU Algorithm:replaces page with smallest count（最少最少使用算法：置换计数器值最小的一个页，即访问次数最少的页）使用算法：置换计数器值最小的一个页，即访问次数最少的页）.MFU Algorithm:based on the argument that the page with the smallest count was probably just bro
38、ught in and has yet to be used（最常使用算法，认为：最小计数的页也最常使用算法，认为：最小计数的页也许刚刚被换入和使用，所以置换计数器值最大的页）许刚刚被换入和使用，所以置换计数器值最大的页）.9.2.6 Allocation of Framesl分配和置换策略分配和置换策略 分配策略分配策略 固定分配固定分配 可变分配可变分配 置换策略置换策略 全局置换全局置换 局部置换局部置换Global vs.Local AllocationlGlobal replacement（全局替换）全局替换）process selects a replacement frame f
39、rom the set of all frames;one process can take a frame from another（发生缺页时在内存中所有的页中发生缺页时在内存中所有的页中选择一个替换页面；一个进程可以从另一个进程中获得页面）选择一个替换页面；一个进程可以从另一个进程中获得页面）.lLocal replacement（局部替换）局部替换）each process selects from only its own set of allocated frames（发生缺页时发生缺页时,进程只能从属于它自进程只能从属于它自己的页中选择一页换出去）己的页中选择一页换出去）.l相对
40、而言，全局替换会带来较高的系统吞吐率相对而言，全局替换会带来较高的系统吞吐率9.2.6 Allocation of Framesl固定分配固定分配&局部置换策略：局部置换策略：基于进程的类型（交互型或批处理型等），或根基于进程的类型（交互型或批处理型等），或根据程序员、系统管理员的建议，为每个进程分配据程序员、系统管理员的建议，为每个进程分配固定数目的物理块，在整个运行期间都不再改变固定数目的物理块，在整个运行期间都不再改变 如果进程在运行中发生缺页，只能从该进程已在如果进程在运行中发生缺页，只能从该进程已在内存的页面中选一页换出，然后再调入另一页，内存的页面中选一页换出，然后再调入另一页，保
41、证分配给该进程的内存空间不变。保证分配给该进程的内存空间不变。9.2.6 Allocation of Framesl可变分配可变分配&全局置换策略：全局置换策略：系统为每个进程分配一定数目的物理块，系统为每个进程分配一定数目的物理块，OS本身本身也保持一个空闲物理块队列也保持一个空闲物理块队列 当某进程发生缺页时，系统从空闲物理块队列中，当某进程发生缺页时，系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装取出一物理块分配给该进程，并将欲调入的缺页装入其中。入其中。当空闲物理块队列中的物理块用完时，当空闲物理块队列中的物理块用完时，OS才从内才从内存中选择一页调出，该页可能是
42、任一进程的页。存中选择一页调出，该页可能是任一进程的页。9.2.6 Allocation of Framesl可变分配可变分配&局部置换：局部置换：为每个进程分配一定数目的内存空间，并且在进为每个进程分配一定数目的内存空间，并且在进程运行期间可根据情况（缺页率）适当增加或减程运行期间可根据情况（缺页率）适当增加或减少所分配的物理块数少所分配的物理块数 当某进程发生缺页时，只允许从该进程已在内存当某进程发生缺页时，只允许从该进程已在内存的页面中选出一页换出，而不影响其它进程的运的页面中选出一页换出，而不影响其它进程的运行行9.2.6 Allocation of Framesl 在采用固定分配策略
43、时，可采用以下几种物理块分配在采用固定分配策略时，可采用以下几种物理块分配方法：方法：平均分配：将系统中所有可供分配的物理块，平均平均分配：将系统中所有可供分配的物理块，平均分配给各个进程分配给各个进程 按比例分配：这是根据进程的大小按比例分配物理按比例分配：这是根据进程的大小按比例分配物理块块 根据进程优先级分配根据进程优先级分配Priority AllocationlUse a proportional allocation scheme using priorities rather than size（根据优先级而不是大小来按比率分配的策略）根据优先级而不是大小来按比率分配的策略）.l
44、If process Pi generates a page fault,（如果进程如果进程Pi产生一个缺产生一个缺页）页）select for replacement one of its frames（选择替换其中选择替换其中的一个页框）的一个页框）.select for replacement a frame from a process with lower priority number（从一个较低优先级的进程中选择一个从一个较低优先级的进程中选择一个页面来替换）页面来替换）.ThrashinglIf a process does not have“enough”pages,the
45、page-fault rate is very high.This leads to（如果一个进程没有足如果一个进程没有足够的页，那么缺页率将很高，这将导致）够的页，那么缺页率将很高，这将导致）:low CPU utilization（CPU利用率低下）利用率低下）.operating system thinks that it needs to increase the degree of multiprogramming（OS认为需要增加多道程序设计的道数）认为需要增加多道程序设计的道数）.another process added to the system（系统中将加入一个新的系统中将
46、加入一个新的进程）进程）.lThrashing（颠簸）颠簸）a process is busy swapping pages in and out（一个进程的页面经常换入换出）一个进程的页面经常换入换出）.Thrashing DiagramThrashing Solutionl采用局部置换：若一个进程开始颠簸，则它只能采采用局部置换：若一个进程开始颠簸，则它只能采用局部置换，这样不会使其它进程也发生颠簸用局部置换，这样不会使其它进程也发生颠簸l给进程提供足够的物理块：根据进程执行的局部模给进程提供足够的物理块：根据进程执行的局部模型，来确定进程真正需要多少物理块型，来确定进程真正需要多少物理块
47、Thrashing SolutionlLocality model（局部模型）局部模型）一个一个locality 是一个进程目前的活跃页面的集合是一个进程目前的活跃页面的集合Locality取决于程序的结构和它的数据结构取决于程序的结构和它的数据结构Process migrates from one locality to another（进程从一个局部移进程从一个局部移到另一个局部）到另一个局部）.Localities may overlap（局部可能重叠）局部可能重叠）.lWhy does thrashing occur?（为什么颠簸会发生）为什么颠簸会发生）size of localit
48、y total memory sizel解决：给每个进程分配的最小物理块数不能少于解决：给每个进程分配的最小物理块数不能少于locality 的大小。这样，就的大小。这样，就可以使进程在把它的可以使进程在把它的locality 页全部装入内存之后，不再发生缺页页全部装入内存之后，不再发生缺页Working setl工作集理论是在工作集理论是在1968年由年由Denning提出来的。它正是提出来的。它正是基于局部的假设基于局部的假设。lDenning认为，程序在运行时对页面的访问是不均匀的，认为，程序在运行时对页面的访问是不均匀的，即往往在某段时间内的访问仅局限于较少的若干个页即往往在某段时间内
49、的访问仅局限于较少的若干个页面，如果能够预知程序在某段时间内要访问哪些页面，面，如果能够预知程序在某段时间内要访问哪些页面，并能将它们提前调入内存，将会大大地降低缺页率，并能将它们提前调入内存，将会大大地降低缺页率，从而减少置换工作，提高从而减少置换工作，提高CPU的利用率。的利用率。Working setl基本思想：基本思想：根据程序的局部性原理，进程在一段时间内总是集中根据程序的局部性原理，进程在一段时间内总是集中访问一些页面访问一些页面(活跃页面活跃页面).如果分配给一个进程的物理块数太少了，使该进程的如果分配给一个进程的物理块数太少了，使该进程的活跃页面不能全部装入内存，则进程在运行过
50、程中将活跃页面不能全部装入内存，则进程在运行过程中将频繁发生缺页频繁发生缺页 如果能为进程提供与活跃页面数相等的物理块数，则如果能为进程提供与活跃页面数相等的物理块数，则可减少缺页中断次数可减少缺页中断次数Working setl具体实现：具体实现：OS跟踪每个进程的工作集，并为其分配大于其工跟踪每个进程的工作集，并为其分配大于其工作集的物理块数。作集的物理块数。如果还有空闲物理块，则可启动另外的进程。如果还有空闲物理块，则可启动另外的进程。如果所有进程的工作集之和超过了可用物理块的总如果所有进程的工作集之和超过了可用物理块的总数，数，则则OS会选择暂停一个进程，该进程被换出，会选择暂停一个进
