上海大学操作系统2研讨

1、2015操作系统第二次研讨 第四组 列举两个以上教材外的页面置换算法，并对它们的实现技术列举两个以上教材外的页面置换算法，并对它们的实现技术进行详细描述。要求用实例说明。进行详细描述。要求用实例说明。 索引节点的建立有何好处？索引节点的结构有何特点？举例索引节点的建立有何好处？索引节点的结构有何特点？举例说明大、中、小、微型文件的文件组织和存取过程有何特点，结说明大、中、小、微型文件的文件组织和存取过程有何特点，结合对索引结构的访问过程分析存取效率。合对索引结构的访问过程分析存取效率。基本工作集算法基本工作集算法1工作集时钟算法工作集时钟算法2索引节点索引节点3目 录一个进程当前正在使用的页面

2、的集合称为它的工作集（一个进程当前正在使用的页面的集合称为它的工作集（working setworking set）（DenningDenning，1968a1968a；DenningDenning，19801980）。）。”“ 工作集是会工作集是会的，进程初始时只有很少的代码页和数据页被调的，进程初始时只有很少的代码页和数据页被调入内存。当执行到未被调入内存的代码或者访问到尚未调入内存的数入内存。当执行到未被调入内存的代码或者访问到尚未调入内存的数据时，这些代码页或者数据页会被调入物理内存，工作集也随之增长。据时，这些代码页或者数据页会被调入物理内存，工作集也随之增长。 系统为每个进程都定义

3、了一个默认的系统为每个进程都定义了一个默认的（根据系统物理内存（根据系统物理内存大小，此值可能为大小，此值可能为2050 MB2050 MB）和）和（根据系统物理内存大（根据系统物理内存大小，此值可能为小，此值可能为45345 MB45345 MB）。）。 如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶段之前，不会产生很多缺页中断。段之前，不会产生很多缺页中断。 任一时刻任一时刻t t，都存在一个集合，它包含所有最近，都存在一个集合，它包含所有最近k k次内存访问所访问过次内存访问所访问过的页面。这个集合的页面。这个集合

4、w(k, t)w(k, t)就是就是。 因为最近因为最近k k1 1次访问肯定会访问最近次访问肯定会访问最近k1k1次访问所访问过的页面，次访问所访问过的页面，所以所以w(k, t)w(k, t)是是k k的单调非递减函数。的单调非递减函数。 设想有一个设想有一个，每进行一次内存访问就把寄存器，每进行一次内存访问就把寄存器左移一位，然后在最右端插入刚才所访问过的页面号。移位寄存器中的左移一位，然后在最右端插入刚才所访问过的页面号。移位寄存器中的k k个页面号的集合就是工作集。个页面号的集合就是工作集。 理论上，当缺页中断发生时，只要读出移位寄存器中的内容并排序；理论上，当缺页中断发生时，只要读

