操作系统淘汰算法有哪几种

　　操作系统中控制内存进出主要有三种淘汰算法，那么他们各自特点是什么呢。下面由学习啦小编为大家整理了操作系统淘汰算法的相关知识，希望对大家有帮助!

　　操作系统淘汰算法详解

　　操作系统淘汰算法1，FIFO(先进先出算法)

　　顾名思义，最先被置换进内存的页面最先出来，公正公平，大家都别抢，但是不一定合理，能者要多劳啊。

　　最先进去的页面，比如一些初始化性质的页面，通常在整个程序运行期间都是需要，被置换出去非常不合理。

　　操作系统淘汰算法2，NRU(Not Recently Used，最近未使用算法，又称CLK算法)

　　a. 给每一帧关联一个附加位，称为使用位

　　b. 当某一页首次装入主存时，该帧的使用位设置为1

　　c. 当该页随后再被访问到时，它的使用位也被置为1

　　d. 对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联

　　e. 当某一页被替换时，该指针被设置成指向缓冲区中的下一帧

　　f. 当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0

　　g. 如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换

　　h. 如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页

　　操作系统淘汰算法3，LRU(Least Recently Used，最少最近使用算法)

　　计时法:给页表中的每一页增加一个域，专门用来存放计时标志，用来记录该页面自上次被访问以来所经历的时间。页面每被访问一次，计时清0。要装入新页时，从内存的页面中选出时间最长的一页，调出，同时把各页的计时标志全部清0，重新开始计时。 计时法可以稍作改变，成为计数法：页面被访问，计数标志清0，其余所有内存页面计数器加1;要装入新页时，选出计数最大的一页调出，同时所有计数器清0。

　　链表法:操作系统为每个进程维护一条链表，链表的每个结点记录一张页面的地址。调用一次页面，则把该页面的结点从链中取出，放到链尾;要装入新页，则把链头的页面调出，同时生成调入页面的结点，放到链尾。链表法可看作简单计时/计数法的改良，维护一个链表，自然要比维护所有页面标志要简单和轻松。可是，这并没有在数量级上改变算法的时间复杂度，每调用一个页面，都要在链表中搜寻对应结点并放至链尾的工作量并不算小。