几种操作系统调度算法.doc

文档介绍：保证调度算法基本思想:向用户做出明确的性能保证,,则你将获得cpu处理能力的1/n算法实现:跟踪计算各个进程已经使用的cpu时间和应该获得的cpu时间,调度将转向两者之比最低的进程五,保证调度算法思想:向用户做出明确的性能保证,:容易实现的一种保证是:当工作时己有n个用户登录在系统,则将获得CPU处理能力的1/,如果在一个有n个进程运行的用户系统中,每个进程将获得CPU处理能力的1/:OS应记录及计算,各个进程在一定时间段内,已经使用的CPU时间和应该得到的CPU时间,,然后去实现它。一种很实际并很容易实现的保证是:若用户工作时有n个用户登录,则用户将获得CPU处理能力的1/n。类似地,在一个有n个进程运行的单用户系统中,若所有的进程都等价,则每个进程将获得1/n的CPU时间。看上去足够公平了。为了实现所做的保证,系统必须跟踪各个进程自创建以来已使用了多少CPU时间。然后它计算各个进程应获得的CPU时间,即自创建以来的时间除以n。由于各个进程实际获得的CPU时间是已知的,所以很容易计算出真正获得的CPU时间和应获得的CPU时间之比。,。于是该算法随后转向比率最低的进程,直到该进程的比率超过它的最接近竞争者为止。彩票调度算法基本思想:为进程发放针对系统各种资源(如cpu时间)的彩票;当调度程序需要做出决策时,随机选择一张彩票,持有该彩票的进程将获得系统资源合作进程之间的彩票交换六,彩票调度算法彩票调度算法:为进程发放针对各种资源(如CPU时间),:平等且体现优先级:进程都是平等的,,可被给予更多彩票,:某进程占用CPU的几率,,,10帧/s,15帧/s,25帧/,然后兑现之,这是个好想法,不过很难实现。但是,有一个既可给出类似预测结果而又有非常简单的实现方法的算法,这个算法称为彩票调度(lotteryscheduling)(Waldspurger和Weihl,1994)。其基本思想是向进程提供各种系统资源(如CPU时间)的彩票。一旦需要做出一项调度决策时,就随机抽出一张彩票,拥有该彩票的进程获得该资源。在应用到CPU调度时,系统可以掌握每秒钟50次的一种彩票,作为奖励每个获奖者可以得到20ms的CPU时间。eOrwell关于“所有进程是平等的,但是某些进程更平等一些”的含义,可以给更重要的进程额外的彩票,以便增加它们获胜的机会。如果出售了100张彩票,而有一个进程持有其中的20张,那么在每一次抽奖中该进程就有20%的取胜机会。在较长的运行中,该进程会得到20%的CPU。相反,对于优先级调度程序,很难说明拥有优先级40究竟是什么意思,而这里的规则很清楚:拥有彩票f份额的进程大约得到系统资源的f份