第3章 处理机调度与死锁
3.1 复习笔记
一、处理机调度的层次和调度算法的目标
调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。
1处理机调度的层次
（1）高级调度（作业调度）。
（2）中级调度（内存调度）。
（3）低级调度（进程调度）。
2处理机调度算法的目标
（1）资源利用率。
（2）公平性。
（3）平衡性。
（4）策略强制执行。
二、作业与进程的基本概念
1批处理系统中的作业
（1）作业和作业步
①作业
作业是用户提交给系统的一项相对独立的工作，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。
②作业步
在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。其中的每一个加工步骤称为一个作业步。
（2）作业控制块（JCB）
①定义
作业控制块是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。
②内容
JCB中包含的内容有：作业标识、用户名称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小等）、资源使用情况等。
2进程调度的任务和方式
（1）进程调度的任务
①保存处理机的现场信息。
②按某种算法选取进程。
③把处理器分配给进程。
（2）进程调度方式
①非抢占方式。
②抢占方式。
【说明】“抢占”必须遵循一定的原则，主要原则有：优先权原则、短进程优先原则、时间片原则。
（3）不能进行进程调度的情况
①在处理中断的过程中。
②进程在操作系统内核程序临界区中。
③需要完全屏蔽中断的原子操作过程中。
3调度的基本准则
（1）CPU利用率，其中计算公式为：
（2）系统吞吐量
（3）周转时间，需掌握以下公式：
①周转时间=作业完成时间-作业提交时间
②平均周转时间=(作业1的周转时间+…+作业n的周转时间)/n
③带权周转时间=作业周转时间/作业实际运行时间
（4）等待时间
（5）响应时间
三、典型调度算法
1先来先服务（FCFS）调度算法
（1）FCFS算法既可用于作业调度，也可用于进程调度。
（2）每次选择最早进入队列的作业（或进程）调入内存（或分配处理机）。
（3）属于不可剥夺算法。
（4）有利于CPU繁忙型作业，不利于I/O繁忙型作业；有利于长作业，不利于短作业。
2短作业优先（SJF）调度算法
（1）SJF算法既可用于作业调度，也可用于进程调度。
（2）每次选择运行时间最短的作业（或进程）调入内存（或分配处理机）。
（3）对长作业不利，且未考虑作业的紧迫程度。
（4）SJF算法的平均等待时间、平均周转时间最少。
3优先级调度算法
（1）既可用于作业调度，也可用于进程调度。
（2）每次选择优先级最高的作业（或进程）调入内存（或分配处理机）。
（3）根据更高优先级进程是否可以抢占正在执行的进程，分类为：
①抢占式优先级调度算法。
②非抢占式优先级调度算法。
（4）根据进程的优先级是否可以改变，将进程的优先级分类为：
①静态优先级。
②动态优先级。
4高响应比优先调度算法（HRRN）
（1）该算法主要用于作业调度。
（2）既考虑了作业的等待时间，又考虑了作业运行时间。
（3）响应比RP的计算公式为：
由上式可以看出：
a．如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，有利于短作业。
b．当要求服务的时间相同时，作业的优先权又决定于其等待时间，类似于FCFS算法。
c．长作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机，避免“饥饿”。
5时间片轮转调度算法
（1）主要适用于分时系统。
（2）每次选择就绪队列中的第一个进程，但是只能运行一个时间片大小。
（3）时间片长短的选择参考因素：系统的响应时间、就绪队列中的进程数目、系统的处理能力。
6多级反馈队列调度算法
（1）调度机制
①设置多个就绪队列，并为每个队列赋予不同的优先级。第一队列优先级最高，其余队列优先级依次降低。
②各个队列中进程执行时间片大小不同。优先级越高的队列中进程运行的时间片越小。
③除第n队列外，每个队列都采用FCFS算法，第n队列中按RR方式运行。
（2）调度算法的优势
①终端型用户：短作业优先。
②短批处理作业用户：周转时间短。
③长批处理作业用户：经过前面队列的部分执行，不会出现“饥饿”。
四、死锁
1死锁的定义、必要条件和处理方法
（1）死锁的定义
死锁是指多个进程因竞争资源而造成的一种相互等待，若无外力作用，这些进程都将无法继续运行。
（2）产生死锁的原因
①竞争不可抢占性资源。
②进程推进顺序不当。
（3）产生死锁的必要条件（填空题重要考点）
产生死锁必须同时具备下面四个必要条件，只要其中一个条件不成立，死锁就不会发生。
①互斥条件。
②请求和保持条件。
③不可抢占条件。
④循环等待条件。
2死锁的处理方法
（1）预防死锁
预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，从而避免死锁的产生。
【说明】互斥条件是非共享设备所必须的，不仅不能改变，还应加以保护。
①破坏“请求和保持”条件
方法：所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。
②破坏“不可抢占”条件
方法：当一个进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源。
③破坏“循环等待”条件
方法：对系统所有资源类型进行线性排序，并赋予不同的序号。每个进程必须按序号递增的顺序请求资源。
（2）死锁避免
①系统安全状态
a．安全状态是指系统能按某种进程推进顺序为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称（P1，P2，…，Pn）为安全序列。
b．如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
②利用银行家算法避免死锁
（3）死锁检测
①资源分配图
资源分配图中的符号表示：
a．圆圈代表一个进程。
b．方框代表一类资源。
c．方框中的一个点代表一类资源中的一个资源。
d．由进程出发到资源的有向边表示请求边。
e．由资源出发到进程的有向边表示分配边。
【说明】资源分配图中有环不一定存在死锁，无环一定没有死锁。
②死锁定理
状态S为死锁状态的充分条件是当且仅当S状态的资源分配图不可完全简化。
（4）死锁解除
①资源剥夺法。
②终止（或撤消）进程法。
③进程回退法。