操作系统原理第3章-存储管理

第三章存储管理1计算机存储器分类外存UserOS内存计算机系统工作中心2本章要点存储管理任务：分配、映射、保护、共享内存划分与分配技术：静态、动态程序装入技术简单存储管理技术虚拟存储管理技术33.1存储管理的任务存储分配地址映射存储保护（MemoryProtection）存储共享（MemorySharing）4存储分配基本任务：管理内存空间的分配与回收（1）分配基本内存空间（2）增加新的内存空间--动态申请或释放内存空间（3）回收内存空间5用于内存管理的数据结构如：位视图、空闲页框表等。记载哪些内存被分配给那个进程，哪些内存空间是空闲的信息。若系统采用虚拟存储管理技术，还需要登记进程的程序和数据中，哪些部分还在内存，哪些部分尚在外存等信息。这些数据结构自身需要占用一定的内存空间，也需要系统花费额外的时间进行维护。6存储分配步骤首先，根据系统的内存分配算法，在空闲的内存分区中寻找到一块满足进程需要的内存空间，将其分配给进程。然后，更新进程的资源分配清单、内存分配情况清单等数据结构。7内存的回收更新相应的数据结构，将回收的内存空间标识为“空闲可用”。？该内存空间是否可以被回收？被其他进程共享？属于相应的进程？与相邻的空闲空间进行合并8地址映射逻辑地址，或相对地址：一般从0开始编址物理地址，或绝对地址：标识内存中的每个存储单元。进程控制块程序数据栈进程控制信息程序入口点地址值增加进程映像分支指令访问数据当前栈顶图3.1进程执行时的寻址9？逻辑地址高级语言或汇编语言使用符号地址：变量名或标号源程序经过编译、链接以后，其中的符号地址就会变成数字式的逻辑地址。编译/链接程序会自动计算每一个变量或标号所对应的逻辑地址是多少。10静态映射：静态重定位地址映射：程序装入内存以后，由操作系统将逻辑地址逻辑地址+起始地址，得到实际的物理地址。重定位（Relocation）：对目标程序中的指令和数据地址进行修改的过程。静态映射实现简单。地址变换只在程序装入是一次完成，程序运行时不再改变。但不适合多道程序系统：不允许系统执行内存的碎片整理；无法实现虚拟存储。11动态映射：动态重定位定义：操作系统将程序装入内存以后，并不立即把目标程序中的逻辑地址转换为物理地址，而是在处理机执行每一条指令时进行地址转换。复杂、费时为了系统效率，处理机中设置了专门的高速硬件，自动完成地址转换，这样的硬件被称作地址管理部件，如下图。12CPU中的地址管理部件CPU地址管理部件程序指令逻辑地址物理地址地址总线图3.2CPU中的地址管理部件工作示意图13存储保护防止地址越界，防止操作越权。地址越界：进程访问不属于自己的地址空间，或进程在运行时所产生的物理地址超越其自身的地址空间范围。--可能侵犯其他用户进程空间，也可能侵犯操作系统的存储空间操作越权：进程对共享存储区的操作违反了系统规定的权限14存储保护的实现存储保护只能在进程执行过程中动态地进行，不能在运行前一次性静态完成。若采用动态映射动态计算物理地址，可能计算出错误地址；若采用静态映射，进程执行过程中也可能出错，从而导致地址越界或操作越权。为提高系统效率，存储保护的主要工作必须由高速的专用硬件完成：在地址管理部件中。15存储共享为了进程通信和节约内存空间，两个或多个进程共用内存中相同的分区，即他们的物理空间有相交的部分。可以共享进程的代码，也可以共享进程数据。一般地，进程之间共享代码的目的主要是为了节约存储空间，共享数据的目的主要是为了实现进程间相互通信。16存储共享示意图PCB3数据代码PCB2代码数据PCB1数据代码进程1进程2进程3图3.3进程之间共享代码和数据17存储共享实现通信的模式通过存储共享完成通信的过程：一个进程将数据写入共享存储区，另一个进程从共享存储区中读出数据。18共享代码程序可重入：设计程序时，逻辑上将程序代码区和数据区分开。代码区不包含运行程序时需要改变的数据，被处理的数据都放在独立的数据区。这样，进程执行过程中就不会改变代码部分的任何内容。数据区是单独的一个段、堆栈式动态申请的分区，或通过参数传递。19共享代码—实现过程创建新进程时，不需要为该进程的代码部分另外申请内存空间，只需将该进程PCB中的进程代码空间的地址指向已有的代码空间地址。进程的数据区，要么等到操作系统为其分配相应存储空间以后，将数据区地址填写在PCB中；要么由进程运行时向操作系统动态申请。20共享代码—实质可以将进程的代码视为处理数据的一组规则或公式，这一组规则或公式存储在内存中的某个分区。进程的执行：利用这一组规则或公式来完成数据的运算。多个进程共享代码：多个进程需要使用同一组规则或公式处理不同的数据。PCB：告诉进程其所需的规则或公式以及需要处理的数据存储在哪里，进程的进度等信息。21共享代码—高级语言程序编程对于高级程序的设计而言，只要相应的编译程序支持可重入的程序设计，那么，设计程序时就不需要考虑程序的可重入问题，不需要将程序代码和数据严格分开。编译程序在编译时，会自动将欲处理的数据与程序代码分开存储，以保证代码部分是纯的、可重入的。22存储扩充内存：速度快、容量小、价格贵。外存：容量大、速度慢、价格便宜。目的：在多道程序系统中能运行更多、更大的程序，降低系统的造价，提高系统的性价比。存储扩充：采用软件手段，在硬件的配合下，将部分外存空间虚拟为内存空间，并将内存和外存有机地结合起来，得到一个容量相当于外存、速度接近于内存、价格十分便宜的虚拟存储系统。23存储扩充—虚拟存储实现过程虚拟存储系统在逻辑上对外是一个整体，用户感觉到系统提供了一个非常大的“内存”空间。操作系统负责完成内存与外存之间的透明切换：进程运行时将需要的数据或代码从外存装入内存，并将内存中暂时不用的部分交换到外存。243.2内存划分与分配技术25内存划分静态划分：划分预先进行，创建新进程时，在内存中找到一个合适的分区分配给它。动态划分：系统初始化时，可以将整个内存的用户区看作一个分区。创建新进程时，根据进程申请的空间大小，在这个分区中动态地为之划分一部分空间。26静态划分必须事先进行，一旦划分完毕，分区的大小和数目将不再改变。可以划分：大小相同/不同的分区，如固定分区和分页。固定分区：根据系统管理员的经验和一些统计规律，事先将内存空间划分为若干个固定大小的分区，称为分区(Partitioning)。当进程申请存储空间时，系统为之分配一个大小合适的空闲分区。27静态划分（续）分页：特殊的静态分区，需要事先将内存空间划分为若干个大小相同的分区，称为页框，或帧（frame）。当进程申请存储空间时，系统可以为之分配多个空闲页框。28固定分区划分：等长8MB8MB8MB8MB8MB操作系统8MB(a)等长分区图3.4固定分区划分29固定分区：等长—总结所有分区的长度相同。优点：分配简单，只要进程大小不超过分区大小，就可以装到任何一个分区中运行。浪费存储空间。若进程申请的存储空间很小，却需要占用整个分区，分区内存在不可用的浪费空间，称为内零头—碎片（internalfragmentation）。无法运行超过分区大小的程序。无法精确确定分区的大小。30固定分区划分：异长图3.4固定分区划分操作系统8MB2MB8MB4MB12MB20MB(b)异长分区31固定分区：异长将内存空间划分为若干个长度不同的分区，以适合于不同大小的进程需要既提高存储空间的利用率、减少浪费，又使长进程能装入运行。但是，确定每个分区的大小也是一件十分困难的事情。32固定分区特点管理简单，只需要建立一张分区使用表，登记分区的使用情况。（等长分区只需要标明分区状态是已分配/空闲）分区号(可省略)大小起始地址状态12040未分配25060已分配350110未分配4100160已分配5200260已分配33固定分区：分配首先，检索分区使用表，从中找出一个尚未分配的、能满足大小且内零头最小的分区。若分区使用表中的分区按从小到大的顺序排列，则分配时，从表中的第一个表项开始查找，找到的第一个尚未分配并满足大小的分区即是最佳的分区。将分区使用表中该分区的状态修改为已分配。若找不到大小足够的分区，则系统将拒绝运行该进程，或采用其它技术进行处理，如覆盖技术等。34固定分区总结固定分区存在内零头，浪费存储空间：异长分区较等长分区可以一定程度上提高系统的性能，但并不能彻底解决问题。35分页式划分（Paging）为了提高内存资源的利用率，可以考虑将分区长度缩小，减少内零头浪费的空间。但是，这样做必须有一个前提，即进程可以分配若干不连续的存储空间。否则，小分区可能使更多的进程无法装入内存。分页划分：系统预先将内存空间划分为若干较小的、固定大小的页框。36分页式划分示意图150213内存页框号图3.5分页式划分37分页式划分特点页框较小，有效地减少了内零头的浪费每个进程平均浪费0.5页框大小。页框大小固定，简化了存储分配。需要记录内存页框的分配和使用情况：位示图、空闲页框表或空闲页框链表等。38分页：数据结构—位示图位示图：是一个由0、1构成的向量，其中每一位(bit)表示一个页框的使用状态。一般规定，0表示页框空闲，1表示页框已被分配。假定存储空间被划分为n个页框，所有页框依次编号为0,1,2,…,n-1，则记录所有页框的使用状态的位示图形如：000001110111111111110001111…00111139分页：数据结构—空闲页框表空闲页框表：以表格形式记载内存页框的使用情况。显然，为每一个空闲页框设置一个表项是不合理的，这将导致页框表太大。可以为一组连续的空闲页框设置一个表项，其中主要包括：首页框号和页框个数，如表3.2所示。40空闲页框表首页框号页框个数501002203030080450210表3.2空闲页框表41分页：数据结构—总结位示图和空闲页框表都需要占用专门的存储空间空闲页框链表：是将内存中所有的空闲页框通过其内的链接指针连成一个链表，系统只需要记录链表头的位置。为进程分配存储空间时，从链表头开始取所需的页框，同时更新链表头。回收进程释放的存储空间时，将新产生的空闲页框链接到空闲页框链表中。42动态划分与分配算法静态划分未考虑进程的实际需要。无论是固定分区，还是分页，都存在不同程度的内零头。动态划分：根据进程的实际需要，动态地划分内存空间，并分配给进程，彻底解决了内零头问题。系统初始化时，内存用户区就是一个大分区。随着进程的创建和撤消，内存被动态划分成若干较小的分区。43动态划分（续）例如，如图3.6有一个128MB的内存，其中操作系统自身占用8MB，剩下的120MB空间供用户进程使用。依次装入进程P1、P2、P3、P4、P5、P6，剩下一个10MB的空闲分区。一段时间之后，进程P1、P3、P5执行结束，释放出3个空闲分区。内存中共有4个空闲分区，44图3.6动态划分内存空间的过程(a)分配之前OS8MB120MB(b)分配之后OS8MBP210MBP140MBP410MBP320MBP620MBP510MB10MB(c)P1、P3、P5结束OS8MBP210MBP410MBP620MB40MB20MB10MB10MB例：动态划分45动态划分—空闲分区表可见，动态分区的分区长度和数目都是可变的。为了实施存储分配，系统必须维护一张空闲分区表，登记内存中的各个空闲分区。空闲分区首址空闲分区长度80120270404009051020046外零头—独立小分区：紧凑动态划分技术解决了静态划分技术的内零头。可能产生很多较小的分区：外零头(ExternalFragment)。紧凑(Compaction)：把内存中的所有空闲分区拼接成一个较大的空闲分区。即把内存中的所有进程移到内存的某一端；所有空闲分区移到另一端例如，将如图3.7(a)所示的内存空间进行紧凑以后的效果见图3.8所示。47图3.8利用紧凑技术消除外零头(a)紧凑之前24MB10MBOS8MBP716MBP210MBP410MBP610MB20MB10MB(b)紧凑以后64MBOS8MBP716MBP210MBP410MBP610MB紧凑技术示意图48动态划分—分配算法采用动态划分技术，为进程分配存储空间的过程较复杂。当系统中有多个满足进程大小的空闲分区时，如何为进程选择一个分区合适的分区呢？目前几种较典型的分区分配方案：49首次适应算法

