大学设计方案方案工作集在页面设置过程中应用与分析

1、学号：20095101250本科毕业论文（设计）学院计算机与信息技术学院专业 计算机科学与技术专业年级2009级姓名 肖志英论文（设计）题目工作集在页面设置过程中的应用与分析指导教师柳春华职称讲师2013年5月4日目录摘要 2Abstract2引论 21. 页面置换算法 32. 工作集算法 32.1 研究背景与意义3抖动现象 3局部性原理 32.2 工作集页面置换算法43. 工作集在页面置换算法中的应用 4 3.1 工作集页面置换算法 4工作集模型 4工作集的性质5工作集页面置换算法的实现63.2 工作集时钟页面置换算法8参考文献 9工作集在页面设置过程中的应用与分析学生姓名：肖志英学号： 2

2、0095101250计算机与信息技术学院计算机科学与技术专业指导教师：柳春华职称：讲师摘要： 操作系统的内存管理一直是计算机领域研究的一个重要方向。文中分析了几种常用内存管理中的页面置换算法极其存在的问题，提出了工作集页面置换算法的操作系统内存管理中的比较完美的一种页面置换算法，并阐述了实现该页面置换算法的原理及应用。关键词： 工作集模型；页面置换；内存管理；.Abstract:Memory management of operating system is a very important research direction in computer science field.In the

3、 paper,several widely-used page-replacement algorithms are introduced and their advantages/disadvantagesare analyzed.The research indicates that working set page-replacement is very close to the ideal one in memory management of operating system.Based on working set,which is used to relize the worki

4、ng set clock algorithms,is introduced and discussed in detail.Keywords:The working set model。 page replacement algorithm of the 。 memory management引论操作系统的内存管理一直是计算机领域研究的一个重要方向，而内存的虚存管理是存储管理的核心。其原因在于内存的价格昂贵，用大量的内存存储所有被访问的程序与数据段是不可能的；而外存尽管访问速度较慢，但价格便宜，适合于存放大量的信息。因此，在内存有限的情况下，扩展一部分内存作为虚拟内存，真正的内存只存储当前运行

5、时所用得到的信息，这无疑咳咳大大扩充内存的功能，并大大提高计算机的并发度。虚拟页式存储管理，就是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理的一种假内存扩充方式。在程序执行时，如果发现要访问的页面不在内存，则系统产生缺页中断。缺页中断服务程序将负责把位于磁盘上的数据加载到物理内存。虚拟页式存储管理虽然在某些程度上可以减少进程所需的内存空间，但同时也会带来运行时间变长的问题。进程在运行的过程中，不可避免地要把外存中存放的一些信息和内存中已有的数据进行交换，由于内外存运行速度的差异，这一步骤所发费的时间一般不可忽略，因而必须采取尽量好的算法来减少读取外存的次数。1

6、. 页面置换算法对于虚拟页式存储，内外存信息的替换是以页面为单位进行的。在进程运行过程中，若其所要访问的页面不在内存时，就会产生缺页中断。当发生缺页中断时，需把所需页调入内存。若内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中，以便为即将调入的页面但应腾出空间。将哪个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。2. 工作集算法2.1 研究背景与意义抖动现象页面置换算法的好坏，直接影响系统的性能。若选用的算法不合适，可能会出现这样的现象：刚被淘汰出去的页，不久又要被访问，又需把它调入而将另一页淘汰出去，很可能又把

7、刚调入的或很快要用的页淘汰出去了。如此反复频繁地更换页面，以致系统的大部分时间都花在页面的调度和传输上了。系统的实际效率很低，这种现象称为“抖动”。局部性原理通过对程序特性的观察，发现进程对主存的访问不是均匀的，而是高度地表现出局部性。它包含两方面的内容：时间局部性和空间局部性。（ 1）时间局部性：是指某个位置最近被访问了，那么往往很快又要被再次访问。这一特性可通过程序中的循环，常用子程序，堆栈，常用变量这类程序结构来说明。（ 2）空间局部性：是指某个位置最近被访问了，那么它最近的位置也要被访问。这一特性可通过程序中数组处理、顺序代码的执行，以及程序员倾向于将常用的变量存放在一起等特点来说明。

