进程调度算法
调度算法的评价指标
先来先服务（FCFS）
先来先服务是非抢占式的算法
一个🌰
例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。
| 进程 | 到达时间 | 运行时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
解释：
先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
因此，调度顺序为：P1->P2->P3->P4
平均周转时间= (7+9+8+11)/4 = 8.75
平均带权周转时间= (1+2.25+8+2.75)/4 = 3.5
平均等待时间= (0+5+7+7)/4 = 4.75
短作业优先（SJF）
短作业优先算法分为抢占式和非抢占式
一个🌰：非抢占式
例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式的短作业优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。
| 进程 | 到达时间 | 运行时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
解释：
短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。
因此，调度顺序为：P1->P3->P2->P4
刚开始只有p1到达，所以执行p1，然后当p1执行完毕后，此时是时刻7，剩余三个进程均已到达，所以按照运行时间最短的，执行p3
周转时间= 完成时间- 到达时间 P1=7-0=7；P3=8-4=4；P2=12-2=10；P4=16-5=11
带权周转时间= 周转时间/运行时间 P1=7/7=1；P3=4/1=4；P2=10/4=2.5；P4=11/4=2.75
等待时间= 周转时间– 运行时间 P1=7-7=0；P3=4-1=3；P2=10-4=6；P4=11-4=7
平均周转时间= (7+4+10+11)/4 = 8
平均带权周转时间= (1+4+2.5+2.75)/4 = 2.56
平均等待时间= (0+3+6+7)/4 = 4
高响应比优先算法（HRRN）
高响应比优先算法是非抢占式的算法
响应比 = 等待时间+要求服务时间 / 要求服务时间
一个🌰
例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用高响应比优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。
| 进程 | 到达时间 | 运行时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
解释：
-
0时刻：只有P1 到达就绪队列，P1上处理机
-
7时刻（P1主动放弃CPU）：就绪队列中有P2 (响应比=(5+4)/4=2.25)、P3((3+1)/1=4)、P4((2+4)/4=1.5)，
-
8时刻（P3完成）： P2(2.5)、P4(1.75)
-
12时刻（P2完成）：就绪队列中只剩下P4
时间片轮转调度算法（RR）
时间片轮转调度算法属于抢占式
如果在一个时间片内，某个进程执行完毕，就会主动放弃处理机，发生调度
如果在一个时间片内，某个进程还未处理完毕，当时间片运行结束后，强行放弃处理机
一个🌰
优先级调度算法
优先级调度分为抢占式和非抢占式
- 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
- 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
但是依然有缺点，可能会导致低优先级的进程永远不会运行。
一个🌰：非抢占式
一个🌰：抢占式
多级反馈队列（Multilevel Feedback Queue）调度算法
是「时间片轮转算法」和「优先级算法」的综合和发展。文章来源：https://www.toymoban.com/news/detail-501943.html
- 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
- 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列
文章来源地址https://www.toymoban.com/news/detail-501943.html
到了这里，关于【操作系统】期末速成之计算题：进程调度算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
