操作系统之调度算法

2023-01-28 22:49:06

调度算法的评价指标

  • cpu利用率

cpu利用率=cpu有效工作时间 / (cpu有效工作时间+cpu空闲时间)

  • 系统吞吐量：单位时间内完成作业的数量

系统吞吐量=总共完成作业数 / 总共耗费时间

  • 周转时间：从作业被提交到作业完成为止的时间间隔

周转时间 = 作业完成时间 - 作业提交时间

  • 带权周转时间

带权周转时间 = 周转时间 / 作业实际运行时间

  • 平均周转时间

平均周转时间 = 各作业周转时间之和 / 作业数

  • 平均带权周转时间

平均带权周转时间 = 各作业带权周转时间之和 / 作业数

  • 等待时间：进程或者作业处于等待处理机状态时间之和
  • 只涉及计算，不涉及I/O操作：
    等待时间 = 周转时间 - 运行时间
  • 若涉及I/O操作，则：
    等待时间 = 周转时间 - 运行时间 - I/O操作时间
  • 响应时间：提出请求到首次收到回复的时间

补充

进程调度方式：
1.非剥夺调度方式也称为非抢占方式：只允许进程主动放弃处理机
2.剥夺调度方式也称为抢占方式：进程状态可以被动进入阻塞态

调度算法

一、不适合用于交互式系统
1.先来先服务(FCFS调度算法)

  • 算法：按照进程或者作业到达的先后顺序
  • 特征：非抢占式算法；适用于作业调度，也适用于进程调度
  • 优点：公平、算法实现简单
  • 缺点：排在长作业后面的短作业需要等待很长时间，带权周 转时间大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利

例题：用先来先服务调度算法求下表中各个进程的周转时间、带权周转时间、等待时间、平均周转时间、平均带权周转时间、平均等待时间操作系统之调度算法
调度顺序：P1->P2->P3->P4(按照到达的先后顺序)
操作系统之调度算法

  • 周转时间：
    (1) P1 = 7-0 = 7 (2) P2 = 11-2 = 9
    (3) P3 = 12-4 = 8 (4) P4 = 16-5 = 11
  • 带权周转时间：
    (1) P1= 7/7 = 1 (2) P2 = 9/4 = 2.25
    (3) P3 = 8/1 = 8 (4) P4 = 11/4 = 2.75
  • 等待时间：
    (1) P1= 7-7 = 0 (2) P2 = 9-4 = 5
    (3) P3 = 8-1 = 7 (4) P4 = 11-4 = 7
  • 平均周转时间 = (7+9+8+11) / 4 = 8.75
  • 平均带权周转时间 = (1+2.25+8+2.75) / 4 = 3.5
  • 平均等待时间 = (0+5+7+7) / 4 =4.75

2.短作业优先(SJF调度算法)

  • 算法：当前已经到达且最短的作业或者进程优先得到服务
  • 特征：非抢占式算法，也有抢占式算法【最短剩余时间优先算法(SRTN算法)】；适用于作业调度，也适用于进程调度
  • 优点：最短的平均等待时间、平均周转时间
  • 缺点：对短作业有利，对长作业不利，可能产生饥饿现象

例题：（1）用短作业优先非抢占式调度算法：求下表中各个进程的周转时间、带权周转时间、等待时间、平均周转时间、平均带权周转时间、平均等待时间
操作系统之调度算法
调度顺序：P1->P3->P2->P4

  • 0时刻：只有P1到达

  • 7时刻：P2、P3、P4均到达且P3运行时间最短，选择P3

  • 8时刻：P2比P4先到达，所以选择P2
    操作系统之调度算法

  • 周转时间：
    (1) P1 = 7-0 = 7 (2) P2 = 12-2 = 10
    (3) P3 = 8-4 = 4 (4) P4 = 16-5 = 11

  • 带权周转时间：
    (1) P1= 7/7 = 1 (2) P2 = 10/4 = 2.5
    (3) P3 = 4/1 = 4 (4) P4 = 11/4 = 2.75

  • 等待时间：
    (1) P1= 7-7 = 0 (2) P2 = 10-4 = 6
    (3) P3 = 4-1 = 3 (4) P4 = 11-4 = 7

  • 平均周转时间 = (7+4+10+11) / 4 = 8

  • 平均带权周转时间 = (1+2.5+4+2.75) / 4 = 2.56

  • 平均等待时间 = (0+6+3+7) / 4 =4

（2）用最短剩余时间优先算法：求下表中进程的调度顺序操作系统之调度算法
注：(1)每当有进程加入就绪队列，就需要进行进程调度
（2）Pi(n)：i代表第i个进程，n代表运行时间
调度顺序：

  • 0时刻：只有P1到达：P1(7)
  • 2时刻：P2加入就绪队列，此时P1(5)、P2(4)，选择P2
  • 4时刻：P3加入就绪队列，此时P1(5)、P2(2)、P3(1)，选择P3
  • 5时刻：P4加入就绪队列，此时P1(5)、P2(2)、P4(4),选择P2
  • 7时刻：P1(5)、P4(4)选择P4
    …
    P1->P2->P3->P2->P4->P1
    操作系统之调度算法

3.高响应比优先算法(HRRN)

  • 算法：每次调度时先计算各个作业或者进程的响应比，响应比最高的优先
  • 响应比 = （等待时间+要求服务时间）/ 要求服务时间
  • 特征：非抢占式算法；适用于作业调度，也适用于进程调度
  • 优缺点：
    1.综合考虑等待时间和运行时间。
    2.等待时间相同时，具有SJF调度算法的优点。
    3.要求服务时间相同时，具有FCFS调度算法的优点。
    4.对于长作业，随着等待时间越来越久，其响应比会越来越大

