操作系统设计与实现(第四章)

1、操作系统设计与实现,主讲教师：徐战亚 Email ：,第四章 存储器管理,一、存储器在操作系统中的地位 是计算机不可缺少的部分，存在的方式也多种多样。 对于操作者、程序设计者、系统开发者都希望能拥有无穷大的、高速的、内容不发生变化的存储器，最根本的还是能以很低的成本来使用。,由于技术的原因，我们无法满足我们的需求，因此，大部分的计算机都以一种层次结构来进行存储器的管理。,高速、价格昂贵、易失信息的Cache一般单位几百KB； 中速、中等价格、易变化的RAM，一般单位为几百M； 低速、低廉价格、不易丢失信息的磁盘，一般单位为G；,存储器层次结构,对于操作系统，它本身提供一个存储管理模块来管理它本

2、身的这个层次性的存储器系统。 Memory manager,由操作系统协调这些存储器的使用 重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。,内存： 是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器。,可以分为： 系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据。,操作系统存储管理目的- 用户对内存的使用要求,1、充分利用内存，为多道程序并发执行提供存储基础； 2、尽

3、可能方便用户使用： 自动装入用户程序； 用户程序中不必考虑硬件细节； 3、系统能够解决程序空间比实际内存空间大的问题； 4、程序在执行时可以动态伸缩； 5、内存存取速度快； 6、存储保护与安全； 7、共享与通信； 8、了解有关资源的使用状况； 9、实现的性能和代价。,操作系统存储管理的任务 前提: 引入多道程序设计技术，满足用户要求,1. 内存空间的管理、分配与回收,记录内存的使用情况 设置相应的内存分配表（见下页） （内存分配回收的依据） 内存空间划分问题？ 静态或动态，等长或不等长,内存分配表 位示图表示法：用一位（bit）表示一个空闲页面（0：空闲，1：占用）；,空闲页面表：包括首页面号

4、和页面个数，连续若干的页面作为一组登记在表中 空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用； 空闲块链表：将所有的空闲块链成一个链表。,确定分配算法 实施内存分配 回收内存 分配回收方式: 静态分配与动态分配,连续性 ； 离散性 驻留性 ； 交换性 一次性； 多次性,2. 存储共享,内存共享：两个或多个进程共用内存中相同区域 目的： 节省内存空间，提高内存利用率 实现进程通信（数据共享） 共享内容： 代码共享，要求代码为纯代码 数据共享,3. 存储保护与安全,保护目的： 为多个程序共享内存提供保障,使在内存中的各道程序, 只能访问它自己的区域，避免各道程序间相互干拢，特别是当

5、一道程序发生错误时, 不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储保护。）,存储保护,保护系统程序区不被用户侵犯; （有意或无意的） 不允许用户程序读写不属于自己地址空间的数据; （系统区地址空间，其他用户程序的地址空间）,保护过程-防止地址越界,每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。,一般由硬件提供一对寄存器： 基址寄存器：存放起始地址 限长寄存器：存放长度 （上界寄存器/下界寄

6、存器）,保护过程-防止操作越权,对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。 即读写保护。,4 .内存“扩充”,通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来扩充内存的容量，使用户得到比实际内存容量大的多的内存空间。,内存“扩充”,具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。,5 . 地址映射（地址重定位，地址变换）,(1) 逻辑地址（相对地址，虚地址） (2) 物理地址（绝对地址，实地址） (3) 地

7、址映射,(1)逻辑地址（相对地址，虚地址）,用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息。,(2)物理地址（绝对地址，实地址） 内存中存储单元的地址，可直接寻址。,(3)地址映射,为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。,*重定位和保护,多道程序导致了分区的产生，而分区也导致了新的问题，即程序的重新定位和保护。 如果多个作业都是为某一个程序服务，当主程序调用这些作业的时候，就需要定位到这些作业，保

8、证程序的运行（主函数和分别编译好的子函数）。这时，链接的时候，链接器按照我们的分区机制来定位程序。 定位和保护的常见方法：,原因: 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,静态重定位,当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。,动态重定位,在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）。 硬件上需要

