2011-12-22 11:17:48 russell_tao 阅读数 10546
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9157 人正在学习 去看看 CSDN讲师

为什么要了解内核的调度策略呢?呵呵,因为它值得我们学习,不算是废话吧。内核调度程序很先进很强大,管理你的LINUX上跑的大量的乱七八糟的进程,同时还保持着对用户操作的高灵敏响应,如果可能,为什么不把这种思想放到自己的应用程序里呢?或者,有没有可能更好的实现自己的应用,使得操作系统能够以自己的意志来分配资源给自己的进程?



带着这两个问题来看看KERNEL。首先回顾上我们开发应用程序,基本上就两种类型,1、IO消耗型:比如hadoop上的trunk服务,很明显它的消耗主要在IO上,包括网络IO磁盘IO等等。2、CPU消耗型,比如mapreduce或者其他的需要对大量数据进行计算处理的组件,就象对高清视频压缩成适合手机观看分辨率的进程,他们的消耗主要在CPU上。当两类进程都在一台SERVER上运行时,操作系统会如何调度它们呢?现在的服务器都是SMP多核的,那么一个进程在多CPU时会来回切换吗?如果我有一个程序,既有IO消耗又有CPU消耗,怎么让多核更好的调度我的程序呢?


又多了几个问题。来看看内核调度程序吧,我们先从它的优先队列谈起吧。调度程序代码就在内核源码的kernel/sched.c的schedule函数中。
首先看下面的优先级队列,每一个runqueue都有。runqueue是什么?下面会详细说下,现在大家可以理解为,内核为每一颗CPU分配了一个runqueue,用于维护这颗CPU可以运行的进程。runqueue里,有几个成员是prio_array类型,这个东东就是优先队列,先看看它的定义:
struct prio_array {
	unsigned int nr_active;    表示等待执行的进程总数
	unsigned long bitmap[BITMAP_SIZE];    一个unsigned long在内核中只有32位哈,大家要跟64位OS上的C程序中的long区分开,那个是64位的。那么这个bitmap是干什么的呢?它是用位的方式,表示某个优先级上有没有待处理的队列,是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级,我只需要四位就能表示某个优先级上有没有进程要运行,例如优先级是2和3上有进程,那么就应该是0110.......非常省空间,效率也快,不是吗?
	struct list_head queue[MAX_PRIO];     与上面的bitmap是对应的,它存储所有等待运行的进程。
};


看看BITMAP_SIZE是怎么算出来的:#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
那么,LINUX默认配置(如果你用默认选项编译内核的话)MAX_PRIO是140,就是说一共内核对进程一共定义了140种优先级。等待某个CPU来处理的进程中,可能包含许多种优先级的进程,但,LINUX是个抢占式调度算法的操作系统,就是说,需要调度时一定是找到最高优先级的进程执行。上面的BITMAP_SIZE值根据MAX_PRIO算出来为5,那么bitmap实际是32*5=160位,这样就包含了MAX_PRIO的140位。优先级队列是怎么使用的?看2649行代码:idx = sched_find_first_bit(array->bitmap);这个方法就用来快速的找到优先级最高的队列。看看它的实现可以方便我们理解这个优先级位的设计:
static inline int sched_find_first_bit(unsigned long *b)
{
	if (unlikely(b[0]))
		return __ffs(b[0]);
	if (unlikely(b[1]))
		return __ffs(b[1]) + 32;
	if (unlikely(b[2]))
		return __ffs(b[2]) + 64;
	if (b[3])
		return __ffs(b[3]) + 96;
	return __ffs(b[4]) + 128;
}

那么__ffs是干什么的?
static inline int __ffs(int x)
{
	int r = 0;

	if (!x)
		return 0;
	if (!(x & 0xffff)) {
		x >>= 16;
		r += 16;
	}
	if (!(x & 0xff)) {
		x >>= 8;
		r += 8;
	}
	if (!(x & 0xf)) {
		x >>= 4;
		r += 4;
	}
	if (!(x & 3)) {
		x >>= 2;
		r += 2;
	}
	if (!(x & 1)) {
		x >>= 1;
		r += 1;
	}
	return r;
}

sched_find_first_bit返回值就是最高优先级所在队列的序号,与queue是对应使用的哈,queue = array->queue + idx;这样就取到了要处理的进程队列。这个设计在查找优先级时是非常快的,非常值得我们学习。


好,优先级队列搞明白了,现在来看看runqueue,每个runqueue包含三个优先级队列。
struct runqueue {
	spinlock_t lock;   这是个自旋锁,nginx里解决惊群现象时也是用这个。与普通锁的区别就是,使用普通锁时,你去试图拿一把锁,结果发现已经被别人拿走了,你就在那睡觉,等别人锁用完了叫你起来。所以如果有一个人拿住锁了,一百个人都在门前睡觉等。当之前的人用完锁回来后,会叫醒所有100个等锁的人,然后这些人开始互相抢,抢到的人拿锁进去,其他的人继续等。自旋锁不同,当他去拿锁发现锁被别人拿走了,他在那不睡觉的等,稍打个盹就看看自己主动看看锁有没有还回来。大家比较出优劣了吗?


	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
	unsigned long nr_running;
#ifdef CONFIG_SMP
	unsigned long cpu_load;
#endif
	unsigned long long nr_switches;


	/*
	 * This is part of a global counter where only the total sum
	 * over all CPUs matters. A task can increase this counter on
	 * one CPU and if it got migrated afterwards it may decrease
	 * it on another CPU. Always updated under the runqueue lock:
	 */
	unsigned long nr_uninterruptible;


	unsigned long expired_timestamp;
	unsigned long long timestamp_last_tick;
	task_t *curr, *idle;
	struct mm_struct *prev_mm;
	prio_array_t *active, *expired, arrays[2];上面说了半天的优先级队列在这里,但是在runqueue里,为什么不只一个呢?这个在下面讲。
	int best_expired_prio;
	atomic_t nr_iowait;
	... ...
};

LINUX是一个时间多路复用的系统,就是说,通过把CPU执行时间分成许多片,再分配给进程们使用,造成即使单CPU系统,也貌似允许多个任务在同时执行。那么,时间片大小假设为100ms,过短过长,过长了有些不灵敏,过短了,连切换进程时可能都要消耗几毫秒的时间。分给100个进程执行,在所有进程都用完自己的时间片后,需要重新给所有的进程重新分配时间片,怎么分配呢?for循环遍历所有的run状态进程,重设时间片?这个性能无法容忍!太慢了,跟当前系统进程数相关。那么2.6内核怎么做的呢?它用了上面提到的两个优先级队列active和expired,顾名思义,active是还有时间片的进程队列,而expired是时间片耗尽必须重新分配时间片的进程队列。


这么设计的好处就是不用再循环一遍所有进程重设时间片了,看看调度函数是怎么玩的:
	array = rq->active;
	if (unlikely(!array->nr_active)) {
		/*
		 * Switch the active and expired arrays.
		 */
		schedstat_inc(rq, sched_switch);
		rq->active = rq->expired;
		rq->expired = array;
		array = rq->active;
		rq->expired_timestamp = 0;
		rq->best_expired_prio = MAX_PRIO;
	} else
		schedstat_inc(rq, sched_noswitch);


当所有运行进程的时间片都用完时,就把active和expired队列互换指针,没有遍历哦,而时间片耗尽的进程在出acitve队列入expired队列时,已经单独的重新分配好新时间片了。


再看一下schedule(void)调度函数,当某个进程休眠或者被抢占时,系统就开始调试schedule(void)决定接下来运行哪个进程。上面说过的东东都在这个函数里有体现哈。
asmlinkage void __sched schedule(void)
{
	long *switch_count;
	task_t *prev, *next;
	runqueue_t *rq;
	prio_array_t *array;
	struct list_head *queue;
	unsigned long long now;
	unsigned long run_time;
	int cpu, idx;


	/*
	 * Test if we are atomic.  Since do_exit() needs to call into
	 * schedule() atomically, we ignore that path for now.
	 * Otherwise, whine if we are scheduling when we should not be.
	 */
	if (likely(!(current->exit_state & (EXIT_DEAD | EXIT_ZOMBIE)))) {先看看当前运行进程的状态
		if (unlikely(in_atomic())) {
			printk(KERN_ERR "scheduling while atomic: "
				"%s/0x%08x/%d\n",
				current->comm, preempt_count(), current->pid);
			dump_stack();
		}
	}
	profile_hit(SCHED_PROFILING, __builtin_return_address(0));


need_resched:
	preempt_disable();
	prev = current;
	release_kernel_lock(prev);
need_resched_nonpreemptible:
	rq = this_rq();      这行找到这个CPU对应的runqueue,再次强调,每个CPU有一个自己的runqueue


	/*
	 * The idle thread is not allowed to schedule!
	 * Remove this check after it has been exercised a bit.
	 */
	if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) {
		printk(KERN_ERR "bad: scheduling from the idle thread!\n");
		dump_stack();
	}


	schedstat_inc(rq, sched_cnt);
	now = sched_clock();
	if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))
		run_time = now - prev->timestamp;
	else
		run_time = NS_MAX_SLEEP_AVG;


	/*
	 * Tasks with interactive credits get charged less run_time
	 * at high sleep_avg to delay them losing their interactive
	 * status
	 */
	if (HIGH_CREDIT(prev))
		run_time /= (CURRENT_BONUS(prev) ? : 1);


	spin_lock_irq(&rq->lock);


	if (unlikely(current->flags & PF_DEAD))
		current->state = EXIT_DEAD;
	/*
	 * if entering off of a kernel preemption go straight
	 * to picking the next task.
	 */
	switch_count = &prev->nivcsw;
	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		switch_count = &prev->nvcsw;
		if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
				unlikely(signal_pending(prev))))
			prev->state = TASK_RUNNING;
		else {
			if (prev->state == TASK_UNINTERRUPTIBLE)
				rq->nr_uninterruptible++;
			deactivate_task(prev, rq);
		}
	}


	cpu = smp_processor_id();
	if (unlikely(!rq->nr_running)) {
go_idle:
		idle_balance(cpu, rq);
		if (!rq->nr_running) {
			next = rq->idle;
			rq->expired_timestamp = 0;
			wake_sleeping_dependent(cpu, rq);
			/*
			 * wake_sleeping_dependent() might have released
			 * the runqueue, so break out if we got new
			 * tasks meanwhile:
			 */
			if (!rq->nr_running)
				goto switch_tasks;
		}
	} else {
		if (dependent_sleeper(cpu, rq)) {
			next = rq->idle;
			goto switch_tasks;
		}
		/*
		 * dependent_sleeper() releases and reacquires the runqueue
		 * lock, hence go into the idle loop if the rq went
		 * empty meanwhile:
		 */
		if (unlikely(!rq->nr_running))
			goto go_idle;
	}


	array = rq->active;
	if (unlikely(!array->nr_active)) {       上面说过的,需要重新计算时间片时,就用已经计算好的expired队列了
		/*
		 * Switch the active and expired arrays.
		 */
		schedstat_inc(rq, sched_switch);
		rq->active = rq->expired;
		rq->expired = array;
		array = rq->active;
		rq->expired_timestamp = 0;
		rq->best_expired_prio = MAX_PRIO;
	} else
		schedstat_inc(rq, sched_noswitch);


	idx = sched_find_first_bit(array->bitmap);         找到优先级最高的队列
	queue = array->queue + idx;
	next = list_entry(queue->next, task_t, run_list);


	if (!rt_task(next) && next->activated > 0) {
		unsigned long long delta = now - next->timestamp;


		if (next->activated == 1)
			delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;


		array = next->array;
		dequeue_task(next, array);
		recalc_task_prio(next, next->timestamp + delta);
		enqueue_task(next, array);
	}
	next->activated = 0;
switch_tasks:
	if (next == rq->idle)
		schedstat_inc(rq, sched_goidle);
	prefetch(next);
	clear_tsk_need_resched(prev);
	rcu_qsctr_inc(task_cpu(prev));


	prev->sleep_avg -= run_time;
	if ((long)prev->sleep_avg <= 0) {
		prev->sleep_avg = 0;
		if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))
			prev->interactive_credit--;
	}
	prev->timestamp = prev->last_ran = now;


	sched_info_switch(prev, next);
	if (likely(prev != next)) {              表面现在正在执行的进程,不是选出来的优先级最高的进程
		next->timestamp = now;
		rq->nr_switches++;
		rq->curr = next;
		++*switch_count;


		prepare_arch_switch(rq, next);
		prev = context_switch(rq, prev, next);              所以需要完成进程上下文切换,把之前的进程信息CACHE住
		barrier();


		finish_task_switch(prev);
	} else
		spin_unlock_irq(&rq->lock);


	prev = current;
	if (unlikely(reacquire_kernel_lock(prev) < 0))
		goto need_resched_nonpreemptible;
	preempt_enable_no_resched();
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
		goto need_resched;
}

