进程调度

2015-7-28 chenhui 进程管理

调度流程:

  1. 时间片被减为0,TIF_NEED_RESCHED 被设置,开始调度
  2. 若当前CPU的运行队列没有进程,就从其他CPU运行队列中取,如果还是没有,选中 idle 进程
  3. 从当前CPU的运行队列(包括活动队列和过期队列)中取出一个待运行的目标进程
  4. 取消 TIF_NEED_RESCHED,防止下次中断再次进入调度
  5. 取出目标进程的页表基地址,并存入 CP15 协处理器,这样就是切换进程地址空间
  6. 把当前寄存器(R0-R15、PC)的状态保存到当前进程的内核栈
  7. 把保存在目标进程内核栈里的寄存器状态写到当前寄存器,包括PC值,这样就跳到目标进程运行了

操作系统的多进程是由每个进程轮流执行实现的,控制这个轮流执行的行为称为进程调度。

在 Linux 中,进程调用有两个结构体是至关重要的,一个是 runqueue_t,另一个是 prio_array_t。


runqueue_t 代表一个进程的运行队列,这个运行队列在系统中的数量是固定的,和处理器个数相同,这是为了支持 SMP。

其定义如下:


struct runqueue { 

	/* 保护进程链表的自旋锁*/ 
	spinlock_t lock;
	
	/* 进程链表中可运行进程的数量。 */
	unsigned long nr_running;

	/* CPU执行进程切换的次数。*/
	unsigned long long nr_switches;
	
	/* 先前在运行队列链表中而现在 睡眠在TASK_UNINTERRUPTIBLE状态的进程的数量。*/
	unsigned long nr_uninterruptible;

	/* 过期队列中最老的进程被插入队列的时间。*/
	unsigned long expired_timestamp;
	
	/* 最近一次定时器中断的时间戳的值。*/
	unsigned long long timestamp_last_tick;
	
	/**
	 * curr-当前正在运行进程的进程描述符指针(对于本地CPU来说,它与current相同)。
	 * idle-当前CPU的idle进程的进程描述符指针。
	 */
	task_t *curr, *idle;
	
	/* 在进程切换期间用来存放被替换进程的内存描述符的地址。*/
	struct mm_struct *prev_mm;
	
	/**
	 * active-指向活动进程的链表数组,活动进程即没有用完时间片的进程
	 * expired-指向过期进程的链表数组,过期进程即已用完时间片的进程
	 * arrays-活动进程和过期进程的两个集合
	 */
	prio_array_t *active, *expired, arrays[2];
	
	/* 过期进程中静态优先级最高的进程(权值最小) */
	int best_expired_prio; 
	
	/* 先前在运行队列的链表中,而现在正等待IO操作结束的进程的数量。 */
	atomic_t nr_iowait; 
};


上面的 active 和 expired 以及 arrays[] 这三个字段非常重要,是进程调度的关键字段。


要搞清楚这三个字段,必须得先搞清楚他们的类型。arrays[2] 是个 prio_array_t 数组,长度为 2,他是真正用来存放活动进程队列和过期进程队列的。而 active 和 expired 则是 prio_array_t 指针,他们本身只是指针,真正的数据并不保存在他们这里。


那么真正的数据保存在哪?很明显,就是 array[2] 这个数组,一开始 active 指向 arrays[0],而 expired 则指向arrays[1],即活动进程被放到 arrays[0],过期进程则放在 arrays[1]。每一个进程的时间片用完,他都会被活动队列里取出放到过期队列里,而当活动进程的进程全部过期时(时间片全部用完),active就会立刻指向存放了所有过期进程的 expired,因为他们只是时间片用完了,只是暂时不允许运行,所以所有的进程用完时间片后,自然就要重新开始,而原来的活动进程队列又会被 expired 使用,成为存放过期进程队列的地方,直到所有活动进程再次用完时间片


由上又可引出另一个重要的结构体:prio_array_t 。即真正代表一个队列的结构体。