(FFA：FirstFitAlgorithm)基本思想：总是从内存的某一端（一般从低地址端）开始查找，选择一个超过进程申请大小的空闲分区。为此，可以将空闲分区表中登记的空闲分区按照其起始地址由小到大的次序依次排列。系统查找空闲分区时，从表头开始查找，取第一个满足要求的分区分配给进程。50首次适应算法（续）

(FFA：FirstFitAlgorithm)若找到的空闲分区恰好与进程申请的存储空间大小相等，或分配给该进程以后，仅剩下一个非常小的空间（小于系统设置的阈值），则将该分区全部分配给申请进程。否则，系统将该分区划分为两个分区，一个分区的长度等于进程申请的空间大小，并将其分配给申请进程。然后，将另一个子分区链接到空闲分区链表中。51首次适应算法—总结

(FFA：FirstFitAlgorithm)优点：尽量使用低地址空间，因而在高地址的空间可能会保留较大的空闲分区。所以，大进程申请的存储空间大都能在高地址端得到满足。缺点：由于每次只简单地使用找到的第一个分区，结果可能导致将较大的空闲分区不断地分割为较小的空闲分区。52下次适应算法

(NFA:Next-FitAlgorithm)首次适应算法每次都从低地址端开始查找空闲分区，总是频繁使用内存的某一端，某些大进程申请的大分区需要很长时间才能在内存的另一端找到。能否均衡使用整个内存空间，加快大分区的查找速度呢？下次适应算法能记住上次分配分区的位置，下一次实施分配时，从上一次的分配位置之后开始查找，选择一个大小足够的空闲分区。

