uC/OS-II学习笔记—空闲链表和就绪链表

咚咚卜

uC/OS-II将任务控制块分成两个链表来管理，这就是空闲任务链表和就绪任务链表。其中，空闲任务链表包含了所有空闲的任务控制块。所谓空闲任务控制块，是指未分配给某个任务的任务控制块。创建一个新任务，前提条件就是系统中还有这样的空闲任务块。就绪链表则是将所有的就绪任务拴在一起，如果有新的任务就绪，就要将其任务控制块从空闲链表中取出，加入到就绪链表中。
操作系统刚启动的时候，在没有执行主程序(Main)任何代码之前，只有任务控制块数组，还没有空闲任务链表和就绪任务链表，或者说这两个链表都空着。这两个链表是在操作系统的初始化程序OSInit中创建的。如下图所示为系统初始化程序OSInit执行后的空闲任务控制块链表。


如图可见，全局变量OSTCBFreeList指向的是空闲链表的表头，表尾的任务控制块的OSTCBNext指向的是空地址，也就是说，如果OSTCBFreeList指向的是空地址，就没有空闲的任务控制块，不能创建新的任务。
既然OSTCBFreeList是指向任务控制块的地址，定义如下：


就是这样，指向任务控制块的指针。因为它与硬件无关，所以在ucos_ii.h中定义。
如果OS_MAX_TASKS的值是14，也就是最多可以同时运行14个用户任务，系统任务数是2，那么内存中就有16个任务控制块，从OSTCBTbl[0]到OSTCBTbl[15]。在操作系统没有建立任何任务的时候，OSTCBFreeList指向OSTCBTbl[0], OSTCBTbl[0]的OSTCBNext指向OSTCBTbl[1]，依此类推。最后，OSTCBTbl[15]的OSTCBNext指向空地址。如果要创建一个新的任务，就根据OSTCBFreeList找到一个任务控制块。
当我们创建第一个任务即空闲任务的时候，就从空闲控制块链表中摘下一个任务控制块给这个任务。当然，这个控制块随即被插入就绪链表。很明显，在没有任务被创建的时候，就绪链表是空的。就绪链表的指针式OS_TCBList，它和OSTCBFreeList的定义方法是完全相同的：


第一个任务应该是空闲任务，如下图所示就是完成了这一操作后的空闲链表和就绪链表。


当创建第一个任务即空闲任务后，空闲链表和就绪链表如上图所示，这时可以清楚地看到就绪链表包含了OSTCBTbl[0]一个控制块，OSTCBList就只想这个任务控制块，而该控制块的前后指针都为0，即OSTCBNext=0,OSTCBPrev=0,表示前面和后面都没有了，就绪链表只有这一个块。比较一下，空闲链表的指针OSTCBFreeList现在指向OSTCBTbl[1]了，空闲链表比原来少了一个控制块，OSTCBTbl[0]被分配了。
创建一个任务的过程，首先应该查看OSTCBFreeList，看它是否为0，如果为0，说明没有空闲的任务控制块可以分配了，于是不能创建新的任务。如果不是0，就将OSTCBFreeList指向的那个任务控制块分配给新的任务，将这个控制块移动到就绪链表，并将OSTCBFreeList指向原来的空闲链表中的下一个任务控制块。
那么，如何将任务控制块移动到就绪链表呢？是插入到表头还是表尾呢？
在上图的基础上我们在创建一个任务——统计任务。需要再从空闲链表中移出一个任务控制块到就绪链表中，结果如下图所示：

当再创建一个任务即统计任务后，OSTCBFreeList所指向的任务控制块OSTCBTbl[1]就被分配给这个任务，OSTCBFreeList就指向了OSTCBTbl[2]。形成如上图所示的右半部分新的空闲链表。uC/OS-II将这个OSTCBTbl[2]插入就绪链表，方法是把它放在表头而不是表尾，于是形成了如图所示的左半部分新的就绪链表，原来在这个链表中OSTCBTbl[0]就到了表尾。这时候，OS_TCBList不再指向OSTCBTbl[0]，而是指向OSTCBTbl[1]。需要注意的是，就绪链表是双向链表，而空闲链表只是一个单项链表，从图中很容易分辨这一点。
从图中可以清楚地看出，OSTCBFreeList永远指向空闲链表的表头，如果它为0，说明没有空闲任务控制块了；OSTCBList永远指向就绪链表的表头，如果它为0，说明没有就绪的任务了。