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

1 比特表的改进算法

这种改进算法的关系在于把各任务划分为若干时间片，然后再根据实时性要求填入比特表中。根据比特表的设计方法，时隙间隔定为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次