处理机调度与死锁
高级调度定义
高级调度：也叫作业调度，调度对象是作业，用于决定把外存上处于后备队列中的哪些作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。
高级调度主要用于多道批处理系统中
分时系统和实时系统不设置高级调度
低级调度定义
低级调度又称为进程调度，其调度对象是进程（或内核级线程）。按某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。
多道批处理系统、分时系统和实时系统都设置低级调度
什么是中级调度，为什么引入中级调度
中级调度又称为内存调度。
引入中级调度主要目的：提高内存利用率和系统吞吐量。
内存紧张时，将暂时不能运行的进程调至外存上去等待，此时的进程处于挂起状态。
当进程具备运行条件、且内存不紧张时，由中级调度决定把外存上哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，插入在就绪队列上等待进程调度。
中级调度实质上就是存储器管理中的对换功能
资源利用率
CPU的利用率=CPU有效工作时间/(CPU有效工作时间+ CPU空闲等待时间)
进程调度的两种方式
先来先服务调度算法
先来先服务作业调度算法
系统按照作业到达的先后次序来进行调度，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程，然后把它们放入就绪队列。
先来先服务进程调度算法
每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。
例：
短作业(进程)优先调度算法
短作业优先(SJF)的调度算法
从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
短进程优先(SPF)调度算法
从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它。
例：
操作系统选择调度方式和调度算法的面向用户的准则和面向系统的准则
进程调度算法就是处理器分配算法
进程调度的任务:
- 保存处理机的现场信息
- 按某种算法选取进程
- 把处理器分配给进程
进程调度机制：
- 排队器
- 分派器
- 处理器上下文切换器
进程调度方式
非抢占方式
把处理机分配给某进程后，就一直让它运行下去，决不会会因为因为时钟中断或其它原因抢占，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程；
优点是实现简单、系统开销小
抢占方式
允许调度程序根据某种原则，去暂停某个正在执行的进程，将处理机分配给另一进程，是现代操作系统广泛使用抢占方式。
缺点是抢占方式比较复杂，所需付出的系统开销也较大
抢占原则
- 优先权原则。
- 短进程优先原则。
- 时间片原则。
高响应比优先调度算法的思想及响应比的计算
特点
``
时间片轮转调度算法原理
系统根据FCFS策略，将所有的就绪进程排成一个就绪队列，系统设置每隔一定时间间隔（例如30ms）产生一次中断，激活系统中的进程调度程序，完成一次调度。
每次调度时，把CPU分配给队首进程，并令其执行一个时间片。
每个进程每次最多执行一个时间片的CPU时间。
时间片大小确定
时间片太大：平均周转时间长，响应时间慢。
时间片太小：系统开销大（进程切换频繁）
时间片长度的选择原则：保证一个基本的交互过程可在一个时间片内完成。
时间片轮转调度算法举例
多级反馈队列调度算法的原理
将进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列中，不同的就绪队列采用不同的调度算法，不同的就绪队列本身也可以设置不同的优先级。
调度机制
就绪队列组织
设置多个就绪队列，每个队列赋予不同的优先级。
第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。
较高优先级的队列一般分配较短的时间片。
每个队列采用FCFS算法
当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。
当轮到该进程执行时，如它能在该时间片内完成，便可退出系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；
如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去;
当一个长作业(进程)从第一队列依次降到第n队列后,在第n队列中采取按时间片轮转的方式运行。
按队列优先级调度
调度程序先从高级就绪进程队列中选取进程，当高级就绪进程队列为空时，才从较低级的就绪进程队列中选取。进程每调度一次优先级下降一个级别。
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；
仅当上级队列均空时，才会调度下级队列中的进程运行。
如果处理机正在为某进程服务时，又有新进程进入上级优先权较高的队列，则此时新进程将抢占正在运行进程的处理机
调度算法的性能
在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，满足各种类型用户的需要
终端型作业用户：在第一队列规定的时间片内完成
短批处理作业用户：在第一、第二、第三队列的时间片内完成
长批处理作业用户：不必担心作业长期得不到处理
死锁定义
定义1：指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。
定义2：如果一组进程中的每个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。
产生死锁原因
竞争资源
当系统中供多个进程共享的资源数目不足以满足各个进程的需要时，会引起各进程对资源的竞争而产生死锁。
进程间推进顺序非法
进程在运行过程中，请求和释放资源的顺序不当，导致产生死锁。
产生死锁的必要条件
互斥条件
临界资源的特性：一段时间内只能给一个进程使用
请求和保持条件
一个进程保持对原有资源占有的同时申请新的资源，若该资源已经被其它进程占有，此时请求进程阻塞，但对自己获得的资源保持不放。
不剥夺条件
资源申请者不能强行从资源占有者手中夺取资源，资源只能由占有者自愿释放
环路等待条件
存在一个进程等待队列 {P1 , P2 , … , Pn}，其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路
处理死锁的基本方法
预防死锁
方法：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。
缺点：可能导致系统资源利用率和系统吞吐量降低。
哪一种必要条件不能摒弃？
互斥条件
哪一种预防方法取得较好的系统性能？
摒弃环路等待条件
避免死锁
在资源的动态分配过程中，防止系统进入不安全状态，从而避免发生死锁。
检测死锁
通过系统所设置的检测机构，及时检测出死锁的发生。
解除死锁
当系统中已发生死锁时，将进程从死锁状态解脱出来。
哪一个方法最易实现？
预防死锁
安全状态定义
指系统能按某种进程顺序(P1, P2, …，Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。称〈P1, P2, …, Pn〉序列为安全序列
不安全状态
如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
安全状态与死锁状态的关系是什么？
安全状态不会发生死锁，不安全状态不一定导致死锁。
银行家算法
思想
当进程提出资源请求后，先假设把资源分配给该进程，然后推算出资源分配后系统的状态是否是安全，如果分配资源后，系统处于安全状态则可以实施资源分配。否则系统处于不安全状态则不能实施资源分配。
银行家算法中的数据结构
可利用资源向量Available
这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，如果Available［j］=K，则表示系统中现有Rj类资源K个。
最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。
需求矩阵Need
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
矩阵间关系
Need［i,j］=Max［i,j］-Allocation［i,j］
细节
设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
- 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
- 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
- 系统假定把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］∶=Available［j］-Requesti［j］，Allocation［i,j］∶=Allocation［i,j］+Requesti［j］，Need［i,j］∶=Need［i,j］-Requesti［j］;
- 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
死锁定理及其作用
S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。