在多道程序系统中，一个作业从提交到执行，通常都要经过多级调度，而系统运行的性能在很大程度上取决于调度，因此调度便成为操作系统设计的一个中心问题之一。
1、高级调度--作业调度，长程调度
作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度(AdmissionScheduling)。
2、低级调度
低级调度的功能---进程调度，短程调度
（1）保存处理机的现场信息
（2）按某种算法选取进程
（3）把处理机分配给进程
3、中级调度---交换调度
1、目的：提高内存利用率和系统吞吐量。
2、方法：
（1）将暂时不能运行的进程调至外存上去等待，此时进程状态为：就绪驻外存状态或挂起状态。
（2）再次满足运行条件时，由中级调度把外存上的具备运行条件的进程，调入内存，挂在就绪队列上等待进程调度
1、作业
(1)作业(Job)。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。
(2)作业步(JobStep)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。
例如，一个典型的作业可分成三个作业步：①“编译”作业步，通过执行编译程序对源程序进行编译，产生若干个目标程序段；②“连结装配”作业步，将“编译”作业步所产生的若干个目标程序段装配成可执行的目标程序；③“运行”作业步，将可执行的目标程序读入内存并控制其运行。
(3)作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。
2、作业控制块JCB
为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块，如同进程控制块是进程在系统中存在的标志一样，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。
每当作业进入系统时，系统便为每个作业建立一个JCB，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。在作业运行期间，系统就按照JCB中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。
3、作业运行的三个阶段和三个状态
4、作业调度的任务
2）决定接纳哪些作业应将哪些作业从外存调入内存，这将取决于所采用的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存；较常用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是“响应比高者优先”的调度算法。我们将在后面对上述几种算法作较为详细的介绍。
1、低级调度的任务
2、进程调度的三个基本机制
（1）排队器（进程队列）；
（2）分派器（分派程序）（调度程序）
（3）上下文切换机制（环境信息切换）
3、进程调度的方式
（1）非抢占方式(Non-preemptiveMode)
引发调度的事件：
①正在执行的进程执行完毕；
②发生某事件而不能再继续执行；
③执行中的进程因提出I/O请求而暂停执行；
④执行了某种原语操作。
特点：实现简单、系统开销小，适用于大多数的批处理系统环境，难以满足紧急任务的要求。
（2）抢占方式(PreemptiveMode)
抢占的原则：
(1)优先权原则
(2)短作业（进程）优先原则
1、处理机调度算法的共同目标
(1)资源利用率
(2)公平性
(3)平衡性
(4)策略强制执行
2、批处理系统的目标
3、分时系统的目标
2）均衡性
4、实时系统的目标
2）可预测性
1、先来先服务调度算法（FCFS）
2、短作业（进程）优先调度算法（SJF/SPF）
SJF/SPF算法的缺点：
(1)对长作业（进程）不利。调度程序总是优先调度那些（即使是后进来的）短作业（进程），可能使长作业（进程）长期不被调度。
(2)未考虑作业（进程）的紧迫程度。不能保证紧迫性作业（进程）被及时处理。
(3)作业（进程）的长短没有客观标准。可能有失公平，损害算法初衷。
1、优先权调度算法的类型
（1）非抢占式优先权算法
主要用于批处理系统中；
（2）抢占式优先权调度算法
能更好地满足紧迫作业的要求，常用于要求比较严格的实时系统中，以及对性能要求较高的批处理系统和分时系统中。
2、优先权的类型
（1）静态优先权
优先权是在创建进程时确定，在进程的整个运行期间保持不变。
优先权的确定依据：进程类型，进程对资源的需求，用户要求。
（2）动态优先权
3、高响应比优先调度算法
（2）高响应比优先调度算法优点：
2、进程切换时机
1、保证调度算法
不做要求
1）可重用性资源
2）可消耗性资源
1）可抢占性资源
2）不可抢占性资源
死锁：指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。
产生死锁的原因：
1、竞争不可抢占性资源引起进程死锁
2、竞争可消耗性资源
3、进程推进顺序不当引起的死锁
当进程P1、P2共享资源A、B时，若推进顺序合法则不会产生死锁，否则会产生死锁。
合法的推进路线：①②③不合法的推进线路：④
1、死锁的定义
如果系统中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程就是死锁的。
2、产生死锁的必要条件
(1)互斥条件
(2)请求和保持条件
(3)不剥夺条件
(4)环路等待条件
3、处理死锁的基本方法
(1)预防死锁
(2)避免死锁
(3)检测死锁
(4)解除死锁
1、第一种协议
系统要求所有进程要一次性地申请在整个运行过程所需要的全部资源。
摒弃请求条件：进程在整个运行期间，不再提出资源要求。
摒弃保持条件：等待期间进程不占有任何资源。
优点：简单、易于实现、且安全。
缺点：（1）资源严重浪费（2）进程延迟运行
2、第二种协议
思想：允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己、且已用完的全部资源，然后再请求新的所需资源。
思想：允许进程还未执行完成时释放已经占有的资源。
方法:
方法：
给资源编号，进程必须按序申请资源。
局限：
所谓安全状态，是指系统能按某种进程顺序(P1,P2,…，Pn)(称P1,P2,…,Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。
如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
避免死锁的关键就是：让系统在动态分配资源的过程中，不要进入不安全状态。
2、安全状态之例
3、由安全状态向不安全状态的转换
如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态，进而可能造成死锁。
1965年由Dijkstra为T.H.E系统设计
基本思想：借用了银行借贷系统的分配策略。
基本规则：
（2）满足最大需求后要及时归还资金
（3）客户申请的贷款数量不超过它自己拥有的最大值时，银行要尽量满足客户需求
客户---->资金
银行---->进程
资源---->操作系统
1、银行家算法中的数据结构
(1)可利用资源向量Available，表示系统中可利用的资源的数目；如Available［j］=K，表示系统中Rj类资源有K个。
(2)最大需求矩阵Max，表示n个进程中的各进程对m类资源的最大需求，如Max［i,j］=K，表示进程i需要Rj类资源的最大数目为K个。
(3)分配矩阵Allocation，表示各进程当前已分得各类资源的数目；如Allocation［i,j］=K，表示进程i当前已分得K个Rj类资源。
(4)需求矩阵Need，表示各进程尚需的各类资源的数目；如Need［i,j］=K，表示进程i还需要K个Rj类资源，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j]
2、银行家算法
(1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Requesti［j］≤Available［j］，便转向步骤3；否则，表示尚无足够资源，Pi须等待。
(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］:=Available［j］-Requesti［j］;Allocation［i,j］:=Allocation［i,j］+Requesti［j］;Need［i,j］:=Need［i,j］-Requesti［j］;
(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi；否则，恢复原来的资源分配状态，让进程Pi等待。
3、安全性算法
（1）设置两个向量：
①工作向量Work:表示系统可提供给进程继续运行的各类资源数目，在执行安全算法开始时，Work=Available;
②Finish:表示系统是否有足够的资源分配给进程，开始时先做Finish［i］：=false;当有足够资源分配给进程时，再令Finish［i］=true.
（2）从进程集合中找到一个能满足下述条件的进程：
①Finish［i］=false且
②Need［i,j］≤Work［j］；若找到，执行步骤(3)，否则，执行步骤(4)。
（3）进程Pi获得资源后，能顺利完成，并释放全部资源，则修改向量：Work［j］：=Work［i］+Allocation［i,j］;Finish［i］：=true;gotostep2;
（4）如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
设置两个向量:work、Finish
从进程集合中找到一个能满足下述条件的进程：Finish[i]=false&Needi<=work
执行：
Work:=Work+Allocation;
Finish[i]:=true;
循环，如果所有进程的Finish[i]=true则安全。
5、银行家算法的优缺点
优点：
缺点：
要求：
1、资源分配图(ResourceAllocationGraph)
资源分配图化简：
2、死锁定理
当且仅当系统某状态S所对应的资源分配图是不可完全化简的，则S是死锁状态，而相应进程被死锁。
如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁
如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。
有环有死锁
有环无死锁
3、死锁检测中的数据结构
(1)可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。
(2)把不占用资源的进程(向量Allocation∶=0)记入L表中，即Li∪L。
(3)从进程集合中找到一个Requesti≤Work的进程，做如下处理：
①将其资源分配图简化，释放出资源，增加工作向量Work∶=Work+Allocationi。
②将它记入L表中。
(4)若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。
重新启动：这是一种常用但比较粗暴的方法，虽然实现简单，但会使之前的工作全部白费，造成很大的损失和浪费。
撤消进程：死锁发生时，系统撤消造成死锁的进程，解除死锁。一次性撤消所有的死锁进程。损失较大。逐个撤消，分别收回资源。
剥夺资源：死锁时，系统保留死锁进程，只剥夺死锁进程占有的资源，直到解除死锁。选择被剥夺资源进程的方法和选择被撤消进程相同。
进程回退：死锁时，系统可以根据保留的历史信息，让死锁的进程从当前状态向后退回到某种状态，直到死锁解除。