8、2.2 工作集页面置换算法现代计算机系统中内存的访问速度远远高于外存的访问速度，如果系统中不产生缺页中断，则访问数据的时间约等于内存访问时间。但是如果发生缺页中断，则需要从外存中将该页调入，在调页过程中，进程由就绪状态转为等待状态，因此会大大降低系统性能。如果缺页频率高，不但进程运行的速度很慢，大大增加了CPU 非生产机时的开销，更增加了通道和外部设备的沉重负担，从而降低了系统效率，甚至引起系统抖动，直至瘫痪。通过对缺页率的长期研究， Denning 于 1968 年提出了工作集理论。由于程序在运行时对页面的访问是不均匀的 ( 即局部性 ) ，如果能够预知程序在某段时间内要访问那些页面，并将它

9、们提前调入内存，这将降低缺页率，提高CPU利用率。用来描述驻留在物理内存中的虚拟页面子集的术语叫做“工作集”。3.工作集在页面置换算法中的应用基于工作集的页面置换算法有两种，工作集页面置换算法和工作集时钟页面置换算法。3.1 工作集页面置换算法工作集模型在单纯的分页系统里，刚启动进程时，在内存中并没有页面。在CPU 试图取第一条指令时就会产生一次缺页中断，使操作系统装入含有第一条指令的页面。其他由访问全局数据和堆栈引起的缺页中断通常会紧接着发生。一段时间以后，进程需要的大部分页面都已经在内存了，进程开始在较少缺页中断的情况下运行。这个策略称为请求调页（demand paging ），因为页面是

10、在需要时被调入的，而不是预先装入。编写一个测试程序很容易，在一个大的地址空间中系统地读所有的页面，将出现大量的缺页中断，因此会导致没有足够的内存来容纳这些页面。不过幸运的是，大部分进程不是这样工作的，它们都表现出了一种局部性访问行为，即在进程运行的任何阶段，它都只访问较少的一部分页面。例如，在一个多次扫描编译器中，各次扫描时只访问所有页面中的一小部分，并且是不同的部分。一个进程当前正在使用的页面的集合称为它的工作集（working set）。如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶段（例如，编译器的下一遍扫描）之前，不会产生很多缺页中断。若内存太小而无法容纳下整个工作集，那

11、么进程的运行过程中会产生大量的缺页中断，导致运行速度也会变得很缓慢，因为通常只需要几个纳秒就能执行完一条指令，而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每 10ms 只能执行一到两条指令，那么它将会需要很长时间才能运行完。若每执行几条指令程序就发生一次缺页中断，那么就称这个程序发生了颠簸。在多道程序设计系统中，经常会把进程转移到磁盘上（即从内存中移走所有的页面），这样可以让其他的进程有机会占有 CPU。有一个问题是，当该进程再次调回来以后应该怎样办？从技术的角度上讲，并不需要做什么。该进程会一直产生缺页中断直到它的工作集全部被装入内存。然而，每次装入一个进程时都要产生 20、100

12、甚至 1000次缺页中断，速度显然太慢了，并且由于 CPU需要几毫秒时间处理一个缺页中断，因此有相当多的 CPU时间也被浪费了。因此，如果能预知程序在某段时间间隔中所要访问的那些页，并在该段时间前就将该页调入主存，至该段时间终了时，再将其中在下一段时间里不再访问的那些页调出主存。这样可以大大减少页的调入和调出工作，缩短等待调页时间，降低缺页频率，从而能大大提高系统效率。工作集的性质Denning 所提出的工作集，粗略的说，是进程在某段时间里实际上要访问的页的集合。 Denning 认为，程序要有效的运行，其工作集必须在主存中，但是如何确定一个进程在某个时间的工作集呢？实际上，计算机无法预知程序

13、的行为，也就是无法预知要访问哪些页。我们只能依据进程过去的行为来估计它未来的行为（这种估计的依据就是程序行为的局部化特性，决定了工作集的变化是缓慢的）。所以把一个运行进程在t-w 到 t 这个时间间隔内所访问的页的集合称为该进程在时间t 的工作集，记为W(t,w) 。并把变量 w 记为“工作集窗口尺寸”。通常还把工作集中所包含的页面数目称为“工作集尺寸”，记为W(t,w) 。可以看出，工作集W是二元函数。首先W是 t 的函数，即随着时间不同，工作集页不同。这包含两方面的含义：（ 1）不同时间工作集所包含的页面数可能不同，也就是工作集尺寸不同。（ 2）不同时间工作集所包含的页面也可能不同。其次，