当然,在我们程序中,也可以通过执行以下系统调用来改变自己进程的优先级。nice系统调用可以改变某个进程的基本优先级,setpriority可以改变一组进程的优先级。









                                
2017-02-04 14:17:07 chenpuo 阅读数 382
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9157 人正在学习 去看看 CSDN讲师


转载自  http://www.linuxidc.com/Linux/2012-02/53369.htm


Linux内核调度算法




================================快速找到最高优先级进程===================

为什么要了解内核的调度策略呢?呵呵,因为它值得我们学习,不算是废话吧。内核调度程序很先进很强大,管理你的LINUX上跑的大量的乱七八糟的进程,同时还保持着对用户操作的高灵敏响应,如果可能,为什么不把这种思想放到自己的应用程序里呢?或者,有没有可能更好的实现自己的应用,使得操作系统能够以自己的意志来分配资源给自己的进程?

带着这两个问题来看看KERNEL。首先回顾上我们开发应用程序,基本上就两种类型,1、IO消耗型:比如Hadoop上的trunk服务,很明显它的消耗主要在IO上,包括网络IO磁盘IO等等。2、CPU消耗型,比如mapreduce或者其他的需要对大量数据进行计算处理的组件,就象对高清视频压缩成适合手机观看分辨率的进程,他们的消耗主要在CPU上。当两类进程都在一台SERVER上运行时,操作系统会如何调度它们呢?现在的服务器都是SMP多核的,那么一个进程在多CPU时会来回切换吗?如果我有一个程序,既有IO消耗又有CPU消耗,怎么让多核更好的调度我的程序呢?


又多了几个问题。来看看内核调度程序吧,我们先从它的优先队列谈起吧。调度程序代码就在内核源码的kernel/sched.c的schedule函数中。
首先看下面的优先级队列,每一个runqueue都有。runqueue是什么?下面会详细说下,现在大家可以理解为,内核为每一颗CPU分配了一个runqueue,用于维护这颗CPU可以运行的进程。runqueue里,有几个成员是prio_array类型,这个东东就是优先队列,先看看它的定义:
[cpp]
  1. struct prio_array {  
  2.     unsigned int nr_active;    表示等待执行的进程总数  
  3.     unsigned long bitmap[BITMAP_SIZE];    一个unsigned long在内核中只有32位哈,大家要跟64位OS上的C程序中的long区分开,那个是64位的。那么这个bitmap是干什么的呢?它是用位的方式,表示某个优先级上有没有待处理的队列,是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级,我只需要四位就能表示某个优先级上有没有进程要运行,例如优先级是2和3上有进程,那么就应该是0110.......非常省空间,效率也快,不是吗?  
  4.     struct list_head queue[MAX_PRIO];     与上面的bitmap是对应的,它存储所有等待运行的进程。  
  5. };  
看看BITMAP_SIZE是怎么算出来的:#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
那么,LINUX默认配置(如果你用默认选项编译内核的话)MAX_PRIO是140,就是说一共内核对进程一共定义了140种优先级。等待某个CPU来处理的进程中,可能包含许多种优先级的进程,但,LINUX是个抢占式调度算法的操作系统,就是说,需要调度时一定是找到最高优先级的进程执行。上面的BITMAP_SIZE值根据MAX_PRIO算出来为5,那么bitmap实际是32*5=160位,这样就包含了MAX_PRIO的140位。优先级队列是怎么使用的?看2649行代码:idx = sched_find_first_bit(array->bitmap);这个方法就用来快速的找到优先级最高的队列。看看它的实现可以方便我们理解这个优先级位的设计:
[cpp]
  1. static inline int sched_find_first_bit(unsigned long *b)  
  2. {  
  3.     if (unlikely(b[0]))  
  4.         return __ffs(b[0]);  
  5.     if (unlikely(b[1]))  
  6.         return __ffs(b[1]) + 32;  
  7.     if (unlikely(b[2]))  
  8.         return __ffs(b[2]) + 64;  
  9.     if (b[3])  
  10.         return __ffs(b[3]) + 96;  
  11.     return __ffs(b[4]) + 128;  
  12. }  
那么__ffs是干什么的?
[cpp]
  1. static inline int __ffs(int x)  
  2. {  
  3.     int r = 0;  
  4.   
  5.     if (!x)  
  6.         return 0;  
  7.     if (!(x & 0xffff)) {  
  8.         x >>= 16;  
  9.         r += 16;  
  10.     }  
  11.     if (!(x & 0xff)) {  
  12.         x >>= 8;  
  13.         r += 8;  
  14.     }  
  15.     if (!(x & 0xf)) {  
  16.         x >>= 4;  
  17.         r += 4;  
  18.     }  
  19.     if (!(x & 3)) {  
  20.         x >>= 2;  
  21.         r += 2;  
  22.     }  
  23.     if (!(x & 1)) {  
  24.         x >>= 1;  
  25.         r += 1;  
  26.     }  
  27.     return r;  
  28. }  
sched_find_first_bit返回值就是最高优先级所在队列的序号,与queue是对应使用的哈,queue = array->queue + idx;这样就取到了要处理的进程队列。这个设计在查找优先级时是非常快的,非常值得我们学习。


好,优先级队列搞明白了,现在来看看runqueue,每个runqueue包含三个优先级队列。
[cpp]
  1. struct runqueue {  
  2.     spinlock_t lock;   这是个自旋锁,nginx里解决惊群现象时也是用这个。与普通锁的区别就是,使用普通锁时,你去试图拿一把锁,结果发现已经被别人拿走了,你就在那睡觉,等别人锁用完了叫你起来。所以如果有一个人拿住锁了,一百个人都在门前睡觉等。当之前的人用完锁回来后,会叫醒所有100个等锁的人,然后这些人开始互相抢,抢到的人拿锁进去,其他的人继续等。自旋锁不同,当他去拿锁发现锁被别人拿走了,他在那不睡觉的等,稍打个盹就看看自己主动看看锁有没有还回来。大家比较出优劣了吗?  
  3.   
  4.   
  5.     /* 
  6.      * nr_running and cpu_load should be in the same cacheline because 
  7.      * remote CPUs use both these fields when doing load calculation. 
  8.      */  
  9.     unsigned long nr_running;  
  10. #ifdef CONFIG_SMP   
  11.     unsigned long cpu_load;  
  12. #endif   
  13.     unsigned long long nr_switches;  
  14.   
  15.   
  16.     /* 
  17.      * This is part of a global counter where only the total sum 
  18.      * over all CPUs matters. A task can increase this counter on 
  19.      * one CPU and if it got migrated afterwards it may decrease 
  20.      * it on another CPU. Always updated under the runqueue lock: 
  21.      */  
  22.     unsigned long nr_uninterruptible;  
  23.   
  24.   
  25.     unsigned long expired_timestamp;  
  26.     unsigned long long timestamp_last_tick;  
  27.     task_t *curr, *idle;  
  28.     struct mm_struct *prev_mm;  
  29.     prio_array_t *active, *expired, arrays[2];上面说了半天的优先级队列在这里,但是在runqueue里,为什么不只一个呢?这个在下面讲。  
  30.     int best_expired_prio;  
  31.     atomic_t nr_iowait;  
  32.     ... ...  
  33. };  
LINUX是一个时间多路复用的系统,就是说,通过把CPU执行时间分成许多片,再分配给进程们使用,造成即使单CPU系统,也貌似允许多个任务在同时执行。那么,时间片大小假设为100ms,过短过长,过长了有些不灵敏,过短了,连切换进程时可能都要消耗几毫秒的时间。分给100个进程执行,在所有进程都用完自己的时间片后,需要重新给所有的进程重新分配时间片,怎么分配呢?for循环遍历所有的run状态进程,重设时间片?这个性能无法容忍!太慢了,跟当前系统进程数相关。那么2.6内核怎么做的呢?它用了上面提到的两个优先级队列active和expired,顾名思义,active是还有时间片的进程队列,而expired是时间片耗尽必须重新分配时间片的进程队列。


这么设计的好处就是不用再循环一遍所有进程重设时间片了,看看调度函数是怎么玩的:
[cpp]
  1. array = rq->active;  
  2. if (unlikely(!array->nr_active)) {  
  3.     /* 
  4.      * Switch the active and expired arrays. 
  5.      */  
  6.     schedstat_inc(rq, sched_switch);  
  7.     rq->active = rq->expired;  
  8.     rq->expired = array;  
  9.     array = rq->active;  
  10.     rq->expired_timestamp = 0;  
  11.     rq->best_expired_prio = MAX_PRIO;  
  12. else  
  13.     schedstat_inc(rq, sched_noswitch);  
当所有运行进程的时间片都用完时,就把active和expired队列互换指针,没有遍历哦,而时间片耗尽的进程在出acitve队列入expired队列时,已经单独的重新分配好新时间片了。


再看一下schedule(void)调度函数,当某个进程休眠或者被抢占时,系统就开始调试schedule(void)决定接下来运行哪个进程。上面说过的东东都在这个函数里有体现哈。
[cpp]
  1. asmlinkage void __sched schedule(void)  
  2. {  
  3.     long *switch_count;  
  4.     task_t *prev, *next;  
  5.     runqueue_t *rq;  
  6.     prio_array_t *array;  
  7.     struct list_head *queue;  
  8.     unsigned long long now;  
  9.     unsigned long run_time;  
  10.     int cpu, idx;  
  11.   
  12.   
  13.     /* 
  14.      * Test if we are atomic.  Since do_exit() needs to call into 
  15.      * schedule() atomically, we ignore that path for now. 
  16.      * Otherwise, whine if we are scheduling when we should not be. 
  17.      */  
  18.     if (likely(!(current->exit_state & (EXIT_DEAD | EXIT_ZOMBIE)))) {先看看当前运行进程的状态  
  19.         if (unlikely(in_atomic())) {  
  20.             printk(KERN_ERR "scheduling while atomic: "  
  21.                 "%s/0x%08x/%d\n",  
  22.                 current->comm, preempt_count(), current->pid);  
  23.             dump_stack();  
  24.         }  
  25.     }  
  26.     profile_hit(SCHED_PROFILING, __builtin_return_address(0));  
  27.   
  28.   
  29. need_resched:  
  30.     preempt_disable();  
  31.     prev = current;  
  32.     release_kernel_lock(prev);  
  33. need_resched_nonpreemptible:  
  34.     rq = this_rq();      这行找到这个CPU对应的runqueue,再次强调,每个CPU有一个自己的runqueue  
  35.   
  36.   
  37.     /* 
  38.      * The idle thread is not allowed to schedule! 
  39.      * Remove this check after it has been exercised a bit. 
  40.      */  
  41.     if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) {  
  42.         printk(KERN_ERR "bad: scheduling from the idle thread!\n");  
  43.         dump_stack();  
  44.     }  
  45.   
  46.   
  47.     schedstat_inc(rq, sched_cnt);  
  48.     now = sched_clock();  
  49.     if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))  
  50.         run_time = now - prev->timestamp;  
  51.     else  
  52.         run_time = NS_MAX_SLEEP_AVG;  
  53.   
  54.   
  55.     /* 
  56.      * Tasks with interactive credits get charged less run_time 
  57.      * at high sleep_avg to delay them losing their interactive 
  58.      * status 
  59.      */  
  60.     if (HIGH_CREDIT(prev))  
  61.         run_time /= (CURRENT_BONUS(prev) ? : 1);  
  62.   
  63.   
  64.     spin_lock_irq(&rq->lock);  
  65.   
  66.   
  67.     if (unlikely(current->flags & PF_DEAD))  
  68.         current->state = EXIT_DEAD;  
  69.     /* 
  70.      * if entering off of a kernel preemption go straight 
  71.      * to picking the next task. 
  72.      */  
  73.     switch_count = &prev->nivcsw;  
  74.     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {  
  75.         switch_count = &prev->nvcsw;  
  76.         if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&  
  77.                 unlikely(signal_pending(prev))))  
  78.             prev->state = TASK_RUNNING;  
  79.         else {  
  80.             if (prev->state == TASK_UNINTERRUPTIBLE)  
  81.                 rq->nr_uninterruptible++;  
  82.             deactivate_task(prev, rq);  
  83.         }  
  84.     }  
  85.   
  86.   
  87.     cpu = smp_processor_id();  
  88.     if (unlikely(!rq->nr_running)) {  
  89. go_idle:  
  90.         idle_balance(cpu, rq);  
  91.         if (!rq->nr_running) {  
  92.             next = rq->idle;  
  93.             rq->expired_timestamp = 0;  
  94.             wake_sleeping_dependent(cpu, rq);  
  95.             /* 
  96.              * wake_sleeping_dependent() might have released 
  97.              * the runqueue, so break out if we got new 
  98.              * tasks meanwhile: 
  99.              */  
  100.             if (!rq->nr_running)  
  101.                 goto switch_tasks;  
  102.         }  
  103.     } else {  
  104.         if (dependent_sleeper(cpu, rq)) {  
  105.             next = rq->idle;  
  106.             goto switch_tasks;  
  107.         }  
  108.         /* 
  109.          * dependent_sleeper() releases and reacquires the runqueue 
  110.          * lock, hence go into the idle loop if the rq went 
  111.          * empty meanwhile: 
  112.          */  
  113.         if (unlikely(!rq->nr_running))  
  114.             goto go_idle;  
  115.     }  
  116.   
  117.   
  118.     array = rq->active;  
  119.     if (unlikely(!array->nr_active)) {       上面说过的,需要重新计算时间片时,就用已经计算好的expired队列了  
  120.         /* 
  121.          * Switch the active and expired arrays. 
  122.          */  
  123.         schedstat_inc(rq, sched_switch);  
  124.         rq->active = rq->expired;  
  125.         rq->expired = array;  
  126.         array = rq->active;  
  127.         rq->expired_timestamp = 0;  
  128.         rq->best_expired_prio = MAX_PRIO;  
  129.     } else  
  130.         schedstat_inc(rq, sched_noswitch);  
  131.   
  132.   
  133.     idx = sched_find_first_bit(array->bitmap);         找到优先级最高的队列  
  134.     queue = array->queue + idx;  
  135.     next = list_entry(queue->next, task_t, run_list);  
  136.   
  137.   
  138.     if (!rt_task(next) && next->activated > 0) {  
  139.         unsigned long long delta = now - next->timestamp;  
  140.   
  141.   
  142.         if (next->activated == 1)  
  143.             delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;  
  144.   
  145.   
  146.         array = next->array;  
  147.         dequeue_task(next, array);  
  148.         recalc_task_prio(next, next->timestamp + delta);  
  149.         enqueue_task(next, array);  
  150.     }  
  151.     next->activated = 0;  
  152. switch_tasks:  
  153.     if (next == rq->idle)  
  154.         schedstat_inc(rq, sched_goidle);  
  155.     prefetch(next);  
  156.     clear_tsk_need_resched(prev);  
  157.     rcu_qsctr_inc(task_cpu(prev));  
  158.   
  159.   
  160.     prev->sleep_avg -= run_time;  
  161.     if ((long)prev->sleep_avg <= 0) {  
  162.         prev->sleep_avg = 0;  
  163.         if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))  
  164.             prev->interactive_credit--;  
  165.     }  
  166.     prev->timestamp = prev->last_ran = now;  
  167.   
  168.   
  169.     sched_info_switch(prev, next);  
  170.     if (likely(prev != next)) {              表面现在正在执行的进程,不是选出来的优先级最高的进程  
  171.         next->timestamp = now;  
  172.         rq->nr_switches++;  
  173.         rq->curr = next;  
  174.         ++*switch_count;  
  175.   
  176.   
  177.         prepare_arch_switch(rq, next);  
  178.         prev = context_switch(rq, prev, next);              所以需要完成进程上下文切换,把之前的进程信息CACHE住  
  179.         barrier();  
  180.   
  181.   
  182.         finish_task_switch(prev);  
  183.     } else  
  184.         spin_unlock_irq(&rq->lock);  
  185.   
  186.   
  187.     prev = current;  
  188.     if (unlikely(reacquire_kernel_lock(prev) < 0))  
  189.         goto need_resched_nonpreemptible;  
  190.     preempt_enable_no_resched();  
  191.     if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))  
  192.         goto need_resched;  
  193. }  