9、一对寄存器的支持。,4.1 基本的内存管理,在运行时进程可以在内存和磁盘之间进行移动（交换和分页技术）的系统； 运行时进程不能够移动的系统，较为简单。 交换和分页技术的目的是由于没有足够的主存来同时容纳所有的进程而被引入。随着硬件的发展，现有的良好的管理方案也会可能变成过时的技术而被淘汰。,4.1.1无交换和分页的单道程序,此方案是指同一个时刻和操作系统共享存储器。,对于A图，操作系统位于主存最底部的RAM，即随机存取存储器中，用户程序位于主存的上部。 对于B图，操作系统位于主存最高端的只读存储器里（ROM）,（其实本身属于一种映像区域，映像了主板上的基本的输入输出系统）。 对于C图，设备的驱

10、动程序位于内存最高端的ROM中，操作系统的其余部分位于低端的RAM中，中间是用户的应用程序。如MS-DOS系统。 对于IBM操作系统，系统位于ROM中的部分即为BIOS。,对于这种方式，不管是哪一个图，操作系统每次把需要的程序从磁盘复制到存储器里并执行，当程序结束时，系统提示结束，当有新的命令时，系统加载新的程序到存储器中，覆盖原来的程序，继续新的执行。 可以满足早期一般的小型的操作系统的需求，但随着硬件性能的提高，这种方式逐渐被淘汰。,4.1.2 固定分区的多道程序,对于常见的系统，我们希望能够支持更多的程序，当某个程序处于等待I/O的时候，可以让CPU为别的程序服务，来提高系统整体的性能。

11、 因此可以用划分分区的方法来同时加载多个程序，可以把主存分为几个大小不同的分区，根据程序的不同，来把他们加载到不同的分区中。而同时，程序也可按照单个输入队列的方式进行输入，也可以按照多个输入队列的方式进行输入。,对于左图，由于作业的大小类似的时候，而且众多的作业大小都类似，而此时分区的大小固定，我们该选择合适大小的分区来运行这个作业，这样的话，类似的作业就被分到了一起，而那些与作业的大小不一致的分区，就必然会出现空闲状态，那些分到一起的进程却不得不等待，等待要分到内存空间。忙得忙，闲的闲。 如分区一和分区三。,对于右图，所有的作业都被放入一个队列，每次当有分区被释放的时候，就从等待队列中寻找，

12、最适合这个分区大小的进程，这样做是为了避免把大的分区分给那小的作业，免得资源被浪费，但这样却常常把小的作业推到了后面；但对于操作系统，我们做普通的要求就是简单的操作能被最快的反馈给我们，即小的作业能够被最快的处理，因此，为了总能够满足用户的这个要求，一般要专门保证总有一个小的分区，专门来处理那些小的事件、作业，免得被大的作业抢去分区。 或者通过加权来判断作业被推后的次数，到了一定的程度，就不再跳过而是立即执行。,4.2 交换,固定分区的方案在批处理系统中是种简单高效的方案，每一个作业都在队列中一直到被分配到某个分区，然后被执行完毕。只要能够放入内存，能够使CPU 繁忙，就能满足要求。,但在分时

13、系统中，或者个人的PC中，这种方案就不太实际，会常常由于主存不够，需要把进程保存到磁盘，同样的，也需要常常动态地把进程从磁盘调入内存。 这时就需要有新的技术，即交换技术(swapping)和虚拟内存技术的引入。,进程依次进入，并获得到自己所需要的内存空间，当某个进程执行完毕后便离开，它原来的占用的内存资源便得到释放，当新的进程到来的时候，又可以从这个被释放的空间中划分新的空间，因此主存的利用变得很高效。（理想上的）,g,上图中的内存分配与固定分区的不同，它是一种可变分区的内存分配，这时内存中的分区的数目和大小都是在随时随着进程的变化而变化的。 实际上，内存空间在不断划分的时候，本身的分布也在变

