精华内容
下载资源
问答
  • 针对许厂煤矿面临的村庄建筑物下压煤、矿井上下矸石大量堆积等问题,提出了在煤柱中掘进巷道并利用矸石回填以置换开采出部分条带煤柱的新技术。在条带开采后所留设的大煤柱中集中布置2条宽4.0m、高5.0m的矸石充填巷,...
  • 提出并阐明了采用条带充填开采置换条带煤柱的基理,分析了影响置换充填开采的关键因素,从充填体宽度、强度及充填方法方面研究了最佳充填开采模式.研究结果表明:条带充填体置换煤柱过程中,条带充填体起到“桥墩”...
  • 页面置换算法

    2019-04-05 18:45:42
    页面置换算法,就是要选出最合适的一个页面,使得置换的效率最高。页面置换算法有很多,简单介绍几个,重点介绍比较重要的LRU及其实现算法。 一、最优页面置换算法 最理想的状态下,我们给页面做个标记,挑选一个最...

    操作系统将内存按照页的进行管理,在需要的时候才把进程相应的部分调入内存。地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,操作系统必须在内存中选择一个页面将其换出内存,以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过(看修改位),就必须把它写回磁盘以更新该页面在磁盘上的副本;如果该页面没有被修改过(如一个包含程序正文的页面),那么它在磁盘上的副本已经是最新的,不需要回写。直接用调入的页面覆盖掉被淘汰的页面就可以了。当发生缺页中断时,虽可随机选择一个页面来置换,但如果每次都选择不常使用的页面会提升系统的性能。如果一个被频繁使用的页面被置换出内存,很可能它在很短时间内又要被调入内存,这会带来不必要的开销。页面置换算法,就是要选出最合适的一个页面,使得置换的效率最高。页面置换算法有很多,简单介绍几个,重点介绍比较重要的LRU及其实现算法。

    1. 有必要指出,“页面置换”问题在计算机设计的其他领域中也会同样发生。例如,多数计算机把最近使用过的32字节或64字节的存储块保存在一个或多个高速缓存中。当这些高速缓存存满之后就必须选择一些块丢掉。除了花费时间较短外(有关操作必须在若干纳秒中完成,而不是像页面置换那样在微秒级上完成),这个问题同页面置换问题完全一样。之所以花费时间较短,其原因是丢掉的高速缓存块可以从内存中获得,而内存既没有寻道时间也不存在旋转延迟。
    2. 第二个例子是Web服务器。服务器可以把一定数量的经常访问的Web页面存放在存储器的高速缓存中。但是,当存储器高速缓存已满并且要访问一个不在高速缓存中的页面时,就必须要置换高速缓存中的某个Web页面。由于在高速缓存中的Web页面不会被修改,因此在磁盘中的Web页面的副本总是最新的。而在虚拟存储系统中,内存中的页面既可能是干净页面也可能是脏页面。除此之外,置换Web页面和置换虚拟内存中的页面需要考虑的问题是类似的。

    一、最优页面置换算法

    最理想的状态下,我们给页面做个标记,挑选一个最远才会被再次用到的页面。最好的页面置换算法,虽然此算法不可能实现。是这样工作的:在缺页中断发生时,有些页面在内存中,其中有一个页面(包含紧接着的下一条指令的那个页面)将很快被访问,其他页面则可能要到10、100或1000条指令后才会被访问,每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。
    最优页面置换算法规定应该置换标记最大的页面。如果一个页面在800万条指令内不会被使用,另外一个页面在600万条指令内不会被使用,则置换前一个页面,从而把因需要调入这个页面而发生的缺页中断推迟到将来,越久越好。
    这个算法惟一的问题就是它是无法实现的。当缺页中断发生时,操作系统无法知道各个页面下一次将在什么时候被访问。(在最短作业优先调度算法中,我们曾遇到同样的情况,即系统如何知道哪个作业是最短的呢?)当然,通过首先在仿真程序上运行程序,跟踪所有页面的访问情况,在第二次运行时利用第一次运行时收集的信息是可以实现最优页面置换算法的。
    用这种方式,可以通过最优页面置换算法对其他可实现算法的性能进行比较。如果操作系统达到的页面置换性能只比最优算法差1%,那么即使花费大量的精力来寻找更好的算法最多也只能换来1%的性能提高。
    为了避免混淆,读者必须清楚以上页面访问情况的记录只针对刚刚被测试过的程序和它的一个特定的输入,因此从中导出的性能最好的页面置换算法也只是针对这个特定的程序和输入数据的。虽然这个方法对评价页面置换算法很有用,但它在实际系统中却不能使用。下面我们将研究可以在实际系统中使用的算法:

    二、最近未使用页面置换算法(NRU)

    为使操作系统能够收集有用的统计信息,在大部分具有虚拟内存的计算机中,系统为每一页面设置了两个状态位。当页面被访问(读或写)时设置访问位R位;当页面(即修改页面)被写入时设置修改位M位。每次访问内存时更新这些位,因此由硬件来设置它们是必要的。一旦设置某位为1,它就一直保持1直到操作系统将它复位。如果硬件没有这些位,则可以进行以下的软件模拟:当启动一个进程时,将其所有的页面都标记为不在内存;一旦访问任何一个页面就会引发一次缺页中断,此时操作系统就可以设置R位(在它的内部表格中),修改页表项使其指向正确的页面,并设为READ ONLY模式,然后重新启动引起缺页中断的指令;如果随后对该页面的修改又引发一次缺页中断,则操作系统设置这个页面的M位并将其改为READ/WRITE模式。
    用R位和M位来构造一个简单的页面置换算法:当启动一个进程时,它的所有页面的两个位都由操作系统设置成0,R位被定期地(比如在每次时钟中断时)清零,以区别最近没有被访问的页面和被访问的页面。
    当发生缺页中断时,操作系统检查所有的页面并根据它们当前的R位和M位的值,把它们分为4类:
    (1)!R&!M //第0类:没有被访问,没有被修改。00
    (2)!R&M //第1类:没有被访问,已被修改。 01
    (3)R&!M //第2类:已被访问,没有被修改。 10
    (4)R&M //第3类:已被访问,已被修改。 11
    尽管第1类初看起来似乎是不可能的,但是一个第3类的页面在它的R位被时钟中断清零后就成了第1类。时钟中断不清除M位是因为在决定一个页面是否需要写回磁盘时将用到这个信息。清除R位而不清除M位产生了第1类页面。
    编号越小的类,越被优先换出。即在最近的一个时钟滴答内,淘汰一个没有被访问但是已经被修改的页面,比淘汰一个被频繁使用但是“clean”的页面要好。
    NRU(Not Recently Used,最近未使用)算法随机地从类编号最小的非空类中挑选一个页面淘汰之。这个算法隐含的意思是,在最近一个时钟滴答中(典型的时间是大约20ms)淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面好。NRU主要优点是易于理解和能够有效地被实现,虽然它的性能不是最好的,但是已经够用了。

    三、先进先出页面置换算法(FIFO)及其改进

    另一种开销较小的页面置换算法是FIFO(First-In First-Out,先进先出)算法。为了解释它是怎样工作的,我们设想有一个超级市场,它有足够的货架能展示k种不同的商品。有一天,某家公司介绍了一种新的方便食品—即食的、冷冻干燥的、可以用微波炉加热的酸乳酪,这个产品非常成功,所以容量有限的超市必须撤掉一种旧的商品以便能够展示该新产品。
    一种可能的解决方法就是找到该超级市场中库存时间最长的商品并将其替换掉(比如某种120年以前就开始卖的商品),理由是现在已经没有人喜欢它了。这实际上相当于超级市场有一个按照引进时间排列的所有商品的链表。新的商品被加到链表的尾部,链表头上的商品则被撤掉。
    同样的思想也可以应用在页面置换算法中。这种算法的思想和队列是一样的,由操作系统维护一个所有当前在内存中的页面的链表,最新进入的页面放在表尾,最久进入的页面放在表头。当发生缺页中断时,淘汰表头的页面并把新调入的页面加到表尾。当FIFO用在超级市场时,可能会淘汰剃须膏,但也可能淘汰面粉、盐或黄油这一类常用商品。因此,当它应用在计算机上时也会引起同样的问题,由于FIFO算法可能会把经常使用的页面置换出去,很少使用纯粹的FIFO算法。这个算法的问题,显然是太过于“公正了”,没有考虑到实际的页面使用频率。一种合理的改进,称为第二次机会算法。即给每个页面增加一个R位,每次先从链表头开始查找,如果R置位,清除R位并且把该页面节点放到链表结尾;如果R是0,那么就是又老又没用到,替换掉。

    四、第二次机会页面置换算法

    FIFO算法可能会把经常使用的页面置换出去,为避免该问题,对该算法做一个简单的修改:检查最老页面的R位。如果R位是0,那么这个页面既老又没有被使用,可以立刻置换掉;如果是1,就将R位清0,并把该页面放到链表的尾端,修改它的装入时间使它就像刚装入的一样,然后继续搜索。
    这一算法称为第二次机会(second chance)算法,页面按照进入内存的时间顺序保存在链表中。
    假设在时间20发生了一次缺页中断,这时最老的页面是A,它是在时刻0到达的。如果A的R位是0,则将它淘汰出内存,或者把它写回磁盘(如果它已被修改过),或者只是简单地放弃(如果它是“干净”的);另一方面,如果其R位已经设置了,则将A放到链表的尾部并且重新设置“装入时间”为当前时刻(20),然后清除R位。然后从B页面开始继续搜索合适的页面。
    第二次机会算法就是寻找一个最近的时钟间隔以来没有被访问过的页面。如果所有的页面都被访问过了,该算法就简化为纯粹的FIFO算法。特别地,想象一下,假设图3-15a中所有的页面的R位都被设置了,操作系统将会一个接一个地把每个页面都移动到链表的尾部并清除被移动的页面的R位。最后算法又将回到页面A,此时它的R位已经被清除了,因此A页面将被淘汰,所以这个算法总是可以结束的。它经常要在链表中移动页面,既降低了效率又不是很有必要。

    五、时钟页面置换算法(clock)

    尽管第二次机会算法是一个比较合理的算法,但它经常要在链表中移动页面,既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中,一个表针指向最老的页面,如图3-16所示。
    当发生缺页中断时,算法首先检查表针指向的页面,如果它的R位是0就淘汰该页面,并把新的页面插入这个位置,然后把表针前移一个位置;如果R位是1就清除R位并把表针前移一个位置,重复这个过程直到找到了一个R位为0的页面为止。了解了这个算法的工作方式,就明白为什么它被称为时钟(clock)算法了。
    这种算法只是模型像时钟,其实就是一个环形链表的第二次机会算法,表针指向最老的页面。缺页中断时,执行相同的操作,包括检查R位等。

    六、最近最少使用页面置换算法(LRU)

    对最优算法的一个很好的近似是基于这样的观察:在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。反过来说,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。这个思想提示了一个可实现的算法:在缺页中断发生时,置换未使用时间最长的页面。这个策略称为LRU(Least Recently Used,最近最少使用)页面置换算法。
    虽然LRU在理论上是可以实现的,但代价很高,为了完全实现LRU,需要在内存中维护一个所有页面的链表,最近最多使用的页面在表头,最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新整个链表。在链表中找到一个页面,删除它,然后把它移动到表头是一个非常费时的操作,即使使用硬件实现也一样费时(假设有这样的硬件)。
    然而,还是有一些使用特殊硬件实现LRU的方法。这个方法要求硬件有一个64位计数器C,它在每条指令执行完后自动加1,每个页表项必须有一个足够容纳这个计数器值的域。在每次访问内存后,将当前的C值保存到被访问页面的页表项中。一旦发生缺页中断,操作系统就检查所有页表项中计数器的值,找到值最小的一个页面,这个页面就是最近最少使用的页面。
    第二个硬件实现的LRU算法。在一个有n个页框的机器中,LRU硬件可以维持一个初值为0的n×n位的矩阵。当访问到页框k时,硬件首先把k行的位都设置成1,再把k列的位都设置成0。在任何时刻,二进制数值最小的行就是最近最少使用的,第二小的行是下一个最近最少使用的,以此类推。

    用软件模拟LRU

    前面两种LRU算法虽然在理论上都是可以实现的,但只有非常少的计算机拥有这种硬件。因此,需要一个能用软件实现的解决方案。一种可能的方案称为NFU(Not Frequently Used,最不常用)算法。该算法将每个页面与一个软件计数器相关联,计数器的初值为0。每次时钟中断时,由操作系统扫描内存中所有的页面,将每个页面的R位(它的值是0或1)加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时,则置换计数器值最小的页面。

    NFU的主要问题是它从来不忘记任何事情。比如,在一个多次(扫描)编译器中,在第一次扫描中被频繁使用的页面在程序进入第二次扫描时,其计数器的值可能仍然很高。实际上,如果第一次扫描的执行时间恰好是各次扫描中最长的,含有以后各次扫描代码的页面的计数器可能总是比含有第一次扫描代码的页面小,结果是操作系统将置换有用的页面而不是不再使用的页面。

    幸运的是只需对NFU做一个小小的修改就能使它很好地模拟LRU。其修改分为两部分:首先,在R位被加进之前先将计数器右移一位;其次,将R位加到计数器最左端的位而不是最右端的位。

    修改以后的算法称为老化(aging)算法。假设在第一个时钟滴答后,页面0到页面5的R位值分别是1、0、1、0、1、1(页面0为1,页面1为0,页面2为1,以此类推)。换句话说,在时钟滴答0到时钟滴答1期间,访问了页0、2、4、5,它们的R位设置为1,而其他页面的R位仍然是0。对应的6个计数器在经过移位并把R位插入其左端后的值。
    发生缺页中断时,将置换计数器值最小的页面。如果一个页面在前面4个时钟滴答中都没有访问过,那么它的计数器最前面应该有4个连续的0,因此它的值肯定要比在前面三个时钟滴答中都没有被访问过的页面的计数器值小。
    该算法与LRU有两个区别。页面3和页面5,它们都连续两个时钟滴答没有被访问过了,而在两个时钟滴答之前的时钟滴答中它们都被访问过。根据LRU,如果必须置换一个页面,则应该在这两个页面中选择一个。然而现在的问题是,我们不知道在时钟滴答1到时钟滴答2期间它们中的哪一个页面是后被访问到的。因为在每个时钟滴答中只记录了一位,所以无法区分在一个时钟滴答中哪个页面在较早的时间被访问以及哪个页面在较晚的时间被访问,因此,我们所能做的就是置换页面3,原因是页面5在更往前的两个时钟滴答中也被访问过而页面3没有。
    LRU和老化算法的第二个区别是老化算法的计数器只有有限位数(本例中是8位),这就限制了其对以往页面的记录。如果两个页面的计数器都是0,我们只能在两个页面中随机选一个进行置换。实际上,有可能其中一个页面上次被访问是在9个时钟滴答以前,另一个页面是在1000个时钟滴答以前,而我们却无法看到这些。在实践中,如果时钟滴答是20ms,8位一般是够用的。假如一个页面已经有160ms没有被访问过,那么它很可能并不重要。

    七、工作集算法

    在单纯的分页系统里,刚启动进程时,在内存中并没有页面。在CPU试图取第一条指令时就会产生一次缺页中断,使操作系统装入含有第一条指令的页面。其他由访问全局数据和堆栈引起的缺页中断通常会紧接着发生。一段时间以后,进程需要的大部分页面都已经在内存了,进程开始在较少缺页中断的情况下运行。这个策略称为请求调页(demand paging),因为页面是在需要时被调入的,而不是预先装入。
    编写一个测试程序很容易,在一个大的地址空间中系统地读所有的页面,将出现大量的缺页中断,因此会导致没有足够的内存来容纳这些页面。不过幸运的是,大部分进程不是这样工作的,它们都表现出了一种局部性访问行为,即在进程运行的任何阶段,它都只访问较少的一部分页面。例如,在一个多次扫描编译器中,各次扫描时只访问所有页面中的一小部分,并且是不同的部分。
    一个进程当前正在使用的页面的集合称为它的工作集。如果整个工作集都被装入到了内存中,那么进程在运行到下一运行阶段(例如,编译器的下一遍扫描)之前,不会产生很多缺页中断。若内存太小而无法容纳下整个工作集,那么进程的运行过程中会产生大量的缺页中断,导致运行速度也会变得很缓慢,因为通常只需要几个纳秒就能执行完一条指令,而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每10ms只能执行一到两条指令,那么它将会需要很长时间才能运行完。若每执行几条指令程序就发生一次缺页中断,那么就称这个程序发生了颠簸(thrashing)。
    在多道程序设计系统中,经常会把进程转移到磁盘上(即从内存中移走所有的页面),这样可以让其他的进程有机会占有CPU。有一个问题是,当该进程再次调回来以后应该怎样办?从技术的角度上讲,并不需要做什么。该进程会一直产生缺页中断直到它的工作集全部被装入内存。然而,每次装入一个进程时都要产生20、100甚至1000次缺页中断,速度显然太慢了,并且由于CPU需要几毫秒时间处理一个缺页中断,因此有相当多的CPU时间也被浪费了。
    所以不少分页系统都会设法跟踪进程的工作集,以确保在让进程运行以前,它的工作集就已在内存中了。该方法称为工作集模型(working set model),其目的在于大大减少缺页中断率。在让进程运行前预先装入其工作集页面也称为预先调页(prepaging)。请注意工作集是随着时间变化的。
    大多数程序都不是均匀地访问它们的地址空间的,而访问往往是集中于一小部分页面。一次内存访问可能会取出一条指令,也可能会取数据,或者是存储数据。在任一时刻t,都存在一个集合,它包含所有最近k次内存访问所访问过的页面。这个集合w(k, t)就是工作集。因为最近k=1次访问肯定会访问最近k>1次访问所访问过的页面,所以w(k, t)是k的单调非递减函数。随着k的变大,w(k, t)是不会无限变大的,因为程序不可能访问比它的地址空间所能容纳的页面数目上限还多的页面,并且几乎没有程序会使用每个页面。图3-19描述了作为k的函数的工作集的大小。
    事实上大多数程序会任意访问一小部分页面,但是这个集合会随着时间而缓慢变化,这个事实也解释了为什么一开始曲线快速地上升而k较大时上升会变慢。举例来说,某个程序执行占用了两个页面的循环,并使用四个页面上的数据,那么可能每执行1000条指令,它就会访问这六个页面一次,但是最近的对其他页面的访问可能是在100万条指令以前的初始化阶段。因为这是个渐进的过程,k值的选择对工作集的内容影响不大。换句话说,k的值有一个很大的范围,它处在这个范围中时工作集不会变。因为工作集随时间变化很慢,那么当程序重新开始时,就有可能根据它上次结束时的工作集对要用到的页面做一个合理的推测,预先调页就是在程序继续运行之前预先装入推测出的工作集的页面。
    为实现工作集模型,操作系统必须跟踪哪些页面在工作集中。通过这些信息可以直接推导出一个合理的页面置换算法:当发生缺页中断时,淘汰一个不在工作集中的页面。为了实现该算法,就需要一种精确的方法来确定哪些页面在工作集中。根据定义,工作集就是最近k次内存访问所使用过的页面的集合(有些设计者使用最近k次页面访问,但是选择是任意的)。为了实现工作集算法,必须预先选定k的值。一旦选定某个值,每次内存访问之后,最近k次内存访问所使用过的页面的集合就是惟一确定的了。
    有了工作集的定义并不意味着存在一种有效的方法能够在程序运行期间及时地计算出工作集。设想有一个长度为k的移位寄存器,每进行一次内存访问就把寄存器左移一位,然后在最右端插入刚才所访问过的页面号。移位寄存器中的k个页面号的集合就是工作集。理论上,当缺页中断发生时,只要读出移位寄存器中的内容并排序;然后删除重复的页面。结果就是工作集。然而,维护移位寄存器并在缺页中断时处理它所需的开销很大,因此该技术从来没有被使用过。
    作为替代,可以使用几种近似的方法。一种常见的近似方法就是,不是向后找最近k次的内存访问,而是考虑其执行时间。例如,按照以前的方法,我们定义工作集为前1000万次内存访问所使用过的页面的集合,那么现在就可以这样定义:工作集即是过去10ms中的内存访问所用到的页面的集合。这样的模型很合适且更容易实现。要注意到,每个进程只计算它自己的执行时间。因此,如果一个进程在T时刻开始,在(T+100)ms的时刻使用了40ms CPU时间,对工作集而言,它的时间就是40ms。一个进程从它开始执行到当前所实际使用的CPU时间总数通常称作当前实际运行时间。通过这个近似的方法,进程的工作集可以被称为在过去的t秒实际运行时间中它所访问过的页面的集合。
    现在看一下基于工作集的页面置换算法。基本思路就是找出一个不在工作集中的页面并淘汰它。在图3-20中读者可以看到某台机器的部分页表。因为只有那些在内存中的页面才可以作为候选者被淘汰,所以该算法忽略了那些不在内存中的页面。每个表项至少包含两条信息:上次使用该页面的近似时间和R(访问)位。空白的矩形表示该算法不需要的其他域,如页框号、保护位、M(修改)位。
    该算法工作方式如下。如前所述,假定使用硬件来置R位和M位。同样,假定在每个时钟滴答中,有一个定期的时钟中断会用软件方法来清除R位。每当缺页中断发生时,扫描页表以找出一个合适的页面淘汰之。
    在处理每个表项时,都需要检查R位。如果它是1,就把当前实际时间写进页表项的“上次使用时间”域,以表示缺页中断发生时该页面正在被使用。既然该页面在当前时钟滴答中已经被访问过,那么很明显它应该出现在工作集中,并且不应该被删除(假定t横跨多个时钟滴答)。
    如果R是0,那么表示在当前时钟滴答中,该页面还没有被访问过,则它就可以作为候选者被置换。为了知道它是否应该被置换,需要计算它的生存时间(即当前实际运行时间减去上次使用时间),然后与t做比较。如果它的生存时间大于t,那么这个页面就不再在工作集中,而用新的页面置换它。扫描会继续进行以更新剩余的表项。
    然而,如果R是0同时生存时间小于或等于t,则该页面仍然在工作集中。这样就要把该页面临时保留下来,但是要记录生存时间最长(“上次使用时间”的最小值)的页面。如果扫描完整个页表却没有找到适合被淘汰的页面,也就意味着所有的页面都在工作集中。在这种情况下,如果找到了一个或者多个R=0的页面,就淘汰生存时间最长的页面。在最坏情况下,在当前时间滴答中,所有的页面都被访问过了(也就是都有R=1),因此就随机选择一个页面淘汰,如果有的话最好选一个干净页面。
    当缺页中断发生后,需要扫描整个页表才能确定被淘汰的页面,因此基本工作集算法是比较费时的。

    简单来说,工作集就是在最近k次内存访问所使用过的页面的集合。原始的工作集算法同样代价很大,对它进行简化:在过去Nms的北村访问中所用到的页面的集合。所以,在实现的时候,可以给每个页面一个计时器。需要置换页面时,同实际时间进行对比,R为1,更新到现在时间;R为0,在规定阈值之外的页面可以被置换。同样,这个算法也可以用时钟的思想进行改进。

    八、Linux使用的页面置换算法

    Linux区分四种不同的页面:不可回收的、可交换的、可同步的、可丢弃的。
    不可回收的:保留的和锁定在内存中的页面,以及内核态栈等。
    可交换的:必须在回收之前写回到交换区或者分页磁盘分区。
    可同步的:若为脏页面,必须要先写回。
    可丢弃的:可以被立即回收的页面。
    Linux并没有像我们之前单纯讨论算法时那样,在缺页中断产生的时候才进行页面回收。Linux有一个守护进程kswapd,比较每个内存区域的高低水位来检测是否有足够的空闲页面来使用。每次运行时,仅有一个确定数量的页面被回收。这个阈值是受限的,以控制I/O压力。每次执行回收,先回收容易的,再处理难的。回收的页面会加入到空闲链表中。
    算法是一种改进地LRU算法,维护两组标记:活动/非活动和是否被引用。第一轮扫描清除引用位,如果第二轮运行确定被引用,就提升到一个不太可能回收的状态,否则将该页面移动到一个更可能被回收的状态。处于非活动列表的页面,自从上次检查未被引用过,因而是移除的最佳选择。被引用但不活跃的页面同样会被考虑回收,是因为一些页面是守护进程访问的,可能很长时间不再使用。另外,内存管理还有一个守护进程pdflush,会定期醒来,写回脏页面;或者可用内存下降到一定水平后被内核唤醒。

    页面置换算法小结

    最优算法在当前页面中置换最后要访问到的页面。不幸的是,没有办法来判定哪个页面是最后一个要访问的,因此实际上该算法不能使用。然而,它可以作为衡量其他算法的基准

    NRU算法根据R位和M位的状态把页面分为四类。从编号最小的类中随机选择一个页面置换。该算法易于实现,但是性能不是很好,还存在更好的算法。

    FIFO算法通过维护一个页面的链表来记录它们装入内存的顺序。淘汰的是最老的页面,但是该页面可能仍在使用,因此FIFO算法不是一个好的选择。

    第二次机会算法是对FIFO算法的改进,它在移出页面前先检查该页面是否正在被使用。如果该页面正在被使用,就保留该页面。这个改进大大提高了性能。时钟算法是第二次机会算法的另一种实现。它具有相同的性能特征,而且只需要更少的执行时间。

    LRU算法是一种非常优秀的算法,但是只能通过特定的硬件来实现。如果机器中没有该硬件,那么也无法使用该算法。NFU是一种近似于LRU的算法,它的性能不是非常好,然而,老化算法更近似于LRU并且可以更有效地实现,是一个很好的选择。

    工作集算法有合理的性能,但它的实现开销较大

    总之,最好的算法是老化算法,基于LRU。具有良好的页面调度性能,可以有效地实现。也存在其他一些算法,但在实际应用中,这种算法可能是最重要的。

    展开全文
  • 从问题出发,设计了由量子进化,最佳模式和其他优化技术所构成的混合量子算法(HQA)。HQA模仿量子行为迭代演化,将种群一分为二,种群1在量子作用和其他优化作用下,探索解空间。种群2保留最佳模式,提高了搜索的...
  • 然后结合功能分层思想和故障树分析方法进行故障模式分析,将故障分级归类。最后故障仿真实例表明,文中提出的故障建模方法能够有效模拟出陀螺故障特征,对一般系统或部件的故障建模问题具有积极的指导作用。
  • 设计模式总结链接 ...简解模板方法是一种基于继承的代码复用的基本技术,很多地方需要重用另一个类许多方法时,可以使用继承的方式进行复用,同时还可以最其进行个性化的改造。二。用途主要是为了

    设计模式总结链接


    模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的形式实现,然后声明一些抽象方法来迫使子类实现剩余的逻辑。不同的子类可以以不同的方式实现这些抽象方法,从而对剩余的逻辑有不同的实现。


    一。简解

    模板方法是一种基于继承的代码复用的基本技术,很多地方需要重用另一个类许多方法时,可以使用继承的方式进行复用,同时还可以最其进行个性化的改造。


    二。用途

    主要是为了促进代码复用,减少工作量,使用模板方法使得程序更加规整,提高可读性。


    三。实例

    模板方法所代表的行为称为顶级行为,其逻辑称为顶级逻辑。模板方法模式的静态结构图如下所示:
    这里写图片描述

    这里涉及到两个角色:
    抽象模板(Abstract Template)角色有如下责任:

    • 定义了一个或多个抽象操作,以便让子类实现。这些抽象操作叫做基本操作,它们是一个顶级逻辑的组成步骤。
    • 定义并实现了一个模板方法。这个模板方法一般是一个具体方法,它给出了一个顶级逻辑的骨架,而逻辑的组成步骤在相应的抽象操作中,推迟到子类实现。顶级逻辑也有可能调用一些具体方法。

        具体模板(Concrete Template)角色又如下责任:
        

    • 实现父类所定义的一个或多个抽象方法,它们是一个顶级逻辑的组成步骤。
    • 每一个抽象模板角色都可以有任意多个具体模板角色与之对应,而每一个具体模板角色都可以给出这些抽象方法(也就是顶级逻辑的组成步骤)的不同实现,从而使得顶级逻辑的实现各不相同。

    源代码
    抽象模板角色类,abstractMethod()、hookMethod()等基本方法是顶级逻辑的组成步骤,这个顶级逻辑由templateMethod()方法代表。

    public abstract class AbstractTemplate {
        /**
         * 模板方法
         */
        public void templateMethod(){
            //调用基本方法
            abstractMethod();
            hookMethod();
            concreteMethod();
        }
        /**
         * 基本方法的声明(由子类实现)
         */
        protected abstract void abstractMethod();
        /**
         * 基本方法(空方法)
         */
        protected void hookMethod(){}
        /**
         * 基本方法(已经实现)
         */
        private final void concreteMethod(){
            //业务相关的代码
        }
    }

    具体模板角色类,实现了父类所声明的基本方法,abstractMethod()方法所代表的就是强制子类实现的剩余逻辑,而hookMethod()方法是可选择实现的逻辑,不是必须实现的。

    public class ConcreteTemplate extends AbstractTemplate{
        //基本方法的实现
        @Override
        public void abstractMethod() {
            //业务相关的代码
        }
        //重写父类的方法
        @Override
        public void hookMethod() {
            //业务相关的代码
        }
    }

    模板模式的关键是:子类可以置换掉父类的可变部分,但是子类却不可以改变模板方法所代表的顶级逻辑。

      每当定义一个新的子类时,不要按照控制流程的思路去想,而应当按照“责任”的思路去想。换言之,应当考虑哪些操作是必须置换掉的,哪些操作是可以置换掉的,以及哪些操作是不可以置换掉的。使用模板模式可以使这些责任变得清晰。

    模板方法模式中的方法   模板方法中的方法可以分为两大类:模板方法和基本方法。
    模板方法   一个模板方法是定义在抽象类中的,把基本操作方法组合在一起形成一个总算法或一个总行为的方法。   一个抽象类可以有任意多个模板方法,而不限于一个。每一个模板方法都可以调用任意多个具体方法。
    基本方法   基本方法又可以分为三种:抽象方法(Abstract Method)、具体方法(Concrete Method)和钩子方法(Hook Method)。
      

    • 抽象方法:一个抽象方法由抽象类声明,由具体子类实现。在Java语言里抽象方法以abstract关键字标示。
    • 具体方法:一个具体方法由抽象类声明并实现,而子类并不实现或置换。
    • 钩子方法:一个钩子方法由抽象类声明并实现,而子类会加以扩展。通常抽象类给出的实现是一个空实现,作为方法的默认实现。

      在上面的例子中,AbstractTemplate是一个抽象类,它带有三个方法。其中abstractMethod()是一个抽象方法,它由抽象类声明为抽象方法,并由子类实现;hookMethod()是一个钩子方法,它由抽象类声明并提供默认实现,并且由子类置换掉。concreteMethod()是一个具体方法,它由抽象类声明并实现。

      默认钩子方法
      一个钩子方法常常由抽象类给出一个空实现作为此方法的默认实现。这种空的钩子方法叫做“Do Nothing Hook”。显然,这种默认钩子方法在缺省适配模式里面已经见过了,一个缺省适配模式讲的是一个类为一个接口提供一个默认的空实现,从而使得缺省适配类的子类不必像实现接口那样必须给出所有方法的实现,因为通常一个具体类并不需要所有的方法。

    命名规则 命名规则是设计师之间赖以沟通的管道之一,使用恰当的命名规则可以帮助不同设计师之间的沟通。   钩子方法的名字应当以do开始,这是熟悉设计模式的Java开发人员的标准做法。在上面的例子中,钩子方法hookMethod()应当以do开头;在HttpServlet类中,也遵从这一命名规则,如doGet()、doPost()等方法。


    计算存款利息系统   考虑一个计算存款利息的例子。假设系统需要支持两种存款账号,即货币市场(Money Market)账号和定期存款(Certificate of
    Deposite)账号。这两种账号的存款利息是不同的,因此,在计算一个存户的存款利息额时,必须区分两种不同的账号类型。
      这个系统的总行为应当是计算出利息,这也就决定了作为一个模板方法模式的顶级逻辑应当是利息计算。由于利息计算涉及到两个步骤:一个基本方法给出账号种类,另一个基本方法给出利息百分比。这两个基本方法构成具体逻辑,因为账号的类型不同,所以具体逻辑会有所不同。
      显然,系统需要一个抽象角色给出顶级行为的实现,而将两个作为细节步骤的基本方法留给具体子类实现。由于需要考虑的账号有两种:一是货币市场账号,二是定期存款账号。系统的类结构如下图所示。
    这里写图片描述

    源代码
    抽象模板角色类

    public abstract class Account {
        /**
         * 模板方法,计算利息数额
         * @return    返回利息数额
         */
        public final double calculateInterest(){
            double interestRate = doCalculateInterestRate();
            String accountType = doCalculateAccountType();
            double amount = calculateAmount(accountType);
            return amount * interestRate;
        }
        /**
         * 基本方法留给子类实现
         */
        protected abstract String doCalculateAccountType();
        /**
         * 基本方法留给子类实现
         */
        protected abstract double doCalculateInterestRate();
        /**
         * 基本方法,已经实现
         */
        private double calculateAmount(String accountType){
            /**
             * 省略相关的业务逻辑
             */
            return 7243.00;
        }
    }

    具体模板角色类

    public class MoneyMarketAccount extends Account {
    
        @Override
        protected String doCalculateAccountType() {
    
            return "Money Market";
        }
    
        @Override
        protected double doCalculateInterestRate() {
    
            return 0.045;
        }
    
    }
    public class CDAccount extends Account {
    
        @Override
        protected String doCalculateAccountType() {
            return "Certificate of Deposite";
        }
    
        @Override
        protected double doCalculateInterestRate() {
            return 0.06;
        }
    
    }

    客户端类

    public class Client {
    
        public static void main(String[] args) {
            Account account = new MoneyMarketAccount();
            System.out.println("货币市场账号的利息数额为:" + account.calculateInterest());
            account = new CDAccount();
            System.out.println("定期账号的利息数额为:" + account.calculateInterest());
        }
    
    }



    模板方法模式在Servlet中的应用
      使用过Servlet的人都清楚,除了要在web.xml做相应的配置外,还需继承一个叫HttpServlet的抽象类。HttpService类提供了一个service()方法,这个方法调用七个do方法中的一个或几个,完成对客户端调用的响应。这些do方法需要由HttpServlet的具体子类提供,因此这是典型的模板方法模式。下面是service()方法的源代码:

    protected void service(HttpServletRequest req, HttpServletResponse resp)
            throws ServletException, IOException {
    
            String method = req.getMethod();
    
            if (method.equals(METHOD_GET)) {
                long lastModified = getLastModified(req);
                if (lastModified == -1) {
                    // servlet doesn't support if-modified-since, no reason
                    // to go through further expensive logic
                    doGet(req, resp);
                } else {
                    long ifModifiedSince = req.getDateHeader(HEADER_IFMODSINCE);
                    if (ifModifiedSince < (lastModified / 1000 * 1000)) {
                        // If the servlet mod time is later, call doGet()
                        // Round down to the nearest second for a proper compare
                        // A ifModifiedSince of -1 will always be less
                        maybeSetLastModified(resp, lastModified);
                        doGet(req, resp);
                    } else {
                        resp.setStatus(HttpServletResponse.SC_NOT_MODIFIED);
                    }
                }
    
            } else if (method.equals(METHOD_HEAD)) {
                long lastModified = getLastModified(req);
                maybeSetLastModified(resp, lastModified);
                doHead(req, resp);
    
            } else if (method.equals(METHOD_POST)) {
                doPost(req, resp);
    
            } else if (method.equals(METHOD_PUT)) {
                doPut(req, resp);        
    
            } else if (method.equals(METHOD_DELETE)) {
                doDelete(req, resp);
    
            } else if (method.equals(METHOD_OPTIONS)) {
                doOptions(req,resp);
    
            } else if (method.equals(METHOD_TRACE)) {
                doTrace(req,resp);
    
            } else {
                //
                // Note that this means NO servlet supports whatever
                // method was requested, anywhere on this server.
                //
    
                String errMsg = lStrings.getString("http.method_not_implemented");
                Object[] errArgs = new Object[1];
                errArgs[0] = method;
                errMsg = MessageFormat.format(errMsg, errArgs);
    
                resp.sendError(HttpServletResponse.SC_NOT_IMPLEMENTED, errMsg);
            }
        }

    当然,这个service()方法也可以被子类置换掉。
    下面给出一个简单的Servlet例子:
    这里写图片描述
    从上面的类图可以看出,TestServlet类是HttpServlet类的子类,并且置换掉了父类的两个方法:doGet()和doPost()。

    public class TestServlet extends HttpServlet {
    
        public void doGet(HttpServletRequest request, HttpServletResponse response)
                throws ServletException, IOException {
    
            System.out.println("using the GET method");
    
        }
    
        public void doPost(HttpServletRequest request, HttpServletResponse response)
                throws ServletException, IOException {
    
            System.out.println("using the POST method");
        }
    
    }

    从上面的例子可以看出这是一个典型的模板方法模式。
    HttpServlet担任抽象模板角色
    模板方法:由service()方法担任。
    基本方法:由doPost()、doGet()等方法担任。
    TestServlet担任具体模板角色
    TestServlet置换掉了父类HttpServlet中七个基本方法中的其中两个,分别是doGet()和doPost()。


    四。优点

    • 提高代码重用性
    • 使得系统中顶层类和底层类具有相同的方法(内容是个性的)
    • 减少了编程人员工作量

    五。不足

    暂无,模板方法主要适用与继承关系中,优缺得看使用场景。

    展开全文
  • Java设计模式_(行为型)_模版方法模式

    万次阅读 2017-10-13 16:13:48
    引用百科 模板方法模式是所有模式中最为常见的几个模式之一,是基于继承的代码复用的基本技术。模板方法模式需要开发抽象类和具体子类的设计师之间的协作。它是类的行为模式,准备一个抽象类,将部分逻辑以具体方法...

    引用百科

    模板方法模式是所有模式中最为常见的几个模式之一,是基于继承的代码复用的基本技术。
    模板方法模式需要开发抽象类和具体子类的设计师之间的协作。它是类的行为模式,准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的形式实现,然后声明一些抽象方法来迫使子类实现剩余的逻辑。不同的子类可以以不同的方式实现这些抽象方法,从而对剩余的逻辑有不同的实现。这就是模板方法模式的用意,模板方法所代表的行为称为顶级行为,其逻辑称为顶级逻辑。


    使用说明

    在一个方法中定义一个算法的骨架,而将一些步骤延迟到子类中。模板方法使的子类可以在不改变算法结构的情况下,重新定义算法中的某些步骤。模版中将主要的方法定义为final,防止子类修改算法骨架,将子类必须实现的方法定义为abstract。而普通的方法(无final或abstract修饰)则称之为钩子。


    相关角色

    1、抽象模板角色:
    定义了一个或多个抽象操作,以便让子类实现。这些抽象操作叫做基本操作,它们是一个顶级逻辑的组成步骤。
    定义并实现了一个模板方法。这个模板方法一般是一个具体方法,它给出了一个顶级逻辑的骨架,而逻辑的组成步骤在相应的抽象操作中,推迟到子类实现。顶级逻辑也有可能调用一些具体方法。


    2、具体模板角色(模版子类)
    实现父类所定义的一个或多个抽象方法,它们是一个顶级逻辑的组成步骤。
    每一个抽象模板角色都可以有任意多个具体模板角色与之对应,而每一个具体模板角色都可以给出这些抽象方法(也就是顶级逻辑的组成步骤)的不同实现,从而使得顶级逻辑的实现各不相同。


    具体实现



    相关代码

    1、抽象模版角色类

    //抽象模板角色类
    public abstract class AbstractTemplate {
    
    	// 模板方法
    	public final void request(String msg) {
    		methodA(msg);
    		methodB(msg);
    		success();
    	}
    
    	// 基本方法留给子类实现
    	public abstract void methodA(String msg);
    
    	// 基本方法留给子类实现
    	public abstract void methodB(String msg);
    
    	// 基本方法,已经实现
    	private void success() {
    		System.out.println("执行处理完成!");
    		// 业务处理逻辑...
    	}
    
    }

    2、具体模版实现类

    //模版具体实现类A
    public class RealemplateA extends AbstractTemplate {
    
    	@Override
    	public void methodA(String msg) {
    		System.out.println("A类 业务A处理..."+msg);
    	}
    
    	@Override
    	public void methodB(String msg) {
    		System.out.println("A类 业务B处理..."+msg);
    	}
    }
    
    //模版具体实现类B
    public class RealemplateB extends AbstractTemplate {
    
    	@Override
    	public void methodA(String msg) {
    		System.out.println("B类 业务A处理..." + msg);
    	}
    
    	@Override
    	public void methodB(String msg) {
    		System.out.println("B类 业务B处理..." + msg);
    	}
    }

    3、客户端Client测试

    public class Client {
    
    	public static void main(String[] args) {
    		// 创建模版
    		AbstractTemplate tmp = new RealemplateA();
    		tmp.request("测试");
    
    		tmp = new RealemplateB();
    		tmp.request("发布");
    	}
    }


    以上代码简单实现了模版方法模式,运行输出:

    A类 业务A处理...测试
    A类 业务B处理...测试
    执行处理完成!
    B类 业务A处理...发布
    B类 业务B处理...发布
    执行处理完成!

    模板模式的关键是:子类可以置换掉父类的可变部分,但是子类却不可以改变模板方法所代表的顶级逻辑。
    每当定义一个新的子类时,应当考虑哪些操作是必须置换掉的,哪些操作是可以置换掉的,以及哪些操作是不可以置换掉的。使用模板模式可以使这些责任变得清晰。


    优缺点:

    优点:
    1)模板方法模式在一个类中形式化地定义算法,而由它的子类实现细节的处理。
    2)模板方法是一种代码复用的基本技术。它们在类库中尤为重要,它们提取了类库中的公共行为。
    3)模板方法模式导致一种反向的控制结构,通过对子类的扩展增加新的行为,符合“开闭原则”。

    缺点:
    1)每个不同的实现都需要定义一个子类,这会导致类的个数增加,系统更加庞大,设计也更加抽象。


    展开全文
  • OS- -内存之页面置换算法 文章目录OS- -内存之页面置换算法一、内存之页面置换算法1.最优页面置换算法2.最近未使用页面置换算法3.先进先出页面置换算法4.第二次机会页面置换算法5.时钟页面置换算法6.最近最少使用...

    OS- -内存之页面置换算法

    一、内存之页面置换算法

    • 当发生缺页异常时,操作系统会选择一个页面进行换出从而为新进来的页面腾出空间
    • 如果要换出的页 面在内存中已经被修改,那么必须将其写到磁盘中以使磁盘副本保持最新状态。如果页面没有被修改 过,并且磁盘中的副本也已经是最新的,那么就不需要进行重写。那么就直接使用调入的页面覆盖需 要移除的页面就可以了
    • 当发生缺页中断时,虽然可以随机的选择一个页面进行置换,但是如果每次都选择一个不常用的页面会 提升系统的性能。如果一个经常使用的页面被换出,那么这个页面在短时间内又可能被重复使用,那么 就可能会造成额外的性能开销

    在关于页面的主题上有很多页面置换算法(page replacement algorithms),这些已经从理论上和实践上得到了证明。

    • 需要指出的是,页面置换问题在计算机的其他领域中也会出现。例如,多数计算机把最近使用过的32 字节或者64字节的存储块保存在一个或多个高速缓存中。当缓存满的时候,一些块就被选择和移除
    • 这些块的移除除了花费时间较短外,这个问题同页面置换问题完全一样。之所以花费时间较短,是因为 丢掉的高速缓存可以从内存中获取,而内存没有寻找磁道的时间也不存在旋转延迟
    • 第二个例子是Web服务器。服务器会在内存中缓存一些经常使用到的Web页面。然而,当缓存满了并 且已经引用了新的页面,那么必须决定退出哪个Web页面。
    • 高速缓存中的Web页面不会被修改。因 此磁盘中的Web页面经常是最新的,同样的考虑也适用在虚拟内存中。在虚拟系统中,内存中的页面 可能会修改也可能不会修改

    下面我们就来探讨一下有哪些页面置换算法。

    1.最优页面置换算法

    最优的页面置换算法很容易描述但在实际情况下很难实现。

    • 它的工作流程如下:
    • 在缺页中断发生时,这 些页面将在下一条指令(包含该指令的页面)上被引用。其他页面则可能要到10、100或者1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。
    • 最优化的页面算法表明应该标记最大的页面。如果一个页面在800万条指令内不会被使用,另外一个页 面在600万条指令内不会被使用,则置换前一个页面,从而把需要调入这个页面而发生的缺页中断推 迟。

    计算机也像人类一样,会把不愿意做的事情尽可能的往后拖。

    • 这个算法最大的问题时无法实现。当缺页中断发生时,操作系统无法知道各个页面的下一次将在什么时 候被访问。这种算法在实际过程中根本不会使用

    2.最近未使用页面置换算法

    • 为了能够让操作系统收集页面使用信息,大部分使用虚拟地址的计算机都有两个状态位,R和M,来和 每个页面进行关联。
    • 每当引用页面(读入或写入)时都设置R,写入(即修改)页面时设置M,这些 位包含在每个页表项中,就像下面所示:
      在这里插入图片描述
    • 因为每次访问时都会更新这些位,因此由硬件来设置它们非常重要。一旦某个位被设置为1,就会一 直保持1直到操作系统下次来修改此位。
    • 如果硬件没有这些位,那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟。
    • 启动一个进 程时,将其所有的页面都标记为不在内存一旦访问任何一个页面就会引发一次缺页中断,此时操作 系统就可以设置R位(在它的内部表中),修改页表项使其指向正确的页面,并设置为READ ONLY 模式,然后重新启动引起缺页中断的指令。
    • 如果页面随后被修改,就会发生另一个缺页异常。从而允许操作系统设置M位并把页面的模式设置为READ/WRITE。
    • 可以用R位和M位来构造一个简单的页面置换算法:当启动一个进程时,操作系统将其所有页面的两 个位都设置为0。R位定期的被清零(在每个时钟中断)。用来将最近未引用的页面和已引用的页面分 开。
    • 当出现缺页中断后,操作系统会检查所有的页面,并根据它们的R位和M位将当前值分为四类:
    • •第0类:没有引用R,没有修改M
    • •第1类:没有引用R,已修改M
    • •第2类:引用R,没有修改M
    • •第3类:已被访问R,已被修改M
    • 尽管看起来好像无法实现第一类页面,但是当第三类页面的R位被时钟中断清除时,它们就会发生。时钟中断不会清除M位,因为需要这个信息才能知道是否写回磁盘中。清除R但不清除M会导致出现 一类页面。
    • NRU(Not Recently Used)算法从编号最小的非空类中随机删除一个页面
    • 此算法隐含的思想是, 在一个时钟内(约20ms)淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好, NRU的主要优点是易于理解并且能够有效的实现

    3.先进先出页面置换算法

    • 另一种开销较小的方式是使用FIF0(First-In,First-Out)算法,这种类型的数据结构也适用在页 面置换算法中。
    • 由操作系统维护一个所有在当前内存中的页面的链表,最早进入的放在表头,最新进入 的页面放在表尾。
    • 发生缺页异常时,会把头部的页移除并且把新的页添加到表尾
    • 还记得缺页异常什么时候发生吗?我们知道应用程序访问内存会进行虚拟地址到物理地址的映 射,缺页异常就发生在虚拟地址无法映射到物理地址的时候。因为实际的物理地址要比虚拟地址 小很多,所以缺页经常会发生
    • 先进先出页面可能是最简单的页面替换算法了。在这种算法中,操作系统会跟踪链表中内存中的所有 页。

    下面我们举个例子看一下
    在这里插入图片描述

    • •初始化的时候,没有任何页面,所以第一次的时候会检查页面1是否位于链表中,没有在链表中,那么就是MISS ,页面1进入链表,链表的先进先出的方向如图所示。
    • •类似的,第二次会先检查页面2是否位于链表中,没有在链表中,那么页面2进入链表,状态为 MISS ,依次类推。
    • •我们来看第四次,此时的链表为12 3,第四次会检查页面2是否位于链表中,经过检索后, 发现2在链表中,那么状态就是HIT ,并不会再进行入队和出队操作,第五次也是一样的。
    • •下面来看第六次,此时的链表还是12 3,因为之前没有执行进入链表操作,页面5会首先进 行检查,发现链表中没有页面5,则执行页面5的进入链表操作,页面2执行出链表的操作,执 行完成后的链表顺序为235

    4.第二次机会页面置换算法

    • 我们上面学到的FIFO链表页面有个缺陷,那就是出链和入链并不会进行check检查,这样就会容 易把经常使用的页面置换出去(无法显示热点数据)
    • 为了避免这一问题,我们对该算法做一个简单的修改:我们检查最老页 面的R位,如果是0,那么这个页面就是最老的而且没有被使用,那么这个页面就会被立刻换出
    • 如果R位是1,那么就清除此位,此页面会被放在链表的尾部,修改它的装入时间就像刚放进来的一 样。然后继续搜索。
    • 这种算法叫做 第二次机会(second chance)算法,就像下面这样,我们看到页面A到H保留在链表 中,并按到达内存的时间排序。
      在这里插入图片描述
    • a)按照先进先出的方法排列的页面;
    • b)在时刻20处发生缺页异常中断并且A的R位已经设置时的 页面链表。
    • 假设缺页异常发生在时刻20处,这时最老的页面是A ,它是在0时刻到达的。如果A的R位是03 那么它将被淘汰出内存,或者把它写回磁盘(如果它已经被修改过),或者只是简单的放弃(如果它是 未被修改过)。
    • 另一方面,如果它的R位已经设置了,则将A放到链表的尾部并且重新设置装入时间 为当前时刻(20处),然后清除R位。然后从B页面开始继续搜索合适的页面。
    • 寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过,该算法就会 被简化为单纯的FIFO算法
    • 具体来说,假设图a中所有页面都设置了 R位。操作系统将页面依次 移到链表末尾,每次都在添加到末尾时清除R位
    • 最后,算法又会回到页面A,此时的R位已经被清 除,那么页面A就会被执行出链处理,因此算法能够正常结束。

    5.时钟页面置换算法

    • 即使上面提到的第二次页面置换算法也是一种比较合理的算法,但它经常要在链表中移动页面,既降低 了效率,而且这种算法也不是必须的。
    • 一种比较好的方式是把所有的页面都保存在一个类似钟面的环形 链表中,一个表针指向最老的页面。

    如下图所示:
    在这里插入图片描述

    • 当缺页错误出现时,算法首先检查表针指向的页面,如果它的R位是。就淘汰该页面,并把新的页面插入到这个位置,然后把表针向前移动一位;如果R位是1就清除R位并把表针前移一个位置。重复这个过程直到找到了一个R位为0的页面位置。

    了解这个算法的工作方式,就明白为什么它被称为 时 钟(clokc)算法了。

    6.最近最少使用页面置换算法(LRU)

    • 最近最少使用页面置换算法的一个解释会是下面这样:在前面几条指令中频繁使用的页面和可能在后面 的几条指令中被使用
    • 反过来说,已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这 个思想揭示了一个可以实现的算法:在缺页中断时,置换未使用时间最长的页面。这个策略称为 LRU(Least Recently Used),最近最少使用页面置换算法
    • 虽然LRU在理论上是可以实现的,但是从长远看来代价比较高。为了完全实现LRU,会在内存中维护 —个所有页面的链表,最频繁使用的贞位于表头,最近最少使用的贞位于表尾
    • 困难的是在每次内存引 用时更新整个链表。在链表中找到一个页面,删除它,然后把它移动到表头是一个非常耗时的操作,即 使使用硬件来实现也是一样的费时
    • 然而,还有其他方法可以通过硬件实现LRU。让我们首先考虑最简单的方式。这个方法要求硬件有一个 64位的计数器,它在每条指令执行完成后自动加1,每个页表必须有一个足够容纳这个计数器值的域
    • 每次访问内存后,将当前的值保存到被访问页面的页表项中。一旦发生缺页异常,操作系统就检查所 有页表项中计数器的值,找到值最小的一个页面,这个页面就是最少使用的页面。

    7.用软件模拟LRU

    • 尽管上面的LRU算法在原则上是可以实现的,但是很少有机器能够拥有那些特殊的硬件。
    • 上面是硬件 的实现方式,那么现在考虑要用软件来实现LRU。一种可以实现的方案是NFU(Not Frequently Used,最不常用)算法
    • 需要一个软件计数器来和每个页面关联,初始化的时候是0。在每个时钟中 断时,操作系统会浏览内存中的所有页,会将每个页面的R位(0或1)加到它的计数器上
    • 这个计数 器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时,则置换计数器值最小的页面
    • NFU最主要的问题是它不会忘记任何东西,想一下是不是这样?例如,在一个多次(扫描)的编译器 中,在第一遍扫描中频繁使用的页面会在后续的扫描中也有较高的计数。
    • 事实上,如果第一次扫描的执 行时间恰好是各次扫描中最长的,那么后续遍历的页面的统计次数总会比第一次页面的统计次数小。 结果是操作系统将置换有用的页面而不是不再使用的页面
    • 幸运的是只需要对NFU做一个简单的修改就可以让它模拟LRU,这个修改有两个步骤:
    • •首先,在R位被添加进来之前先把计数器右移一位
    • 第二步,R位被添加到最左边的位而不是最右边的位

    修改以后的算法称为老化Caging)算法,下图解释了老化算法是如何工作的:
    在这里插入图片描述

    • 我们假设在第一个时钟周期内页面0-5的R位依次是1, 0, 1, 0, 1, 1,(也就是页面0是1,页 面1是0,页面2是1这样类推)。
    • 也就是说,在0个时钟周期到1个时钟周期之间,0, 2, 4, 5 都被引用了,从而把它们的R位设置为1,剩下的设置为0。
    • 在相关的六个计数器被右移之后R位被 添加到 左侧,就像上图中的a。剩下的四列显示了接下来的四个时钟周期内的六个计数器变化。
    • CPU正在以某个频率前进,该频率的周期称为时钟滴答或时钟周期
    • 一个10OMhz的处理器每 秒将接收100,000,000个时钟滴答。
    • 当缺页异常出现时,将置换(就是移除)计数器值最小的页面。如果一个页面在前面4个时钟周期内 都没有被访问过,那么它的计数器应该会有四个连续的0,因此它的值肯定要比前面3个时钟周期内 都没有被访问过的页面的计数器小。

    这个算法与LRU算法有两个重要的区别:看一下上图中的e ,第三列和第五列
    在这里插入图片描述

    • 它们在两个时钟周期内都没有被访问过,在此之前的时钟周期内都引用了两个页面。
    • 根据LRU算法, 如果需要置换的话,那么应该在这两个页面中选择一个。那么问题来了,我萌应该选择哪个?
    • 现在的问 题是我们不知道时钟周期1到时钟周期2内它们中哪个页面是后被访问到的。因为在每个时钟周期内 只记录了一位,所以无法区分在一个时钟周期内哪个页面最早被引用,哪个页面是最后被引用的。
    • 因 此,我们能做的就是置换页面3 ,因为页面3在周期0-1内都没有被访问过,而页面5却被引用 过。
    • LRU与老化之前的第2个区别是,在老化期间,计数器具有有限数量的位(这个例子中是8位),这 就限制了以往的访问记录。
    • 如果两个页面的计数器都是0,那么我们可以随便选择一个进行置换。实际 上,有可能其中一个页面的访问次数实在9个时钟周期以前,而另外一个页面是在1000个时钟周期之 前,但是我们却无法看到这些。
    • 在实际过程中,如果时钟周期是20 ms, 8位一般是够用的。所以我们 经常拿20 ms来举例。

    8.工作集页面置换算法

    • 在最单纯的分页系统中,刚启动进程时,在内存中并没有页面。此时如果CPU尝试匹配第一条指令,就会得到一个缺贞异常,使操作系统装入含有第一条指令的页面
    • 其他的错误比如全局变量和堆栈 引起的缺贞异常通常会紧接着发生。一段时间以后,进程需要的大部分页面都在内存中了,此时进程开 始在较少的缺页异常环境中运行。这个策略称为请求调页(demand paging),因为页面是根据需要被 调入的,而不是预先调入的。
    • 一个大的地址空间中系统的读所有的页面,将会造成很多缺贞异常,因此会导致没有足够的内存来容 纳这些页面
    • 不过幸运的是,大部分进程不是这样工作的,它们都会以局部性方式(locality of reference)来访问,这意味着在执行的任何阶段,程序只引用其中的一小部分
    • 一个进程当前正在使用的页面的集合称为它的 工作集(working set),如果整个工作集都在内存中, 那么进程在运行到下一运行阶段(例如,编译器的下一遍扫面)之前,不会产生很多缺贞中断
    • 如果内 存太小从而无法容纳整个工作集,那么进程的运行过程中会产生大量的缺页中断,会导致运行速度也会 变得缓慢
    • 因为通常只需要几纳秒就能执行一条指令,而通常需要十毫秒才能从磁盘上读入一个页面。 如果一个程序每10 ms只能执行一到两条指令,那么它将需要很长时间才能运行完。如果只是执行几条指令就会产生中断,那么就称作这个程序产生了颠簸(thrashing)。
    • 在多道程序的系统中,通常会把进程移到磁盘上(即从内存中移走所有的页面),这样可以让其他进程 有机会占用CPU
    • 有一个问题是,当进程想要再次把之前调回磁盘的页面调回内存怎么办?从技术的 角度上来讲,并不需要做什么,此进程会一直产生缺页中断直到它的工作集 被调回内存。
    • 然后,每次 装入一个进程需要20、100甚至1000次缺页中断,速度显然太慢了,并且由于CPU需要几毫秒时间 处理一个缺页中断,因此由相当多的CPU时间也被浪费了。
    • 因此,不少分页系统中都会设法跟踪进程的工作集,确保这些工作集在进程运行时被调入内存。这个方 法叫做工作集模式(working set model)
    • 它被设计用来减少缺页中断的次数的。在进程运行前首 先装入工作集页面的这一个过程被称为 预先调页(prepaging),工作集是随着时间来变化的
    • 根据研究表明,大多数程序并不是均匀的访问地址空间的,而访问往往是集中于一小部分页面。一次内 存访问可能会取出一条指令,也可能会取出数据,或者是存储数据
    • 在任一时刻t,都存在一个集合, 它包含所哟欧最近k次内存访问所访问过的页面。这个集合w(k,t)就是工作集。因为最近k=1次 访问肯定会访问最近k>1次访问所访问过的页面,所以w(k,t)是k的单调递减函数。
    • 随着k的增 大,w(k,t)是不会无限变大的,因为程序不可能访问比所能容纳页面数量上限还多的页面。
      在这里插入图片描述
    • 事实上大多数应用程序只会任意访问一小部分页面集合,但是这个集合会随着时间而缓慢变化,所以为 什么一开始曲线会快速上升而k较大时上升缓慢
    • 为了实现工作集模型,操作系统必须跟踪哪些页面在 工作集中。一个进程从它开始执行到当前所实际使用的CPU时间总数通常称作当前实际运行时间
    • 进程的工作集可以被称为在过去的t秒实际运行时间中它所访问过的页面集合。
    • 下面来简单描述一下工作集的页面置换算法,基本思路就是找出一个不在工作集中的页面并淘汰它

    下 面是一部分机器页表:
    在这里插入图片描述

    • 因为只有那些在内存中的页面才可以作为候选者被淘汰,所以该算法忽略了那些不在内存中的页面。
    • 每 个表项至少包含两条信息:上次使用该页面的近似时间和R (访问)位。空白的矩形表示该算法不需要其他字段,例如页框数量、保护位、修改位。
    • 算法的工作流程如下:
    • 假设硬件要设置R和M位。同样的,在每个时钟周期内,一个周期性的时钟中 断会使软件清除Referenced(引用)位。在每个缺贞异常,页表会被扫描以找出一个合适的页面把它 置换
    • 随着每个页表项的处理,都需要检查R位。如果R位是1,那么就会将当前时间写入页表项的 上次使 用时间域,表示的意思就是缺贞异常发生时页面正在被使用。因为页面在当前时钟周期内被访问过,那 么它应该出现在工作集中而不是被删除(假设t是横跨了多个时钟周期)。
    • 如果R位是0,那么在当前的时钟周期内这个页面没有被访问过,应该作为被删除的对象。为了查看 是否应该将其删除,会计算其使用期限(当前虚拟时间-上次使用时间),来用这个时间和t进行对 比。如果使用期限大于t,那么这个页面就不再工作集中,而使用新的页面来替换它。然后继续扫描更 新剩下的表项
    • 然而,如果R位是0但是使用期限小于等于t,那么此页应该在工作集中。此时就会把页面临时保存起 来,但是会记生存时间最长(即上次使用时间的最小值)的页面。
    • 如果扫描完整个页表却没有找到适合 被置换的页面,也就意味着所有的页面都在工作集中。在这种情况下,如果找到了一个或者多个R = 0 的页面,就淘汰生存时间最长的页面。
    • 最坏的情况下是,在当前时钟周期内,所有的页面都被访问过了(也就是都有R = 1),因此就随机选择一个页面淘汰,如果有的话最好选一个未被访问的页面,也就 是干净的页面

    9.工作集时钟页面置换算法

    • 缺页异常发生后,需要扫描整个页表才能确定被淘汰的页面,因此基本工作集算法还是比较浪费时间 的。
    • 一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息,这种算法称为 WSClock(工作集时钟)。由于它的实现简单并且具有高性能,因此在实践中被广泛应用。

    与时钟算法一样,所需的数据结构是一个以页框为元素的循环列表,就像下面这样:
    在这里插入图片描述

    • 工作集时钟页面置换算法的操作:a)和b)给出R = 1时所发生的情形;c)和d)给出R = 0的例子
    • 最初的时候,该表是空的。当装入第一个页面后,把它加载到该表中。随着更多的页面的加入,它们形 成一个环形结构。每个表项包含来自基本工作集算法的上次使用时间,以及R位(已标明)和M位 (未标明)。
    • 与时钟算法一样,在每个缺页异常时,首先检查指针指向的页面。如果R位被是设置为1,该页面在当 前时钟周期内就被使用过,那么该页面就不适合被淘汰
    • 然后把该页面的R位置为0,指针指向下一个 页面,并重复该算法。该事件序列化后的状态参见图b。
    • 现在考虑指针指向的页面R = 0时会发生什么,参见图c,如果页面的使用期限大于t并且页面为被访 问过,那么这个页面就不会在工作集中,并且在磁盘上会有一个此页面的副本
    • 申请重新调入一个新的 页面,并把新的页面放在其中,如图d所示。另一方面,如果页面被修改过,就不能重新申请页面,因 为这个页面在磁盘上没有有效的副本
    • 为了避免由于调度写磁盘操作引起的进程切换,指针继续向前 走,算法继续对下一个页面进行操作。毕竟,有可能存在一个老的,没有被修改过的页面可以立即使 用
    • 原则上来说,所有的页面都有可能因为磁盘I/O在某个时钟周期内被调度。为了降低磁盘阻塞,需要 设置一个限制,即最大只允许写回n个页面。一旦达到该限制,就不允许调度新的写操作。
    • 那么就有个问题,指针会绕一圈回到原点的,如果回到原点,它的起始点会发生什么?这里有两种情 况:
      •👏至少调度了一次写操作
      •👏没有调度过写操作
    • 在第一种情况中,指针仅仅是不停的移动,寻找一个未被修改过的页面。由于已经调度了一个或者多个 写操作,最终会有某个写操作完成,它的页面会被标记为未修改
    • 置换遇到的第一个未被修改过的页 面,这个页面不一定是第一个被调度写操作的页面,因为硬盘驱动程序为了优化性能可能会把写操作重 排序
    • 对于第二种情况,所有的页面都在工作集中,否则将至少调度了一个写操作。由于缺乏额外的信息,最 简单的方法就是置换一个未被修改的页面来使用,扫描中需要记录未被修改的页面的位置,如果不存在 未被修改的页面,就选定当前页面并把它写回磁盘。

    10.页面置换算法小结

    我们到现在已经研究了各种页面置换算法,现在我们来一个简单的总结,算法的总结归纳如下:
    在这里插入图片描述

    • 最优算法在当前页面中置换最后要访问的页面。不幸的是,没有办法来判定哪个页面是最后一个要访问的,因此实际上该算法不能使用。然而,它可以作为衡量其他算法的标准。
    • NRU算法根据R位和M位的状态将页面分为四类。从编号最小的类别中随机选择一个页面。 NRU算法易于实现,但是性能不是很好。存在更好的算法。
    • FIFO会跟踪页面加载进入内存中的顺序,并把页面放入一个链表中。有可能删除存在时间最长 但是还在使用的页面,因此这个算法也不是一个很好的选择。
    • 第二次机会算法是对FIFO的一个修改,它会在删除页面之前检查这个页面是否仍在使用。如果 页面正在使用,就会进行保留。这个改进大大提高了性能。
    • 时钟算法是第二次机会算法的另外一种实现形式,时钟算法和第二次算法的性能差不多,但是会 花费更少的时间来执行算法
    • LRU算法是一个非常优秀的算法,但是没有特殊的硬件(TLB)很难实现。如果没有硬件,就不能使用LRU算法。
    • NFU算法是一种近似于LRU的算法,它的性能不是非常好
    • 老化算法是一种更接近LRU算法的实现,并且可以更好的实现,因此是一个很好的选择
    • •最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销,但是它的实现比较复杂。WSClock是另外一种变体,它不仅能够提供良好的性能,而且可以高效地实现

    总之,最好的算法是老化算法和WSClock算法。他们分别是基于LRU和工作集算法。

    他们都具有良好 的性能并且能够被有效的实现。还存在其他一些好的算法,但实际上这两个可能是最重要的

    展开全文
  • 等价关系在网络分析、图论、模式识别和数据库技术等方面都有许多应用,而任意等价关系矩阵都置换合同于块1-对角矩阵标准形,从置换运算的角度分析置换合同的几条性质,提出基于图的深度优先搜索策略的置换矩阵构造...
  • 模式方法模式是类的行为模式,准备一个抽象类,将部分逻辑以具体方法...在定义新的子类的时候,应当考虑哪些操作是必须置换掉的,哪些操作是可以置换掉的,以及哪些操作是不可以置换掉的,使用模板方法模式可以使...
  • 访问者模式是一种将数据操作与数据结构分离的设计模式,它可以算是 23 中设计模式中最复杂的一个,但它的使用频率并不是很高,大多数情况下,你并不需要使用访问者模式,但是当你一旦需要使用它时,那你就是需要使用...
  • 模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的形式... 模板方法模式是所有模式中最为常见的几个模式之一,是基于继承的代码复用的基本技术。  模板方法模式需要开发抽象
  • 在阎宏博士的《JAVA与模式》一书中开头是这样描述模板方法(Template Method)模式的:  模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的形式实现,然后声明一些抽象方法...
  • 设计模式----模板方法模式

    千次阅读 2018-07-31 11:44:33
    一个抽象类中,有一个主方法,再定义1…n个方法,可以是抽象的,也可以是实际的方法(将部分逻辑以具体方法以及具体构造函数的形式实现,然后声明一些抽象方法来迫使...模板模式的关键是:子类可以置换掉父类的可...
  • 《JAVA与模式》之模板方法模式 在阎宏博士的《JAVA与模式》一书中开头是这样描述模板方法(Template Method)模式的:  模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的...
  • 快速梳理23种常用的设计模式

    千次阅读 2018-11-17 22:54:34
    本文旨在快速梳理常用的设计模式,了解每个模式主要针对的是哪些情况以及其基础特征,每个模式前都有列举出一个或多个可以深入阅读的参考网页,以供读者详细了解其实现。 快速回忆 一、创建型 单例(Singleton...
  • 模板方法模式是所有模式中最为常见的几个模式之一,是基于继承的代码复用的基本技术。 模板方法模式需要开发抽象类和具体子类的设计师之间的协作。一个设计师负责给出一个算法的轮廓和骨架,另一些设计师则负责给出...
  • 本篇文章介绍一种设计模式——外观模式。本篇文章内容参考:《JAVA与模式》之模板方法模式,模板方法模式深度解析(三)。 一、模版方法模式的定义模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法...
  • Java设计模式之模板方法模式
  • 设计模式大总结(一)

    千次阅读 热门讨论 2014-06-20 15:39:54
    本节将对设计模式的23种模式进行详细的讲解。设计模式就是遵循六大基本原则的,分为三个类别模式,尽管每一个设计模式可能只遵循六大基本原则中的几个,但运用正确我们就会变得不简单。而六大基本原则又是基于面向...
  • 在阎宏博士的《JAVA与模式》一书中开头是这样描述模板方法(Template Method)模式的:  模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的形式实现,然后声明一些抽象方法来...
  • 在阎宏博士的《JAVA与模式》一书中开头是这样描述模板方法(Template Method)模式的:  模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的形式实现,然后声明一些抽象方法...
  • 在阎宏博士的《JAVA与模式》一书中开头是这样描述模板方法(Template Method)模式的:  模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及具体构造函数的形式实现,然后声明一些抽象方法来...
  • 【设计模式】之六大原则(二)

    千次阅读 2015-09-30 22:32:24
     【设计模式】之六大原则(二) 目录 四、Barbara Liskov Priciple (里氏代换原则)   1、问题由来   2、定义   3、理解 五、迪米特原则   1、定义   2、问题由来 ...
  • 【设计模式】设计模式之结构型模式(适配器、桥接、组合、装饰、外观、享元、代理)1、设计模式1.1 设计模式介绍1.2 分类2、结构型模式2.1 概述2.2 七大结构型设计模式2.2.1 适配器模式 1、设计模式 1.1 设计模式...
  • 模板方法模式

    2015-06-30 09:43:31
    模板方法模式是类的行为模式。准备一个抽象类,将部分逻辑以具体方法以及... 模板方法模式是所有模式中最为常见的几个模式之一,是基于继承的代码复用的基本技术。  模板方法模式需要开发抽象类和具体子类的设...
  • 适配器模式

    2016-04-03 14:19:55
    适配器模式 UML类图  1、接口继承与实现继承 在Adapter模式的两种模式中,有一个很重要的概念就是接口继承和实现继承的区别和联系。接口继承和实现继承是面向对象领域的两个重要的概念,接口继承指的是通过...
  • 虽然很想往技术美工方向发展了。因为是学程序出身,眼下能做的也就是写写Shaders。等到手上的项目做完,会公开始用的实时光照模型……不过那是后话了。现在只是想配合一下这两天大家讨论的热火朝天的Normal Map,在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,803
精华内容 4,721
关键字:

技术置换模式