例题：用高响应比优先算法：求下表中进程的调度顺序
操作系统之调度算法
响应比求解：
0时刻：只有P1
7时刻：

  • P2等待时间 = 7-2 = 5，P2响应比 = （5+4）/ 4 = 2.25
  • P3等待时间 = 7-4 = 3，P3响应比 =（3+1）/ 1 = 4
  • P4等待时间 = 7-5 = 2，P4响应比 = （2+4）/ 4 = 1.5
    所以选择P3

8时刻：

  • P2等待时间 = 8-2 = 6，P2响应比 = （6+4）/ 4 = 2.5
  • P4等待时间 = 8-5 = 3，P4响应比 = （3+4）/ 4 = 1.75
    所以选择P2

12时刻：只有P4

调度顺序：P1->P3->P2->P4

操作系统之调度算法
二、适合用于交互式系统
1.时间片轮转调度算法(RR)

  • 算法：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排列
  • 特征：抢占式算法；仅适用于进程调度
  • 优点：公平、响应快，适用于分时操作系统
  • 缺点：高频率的进程切换导致有一定开销；不区分任务紧急程度
  • 时间片设置：
    1.时间片太大，会退化为FCFS算法，并且会增大进程响应时间
    2.时间片太小，会导致进程切换过于频繁，系统会花大量时间来处理进程切换，从而导致实际用于进程执行的实际比例减少。

例题：用时间片轮转调度算法：分析时间片大小为2时的进程运行情况
操作系统之调度算法
时间片大小为2：

  • 0时刻：只有P1,P1(5)
  • 2时刻：
    P2到达,插入就绪队列;P1未执行完,重新插入就绪队列队尾：P2(4)->P1(3)
  • 4时刻：
    P3到达，插入就绪队列，P2未执行完，重新插入就绪队列：P1(3)->P3(1)->P2(2)
  • 5时刻：
    P4到达，插入就绪队列：P1(2)->P3(1)->P2(2)->P4(6)
  • 6时刻：
    P1未执行完,重新插入就绪队列队尾：P3(1)->P2(2)->P4(6)->P1(1)
  • 7时刻：
    P3执行完，提前进程调度： P2(2)->P4(6)->P1(1)
  • 9时刻：
    P4(6)->P1(1)
    …
    调度顺序：P1->P2->P1->P3->P2->P4->P1->P4
    操作系统之调度算法

2.优先级调度算法

  • 算法：每个作业或者进程有各自的优先级数，优先级数高的优先
  • 特征：抢占式算法，也有非抢占式算法；适用于进程调度和作业调度,也可用于I/O调度
  • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统，比较灵活
  • 缺点：若源源不断地有高级优先进程到来，可能导致饥饿。

例题：（1）用优先级调度非抢占式算法：求下表中进程的调度顺序（一般情况，优先数越大，优先级越高）操作系统之调度算法
调度顺序：

  • 0时刻：只有P1
  • 7时刻：P2、P3、P4依次已到达，P3优先数高，选择P3
  • 8时刻：P2和P4优先数相同，P2先到达，选择P2
    …
    P1->P3->P2->P4
    操作系统之调度算法

（2）用优先级调度非抢占式算法：求下表中进程的调度顺序（一般情况，优先数越大，优先级越高）操作系统之调度算法
调度顺序：

  • 0时刻：只有P1到达，P1(7)
  • 2时刻：P2到达，调度切换，此时：P2(4)、P1(5)，但P2优先数高，所以选择P2
  • 4时刻：P3到达，调度切换，此时：P1(5)、P2(2)、P3(1),P3优先数高，选择P3
  • 5时刻：P4到达，此时：P1(5)、P2(2)、P4(4)，P2和P4优先数高且相等，但P2先到达就绪队列，选择P2
    …
    P1->P2->P3->P2->P4->P1
    操作系统之调度算法

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

  • 算法：
    1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    2.新进程到达时先进入第1级队列，按FCFS原则排队等待分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级队列，则重新放回该队列队尾
    3.只有第K级队列为空时，才会为K+1级队头进程分配时间片
  • 特征：抢占式算法，也有非抢占式算法；适用于进程调度
  • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统，比较灵活
  • 缺点：若源源不断地有高级优先进程到来，可能导致饥饿。

例题：用多级反馈队列调度算法：分析下表中进程运行的过程
操作系统之调度算法
多级就绪队列
操作系统之调度算法

分析：

  • 0时刻：P1进入第1级队列，执行时间片，此时：P1(7)，P1进入第2级队列
  • 1时刻：P2进入第1级队列，因为第1级队列有进程，所以不执行第2级队列，对P2执行时间片，此时：P1(7),P2(3)，P2进入第2级队列
  • 2时刻：因为第1级队列没有进程，所以调度P1，此时：P1(5),P2(3)，P1进入第3级队列
  • 4时刻：P2(3),P1(5),执行第2级队列，调度P2，此时P2(2),P1(5)
  • 5时刻：P3到达，抢占处理机，此时：P3(1)，P2(2)，P1(5)
  • 6时刻：P3处理完成，继续运行P2，此时：P2(2),P1(5)
  • 8时刻：只剩P1，在第3级队列
    P1->P2->P1->P2->P3->P2->P1

操作系统之调度算法

上一篇：IDEA mybatis-plus搭建


下一篇：P4 04 特征工程的定义