【OS】处理机调度和死锁

处理及调度的层次

作业从进入系统成为后备作业开始，直到运行结束退出系统为止，经历不同级别的调度。
·高级调度（作业调度）
·中级调度
·低级调度（进程调度）

高级调度（作业调度）

功能：根据某种算法，把外存上处于后备作业队列中的作业调入内存，为它们创建进程，分配必要的资源，并将它们放入就绪队列。

调度对象：作业。
作业：不仅包含通常的程序和数据，还配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。
作业=程序+数据+作业说明书（根据说明书对程序的运行进行控制-作业控制快（JCB））
作业步（内存管理的内容）：作业的一部分，通常在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称为一个作业步。各作业步之间存在着相互联系。
典型的作业分为三步—编译作业+连接装配作业+运行作业步
作业流：若干个作业进入系统，存放在外存。
作业控制块（JCB）：为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制快，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。
当一个作业进入系统时，由“作业注册”程序为该作业建立JCB，再根据作业类型，将它放到对应的作业后备队列中等待调度。调度程序依据一定的调度算法来调度它们，被调度的作业将被装入内存。在作业运行期间，系统就按照JCB中的信息和作业说明书对作业进行控制。
当一个作业执行结束进入完成状态时，系统负责回收已分配给它的资源，撤销作业控制块。
主要功能：根据JCB中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为其创建进程、分配必要的资源，然后再将新建的进程插入到就绪队列，准备执行。
主要用于多道批处理系统。在分时和实时系统中不设置高级调度。

进程调度（低级调度）

调度对象是进程（内核级线程），是最基本的一种调度

主要功能

1）保存处理机现场信息，在进行调度时首先保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。
2）按某种算法选取进程
3）把处理器分配给进程。由分派程序把处理器分配给该进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。

进程调度机制

进程调度方式

非抢占式

引起进程调度的因素

1.正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行。
2.在进程通信或同步过程中，执行了某种原语操作。

特征

1.系统开销小，适用于大多数的批处理系统
2.难以满足紧急任务的要求，无法立即执行。

抢占式

特点

优点：可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更公平的服务。
缺点：系统开销较大

抢占原则

1.优先权原则
2.短进程优先原则
3.时间片原则

中级调度（就是挂起）

为了使内存中同时存放的进程数目不至于太多，有时需要把某些进程从内存中移到虚拟内存上，以减少多道程序的数目，为此设立了中级调度。
功能：在内存使用情况紧张时，将一些暂时不能运行的进程从内存对换到外存的虚拟内存上等待。
目的：提高内存的利用率和系统吞吐量
它实际上就是存储器管理中的对换功能。

进程调度模型

1.仅有进程调度的队列模型

分时操作系统中，仅设置进程调度，用户键入的命令和数据直接送入内存，按时间片轮转的方式运行

分时操作系统只有低级调度，没有后备作业队列。

2.具有高级调度和低级调度的调度队列模型

1）就绪队列的形式
2）设置多个阻塞队列

3.具有三级调度的队列模型

调度算法

选择调度算法的原则

用户准则--------作业周转时间（是批处理系统衡量调度性能的重要指标）

概念：批处理用户从作业提交给系统开始，到作业完成为止的时间间隔
周转时间=在后备队列上等待作业调度的时间
+进程在就绪队列上等待进程调度的时间
+进程在CPU上运行的时间
+等待l/O操作完成的时间

作业周转时间与平均周转时间

若作业i提交给系统的时刻是ts,完成时刻是tf,
该作业的周转时间ti=tf-ts
实际上，它是作业在系统里的等待时间与运行时间之和。

为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。
平均作业周转时间T=（∑ti）/n

作业带权周转时间与平均带权周转时间
如果作业i的周转时间ti所需运行时间为tk,则该作业的带权周转时间wi=ti/tk
ti=等待时间+运行时间，所以带权周转时间总大于1
平均作业带权周转时间W=(∑wi)/n

用户准则--------响应时间

概念；从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间（换句话说，直到屏幕上显示出结果为止的一段时间间隔）
响应时间=从键盘输入的请求信息传送到处理机的时间
+处理机对请求信息进行处理的时间
+将所形成的响应时间回送到终端显示器时间
评价分时系统的性能，是选择分时系统中进程调度算法的重要准则之一。

用户准则----截止时间

概念：某任务必须开始执行的最迟时间，或必须完成的最迟时间
评价实时系统性能的重要指标

用户准则——优先权

以便某些紧急作业能得到及时处理，在某些场合会选择抢占式调度方式。

系统准则-----系统吞吐量

单位时间内系统完成的作业书，与批处理作业长度有关。
评价批处理系统性能的重要指标

系统准则——资源利用率

CPU利用率=CPU有效工作时间/CPU总运行时间
CPU总运行时间=CPU有效工作时间+CPU空闲等待时间

系统准则——公平性

确保每个用户每个进程获得合理的CPU份额或其他资源份额，确保不会出现饿死情况。

处理机调度算法

先来先服务调度算法（作业调度+进程调度）
最短作业调度算法（作业调度+进程调度）
高响应比调度算法（作业调度+进程调度）
高优先权调度算法（作业调度+进程调度）
时间片轮转调度算法（进程调度）
多级反馈调度算法（进程调度）

1.先来先服务（FCFS）调度算法

（1）平均作业周转时间和作业的提交和调度顺序有关
（2）有利于CPU繁忙型的作业，不利于I/O繁忙型作业
（3）不利于短作业，优于长作业
例子：

2.最短作业（SJF）调度算法

该算法调度依据：CPU运行时间
缺点：
1）该算法对长作业不利；如果有一长作业（进程）进入系统的后备队列（就绪队列），由于调度程序总是优先调度那些（即使是后进来的）短作业（进程），将导致长作业长期不被调度。
2）该算法完全没有考虑作业的紧迫程度，无法保证紧迫性作业会被及时处理
3）由于作业的长短只是根据用户所提供的估计执行时间而定，用户可能会有意无意缩短其作业的估计运行时间，致使该算法不一定真正做到短作业优先调度。

3.响应比最高者优先（HRRF）调度算法

FCFS和SJF是片面的调度算法
FCFS只考虑作业等候时间而忽视了作业的计算时间问题
SJF只考虑用户估计的作业计算时间而忽视作业等待时间
HRRF是介于两者之间的非剥夺式算法，两者都考虑到了。（考虑作业等待时间+作业运行时间；照顾短作业+不使长作业的等待时间过长，改进了调度性能。）
响应比=作业周转时间/作业处理时间
=（作业等待时间+作业处理时间）/作业处理时间
=1+作业等待时间/作业处理时间

短作业容易得到较高响应比
长作业等待时间足够长后，也将获得够高的响应比
饥饿现象不会发生。