其定义如下:


struct prio_array {

	/* 链表中进程描述符的数量。*/
	unsigned int nr_active;
	
	/* 优先权数组,位数和MAX_PRIO相同。某优先权的进程链表不为空时设置相应的位。 */
	unsigned long bitmap[BITMAP_SIZE];
	
	/* 140个优先权队列的头结点,该数组里每一个成员对应一个进程。*/
	struct list_head queue[MAX_PRIO];
};


prio_array 其实很简单,因为 Linux 的进程要按照优先级来进行调度,优先级越低越容易得到处理器资源。


根据优先级的不同,把不同的进程存放在 queue 这个数组里,这个数组是一个链表数组,可以看出每一个优先级都对应一个进程队列。


看来了两个数据结构,再来看看进程调度的初始化。在内核初始化的 start_kernel() 函数里调用了 sched_init() 来初始化系统的调度子系统。


void __init sched_init(void)
{
	runqueue_t *rq;
	int i, j, k;

	prio_array_t *array; 
	
	for (i = 0; i < NR_CPUS; i++) {
		//每个处理器都有自己的 prio_array_t ,这里遍历所有处理器
		
		//取出当前处理器的 prio_array_t
		rq = cpu_rq(i);			
		
		//初始化运行队列锁
		spin_lock_init(&rq->lock);	
		
		//活动进程队列指向 arrays[0]
		rq->active = rq->arrays;	
		
		//过期进程队列指向arrays[1]
		rq->expired = rq->arrays + 1;
		
		//初始化过期进程中优先级最高的,现在还没有进行任务调度呢,所以就弄个MAX_PRIO
		rq->best_expired_prio = MAX_PRIO;
		
		atomic_set(&rq->nr_iowait, 0);	
		
		for (j = 0; j < 2; j++) {
			/* 遍历arrays[]数组,其实就是遍历初始化运行队列和过期队列*/ 
			
			//指向当前的arrays[index]
			array = rq->arrays + j;  
			
			for (k = 0; k < MAX_PRIO; k++) { 
				//初始化当前队列的优先级数组
				
				//初始化当前循环到的链表
				INIT_LIST_HEAD(array->queue + k); 
				
				//bitmap的某位被使用时,才意味着对应优先级被使用
                                //这里没有一个优先级被使用,自然就要把他们全部清零
				__clear_bit(k, array->bitmap);
			}
			
			//这里把最高优先级占用,因为最高优先级是 idle 进程的,所以不让他们用
			__set_bit(MAX_PRIO, array->bitmap);
		}
	}
	
	// idle 进程使用的是最基础的页表,所以mm_count + 1,加的就是这个页表
	atomic_inc(&init_mm.mm_count);
	
	//把当前进程初始化为 idle 进程
	init_idle(current, 0);
}


调度子系统的初始化就这么完成了,那么系统会在什么时候执行调度呢?

很简单,当然是时间片被减为 0 的时候执行的调度,那么时间片又是什么被减的呢?答案是时钟中断,每来一次时钟中断,就会把当前运行的进程的时间片减一,减到 0 之后就会给当前进程设置一个标签,然后在时钟中断结束时执行调度。


关于时钟中断相关内容,请看:中断三部曲之中断处理程序的实现 这篇文章的结尾提供了时钟中断的注册到递减时间片的详细流程。


如果你看了上面那篇文章,你就会知道,一旦时间片被减为 0 可以执行调度,那么在 ret_to_user 子程序中就会执行调度,下面是相关代码片段:


