嵌入式导论3：资源共享

嵌入式导论3：资源共享

1、优先级反转（Priority Inversion）

例1：
T1的优先级要高于T2的优先级。

T2在t0时刻执行P操作（获得信号量S），在t1时刻，由于T1的优先级要高于T2，T1发生抢占，T2被阻塞。

在t2时刻，T1执行P操作（此时T2持有信号量S），T1被阻塞，必须要等到T2把临界区里的任务执行完后用V操作释放信号量S后T1才能进入临界区继续执行。

例2：
优先级T1>T2>T3

T3先执行，且执行P操作，进入临界区。

T2，T1依次进来，当T1执行P操作时，发生阻塞。T2会继续执行。
T2执行完后，T3继续执行，执行V操作释放临界区资源，这时候T1被唤醒。

这样，T1的优先级比T2高，但是T2却先于T1执行，就会造成优先级反转。

2、资源访问协议（Resource Access Protocols）

基本思想：

修改导致阻塞的进程的优先级。当一个优先级较低的进程阻塞了一个优先级较高的进程时，会将这个优先级较低的进程的优先级提高。

方法：

1. 优先级继承协议（Priority Inheritance Protocol, PIP），适用于静态优先级的情况。
2. 优先级天花板协议（Priority CeilingProtocol, PCP），适用于静态优先级的情况。
3. 堆栈资源策略（Stack Resource Policy, SRP），适用于动态和静态优先级的情况。

下面分别介绍这三种方法：

（1）优先级继承协议（PIP）

前提：

优先级固定

基本思想：

（1）当一个优先级较低的进程阻塞了一个优先级较高的进程时，会将这个优先级较低的进程的优先级提高到被阻塞的进程的优先级。
（2）当一个优先级较低的进程阻塞了多个优先级较高的进程时，会将这个优先级较低的进程的优先级提高到被阻塞的进程中优先级最高的进程的优先级。

算法描述：

1. 如果进程Ti视图进入临界区会出现以下三种情况：
   （1）如果临界区资源被一个较高优先级的进行占用，Ti会被阻塞，不进去后续操作；
   （2）如果临界区资源被一个较低优先级的进行占用，Ti会被阻塞，且进行第2步；
   （3）否则，就立即进入临界区。
2. 当进程Ti被阻塞时，它将自己的优先级捐赠给当前拥有信号量的进行Tk。在当前拥有信号量的进程Tk离开临界区之前都会保持这个优先级。
3. 当进程Tk离开临界区后，执行V操作释放信号量，然后这个信号量就会给到当前阻塞队列中优先级最高的进程。如果只有一个进程被阻塞，那么Tk会立即恢复为它原本的优先级；否则，会改变为现在仍在阻塞队列中的进程的最高优先级。

例1：

从上面这个例子可以看出，使用PIP后，T1被阻塞时，T3的优先级升高为T1的优先级（比T2的优先级高），因此此时T3由于T2执行。T3执行完毕后，执行V操作释放信号量，此时T3的优先级会恢复为原始优先级，T1被唤醒，由于T1的优先级高于T2的优先级，因此T1先执行。T1执行完毕后，T2才能够执行。

例2：注意在释放信号量b时，T3的优先级没有发生变化，这是因为T3的优先级为阻塞队列中的进程的最高优先级（即T1的优先级），否则，T2就会先于T1执行了。

例3：可能会发生死锁

T1的优先级高于T2的优先级。
T2先执行，获取信号量Sb；T1进入就绪队列后发生抢占，获取信号量Sa，然后请求信号量Sb（被T2持有），会被阻塞。根据PIP，T2的优先级升高为T1的优先级，T2执行，请求信号量Sa（被T1持有），会被阻塞。这样就会出现T1被T2阻塞，T2被T1阻塞的死锁的局面。
事实上，就算没有进行优先级捐赠，这样的死锁同样有可能发生。也就是说，PIP并不能防止这样的死锁的发生。

（2）优先级天花板协议（PCP）

前提：

优先级固定

基本思想：

算法描述：