3处理机调度与死锁

一．处理机调度相关基本概念

处理机调度：多道程序环境下，动态的把处理机分配给就绪队列中的一个进程使之执行。

高级调度：主要在早期批处理阶段，处理在外存上的作业。

决定外存后备队列中的哪些作业调入内存;

为它们创建进程、分配必要的资源;

将新创建的进程排在就绪队列上，准备执行。

中级调度：提高内存利用率和系统吞吐量。根据条件将一些进程调出或再调入内存。

低级调度：决定内存就绪队列中的哪个进程获得处理机，进行分配工作。是最基本的一种调度，在三种基本OS中都有。

二．常用调度算法

1)面向用户的准则

2)面向系统的准则

1、先来先服务调度算法FCFS

不利于短作业（进程）

2.短作业（进程）优先调度算法SJF/SPF

分抢占和非抢占两种方式

能有效的降低作业的平均等待时间，提高系统吞吐量。

3.高优先权优先调度算法HPF

（1）非抢占式优先权算法

（2）抢占式优先权算法关键点：新作业产生时

4.高响应比优先调度算法HRRN

优先权 =（等待时间+要求服务时间)/要求服务时间

     = 响应时间 / 要求服务时间

基于时间片的轮转调度算法RR

（1）时间片轮转算法

能够及时响应，但没有考虑作业长短等问题。

（2）多级反馈队列算法FB

特点：多个就绪队列，循环反馈

    动态优先级、时间片轮转

1）设置多个就绪队列，各队列有不同的优先级,优先级从第一个队列依次降低。

2）赋予各队列进程执行时间片大小不同, 优先权越高，时间片越短。

三．实时调度

1.实现实时调度的基本条件

1）提供必要的信息

就绪时间。该任务成为就绪状态的时间。

开始截止时间、完成截止时间。

处理时间。从开始执行到完成所需时间。

资源要求。任务执行时所需的一组资源。

优先级。根据任务性质赋予不同优先级。

2）系统处理能力足够强

3）采用抢占式调度机制

4）具有快速切换机制

进程切换发生的时机

进程执行完

进程I/O阻塞

新进程出现时可能的抢占

某进程松弛度为0时发生抢占

四．产生死锁的原因和必要条件

死锁（Deadlock）: 指进程之间无休止地互相等待!

饥饿（Starvation）:指一个进程无休止地等待！

原因：

1.竞争资源。系统中供多个进程共享的资源如打印机、公用队列等的数目不满足需要时，会引起资源竞争而产生死锁。

2.进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。

条件：

①互斥条件：进程对所分配到的资源进行排他性使用

②请求和保持条件：进程已经保持了至少一个资源，又提出新的资源请求，而新请求资源被其他进程占有只能造成自身进程阻塞，但对自己已获得的其他资源保持不放，必然影响其他进程。

③不剥夺条件：进程已获得的资源未使用完之前不能被剥夺，只能在使用完时由自己释放。

④环路等待条件

五．预防死锁的方法

破坏死锁条件

六．死锁的检测与解除

1.剥夺资源。从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。

2.撤销进程。最简单的是让全部进程都死掉；温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用，使死锁状态消除为止。