14、化的越来越复杂，越来越不便于管理。 迫切需要一个机制去整理这个零碎的空间。即空闲区域的合并-内存紧缩。(低效的操作，耗时),*新的问题,如果根据进程需要给它分配内存，而且，进程运行的时候大小不再变化，那么分配就简单，根据需要的大小分配即可； 如果进程运行时，该进程的数据段增长，就需要分配新的内存，那进程所需的空间就开始变大，上图中，如果相邻区域是空洞，则直接分配给它，但如果是进程时？交换，将某一进程移出，但此时内存满了，磁盘交换分区也满了，某进程则必须等待或杀死。,*新问题的解决带来的矛盾：,多数的进程都需要动态的空间，且申请新的内存空间，频繁的交换导致大量的进程等待和时间开销。,*矛盾的解决

15、,在每个进程申请空间的时候分配一些多余的内存空间；（A） 或者对于具有两个可增长数据部分的进程，采用在进程的分区内分开放置的方式管理。（B）,4.2 .1 使用位图的内存管理,由于操作系统需要对内存进行分配管理和回收，所以，它必须很好地对内存进行跟踪，常用的是位图法和自由链表：,(a),对于位图方法，位图的大小与内存的大小和分配的单位的大小相关，内存不变时，被分配的单个单元越小，则位图就越大。 位图的组织结构简单，便于管理，且占用的内存很小但也有缺陷：定位的速度受限，由于每个位图单元代表一个被分配的单元，所以连续性不强，对于某个需要几个分配单元大小的进程就很难快速在位图中找到这样连续的空间。故

16、实际不很常用。,4.2 .2 使用链表的内存管理,这种方法是通过一个链表来管理已经分配的和尚未分配的内存段，通过对链表的维护达到对内存的管理。这里的内存段可以使被某个进程所占用，也可以是个空洞，即尚未分配的区域。 表的内容包括段的性质、开始地址、长度、长度和指向下一个表项的指针。这是一般，链表的组织都按照地址来排列，这样的进程切换会很直观，更有效的方法是采用双向链表来记录。 但这时就需要对空洞进行处理。,对于某进程X结束的时候同邻居合并的四种方式,对于这种内存的组织和管理方法，我们需要讨论如何用合理的方法来为新创建的进程和新换进来的进程分配大小： *最简单的分配算法首次适配算法 存储管理器沿内

17、存段链表从头开始寻找足够的空间来装载进程，除非找到的这个区域的大小刚好和进程相同，否则就要把这个空间拆为两部分，一部分来装进程，另一部分依然为空。 属于快速算法，搜索的开销很小。,*首次适配的变形下次适配 工作方式与首次适配相同，区别在于每次搜索完毕后记录当前的位置，下次搜索时从此处开始搜索。 *最佳适配算法 每次搜索整个链表中最适合该进程大小的内存空间，没有完全相同就寻找次之的；每次都要搜索整个链表故速度很慢，而且每次都可能拆分内存，而且生成的新的内存空间会很小。,*放弃最佳适配算法采用最差适配算法 采用最差，即每次找最大的内存空间分给进程，这样就不会产生大量的极小的内存空洞，即被分开后剩余

18、的那部分仍然足够大，可以继续被使用。 对于这四种算法，都不是很有效的方法，如果把表示进程占用的内存段和表示空闲的内存段分开放到两个链表中，这样检索效率会提高很多，但这样的带来的新的麻烦就是控制过程的复杂化和内存释放过程的延长，不得不把释放的内存从一个链表中清除再放到另一个中去。,*一些改进思路,* 进程和空洞存放在两个链表中，针对最佳适配算法的缺陷，将空洞的组织不按地址，而是按照大小来组织，这样就减小了搜索时的开销。 *进程和空洞存放在两个链表中，用空洞本身来存放这个链表，第一个字存放空洞的大小，第二个字存放下一个空洞的地址。 *快速适配法，按照常见进程需要的空间大小设置单独的链表，这种算法就

19、根据进程所需空间的大小快速在这些特殊的空洞链表中查找空内存。它需要将所有的空洞进行排序，即进程换出时的空洞合并判断。,4.3 虚拟存储器,交换技术与覆盖技术是在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾。 覆盖技术主要用在早期的操作系统中； 交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现。 交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换。,覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。 把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不

