自制嵌入式实时操作系统

        调度算法是操作系统调度的核心内容，我们需要完成一个具有32个优先级的调度策略，支持优先级抢占式调度算法。也就是说，具有较高优先级的任务将被操作系统优先执行，而具有较低优先级的任务将等待比自己优先级高的任务执行完毕、等待资源或主动休眠时才能获得执行权。采用优先级抢占式调度的算法，有利于嵌入式单片机的实时性。当较高优先级的任务需要执行时，系统将立即执行调度，运行高优先级任务。

        我们为操作系统预先设计32个优先级，因此操作系统最多支持32个并行任务，而具有相同优先级的任务将不被执行，也就是说不支持相同优先级的多个任务同时运行。当操作系统的调度心跳执行时，系统将从所有任务中，找到一个优先级最高的任务然后将其指定为当前需要执行的任务。为了找到一个优先级最高的任务，我们可以定义个uint32_t类型的变量名为优先级就绪队列，这个变量的每一个bit位表示一个优先级，因此这个变量可表示32个优先级调度任务。当某个任务需要执行时，这个任务优先级数值所对应就绪队列的bit位上置为1，而当这个任务等待资源或主动休眠时，将就绪队列的bit位上置为0。

        例如，系统中有两个任务A和B，任务A的优先级为7，任务B的优先级为23。优先级就绪队列的每一个bit位都是0，表示没有任务需要执行，这是操作系统没有任务需要执行，也就是说所有任务都处于休眠状态：

                 00000000 00000000 00000000 00000000

        而当任务B需要执行时，任务B的优先级为23，因此将优先级队列的第23个bit位置为1，这时操作系统从优先级队列的低位向高位依次查找到第一个为1的位置，也就找到了需要执行的任务优先级位23，于是将优先级位23的任务指定位当前执行任务开始执行：

                 00000000 10000000 00000000 00000000

        当任务A需要执行时，任务A的优先级位7，因此将优先级队列的第7个bit位置为1，这时操作系统从优先级队列的低位向高位依次查找到第一个为1的位置，也就找到了需要执行的任务优先级位7，于是将优先级位7的任务指定位当前执行任务开始执行：

                 00000000 10000000 00000000 10000000

        于是我们可以编写程序查找优先级队列中由低向高第一个位1出现的位置：

uint32_t pcb_ready = 0x800080;
int proi = -1;
for (int i = 0; i < 32; i++)
{
	if (pcb_ready >> i & 1)
	{
		proi = i;
		break;
	}
}	
printf("curr proi %d\n", proi);

        运行结果为7，表示当前需要运行的任务队列中，优先级最高的任务位7。

        这个优先级任务查找算法在操作系统运行的32个任务中的平均调度时间位O(32)。而我们希望在操作系统执行调度时，时间尽可能的少，尽量节省调度时间，而将运行时间交给任务执行。因此我们有必要优化优先级任务查找算法。好的做法时将0~31这32个优先级出现的全部可能列表，并指定一个bitmap来表示其第一个1出现的位置。但是32位可表示的数值范围为0～4294967295，如果将这些数值都做成bitmap的话占用的内存就太大了。但是我们可以将32位的bitmap分割成4个8位的bitmap，我们只需要执行在这4个bitmap中查找1出现的位置即可。于是我们定义一个8位的bitmap，表示第一个1出现的位置：

//记录优先级是0~255，第一个1的位置，也就是优先级位置
const uint8_t map_proi[256] = {
	/* 00 */ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	/* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
	/* END */
};

        于是，当操作系统执行调度算法时，就可以将32位的优先级队列中的4个8位变量中取出第一个1出现的位置，在8个bit位中取出优先级最高的任务所在位置，其时间复杂度位O(1)，从32位中取出优先级最高任务所在位置的时间复杂度位O(4)，其计算方法如下：

//任务就绪队列位图，bit位中为1表示已就绪，0表示未就绪
uint32_t pcb_ready_map = 0;

//内核中pcb，静态申请32个pcb
pcb_s pcbs[PROCESS_CNT] = {0};

//获取优先级最高的任务索引
uint32_t pcb_get_highest_prio(void)
{
	if (pcb_ready_map & 0xff)
	{
		return map_proi[pcb_ready_map & 0x00ff];
	}

	if (pcb_ready_map & 0xff00)
	{
		return map_proi[(pcb_ready_map & 0xff00) >> 8] + 8;
	}

	if ((pcb_ready_map & 0xff0000))
	{
		return map_proi[(pcb_ready_map & 0xff0000) >> 16] + 16;
	}

	return map_proi[(pcb_ready_map & 0xff000000) >> 24] + 24;
}

//获取优先级最高的任务
pcb_s *pcb_get_highest_pcb(void)
{
	return &pcbs[pcb_get_highest_prio()];
}

        这样，我们就优化了调度算法，从O(32)降低到O(4)，也就达到了操作系统调度时间尽量降低的目的。其核心思想是使用空间复杂度来换取时间复杂度。可以清楚的看到，这个算法较第一种算法的空间复杂度为多，这个算法的空间复杂度为S(256)。虽然空间复杂度提高了，但是时间复杂度却降低了，这在嵌入式实时操作系统中无疑是划算的。

        最后我们需要完成两个函数，用于任务的就绪状态的变更：

//将任务加入就绪队列
void pcb_ready(pcb_s *pcb)
{
	pcb_ready_map |= 1 << pcb->prio;
	pcb->status = PCB_ST_READ;
}

//将任务由就绪队列挂起
void pcb_block(pcb_s *pcb)
{
	pcb_ready_map &= ~(1 << pcb->prio);
	pcb->status = PCB_ST_BLOCK;
}

        将任务加入到就绪队列时，只需要将就绪队列中指定优先级的位置上置1即可；相反的，当任务由就绪变为休眠时，只需要将就绪队列中的位置上置0即可。