53下次适应算法—总结

(NFA:Next-FitAlgorithm)该算法常常会导致内存中缺乏大分区，因为它会均衡地利用空闲分区，包括分割较大的空闲分区。从而使得大进程无法装入内存运行。下次适应算法可能会导致大量的外零头，需要较频繁地实施紧凑操作。54最佳适应算法

(BFA：BestFitAlgorithm)总是选择满足申请要求且长度最小的空闲分区。为了提高查找效率，可以将所有的空闲分区按照长度由小到大的次序依次排列在空闲分区表中。为进程分配存储空间时，从表头开始查找，第一个满足进程申请存储空间大小的分区就是最适合的分区。55最佳适应算法—总结

(BFA：BestFitAlgorithm)优点：尽量不分割大的空闲分区缺点：可能会形成大量较小的、难以再分配的分区——大量的外零头。最佳适应算法并非是最好的算法。56最差适应算法

(WFA：WorstFitAlgorithm)选择满足申请要求且长度最大的空闲分区，使分割出来的剩余空闲分区较大。为了提高系统效率，可将系统中所有的空闲分区按照长度由大到小的次序依次排列在空闲分区表中。为进程分配存储空间时，从表头开始查找，选择第一个满足进程需要的分区。如果第一个空闲分区小于进程申请空间的大小，则不能立即为进程分配存储空间。57最差适应算法—总结

(WFA：WorstFitAlgorithm)优点：可以避免形成大量较小外零头，但它总是分割大的空闲分区。当遇到大进程申请大空间时，无法找到一个足够大的空闲分区。注意：在大进程面前，内存中所谓的较大空闲分区也是外零头了。58例如当系统进行到如图3.6(c)所示的情形时，若有一个进程P7申请大小为16MB的存储空间。分别采用上述4种算法进行分配，如图所示，分析结果。59图3.7动态划分的4种分配算法(a)FFA或WFA24MB10MBOS8MBP716MBP210MBP410MBP610MB20MB10MB(b)NFA24MB10MBOS8MBP716MBP210MBP410MBP610MB20MB10MB此次分配位置上次分配位置(c)BFA10MBOS8MBP210MBP716MBP410MBP610MB10MB40MB4MB例：动态划分四种算法对比60伙伴系统(BuddySystem)静态划分方案限制了系统中活跃进程的数目。并且，只能运行不超过分区大小的进程，如果进程远远小于分区大小，则内存空间的利用率非常低。动态划分方案使存储管理复杂化，并且需要系统付出紧凑外零头的额外开销。伙伴系统：综合静态划分技术和动态划分技术的优点61伙伴系统内存的用户可用空间为2u。系统总是为进程分配大小为2i的一个空闲分区。其中m≤i≤U，2m是系统允许的最小分区尺寸。如果进程申请的存储空间大小为k，且2i-1＜k≤2i,则将整个2i大小的分区分配给它。否则，该分区被分割成大小相等（2i-1）的两个分区。再判断k是否满足条件：2i-2<k≤2i-1,若满足条件，则将两个伙伴中的任何一个分配给进程；否则，将其中一个伙伴又平均分成两个分区。此过程一直继续进行，直到产生的分区大于或等于k，将其分配给进程。

伙伴系统—设计思想62

伙伴系统—存储分配进程申请大小为k的空间，系统为之分配一个2i的空闲分区，其中，2i-1＜k≤2i若k＞2u，即进程>内存空间，失败；若当前无尺寸为2i的空闲分区，则：(1)将i变为i+1，查找一个尺寸为2i+1的空闲分区。若存在，转(2)执行;否则，继续执行(1)；⑵等分2i+1空闲分区:产生两个2i的伙伴分区；⑶把其中一个2i的伙伴分区作为空闲分区；(4)另一个2i空闲分区分配给进程，结束。63伙伴系统—空间回收

当进程执行完毕，释放一个尺寸为2i的分区时，系统用下面的算法回收该分区：如果被回收分区的伙伴分区非空闲，那么保留该分区为一个独立的空闲分区，否则[1]合并回收分区及其伙伴分区，从而得到一个尺寸为2i+1的空闲分区；[2]系统再次调用本算法回收上一步得到的尺寸为2i+1的空闲分区。64例如—伙伴系统有进程P1、P2、P3、P4、P5相继申请、释放空间。系统分配、回收（合并）伙伴分区的过程如图所示：65P1申请100KBP2申请200KBP3申请120KBP4申请300KB系统初始状态P2、P3结束P5申请160KBP1执行结束P5执行结束P4执行结束1MBP1128KB256KB512KBP1128KBP2512KBP1P3P2512KBP1P3P2P4P1128KB256KBP4P1128KBP5P4256KBP5P4512KBP41MB图3.9一个伙伴系统的内存分配与回收过程663.3程序装入技术67可执行程序的生成步骤图3.10高级程序处理过程源程序目标模块编译库函数装入模块链接编辑执行目标模块内存68可执行程序的装入？如何装入待执行的程序及其所需的数据？何时将程序的逻辑地址转换为物理地址3种装入方式：绝对装入、重定位装入和运行时动态装入。

69绝对装入程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定的地方。优点：实现简单，无须进行逻辑地址到物理地址的变换。70绝对装入（续）缺点：程序每次必须装入同一内存区；程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；程序的修改（增加或删除指令）将引起整个程序中指令地址的变动；程序中的所有存储引用，例如函数调用或过程调用等，在装入之前都必须转换为物理地址，这不利于存储共享。71重定位装入允许将程序装入与逻辑地址不同的物理内存空间。即程序可以装入到内存的任何位置，其逻辑地址与装入内存后的物理地址无直接关系。但是，必须进行地址映射，将逻辑地址转换为物理地址。静态重定位技术：地址映射在程序装入时进行，以后不再更改程序地址。72重定位装入（续）有利于程序代码和数据的共享。因为装入程序时，可以将其中的某些存储引用的逻辑地址映射为内存中已有的共享区的物理地址。但是，静态重定位不允许程序在内存中移动。这不便于进程交换和紧凑拼接操作，也很难实现多道程序环境下，多个程序同时装入内存的要求。所以，重定位装入方式只适合于单道程序环境。73运行时动态装入定义：程序的地址转换不是在装入时进行，而是在程序运行时动态进行。运行时动态装入需要硬件支持，即重定位寄存器，用于保存程序在内存中的起始地址。程序被执行时，通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地址。运行时动态装入有利于多道程序环境下，进程的换进/换出及实现紧凑技术。

