多线程的那点儿事（之优先级反转）

winston

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    优先级反转对于编写应用层的人员来说不大会发生，但是对于操作系统的设计者来说确是一个逃不过去的问题。要知道怎么样处理优先级反转？那么先看看它是怎么发生的。


    （1）调度队列和线程优先级
    在操作系统中，线程的状态有很多种。比如说，线程的状态可能是suspend、block、ready、die几种类型。我们把所有的ready线程放在一个队列里面，这就构成了一个基本的调度队列。    我们还知道，为了对所有的线程进行有差别的时间调度，我们对所有的线程分配了优先级。打个比方，调度队列有32个线程，每个线程的优先级也是1到32。这些优先级对于线程来说有什么意义呢？那就是，高优先级可以获得较多的时间片运行机会。进一步极端一点说，优先级为32可以32个基本时间片，那么优先级为1的线程只能获得一个时间片的运行机会。

    （2）锁和线程

    在队列调度过程当中，高优先级的线程获得较多的运行机会，而与此对应的低优先级线程运行的机会较少。举个例子来说，现在有32个线程，线程的优先级分布在1~32之间。那么这些程序怎么运行呢，

    线程0x20  优先级32   时间片 32个
    线程0x1F  优先级31   时间片 31个
    线程0x1E  优先级30   时间片 30个
    /* 其他线程 */
    线程0x01  优先级01   时间片 01个

    所以如果总的时间片为(1 + 32) * (32 / 2) = 528, 所以一段时间内每个线程都有运行的机会。只不过，各个线程运行的机会不一样而已。但是这一切都因为锁的存在发生了改变。假设现在线程0x20和0x1都在争取一个锁，而这个锁此时正处在线程0x01的运行时间片内，所以线程0x01获得了锁。那么线程0x20此时只好退出运行队列，静静等待线程0x1退出锁了。
    糟糕的还不止这一点，前面我们说过低优先级的线程运行机会较少。所以，线程0x01获得运行的机会只是1/528，即使线程0x20退出了队列，那只有1/496，其中 496 = (1 + 31) / 2 * 31。如果线程0x01运行的时间还比较长，那就比较悲催了。线程0x20还要等待多长时间才能获得线程0x01的锁，那就只有天知道了。此时，原来的优先级也失去了意义，这才是优先级发生反转的真实原因。
    （3）解决方法
    原来制定优先级的目的就是为了让有的程序运行时间长一点，有的程序运行时间短一点。然而，这一切在锁面前从优点变成了缺点。那么解决的办法是什么呢？其实也不难，那就是提高线程0x01的优先级，尽快让线程0x01尽快退出锁。线程0x01和线程0x20交换一下优先级的方法就不错。


总结：

    （1）优先级反转提醒我们使用锁的代码段应尽量短；
    （2）注意用小锁代替大锁，减少冲突的机会；
    （3）如果锁保护的代码段很短，直接使用原子锁忙等也是不错的一个方法。