进程优先级逆转问题的解决

这是在看《鼠眼再看Linux调度器》时候，看到优先级逆转这个问题，找了几篇论文读了一下，稍微有些认识，后面主要是讲优先级继承协议。

优先级逆转：
如果系统对资源的访问策略是先来先服务(First Come First Served)则一旦低优先级的任务使用临界资源并上锁，就会使得随后到达的高优先级任务等待直到低优先级任务释放此临界资源，这种情况称为优先级逆转。
优先级逆转产生的直接原因是为了保持共享资源的一致性，并发的多任务需要按照互斥对共享资源进行访问。

避免优先级反转的两种常见方法是：优先级继承协议(Priority Inheritance Protocol, PIP)和优先级上限协议(Priority Ceiling Protocol, PCP)，其中优先级上限协议又被称为优先级天花板协议。
两种方法的前提都是优先级可改变，而且是可以动态改变的。

优先级上限协议：
为每个信号量设置一个“优先级顶”，“优先级顶”定义为要调用该信号量的所有任务中最高优先级。一个任务要想对共享资源操作开始一个新的临界区时，它的优先级必须严格高于当前其他任务锁住各信号量的“优先级顶”，否则它将被占有最高“优先级顶“信号量的任务所阻塞。每个信号量的“优先级顶”是在任务集执行之前通过预分析得到的。

优先级继承协议：
优先级继承协议(Priority Inheritance Protocol, PIP)的基本思想是当更高优先级的进程Ji被进程Jk阻塞时，Jk暂时继承Ji的优先级，这将防止中间优先级的进程抢占进程Jk使高优先级进程Ji的阻塞时间延长。

优先级继承协议中的死锁问题：
低优先级作业Jl获取信号量S1进入临界区Z1，在执行过程中高优先级Jh抢占Jl并获取信号量S2进入临界区Z2，在Z2中Jh申请S1被Jl阻塞，Jl继承Jh优先级继续执行Z1，此时Jl需要获取S2，死锁产生。
可见嵌套信号量顺序不一致造成了死锁，通过预先设定信号量获取顺序可以防止思索。或者是临界区执行过程是原子的，中间不允许被抢占。

如果进程拥有互斥锁并通过该互斥锁继承了高优先级，当进程释放该互斥锁，则进程的继承优先级应该设置为它拥有的所有互斥锁中能够继承的最高优先级。

信号量的优先级等于阻塞在这个信号量上的所有任务的最高优先级；每个任务的优先级为它拥有的信号量中的最高优先级。
SEMi->pri =
if(有任务阻塞在此SEM)
    取 max(TASKi1->pri, TASKi2->pri, ...Taskij->pri)
else
    取0

TASKn->pri =
if(有成功获取的信号量)
    取 max(SEM1->pri, SEM2->pri, ....SEMm->pri, TASKn->real_pri)
else
    取 TASKn->real_pri

解决方法：
1> 在mutex/sem结构中添加拥有该资源的进程
2> 在mutex/sem结构中记录继承的优先级
2> 在进程控制块中增加保存进程原先优先级的字段，便于执行完临界区后恢复之前的优先级
3> 在进程控制块中增加保存进程目前等待的资源的信号量

例如：
struct task_struct {
....
int save_prio, prio, static_prio;
...
mutex_t* block_on;
struct mutex_list_t locks_held;
};

struct mutex_list_t{
struct task_struct *proc;
struct mutex_list_t *next,*prev;
struct mutex mutex;
uint inherit_pri;
};

struct mutex{
atomic_t count;
mutex_list_t owner;
};

如果进程拥有互斥锁并通过该互斥锁继承了高优先级，当进程释放该互斥锁后应该重新计算它的优先级，比较进程的优先级是否大于互斥锁的继承优先级，如果进程优先级低于互斥锁的优先级，则保存进程原先的优先级，提高进程的优先级到继承优先级。
如果进程拥有多个互斥锁，则进程的继承优先级应该设置为它拥有的所有互斥锁中能够继承的最高优先级。

当进程获得互斥缩的时候，如果锁是空闲的，直接将互斥锁加入到进程结构的拥有锁列表中locks_held，并设置锁的拥有者为当前进程。
如果锁已经被锁住了，则进行优先级继承，设置进程结构中的被阻塞锁block_on为这个锁。然后执行schedule()调度其他进程来运行。
优先级继承过程，将当前被阻塞的进程的优先级传递给直接和所有间接阻塞它的进程。
获得拥有该mutex的进程，如果找到的进程在block_on字段上有阻塞的锁，则继续查找拥有这个锁的进程，一直到找到一个最终进程，提高最终进程的优先级。

参考：
优先级继承协议在 Linux 中的实现
鼠眼再看Linux调度器
http://blog.chinaunix.net/u1/42957/showart.php?id=337604
Linux 进程同步中优先级翻转问题的解决