74可执行程序的链接形成？目标模块如何链接成装入模块呢静态链接动态链接：装入时动态链接和运行时动态链接75静态链接定义：程序被装入内存之前，必须完全链接成一个装入模块，将其中的存储引用全部转换为相对地址跳转语句。并将多个目标模块链接成为一个模块，使装入模块中的每一条指令具有相对于整个模块的第一条语句的逻辑地址。静态链接生成的装入模块可以采用重定位装入或运行时动态装入方式。静态链接需要花费大量的处理机时间。而其中的很多模块将不会运行，浪费存储空间和处理机时间。

76链接图3.11目标模块链接成装入模块模块1…ifx>1thencallmm1elsecallmm2…模块mm1模块mm2(a)目标模块模块1…ifx>1thenelse…模块mm1模块mm2(b)装入模块？执行？执行77动态链接定义：不用事先链接所有目标模块形成一个完备的装入模块，而是生成一个含有未被链接的外部模块引用的装入模块，这些外部模块可以在装入时链接，或运行时链接。78装入时动态链接定义：当系统装入含有未链接的外部模块引用的装入模块时，每当遇到一个外部模块引用，则查找相应的目标模块。将其装入内存，并将模块内的指令地址转换为相对于整个装入模块起始地址的相对地址。优点：有利于目标模块的更新与升级；有利于代码共享；有利于扩充软件的功能--可以将扩充部分作为动态链接模块。但是，可能链接一些不会执行的模块，浪费存储空间和处理机时间。79运行时动态链接定义：外部模块引用直至程序执行时才装入内存，并链接到装入模块中，进行地址转换。可以解决静态链接和装入时动态链接都面临的存储空间和处理机时间浪费问题，不需要执行的模块就不会装入内存。广泛用于事务处理系统，如航空售票系统、银行管理系统等。另外，操作系统自身的一些特殊处理例程，如错误处理例程，也无需事先全部装入内存。803.4简单存储管理技术

81简单存储相对于虚拟存储而言，指为了实现简单，执行之前，操作系统必须将待执行的程序全部装入内存。然而，现代操作系统大都支持虚拟存储功能，允许进程装入部分程序即可开始执行，其余部分保留在外存。当执行所需的部分不在内存时，中断进程执行，使之阻塞等待，直到相应部分装入内存。82？程序在内存中如何组织连续存储:需要内存中的一块连续的、足够大的分区。如果内存中没有足够大的连续空闲分区，但存在总量足够的独立小分区，即外零头。系统要么拒绝分配空间，要么采用紧凑技术拼接外零头或采用交换技术。83？程序在内存中的组织（续）非连续存储：允许进程的程序和数据分别装在内存的不同分区中。但，必须登记一个进程分到的所有分区的位置、大小、使用情况（如是否共享等）等信息。常用的非连续存储技术：分页存储技术、分段存储技术及其结合—段页式技术。84图3.12内存的连续存储与非连续存储…OS进程P…基地址(a)连续存储进程P（2）…OS…进程P（1）…进程P（n）…进程的组成基地址长度…P(1)2604200…P(2)1240300……………P(n)6500300…(b)非连续存储85连续存储管理最简单的存储管理技术要求系统配置专门的硬件实现快速地址转换和存储保护。处理机硬件基址寄存器(Baseregister)界限寄存器(Boundsregister)86连续存储管理（续）

基址寄存器：存放当前执行进程所在分区的物理存储单元的起始地址。界限寄存器：存放当前执行进程所在分区最后一个物理存储单元的地址，限定进程的执行范围，保护其他进程不被非法访问。基址寄存器和界限寄存器被多个进程共享，只有当前执行进程才使用它们。87装入时，进程分区的基地址值和分区的最后一个物理存储单元的地址值，分别填入该进程PCB的相应字段中。当进程被调度执行时，将PCB中对应的进程基地址值写入基址寄存器中，并将进程获得的内存分区最大地址值，填入界限寄存器中。当进程被交换出/换入内存时，上述两个地址值也会发生改变。

连续存储管理（续2）

88地址映射与存储保护逻辑地址转换成物理地址—取基址寄存器中的值，加上逻辑地址值，生成一个物理地址。地址越界检查—取界限寄存器中的值，与第一步计算的结果进行比较。如果生成的物理地址超出了界限范围，产生一个中断，报告地址越界。否则，继续该指令的执行。89程序部分数据部分内存基址寄存器加法器逻辑地址界限寄存器比较器越界中断物理地址图3.13连续存储管理的地址转换和越界检查90简单分页存储管理–非连续连续存储：存在外零头，浪费存储空间。“紧凑”需要系统额外开销。非连续存储：允许将一个进程的程序和数据离散存储在多个独立的分区中，消除了外零头。

91分页式存储--基本原理

分页存储管理技术是一种特殊的固定分区方法。系统事先将物理内存划分成许多尺寸相等的页框(PageFrame)，并将进程分割成许多大小相同的页面(Page)，页面与页框大小相同。92分区：进程的逻辑地址空间是连续的、一维的、线性地址，进程的每一条指令和数据的地址相对于第一条语句的地址而定。分页：进程被分割成许多页面。每个页面内的指令和数据是连续的，它们的地址相对于其所属页的第一条语句的地址，称为页内偏移量。（分页）逻辑地址被分为两部分：页号和页内偏移量

页号页内偏移量151090图3.14分页管理的逻辑地址表示93程序装入过程当一个进程被装入物理内存时，系统将为该进程的每个页面分配一个独立的页框。同一个进程的多个页面不必存放在连续的多个页框中，并利用相应的数据结构将所分配到的每个页框信息登记下来。94例如—分页系统假设内存能提供16个空闲页框，进程P1被分割成4个页面，装入内存中的0号至3号页框。进程P2被分割成3个页面，装入4号至6号页框。进程P3被装入7号至12号页框，如图3.15(a)所示。此时，进程P4请求分配5个页框大小的存储空间，但内存只有3个空闲页框。于是，将暂时不运行的P2交换出内存，如图3.15(b)所示。然后，再将P4装入4、5、6、13、14号页框，如图3.15(c)所示。

