408571: GYM103192 B 页面置换

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. 页面置换time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

通俗的理解:现代计算机常采用页式存储,也就是把各种内容切分成固定大小的块进行存储。操作系统在使用某个页面的内容时,只能从内存中读取内容,所以当要使用某个页面时,如果其不在内存中,就需要将其先从外存调入内存中,但是显然内存的大小是有限的,当新的页面将要进入内存时,如果内存已满,就需要淘汰掉现有的页面,所以需要一些策略来对页面进行调度,这种策略就被叫做页面调度算法。

缺页中断:当调用某页面时,若其不在内存中,就发生缺页中断。

下面给出三种调度算法

1.FIFO调度算法 当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。

2.LRU调度算法 当需要淘汰一个页面时,总是选择在最近一段时间内最久不用的页面予以淘汰。 即淘汰最近最长时间未访问过的页面。

3.OPT调度算法 当需要淘汰一个页面时,从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。

zyw想知道这三种调度算法的优劣,他会以缺页次数为指标,所以请你告诉他哪一种方法缺页中断次数最少,并且告诉他会发生多少次缺页中断。(假定一开始内存中没有任何页面)

Input

第一行给定三个整数n, m, k,分别表示页面请求次数,外存中页面个数(从1开始编号),内存的大小。其中n ≤ 105, m ≤ 103, k ≤ 100

第二行给出n1m之间的整数,表示页面调用请求的顺序。

Output

第一行输出最优的方法,如果有两种或更多方法是最优的,输出任意一种都可以。

第二行输出缺页中断的次数。

ExampleInput
12 8 4
6 2 4 1 4 6 3 8 4 5 7 3
Output
FIFO
8

加入题单

上一题 下一题 算法标签: