存储管理的页面置换算法
存储管理的页面置换算法在考试中常常会考到,操作系统教材中主要介绍了 3 种常用的页面
置换算法,分别是:先进先出法(FIFO)、最佳置换法(OPT)和最近最少使用置换法(LRU)。
大家要理解 3 种置换算法的含义,然后能熟练地运用在具体的练习中就可以了。
为什么要进行页面置换
在请求分页存储管理系统中,由于使用了虚拟存储管理技术,使得所有的进程页面不是一次
性地全部调入内存,而是部分页面装入。
这就有可能出现下面的情况:要访问的页面不在内存,这时系统产生缺页中断。操作系统在
处理缺页中断时,要把所需页面从外存调入到内存中。如果这时内存中有空闲块,就可以直
接调入该页面;如果这时内存中没有空闲块,就必须先淘汰一个已经在内存中的页面,腾出
空间,再把所需的页面装入,即进行页面置换。
有助于理解的关键词有:请求分页、虚拟存储、缺页中断、页面置换。
先进先出法(FIFO)
算法描述:由于认为最早调入内存的页不再被使用的可能性要大于刚调入内存的页,因此,
先进先出法总是淘汰在内存中停留时间最长的一页,即先进入内存的页,先被换出。先进先
出法把一个进程所有在内存中的页按进入内存的次序排队,淘汰页面总是在队首进行。如果
一个页面刚被放入内存,就把它插在队尾。
【例 1】教材第 4 章课后习题。
考虑下述页面走向:1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6。
当内存块数量分别为 3,5 时,试问先进先出置换算法(FIFO)的缺页次数是多少?(注意,
所有内存块最初都是空的,凡第一次用到的页面都产生一次缺页。)
解:当内存块数量分别为 3 时,FIFO 算法的执行过程如下图所示。