uCOS任务调度算法思路

这里介绍uCOS最重要的任务调度算法：优先级位图法。

首先明确，uCOS中每一个任务都有唯一的优先级，也就是说一个优先级就能直接确定一个任务。

对于第一个要求，只要有一个数据结构来存储就绪的状态即可，例如数组。

对于第二个要求，对一个实时性比较高的操作系统来说，是不容易实现的。如果使用数组的数据结构，那么寻找最高优先级的就绪任务就需要遍历数组，显然速度很慢。如果任务比较少，可以允许遍历。但是一旦任务数量多起来，甚至说支持256个任务时，显然就不可能遍历了。

这里引入uCOS的优先级位图法，以64个优先级为例。

位图法详解

64个优先级分为两层查找，做一个8*8的数组。

第一层用一个字节表示，也就是OSRdyGrp，这个字节哪个位置上是1，就代表哪一行有就绪任务。

第二层是找到的某一行，也是用一个字节表示，**OSRdyTbl[]**，这个字节哪个位置上是1，就代表这一行的那一个是就绪任务。

现在创建一个优先级为15的任务。因为分了两层，并且第一层的索引是8个，所以15这个数字的最低三位表示这个任务在那一行的位置，次三位表示这个任务所在的行。

1
2
3

int prio = 15;
x = prio & 0x07; //获得在一行的哪一个位置
y = prio >> 3; //获得在哪一行

但是此时只是得到了两个数字，而不是两层索引。现在要把y = 1变成00000010的表示，并且将这个二进制数和OSRdyGrp结合起来，就达到了我们的目的。

uCOS引入了一个查找表，**OSMapTbl[]**。下标为1时，元素为00000010，同样的下标为7时，元素为10000000。

int prio = 15;
int x = OSMapTbl[prio & 0x07];
int y = OSMapTbl[prio >> 3];
OSRdyGrp |= y;
OSRdyTbl[y] = x;
//在实际的代码中，就不需要x和y了，直接进行或运算即可

因为有两层的位图索引，所以只要找到OSRdyGrp中的最低有效位，就能知道是哪一行，然后在对应的行**OSRdyTbl[]**中寻找最低有效位，就能找到是哪一列，结合起来就是最高优先级了。但是这样去直接在这两个字节中寻找，依然需要非常数级别的时间。有没有什么办法减少这个时间呢？

uCOS又引入了一个查找表OSUnMapTbl[]。对于OSRdyGrp或者**OSRdyTbl[]**的每一个可能的数字，其最低有效位都是固定可知的，将这些有限的数据记录成一张查找表，就可以直接找到最低有效位。

1
2
3

y = OSUnMapTbl[OSRdyGrp];
x = OSUnMapTbl[OSRdyTbl[y]];
prio = y * 8 + x;

可以看到在寻找最低有效位时不能保证实时性，所以引入了优先级位图法的额外查找表。

虽然在两层索引中，寻找最低有效位的时间是有限的，查找两个字节，也就是顶多16次查找，但是对实时操作系统来时可能还是难以容忍。

在TLSF内存管理算法中得到了一点启示，使用CLZ硬件指令得到最高有效位，这个操作是一个硬件电路实现的指令，其复杂度可以认为是常数级别。

硬件实现某种操作，降低复杂度，耦合软件与硬件带来更好的性能，和更低的编程门槛。

虽然说优先级位图法的查找表带来了额外空间，但是对一个任务数量本身就有限的嵌入式操作系统来说，这个查找表的大小也并没有很大，最终认为，软件上的巧妙实现是更加优秀的。

任务在何时进行切换？

首先考虑什么情况下任务不会位于就绪状态：

那么何时对就绪状态进行更新呢？

每次进行Tick时，进入SysTickHandler，将delay的任务的Timedly计时减少。如果Timedly时间到了，就进入了就绪的状态。