一种基于比特表的实时多任务新调度算法

这种改进算法的关系在于把各任务划分为若干时间片，然后再根据实时性要求填入比特表中。根据比特表的设计方法，时隙间隔定为5ms，总时隙数为LCM（10/5，20/5，30/5）=6。把各中断级和时钟级任务运行时间的最大公约数定为时间片。即有如下计算公式：

T=GCD{Ti}

T为时间片，Ti为时钟级和中断级任务实时性要求，GCD（Greatest Common Divisor）求最大公约数，LCM（Lowest Common Multiple）求最小公倍数。

本例中的时间片T=GCD{0.5,1,2.5,1,5}=0.5ms。（假设时钟中断处理时间为0.5ms）。

时间片的分配，必须遵循以下原则：

①满足实时性要求；

②确保每一个时隙中所有分配的任务都必须完全运行；

③均衡考虑CPU对各任务的运行，优先考虑时钟级任务和中断级任务。

按上述原则，中断级任务分1个时间片，时钟级1分配2个时间片，时钟级2分配3个时间片，时钟级3分配1个时间片，时钟级4分配2个时间片，而将每个时隙剩余的时间分配给基本级任务。这样，即使是在系统最繁忙的时候也有一个时间片分配给基本级任务，从而弥补了比特表算法的不足。

综上所述，设计图1所示的比特表。

此比特表的时隙任务安排完全满足实时性要求。A任务每时隙运行1次，每时隙运行2个时间片。A任务每5ms运行1次。B任务每10ms运行1次，C任务每20ms运行1次。由此可以得到各任务的启动顺序及执行时间如图2所示。图2中，I表示时钟中断处理程序，它的优先级最高。A、B、C、D为时钟级任务，其中A的优先级较高。将I、A、B、C、D处理完后余下的时间留给基本级E。

2 程序设计值得注意的问题

在任务调度算法中，关键是如何确定就绪队列、任务控制数据块的数据结构和解决资源冲突。就绪队列指明了在某一时刻已就绪、可被执行的任务队列。在数据结构上通常可用位映像的方法来实现。如系统的最多任务为32个，可采用4个字节的每一位来对应人某个任务。若此位为“1”，则表明该任务就绪；若为“0”，则表明任务空闲。并且可规定低位所代表的任务优先级高于高位所指示的任务。

某个任务投入运行时需保护现场数据，这些数据都存入一个地址固定的数据存储区，称为任务控制数据块。需保护的内容应按应用程序的特点来决定。对于常用的MCS51系列的单片机来说，现场保护数据一般应包括PC、ACC、PSW、SP、DPTR等寄存器内容。任务控制数据块一般放在外部数据存储器内。为了查找方便，可以按任务号将各个任务数据块的首地址编成一个一维表格，表格的每行对应各任务数据块数据结构首地址，如图3所示。

在任务调度程序中，还应很好地解决资源的互斥问题，即保证不可共享的资源只被一个任务所访问。在RTCS中，各任务间并非完全隔绝，它们相互合作、相互竞争。例如，某系统中数据显示任务要定时显示某数据区的数据；数据计算任务也要在某种情况下计算、刷新此数据区内容。在这里，数据计算任务在运行时就不允许让显示任务中断计算任务；否则，有可能导致显示的数据不正确。解决资源竞争的方法往往是在主程序中设置一标志字节或标志位。例如，显示任务在运行时首先判断此标志，若发现计算任务尚未完成，则不做任何工作直接退出任务。

3 小结

RTCS中的实时性和并行性是非常重要的，但两者之间有一定的矛盾。完全实现在两大特性的重要手段就是，采用有效的任务调度算法程序来协调两者之间的矛盾，从而保证系统的实时性和并行性。在简单系统中，“按时间片循环”调度算法已能初步满足要求；但在较复杂和要求较高的系统中，这显然不满足需要。基于BitMap的调度算法能较好地满足比较复杂系统的要求，而对于前面讲到的系统中要求执行时间长、实时性要求较高的任务而言，单纯的BitMap算法无法满足要求，这个时候我们提出将比特表的时隙细分成时间片进行分配，这比BitMap按照任务进行分配的算法更能解决复