ENTRY(ret_to_user)
ret_slow_syscall:
	disable_irq r1				@ disable interrupts
	ldr	r1, [tsk, #TI_FLAGS]
	tst	r1, #_TIF_WORK_MASK
	bne	work_pending
no_work_pending:
	slow_restore_user_regs


4~6 行,读出进程的 task_struct 描述符的 flags 字段。如果需要调用,那么这里会存放 TIF_NEED_RESCHED 标记。如果存放了,就调用 work_pending 这个子进程。

继续看 work_pending:


work_pending:
	tst	r1, #_TIF_NEED_RESCHED
	bne	work_resched
	tst	r1, #_TIF_NOTIFY_RESUME | _TIF_SIGPENDING
	beq	no_work_pending
	mov	r0, sp				@ 'regs'
	mov	r2, why				@ 'syscall'
	bl	do_notify_resume
	disable_irq r1				@ disable interrupts
	b	no_work_pending


work_pending 很简单,就是看看上面读出的 flags 字段是否设置 TIF_NEED_RESCHED,如果设置了,那么就跳到 work_resched 进行调度。

下面是 work_resched 的实现:


work_resched:
	bl	schedule


这就到了重头函数:schedule()。这个函数是调度的核心。

schedule() 比较长,下面分段来分析(去掉了部分代码,力求简洁易懂)。


void __sched schedule(void) 
{
	long *switch_count;
	
	//prev指向当前进程,即被替换出去的进程
	task_t *prev;
	
	//next指向被选中的进程,这个进程将取代当前进程在CPU上执行。
	//如果系统中没有优先级高于当前进程,那么next会和current相等。不发生任何切换。
	task_t *next;
	
	runqueue_t *rq;
	prio_array_t *array;
	struct list_head *queue;
	unsigned long long now;
	unsigned long run_time;
	int cpu, idx;
 
	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
	
need_resched:
	//此处需要禁止抢占,因为后面需要访问任务的运行队列。 
	preempt_disable();


上面是 schedule() 的一些变量定义,其中最需要关心的是 prev 和 next 这两个指针。

	...

	cpu = smp_processor_id();
 	//取出当前 CPU 。
 	
	if (unlikely(!rq->nr_running)) { 
	//如果当前运行队列里没有可运行的进程了
go_idle:
 
		idle_balance(cpu, rq);
		//运行队列中没有可运行的进程存在,调用idle_balance()。
		//他会从另一个处理器的运行队列迁移一些可运行进程到本地运行队列中。
		
		if (!rq->nr_running) { 
			//如果迁移后依然没有可运行的进程
			
			next = rq->idle;
			//把 next 设为当前队列的 idle 进程,即准备运行 idle 进程
			
			rq->expired_timestamp = 0;
			//初始化过期队列的最老插入进程时间

                if (!rq->nr_running)
			//再次判断有没有运行进程,如果没有了,则开始运行 idle 进程。
			goto switch_tasks;
		}
	} else {
		//当前运行队列里有可以运行的进程,这里什么都不做

		...
		if (unlikely(!rq->nr_running))
			//再次判断有没有运行进程,如果没有了,则跳回到上面重新操作
			goto go_idle;
	}

	/* 运行到此,说明运行队列中有线程可被运行。 */


上面这段代码非常关键!他查找是否有进程可运行,如果有则说明可以挑出一个运行,如果没有,就尝试在其他处理器的运行队列里寻找,如果还是没有,就会运行 idle 进程。


	array = rq->active;
	//取出当前运行队列的活动进程链表
	
	if (unlikely(!array->nr_active)) {
		//检查是否有进程可被运行,如果又没有了就进入


		/* 到了这里就说明,活动队列中没有可运行进程了。交换活动集合和过期集合。 */
 
		rq->active = rq->expired;
		//把活动进程链表指向过期进程链表
		
		rq->expired = array; 
		//过期进程链表指向活动进程链表
		
		array = rq->active;
		//取出活动进程链表
		
		rq->expired_timestamp = 0;
		//初始化过期队列的最老插入进程时间( 过期队列现在为空 )
		
		rq->best_expired_prio = MAX_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);
	//queue保存了找到的进程在活动进程队列里的链表节点,这里取出找到的那个进程的进程描述符

/* 到了这里,prev保存的肯定是当前进程,而 next 保存的就是切换到的那个进程。 */
上面这三句代码就挑出了要切换到的进程。



	next->activated = 0;
switch_tasks:
	
	/* 运行到这里,开始进行进程切换了。*/

	if (next == rq->idle)
        //如果要切换到 idle 进程,那么就递增统计计数
		schedstat_inc(rq, sched_goidle);    

    prefetch(next);
    //prefetch提示CPU控制单元把next的进程描述符的第一部分字段的内容装入硬件高速缓存。
    //这改善了schedule的性能。

    clear_tsk_need_resched(prev); 
	//清除TIF_NEED_RESCHED标志,这样下次进入中断时就不会再次进入 schedule 从而调度程序了。
 
	rcu_qsctr_inc(task_cpu(prev));
	//记录CPU正在经历静止状态。主要与RCU相关。
 
	prev->sleep_avg -= run_time;
	//减少prev的平均睡眠时间
	
	if ((long)prev->sleep_avg <= 0)
		//平均睡眠时间当然不能是负数...
		prev->sleep_avg = 0;
 
	prev->timestamp = prev->last_ran = now;
	//更新进程的时间戳

    sched_info_switch(prev, next);
    //更新调度统计值


上面这堆代码执行一些预处理操作。

接下来就要开始切换了。


    if (likely(prev != next)) { 
		//prev和next不同,需要切换 
		
		next->timestamp = now;
		//更新最近插入运行队列的时间为当前纳秒数(时间戳)
		
		rq->nr_switches++;
		//递增进程切换数

		rq->curr = next;
		//因为要切换到 next 了,自然要把当前运行的进程设为 next。
		
		++*switch_count;		
 
		prev = context_switch(rq, prev, next); 
		//context_switch执行真正的进程切换
		
		
		// =====================================
		//
		// 注意!此时进程切换已经成功,被切换的进程就卡在这个地方了
		// 当进程再次被切换进来后,以下代码被接着运行。
		// 但是此时prev并不指向当前进程,而是指代码从哪一个进程切换到本进程。
		// =====================================

		barrier();
 
		finish_task_switch(prev);
		//对前一个进程进行一些收尾工作,比如减少它的mm_struct,task_struct的引用计数等。
	} else
		/* 如果prev和next是同一个进程,就不做进程切换。 */
		spin_unlock_irq(&rq->lock);


在上面这段代码,就完成了进程的切换。

我们可以看到,进程的切换由  context_switch() 实现。


	prev = current;
	//在前几句中(context_switch之后),prev代表的是从哪个进程切换到本进程。
	//在继续进行调度之前,将prev设置成当前进程。

        /* 注意,prev现在已经是 current 了 */
    
	...
	preempt_enable_no_resched();
	//打开抢占,并检查是否需要重新调度。
	
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) 
		//如果 TIF_NEED_RESCHED 被设置,就说明需要调度程序了
		goto need_resched;
		//跳回到上面进行调度
}