95图3.15进程装入到离散的页框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5页框号内存(a)依次装入P1、P2、P3P1P2P3空闲0123456789101112131415P1.2P1.1P1.0P1.3P3.0P3.1P3.2P3.3P3.4P3.5页框号内存(b)换出P2P1空闲P3空闲0123456789101112131415P1.2P1.1P1.0P1.3P4.0P4.1P4.2P3.0P3.1P3.2P3.3P3.4P3.5P4.3P4.4页框号内存(c)装入P4P1P4P3空闲P496分页系统数据结构：页表页表：系统为每个进程建立一张页面映射表。用于记载进程的各页面到物理内存中页框的映射信息。进程的每个页面依次对应页表中的一个表项，其中包含相应页在内存中对应的物理页框号和页面存取控制权限等字段。97页号页框号00112233进程P1页表页号页框号0-1-2-进程P2页表页号页框号071829310411512进程P3页表页号页框号041526313414进程P4页表图3.16进程P1、P2、P3、P4的页表示意图例如：页表98数据结构：页框表空闲页框表：登记系统中剩下的空闲页框情况图3.17Fig3-15a的空闲页框表示意图15141399地址变换硬件--实现逻辑地址到物理地址的转换分页系统中的地址变换过程如下：（1）

根据逻辑地址,计算出页号和页内偏移量；（2）

用页号检索页表，查找指定页面对应的页框号；（3）

根据页框号和页内偏移量，计算出物理地址。100页表寄存器页表寄存器：实现快速地址映射，存储执行进程的页表起始地址。页表寄存器设置在处理机硬件中。当进程被创建时，其页表起始地址记载于进程PCB中。当进程被调度执行时，页表的起始地址将从该进程的PCB中取出，并填入页表寄存器中。进行地址变换时，处理机从页表寄存器中查找页表的地址。101页号偏移量逻辑地址物理地址页框号偏移量页表寄存器页表起始地址内存页框号页表地址转换程序+偏移量图3.18分页系统的地址变换过程页框102大页表大逻辑地址空间，页表非常大，需要占用相当大的内存空间。比如，32位逻辑地址空间，假设页面大小为4KB（212），则4GB（232）的逻辑地址空间将被划分成220个页面。103大页表（续）若采用一级页表，则其内将包含1兆（220）个页表项。若按字节寻址，一个页表项占4B，则一级页表需要占用4MB（222）内存空间。不可能将4MB的页表保存在一个连续区中。那么，如何处理大页表的存储与检索呢？104二级页表将一个大页表全部保存在内存中。首先，将其分割，并离散地存储在内存的多个页框中。为之建立二级页表，记录被分割的各个页面存储在哪些页框中，也称为外层页表（OuterPageTable）。对于4GB的进程，若采用二级页表，则对应的二级页表结构如图：105……4GB的用户进程4MB的一级页表4KB的二级页表图3.194GB进程的二级页表结构106多级页表对于某些机器，二级页表也可能非常大。可以采用多级页表，对外层页表再进行分页，将各个页面离散地存储到不相邻接的物理页框中虽然，对大页表而言，多级页表方法消除了对较大的连续内存空间的需要，但并未解决大页表占用较大的内存空间的问题，建立多及页表反而会增加额外的存储空间。107大页表—解决方案最好的解决办法是采用虚拟存储技术，内存中仅装入页表的一部分。即只将当前需要的部分页表项装入内存，其余页表项驻留在磁盘上，需要时再将它们装入内存。若采用多级页表，对于正在运行的进程，必须将其外层页表调入内存（全部），而内层页表只需调入几页就可以了（部分）。108反置页表--(InvertedPageTable)一般情况下，系统从进程的角度为每个进程建立一张页表，页表的表项按页号排序。这种方法可能导致一个大进程的页表太大，占据大量的内存空间。反置页表：从内存的角度建立页表，整个系统只有一张页表。页表的表项基于内存中的每一个物理页框设置，页表项按页框号的顺序排序。其中还必须包含页框对应的页号及其隶属进程的标识符等信息。109反置页表（续）通常，反置页表需要包含成千上万个表项，利用进程ID和页号检索其中某一个表项的速度很慢。可以根据进程ID和页号构建Hash表。Hash表的每一项指向反置页表中的某一项。但是，可能会出现多个逻辑地址被映射到一个Hash表项的情况。需要通过链接指针将多个冲突的映射链接起来。一般，冲突的表项一般只有一项，或两项。

110反置页表--地址变换首先，以进程ID和页号为参数，代入Hash函数进行计算。然后，根据计算结果，检索反置页表。若检索完整个反置页表都未找到与之匹配的表项，表明此页尚未装入内存。若系统支持虚拟存储技术，则产生中断--请求调页。若系统不支持虚拟存储技术，则表示地址出错。当检索到反置页表中的对应表项时，将其中的页框号与逻辑地址中的偏移量相加，构成物理地址。

111图3.20利用反置页表进行地址变换

物理地址偏移量页框号逻辑地址偏移量页号HashHash表页号进程ID指针页框号反置页表112快表分页系统：处理机每次存取指令或数据至少需要访问两次物理内存—第一次访问页表，第二次存取指令或数据，大页表可能访问次数更多。为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表、TLB(TranslationLookasideBuffer)，或联想存储器（AssociativeMemory）

