操作系统笔记

概念

静止就绪:这个也叫做挂起就绪,是指进程被对换到辅存时的就绪状态,是不能被直接调度的状态,只有当主存中没有活跃就绪态进程,或者是挂起就绪态进程具有更高的优先级,系统将把挂起就绪态进程调回主存并转换为活跃就绪。
活动就绪:进程在主存并且可被调度的状态。
静止睡眠(阻塞):是指进程对换到辅存时的阻塞状态,一旦等待的事件产生便进入静止就绪状态。
活动睡眠(阻塞):是指进程已在主存,一旦等待的事件产生便进入活跃就绪状态。

  • 正在执行的进程由于其时间片用完被暂停执行,此时进程应从执行状态变为活动就绪状态
  • 处于静止睡眠状态的进程,在进程等待的事件出现后,应变为静止就绪状态
  • 若进程正处于执行状态时,因终端的请求而暂停下来以便研究其运行情况,这时进程应转变为静止就绪状态
  • 若进程已处于睡眠状态,则此时应转变为静止睡眠状态

常见的页面调度算法

(1) 随机算法rand (Random Algorithm)

利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单,而且容易实现。但是,这种算法完全没用利用主存储器中页面调度情况的历史信息,也没有反映程序的局部性,所以命中率较低。

(2) 先进先出调度算法(FIFO)

先进先出调度算法根据页面进入内存的时间先后选择淘汰页面,本算法实现时需要将页面按进入内存的时间先后组成一个队列,每次调度队首页面予以淘汰。它的优点是比较容易实现,能够利用主存储器中页面调度情况的历史信息,但是,它没有反映程序的局部性,因为最先调入主存的页面,很可能也是经常要使用的页面。

(3) 最近最少调度算法LFU(Least Frequently Used Algorithm )

先进先出调度算法没有考虑页面的使用情况,大多数情况下性能不佳。根据程序执行的局部性特点,程序一旦访问了某些代码和数据,则在一段时间内会经常访问他们,因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用,总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。

(4) 最近最不常用调度算法LRU(Least Recently Used Algorithm)

由于程序设计中经常使用循环结构,根据程序执行的局部性特点,可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问,显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面,每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器,记录访问次数。计数器由硬件或操作系统自动定时清零。

(5)最优替换算法OPT(Optimal replacement Algorithm)

前面介绍的几种页面调度算法主要是以主存储器中页面调度情况的历史信息为依据的,他假设将来主存储器中的页面调度情况与过去一段时间时间内主存储器中的页面调度情况是相同的。显然,这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面,这种算法的命中率一定是最高的,它就是最有替换算法。要实现OPT算法,唯一的方法就是让程序先执行一遍,记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然,这样做是不现实的。因此,OPT算法只是一种理想化的算法,然而,它也是一种很有用的算法。实际上,经常把这种算法用来作为评价其它页面调度算法好坏的标准。在其它条件相同的情况下,哪一种页面调度算法的命中率与OPT算法最接近,那么,它就是一种比较好的页面替换算法。

(6)时钟置换算法(CLOCK)

时钟置换算法也称为最近未使用算法,时LRU和FIFO的折中.CLOCK维护一个内存所有页面的循环链表,当程序需要访问链表存在的页面时,该页面的访问位置为1.否则一个指针就从上次被淘汰页面的下一个位置开始顺序地遍历这个循环链表.当指针指向的页面访问位为1时,则置为0.否则如果是0则淘汰该页面.

0%