当然,在我们程序中,也可以通过执行以下系统调用来改变自己进程的优先级。nice系统调用可以改变某个进程的基本优先级,setpriority可以改变一组进程的优先级。linux








=========================CPU时间片如何分配===========================


内核在微观上,把CPU的运行时间分成许多分,然后安排给各个进程轮流运行,造成宏观上所有的进程仿佛同时在执行。双核CPU,实际上最多只能有两个进程在同时运行,大家在top、vmstat命令里看到的正在运行的进程,并不是真的在占有着CPU哈。

所以,一些设计良好的高性能进程,比如nginx,都是实际上有几颗CPU,就配几个工作进程,道理就在这。比如你的服务器有8颗CPU,那么nginx worker应当只有8个,当你多于8个时,内核可能会放超过多个nginx worker进程到1个runqueue里,会发生什么呢?就是在这颗CPU上,会比较均匀的把时间分配给这几个nginx worker,每个worker进程运行完一个时间片后,内核需要做进程切换,把正在运行的进程上下文保存下来。假设内核分配的时间片是100ms,做进程切换的时间是5ms,那么进程性能下降还是很明显的,跟你配置的worker有关,越多下降得越厉害。

当然,这是跟nginx的设计有关的。nginx是事件驱动的全异步进程,本身设计上就几乎不存在阻塞和中断,nginx的设计者就希望每一个nginx worker可以独占CPU的几乎全部时间片,这点就是nginx worker数量配置的依据所在。


当然,实际的运行进程里,大部分并不是nginx这种希望独占CPU全部时间片的进程,许多进程,比如vi,它在很多时间是在等待用户输入,这时vi在等待IO中断,是不占用时间片的,内核面对多样化的进程,就需要技巧性的分配CPU时间片了。


内核分配时间片是有策略和倾向性的。换句话说,内核是偏心的,它喜欢的是IO消耗型进程,因为这类进程如果不能及时响应,用户就会很不爽,所以它总会下意识的多分配CPU运行时间给这类进程。而CPU消耗进程内核就不太关心了。这有道理吗?太有了,CPU消耗型慢一点用户感知不出来,电信号和生物信号运转速度差距巨大。虽然内核尽量多的分配时间片给IO消耗型进程,但IO消耗进程常常在睡觉,给它的时间片根本用不掉。很合理吧?


那么内核具体是怎么实现这种偏心呢?通过动态调整进程的优先级,以及分配不同长短的CPU时间处来实现。先说内核如何决定时间片的长度。

对每一个进程,有一个整型static_prio表示用户设置的静态优先级,内核里它与nice值是对应的。看看进程描述结构里的static_prio成员。

[cpp]
  1. struct task_struct {  
  2.     int prio, static_prio;  
  3. ......}  

nice值是什么?其实就是优先级针对用户进程的另一种表示法,nice的取值范围是-20到+19,-20优先级最高,+19最低。上篇曾经说过,内核优先级共有140,而用户能够设置的NICE优先级如何与这140个优先级对应起来呢?看代码:

[cpp]
  1. #define MAX_USER_RT_PRIO    100   
  2. #define MAX_RT_PRIO     MAX_USER_RT_PRIO   
  3. #define MAX_PRIO        (MAX_RT_PRIO + 40)  
可以看到,MAX_PRIO就是140,也就是内核定义的最大优先级了。

[cpp]
  1. #define USER_PRIO(p)        ((p)-MAX_RT_PRIO)   
  2. #define MAX_USER_PRIO       (USER_PRIO(MAX_PRIO))  
而MAX_USER_PRIO就是40,意指,普通进程指定的优先级别最多40,就像前面我们讲的那样-20到+19。


[cpp]
  1. #define NICE_TO_PRIO(nice)  (MAX_RT_PRIO + (nice) + 20)  
nice值是-20表示最高,对应着static_prio是多少呢?NICE_TO_PRIO(0)就是120,NICE_TO_PRIO(-20)就是100。


当该进程刚被其父进程fork出来时,是平分其父进程的剩余时间片的。这个时间片执行完后,就会根据它的初始优先级来重新分配时间片,优先级为+19时最低,只分配最小时间片5ms,优先级为0时是100ms,优先级是-20时是最大时间片800ms。我们看看内核是如何计算时间片长度的,大家先看下task_timeslice时间片计算函数:

[cpp]
  1. #define SCALE_PRIO(x, prio) \   
  2.     max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)  
  3.   
  4. static unsigned int task_timeslice(task_t *p)  
  5. {  
  6.     if (p->static_prio < NICE_TO_PRIO(0))  
  7.         return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);  
  8.     else  
  9.         return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);  
  10. }  
这里有一堆宏,我们把宏依次列出看看它们的值:
[cpp]
  1. # define HZ     1000       
  2. #define DEF_TIMESLICE       (100 * HZ / 1000)  
所以,DEF_TIMESLICE是100。假设nice值是-20,那么static_prio就是100,那么SCALE_PRIO(100*4, 100)就等于800,意味着最高优先级-20情形下,可以分到时间片是800ms,如果nice值是+19,则只能分到最小时间片5ms,nice值是默认的0则能分到100ms。


貌似时间片只与nice值有关系。实际上,内核会对初始的nice值有一个-5到+5的动态调整。这个动态调整的依据是什么呢?很简单,如果CPU用得多的进程,就把nice值调高点,等价于优先级调低点。CPU用得少的进程,认为它是交互性为主的进程,则会把nice值调低点,也就是优先级调高点。这样的好处很明显,因为1、一个进程的初始优先值的设定未必是准确的,内核根据该进程的实时表现来调整它的执行情况。2、进程的表现不是始终如一的,比如一开始只是监听80端口,此时进程大部分时间在sleep,时间片用得少,于是nice值动态降低来提高优先级。这时有client接入80端口后,进程开始大量使用CPU,这以后nice值会动态增加来降低优先级。


思想明白了,代码实现上,优先级的动态补偿到底依据什么呢?effective_prio返回动态补偿后的优先级,注释非常详细,大家先看下。

[cpp]
  1. /* 
  2.  * effective_prio - return the priority that is based on the static 
  3.  * priority but is modified by bonuses/penalties. 
  4.  * 
  5.  * We scale the actual sleep average [0 .... MAX_SLEEP_AVG] 
  6.  * into the -5 ... 0 ... +5 bonus/penalty range. 
  7.  * 
  8.  * We use 25% of the full 0...39 priority range so that: 
  9.  * 
  10.  * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs. 
  11.  * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks. 
  12.  * 
  13.  * Both properties are important to certain workloads. 
  14.  */  
  15. static int effective_prio(task_t *p)  
  16. {  
  17.     int bonus, prio;  
  18.   
  19.     if (rt_task(p))  
  20.         return p->prio;  
  21.   
  22.     bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;  
  23.   
  24.     prio = p->static_prio - bonus;  
  25.     if (prio < MAX_RT_PRIO)  
  26.         prio = MAX_RT_PRIO;  
  27.     if (prio > MAX_PRIO-1)  
  28.         prio = MAX_PRIO-1;  
  29.     return prio;  
  30. }  
可以看到bonus会对初始优先级做补偿。怎么计算出这个BONUS的呢?

[cpp]
  1. #define CURRENT_BONUS(p) \   
  2.     (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \  
  3.         MAX_SLEEP_AVG)  
可以看到,进程描述符里还有个sleep_avg,动态补偿完全是根据它的值来运作的。sleep_avg就是关键了,它表示进程睡眠和运行的时间,当进程由休眠转到运行时,sleep_avg会加上这次休眠用的时间。在运行时,每运行一个时钟节拍sleep_avg就递减直到0为止。所以,sleep_avg越大,那么就会给到越大的动态优先级补偿,达到MAX_SLEEP_AVG时会有nice值-5的补偿。


内核就是这么偏爱交互型进程,从上面的优先级和时间片分配上都能看出来。实际上,内核还有方法对交互型进程搞优待。上篇说过,runqueue里的active和expired队列,一般的进程时间片用完后进expired队列,而对IO消耗的交互型进程来说,则会直接进入active队列中,保证高灵敏的响应,可见什么叫万千宠爱于一身了















===============多核系统的负载均衡==================


多核CPU现在很常见,那么问题来了,一个程序在运行时,只在一个CPU核上运行?还是交替在多个CPU核上运行呢?LINUX内核是如何在多核间调度进程的呢?又是内核又是CPU核,两个核有点绕,下面称CPU处理器来代替CPU核。

实际上,如果你没有对你的进程做过特殊处理的话,LINUX内核是有可能把它放到多个CPU处理器上运行的,这是内核的负载均衡。上文说过,每个处理器上有一个runqueue队列,表示这颗处理器上处于run状态的进程链表,在多处理器的内核中,就会有多个runqueue,而如果他们的大小很不均衡,就会触发内核的load_balance函数。这个函数会把某个CPU处理器上过多的进程移到runqueue元素相对少的CPU处理器上。

举个例子来简单说明这个过程吧。当我们刚fork出一个子进程时,子进程也还在当前CPU处理器的runqueue里,它与父进程均分父进程的时间片。当然,时间片与多处理器间的负载均衡没有关系。假设我们的系统是双核的,父进程运行在cpu0上,那么这个fork出来的进程也是在cpu0的runqueue中。

那么,什么时候会发生负载均衡呢?

1、当cpu1上的runqueue里一个可运行进程都没有的时候。这点很好理解,cpu1无事可作了,这时在cpu1上会调用load_balance,发现在cpu0上还有许多进程等待运行,那么它会从cpu0上的可运行进程里找到优先级最高的进程,拿到自己的runqueue里开始执行。

2、第1种情形不适用于运行队列一直不为空的情况。例如,cpu0上一直有10个可运行进程,cpu1上一直有1个可运行进程,显然,cpu0上的进程们得到了不公平的对待,它们拿到cpu的时间要小得多,第1种情形下的load_balance也一直不会调用。所以,实际上,每经过一个时钟节拍,内核会调用scheduler_tick函数,而这个函数会做许多事,例如减少当前正在执行的进程的时间片,在函数结尾处则会调用rebalance_tick函数。rebalance_tick函数决定以什么样的频率执行负载均衡。

