第八章 调度与死锁
8.1 调度的基本概念
一、调度的类型（层次关系）
1.高级调度（作业调度）
高级调度又称长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业凋入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列0高级调度上要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。
- 低级调度（进程调度）
低级调度又称为进程调度或短程调度，其所调度的对象是进程(或内核级线程)。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。
- 中级调度（对换）
中级调度又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐 最。为此，应把那些暂时不能运行的进程，凋至外存等待，此时进程的状态称为就绪驻外 存状态(或挂起状态)。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定， 把外存上的那些己具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。
二、调度准则（CPU利用率高）
- 平均周转时间短（批处理）
周转时间T=完成时刻-提交时刻=等待时间+运行时间
带权周转时间W=T/运行时间
- 相应时间快（分时）
- 截止时间有保证（实时）
8.2 调度算法
一、先来先服务（FCFS）
FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择儿个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。
|
进程名 |
A |
B |
C |
D |
E |
|
到达时刻 |
0 |
1 |
2 |
3 |
4 |
|
服务时间 |
4 |
3 |
5 |
2 |
4 |
|
开始时刻 |
0 |
4 |
7 |
12 |
14 |
|
完成时刻 |
4 |
7 |
12 |
14 |
18 |
|
T |
4 |
6 |
10 |
11 |
14 |
|
W |
1 |
2 |
2 |
5.5 |
3.5 |
二、短作业（进程）优先（SJ(P)F）
SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以 作业所要求的运行时间来衡量的。SJF箅法可以分別用于作业调度和进程调度。在把短作 业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若千个估计运行时间 最短的作业，优先将它们调入内存运行。
|
进程名 |
A |
B |
C |
D |
E |
|
到达时刻 |
0 |
1 |
2 |
3 |
4 |
|
服务时间 |
4 |
3 |
5 |
2 |
4 |
|
开始时刻 |
0 |
6 |
13 |
4 |
9 |
|
完成时刻 |
4 |
9 |
18 |
6 |
13 |
|
T |
4 |
8 |
16 |
3 |
9 |
|
W |
1 |
2.67 |
3.2 |
1.5 |
2.25 |
三、时间片轮转（RR）
四、优先级
我们可以这样来看作业的优先级，对于先来先服务调度算法，作业的等待时间就是作 业的优先级，等待时间越长，其优先级越对了-短作业优先调度算法，作业的长短就是 作业的优先级，作业所需运行的时间越短，优先级越高。但上述两种优先级都不能反映作业的紧迫程度。而在优先级调度算法屮，则是基于作业的紧迫程度，由外部赋予作业相 应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。 优先级调度算法可作为作业调度算法，也可作为进程调度算法。当把该算法用于作业调度 时，系统是从后备队列中选择若干个优先级最高的作业装入内存。
- 静态优先级
- 动态
- 非抢占
- 抢占
- 响应比高者优先
响应比=（等待时间+运行时间）/运行时间
五、多级队列
六、多级反馈队列（UNIX）