20、会同时执行的程序段共享同一块内存区域。 程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）。 一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后又由操作系统完成自动覆盖。,缺点：对用户不透明，增加了用户负担。 例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构。,虚拟存储器的基本思想是： 程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分

21、保存在磁盘上，并在需要时在内存和磁盘之间动态交换。 虚拟存储器支持多道程序设计技术。,虚存： 把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存。 实现思想： 当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。,4.3.1 分页,虚拟存储器常用的技术，在这种虚拟存储器系统中，内存管理单元负责地址的计算和重新定位。它是一组或一个芯片，完成地址映射的功能。,*隐含的问题： 程序不知道实际的存储器的大小，由于页和页框的大小一样，则必然有些程序中的地址是没有经过映射的，即虚拟存储器中有空页，他没有和实际

22、的物理内存对应起来。虚页是否被对应了都专门有一位来存储这个信息。 如：MOV REG,32780 这时会发现在虚页8里没有对应的物理地址，这是MMU就无法处理此时的问题。这是的故障就叫做缺页故障。操作系统需要找到一个页框将其内容一到磁盘，把刚才需要引用的页取到这个页框中，并修改映射，然后重新启动刚才的指令。,MMU的内部结构及工作方法,110,在/不在内存,页表,虚地址 8196,物理地址 24580,4.3.2 页表 （page table）,页表是用来索引页面的，通过判断页表的存在位，判断这个虚页在物理内存中是否有对应的页框，当有的时候，就直接通过页表函数获得实际的物理地址来定位到实际的物

23、理内存，如果没有，就通知操作系统，引发陷入，去找空页框来装入这个虚页。,对于16位指令系统的一种方案,地址映射在实际应用中的问题： 现代计算机的虚地址一般最少都32位，如果按照页面4K来处理，则对此系统来说，就是有 的页面大小，同时又有 个页表记录。而64位系统的更为庞大. 即问题主要是页表的庞大导致了索引不再高效； 另外，从虚地址到物理地址的映射的频繁执行，现有的庞大页表无法完成快速的查找定位. 即问题是地址映射相应变慢。,问题的解决： 一、利用硬件配合解决-CPU端 将页表装入寄存器中，避免进程运行时访问内存，对页表的检查也直观。但这样当页表大的时候，就要多的硬件寄存器来存放，代价昂贵。每

24、次进程切换时候都要装入内存中的页表，开销也会很大。 二、另一种极端，全放入内存 这时的硬件开销就很小，只需要指向页表起始地址的寄存器即可。环境切换时，改变这个寄存器里的东西即可。但缺点是执行每条指令时都要一次或多次访问内存。故很少单纯使用。,*多级页表,为了不将庞大的页表全放内存，引入了多级页表技术： 对于此例：32位虚地址分为了10位的PT1域，10位的PT2域，每个页的大小是12位。 每一个进程都拥有自己的页表，即每个进程都可以拥有4G的虚存空间。 当一个虚地址定位的时候，具体过程如下：,物理内存,当用户的页不在主存中，就会发生缺页故障，由操作系统完成换页的工作。,*页表分析,页框号：具体

25、对应的物理内存的位置 在/不在位：表示是否会发生缺页 保护位：表示这个页所允许的操作 ，表示此页所允许的操作 修改位：表示此页被修改的情况（上一次的操作）-dirty bit 引用位：此页被访问的情况，页面替换算法的重要依据 禁用缓存：特殊使用，保证数据的及时更新,4.3.3 TLB-转换后援存储器,用硬件手段来解决庞大的页表的问题，由于页表使用的不均匀性，小部分页表被大量频繁的使用，另一些则很少被使用，故专门用硬件TLB(Translation Lookaside Buffer)来存放常用的页号，并不停的保持TLB中页号的更新。 工作时，当有虚地址需要转换时，先到TLB中去作判断，如果不在T