[cpp]
  1. static void rebalance_tick(int this_cpu, runqueue_t *this_rq,  
  2.                enum idle_type idle)  
  3. {  
  4.     unsigned long old_load, this_load;  
  5.     unsigned long j = jiffies + CPU_OFFSET(this_cpu);  
  6.     struct sched_domain *sd;  
  7.   
  8.     /* Update our load */  
  9.     old_load = this_rq->cpu_load;  
  10.     this_load = this_rq->nr_running * SCHED_LOAD_SCALE;  
  11.     /* 
  12.      * Round up the averaging division if load is increasing. This 
  13.      * prevents us from getting stuck on 9 if the load is 10, for 
  14.      * example. 
  15.      */  
  16.     if (this_load > old_load)  
  17.         old_load++;  
  18.     this_rq->cpu_load = (old_load + this_load) / 2;  
  19.   
  20.     for_each_domain(this_cpu, sd) {  
  21.         unsigned long interval;  
  22.   
  23.         if (!(sd->flags & SD_LOAD_BALANCE))  
  24.             continue;  
  25.   
  26.         interval = sd->balance_interval;  
  27.         if (idle != SCHED_IDLE)  
  28.             interval *= sd->busy_factor;  
  29.   
  30.         /* scale ms to jiffies */  
  31.         interval = msecs_to_jiffies(interval);  
  32.         if (unlikely(!interval))  
  33.             interval = 1;  
  34.   
  35.         if (j - sd->last_balance >= interval) {  
  36.             if (load_balance(this_cpu, this_rq, sd, idle)) {  
  37.                 /* We've pulled tasks over so no longer idle */  
  38.                 idle = NOT_IDLE;  
  39.             }  
  40.             sd->last_balance += interval;  
  41.         }  
  42.     }  
  43. }  
当idle标志位是SCHED_IDLE时,表示当前CPU处理器空闲,就会以很高的频繁来调用load_balance(1、2个时钟节拍),反之表示当前CPU并不空闲,会以很低的频繁调用load_balance(10-100ms)。具体的数值要看上面的interval了。

当然,多核CPU也有许多种,例如INTEL的超线程技术,而LINUX内核对一个INTEL超线程CPU会看成多个不同的CPU处理器。

上面说过,如果你没有对你的进程做过特殊处理的话,LINUX内核是有可能把它放到多个CPU处理器上运行的,但是,有时我们如果希望我们的进程一直运行在某个CPU处理器上,可以做到吗?内核提供了这样的系统调用。系统调用sched_getaffinity会返回当前进程使用的cpu掩码,而sched_setaffinity则可以设定该进程只能在哪几颗cpu处理器上执行。当我们对某些进程有强烈的期待,或者想自己来考虑CPU间的负载均衡,可以这么试试哈。





PS,  引起CPU上下文切换的原因有哪些?

          对于抢占式操作系统而言, 大体有几种:

          1、当前任务的时间片用完之后,系统CPU正常调度下一个任务;

          2、当前任务碰到IO阻塞,调度线程将挂起此任务,继续下一个任务;

          3、多个任务抢占锁资源,当前任务没有抢到,被调度器挂起,继续下一个任务;

          4、用户代码挂起当前任务,让出CPU时间;

          5、硬件中断;

另外关于性能相关的分析工具有个LMbench, 详细可参考链接:

http://www.tuicool.com/articles/MjyANr

























2012-04-17 19:20:42 macky0668 阅读数 7217
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9157 人正在学习 去看看 CSDN讲师

linux内核调度算法(3)--多核系统的负载均衡

分类: linux 技术分享

多核CPU现在很常见,那么问题来了,一个程序在运行时,只在一个CPU核上运行?还是交替在多个CPU核上运行呢?LINUX内核是如何在多核间调度进程的呢?又是内核又是CPU核,两个核有点绕,下面称CPU处理器来代替CPU核。


实际上,如果你没有对你的进程做过特殊处理的话,LINUX内核是有可能把它放到多个CPU处理器上运行的,这是内核的负载均衡。上文说过,每个处理器上有一个runqueue队列,表示这颗处理器上处于run状态的进程链表,在多处理器的内核中,就会有多个runqueue,而如果他们的大小很不均衡,就会触发内核的load_balance函数。这个函数会把某个CPU处理器上过多的进程移到runqueue元素相对少的CPU处理器上。


举个例子来简单说明这个过程吧。当我们刚fork出一个子进程时,子进程也还在当前CPU处理器的runqueue里,它与父进程均分父进程的时间片。当然,时间片与多处理器间的负载均衡没有关系。假设我们的系统是双核的,父进程运行在cpu0上,那么这个fork出来的进程也是在cpu0的runqueue中。

那么,什么时候会发生负载均衡呢?

1、当cpu1上的runqueue里一个可运行进程都没有的时候。这点很好理解,cpu1无事可作了,这时在cpu1上会调用load_balance,发现在cpu0上还有许多进程等待运行,那么它会从cpu0上的可运行进程里找到优先级最高的进程,拿到自己的runqueue里开始执行。

2、第1种情形不适用于运行队列一直不为空的情况。例如,cpu0上一直有10个可运行进程,cpu1上一直有1个可运行进程,显然,cpu0上的进程们得到了不公平的对待,它们拿到cpu的时间要小得多,第1种情形下的load_balance也一直不会调用。所以,实际上,每经过一个时钟节拍,内核会调用scheduler_tick函数,而这个函数会做许多事,例如减少当前正在执行的进程的时间片,在函数结尾处则会调用rebalance_tick函数。rebalance_tick函数决定以什么样的频率执行负载均衡。

  1. static void rebalance_tick(int this_cpu, runqueue_t *this_rq,  
  2.                enum idle_type idle)  
  3. {  
  4.     unsigned long old_load, this_load;  
  5.     unsigned long j = jiffies + CPU_OFFSET(this_cpu);  
  6.     struct sched_domain *sd;  
  7.   
  8.     /* Update our load */  
  9.     old_load = this_rq->cpu_load;  
  10.     this_load = this_rq->nr_running * SCHED_LOAD_SCALE;  
  11.     /* 
  12.      * Round up the averaging division if load is increasing. This 
  13.      * prevents us from getting stuck on 9 if the load is 10, for 
  14.      * example. 
  15.      */  
  16.     if (this_load > old_load)  
  17.         old_load++;  
  18.     this_rq->cpu_load = (old_load + this_load) / 2;  
  19.   
  20.     for_each_domain(this_cpu, sd) {  
  21.         unsigned long interval;  
  22.   
  23.         if (!(sd->flags & SD_LOAD_BALANCE))  
  24.             continue;  
  25.   
  26.         interval = sd->balance_interval;  
  27.         if (idle != SCHED_IDLE)  
  28.             interval *= sd->busy_factor;  
  29.   
  30.         /* scale ms to jiffies */  
  31.         interval = msecs_to_jiffies(interval);  
  32.         if (unlikely(!interval))  
  33.             interval = 1;  
  34.   
  35.         if (j - sd->last_balance >= interval) {  
  36.             if (load_balance(this_cpu, this_rq, sd, idle)) {  
  37.                 /* We've pulled tasks over so no longer idle */  
  38.                 idle = NOT_IDLE;  
  39.             }  
  40.             sd->last_balance += interval;  
  41.         }  
  42.     }  
  43. }  

当idle标志位是SCHED_IDLE时,表示当前CPU处理器空闲,就会以很高的频繁来调用load_balance(1、2个时钟节拍),反之表示当前CPU并不空闲,会以很低的频繁调用load_balance(10-100ms)。具体的数值要看上面的interval了。


当然,多核CPU也有许多种,例如INTEL的超线程技术,而LINUX内核对一个INTEL超线程CPU会看成多个不同的CPU处理器。


上面说过,如果你没有对你的进程做过特殊处理的话,LINUX内核是有可能把它放到多个CPU处理器上运行的,但是,有时我们如果希望我们的进程一直运行在某个CPU处理器上,可以做到吗?内核提供了这样的系统调用。系统调用sched_getaffinity会返回当前进程使用的cpu掩码,而sched_setaffinity则可以设定该进程只能在哪几颗cpu处理器上执行。当我们对某些进程有强烈的期待,或者想自己来考虑CPU间的负载均衡,可以这么试试哈。

2012-04-17 19:20:16 macky0668 阅读数 4913
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9157 人正在学习 去看看 CSDN讲师

linux内核调度算法(2)--CPU时间片如何分配

分类: linux 技术分享

内核在微观上,把CPU的运行时间分成许多分,然后安排给各个进程轮流运行,造成宏观上所有的进程仿佛同时在执行。双核CPU,实际上最多只能有两个进程在同时运行,大家在top、vmstat命令里看到的正在运行的进程,并不是真的在占有着CPU哈。

所以,一些设计良好的高性能进程,比如nginx,都是实际上有几颗CPU,就配几个工作进程,道理就在这。比如你的服务器有8颗CPU,那么nginx worker应当只有8个,当你多于8个时,内核可能会放超过多个nginx worker进程到1个runqueue里,会发生什么呢?就是在这颗CPU上,会比较均匀的把时间分配给这几个nginx worker,每个worker进程运行完一个时间片后,内核需要做进程切换,把正在运行的进程上下文保存下来。假设内核分配的时间片是100ms,做进程切换的时间是5ms,那么进程性能下降还是很明显的,跟你配置的worker有关,越多下降得越厉害。

当然,这是跟nginx的设计有关的。nginx是事件驱动的全异步进程,本身设计上就几乎不存在阻塞和中断,nginx的设计者就希望每一个nginx worker可以独占CPU的几乎全部时间片,这点就是nginx worker数量配置的依据所在。


当然,实际的运行进程里,大部分并不是nginx这种希望独占CPU全部时间片的进程,许多进程,比如vi,它在很多时间是在等待用户输入,这时vi在等待IO中断,是不占用时间片的,内核面对多样化的进程,就需要技巧性的分配CPU时间片了。


内核分配时间片是有策略和倾向性的。换句话说,内核是偏心的,它喜欢的是IO消耗型进程,因为这类进程如果不能及时响应,用户就会很不爽,所以它总会下意识的多分配CPU运行时间给这类进程。而CPU消耗进程内核就不太关心了。这有道理吗?太有了,CPU消耗型慢一点用户感知不出来,电信号和生物信号运转速度差距巨大。虽然内核尽量多的分配时间片给IO消耗型进程,但IO消耗进程常常在睡觉,给它的时间片根本用不掉。很合理吧?


那么内核具体是怎么实现这种偏心呢?通过动态调整进程的优先级,以及分配不同长短的CPU时间处来实现。先说内核如何决定时间片的长度。

对每一个进程,有一个整型static_prio表示用户设置的静态优先级,内核里它与nice值是对应的。看看进程描述结构里的static_prio成员。

  1. struct task_struct {  
  2.     int prio, static_prio;  
  3. ......}  

nice值是什么?其实就是优先级针对用户进程的另一种表示法,nice的取值范围是-20到+19,-20优先级最高,+19最低。上篇曾经说过,内核优先级共有140,而用户能够设置的NICE优先级如何与这140个优先级对应起来呢?看代码:

  1. #define MAX_USER_RT_PRIO    100  
  2. #define MAX_RT_PRIO     MAX_USER_RT_PRIO  
  3. #define MAX_PRIO        (MAX_RT_PRIO + 40)  

可以看到,MAX_PRIO就是140,也就是内核定义的最大优先级了。

  1. #define USER_PRIO(p)        ((p)-MAX_RT_PRIO)  
  2. #define MAX_USER_PRIO       (USER_PRIO(MAX_PRIO))  

而MAX_USER_PRIO就是40,意指,普通进程指定的优先级别最多40,就像前面我们讲的那样-20到+19。


  1. #define NICE_TO_PRIO(nice)  (MAX_RT_PRIO + (nice) + 20)  

nice值是-20表示最高,对应着static_prio是多少呢?NICE_TO_PRIO(0)就是120,NICE_TO_PRIO(-20)就是100。


当该进程刚被其父进程fork出来时,是平分其父进程的剩余时间片的。这个时间片执行完后,就会根据它的初始优先级来重新分配时间片,优先级为+19时最低,只分配最小时间片5ms,优先级为0时是100ms,优先级是-20时是最大时间片800ms。我们看看内核是如何计算时间片长度的,大家先看下task_timeslice时间片计算函数:

  1. #define SCALE_PRIO(x, prio) \  
  2.     max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)  
  3.   
  4. static unsigned int task_timeslice(task_t *p)  
  5. {  
  6.     if (p->static_prio < NICE_TO_PRIO(0))  
  7.         return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);  
  8.     else  
  9.         return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);  
  10. }  

这里有一堆宏,我们把宏依次列出看看它们的值:
  1. # define HZ     1000      
  2. #define DEF_TIMESLICE       (100 * HZ / 1000)  

