进程调度算法

/ 0评 / 2

一、进程调度算法的评价指标

  1. cpu利用率:

    利用率=cpu忙碌时间/总时间

  2. 系统吞吐量:

    系统吞吐量=总共完成了多少道作业/总共花费的时间

  3. 周转时间:

    1. 周转时间: 周转时间=作业完成时间-作业提交时间
    2. 平均周转时间: 平均周转时间=各作业周转时间之和/作业数量
    3. 带权周转时间: 带权周转时间=作业周转时间/作业实际运行的时间
    4. 平均带权周转时间: 平均带权周转时间=各作业带权周转时间之和/作业数量
  4. 等待时间:

    进程/作业 等待被服务的时间之和

    平均等待时间即各个 进程/作业 等待时间的平均值

  5. 响应时间:

    从用户提交请求到首次产生响应所用的时间


二、调度算法(早期批处理系统)

Tips:各种调度算法的学习思路

1. 先来先服务(FCFS)

image-20200325150609731

2. 短作业优先(SJF)

  1. 短作业/进程优先调度算法:每次调度时选择当前已到达运行时间最短的作业/进程。

  2. 最短剩余时间优先算法:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行时间的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度

    image-20200325152858734

3. 高响应比优先

响应比: 响应比=(等待时间+要求服务时间)/要求服务时间

高响应比优先算法规则:在每次调度时先计算各个作业/进程的相应比,选择相应比最高的作业/进程为其服务

image-20200325154733465


知识回顾

image-20200325154848100


三、调度算法(交互式系统)

1. 时间片轮转调度算法(RR)——常用于分时操作系统

算法规则:按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。

如果时间片太大,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法退化为先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大

如果时间片太小,进程调度、切换是有时间代价的(保存、恢复运行环境),因此如果时间片太小,会导致进程切换过于频繁,系统会花大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减小。

image-20200325163257508

2. 优先级调度算法

算法规则:每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程

抢占式的优先级调度算法:每次调度时选择当前已到达优先级最高的进程。当前进程主动放弃处理机时发生调度。另外,当就绪队列发生改变时也需要检查是否会发生抢占。

非抢占的优先级调度算法:每次调度时选择当前已到达优先级最高的进程。仅在当前进程主动放弃处理机时发生调度。

优先级调度算法的补充:

image-20200325171035937

3. 多级反馈队列调度算法

算法规则:

  1. 设置多级就绪队列,各级队列优先级从高到低,时间片从小到大

  2. 新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经是在最下级的队列,则重新放回该队列队尾。

  3. 只有第K级队列为空时,才会为K+1级队头分配时间片。

    抢占式的算法:在K级队列的进程运行过程中,若上级的队列(1~K-1级)中进入了一个新进程,则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回K级队列队尾。

    image-20200325173853530


知识回顾

image-20200325174051062


发表评论

电子邮件地址不会被公开。 必填项已用*标注