113快表的工作原理快表的工作原理类似于系统中的数据高速缓存(cache)，其中专门保存当前进程最近访问过的一组页表项。根据局部性原理，在一个很短的时间段内，程序的执行总是局部于某一个范围。即，进程最近访问过的页面在不久的将来还可能被访问。114分页系统地址转换首先，通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项。若快表中存在该表项，称为命中（hit），取出其中的页框号，加上页内偏移量，计算出物理地址。若快表中不存在该页表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的页框号，并计算物理地址。同时，更新快表，将该表项插入快表中—快表已满？？？。115图3.21具有快表的分页系统地址变换过程页号偏移量逻辑地址物理地址页框号偏移量偏移量内存快表页框号页表页框TLB命中命中失败116页面与页框大小分页系统中，页面=页框。页框的大小由计算机的硬件逻辑定义。通常，页框的大小是2的幂次个字节，且常在512B（29）～4KB（212）之间，典型的页框大小为1KB。将页框大小设置为2的幂次，可以简化处理机中地址变换硬件逻辑的设计与实现—逻辑地址<->页号、偏移量，页框号、偏移量<->物理地址。117页面与页框大小（续）影响页面与页框大小的主要因素：页内零头、地址转换速度和页面交换效率。较小的页面有利于减少内零头，从而有利于提高内存的利用率。然而，较小的页面也将导致页表过大，从而降低处理机访问页表时的命中率(HitRate)。块（内外存数据交换单位）越大，内/外存之间的数据交换效率越高。因此，对于支持交换技术的系统，较大的页面有利于提高页面换进/换出内存的效率。118分页存储管理—总结彻底消除了外零头,仅存在很少的内零头,提高了内存利用率。分页操作由系统自动进行,一个页面不能实现某种逻辑功能。用户看到的逻辑地址是一维的，无法调试执行其中的某个子程序或子函数。采用分页技术不易于实现存储共享，也不便于程序的动态链接。119简单分段存储管理基于模块化程序设计时，常常需要将一个大任务划分成若干相对独立的子任务，对应于子任务编写子程序，称为段(Segment)。每个子程序可以独立地编辑、编译、链接和执行。各个子程序由实现的功能决定，长度各不相同。执行时，根据实际需要，将若干子程序链接成一个大程序。120基本原理—分段管理程序由若干逻辑段组成，每个段有自己的名字和长度。程序的逻辑地址是由段名（段号）和段内偏移量决定。每个段的逻辑地址从0开始编址。段号段内偏移量151090图3.22分段管理的逻辑地址表示121基本原理（续）系统采用动态划分技术，将物理内存动态地划分成许多尺寸不相等的分区（Partition）。当一个进程被装入物理内存时，系统将为该进程的每一段独立地分配一个分区。同一进程的多个段不必存放在连续的多个（小）分区中。122分段系统的基本数据结构段表:每个进程建立一个，用于描述进程的分段情况，记载进程的各个段到物理内存中分区的映射情况。其中包含段号、段长、段基址以及对本段的存取控制权限（共享）等信息。空闲分区表:用于记载物理内存中的空闲分区情况注意：由于分段基于分区，因此分区管理中的空闲分区管理数据结构同样适用于分段管理的空闲分区管理。123图3.23分段存储示例…P2.1P1.0P1.2P1.1…P2.0(a)分段存储0500100执行存取控制段基址段长段号1200800只读22001000执行(b)进程P1的段表01001200执行存取控制段基址段长段号1200600执行(c)进程P2的段表124地址变换和存储保护—步骤

（1）根据逻辑地址中的段号检索进程段表，获得指定段对应的段表项；（2）判断是否地址越界。比较逻辑地址中的段内偏移量与段表项中的段长，若超过段的长度，则产生存储保护中断（该中断将由操作系统进行处理）；否则，转（3）；（3）把逻辑地址中的段内偏移量与段表表项中的段基址相加，从而得到物理地址。125段表寄存器段表同样被保存在物理内存中。段表寄存器：实现快速地址变换，用来存放当前执行进程的段表在物理内存中的起始地址。当创建进程，将进程的程序和数据装入内存时，系统为之建立段表，并将段表的起始地址填入进程的PCB中。当进程被调度执行时，取出其PCB中的段表首地址，填入段表寄存器中。126图3.24分段系统的地址变换过程内存物理地址段基址+偏移量偏移量段号偏移量逻辑地址段表寄存器段表起始地址+段表段长段基址+越界判断中断越界正常段段127分段系统的快表在分段系统中，为了访问内存中的一条指令或数据，需要两次访问内存：—第一次，访问内存中的段表，获得对应段的起始地址。根据段的起始地址和段内偏移量，计算出物理地址。—第二次，根据物理地址，访问对应存储单元的指令或数据。为了提高处理机的效率，类似分页系统的快表，可以为分段系统增加一个快表，用于保存最近使用过的段表项。

128分段系统—总结

有效消除了内零头，提高了存储利用率。允许子程序独立编译和修改，而不需要重新编译或链接其它相关子程序。容易实现存储共享。具有较高的安全保障。很容易满足程序段的动态增长需要。129分页与分段技术的比较都采用非连续存储，由地址映射实现地址变换。不同主要表现在：（1）

页是信息的物理单位，大小固定。段是信息的逻辑单位，各段的长度不固定。每一段都具有一定逻辑含义。（2）

分页的地址空间是一维的，逻辑地址的划分由机器硬件实现，用户不清楚具体分页情况。分段的地址空间是二维或多维的，程序员知道段名和段内偏移量。（3）分页活动源于系统管理物理内存的需要，在系统内部进行，由系统实施，用户看不见。分段活动源于用户进行模块化程序设计的需要，在系统外部进行，由用户实施，用户是知道的。

130简单段页式存储管理基本思想：采用分段方法组织用户程序，采用分页方法分配和管理内存。即，用户程序可以用模块化思想进行设计，一个用户序由若干段构成。系统将内存划分成固定大小的页框，并将程序的每一段分割成若干页以后装入内存执行。131逻辑地址在段页式系统中，进程的每一段被进一步分割成页面，段内代码和数据地址不再连续。逻辑地址由3部分组成：段号、段内页号、页内偏移量，如图段号段内页号页内偏移量图3.25段页式系统的逻辑地址结构132数据结构用于管理的数据结构：段表、页表，如图图3.26段页式系统的数据结构段0段1段2用户程序段表03页表首址页表长度段号12内存

OS

0页号页框号12页号页框号页表133段表寄存器—段页式管理段表寄存器：加速地址变换，用于存放执行进程段表的起始地址。134地址变换—过程首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。再根据逻辑地址中指定的页号检索该页表，找到对应页所在的页框号。最后，用页框号加上逻辑地址中指定的页内偏移量，形成物理地址。135图3.27段页式系统的地址变换过程段表页表首址段号页内偏移量逻辑地址段内页号++物理地址页框号+页内偏移量页表页框号+偏移量内存页框页框页框段表寄存器段表起始地址136快表—段页式管理第一次，访问段表，从中获得该段的页表首址；第二次，访问页表，从中取出逻辑地址指定的页面所在的页框号，并将该页框号和页内偏移量相加，形成指令或数据的物理地址；第三次访问内存，根据前面计算的物理地址，取出对应存储单元的指令或数据。可以在地址变换机构中增设一个高速缓冲寄存器，其中保存最近使用过的页号及其所属的段号—页框号？？？。137段页式有快表的地址转换—过程首先，利用段号和页号检索该高速缓冲寄存器。若找到匹配的表项，则可以从中获得相应页面的页框号，加上页内偏移量，形成物理地址。若该高速缓冲寄存器中未包含对应表项，则需要访问段表及页表，计算出物理地址以后，从相应存储单元获取指令或数据。138段页式存储管理—总结综合了分段和分页技术的优点，既能有效地利用存储空间，又能方便用户进行程序设计。但是，实现段页式存储管理系统需要增加硬件成本，系统的复杂度和管理开销也大大增加。因此，段页式存储管理技术适合于大、中型计算机系统，不太适合小型、微型计算机系统。1393.5虚拟存储管理技术

