基于加权平均PIP的Linux线程调度方法研究

张治元

基于加权平均PIP的Linux线程调度方法研究

张治元

（湖南邮电职业技术学院，湖南长沙410015）

在Linux系统中，优先级反转问题可能会造成系统崩溃。优先级反转使得高优先级任务的执行时间无法预测，增加了实时系统的不确定性，而优先级继承协议（PIP）很好地解决优先级反转问题。文章在对PIP协议进行分析的基础上，利用加权平均的思想，形成了加权平均PIP算法。它可以用来进行线程调度，改善系统的实时性。

加权平均值；PIP；线程调度；优先级反转

众所周知，Linux内核是由Linus Torvalds在1991年开发出来的，从那之后Linux操作系统以令人震惊的速度迅速在服务器和桌面系统中获得了成功。它已经被业界认为是未来最有前途的操作系统之一，特别是在嵌入式领域，由于Linux操作系统具有开放源代码、配备需求低廉、良好的可移植性、丰富的代码资源以及稳定性，越来越多受到业内人士关注。Linux系统具有较好的平均响应时间和较高的吞吐量，但是，实时系统需要重点关注任务的即时完成，尽量减少进程运行的不可预测性是一个非常困难的挑战性问题［1］［2］。

本文试图从加权平均PIP的角度来解决这个问题，先是分析优先级反转问题，再是阐述优先级继承协议，最后对PIP进行改善，提出了加权平均优先继承协议。

1　优先级继承协议

1.1优先级反转

优先级反转是指当一个高优先级任务访问共享资源时，该资源已被一个低优先级任务占有［3］［4］，而这个低优先级任务在访问共享资源时又可能被其它中优先级的任务抢占，造成高优先级任务被许多较低优先级任务阻塞，高优先级任务在低优先级任务之后运行，实时性得不到保证。

假设：系统内低优先级的任务task3占用着高优先级任务task1要使用的资源，任务task1只好等待任务task3执行完毕，并释放该资源后才能被调度执行。这时，如果有中优先级任务task2进入就绪，剥夺了任务task3的CPU使用权，使得系统只有先让task2运行完毕，且任务task3重新运行结束并释放资源后，任务task1才能运行。这样，任务task1和task2的优先级发生了颠倒。在这种情况下，高优先级任务的优先级已经降到了低优先级的水平，从而发生优先级反转现象，中优先级任务抢占低优先级任务。图1就是优先级反转的请况。

图1　优先级反转

1.2优先级继承协议

优先级反转让系统的行为难以预测，严重时会导致系统崩溃，是影响嵌人式Linux系统实时性的重要因素。解决优先级反转问题典型协议有优先级继承协议（priority inheritance protocol，PIP）。

优先级继承的基本思想是当低优先级任务占用资源，而高优先级任务也要访问此资源时，将低优先级任务的优先级提高到与高优先级同样的级别，以便于原来的低优先级任务获得更多资源（如CPU时间，内存等），尽快完成任务，释放所占用资源［5］。

假设：任务task1具有高优先级，任务task3具有低优先级。任务task3首先获得共享资源R，而任务task1也请求该资源，优先级继承协议要求任务task3以任务task1的优先级执行临界区。任务task3在执行临界区时，其优先级比它本身的优先级高，这时，中优先级的任务task2不能抢占任务task3，当任务task3退出临界区时，又恢复到原来的优先级，使任务task1仍为最高优先级的任务，这样，任务task1不会被中优先级的任务无限期阻塞了［6］。优先级继承情况如下图2所示：

图2　优先级继承

2　加权平均PIP

2.1加权平均优先继承协议

综合分析优先级继承协议，其具有如下特性：

1）优先级继承协议完美地解决了优先级反转的问题。

2）如果任务成功地获得了信号量，任务的优先级将被提升为它所占有的所有信号量的优先级最高的那个优先级。当任务使用完资源，释放信号量后，其优先级恢复到原先的优先级。

3）如果共享资源中断或对其操作时间相对较长，而一些高优先级任务对此共享资源的操作又不是必需的，让高优先级任务长时间阻塞会对实时系统造成很大的影响。

4）可能会造成死锁。假如：低优先级任务C获取资源R1，在执行过程中高优先级A抢占C并获取资源R2，A又申请资源R1被阻塞，C继承A优先级继续执行R1，此时C需要获取资源R2，死锁产生。如下图3所示：

图3　死锁

本文针对以上的问题，对PIP进行改善，在此基础上形成了加权平均优先继承协议。

加权平均PIP主要适用于Linux系统的线程或者进程调度。一个线程对应着多个任务，进程和线程都有自己的优先级，给每个线程分配一个相应的权值。求得其线程所有实时任务的平均优先级值，将权值和优先级值相乘。