14、工作集 W也是工作集窗口尺寸 w 的函数。工作集尺寸 W是工作集窗口尺寸 w 的单调递增函数，且满足蕴含特性，即 W(t,w) W(t,w+a) , 其中a>0。图 1描述了作为 t 的函数的工作集的大小。正确的选择工作集窗口尺寸的大小对工作集存储管理策略的有效工作是有很大影响的。如果w 选取过大，甚至把整个作业地址空间全部包含在内，就失去了虚存的意义。 W选取过小，则将引起频繁缺页，降低了系统效率。 W(k,w) t图 1 工作集是从 t-w 到 t 过程中所访问过的页面的集合，函数 W(t,w) 是在时刻 t 时工作集的大小正确的策略并不是消除缺页现象，而应使缺页间隔时间保持在合理水

15、平。当此间隔时间过小时，应增加其页框数。过大则应增加多道程序，减少分给进程的页框数，以提高整个系统的效率。因此应把缺页的间隔时间控制在合理的范围，使分给进程的页面数保持在上、下限之间。工作集页面置换算法的实现基于工作集的页面置换算法，基本思路就是找出一个不在工作集中的页面并淘汰它。在图 2中读者可以看到某台机器的部分页表。因为只有那些在内存中的页面才可以作为候选者被淘汰，所以该算法忽略了那些不在内存中的页面。每个表项至少包含两条信息：上次使用该页面的近似时间和R（访问）位。空白的矩形表示该算法不需要的其他域，如页框号、保护位、M（修改）位。2204当前实际时间一个页面的信息R(访问 )位208

16、41上次使用的时间20031198011213020141202012032116200扫描所有页面检查R 位：若（ R= =1）设置上次使用时间为当前实际时间若（ R= =0 且生存时间w）移出这个页面若（ R= =0 且生存时间w）记住最小时间图 2工作集页面置换算法该算法工作方式如下。如前所述，假定使用硬件来置R 位和 M 位。同样，假定在每个工作集窗口尺寸中，有一个定期的时钟中断会用软件方法来清除R位。每当缺页中断发生时，扫描页表以找出一个合适的页面淘汰之。在处理每个表项时，都需要检查R 位。(1) 如果它是 1，就把当前实际时间写进页表项的“上次使用时间”域，以表示缺页中断发生时该页

17、面正在被使用。既然该页面在当前工作集窗口尺寸中已经被访问过，那么很明显它应该出现在工作集中，并且不应该被删除（假定t 横跨多个时钟滴答）。(2) 如果 R 是0，那么表示在当前时钟滴答中，该页面还没有被访问过，则它就可以作为候选者被置换。为了知道它是否应该被置换，需要计算它的生存时间（即当前实际运行时间减去上次使用时间），然后与w 做比较。如果它的生存时间大于w，那么这个页面就不再在工作集中，而用新的页面置换它。扫描会继续进行以更新剩余的表项。(3) 如果 R 是0同时生存时间小于或等于 w，则该页面仍然在工作集中。这样就要把该页面临时保留下来，但是要记录生存时间最长（“上次使用时间”的最小值

18、）的页面。如果扫描完整个页表却没有找到适合被淘汰的页面，也就意味着所有的页面都在工作集中。在这种情况下，如果找到了一个或者多个R 0的页面，就淘汰生存时间最长的页面。在最坏情况下，在当前时间滴答中，所有的页面都被访问过了（也就是都有 R1），因此就随机选择一个页面淘汰，如果有的话最好选一个干净页面。3.2 工作集时钟页面置换算法当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法是比较费时的。有一种改进的算法，它基于时钟算法，并且使用了工作集信息，称为WSClock（工作集时钟）算法（ Carr 和 Hennessey，1981）。由于它实现简单，性能较好，所以在实际工作

19、中得到了广泛应用。它所需的数据结构是一个以页框为元素的循环表，参见图3-21a 。最初，该表是空的。当装入第一个页面后，把它加到该表中。随着更多的页面的加入，它们形成一个环。每个表项包含来自基本工作集算法的上次使用时间，以及 R 位（已标明）和 M位（未标明）。2204当前实际时间16200162002084120321208412032120031202012003120201198012014119801201401213 0上次使用时间R 位12130(a)(b)162001620020841208412032120321200312003120201202011980119801201