26、LB中，就去页表中查询，并在获得后更新TLB中的页号数据，淘汰一个条目，将其信息写回内存中的页表项，把新的条目加入；如果虚页号在TLB中，则判断保护情况，合法就直接取出使用，不用查询页表，不合法时，就出现保护故障。,*软件TLB管理,现代很多大型操作系统的缺页故障不再由MMU处理，而是交给TLB，而TLB也是由操作系统装入的，因此，TLB的缺页故障比MMU的高得多，但通过设置TLB的大小，可以很有效提高页面的命中率，而此时MMU的设计就可以简化很多，从而使CPU可以更好地设计自己所需的其他部件。 并且操作系统可以根据进程的性质，自动预装进程可能需要的页面这样，就是进程的缺页率大大减少。,4.3

27、.4 逆向页表,若对于64位计算机，页框如果仍然4K，此时页表项就变得更加庞大，不可能去管理好，故用了逆向的思路来处理即每一个物理页框对应了一个页表项，用对应的函数来处理他们之间的关系。节省了大量的物理空间。 弱点是虚地址到实际物理地址转换很困难，不能根据虚地址查物理地址，而是在逆向表中查进程对应的表项。,4.4 页面替换算法,页的置换算法：当发生缺页，而主存中已无空闲页架时，需选一页淘汰。选取淘汰页的方法叫页的置换算法。 抖动：刚被淘汰出去的页，不久又被访问，又需把它调入而将另一页淘汰出去，很可能又把刚调入的或很快要用的页淘汰出去了。如此反复更换页面，以至系统大部分机时花在页面的调度和传输上

28、，系统的实际效率很低。这种现象称为“抖动”。 缺页率：f = (缺页次数/访问页面总数)% 常见的页面置换算法： 最佳置换算法 OPT；先进先出置换算法FIFO；最近最少使用置换算法LRU；最近未使用置换算法NUR；工作集.,4.4.1 最佳置换算法 OPT（Optimum Strategy）,基本原则： 淘汰在将来再也不被访问，或者是在最远的将来才能被访问的页。 特点： 无法预测作业将用到哪些页！所以此算法是无法实现的理论上的算法。 例：某进程分配页架数为3，其运行期间页面访问序列：A,B,C,D,A,B,E,A,B,C,D,E，分析其按照OPT算法进行页面置换时的缺页情况。（堆栈式算法）,

29、最佳置换算法OPT,4.4.2最近未使用置换算法 （Not used Recently）NUR,页表扩充：为每个页面设置两个硬件位访问位和修改位。 访问位= 0：该页尚未被访问过R:读写时设置 = 1：该页已经被访问过 修改位= 0：该页尚未被修改过 M:修改时设置 = 1：该页已经被修改过,即对应的四类情况为： *第0类：未被访问，没有被修改 *第1类：未被访问，已被修改-（由第3类产生) *第2类：已被访问，没有被修改 *第3类：被访问，被修改,4.4.3 先进先出置换算法FIFO (first-in,first-out),基本原则：选择最早进入主存的页面淘汰。 理由：最早进入的页面其不再

30、使用的可能性比最近调入的页面要大。 实现简单：把进入主存的各页面按进入主存的时间次序构成队列（链表或表格），总是淘汰队头的页面。 缺点： 只有按照线性顺序访问地址空间时才是理想的，否则效率不高。 异常现象：对于一些特定的访问序列，随分配页架数增加，缺页频率反而增加！,先进先出置换算法FIFO,4.4.4 第二次机会页面替换算法,由于FIFO会把经常使用的页面换掉，故需要一次改进，对页面的引用位进行检查，来判断这个页的使用情况，如果未被引用，则替换掉此页，如果不为0，表示此页被使用过，则清除R位，并放入队列最后，将它当作新的页面来对待，从而保证了经常使用的页面能够被保持下来。 该算法其实就是查找

31、从上一次检查以来没有引用过的页面，如果都被引用了，它就成了FIFO算法。,当在时间到了 20的时候，此时发生了页面故障，需要淘汰一个老的页面，首先对A页面进行判断，如果A页面的引用位是0，则A就被淘汰出去，要么被直接丢弃，要么被写回硬盘。如果引用位是1，A页面将被放入队列的尾部，同时它的引用位将被清零。,4.4.5 时钟页面替换算法,由于第二次机会算法需要在链表中移动页面，导致了不必要的开销，故用时钟页面替换算法来提高效率。,原理同第二次机会算法一样，但只是实现方法不一样而已。,4.4.6 最久最少使用页面替换算法(LRU),基本原则：选择最近一段时间内最长时间没有被访问过的页面淘汰。 基本理