所以,DEF_TIMESLICE是100。假设nice值是-20,那么static_prio就是100,那么SCALE_PRIO(100*4, 100)就等于800,意味着最高优先级-20情形下,可以分到时间片是800ms,如果nice值是+19,则只能分到最小时间片5ms,nice值是默认的0则能分到100ms。


貌似时间片只与nice值有关系。实际上,内核会对初始的nice值有一个-5到+5的动态调整。这个动态调整的依据是什么呢?很简单,如果CPU用得多的进程,就把nice值调高点,等价于优先级调低点。CPU用得少的进程,认为它是交互性为主的进程,则会把nice值调低点,也就是优先级调高点。这样的好处很明显,因为1、一个进程的初始优先值的设定未必是准确的,内核根据该进程的实时表现来调整它的执行情况。2、进程的表现不是始终如一的,比如一开始只是监听80端口,此时进程大部分时间在sleep,时间片用得少,于是nice值动态降低来提高优先级。这时有client接入80端口后,进程开始大量使用CPU,这以后nice值会动态增加来降低优先级。


思想明白了,代码实现上,优先级的动态补偿到底依据什么呢?effective_prio返回动态补偿后的优先级,注释非常详细,大家先看下。

  1. /* 
  2.  * effective_prio - return the priority that is based on the static 
  3.  * priority but is modified by bonuses/penalties. 
  4.  * 
  5.  * We scale the actual sleep average [0 .... MAX_SLEEP_AVG] 
  6.  * into the -5 ... 0 ... +5 bonus/penalty range. 
  7.  * 
  8.  * We use 25% of the full 0...39 priority range so that: 
  9.  * 
  10.  * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs. 
  11.  * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks. 
  12.  * 
  13.  * Both properties are important to certain workloads. 
  14.  */  
  15. static int effective_prio(task_t *p)  
  16. {  
  17.     int bonus, prio;  
  18.   
  19.     if (rt_task(p))  
  20.         return p->prio;  
  21.   
  22.     bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;  
  23.   
  24.     prio = p->static_prio - bonus;  
  25.     if (prio < MAX_RT_PRIO)  
  26.         prio = MAX_RT_PRIO;  
  27.     if (prio > MAX_PRIO-1)  
  28.         prio = MAX_PRIO-1;  
  29.     return prio;  
  30. }  

可以看到bonus会对初始优先级做补偿。怎么计算出这个BONUS的呢?

  1. #define CURRENT_BONUS(p) \  
  2.     (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \  
  3.         MAX_SLEEP_AVG)  

可以看到,进程描述符里还有个sleep_avg,动态补偿完全是根据它的值来运作的。sleep_avg就是关键了,它表示进程睡眠和运行的时间,当进程由休眠转到运行时,sleep_avg会加上这次休眠用的时间。在运行时,每运行一个时钟节拍sleep_avg就递减直到0为止。所以,sleep_avg越大,那么就会给到越大的动态优先级补偿,达到MAX_SLEEP_AVG时会有nice值-5的补偿。


内核就是这么偏爱交互型进程,从上面的优先级和时间片分配上都能看出来。实际上,内核还有方法对交互型进程搞优待。上篇说过,runqueue里的active和expired队列,一般的进程时间片用完后进expired队列,而对IO消耗的交互型进程来说,则会直接进入active队列中,保证高灵敏的响应,可见什么叫万千宠爱于一身了。

2019-02-15 14:10:12 CrazyHeroZK 阅读数 285
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9157 人正在学习 去看看 CSDN讲师

进程调度

  1. 暂时以2.6.24内核版本讲解,该版本是CFS调度器注入Linux内核之后的第二个版本,在框架和数据结构上与4.x之后没有本质上的区别。但是由于4.x对CFS调度做了很大的优化,代码量暴增10倍之多,故不容易把握算法与框架的本质,所以暂时以麻雀虽小五脏俱全的2.6.24作为讲解数据结构方面的基础。
  2. 主要讲解CFS调度类与调度框架,实时进程与其他类型的进程调度算法与CFS在框架上没有区别。
  3. 在讲解代码实现时,修调整函数原本的封装结构,并且没有列出锁、中断、抢占等操作,这仅仅是为了更清晰的理解调度框架做了什么
  4. 在一些算法和描述上参考了 JeanCheng CSDN博客专家的文章,原地址 目录索引

概述

分时系统

为了让所有共享CPU资源,并且进程响应时间尽可能快,后台作业的吞吐量尽可能高,尽可能避免进程的饥饿现象,低优先级和高优先级的进程尽可能调和等,Linux设计了一套本质上基于多个进程以“时间多路复用“的方式来调度所有进程的分时技术调度器 ———— 即将使用CPU的时间分片,每一个进程获得一片或多片时间,在某个进程消耗完自己的分得的时间资源后,由时间中断中来检查,然后强制的切换到另一个进程,通过这样的快速切换,从表面上达到所有进程都同时运行的效果,其中何时切换进程并选择哪一个进程来运行即为调度策略。

进程优先级

为了从基本准则上公平的分配CPU运行时间资源,我们将进程按等级分类,优先级越高的进程分得的CPU资源越多,而等级越低分得的CPU资源越少。但是必须保证每一个进程在一定时间内都能运行,否则可能出现低优先级进程被“饿死”的现象,即表现为进程卡顿、甚至无法响应。所以在实际的调度过程中,需要按实际的作业场景再次将进程分类,并动态的调整他们的优先级,使其在需要时能及时的分配到CPU资源,完成必要的工作后,随后立马放弃CPU资源,让真正优先级高的进程再次运行。

进程分类

  1. 按使用CPU的使用程度分类为I/O受限(I/O-dound)CPU受限(CPU-bound)。I/O受限型也称作I/O密集型,这类进程频繁的使用I/O设备,并花费很多时间等待I/O操作的完成,他们IO数据就绪时要求立马得到响应,读取完数据之后又立马进入睡眠再次等待后续数据就绪,比如数据库服务器、文本编辑器等;CPU受限型也称为计算密集型,这类进程花费大量CPU时间进行数值计算,他们会一直使用CPU,基本不睡眠,比如图形渲染、科学计算等。

  2. 按作业场景分类为交互式进程批处理进程实时进程。交互式进程,此类进程经常与用户进行交互,因此需要花费很多时间等待键盘和鼠标操作,当接受了用户的输入后,进程必须很快被唤醒,否则用户会感觉系统反应迟钝,比如图形界面的应用程序。批处理进程,此类进程不必与用户交互, 因此经常在后台运行. 因为这样的进程不必很快相应, 因此常受到调度程序的怠慢,比如科学计算程序。实时进程,这些进程由很强的调度需要,这样的进程绝不会被低优先级的进程阻塞,并且他们的响应时间要尽可能的短,比如视频音频应用程序。

进程调度策略

为了更好的描述进程类型和和优先级与调度之间的关系,我们用调度策略来描述。不同的调度策略他们分配CPU资源的算法不同或组织进程的结构不同,但是被调度器使用的方式相同。

调度器

主调度器

调度的最终目标是选择一个合适的进程来使用CPU资源,使暂时让出的CPU资源使用的进程的状态得到保存,并使即将获得CPU资源使用的进程的状态得到恢复,为完成这一些动作而设计的算法和实现即为主调度器。

周期调度器

为了达到不需要编程者手工的插入调度相关的代码就能完成调度,Linux在以合理的使用主调度为目的,设计出周期调度器。通过在时间中断中触发周期调度器,并在时间中断结束后,调用主调度器(如果需要),进程的调度可以对编程者透明化,从而达到简化编程的目的。

调度框架

调度框架使用运行队列作为管理进程调度的组织结构的入口,并将进程分类调度,不同类型的调度算法有着不同的属性,调度框架用调度实体来描述它们,但是它们在参与调度时有相同的行为,调度框架用调度类来描述这些行为。

运行队列

运行队列是程序在排队等待使用CPU资源的一种管理容器。在调度框架顶层实现中,调度框架只识别运行队列,至于属于不同调度类的进程要以怎样的方式组织,这依赖于调度类相应的调度队列。所以运行队列要想管理有所的不同调度类的进程,必须包含所有的调度类的调度队列,每次对运行队列的操作被调度类转变为对相应调度队列的操作。

调度实体

不同类型进程参与调度所使用的基本属性,它是进程本身与调度框架的纽扣。如果将调度框架的实现看做面向对象,那么调度框架是容器,而调度实体是容器中的元素基类,而进程则是基类的派生类。

调度标志

内核通过在进程栈上设置一个标志来标识进程的特殊状态,其中就包括 调度标志 ———— TIF_NEED_RESCHED,如果被设置就表示该进程应该被调度,让出CPU资源。它存在 struct thread_infoflags 字段中,而整个结构体位于内核栈的栈低,内核通过 esp 寄存器可以快速的计算出其指针位置。

调度类

为了将不同类型进程调度融合在一起,我们以面向对象的方式抽象出一系列实现调度器的基本操作,这些操作的集合成为调度类。不同类型的进程归纳在不同的调度类,就获取不同的调度策略。

调度框架使用运行队列作为数据结构,调度类作为数据结构的操纵集合来实现调度,而发生调度有两种情况:

  1. 调用主调度器主动的放弃对CPU资源的使用,并选择一个合适的进程来使用CPU。
  2. 周期调度器强制的剥夺当前运行的进程对CPU资源的使用,并选择一个合适的进程来使用CPU。

因为对这些动作分解后,最后都会变为对特殊调度类和他们匹配的调度队列的操作,所以调度类要实现以下的动作:

  1. enqueue_task() 因为当前运行的进程从运行状态可能转变为排队状态,所以需要入队列。
  2. dequeue_task() 因为即将运行的进程从排队状态转变为排队状态,所以需要出队列。
  3. put_prev_task() 因为当前运行的进程一定会从运行状态转变为非运行状态,所以需要放置前运行进程。有可能排队,也有可能因为标记为非运行状态,不再排队。
  4. pick_next_task() 因为要选择一个新的进程来替换当前运行的进程,所以需要选择一个进程并出队列。
  5. task_tick() 为了周期的判断是否应该剥夺当前进程对CPU资源的使用,调度框架在时间中断中使用该函数检查进程,如果应该被剥夺则标记。

在进程被剥夺CPU资源的使用权后,可能还希望再次使用;或在新的进程希望参与到调度中来,所有调度类还要实现以下动作:

  1. enqueue_task() 因为操作的进程或新进程还不处于运行队列中,所有需要排队后才能产于调度。
  2. check_preempt_curr() 因为当前运行的进程优先级比试图再次使用CPU资源的进程的优先级低,所有需要进行此类的检查,以便及时的剥夺当前运行进程的使用权 ———— 即抢占低优先级进程。
  3. task_new() 因为刚创建的进程在参与调度前,需要特殊的初始化,所以需要实现此动作。

调度实现

调度策略与调度类

内核将进程的调度策略归纳为:

  1. SCHED_NORMAL 普通非实时进程策略,大部分进程都属于该类调度策略。
  2. SCHED_BATCH 批处理非实时进程策略,它是 SCHED_NORMAL 的分化版本,最大的不同就是优先级更低,而且肯定不会去抢占 SCHED_NORMAL 类型的进程。
  3. SCHED_IDLE 空闲非实时进程策略,优先级最低,除非其他所有的进程都挂起等待各自的资源就绪,否则不会允许此类的进程。
  4. SCHED_FIFO 先入先出的实时进程策略,高优先级的任务可以抢占低优先级的任务,但同优先级的进程除非自动放弃CPU,否则不会被主动剥离CPU使用权。而且肯定不会被非实时进程抢占。
  5. SCHED_RRSCHED_FIFO 类似,但在使用CPU到期时,会被强制剥夺CPU使用权,并放置在队列尾部,以轮转的方式使用CPU。
  6. SCHED_DEADLINE 新支持的实时进程调度策略,针对突发型计算,且对延迟和完成时间高度敏感的任务适用。(暂时没有搞懂怎么回事)

内核在预实现了以下的调度类来处理这些策略的进程调度:

  1. dl_sched_class 服务 SCHED_DEADLINE 策略的进程调度。
  2. rt_sched_class 服务 SCHED_RRSCHED_FIFO 策略的进程调度,因为他们是和优先级强关联的,所以调度队列的组织结构是一样的 ———— 都是优先级队列。
  3. fair_sched_class 服务 SCHED_NORMALSCHED_BATCH 策略的进程调度,即著名的完全公平调度类,因为他们是将优先级转变为权重,进而转换为虚拟运行时间进行排队,所以使用红黑树来组织待调度进程,并且能保证在一定调度周期内,所有的进程都能被调度一次,所以叫完全公平调度类。
  4. idle_sched_class 服务 SCHED_IDLE 策略的进程调度,内核中每个CPU上只有一个这样的进程,即为 swapper pid 为0的零号进程。

内核将会以下列的优先级来组织调度类,即从优先级最高的调度类来选择下一个运行的进程:

dl_sched_class > rt_sched_class > fair_sched_class > idle_sched_class

