uCOS任务调度算法思路#

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

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

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

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

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

位图法详解#

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

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

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

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

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[]**的每一个可能的数字，其最低有效位都是固定可知的，将这些有限的数据记录成一张查找表，就可以直接找到最低有效位。

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

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

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

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

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

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

任务在何时进行切换？

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

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

每次进行Tick时，进入SysTickHandler，将delay的任务的Timedly计时减少。如果Timedly时间到了，就进入了就绪的状态。
一个外部中断到来，带来的某一个任务所需要的资源，不过是以事件的形式进行表示，比如释放一个semaphore。
一个事件到来，会将等待这个事件的任务置为就绪状态。

就绪状态更新完成之后，在何时唤起PendSV?

首先想到的就是自然的任务切换，也就是在SystickHandler中。这是一个自然的任务调度，保证最高优先级的任务运行结束之后其他任务得到调度
其次就是外部中断结束之后，查看是否有带来任务所需要的资源，是否有将某个任务置为就绪。这是一个外部中断触发的调度，完成中断之后要立即进行一次任务的调度，以保证实时性

上述两种唤起PendSV也并不是直接就进行任务的切换，而是在中断结束时确保没有中断嵌套，并且对PendSV中断进行置位。

在进入ISR时会调用OSIntEnter()退出ISR时会调用OSIntExit()，二者除了对中断嵌套进行记录进行操作等等，在**OSIntExit()**中还会进行新任务的调度，并且进行置位准备调用PendSV中断。