若任务成功的获得了资源，则把该任务的优先级设置为所有想获取该资源的任务优先级的平均值，再将其线程的优先级设置成权值与优先级平均值的乘积。

2.2基于加权平均PIP的线程调度方法

1）当PIP用来进行线程调度的时候，可定义线程Ki的优先权prio（Ki）为实时任务集合Ri所有任务中最大的优先权：

当|Ri|=0，即没有实时任务时，Prio（Ki）则为默认的线程优先级，其优先级保持不变。若有实时任务，即if|Ri|≠0时，则把线程Ki的优先级设置为实时任务中优先级最大的，这就是PIP的思想。

在这种情况下，核心线程可以充分地利用cpu，但是其他的实时任务遭受不必要的执行延迟。因此，本文提出在选择线程时使用加权平均PIP.

2）用加权平均PIP进行线程调度

其中，rj属于Ri

当没有实时任务时，其就根据普通线程Ki的优先级执行任务。否则的话，其Wi为Ki的权值，其优先权平均值反映的是实时任务集合的请况，而权值反映的单个线程的特点。所以加权平均PIP则能改善PIP的不足。其算出来的优先级是被Ri优先级的最大值所约束，而不是打断去实时任务。

3）加权平均PIP进行kswapd线程调度的案例分析

线程调度过程中会遇到很多问题，最主要有四种线程会影响实时任务的执行。有IRQ线程and ksoftirqd线程，pdflush线程，kswapd线程，用户线程。单分析kswapd线程而言，kswapd线程丢出最近用的很少的页去维持空白页的数量，虽然帮助普通任务分配空白页，但是也造成了问题。例如，如果kswapd线程遭遇了长时间的延迟，则实时任务请求额外的页面时，必须回收用过的页面。为了解决这些问题，用加权平均PIP进行选择。

LRU缓存页就是kswapd实时任务中的元素，R非常复杂，因为其缓存页的数量太多了。缓存页被不同优先级的任务所享有。为了简化这个问题，我们就假定每个实时任务在LRU缓存中都占有相同的页数。

除了kswapd线程的权值，优先级的平均值之外，还要求出所有实时任务使用LRU缓存页的比率，用page_ratio表示。通过优先级的平均值乘以LRU缓存页的比率的积来改变线程的优先级。

其中r属R，K代表的是kswapd线程。

3　结束语

在Linux发展过程中，出现了很多的调度算法，优先级反转也得到了很好的解决，但仍存在相应不足。本文把加权平均PIP的想法应用到线程调度上，通过计算线程实时任务的平均值以及该线程的权值，来决定线程的优先权。加权平均PIP虽然暂时还没有大的应用，但是理论上是可行的。

［1］L.Sha，R.Rajkumar，J.P.Lehoczky.Priority Inheritance Protocols：An Approach to Real-TimeSynchronization，IEEE Trans.Computers，1990，pp.1175-1185.

［2］李伊.基于认知无线传感器网络的能效优化策略监测机制研究［J］.湖南邮电职业技术学院学报，2016（1）：10-14.

［3］李冠楠，李家春.基于杂交遗传算法的多处理器硬实时容错调度算法［J/OL］.计算机应用研究，2016（9）.http：// www.cnki.net/kcms/detail/51.1196.TP.20151028.1121.080. htm l.

［4］ZarandiH R，MottaghiMH.DFTS：a dynamic fault-tolerant scheduling for real-time tasks inmulticore processors［J］. Microprocessors&Microsystems，2014（1）：88-97.

［5］Pathan R M.Fault-tolerant and real-time scheduling for mixed-criticality systems［J］.Real-TimeSystems，2014（4）：509-547.

［6］孔凡风，朱永平.基于Zigbee技术无线传感器网络平台的设计与实现［J］.湖南邮电职业技术学院学报，2015（2）：16-19.

Linux thread schedulingmethod based on weighted average PIP

ZHANG Zhi-yuan
（Hunan Postand Telecommunication College，Changsha，Hunan，China410015）

In the Linux system，the problem ofpriority inversionmay cause systems to crash.Theexecution time of thehigh priority task cannotbepredicted because ofpriority inversion，and theuncertainty of the real-time system is increased.PIP（priority inheritance protocol）isagood solution to the priority inversion problem.In thispaper，the ideaofweighted average value，with PIP，formsaweighted average PIPalgorithm，which can be used for thread scheduling，improving the real-time performance of the system.

weighted average value；PIP；thread scheduling；priority inversion

10.3969/j.issn.2095-7661.2016.02.008】

TP316.81

A

2095-7661（2016）02-0026-03

2016-04-26

湖南省教育科学规划课题，课题批准号：xjk012czj016。

张治元（1970-），男，湖南澧县人，湖南邮电职业技术学院互联网工程系副教授，硕士，研究方向：智能控制。