20、4120140220411213新页面0(c)(d)图 3工作集时钟页面置换算法的操作：(a) 和(b)给出在 R=1 时所发生的情形；(c)和(d)给出 R=0 的例子每次缺页中断时，首先检查指针指向的页面。如果R 位被置为 1，该页面在当前时钟滴答中就被使用过，那么该页面就不适合被淘汰。然后把该页面的R位置为 0，指针指向下一个页面，并重复该算法。该事件序列之后的状态参见图 3-21b 。现在来考虑指针指向的页面在R=0时会发生什么，参见图3-21c 。如果页面的生存时间大于t 并且该页面是干净的，它就不在工作集中，并且在磁盘上有一个有效的副本。申请此页框，并把新页面放在其中，如图3-21

21、d 所示。另一方面，如果此页面被修改过，就不能立即申请页框，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个旧的且干净的页面可以立即使用。原则上，所有的页面都有可能因为磁盘I/O 在某个时钟周期被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回n 个页面。一旦达到该限制，就不允许调度新的写操作。如果指针经过一圈返回它的起始点会发生什么呢？这里有两种情况：（ 1) 至少调度了一次写操作。（ 2) 没有调度过写操作。对于第一种情况，指针仅仅是不停地移动，寻找一个干净页面。既然已经调度了一个或者

22、多个写操作，最终会有某个写操作完成，它的页面会被标记为干净。置换遇到的第一个干净页面，这个页面不一定是第一个被调度写操作的页面，因为硬盘驱动程序为了优化性能可能已经把写操作重排序了。对于第二种情况，所有的页面都在工作集中，否则将至少调度了一个写操作。由于缺乏额外的信息，一个简单的方法就是随便置换一个干净的页面来使用，扫描中需要记录干净页面的位置。如果不存在干净页面，就选定当前页面并把它写回磁盘。参考文献：1 屠立德 . 操作系统基础M. 北京：清华大学出版社，1987.11:133-136.2 汤小丹，梁红兵，哲凤屏，汤子灜. 计算机操作系统 M.3 版 . 西安：西安电子科技大学出版社， 2

23、007.5:142-155.3 陈向群，马洪兵 . 现代操作系统 M.3 版 . 北京：机械工业出版社， 2009:118-120.4 庞丽萍 . 操作系统原理 M.3 版 . 武汉：华中科技大学出版社， 1988： 162-164.5 刘道斌 , 白硕 . 基于工作流状态的动态访问控制 J. 计算机研究与发展， 2003， 40417-421.6 李东波，徐平，韩祥兰 . 基于专家系统的工作流管理系统模型研究 J. 南京理工大学学报，2001； 25(1) ： 96-997 曹化工，杨曼红 . 基于对象 Petri 网的工作流过程定义 J. 汁算机轴助设计与图形学学报， 2001：13(1)

24、 ： 13-188 张晓东，柴跃廷，任守榘 . 基于业务规则的事件驱动建模方法J. 清华大学学报，1999； 399 汪利宝，王更生，李宋 . 数据库加密设计及其安全体系研究 J. 江西南昌 : 计算机与现代化.2004.6,23-2410 郑惠生，宋秀琴，郝长胜 . 基于 ASP 的网络学生信息管理系统 J. 辽宁阜新：辽宁工程技术大学学报 ( 自然科学版 ).2006Vol.2511WorkflowManagementCoalition,WfMC-TC-1019,WorkflowSecurityConsiderationsWhitePaperS. 1998.12WorkflowManage

25、mentCoalition,WfMC-TC00-1003,the Workflow Reference ModelS.1995.13DiimitriosGeorgakopoulos,MarkHornick,AmitSheth.Anoverviewofworkflowmanagmanagement: from Process modeling to workflow automation infrastructureJ.Distributed and Parallel Databases,1995, 3(2):119153.14Sandhu R, Samarati. Access control principle and practiceJ. Communications Magazine, IEEE, 1994. 32(9): 4048.15Department of Defense. DOD5200.28-STD, Trusted