上面是进程切换回来后执行的代码,整个 schedule() 就结束了。

实际上 schedule() 本身并不复杂,其实就是挑选出一个进程,然后执行 switch_context(),这个 switch_context() 才是重头戏!我们接下来再来看 switch_context()。


static inline
task_t * context_switch(runqueue_t *rq, task_t *prev, task_t *next)
{
	struct mm_struct *mm = next->mm; 
	//取出切换到的进程的内存描述符
	
	struct mm_struct *oldmm = prev->active_mm;
	//取出当前进程的内存描述符
	
	if (unlikely(!mm)) {
		//如果是切换到一个内核线程 
		
		...
	} else{
		//切换到普通进程,那么就需要切换内地址空间了。
		
		switch_mm(oldmm, mm, next);
		//切换地址空间
	}

	if (unlikely(!prev->mm)) {
		//如果当前进程是内核线程 
		...
	}

	switch_to(prev, next, prev);
	//终于可以真正的切换了。

	return prev;
}

上面这段代码我去掉了内核线程相关的内容。内核线程和普通进程不同的是他共享上一个切换的进程的进程地址空间,其他的都一样,为省篇幅就删掉了。

context_switch() 最重要的就两点,第一点是切换进程地址空间,第二点是执行 switch_to() 跳转到切换到的进程。