下面将以完全公平调度类为例来介绍新的基于调度类设计的调度实现。

进程的调度

首先,必须明确的是进程的状态与进程调度的关联,只有处于 TASK_RUNNING 的进程才可以参与调度 ———— 可以排队到相应的调度队列中。

调度发送的时机有以下列出的几处:

  1. 由编程者主观的调用 schedule() 主调度器,即因为当前进程要等待一个未就绪的条件而放弃CPU资源的调度。
  2. 由时间中断在检查确定当前进程运行时间配额用完后,退出中断并完全将要返回可抢占状态时,调用 preempt_schedule_irq() 周期调度器而强制剥夺当前运行进程对CPU资源使用的调度。另外这种情况切换也会在从硬中断、系统调用或(缺页)异常返回用户空间时触发。
  3. 由于系统支持内核态抢占,在内核态离开原子上下文(使能软中断、自旋锁解锁等)时,调用 preempt_schedule() 抢占调度器触发的进程调度。

在系统启动时会初始化一个每隔一定时间触发的时钟中断,在中断中对当前运行进程的运行时间进行更新,如果该进程需要被调度,就在进程上设置 TIF_NEED_RESCHED,之后从时钟中断返回。因为上面已经提到从中断上下文返回时是有调度时机的,在内核源码的汇编代码中所有中断返回处理都必须去判断 TIF_NEED_RESCHED 是否设置,如设置则最终执行 schedule() 进行调度。

数据结构介绍

  1. 进程与调度相关的基本字段

进程使用调度实体的数据结构参与调度,这样设计还可以组合更大的调度单位,比如以进程组的方式调度。调度实体内嵌入进程描述符中,如下:

struct task_struct {
	/* 进程优先级
	 * prio: 动态优先级,范围为100~139,与静态优先级和补偿(bonus)有关,内核需要暂时提高进程的优先级, 因此需要用prio表示
	 * static_prio: 静态优先级,static_prio = 100 + nice + 20 (nice值为-20~19,所以static_prio值为100~139)
	 * normal_prio: 表示基于进程的静态优先级static_prio和调度策略计算出的优先级
	 */
	int prio,/**< 动态优先级*/ static_prio, /**<静态优先级*/normal_prio; /**<普通动态优先级*/
	const struct sched_class *sched_class; /**< 所属调度类*/

	struct sched_entity se; /**<完全公平调度队列中的节点(调度实体)*/

	unsigned int policy;/**<进程调度类型:SCHED_NORMAL、 sched_rr 或 sched_fifo */
	cpumask_t cpus_allowed;/**<能执行该进程的CPU掩码*/
};

struct sched_entity {
	struct load_weight	load;		/**< 负载权重和重除 for load-balancing */
	struct rb_node		run_node; /**< 嵌入到红黑树的节点*/
	unsigned int		on_rq; /**< 是否在调度队列上*/

	u64			exec_start; /**< 开始执行的时间*/
	u64			sum_exec_runtime; /**< 执行总时间*/
	u64			vruntime; /**< 虚拟运行时间*/
	u64			prev_sum_exec_runtime; /**< 上次调度以来的执行总时间*/
}

struct load_weight {
	unsigned long weight /**< 权重*/, inv_weight/**< 除重系数*/;
};
  1. 调度类

进程必然属于某一调度类,以使调度框架在调度的顶层实现函数中可以以同样的方式操作进程。

struct sched_class {
	/* 系统中多个调度类, 按照其调度的优先级排成一个链表
	 * 下一优先级的调度类
	 * 调度类优先级顺序: stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
	 */
	const struct sched_class *next;

	/*  将进程加入到运行队列中,即将调度实体(进程)放入红黑树中,并对 nr_running 变量加1   */
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
	/*  从运行队列中删除进程,并对 nr_running 变量中减1  */
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
	/*  放弃CPU,在 compat_yield sysctl 关闭的情况下,该函数实际上执行先出队后入队;在这种情况下,它将调度实体放在红黑树的最右端  */
	void (*yield_task) (struct rq *rq);

	/*   检查当前运行进程是否可被新进程抢占 */
	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);

	/*  周期调度时,选择下一个应该要运行的进程运行  */
	struct task_struct * (*pick_next_task) (struct rq *rq);
	/* 周期调度时,将进程放回运行队列 */
	void (*put_prev_task) (struct rq *rq, struct task_struct *p);

#ifdef CONFIG_SMP
	unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
			struct rq *busiest, unsigned long max_load_move,
			struct sched_domain *sd, enum cpu_idle_type idle,
			int *all_pinned, int *this_best_prio);

	/* 迁移任务到另一个CPU */
	int (*move_one_task) (struct rq *this_rq, int this_cpu,
			      struct rq *busiest, struct sched_domain *sd,
			      enum cpu_idle_type idle);
#endif

	/* 当进程改变它的调度类或进程组时被调用 */
	void (*set_curr_task) (struct rq *rq);
	/* 该函数通常调用自 time tick 函数;它可能引起进程切换。这将驱动运行时(running)抢占 */
	void (*task_tick) (struct rq *rq, struct task_struct *p);
	/* 在进程创建时调用,不同调度策略的进程初始化不一样 */
	void (*task_new) (struct rq *rq, struct task_struct *p);
};

/*CFS调度类*/
static const struct sched_class fair_sched_class;
  1. CFS

不同的调度类虽然有相同行为,但是其实现不同,也需要不同的数据结构。

struct cfs_rq {
	struct load_weight load;
	unsigned long nr_running;

	u64 exec_clock;
	u64 min_vruntime;

	struct rb_root tasks_timeline;
	struct rb_node *rb_leftmost;
	struct rb_node *rb_load_balance_curr;
	/* 'curr' points to currently running entity on this cfs_rq.
	 * It is set to NULL otherwise (i.e when none are currently running).
	 */
	struct sched_entity *curr;
}

CFS调度队列通过红黑树组织,因为其管理的待调度进程通过 虚拟时间 来升序排序的,虚拟时间越小则越靠左边,而每次调度时都取最左边的进程,所以更容易被调度。

  1. 运行队列

整个调度框架的数据结构总入口,调度框架和实现函数只识别运行队列,而具体的实现交于不同的调度类。每个CPU上有一个运行队列,以减少调度时带来的并发竞争。

struct rq {
	unsigned long nr_running; /**< 可运行进程的总数*/

	#define CPU_LOAD_IDX_MAX 5
	unsigned long cpu_load[CPU_LOAD_IDX_MAX];/**< 跟踪运行队列的负载平均值*/

	struct load_weight load; /**< 所管理的运行进程总负载权重,用于计算运行队列的基础虚拟时间*/

	struct cfs_rq cfs; /**< 完全公平调度队列*/

	unsigned long nr_uninterruptible; /**< 处于不可中断的进程数量*/

	struct task_struct *curr, *idle; /**< 当前运行的进程和swapper进程*/
	struct mm_struct *prev_mm; /**< 上下文切换中暂存的用户进程内存描述符*/

	/*调度器的自身时钟计数*/
	u64 clock/**<单调递增的节拍*/, prev_clock_raw/**< 系统节拍*/;
	u64 tick_timestamp; /**< 时钟中断时的当前时间戳*/


#ifdef CONFIG_SMP
	struct sched_domain *sd; /**< 描述负载均衡相关的CPU分布的调度域*/

	/* For active balancing */
	int active_balance;
	int push_cpu;

	struct task_struct *migration_thread; /**< 处理迁移的进程*/
	struct list_head migration_queue; /**< 待迁移的进程队列头*/
#endif
}

优先级的处理

调度框架将进程对CPU资源配额配额抽象为优先级,并数值范围 0~139 表示(120为默认值),数值越低,优先级越高。从 0~99 的范围专供实时进程使用,其余为普通进程(CFS调度类管理的进程)。在用户态还使用 nice-20~19 来表示普通进程对其他进程的友好程度(0为默认值),即让出更多的CPU使用时间,这个值映射到范围 100~139

优先处理与转换的宏和数据如下:

#define MAX_USER_RT_PRIO	100
#define MAX_RT_PRIO		MAX_USER_RT_PRIO

#define MAX_PRIO		(MAX_RT_PRIO + 40)
#define DEFAULT_PRIO	(MAX_RT_PRIO + 20)

/*友好值与优先级的相互转换*/
#define NICE_TO_PRIO(nice)	((nice) + DEFAULT_PRIO)
#define PRIO_TO_NICE(prio)	((prio) - DEFAULT_PRIO)
#define TASK_NICE(p)		PRIO_TO_NICE((p)->static_prio)

/*默认友好值的权重*/
#define SCHED_LOAD_SHIFT	10
#define SCHED_LOAD_SCALE	(1L << SCHED_LOAD_SHIFT)
#define NICE_0_LOAD		SCHED_LOAD_SCALE
#define NICE_0_SHIFT	SCHED_LOAD_SHIFT

内核在实现CFS时,使用权重来描述进程应该分得多少CPU时间,因为CFS只负责非实时进程,所以权重与 nice 值密切相关。一般这个概念是,进程每降低一个 nice 值(优先级提升), 则多获得 10% 的CPU时间, 每升高一个 nice 值(优先级降低), 则放弃 10% 的CPU时间。

为执行该策略,内核需要将优先级转换为权重值,并提供了一张优先级到权重转换表 prio_to_weight ,各个值之间的乘积因子为 1.25 ,此值是为达到 nice 值增减一个单位,CPU时间占比就相应的浮动 10% 而设定的。由于在计算过程中需要使用除法,内核还提供一张 定点数除法 的倒数表 prio_to_wmult 数组,这两个数组中的数据是一一对应的,用来帮助内核进行浮点运算。

对于CFS调度类,内核不仅使用权重来衡量进程在一定CPU时间周期分得的时间配额,还是使用权重来衡量进程运行的虚拟时间的快慢 ———— 权重越大,流失得越慢。计算相当公式如下:

  • nice != NICE_0_LOAD 虚拟时间 vruntime = real_exec_time * NICE_0_LOAD / weight
  • nice == NICE_0_LOAD 虚拟时间 vruntime 即使真实运行时间 real_exec_time

可见权重越大,虚拟时间也流失得越慢,在上面介绍的CFS调度队列红黑树中排队越靠前。

调度的初始化

内核将在系统启动时初始化调度框架的数据结构。在 start_kernel() 中调用 sched_init() 函数初始化 rq,并初始化第一个进程 ———— 即 swapper 进程的调度相关的数据结构。

void __init sched_init(void)
{
	for_each_possible_cpu(i) {
		struct rt_prio_array *array;
		struct rq *rq;

		rq = cpu_rq(i);
		init_cfs_rq(&rq->cfs, rq);
		...
	}
	...
	set_load_weight(&init_task);
	...
	open_softirq(SCHED_SOFTIRQ, run_rebalance_domains, NULL);
	...
	init_idle(current, smp_processor_id());
	current->sched_class = &fair_sched_class;
}

该函数主要是遍历运行队列的 per-cpu 结构,对运行队列进行初始化,包括其中的CFS调度队列。之后初始化零号进程的调度相关字段,注意此时故意将 swapper 进程设置为 CFS 调度策略,是为随后 在 rest_init() 中创建 其他内核线程和一号 init 进程,因为子进程会继承大部分父进程的调度属性,包括调度策略,在完成最终初始化后,swapper 才变身为 IDLE 调度策略,并使能抢占以让其他进程或线程运行,随后只会执行 cpu_idle() 死循环函数知道关机。而一号 init 进程在创建初期还是执行在内核态的内核线程,它在此形态下还负责继续完成启动内核的多核启动;通过 smp_init()sched_init_smp() 函数内核将完成其他CPU的启动,最重要的是回调启动过程注册 per-cpu 初始化回调链(参见 register_cpu_notifier() 的使用)、克隆启动CPU上的 swapper 进程(克隆的进程不会驻留在进程组织结构中,但是占用了pid号)、初始化调度域等(由于此部分涉及很多硬件相关的知识,不能一一列举功能);随后 init 进程执行 run_init_process("/sbin/init"); 转变为一个用户态进程,负责所有用户态僵死进程的回收工作。

周期调度器

周期调度器由 scheduler_tick() 实现信息的统计和判断是否应该剥夺当前运行进程对CPU资源的使用权,该函数由时钟硬中断在固定时间内触发,如果进程对CPU资源的使用到期,则进行简单标记,在退出中断上下文时再配合主调度器 scheduler() 进行强制调度,它是以一种对进程透明的、公平的为所有进程分配CPU资源的使用权的重要手段。

void scheduler_tick(void)
{
	int cpu = smp_processor_id();
	struct rq *rq = cpu_rq(cpu);
	struct task_struct *curr = rq->curr;

	/*更新运行队列自己的节拍*/
	__update_rq_clock(rq);
	...

	/*更新运行队列CPU负载*/
	update_cpu_load(rq);
	/* 如果当前不是idle进程,则更新运行进程的信息
	 * 这可能会导致在时间中断结束时重新选择一个可运行的进程进行调度
	 * 使用调度类模拟多态
	 * @see task_tick_fair()
	 */
	if (curr != rq->idle) /* FIXME: needed? */
		curr->sched_class->task_tick(rq, curr);
	...
#ifdef CONFIG_SMP
	/* 负载均衡 */
	trigger_load_balance(rq, cpu);
#endif
}

