嵌入式实时操作系统的设计与开发（调度策略学习）

将调度分为两层，上层为策略，下层为机制，并且采用策略与机制分离的设计原则，可以方便灵活地扩展调度策略，而不改变底层的调度机制。

调度策略就是如何确定线程的CPU、优先级prio等参数，线程是按照FIFO，还是分时策略来调度。对某些线程要特殊调度处理，然后根据相应操作来初始化线程。一种策略就对应一种线程。

线程调度分层结构

调度策略本质就是调度算法，即确定任务执行顺序的规则，调度策略目前包括通用策略、分时策略、周期策略和RM策略，用户还可以自行扩展新的调度策略。

用户创建线程时，需要指定某种调度策略，并找到该调度策略对应的策略控制块，再为TCB成员赋值。

调度策略分类

1. 普通线程（通用策略创建的线程）。这种线程，需要人为指定CPU、优先级信息，通过acoral_create_thread创建。
2. 分时线程（分时策略创建的线程）。aCoral支持相同优先级的线程，对于相同优先级的线程，默认采用FIFO的方式调度，因此，当用户需要以分时的方式和其他线程共享CPU资源时，可以将该线程设置为分时线程。若用分时调度策略创建线程，应注意以下两点：
   （1）只存在相同优先级的分时策略，不同优先级线程之间不存在所谓的分时策略，它们是按优先级抢占策略来调度的。
   （2）必须都是分时线程。
3. 周期线程（周期策略创建的线程）。这种线程需要每隔一个固定时间就要执行一次，如信号采集系统有一个采样周期，每隔一段时间就要采集一路信号。
4. RM线程（RM策略创建的线程）。RM是一种可以满足任务截止时间的强实时调度算法，这种策略需要周期性线程策略支持。在配置成支持RM的线程策略，就必须同时配置支持周期性策略。
5. POSIX线程（POSIX策略创建的线程）。POSIX线程属于非实时线程，也是一个标准，这类线程的主要特点是越公平越好。让aCoral支持POSIX标准有两个出发点，一是实现最大公平，二是实现POSIX标准。为了实现最大公平，这种线程又有了一个自己的调度算法：电梯调度算法。

描述调度策略

typedef struct{
	acoral_list_t list; //策略链表结点，用于将策略挂到策略链表上去，用于把各个调度策略串到一个链表上，创建线程找策略的时候去这个链表上，根据策略名找，有几个策略就有几个结点
	acoral_u8 type; //策略类型，比如COMM
	_id (*policy_thread_init)(acoral_thread_t *, void (*route)(void *args), void *,void *); //策略线程初始化函数，用于确定线程的CPU、优先级等参数。
	void (*policy_thread_release)(acoral_thread_t *); //某种策略的释放函数，用于消灭线程时调用
	void (*delay_deal)(void); //与延时相关的处理函数，如period、slice等策略都要用到类似的延时机制。
	char *name; //用于传递某种调度策略所需要的参数。每种策略对应一种数据结构，用来保存线程的参数，比如普通策略的参数只有CPU、prio。
}acoral_sched_policy_t;
1
2
3
4
5
6
7
8

//普通线程调度相关的数据
typedef struct{
	unsigned char prio; 
	unsigned char prio_type; //优先级类型，有BASE_PRIO，根据系统需要在创建线程时进行调整；ABSOLUTE，表示优先级设定是多少就多少
}comm_policy_data_t
1
2
3
4
5

//周期策略数据块
typedef struct{
	unsigned char prio;
	unsigned char prio_type;
	unsigned int time;//线程周期，单位毫秒
}period_polciy_data_t;
1
2
3
4
5
6

查找调度策略

当用户想根据某种调度策略创建线程时，须根据TCB的policy成员值从策略控制块链表中查找相应的结点，将信息取出赋值给TCB成员。