5、出移位寄存器中的内容并排序；然后删除重复的页面。结果就是工作集。然后删除重复的页面。结果就是工作集。 然而，维护移位寄存器并在缺页中断时处理它所需的开销很大，因此然而，维护移位寄存器并在缺页中断时处理它所需的开销很大，因此该技术从来没有被使用过。该技术从来没有被使用过。基于程序的基于程序的，在任何给定时刻，一个进程不久的将来所需内，在任何给定时刻，一个进程不久的将来所需内存数量，可通过考查其过去最近的时间内的内存需求做出估计。存数量，可通过考查其过去最近的时间内的内存需求做出估计。用用W(tW(t，)表示在时刻表示在时刻t-t-到时刻到时刻t t之间所访问的页面集合，则它就是进程之间所访问的页

6、面集合，则它就是进程在时刻在时刻t t的工作集，的工作集， 是系统定义的一个常量。是系统定义的一个常量。”“工作集算法基本思想：找出一个不在工作集中的页面并淘汰它。工作集算法基本思想：找出一个不在工作集中的页面并淘汰它。每当缺页中断发生时，扫描页表以找出一个合适的页面淘汰之。每当缺页中断发生时，扫描页表以找出一个合适的页面淘汰之。扫描开始扫描开始/处理一个表项处理一个表项if() 上上次使用时间次使用时间 = = 当前实际时间当前实际时间else = 当前实际运行时间当前实际运行时间 - - 上次使用时间上次使用时间if()用新的页面置换它用新的页面置换它else临时保留该表项，记录其临时保留

7、该表项，记录其TTL 扫描继续进行以更新剩余表项扫描继续进行以更新剩余表项扫描结束扫描结束 当前实际运行时间当前实际运行时间:2204:2204一个页面的信息一个页面的信息上次使用时间上次使用时间 访问位访问位R R1 1当前时钟中断期间被访问当前时钟中断期间被访问0 0表示表示当前时钟中断期间未被访问当前时钟中断期间未被访问 如果扫描完整个页表却没有找到适合被淘汰的页面，说明所有页面都如果扫描完整个页表却没有找到适合被淘汰的页面，说明所有页面都在工作集中。在工作集中。1 1、如果找到一个或多个、如果找到一个或多个R=0R=0的页面，则淘汰的页面，则淘汰的页面。的页面。2 2、如果所有表项、如

8、果所有表项R=1R=1，就，就选择一个页面淘汰。选择一个页面淘汰。 当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法是比较基本工作集算法是比较费时费时的。的。 有一种改进的算法，它基于时钟算法，并且使用了工作集信息，称为有一种改进的算法，它基于时钟算法，并且使用了工作集信息，称为（Carr Carr 和和HennesseyHennessey，19811981）。由于它）。由于它实现简单，性能较好，所以在实际工作中得到了广泛应用。实现简单，性能较好，所以在实际工作中得到了广泛应用。 ：维持一个保存所有页面的环形

9、链表，一个指针指向：维持一个保存所有页面的环形链表，一个指针指向最老页面，发生缺页中断时，检查指针指向页面，若最老页面，发生缺页中断时，检查指针指向页面，若R=0R=0，则更新它，若，则更新它，若R=1,R=1,清除清除R R位，指针前移，继续搜索。位，指针前移，继续搜索。 2020120141162001213019801上次使用时间访问位R 与时钟算法一样，所需的数据结与时钟算法一样，所需的数据结构是一个以页框为元素的循环表。最构是一个以页框为元素的循环表。最初，该表是空的。当装入第一个页面初，该表是空的。当装入第一个页面后，把它加到该表中。随着更多的页后，把它加到该表中。随着更多的页面的

10、加入，它们形成一个环。面的加入，它们形成一个环。每次缺页中断时，首先检查指针指向的页面。每次缺页中断时，首先检查指针指向的页面。if(R = 1)R = 0上次使用时间上次使用时间 = = 当前实际时间当前实际时间elseTTL = 当前实际运行时间当前实际运行时间 - - 上次使用时间上次使用时间if(TTL & M = 0) /不在工作集中，并且在磁盘上有一个有效的副本。不在工作集中，并且在磁盘上有一个有效的副本。用新的页面置换它用新的页面置换它else /在工作集中或这个页面在磁盘上没有有效副本在工作集中或这个页面在磁盘上没有有效副本2020120141162001213019801上次

11、使用时间访问位R指针经过一圈返回起始点：指针经过一圈返回起始点：1) 1) 至少调度了一次写操作。至少调度了一次写操作。2) 2) 没有调度过写操作。没有调度过写操作。对于对于，指针仅仅是不停地移动，寻找一个干净页面。既然已，指针仅仅是不停地移动，寻找一个干净页面。既然已经调度了一个或者多个写操作，经调度了一个或者多个写操作，最终会有某个写操作完成最终会有某个写操作完成，它的页面会，它的页面会被标记为干净。置换遇到的第一个干净页面，这个页面不一定是第一个被标记为干净。置换遇到的第一个干净页面，这个页面不一定是第一个被调度写操作的页面，因为硬盘驱动程序为了优化性能可能已经把写操被调度写操作的页面

12、，因为硬盘驱动程序为了优化性能可能已经把写操作重排序了。作重排序了。对于对于，所有的页面都在工作集中，否则将至少调度了一个写，所有的页面都在工作集中，否则将至少调度了一个写操作。由于缺乏额外的信息，一个简单的方法就是随便置换一个干净的操作。由于缺乏额外的信息，一个简单的方法就是随便置换一个干净的页面来使用，扫描中需要记录干净页面的位置。如果不存在干净页面，页面来使用，扫描中需要记录干净页面的位置。如果不存在干净页面，就选定当前页面并把它写回磁盘。就选定当前页面并把它写回磁盘。u 索引节点的建立有何好处？索引节点的建立有何好处？ 文件目录：文件目录：文件控制块的有效集合，存放在磁盘上。文件控制块

13、的有效集合，存放在磁盘上。 基本信息基本信息：文件：文件名、物理位置、逻辑结构、物理结构名、物理位置、逻辑结构、物理结构存取控制信息类存取控制信息类：文件主、核准用户和一般用户的存取权限文件主、核准用户和一般用户的存取权限使用信息类使用信息类：文：文件建立日期和时间、文件上一次修改对的日期和时间、件建立日期和时间、文件上一次修改对的日期和时间、 当前使用信息当前使用信息 文件控制块文件控制块在检索目录文件的过程中，只用到了在检索目录文件的过程中，只用到了，仅当找到一个目录项中的文件，仅当找到一个目录项中的文件名和要查找的文件名相匹配时，才需要从该目录中读出该文件的物理地址，名和要查找的文件名相

14、匹配时，才需要从该目录中读出该文件的物理地址，而其它一些对该文件进行描述的信息在检索目录时一概不用。而其它一些对该文件进行描述的信息在检索目录时一概不用。u 索引节点的结构有何特点？索引节点的结构有何特点？ ：包含操作系统所需要的关于某个文件的关键信息。可以有多个文：包含操作系统所需要的关于某个文件的关键信息。可以有多个文件名与一个索引节点相关联，但每个文件只能由一个索引节点来控制。件名与一个索引节点相关联，但每个文件只能由一个索引节点来控制。 节点节点说明说明文件模式16位标记，保存与文件相关的访问和执行许可权链接计数访问该索引节点的目录数所有者ID该文件的单个所有者组ID与该文件相关联的组所有者文件大小文件的字节数文件地址39个字节的地址信息最后一次被访问文件最后一次被访问的时间最后一次被修改文件最后一次被修改的时间索引节点被修改索引节点文件最后一次被修改的时间u 举例说明大、中、小、微型文件的文件组织和存取过程有何特举例说明大、中、小、微型文件的文件组织和存取