您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 毕业论文设计工作集在页面设置过程中的应用与分析
本科毕业论文(设计)学院计算机与信息技术学院专业计算机科学与技术专业年级2009级姓名肖志英论文(设计)题目工作集在页面设置过程中的应用与分析指导教师柳春华职称讲师学号:2009510125012013年5月4日目录摘要...............................................................2Abstract............................................................2引论................................................................21.页面置换算法......................................................32.工作集算法........................................................32.1研究背景与意义...............................................32.1.1抖动现象...............................................32.1.2局部性原理.............................................32.2工作集页面置换算法...........................................43.工作集在页面置换算法中的应用......................................43.1工作集页面置换算法...........................................43.1.1工作集模型.............................................43.1.2工作集的性质...........................................53.1.3工作集页面置换算法的实现...............................63.2工作集时钟页面置换算法.......................................8参考文献............................................................92工作集在页面设置过程中的应用与分析学生姓名:肖志英学号:20095101250计算机与信息技术学院计算机科学与技术专业指导教师:柳春华职称:讲师摘要:操作系统的内存管理一直是计算机领域研究的一个重要方向。文中分析了几种常用内存管理中的页面置换算法极其存在的问题,提出了工作集页面置换算法的操作系统内存管理中的比较完美的一种页面置换算法,并阐述了实现该页面置换算法的原理及应用。关键词:工作集模型;页面置换;内存管理;.Abstract:Memorymanagementofoperatingsystemisaveryimportantresearchdirectionincomputersciencefield.Inthepaper,severalwidely-usedpage-replacementalgorithmsareintroducedandtheiradvantages/disadvantagesareanalyzed.Theresearchindicatesthatworkingsetpage-replacementisveryclosetotheidealoneinmemorymanagementofoperatingsystem.Basedonworkingset,whichisusedtorelizetheworkingsetclockalgorithms,isintroducedanddiscussedindetail.Keywords:Theworkingsetmodel;pagereplacementalgorithmofthe;memorymanagement引论操作系统的内存管理一直是计算机领域研究的一个重要方向,而内存的虚存管理是存储管理的核心。其原因在于内存的价格昂贵,用大量的内存存储所有被访问的程序与数据段是不可能的;而外存尽管访问速度较慢,但价格便宜,适合于存放大量的信息。因此,在内存有限的情况下,扩展一部分内存作为虚拟内存,真正的内存只存储当前运行时所用得到的信息,这无疑咳咳大大扩充内存的功能,并大大提高计算机的并发度。虚拟页式存储管理,就是将进程所需空间划分3为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理的一种假内存扩充方式。在程序执行时,如果发现要访问的页面不在内存,则系统产生缺页中断。缺页中断服务程序将负责把位于磁盘上的数据加载到物理内存。虚拟页式存储管理虽然在某些程度上可以减少进程所需的内存空间,但同时也会带来运行时间变长的问题。进程在运行的过程中,不可避免地要把外存中存放的一些信息和内存中已有的数据进行交换,由于内外存运行速度的差异,这一步骤所发费的时间一般不可忽略,因而必须采取尽量好的算法来减少读取外存的次数。1.页面置换算法对于虚拟页式存储,内外存信息的替换是以页面为单位进行的。在进程运行过程中,若其所要访问的页面不在内存时,就会产生缺页中断。当发生缺页中断时,需把所需页调入内存。若内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区中,以便为即将调入的页面但应腾出空间。将哪个页面调出,需根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法。2.工作集算法2.1研究背景与意义2.1.1抖动现象页面置换算法的好坏,直接影响系统的性能。若选用的算法不合适,可能会出现这样的现象:刚被淘汰出去的页,不久又要被访问,又需把它调入而将另一页淘汰出去,很可能又把刚调入的或很快要用的页淘汰出去了。如此反复频繁地更换页面,以致系统的大部分时间都花在页面的调度和传输上了。系统的实际效率很低,这种现象称为“抖动”。2.1.2局部性原理通过对程序特性的观察,发现进程对主存的访问不是均匀的,而是高度地表现出局部性。它包含两方面的内容:时间局部性和空间局部性。(1)时间局部性:是指某个位置最近被访问了,那么往往很快又要被再次访问。这一特性可通过程序中的循环,常用子程序,堆栈,常用变量这类程序结构来说明。(2)空间局部性:是指某个位置最近被访问了,那么它最近的位置也要被访4问。这一特性可通过程序中数组处理、顺序代码的执行,以及程序员倾向于将常用的变量存放在一起等特点来说明。2.2工作集页面置换算法现代计算机系统中内存的访问速度远远高于外存的访问速度,如果系统中不产生缺页中断,则访问数据的时间约等于内存访问时间。但是如果发生缺页中断,则需要从外存中将该页调入,在调页过程中,进程由就绪状态转为等待状态,因此会大大降低系统性能。如果缺页频率高,不但进程运行的速度很慢,大大增加了CPU非生产机时的开销,更增加了通道和外部设备的沉重负担,从而降低了系统效率,甚至引起系统抖动,直至瘫痪。通过对缺页率的长期研究,Denning于1968年提出了工作集理论。由于程序在运行时对页面的访问是不均匀的(即局部性),如果能够预知程序在某段时间内要访问那些页面,并将它们提前调入内存,这将降低缺页率,提高CPU利用率。用来描述驻留在物理内存中的虚拟页面子集的术语叫做“工作集”。3.工作集在页面置换算法中的应用基于工作集的页面置换算法有两种,工作集页面置换算法和工作集时钟页面置换算法。3.1工作集页面置换算法3.1.1工作集模型在单纯的分页系统里,刚启动进程时,在内存中并没有页面。在CPU试图取第一条指令时就会产生一次缺页中断,使操作系统装入含有第一条指令的页面。其他由访问全局数据和堆栈引起的缺页中断通常会紧接着发生。一段时间以后,进程需要的大部分页面都已经在内存了,进程开始在较少缺页中断的情况下运行。这个策略称为请求调页(demandpaging),因为页面是在需要时被调入的,而不是预先装入。编写一个测试程序很容易,在一个大的地址空间中系统地读所有的页面,将出现大量的缺页中断,因此会导致没有足够的内存来容纳这些页面。不过幸运的是,大部分进程不是这样工作的,它们都表现出了一种局部性访问行为,即在进程运行的任何阶段,它都只访问较少的一部分页面。例如,在一个多次扫描编译器中,各次扫描时只访问所有页面中的一小部分,并且是不同的部分。一个进程当前正在使用的页面的集合称为它的工作集(workingset)。如果5整个工作集都被装入到了内存中,那么进程在运行到下一运行阶段(例如,编译器的下一遍扫描)之前,不会产生很多缺页中断。若内存太小而无法容纳下整个工作集,那么进程的运行过程中会产生大量的缺页中断,导致运行速度也会变得很缓慢,因为通常只需要几个纳秒就能执行完一条指令,而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每10ms只能执行一到两条指令,那么它将会需要很长时间才能运行完。若每执行几条指令程序就发生一次缺页中断,那么就称这个程序发生了颠簸。在多道程序设计系统中,经常会把进程转移到磁盘上(即从内存中移走所有的页面),这样可以让其他的进程有机会占有CPU。有一个问题是,当该进程再次调回来以后应该怎样办?从技术的角度上讲,并不需要做什么。该进程会一直产生缺页中断直到它的工作集全部被装入内存。然而,每次装入一个进程时都要产生20、100甚至1000次缺页中断,速度显然太慢了,并且由于CPU需要几毫秒时间处理一个缺页中断,因此有相当多的CPU时间也被浪费了。因此,如果能预知程序在某段时间间隔中所要访问的那些页,并在该段时间前就将该页调入主存,至该段时间终了时,再将其中在下一段时间里不再访问的那些页调出主存。这样可以大大减少页的调入和调出工作,缩短等待调页时间,降低缺页频率,从而能大大提高系统效率。3.1.2工作集的性质Denning所提出的工作集,粗略的说,是进程在某段时间里实际上要访问的页的集合。Denning认为,程序要有效的运行,其工作集必须在主存中,但是如何确定一个进程在某个时间的工作集呢?实际上,计算机无法预知程序的行为,也就是无法预知要访问哪些页。我们只能依据进程过去的行为来估计它未来的行为(这种估计的依据就是程序行为的局部化特性,决定了工作集的变化是缓慢的)。所以把一个运行进程在t-w到t这个时间间隔内所访问的页的集合称为该进程在时间t的工作集,记为W(t,w)。并把变量w记为“工作集窗口尺寸”。通常还把工作集中所包含的页面数目称为“工作集尺寸”,记为︱W(t,w)︱。可以看出,工作集W是二元函数。首先W是t的函数,即随着时间不同,工作集页不同。这包含两方面的含义:(1)不同时间工作集所包含的页面数可能不同,也就是工作集尺寸不同。(2)不同时间工作集所包含的页面也可能不同。6其次,工作集W也是工作集窗口尺寸w的函数。工作集尺寸︱W︱是工作集窗口尺寸w的单调递增函数,且满足蕴含特性,即︱W(t,w)︱︱W(t,w+a)︱,其中a0。图1描述了作为t的函数的工作集的大小。正确的选择工作集窗口尺寸的大小对工作集存储管理策略的有效工作是有很大影响的。如果w选取过大,甚至把整个作业地址空间全部包含在内,就失去了虚存的意义。W选取过小,则将引起频繁缺页,降低了系统效率。正确的策略并不是消除缺页现象,而应使缺页间隔时间保持在合理水平。当此间隔时间过小时,应增加其页框数。过大则应增加多道程序,减少分给进程的页框数,以提高整个系统的效率。因此应把缺页的间隔时间控制在合理的范围,使分给进程的页面数保持在上、下限之间。3.1.3工作集页面置换算法的实现基于工作集的页面置换算法,基本思路就是找出一个不在工作集中的页面并淘汰它。在图2中读者可以看到某台机器的部分页表。因为只有那些在内存中的页面才可以
本文标题:毕业论文设计工作集在页面设置过程中的应用与分析
链接地址:https://www.777doc.com/doc-2365191 .html