先来看看 switch_mm 是怎么切换进程地址空间的。


static inline void
switch_mm(struct mm_struct *prev, struct mm_struct *next,
	  struct task_struct *tsk)
{
	unsigned int cpu = smp_processor_id();
	//取出当前 CPU
	
	if (prev != next) { 
		//不相同才需要切换
		
		cpu_set(cpu, next->cpu_vm_mask);
		
		cpu_switch_mm(next->pgd, next);
		//执行真正的操作
		
		cpu_clear(cpu, prev->cpu_vm_mask);
		//清除上面的 cpu_set 设置的位
	}
}


可以看出他又调用了 cpu_switch_mm() 这个函数来进行下一步操作。

要注意,这里传入了要切换到的进程的内存描述符的 pgd 字段,这个字段保存了这个进程的一级页表的基地址(虚拟地址)。


#define cpu_switch_mm(pgd,mm) cpu_do_switch_mm(virt_to_phys(pgd),mm)

cpu_switch_mm 是一个宏,他只是简单的把刚才传入了一级页表的基地址转成物理地址,这是因为我们设置页表基地址时,设置的是物理地址而不是虚拟地址。


#define cpu_do_switch_mm(pgd,mm)	processor.switch_mm(pgd,mm)

cpu_do_switch_mm() 又是一个宏,他又调用了 processor.switch_mm() 这个函数,这个函数对于每个处理器架构来说都不一样。但对于 ARM 来说,其实大同小异。

ARM9 调用的是 cpu_arm920_switch_mm()。


ENTRY(cpu_arm920_switch_mm)
	mov	ip, #0
	mov	r1, #(CACHE_DSEGMENTS - 1) << 5	
1:	orr	r3, r1, #(CACHE_DENTRIES - 1) << 26 
2:	mcr	p15, 0, r3, c7, c14, 2		
	subs	r3, r3, #1 << 26 
	bcs	2b				
	subs	r1, r1, #1 << 5
	bcs	1b				
	mcr	p15, 0, ip, c7, c5, 0	 
	mcr	p15, 0, ip, c7, c10, 4 
	mcr	p15, 0, r0, c2, c0, 0 
	mcr	p15, 0, ip, c8, c7, 0	
	mov	pc, lr


根据 ARM 的参数传递约定,C 语言传入的第一个参数保存在 R0,也就是说页表基地址保存在 R0。

12 行,把页表基地址存入 CP15 协处理器。这样就成功切换进程地址空间了。


既然成功切换了进程地址空间,那么接下来就再来看看 switch_to 的实现。


#define switch_to(prev,next,last)					\ 
	do {									\
		last = __switch_to(prev,prev->thread_info,next->thread_info);	\
	} while (0)

他又调用了 __switch_to(),这个 __switch_to() 又是由汇编代码编写的。


ENTRY(__switch_to)	 	 
	add	ip, r1, #TI_CPU_SAVE	
	ldr	r3, [r2, #TI_TP_VALUE]
	stmia	ip!, {r4 - sl, fp, sp, lr}
	ldr	r6, [r2, #TI_CPU_DOMAIN]!

	mov	r4, #0xffff0fff
	str	r3, [r4, #-3]			@ Set TLS ptr
	mcr	p15, 0, r6, c3, c0, 0		@ Set domain register
	ldmib	r2, {r4 - sl, fp, sp, pc}

4 行,保存当前进程的寄存器上下文。

10 行,把切换的进程的寄存器上下文写入寄存器。注意这里包括了 PC,也就是说,这句代码执行完后,就跳到了这个进程运行了。


至此,进程调度就全部分析完了。


发表评论:

Copyright ©2015-2016 freehui All rights reserved