主要是更新运行队列的虚拟时钟节拍,每个运行队列有自己的时间节拍概念,是因为时钟中断的实现不同和各个运行队列调度频繁程度不同,而调度又是基于分时机制的,所以为了较为精准计算运行的进程何时应该被抢占何时应该被调度,运行队列使用各自虚拟时钟节拍来计算相关的时间参数。内核使用开机后流失的纳秒时间来描述运行队列的节拍,使用 __update_rq_clock() 来更新这些时间属性,保证其单调性。

系统在运行一段时间后,不同的CPU上调用 fork() 的次数不同,导致进程在全局的运行队列里数量不平衡,内核需要以一种参数来描述这一情况,并以此为标准来进行负载平衡,将进程从繁忙的CPU运行队列中迁移到空闲的CPU运行队列中。 update_cpu_load() 负载完成负载计算,其本质上存储当前负载的一系列历史平均值。

不同进程其调度策略不同,运行时间统计信息和组织结构也不同,但是他们都需要周期的检查当前运行的进程是否应该被抢占,所以各个调度实现了自己的响应节拍的方法,由调度类的 task_tick() 方法,这里主要介绍CFS类的 task_tick_fair() 方法。

static void task_tick_fair(struct rq *rq, struct task_struct *curr)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &curr->se;
	/* 遍历调度实体,如果是非组调度,则仅循环一次,
	 * 否则向顶层的父调度实体遍历*/
	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
		/* 更新运行时统计信息*/
		update_curr(cfs_rq);

		/*判断当前进程是否能被抢占*/
		if (cfs_rq->nr_running > 1)
			check_preempt_tick(cfs_rq, curr);
	}
}

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 now = rq_of(cfs_rq)->clock;
	unsigned long delta_exec;
	unsigned long delta_exec_weighted;

	delta_exec = (unsigned long)(now - curr->exec_start);

	/*(累加)统计信息*/
	curr->sum_exec_runtime += delta_exec;
	delta_exec_weighted = delta_exec;
	/* 累加虚拟运行时间
	 * 1. 如果是 0 nice 的进程,虚拟运行时间即为真实运行时间
	 * 2. 否则使用权重计算得到 与优先级成反比的虚拟运行时间(权重越大增长得越慢)
	 * 计算公式 curr−>vruntime += delta_exec * NICE_0_LOAD / curr−>se−>load.weight
	 */
	if (unlikely(curr->load.weight != NICE_0_LOAD)) {
		delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
							&curr->load);
	}
	curr->vruntime += delta_exec_weighted;

	...

	/*重置启动时间*/
	curr->exec_start = now;
}

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	unsigned long ideal_runtime, delta_exec;

	/*计算理想的运行时间(片)*/
	ideal_runtime = sched_slice(cfs_rq, curr);
	/*计算实际的运行时间*/
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
	/*如果时间运行时间大于理想的运行时间,则应该被抢占(让出CPU)*/
	if (delta_exec > ideal_runtime)
		resched_task(rq_of(cfs_rq)->curr);
}

CFS的分时是将降低当前运行进程对其他待调度进程造成的延迟为目标的调度算法,在一定的调度周期内,调度队列内所有的进程都被调度运行一次,即公平对待每个进程。从 update_curr() 函数可以得知每次时钟中断都会增加运行进程的虚拟运行时间,如果是进程的权重是 NICE_0_LOAD (即进程的 nice 值为120的默认值),那么虚拟运行时间就是真实运行时间。一旦进程改变其 nice 值,内核才会使用静态表将真实运行时间进行一个成反比的转换,然后才进行累加,就会出现 nice 值越小虚拟运行时间增长得越慢,而进程是以虚拟运行时间为键组织在一棵红黑树中,调度框架每次从最左边的进程开始调度(相当于排队),高优先级的进程有更多机会靠近左边,但是运行中的进程虚拟时间增加,而排队的进程虚拟时间不变,每次时钟到来后,都检查当前的真实时间是否达到了理想的运行时间,这个理想运行时间是通过 sched_slice() 计算得到的,相当于它将一定调度周期的时间(称为调度延迟,由sysctl_sched_latency控制)按进程各自的权重在调度队列中进程权重总和的占比进行CPU时间配额的分配,一旦超过理想运行时间,就使用 resched_task() 进行标记,随后进程被抢占。通过这样的手段可以保证排队的进程在一定延迟时间内都能被调度运行一次,因为红黑树中的进程总是向左移动的。

static void resched_task(struct task_struct *p)
{
	int cpu;

	/*已经处于重新调度的状态*/
	if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
		return;
	/*设置调度标志*/
	set_tsk_thread_flag(p, TIF_NEED_RESCHED);

	/*如果是本地CPU,则将在下一个时钟到来时被调度*/
	cpu = task_cpu(p);
	if (cpu == smp_processor_id())
		return;

	/* 如果目标进程被CPU轮训了,也不做任何操作,
	 * cpu_idle() 会在 swapper 进程被调度期间轮训查看可用进程
	 * 否则发起CPU间中断,强制将进程陷入内核中断中,以便立马被调度
	 */
	if (!tsk_is_polling(p))
		smp_send_reschedule(cpu);
}

主调度器

所有调度器都依赖主调度器,它不仅负责如何处理当前运行进程和如何选择下一个运行的进程,还负责进程上下文的切换。

void __sched schedule(void)
{
	struct task_struct *prev, *next;
	struct rq *rq;
	int cpu;

need_resched
	...
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	/*标记CPU经过了一个静默周期*/
	rcu_qsctr_inc(cpu);
	prev = rq->curr;

	...
	/*发送切换时,需要更新运行队列的虚拟时钟*/
	__update_rq_clock(rq);
	...

	/*判断是否为主动放弃CPU*/
	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
				unlikely(signal_pending(prev)))) {
			/*可中断,且有信号需要处理*/
			prev->state = TASK_RUNNING;
		} else {
			/*否则失效进程*/
			deactivate_task(rq, prev, 1);

			...
		}
	}

	/*负载均衡*/
	if (unlikely(!rq->nr_running))
		idle_balance(cpu, rq);

	/*调用进程所属的调度类,重新放置运行当前运行的进程*/
	put_prev_task(rq, prev);
	/*更加调度类选择最优进程进行调度,可能是其他调度的进程*/
	next = pick_next_task(rq, prev);

	/*清除重新调度的标志*/
	clear_tsk_need_resched(prev);

	if (likely(prev != next)) {
		rq->curr = next;
		/*上下文切换*/
		context_switch(rq, prev, next); /* unlocks the rq */
	}

	...

	/*因为运行队列解锁了,所以其他路径可能发起了强制抢占刚换入的进程*/
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
		goto need_resched;
}

每次切换时都会更新进程和调度框架本身相关的时间等属性,虽然从周期调度器来看,这一步有些多余,因为在 scheduler_tick() 中已经调用过此函数,在没有经历一个时钟周期的情况下再次调用,肯定是没有效果的,但是 schedule() 可以被主动调用,如果恰好在时钟周期经历过一半时间时发生切换,那么运行队列的和正在运行的进程的时间属性会丢失精度,对于CFS来说肯定有不公平的调度发生。

如果进程是主动放弃CPU,并且其状态是非 TASK_RUNNING 状态,那么需要将进程从调度队列的管理中移除,内核通过调度框架函数 deactivate_task() 来调用进程对应调度类的 dequeue_task() 实现函数,因为其调度队列的组织结构不同,统计信息也不相同;由于在此处调用时,参数是运行进程,而运行进程本本身不在调度队列里,所以只是简单的更新统计信息,并不会有真正的出队列的操作(但在其他的地方调用会有),对于 CFS 的实现为 dequeue_task_fair()

static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep)
{
	/*如果处于不可中断状态,则增加统计*/
	if (p->state == TASK_UNINTERRUPTIBLE)
		rq->nr_uninterruptible++;

	p->sched_class->dequeue_task(rq, p, sleep);
	p->se.on_rq = 0;

	/*进程离开了运行队列,管理的进程数和总的权重需要减少*/
	rq->nr_running--;
	rq->load -= p->se.load.weight;
}

static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;

	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
		/*
		 * 为运行或休眠更新虚拟时钟
		 */
		update_curr(cfs_rq);

		/* 与以往调度的有区别
		 * 非运行的进程在调度队列上,而在运行的进程不在调度队列上
		 * idle 进程永远都不在调度队列上
		 * 不为运行进程则从红黑树中移除
		 */
		if (se != cfs_rq->curr)
			__dequeue_entity(cfs_rq, se);

		/*进程离开了调度队列,管理的进程数和总的权重需要减少*/
		cfs_rq->load -= se->load.weight;
		cfs_rq->nr_running--;
		se->on_rq = 0;

		...
	}
}

但是如果进程还处于 TASK_RUNNING 状态,则需要再次排队,该动作又 put_prev_task() 实现,与 deactivate_task() 一样,都是框架函数,CFS 的实现为 put_prev_task_fair(),从实现中可以看到 prev->se.on_rq 是指示进程是否被调度队列和运行队列管理,而非单纯的表示是否在调度队列的用于排队进程的数据结构中。

static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
	struct sched_entity *se = &prev->se;
	struct cfs_rq *cfs_rq;

	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);

		/* 如果还处于运行状态,即没有调用
		 * deactivate_task()/dequeue_task() 弹出队列
		 */
		if (prev->se.on_rq) {
			/* 需要更新时间属性 */
			update_curr(cfs_rq);
			/* 将当前运行的进程重新插入调度队列中 */
			__enqueue_entity(cfs_rq, &prev->se);
		}
		/*当前操作的运行进程再次排队,所以需要重置运行进程*/
		cfs_rq->curr = NULL;
	}
}

在调度框架将当前运行的进程再次排队或移除后,需要根据进程属于不同的调度类选择一个最优的进程来使用CPU资源,其规则就是从最好优先级的调度类开始查找,如果存在一个这样的进程就将其选择为即将运行的进程。这通过 pick_next_task() 框架函数来实现的,对于 CFS 的实现为 pick_next_task_fair()。从实现可以看出内核优先选择实时进程,如果没有再选择普通进程,如果所有的普通进程都在休眠,那么才会选择各自的 swapper 零号进程。

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
	const struct sched_class *class;
	struct task_struct *p;

	/* 优化:我们知道所有的进程都在CFS中,则我们直接调用该类的pick函数 */
	if (likely(rq->nr_running == rq->cfs.nr_running)) {
		p = fair_sched_class.pick_next_task(rq);
		if (likely(p))
			return p;
	}

	/* 否则按系统约定的,从最高优先级的调度类开始,
	 * 依次遍历查找一个优先的进程用于调度
	 */
	class = sched_class_highest;
	for ( ; ; ) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
		class = class->next;
	}
	/*用于不可能返回NULL,因为有idle进程的存在*/
}

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;

	if (unlikely(!cfs_rq->nr_running))
		return NULL;

	/*组调度相关*/
	do {
		if (first_fair(cfs_rq)) {
			se = __pick_next_entity(cfs_rq);
			if (se->on_rq) {
				/*出队列*/
				__dequeue_entity(cfs_rq, se);
				/*更新开始运行时间*/
				se->exec_start = rq_of(cfs_rq)->clock;
				/*将调度队列的当前运行进程设置为新选择的进程*/
				cfs_rq->curr = se;
				/*保存上次运行的总时间*/
				se->prev_sum_exec_runtime = se->sum_exec_runtime;
			}
		}
		/*如果父级调度队列中没有,则查看自己调度队列中的进程,知道找到一个可用进程*/
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);

	return task_of(se);
}

接下来就是切换上下文,在切换前必须调用 clear_tsk_need_resched() 清零 TIF_NEED_RESCHED ,而且有可能选择的进程还是当前运行的进程,所以可能并不会发送上下文切换,切换一旦完成,后续的代码就是在另外一个进程上下文中运行了,这看上去有些奇怪。上下文切换和硬件架构有直接关系,由 context_switch() 实现核心代码采用汇编编写,严格说来其实这部分不属于调度框架,主要有以下的动作:

  1. 切换内存虚地址空间的切换。如果是用户进程才会真正发生虚地址的切换,而如果是内核线程,仅做一个标记,此后不再响应IPI来带的TLB刷新动作。
  2. CPU硬件上下文的切换,主要是寄存器的状态的保存于恢复,不同CPU架构肯定实现不同。
  3. 完成切换 finish_task_switch() ,如果需要会真正的是否虚地址内存描述符和进程描述符,因为只有完成切换后,才能真正的结束对他们的引用。

到此最后就算完成两个进程之间的调度切换了,但是由于现在内核是可并发、可抢占的,所以还要再次检查新运行进程的调度标志,如果需要调度会立马又被抢占的要求放弃CPU的使用,因为内核可能从其他CPU上要求该进程放弃。