acoral_list_t policy_list;
acoral_sched_policy_t *acoral_get_policy_ctrl(unsigned char type){
	acoral_list_t *tmp,*head;
	acoral_sched_policy_t *policy_ctrl;
	head = &policy_list;
	tmp = head;
	for(tmp=head->next;tmp!=head;tmp=tmp->next)
	{
		policy_ctrl = list_entry(tmp,acoral_sched_policy_t,list);
		if(policy_ctrl->type == type)
			return policy_ctrl;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

当创建一个结构体变量时，该结构体变量在内存中会占据一段连续的内存空间，每个成员变量都在这个内存块中有自己的地址偏移。

结构体指针实际上是一个执行结构体内存块起始地址的指针。通过这个指针，可以访问结构体内存块中的各个成员变量。

1. 内存布局：结构体的成员变量在内存中是按照它们在结构体定义中的顺序排列的，成员变量之间是连续存储的。
2. 操作符->，结构体指针用->来访问结构体成员

struct Point{
	int x;
	int y;
};

struct Point p1;
struct Point *ptr = &p1;

ptr->x = 10;
ptr->y = 20;

p1.x = 5;
p1.y = 15;
1
2
3
4
5
6
7
8
9
10
11
12
13

注册调度策略

若要扩展新的调度策略并且生效，须进行注册，只有注册后，用户才能通过此策略创建特定类型的线程。
注册就是将用户自己定义的调度策略挂载到策略控制链表上，放在队尾。

void acoral_register_sched_policy(acoral_sched_policy_t *policy){
	acoral_list_add2_tail(&policy->list, &policy_list);
}
1
2
3

通用调度策略是在什么时候注册的呢？
在进行通用调度策略初始化comm_policy_init()时注册

acoral_sched_policy_t comm_policy;
void comm_policy_init()
{
	comm_policy.type = ACORAL_SCHED_POLICY_COMM;
	comm_policy.policy_thread_init = comm_policy_thread_init;
	comm_policy.policy_thread_release = NULL;
	comm_policy.delay_deal = NULL;
	comm_policy.name = "comm";
	acoral_register_ched_policy(&comm_policy);
}
1
2
3
4
5
6
7
8
9
10

acoral_list_t period_delay_queue; //周期线程专用延时队列，只要是周期线程，就会被挂载到这个队列上，延时时间就是周期，每次周期过后重新挂载
acoral_sched_policy_t period_policy;
void period_policy_init(void)
{
	acoral_init_list(&period_delay_queue);
	period_policy.type=ACORAL_SCHED_POLICY_PERIOD;
	period_policy.policy_thread_init=period_policy_thread_init;
	period_policy.policy_thread_release=period_policy_thread_release;
	period_policy.delay_deal=period_delay_deal;
	period_policy.name="period";
	acoral_register_sched_policy(&period_policy);
}
1
2
3
4
5
6
7
8
9
10
11
12

通用调度策略初始化又是在什么时候被调用的呢？

void sched_policy_init()
{
	acoral_init_list(&policy_list);
	comm_policy_init();
#ifdef CFG_THRD_PERIOD
	period_policy_init();
#endif
}
1
2
3
4
5
6
7
8

void acoral_thread_sys_init()
{
	acoral_sched_mechanism_init();
	acoral_sched_policy_init();
}
1
2
3
4
5

void acoral_sched_machanism_init()
{
	acoral_thread_pool_init();
	acoral_thread_runqueue_init();
	acoral_init_list(&acoral_threads_queue); //全局所有线程队列
}
1
2
3
4
5
6

acoral_pool_ctr_ acoral_thread_pool_ctrl;
void acoral_thread_pool_init()
{
	acoral_thread_pool_ctrl.type = ACORAL_RES_THREAD;
	acoral_thread_pool_ctrl.size = sizeof(acoral_thread_t);
	if(CFG_MAX_THREAD > 20)
		acoral_thread_pool_ctrl.num_per_pool = 20;
	else
		acoral_thread_pool_ctrl.num_per_pool = CFG_MAX_THREAD;
	acoral_thread_pool_ctrl.max_pools = CFG_MAX_THREAD/acoral_thread_pool_ctrl.num_per_pool;
	acoral_pool_ctrl_init(&acoral_thread_pool_ctrl);
}
1
2
3
4
5
6
7
8
9
10
11
12

void acoral_pool_ctrl_init(acoral_pool_ctrl_t *pool_ctrl)
{
	unsigned int size;
	pool_ctrl->free_pools = &pool_ctrl->list[0];
	pool_ctrl->pools = &pool_ctrl->list[1];
	pool_ctrl->num = 0;
	acoral_init_list(pool_ctrl->pools);
	acoral_init_list(pool_ctrl->free_pools);
	//调整pool的对象个数最大化利用分配了的内存
	size = acoral_malloc_adjust_size(pool_ctrl->size * pool_ctrl->num_per_pool);
	if (size < pool_ctrl->size)
	{
		pool_ctrl->num_per_pool = 0;
	}
	else
	{
		pool_ctrl->num_per_pool = size / pool_ctrl->size;
		acoral_create_pool(pool_ctrl); // 先创建一个资源池，后面如果一个池子不够了，那在不超过这类资源的max_pool的条件下再创建新的池子
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void acoral_thread_runqueue_init()
{
	acoral_rdy_queue_t *rdy_queue;
	rdy_queue = &acoral_ready_queues;
	acoral_prio_queue_init(rdy_queue);
}
1
2
3
4
5
6