介绍一些进程调度上判断依据的概念和计算方式以及进程调度算法的说明。
基本概念
-
完成时间：进程完成的时间。
-
周转时间：指进程从到达等待队列到完成执行的时间。
$$
T_i=作业i完成时间-作业i到达时间 \quad or \quad T_i=作业i执行时间+作业i等待时间
$$ -
带权周转时间
$$
带权周转时间=\frac{周转时间}{实际执行时间}
$$ -
平均周转时间
$$
平均周转时间=\frac{\sum_{i=1}^{n}作业_i周转时间}{n}
$$ -
平均带权周转时间
$$
平均带权周转时间=\frac{\sum_{i=1}^{n}带权周转时间}{n}
$$
调度算法
先来先服务调度算法
-
最简单的调度算法，先进入的队列的进程优先调度
-
非抢占式算法
短作业优先调度算法
- 每一次调度从预估运行时间最小的进程优先调度
- 非抢占式调度算法
- 和先来先服务调度算法相比，降低平局周转时间和平局带权周转时间
- 但是存在进程"饿死"问题，即一直有短作业进程进入队列，而长作业进程始终不能被调度
时间片轮转调度算法
- 进程按到达系统时间的先后次序排队，按照先来先服务的规则调度进程，但是每个进程在处理机上运行规定好的一个时间片的时间，如果没有执行完，则将进程重新排队到就绪队列队尾。
- 如果进程在一个时间片上执行等待其他事件发生或资源，则将进程插到阻塞队列中，等所有资源拿到后在插入到就绪队列队尾。
- 抢占式调度算法。
高响应比优先调度算法
-
非抢占式算法
-
在调度进程的时候统计计算响应比的值，来选择调度哪一个进程，计算公式如下：
$$
R_p=\frac{运行时间+等待时间}{运行时间}
$$
响应比大，优先调度。
优先级调度算法
-
静态优先级
进程创建时就定义一个优先级，之后整个生命周期优先级不在改变。
- 简单、系统开销小
- 不灵活，优先级低的长时间得不到调度
-
动态优先级
进入系统时根据某种规则赋予一个优先级，其后不断进行动态调整。
- 灵活、资源利用率高
优先级调度算法分为抢占式和非抢占式两种。
抢占式指的是只有就绪队列中有比当前运行进程的优先级高的，运行进程被切换下来，运行优先高的进程。
非抢占式指的是当有优先级高的进程在队列中，当前运行的的进程不会切换下来，而是等它执行完。
抢占式适合对实时性要求高的系统，但是会增加系统进程切换的开销。
非抢占式适合批处理系统，只有线程完成或者等待资源才会从处理机上下来。
多级反馈队列调度算法
-
有多个就绪队列，每个队列对应一个优先级。每个优先级队列分配的时间片不同，优先级越高，时间片长度越短。
-
新进程进入系统先放入最高优先队列Q1中，执行一个时间片的时间，如果没有执行完，则放入到下一个优先级的队列Q2的队尾。
-
仅当前面优先级高的几个队列为空，才能调度后面较低优先级队列中的进程。
当低优先级队列中进程上处理运行，如果此时高优先级队列中进入新进程，处理机采用抢占式策略，将当前运行进程切换下来，然后运行优先级高队列上的进程。
同优先级队列中的进程按照先来先服务的策略，不进行抢占。
多级反馈队列调度算法能够满足段进程优先处理，系统开销小（长作业进程主要在低优先级队列中进行），能够同时支持分时，实时，批处理的通用操作系统。还是存在较低队列中进程长时间得不到运行，导致"饥饿"。
解题方法
对于进程调度求解可以进行画图的形式来做题。例题：