140简单存储：要求将一个进程所需的程序和数据全部装入内存方可执行。这样的系统存在两个很严重的问题。—其一，对于大进程，如果其所需内存空间超过了内存的最大容量，则无法运行。—其二，对于多道程序系统，由于每一个进程需要全部装入内存，使同时驻留内存的进程数量受到限制。虽然也可以通过提高内存容量来解决，但是代价太高。将一部分价格较低的外存空间当作内存使用，从逻辑上扩充内存容量，将获得更高的性价比。141虚拟存储技术的理论依据程序执行的局部性原理：程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。142实现虚拟存储的一般过程

进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁盘上。进程运行时，如果它所需要访问的页面（段）已经装入内存，则可以继续执行下去；如果其所需要访问的页面（段）尚未装入内存，则发生缺页（段）中断，进程阻塞。此时，系统将启动请求调页（段）功能，将进程所需的页（段）装入内存。143实现虚拟存储的一般过程（续）

如果当前内存已满，无法装入新的页（段），则还需要利用页（段）置换功能，将内存中暂时不用的页（段）交换到磁盘上，以腾出足够的内存空间。再将进程所需的页（段）装入内存，唤醒阻塞的进程，使之重新参与调度执行。144从外存装入页/段更新页/段表交换页/段内存满？是否缺页/段中断页/段在内存是否进程执行图3.28实现虚拟存储的典型过程145虚拟存储定义通过系统提供的缺页/段中断功能和交换技术，动态装入进程的程序代码和数据，使得一个大的用户程序能在一个相对较小的内存空间中运行，也使得有限的内存能同时容纳更多的进程。习惯上，人们把这种用户感觉上的、由实际内存和部分外存共同构成的存储空间称为虚拟存储器146虚拟存储技术的技术支持

首先，必须有相应的硬件支持，用以实现虚拟分页或虚拟分段存储管理。其次，操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移动。147虚拟存储的基本数据结构

由于虚拟存储系统中，进程的程序代码和数据只有一部分在内存，另一部分保存在外存。在页/段表项中增加一个“存在”字段，其值为0或1。增加一个“修改”字段，表明对应页/段自进入内存以来是否被修改过。只有被修改过的页/段才需要保存到外存，若需要将未修改过的页/段换出内存，只需要将新装入的页/段直接覆盖其存储区域，而不必将其内容保存到外存。

148图3.29虚拟分页、分段及段页式存储系统的数据结构页号页框号存在修改其他控制(a)虚拟存储页表项段号段长存在修改其他控制(b)虚拟存储段表项段基址长(c)虚拟存储段页式系统的段表项和页表项段号其他控制页表长度页表基址段表项页号页框号存在修改其他控制页表项虚拟存储数据结构对比图

149虚拟存储的优点第一，可以运行大程序，包括超过内存实际容量的大程序。第二，可以在有限的物理内存中运行更多的程序。多道程序系统的度（作业个数）不再受到物理内存空间的限制。150虚拟存储的典型问题

--抖动（thrashing）当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。如果系统花费大量的时间把程序和数据频繁地装入和移出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。根本原因：选择的页面或段不恰当。151虚拟存储分页技术

建立在简单分页存储管理系统之上，是目前常用的一种虚拟存储管理技术。常用：虚拟分页式、虚拟段页式。152地址变换过程基于简单存储分页系统增加了某些功能，如产生和处理缺页中断，以及从内存中换出页面等。进程执行时，首先通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项。若快表中不存在该页表项，则再查找页表。检查对应的页面是否在内存中存在。若该页面不在内存，启动缺页中断处理例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将对应的页表项插入快表中，更新快表。若快表中存在该表项，则直接取出其中的页框号，加上页内偏移量，计算出物理地址。153访问页表图3.30虚拟存储分页系统地址变换过程物理地址页框号偏移量更新快表页号偏移量逻辑地址检索快表是否是否换出页面处理机处理中断是否处理机从外存取该页将该页装入内存更新页表缺页中断处理？命中？内存满？页在内存154缺页中断处理过程（1）操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；（2）操作系统通知处理机从外存读取指定的页面；（3）处理机激活I/O设备；（4）检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；（5）利用页面置换算法，选择内存中的某个页面，换出内存；（6）将指定页面从外存装入内存；（7）更新该进程的页表；（8）更新快表；（9）计算物理地址。155虚拟存储分段技术

建立在简单存储分段系统基础上，利用动态分区技术分配存储空间，并以段作为交换的单位。进程执行之前，系统为之分配几个必要的内存分区，每一个分区中装入一段。当进程执行过程中，出现缺段中断时，操作系统将为进程装入需要的程序段。156虚拟存储分段：数据结构

需要修改段表，增加“存在”字段和“修改”字段，分别标明对应段是否存在于内存，以及内存中的段自装入以来是否被修改过。157地址变换与存储保护在简单分段系统的地址变换机构基础上形成的。越界检查：可能产生一个地址越界中断，进入相应的中断处理例程执行。一般地，当地址越界中断处理完毕，该进程将异常结束。操作合法性检查：如果属于非法操作，产生非法访问中断，这时也会让进程异常终止。缺段处理：执行进程被阻塞。并产生一个中断信号，处理机执行缺段中断处理例程。158图3.31虚拟存储分段系统地址变换过程物理地址段基址偏移量更新快表否非法访问中断是是否是越界中断处理访问段表段号偏移量逻辑地址检索快表否是缺段中断处理否更新段表？命中？段在内存？地址越界？合法访问159图3.31虚拟存储分段系统中的缺段中断的处理过程换出一个或几个段形成一个合适空闲区返回修改段表、空闲分区表从外存读入段s唤醒进程是拼接外零头，形成一个合适的空闲区是段s不在内存阻塞执行进程内存中有合适的空闲区吗？否空闲区容量总和能否满足？否160虚拟存储段页式技术

虚拟存储段页式系统中，程序和数据通常以页面为单位被系统装入和移出内存。因此，一般不需要在段表项中增加“存在”字段和“修改”字段，而将它们放在页表中。段表中需要保留基于段的保护与存储共享等目的的存取控制信息，页表中设置基于页的控制信息。

