RT(RealTime scheduler)实时调度器，对应用户设定的调度策略为 SCHED_FIFO/SCHED_RR。
SCHED_FIFO 先进先出队列调度，高优先级任务一直运行，直到任务阻塞，或者主动退出，或者被更高优先级
任务抢占。
SCHED_RR 时间片轮转调度，每个实时任务划分一个时间片，时间片用完会切换到其他任务执行。




进程几种状态表示：


1.      TASK_RUNNING: 这里表示进程没有被阻塞，即READY和RUNNING的结合体。至于具体是READY还是 RUNNING，在需要的时候可以做如下判断：调度程序取得该进程的进程状态为TASK_RUNNING且其所在CPU的current_task就是该进程，则认定他是RUNNING，否则就是READY。需要做如上判断的情况其实并不多，所以统以TASK_RUNNING描述便已足够。


2.      TASK_INTERRUPTIBLE: 进程处于BLOCK状态且可以被SIGNAL唤醒


3.      TASK_UNINTERRUPTIBLE: 进程处于BLOCK状态但不能被SIGNAL唤醒


4.      TASK_ZOMBIE: 进程已经结束，但描述符还没有被回收。


5.      TASK_STOPPED: 进程停止运行。通常在收到SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU等信号时发生；或者在调试时收到任何信号都会发生。可向其发送SIGCONT使其继续运行。


task的状态记录在task_struct结构的state成员中。


调度程序每次从处于running状态的task中选择一个最合适的来运行。


RT调度器的核心是优先级队列，调度程序从最高优先级队列头部选择一个task运行，
调度结束会将任务放到对应的优先级队列尾部。
bitmap标示优先级，某个bit置1标示该优先级队列不为空。


struct rt_prio_array {
DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
struct list_head queue[MAX_RT_PRIO];

};

task入队操作：

/*
 * Adding/removing a task to/from a priority array:
 */
static void
enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
{
	struct sched_rt_entity *rt_se = &p->rt;

	if (flags & ENQUEUE_WAKEUP)
		rt_se->timeout = 0;

	//flag为0的话，将实体的run_list 加入优先级队列queue尾部，否则插入头部，优先调度。
	enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);

	//p不是当前rq正在运行进程，并且p可以在其他cpu上运行，就将p进入rq pushable_tasks，可以做负载均衡时使用，
	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
		enqueue_pushable_task(rq, p);

	inc_nr_running(rq);
	inc_hmp_sched_stats_rt(rq, p);
}
//先将实体所做task group删除队列，然后再依次入队列
static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
{
	dequeue_rt_stack(rt_se);
	for_each_sched_rt_entity(rt_se)
		__enqueue_rt_entity(rt_se, head);
}

static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
{
	struct sched_rt_entity *back = NULL;

	//从下往上遍历,支持task group
	for_each_sched_rt_entity(rt_se) {
		rt_se->back = back;
		back = rt_se;
	}

	//从上往下遍历，依次出队
	for (rt_se = back; rt_se; rt_se = rt_se->back) {
		if (on_rt_rq(rt_se))
			__dequeue_rt_entity(rt_se);
	}
}

static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);//实体所在rq
	struct rt_prio_array *array = &rt_rq->active; //优先级数组

	list_del_init(&rt_se->run_list);//list中删除实体
	if (list_empty(array->queue + rt_se_prio(rt_se)))//该实体所在优先级队列为空
		__clear_bit(rt_se_prio(rt_se), array->bitmap);//bitmap标识对应优先级queue 是否为空

	dec_rt_tasks(rt_se, rt_rq);
	if (!rt_rq->rt_nr_running)
		list_del_leaf_rt_rq(rt_rq);
}

//入队，调度实体加入对应优先级队列中
static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
{
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);//实体所在rq
	struct rt_prio_array *array = &rt_rq->active;//优先级数组
	struct rt_rq *group_rq = group_rt_rq(rt_se);//实体所属group
	struct list_head *queue = array->queue + rt_se_prio(rt_se);//优先级队列

	/*
	 * Don't enqueue the group if its throttled, or when empty.
	 * The latter is a consequence of the former when a child group
	 * get throttled and the current group doesn't have any other
	 * active members.
	 */
	if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
		return;

	if (!rt_rq->rt_nr_running)
		list_add_leaf_rt_rq(rt_rq);

	if (head)
		list_add(&rt_se->run_list, queue);
	else
		list_add_tail(&rt_se->run_list, queue);
	__set_bit(rt_se_prio(rt_se), array->bitmap);

	inc_rt_tasks(rt_se, rt_rq);
}

//出队操作，更新rq当前task 状态，实体出队，然后实体加入队列尾部
static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
{
	struct sched_rt_entity *rt_se = &p->rt;

	update_curr_rt(rq);
	dequeue_rt_entity(rt_se);

	dequeue_pushable_task(rq, p);

	dec_nr_running(rq);
	dec_hmp_sched_stats_rt(rq, p);
}

static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
	dequeue_rt_stack(rt_se); //先从运行队列删除调度实体

	for_each_sched_rt_entity(rt_se) {
		struct rt_rq *rt_rq = group_rt_rq(rt_se);

		if (rt_rq && rt_rq->rt_nr_running)
			__enqueue_rt_entity(rt_se, false);//将调度实体再重新加入队列尾部
	}
}

//RT调度器选择下个task过程：

static struct task_struct *pick_next_task_rt(struct rq *rq)
{
	struct task_struct *p = _pick_next_task_rt(rq);

	/* The running task is never eligible for pushing */
	//p接下来将开始运行，自然不需要再push到其他rq
	if (p)
		dequeue_pushable_task(rq, p);

#ifdef CONFIG_SMP
	/*
	 * We detect this state here so that we can avoid taking the RQ
	 * lock again later if there is no need to push
	 */
	rq->post_schedule = has_pushable_tasks(rq);
#endif

	return p;
}

static struct task_struct *_pick_next_task_rt(struct rq *rq)
{
	struct sched_rt_entity *rt_se;
	struct task_struct *p;
	struct rt_rq *rt_rq;

	rt_rq = &rq->rt;
	
	//TASK_RUNNIG 数目
	if (!rt_rq->rt_nr_running)
		return NULL;

	if (rt_rq_throttled(rt_rq))
		return NULL;

	do {//处理组调度，task group 父进程在子进程的后面
		rt_se = pick_next_rt_entity(rq, rt_rq);
		BUG_ON(!rt_se);
		rt_rq = group_rt_rq(rt_se);//实体在这个rq上
	} while (rt_rq);

	/*
	 * Force update of rq->clock_task in case we failed to do so in
	 * put_prev_task. A stale value can cause us to over-charge execution
	 * time to real-time task, that could trigger throttling unnecessarily
	 */
	if (rq->skip_clock_update > 0) {
		rq->skip_clock_update = 0;
		update_rq_clock(rq);
	}
	p = rt_task_of(rt_se);
	p->se.exec_start = rq_clock_task(rq);//rt优先级可能会调整为nice?

	return p;
}

//找个rq最高优先级队列第一个进程
static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
						   struct rt_rq *rt_rq)
{
	struct rt_prio_array *array = &rt_rq->active;
	struct sched_rt_entity *next = NULL;
	struct list_head *queue;
	int idx;
	//第一个为1的bit代表了优先级queue的idx
	idx = sched_find_first_bit(array->bitmap);
	BUG_ON(idx >= MAX_RT_PRIO);

	queue = array->queue + idx;
	next = list_entry(queue->next, struct sched_rt_entity, run_list);

	return next;
}