uCOS II 系列文章之查找最高优先级任务

预计阅读时间： 5分钟

我们知道在 u/COS II 中，一个任务只有一个优先级，并且这个优先级在整个系统是唯一的，也就是一个任务也是对应一个优先级。优先级即任务，任务即优先级。我们只需通过优先级就可以找到所有和该任务相关的资源。现在问题是就绪表中有那么多任务处于就绪态，如何从中找到其中最高优先级。方法有很多，其中一个就是 for 循环找优先级，遍历所有就绪表，从中找到最高优先级，但这里有一个问题，如果就绪表中处于就绪的这个优先级比较低，那么搜索时间肯定比在高优先级的情况下搜索时间长，这就不符合系统运行时间是确定的要求。所以 u/COS II 采用了空间换时间的方法，事先将一个字节的所有情况记录下来，然后从中找就行了。这就是 OSUnMapTbl[256]。

[img=360.5185pt,346.5178pt]http://www.embed.cc/bbs/source/plugin/csdn123_news/display_picture.php?url=https%3A%2F%2Fmmbiz.qpic.cn%2Fmmbiz_png%2FfpA42W9rbq6cutNjnqT45nnMDgNECrb19kz6c7cCNcmgGFZYGibdI2ZYVGuNLCx7UaMhP5sPwkAe1UmJAvyzSGg%2F640%3Fwx_fmt%3Dpng[/img]

这张表的功能只有一个，就是记录一个字节中哪一 bit 先置 1（从右往左数），比如一个字节是 0x21，二进制表示 0010 0001 b，那好，就用这个值作为查表的索引。OSUnMapTbl[0x21]就是 0，也就是 bit 0 位先置 1，不信，自己查去。我们不禁会想，需要查表吗，这不是很明显的是吗，直接看二进制就知道了啊，但是机器没我们聪明，他可没有办法进行图像处理，所以只好采用这种办法笨办法找了（在 CM3 中有一条指令可以实现找前导 0 的，这样就能最少节省 256 字节空间了，为啥是 256, 一个字节 8 位，每位两种可能，0、1，256 字节包含了所有可能）。现在我们看在 8*8 的就绪表如何进行查找。

[img=379.51953pt,57.50299pt]http://www.embed.cc/bbs/source/plugin/csdn123_news/display_picture.php?url=https%3A%2F%2Fmmbiz.qpic.cn%2Fmmbiz_png%2FfpA42W9rbq6cutNjnqT45nnMDgNECrb1gUDYicIdLcDl635XX7uxeghuyyHibsiaiafazw8icKia2jIuibnE0b2gLUlZw%2F640%3Fwx_fmt%3Dpng[/img]

是不是很清爽，执行时间也是确定的，符合要求。

这里有一个局部变量 y，还有之前讲的就绪组变量 OSRdyGrp。在每一次就绪表操作后，也会同步更新 OSRdyGrp。这里记录了一个组中是否有任务处于就绪，只要有就绪任务，相应位置置 1。操作后如果发下该组值为 0 ，也就是该组没有任务，就会将 OSRdyGrp 相应 bit 位清零。

[img=306.51575pt,46.00236pt]http://www.embed.cc/bbs/source/plugin/csdn123_news/display_picture.php?url=https%3A%2F%2Fmmbiz.qpic.cn%2Fmmbiz_png%2FfpA42W9rbq6cutNjnqT45nnMDgNECrb15ib9mcgORsXVf0uEAzKoSYHlsQ8nzNXwccBwnmSUSkJbQfJ6sFP7FYg%2F640%3Fwx_fmt%3Dpng[/img]

从 OSRdyGrp = 0x69 值可以发现组号 0、3、5、6 共四组有任务处于就绪态，但是每一组有多少任务处于就绪态不确定，但是该组最少有一个任务处于就绪态（结合就绪表理解）。现在需要确定这些组的最高优先级组（先确定组号是最小，如果组号是最小，那么这个组计算出的优先级肯定比其他组优先级高），就绪组值为 0110 1001b，十六进制 69H，十进制表示 105, 可根据十进制在 OSUnMapTbl 找到索引值 105 的值为 0（从 0 开始计数），

也就是说最高优先级为 0 组，也可根据十六进制，高 4 位是 6，从 OSUnMapTbl 表找 6 行(0x60 to 0x6F), 低 4 位是 9，找 9 列（从 0 开始计数），也可以从表中看出值为 0 ，而事实上由于 bit 0 置 1，所以最高优先级组肯定是 0 组，由此我们可以从表中观察出只要是奇数，最高优先级组肯定是 0 组，因为它的最低位肯定置 1，即奇数，即 0 组有任务处于就绪态。既然 0 组有就绪态，那么不管还有哪些组处于就绪，都不可能比 0 组更高优先（0 组是最高优先组），所以只要是奇数，最高优先级组都是 0 组，即表中的值为 0。 在得到最高优先组的基础上通过 OSUnMapTbl 获得该组的最高优先级任务。同理，也是通过该索引表获得一个字节的最先置 1 的位置，可以获得一个任务优先级的列号，再和之前的组号组合，就可唯一确定一个任务，并且因为组号也是最高优先组，所以该任务的优先级是所有就绪态任务中的最高优先级。

我们再简单看一下 16*16 位就绪表的情况：

[img=415.3pt,197.89236pt]http://www.embed.cc/bbs/source/plugin/csdn123_news/display_picture.php?url=https%3A%2F%2Fmmbiz.qpic.cn%2Fmmbiz_png%2FfpA42W9rbq6cutNjnqT45nnMDgNECrb1ru8HfxdyqNiawe7YQ6jib7erUb5NzqBmVgY7cbbvNpMV0DTEuLzaxnUA%2F640%3Fwx_fmt%3Dpng[/img]

因为变量位数不一样，更重要的是为了节省空间（如果是 16 位变量，直接按索引值得话需要 65536 个字节空间大小），所以采用判断方式节省了空间，使 256 个字节就可以获得需要的组号，效率上只比直接索引多了一个判断时间，可以说是非常划算的。可以看到它首先判断低 8 位情况，如果存在就绪组，就从中获得最高优先组，高 8 位就可以不管了，因为运算目标只有一个，就是从所有就绪组中获得一个最高就绪组，既然最低 8 位有就绪组，那最高就绪组肯定就在其中，不可能在高 8 位；如果不在低 8 位，那就继续找高 8 位，因为已经确定了不在低 8 位，即不可能是 0-7 组，所以需要进行偏移，偏移值为 8，所以如果最高 8 位有 bit 置 1，肯定是 8 < y < 15。这样就获得了一个 16 位变量的所有可能置 1 的位置。需要说明一点的是因为就绪表一行有 16 个任务，所以组号需要 *16，采用位运算效率更高，这里右移 4 位即 *16。注意位运算不能乱用，否则会导致错误。

总结：该表用于确定一个字节的最先置 1 的位置，如果 OSRdyGrp 所有位都没置 1，说明没有就绪态任务，但是这种情况在 UCOS II 中不会出现，因为必定有系统任务处于就绪态。利用该思想，我们为了节省空间，也可以做成 4*4 的索引表，但这样会影响效率，如果任务数少又想节省空间的话可以修改该表。

-THE END-

如果觉得文章对你有帮助，欢迎转发、分享给朋友，感谢你的支持！

微信公众号「鱼鹰谈单片机」

每周一更单片机知识

长按后识别图中二维码关注

  如果对你有帮助，在这里点个好看再走呗