学习啦>学习电脑>操作系统>操作系统基础知识>

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

加城分享

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

  操作系统淘汰算法详解

  操作系统淘汰算法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。

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

    3974692