唤醒进程

在进程让出CPU后,如果需要及时的再次让其运行,可以使用 try_to_wake_up() 主动唤醒它,并且如果以非 TASK_RUNNING 调度出去的进程,从上面的主调度器的实现可获知,此时进程不处于排队状态,而不处于排队状态就永远不会获得运行的机会(不允许运行的进程,甚至连 kill -9 pid 都不会响应,也就没办法终止它们),所以主动唤醒它是唯一的途径。综上,此函数的主要功能就是再次将没有排队的进程重新插入相应的调度队列中,并更新统计信息等。

static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
{
	int cpu, orig_cpu, this_cpu, success = 0;
	unsigned long flags;
	long old_state;
	struct rq *rq;

	...

	rq = task_rq_lock(p, &flags);
	old_state = p->state;
	/*不处于期望的状态*/
	if (!(old_state & state))
		goto out;

	/*已在调度队列中,仅重置为运行态标记即可*/
	if (p->se.on_rq)
		goto out_running;

	cpu = task_cpu(p);
	orig_cpu = cpu;
	this_cpu = smp_processor_id();

#ifdef CONFIG_SMP
	/*正在运行(运行的进程不在调度队列中),仅重新激活*/
	if (unlikely(task_running(rq, p)))
		goto out_activate;

	/* 选择新的运行CPU,可能因负载平衡而发生迁移
	 * 如果不发送迁移,那么还是使用以前的CPU来运行该进程
	 * 这样可以更好的利用缓存信息
	 */
	new_cpu = cpu;

	/*负载均衡相关*/
	...

out_set_cpu:
	/*在空闲CPU上唤醒是最优选择*/
	new_cpu = wake_idle(new_cpu, p);
	if (new_cpu != cpu) {
		/*重新设置进程的运行CPU(运行队列)*/
		...
	}

out_activate:
#endif /* CONFIG_SMP */

	/*更新运行队列的虚拟时钟*/
	update_rq_clock(rq);
	/*激活进程,即再次插入到调度队列中*/
	activate_task(rq, p, 1);
	/* 调用进程所属的调度类的方法,
	 * 判断是否应该抢占进程的目标运行队列正在运行的进程
	 */
	check_preempt_curr(rq, p);
	success = 1;

out_running:
	p->state = TASK_RUNNING;
out:
	task_rq_unlock(rq, &flags);

	return success;
}

主要的动作就是更新目标运行进程的时间属性、排队进程、检查抢占等。

update_rq_clock() 更新运行队列的时间属性,因为可能发生强制抢占,而此时时间中断没有正确更新运行队列的虚拟节拍,可能就会导致新排队的进程在计算虚拟时间时发生错误,从而导致不公平的对待所有的进程。

activate_task() 排队进程到调度队列中,这与 deactivate_task() 一样是框架函数,CFS类由 enqueue_task_fair() 实现。

static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)
{
	/*如果被唤醒的进程是非中断状态,则修改统计*/
	if (p->state == TASK_UNINTERRUPTIBLE)
		rq->nr_uninterruptible--;

	/* 1. 入队列(根据被唤醒进程的调度类的具体实现而定),
	 * 2. 累加运行队列的总就绪进程数和总负载
	 */
	p->sched_class->enqueue_task(rq, p, wakeup);
	p->se.on_rq = 1;

	rq->nr_running++;
	rq->load += p->se.load.weight;
}

static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
{
	u64 vruntime;
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;

	for_each_sched_entity(se) {
		if (se->on_rq)
			break;
		cfs_rq = cfs_rq_of(se);

		/*
		 * 更新当前运行进程的虚拟时钟,应为它可能被抢占而得不到应有的更新
		 */
		update_curr(cfs_rq);

		if (wakeup) {
			/*从休眠中唤醒目标进程,为了排队计算一个新的虚拟时间*/
			place_entity(cfs_rq, se, 0);
		}

		/*入队列*/
		if (se != cfs_rq->curr)
			__enqueue_entity(cfs_rq, se);

		/*更新调度队列的统计信息*/
		cfs_rq->load += se->load.weight;
		cfs_rq->nr_running++;
		se->on_rq = 1;

		wakeup = 1;
	}
}

在排队中最重要的函数就是 place_entity() ,其名字有些歧义,它的主要功能就是为新排队的进程计算一个合适的、利于公平调度的虚拟时间,以使其在红黑树中有一个正确的位置。
因为休眠或新的进程它的虚拟时间一直没有向前推进,而已排队的进程虚拟时间却一直在推进,所以当休眠或新进程插入红黑树时,势必会很靠前,即使他运行许多周期之后还是小于其他进程的虚拟时间,这样肯定会将其他进程饿死,所以对休眠的进程进行一些运行时间补偿,但又不能将其他进程饿死,是该函数的核心思路。内核以当前调度队列的最小虚拟时间为基础,根据配置特性在该值上加减一小段时间来调整新排队进程的虚拟时间。

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
	u64 vruntime;

	vruntime = cfs_rq->min_vruntime;

	if (sched_feat(TREE_AVG)) {
		/*树中最大和最小虚拟时间的平均值*/
		struct sched_entity *last = __pick_last_entity(cfs_rq);
		if (last) {
			vruntime += last->vruntime;
			vruntime >>= 1;
		}
	} else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running) {
		/*树中所有权重下平分一定调度延迟的时间片*/
		vruntime += sched_vslice(cfs_rq)/2;
	}

	/*新创建的进程,责罚一个平均延迟*/
	if (initial && sched_feat(START_DEBIT))
		vruntime += sched_vslice_add(cfs_rq, se);

	if (!initial) {
		/* 休眠进程稍微补偿一些*/
		if (sched_feat(NEW_FAIR_SLEEPERS) && entity_is_task(se))
			vruntime -= sysctl_sched_latency;

		/* ensure we never gain time by being placed backwards. */
		vruntime = max_vruntime(se->vruntime, vruntime);
	}

	se->vruntime = vruntime;
}

创建进程

新创建的进程还从来没有参与过调度,所以需要特殊的函数来初始化、首次唤醒和切换,内核分别用 sched_fork()wake_up_new_task()schedule_tail() 来处理这些特殊情况。

内核通过从父进程那里继承一些调度属性,来初始化新进程的调度属性,通过 sched_fork() 完成。一般情况下,子进程都和父进程在同一个CPU上运行,除非此时有空闲的CPU或CPU处于严重的不平衡,才会选择出一个新的合适的CPU作为子进程的目标CPU;由于子进程继承了父进程的虚拟时间,当子进程被迁移到其他CPU上后,其他虚拟时间就和所在的调度队列的最小虚拟时间不匹配,如果不调整就会发生不公平的调度,内核会以两个调度队列的最小虚拟时间差来调整子进程虚拟时间。在父进程运行的过程中,有时会发生优先级临时提升的情况,比如正在处理实时互斥量,为了子进程不会继承这个临时的状态来以提升自己的优先级而造成安全隐患,内核将子进程的动态优先级还原。以上这两点就是 sched_fork() 的主要工作。

void sched_fork(struct task_struct *p, int clone_flags)
{
	/*如果没有负载均衡,则新进程与父进程在同一个CPU上运行*/
	int cpu = get_cpu();

	/*初始化调度实体*/
	p->se.exec_start = 0;
	p->se.sum_exec_runtime = 0;
	p->se.prev_sum_exec_runtime = 0;
	p->se.on_rq = 0;

	/*保证不会被意外的唤醒,因为它已在运行状态(假的)*/
	p->state = TASK_RUNNING;

#ifdef CONFIG_SMP
	/*自平衡,选择一个负载小的CPU来作为新进程的CPU*/
	cpu = sched_balance_self(cpu, SD_BALANCE_FORK);
#endif

	/*调整虚拟时间*/
	struct cfs_rq *old_cfsrq = &task_rq(p)->cfs;
	struct cfs_rq *new_cfsrq = &cpu_rq(cpu)->cfs;

	/* 从上层函数中继承父进程的虚拟时间 :
	 *		p->se.vruntime = parent->se.vruntime;
	 * 由于新调度队列与原调度队列虚拟时间可能不同步
	 * 调整这个差值,防止不公平发生
	 */
	p->se.vruntime -= old_cfsrq->min_vruntime -
					 new_cfsrq->min_vruntime;

	/*设置CPU*/
	task_thread_info(p)->cpu = cpu;

	/*继承原始优先级*/
	p->prio = current->normal_prio;
	if (!rt_prio(p->prio))
		p->sched_class = &fair_sched_class;

	/*配合首次切换*/
	task_thread_info(p)->preempt_count = 1;
	put_cpu();
}

通过 wake_up_new_task() 进行首次唤醒,将进程排队到调度队列是主要的任务,每个调度类可能不同实现,对于没有 实现 task_new() 的调度类就使用 调度框架 函数 activate_task() 进行简单的入队列操作,否则使用特有的调度类 task_new() 来处理。对于CFS有 task_new_fair() 来处理普通进程的首次入队列操作。在入队列后,由于子进程可能被迁移到其他CPU,而其他CPU上正在运行的进程比此子进程的优先级低,所以再使用调度框架函数 check_preempt_curr() 来检查和处理这种情况。 task_new_fair() 主要完成入队列,和在父子进程返回用户态时,是否应该让子进程优先于父进程运行,默认是子进程滞后,那么它从父进程继承而来的虚拟时间会有一个增加(责罚),但如果配置(sysctl_sched_child_runs_first)需要让子进程先运行,则简单的交换它们的虚拟时间即可,当然这一切只会在父子进程将在同一个CPU上运行时会这样去考虑。

void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
{
	unsigned long flags;
	struct rq *rq;

	rq = task_rq_lock(p, &flags);
	/*可能发生强制抢占,更新运行队列的时间*/
	update_rq_clock(rq);

	/*计算动态优先级,基本上只会影响实时进程*/
	p->prio = effective_prio(p);

	/*入队列*/
	if (!p->sched_class->task_new || !current->se.on_rq) {
		activate_task(rq, p, 0);
	} else {
		p->sched_class->task_new(rq, p);
		rq->nr_running++;
		rq->load += p->se.load.weight;
	}
	/*检查是否应该抢占*/
	check_preempt_curr(rq, p);
	task_rq_unlock(rq, &flags);
}

static void task_new_fair(struct rq *rq, struct task_struct *p)
{
	struct cfs_rq *cfs_rq = task_cfs_rq(p);
	struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
	int this_cpu = smp_processor_id();

	/*可能发生强制抢占,更新调度队列的时间*/
	update_curr(cfs_rq);
	/*计算子进程的虚拟时间,有一定的时间惩罚,即默认是子进程滞后父进程运行*/
	place_entity(cfs_rq, se, 1);
	/*如果配置需要,则将子进程放置在父进程前运行,简单交换虚拟运行时间即可*/
	if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
			curr && curr->vruntime < se->vruntime) {
		swap(curr->vruntime, se->vruntime);
	}
	/*入队列*/
	enqueue_task_fair(rq, p, 0);
	/* 抢占当前运行的进程,
	 * CFS类的进程在 fork() 之后肯定会抢占子进程所在队列上的运行进程
	 * 虽然可能被抢占的进程又会立马被调度(比如被抢占的进程是一个实时进程)
	 */
	resched_task(rq->curr);
}

通过 schedule_tail() 来完成第一切换,虽然这个函数非常的简单,但调用它的这个过程一个非常特别的事情。虽然子进程复制了父进程的所有状态,但是调度相关的信息却是特有的,从这个方面的来看,子进程是从来没有调度过的,所以不能像不同切换一样简单的将其上下文恢复到上次切换的状态,因为它根本就没有切换过。内核通过在 do_fork() 创建子进程的过程中给其标识一个特殊的标志 TIF_FORK(存储在 struct thread_infoflags 字段中),在首次进程调用 switch_to() 进程切换上下文时,内核一旦发现进程带有此标志(使用的是 test_and_clear_bit() 类似的操作),就强制跳转到汇编函数 ret_from_fork() 来完成子进程首次运行并返回用户态或内核态的任务。在此函数中调用 schedule_tail() 完成切换后的工作,而对于用户态的子进程 ret_from_fork() 强制设置 eax0 值,这个寄存器是系统调用存储返回值的地方,在此处就是 fork() 系统调用的返回值,所以就造成了 一次系统调用 返回两个不同的值,父进程返回子进程的进程号,子进程返回 0 。这样在用户态就形成了一个分叉的逻辑流,这也是 fork 命名的来源;对于内核态的线程,ret_from_fork() 就抹去内核栈的原来数据(因为此时内核栈还保存了父进程的状态)和去装载特殊的执行回调函数,然后执行。

void schedule_tail(struct task_struct *prev)
{
	struct rq *rq = this_rq();

	/*prev 为让出CPU给子进程运行的进程*/
	finish_task_switch(rq, prev);
	if (current->set_child_tid)
		put_user(task_pid_vnr(current), current->set_child_tid);
}
没有更多推荐了,返回首页