自制嵌入式实时操作系统

    返回首页    发表留言
本文作者:李德强
          第二节 调度算法
 
 

        调度算法是操作系统调度的核心内容,我们需要完成一个具有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即可。

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2020 问渠网

辽公网安备 21011302000146号

辽ICP备15013245号