32、由：认为过去一段时间里不曾被访问过的页，在最近的将来也可能不再会被访问。 实现困难：需为每个页设置一个特定单元，记录上次访问后到现在的时间量 t，并选择 t 最大的页淘汰。无论硬件还是软件实现开销都很大！,LRU的硬件实现：矩阵方法实现 页面K被使用，则将K行全置1，然后，将K列全置0，如果需要淘汰的时候按照行来判断。,4.4.7 软件仿真的LRU算法,用计数器跟踪每个页面被访问的频繁程度，被访问一次就将计数器累加一次，当发生需要淘汰页面的情况的时候，将计数器值最小的页面淘汰掉即可。 即软件的NFU (not frequently used) 算法。 弊端：保留了每次的访问信息，会影响到以后的

33、页面的访问信息。 改进方案：计数器累加前先右移一位，R位累加到计数器的前端而不是后端。,4.5 分页系统中的设计问题,如何从整体把握分页模块的设计，各个细节在模型中的重要性和设计需求.,4.5.1 工作集模型,请调策略：根据需求将需要的页面调入内存中的工作方式称为请调； 访问局部性：进程对页面访问的局部性，而且对于所有进程都有此特性； 工作集：一个进程当前使用的页的集合叫做此进程的工作集。,颠簸：进程执行过程当中，一个隔几个指令就发生一次页面故障的程序成为在颠簸。 指令执行通常需几个纳秒，读入页面一般需要几十毫秒。 进程在换出内存然后又被调入，这样的过程使得系统的性能花费在页面的移动上，由于每

34、次装入的请调策略，使得开始执行的时候程序颠簸很厉害，故利用工作集的方法来解决这个问题。将常用的页作标识，则移出后之保留，进行跟踪，以后再调入的时候，根据这些信息来快速调入，-预调。,4.5.2 局部与全局分配策略,一直讨论的是某一个进程发生缺页故障，而实际上内存中存在的是多个进程的页面，当其中某个进程发生缺页故障的时候，实际的替换应该有很多种方法，即涉及到了对某个进程的页面替换还是对整个内存中页面的替换的问题。 对于某个进程发生了缺页故障，替换页面时只从此进程拥有的页面中淘汰的方法叫做局部页面替换策略（其实对应的是在内存中为每个进程分配了固定的内存片断）；从内存中只关心页面的年龄来进行淘汰的方

35、法叫做全局页面替换策略（其实对应了每个进程的页框数是可以变化的）。,Original configuration,Local page replacement,Global page replacement,局部与全局的优劣性的比较： 一般来说，全局比局部较优 局部：当内存中有空页框的时候，仍然在自己固定的段内替换，会导致很高缺页率；工作集增大，颠簸变大，工作集变小，内存又会被浪费。 全局：系统需要不断确定该给不同的进程多少页框，但是由于工作集变化的过快，跟踪年龄位也很难实现。可以定期为当前进程平均分配同等页框，但进程的大小不同，这种分配仍不合理；也可按照进程大小来分配；或者为每个进程规定最小

36、页框数，这样可保证每个进程都可以执行。,无论何种方案都是为了减少颠簸，因此有需要将颠簸直接控制，即PFF算法（page fault frequency）,A表示故障率过高，B表示故障率过低，过高表示页框太少，需要增加分配；过低表示页框过多，需要减少页框。,4.5.3 页面大小,页面大小的选择，会影响内存的利用率。 内零头的产生：由于分页存储，且页面有大小，当一个页被写入了数据，就认为此页被使用了，别的进程就不会再来用这个页面，因此，就产生了内零头，且平均大小为 段数页长/2。,Eg：一个程序被分为八个部分执行，每次需要4k的内存，则页长为32k时，就分配了32k，16k时就分配了16k，4k时就分配了4k。过大浪费即越大。过小的话，页表就变得庞大，装入时就使大量时间花在了寻道上，每次装入页面