408571: GYM103192 B 页面置换
Description
在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
通俗的理解:现代计算机常采用页式存储,也就是把各种内容切分成固定大小的块进行存储。操作系统在使用某个页面的内容时,只能从内存中读取内容,所以当要使用某个页面时,如果其不在内存中,就需要将其先从外存调入内存中,但是显然内存的大小是有限的,当新的页面将要进入内存时,如果内存已满,就需要淘汰掉现有的页面,所以需要一些策略来对页面进行调度,这种策略就被叫做页面调度算法。
缺页中断:当调用某页面时,若其不在内存中,就发生缺页中断。
下面给出三种调度算法
1.FIFO调度算法 当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。
2.LRU调度算法 当需要淘汰一个页面时,总是选择在最近一段时间内最久不用的页面予以淘汰。 即淘汰最近最长时间未访问过的页面。
3.OPT调度算法 当需要淘汰一个页面时,从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。
zyw想知道这三种调度算法的优劣,他会以缺页次数为指标,所以请你告诉他哪一种方法缺页中断次数最少,并且告诉他会发生多少次缺页中断。(假定一开始内存中没有任何页面)
Input第一行给定三个整数n, m, k,分别表示页面请求次数,外存中页面个数(从1开始编号),内存的大小。其中n ≤ 105, m ≤ 103, k ≤ 100。
第二行给出n个1到m之间的整数,表示页面调用请求的顺序。
Output第一行输出最优的方法,如果有两种或更多方法是最优的,输出任意一种都可以。
第二行输出缺页中断的次数。
ExampleInput12 8 4 6 2 4 1 4 6 3 8 4 5 7 3Output
FIFO 8