161地址变换首先，通过根据段号和页号，查找快表中是否存在对应的页表项。若快表中不存在该页表项，则再查找段表。然后，检索段号对应的段表项，找到对应段的页表起始地址。再根据页号检索该页表，检查对应页面是否在内存。若该页面不在内存，启动缺页中断处理例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将对应的页表项插入快表中，更新快表。若快表中存在该表项，则直接取出其中的页框号，加上页内偏移量，计算出物理地址。162图3.32虚拟存储段页式系统地址变换过程更新页表缺页中断处理物理地址页框号偏移量更新快表是否访问段表访问页表检索快表段号页内偏移量逻辑地址段内页号否是？命中？页在内存163虚拟存储系统的软件策略现代操作系统几乎都采用虚拟存储管理系统一些特殊的操作系统和一些较老的操作系统没有采用虚拟存储技术。例如，MSDOS、早期的UNIX和一些嵌入式（专用）操作系统等。大多采用分段与分页相结合的段页式管理系统。下面以分页存储管理为例，介绍虚拟存储系统采用的软件策略。164虚拟存储系统的软件策略（续）驻留集管理(ResidentSetManagement)放置策略(PlacementPolicy)获取策略(FetchPolicy)置换策略(ReplacementPolicy)清除策略(CleaningPolicy)负载控制(LoadControl)165驻留集管理驻留集：虚拟存储系统中，每个进程驻留在内存的页面集合，或进程分到的物理页框集合。驻留集管理主要解决的问题是，系统应当为每个活跃进程分配多少个页框。166影响页框分配的主要因素

分配给每个活跃进程的页框数越少，同时驻留内存的活跃进程数就越多，进程调度程序能调度就绪进程的概率就越大。然而，这将导致进程发生缺页中断的概率较大；为进程分配过多的页框，并不能显著地降低其缺页中断率。

167基本的驻留集管理策略固定分配策略(Fixed-AllocationPolicy)可变分配策略(Variable-AllocationPolicy)168固定分配策略为每个进程分配固定数量的页框。即，每个活跃进程的驻留集尺寸在运行期间固定不变。为进程分配多少个页框是合理的呢？—可以由系统根据进程的类型确定，也可以由编程人员或系统管理员指定。169可变分配策略为每个活跃进程分配的页框数在进程的生命周期内是可变的。即，系统可以首先给进程分配一定数量的页框。进程运行期间，可以增加或减少页框。系统可以根据进程的缺页率调整进程的驻留集。—当进程的缺页率很高时，驻留集太小，需要增加页框；—当缺页率一段时间内都保持很低时，可以在不会明显增加进程缺页率的前提下，回收其一部分页框，减小进程的驻留集。170可变分配vs.固定分配可变分配策略比固定分配策略更灵活，既可以提高系统的吞吐量，又能保证内存的有效利用。可变分配要求统计进程的缺页率，增加系统额外开销。而准确判断进程缺页率的高低，确定缺页率的阈值是非常困难的。可变分配策略不仅需要操作系统软件专门的支持，而且，还需要处理机平台提供的硬件支持171页面放置策略解决的问题：系统应当在内存的什么位置为活跃进程分配页框？一般地，对于一个分页系统或段页式系统，将进程的一个页面装入哪一个页框无关紧要。对于分段系统，需要考虑将一个程序段装入哪一个合适的分区中，可采用的分配算法包括首次适应法、下次适应法、最佳适应法或最差适应法等。172页面获取策略解决的问题：系统应当在何时把一个页面装入内存？请求调页(DemandPaging)预调页(Prepaging)173请求调页仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。采用请求调页方式，一次装入请求的一个页面，磁盘I/O的启动频率较高，系统的开销较大。174预调页方式当进程创建时，预先为进程装入多个页面。缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率175页面置换策略当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。应该解决的基本问题：—当系统欲把一个页面装入内存时，应当在什么范围内判断已经没有空闲页框供分配？—当指定的范围内没有空闲页框时，应当从指定的范围内选择哪个页面移出内存？176局部置换策略—范围可以采用局部置换或全局置换策略。局部置换：系统在进程自身的驻留集中判断当前是否存在空闲页框，并在其中进行置换。177全局置换策略在整个内存空间内判断有无空闲页框，并允许从其它进程的驻留集中选择一个页面换出内存。178分配模式vs.置换模式固定分配策略局部置换策略全局置换策略可变分配策略可变分配策略+局部置换策略—即可增加或减少分配给每个活跃进程的页框数；当进程的页框全部用完，而需要装入一个新的页面时，系统将在该进程的当前驻留集中选择一个页面换出内存。

179页面置换策略—页面选择页面置换算法：在指定的置换范围内，决定将哪一个页面换出内存。置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现“抖动”现象。常用的页面置换算法：最佳置换算法、最近最少使用算法、先进先出算法和时钟算法等180最佳置换算法

(OptimalAlgorithm，OPT)基本思想：被置换的页面是将来不再访问，或在最远的将来才被访问的页面。若采用固定分配策略，最佳置换算法可以保证系统的缺页率最低。但是，无法预知一个进程在内存的若干页面中，哪一个页面是将来不再访问的，甚至最长时间内将不再被访问的，因而该算法是无法实现的。该算法可以用于评价其它置换算法的性能。181OPT置换算法示例假设系统分配给某进程3个页框，且进程开始运行时，这3个页框是空的—采用请求调页和局部置换策略。考虑下列页面号引用序列：2、3、2、1、5、2、4、5、3、2、5、218222323231235235435435435235235235页面引用序列232152453252FFFF

F

F

12次页面引用6次缺页中断（F和F）3次页面置换（F）图3.33采用OPT置换算法的缺页中断（请求调页）与（局部）页面置换过程183OPT算法的实现方案据局部性原理，如果一个页面最近被访问过，那么，它将在不久的将来再次被访问。如果一个页面已经很长时间未被访问过，则在很久的将来，它将不会被访问。因此，可以根据页面的使用历史，判断其将来的行为。184最近最少使用置换算法

(LeastRecentlyUsedAlgorithm，LRU)LRU定义：根据页面装入内存以后的使用情况，选择淘汰最近最久未被使用的一个页面。该算法的性能接近OPT算法，但实现较困难。一种方法：为每一个页面增加一个访问字段，用以标注该页最后一次被访问的时间。需要选择淘汰页面时，比较置换范围内的所有页面的最后访问时间，选择访问时间最远的哪个页面。实现该方法的开销非常大，不易实现。185LRU置换算法的实现（续）另一种方法：将访问页面组织在一个堆栈中，最近访问的页面位于栈顶，栈底的页面即是最久未被访问的。栈——后进先出实践证明，该方法的实现仍然很困难，系统付出的代价也非常大。186LRU置换算法示例

22323231251251254254354352352352页面引用序列232152453252FFFF

F

F

F

12次页面引用7次缺页中断（F和F）4次页面置换（F）图3.34采用LRU置换算法的缺页中断与页面置换过程187先进先出置换算法

(First-inFirst-outAlgorithm，FIFO)淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。实现时，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，使它总是指向最老的页面。18822323231531521524524324324354352页面引用序列232152