嵌入式Linux系统实时进程调度算法改进之二 微软雅黑, 嵌入式, Linux

pengpengpang

　3.3　链表定义


　　整个调度算法可以用双链表来描述，即两级队列，分别用两个指针指向。最初，这两部分的头指针都指向“0”，表明这两个队列均为空。其中实时进程的就绪等待队列用一个循环单链表完成。

　　开始时的一级队列，是新到的比当前运行进程优先级低的实时进程。如果一个进程由于时间片到时或被更高优先级任务抢占，根据它的优先级将其插入到第二级队列。

　　若当前进程的时间片到时，CPU便选择当前队列中第二个节点的进程来判断，如果它的紧迫度大于1的话，说明这个进程在规定时间内不能完成，它必定夭折，将其放入普通进程队列中，再选择链表的第三个节点判断，如果紧迫度小于等于1便运行它，情况如图１所示。

                                                                   图1　优化后调度算法的实时进程优先级表

　　当一级队列为空时，二级队列便升成一级队列。

　　普通进程的调度通过单链表来实现。如果新来的进程属于普通进程，则根据优先级高低插入普通队列。只有实时队列（一级和二级队列）为空时，普通队列才能被调度。

　　3.4　实时进程的调度策略算法描述


　　1）实时就绪队列的初始化



　　2） 实时进程接收策略


　　#define K 10

　　void* pnow；

　　pnew指向新来的实时进程，pnow指向当前运行的实时进程。



　　3）实时进程插入策略



　　说明：根据传来的h值，决定在一级队列h的值是Headl时还是在二级队列h的值是Head2时中查找插入的合适位置。


　　当P是新来的任务时，h的值是Head1，p被括入一级队列。p2是p1的后继节点。在循环体中，当新来的进程P高于一级队列的进程p2时，停止循环，将P插入到p1的后面；当p1等于Head2时，说明一级队列的节点的优先级都比P节点的高，停止循环，把P插在p1的后面，则该节点便成了一级队列的末尾。

　　当P是被抢占的任务时，h的值是Head2，p被插入二级队列。在循环体中，当P的优先级高于二级队列的进程p2时，停止循环，将P插入到p1的后面；如果P高于二级队列的所有进程时，也会在p2指向Head时，因（*p）.w<=（*p2） .w而停止，则该节点便成了二级队列的末尾。因为（（head1）.w=-1，而任何进程的优先级数都不会小于1因此当p1，p2在这二级队列中遍历时，一定能有机会停止。

　　4） 调度等待链表中的一级队列


　　当前进程完成或时间片到时，调度等待链表中的一级队列中最前面的实时进程：



　　5）实时进程删除策略


　　针对目前Linux实时系统调度算法中仅用进程的价值来确定优先级的现象，本文提出了综合考虑进程的重要性和紧迫度来决定优先级的调度算法。算法将进程的截止期和价值两个不相关的概念，通过公式结合在一起，用来计算就绪等待队列中进程的优先级数。


　　该算法通过双链表来实现。在CPU正常负载的情况下，优化后的调度算法体现了更优的实时性能。