操作系统考试复习—第三章 优先级倒置 死锁问题

当前OS广泛采用优先级调度算法和抢占方式，然而在系统中存在着影响进程运行的资源从而可能产生"优先级倒置"现象

具体解释为：在原本的调度算法设计中，高优先级进程可以抢占低优先级的CPU资源，先执行高优先级任务。但是存在某种情况下会出现高优先级的进程无法完成需要等低优先级的进程完成后才可以执行，这样的现象在实时系统当中很危险有很大的坏处所以我们要避免它的出现。

这种情况是怎么形成的呢，假如有三个完全独立的进程P1,P2,P3。P1的优先级最高依次减小，P3优先级最低。P1和P3两者共用一个临界资源。当P3先执行的时候只是进行了P操作未进行V操作将临界资源释放但是P2这时候把P3的处理机抢占了这时P3无法执行。当P1要执行的时候虽然可以将P2占有的处理机抢占但是无法把P3占用的临界资源进行得到。所以需要等待P2执行结束再P3执行结束释放临界资源这时候P1才可以进行执行。

通俗来讲：

优先级反转最坏的一种情况就是，一个高优先级任务很紧急，但其资源已经被一个低优先级任务占有，且该低优先级任务前还有很多个耗时很长的中优先级任务。

对于针对任务的紧急重要程度而设计的优先级调度机制，优先级反转导致的这种情况是对优先级调度本身的践踏，

其公平，无错，循规蹈矩，但后果恶劣。
解决优先级倒置的方法有：优先级继承方法。

优先级继承方法是有效解决优先级反转问题的一种方法，其“继承”的思路其实不复杂。简言之，优先级继承就是临时把低优先级任务的优先级升高，让CPU优先并尽快执行完该低优先级任务，执行完时将其优先级再降至原优先级，并释放资源，原本的高优先级任务拿到资源后则可以抢占CPU并执行。

 死锁问题

死锁问题的定义：在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占用的资源.或者说每个进程所等待的事件是该组中其他进程释放所占有的资源。

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

产生死锁的四个必要条件：

1.互斥条件：进程对所分配到的资源进行排它性使用，即在一段时间内，某资源只能被一个进程占用。如果此时还有其他进程请求资源，则该请求进程只能等待，直至该资源的进程用毕释放。

2.请求保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被堵塞，但对自己已获得的资源保持不放。

3.不可抢占条件：进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完之后自己释放

4.循环等待条件：在发生死锁的时，必然存在一个进程—资源的循环链。

例如：进程 P1 已经分得了两个 R1 资源，并又请求一个 R2 资源；进程 P2 分得了一个 R1 和一个 R2 资源，并又请求一个 R1 资源。

死锁的检测

为了能对系统是否已发生了死锁进行检测，必须

1.用某种数据结构来保存资源的请求和分配信息；

2.提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

数据结构：资源分配图由一组结点和一组边构成。

结点分为资源结点(对应一类资源,一类资源可能由多个)和进程结点(对应一个进程)。

边分为分配边(资源结点->进程结点)和申请边(进程结点->资源结点)

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可用顺利地执行下去。

如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。

相应地，这些被激活的进程执行完之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程

如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）

如果最终不能消除所有边，那么此时就是发生了死锁。

检测死锁的算法：

1）在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。

2）进程Pi所释放的资源，可用唤醒某些某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。根据1中的方法进行一系列简化后，若能消区图中所有的边，则称该图是完全简化的。那么也就是不存在死锁的

对于下面的资源分配图来说：

 对于P1而言它向R2请求资源由于R2里面有两个资源只有一个被分配了所以P1是可用进行下去的。所以我们认为P1是可以运行完释放的我们将P1的分配边和请求边删去。然后我们发现P2从堵塞状态到了可以执行的状态了，所以P2也是可用将它的分配边和请求边释放了。最后都是孤立结点了，那么就可以认为是不存在死锁的。

 死锁的解除

解除死锁的基本方法：

1.抢占资源法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这样资源分配给其他的死锁进程。但是应该防止被挂起的进程长时间得不到资源而饥饿。

2.撤销进程法（或终止进程法）：

一种情况是终止所有的死锁进程那么死锁也就解除了。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。

另一种情况是：按照某种顺序逐个地终止进程，直到有足够的资源将系统从死锁状态释放出来。但是这种方法所付出的代价可能性也很大因为每次释放一个进程都要用检测算法检测是不是从死锁状态释放了。另外也需要寻找思考用什么样的策略选择一个要终止的进程。

3.进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。