日志标签 ‘进程调度’

基于CFS算法的schedule()源码分析

2012年4月5日

内核中的调度算法在不断变化,2.4内核中的调度器是在所有的进程中选择优先级最高的进程,2.6内核前期的调度器是基于O(1)算法的,而2.6.23版本之后的内核采用CFS调度算法,并同时对调度器进行了比较大的改善。内核主要是引入了调度器类来增加调度器的可扩展性。调度器类将各种调度策略模块化,封装了对不同调度策略的具体实现。

内核中对进程调度的方法有两种,其一为周期性调度器(generic scheduler),它对进行进行周期性的调度,以固定的频率运行;其二为主调度器(main scheduler),如果进程要进行睡眠或因为其他原因主动放弃CPU,那么就直接调用主调度器。

内核的主调度器是通过schedule()实现的,该函数的主要工作就是挑选下一个应该被调度的进程next。
该函数首先禁止内核抢占,并且依次获取当前CPU编号cpu、当前CPU对应的运行队列rq、当前进程的切换次数switch_count以及当前进程的描述符prev。

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

need_resched:
	preempt_disable();
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	rcu_sched_qs(cpu);
	prev = rq->curr;
	switch_count = &prev->nivcsw;

	release_kernel_lock(prev);
need_resched_nonpreemptible:

	schedule_debug(prev);

	if (sched_feat(HRTICK))
		hrtick_clear(rq);

接下来通过update_rq_clock()更新就绪队列上的时钟,接着通过clear_tsk_need_resched()清除当前进程prev的重新调度标志TIF_NEED_RESCHED。

	raw_spin_lock_irq(&rq->lock);
	update_rq_clock(rq);
	clear_tsk_need_resched(prev);

如果当前进程是可中断睡眠状态(可运性状态TASK_RUNNING宏的值为0),但它却收到了某个唤醒它的信号,那么当前进程的标志被更新为TASK_RUNNING,等待再次被调度。否则,通过deactivate_task()将当前进程prev从就绪队列中删除。

这里的deactivate_task()根据调度类的不同实现也有所不同,但这些差异对主调度器是透明的,因为调度器类在各种调度实例和调度器之间起到了连接作用。该函数的核心语句即为:

p->sched_class->dequeue_task(rq, p, sleep);

sched_class是进程描述符中描述当前进程所属调度类的字段,通过这个字段回调钩子函数dequeue_task()。

	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		if (unlikely(signal_pending_state(prev->state, prev)))
			prev->state = TASK_RUNNING;
		else
			deactivate_task(rq, prev, 1);
		switch_count = &prev->nvcsw;
	}

	pre_schedule(rq, prev);

	if (unlikely(!rq->nr_running))
		idle_balance(cpu, rq);

通过put_prev_task()将prev进程重新插入到就绪队列合适的位置中。再通过pick_next_task()在当前的就绪队列中挑选下一个应该被执行的进程next。这两个函数都属于调度器类中的钩子函数,它们的具体实现根据调度实例的不同而不同。

	put_prev_task(rq, prev);
	next = pick_next_task(rq);

有时候,调度器所选的下一个被执行的进程恰好就是当前进程,那么调度器就不必耗费精力去执行上下文切换,但这种情况不是经常发生的。如果prev和next不是同一个进程,那么先通过sched_info_switch()更新两个进程描述符的相关字段,并且更新可运行队列的相关字段。

接下来调用context_switch()进行prev和next两个进程的上下文切换,该函数由一段汇编代码组成。

	if (likely(prev != next)) {
		sched_info_switch(prev, next);
		perf_event_task_sched_out(prev, next);

		rq->nr_switches++;
		rq->curr = next;
		++*switch_count;

		context_switch(rq, prev, next); /* unlocks the rq */
		/*
		 * the context switch might have flipped the stack from under
		 * us, hence refresh the local variables.
		 */
		cpu = smp_processor_id();
		rq = cpu_rq(cpu);
	} else
		raw_spin_unlock_irq(&rq->lock);

切换完毕后,当前的进程就是新选择的进程,它会开始执行。而被切换出去的进程重新运行时会从切换函数的下一条语句开始执行。

	post_schedule(rq);

	if (unlikely(reacquire_kernel_lock(current) < 0)) { 		prev = rq->curr;
		switch_count = &prev->nivcsw;
		goto need_resched_nonpreemptible;
	}

	preempt_enable_no_resched();
	if (need_resched())
		goto need_resched;
}

根据上述对主调度器函数源码的分析,可以总结出主调度器的主要功能如下:

1.获取当前进程的描述符以及本地CPU的运行队列

2.将当前进程prev放入可运行队列中,等待下一次被重新调度

3.在当前的可运行队列中选取下一个被调度的新进程next

4.从当前进程切换到新进程

Linux2.6进程调度分析(3)-与调度有关的函数分析

2011年4月8日

前面两篇文章从原理角度分析了进程的调度,本文将从具体的源码出发,分析与进程进程调度密切相关的几个函数。

1.时间片的分配:task_timeslice()

正如我们所知的那样,进程的时间片与进程的静态优先级有直接的关系。从代码中可以看到,根据进程静态优先级static_prio与NICE_TO_PRIO(0)的大小关系,进程时间片的分配可以分为两条路线。以下代码如无特别说明均位于linux/kernel/sched.c下。

static unsigned int task_timeslice(task_t *p)
{
	if (p->static_prio < NICE_TO_PRIO(0)) 		return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);
	else
		return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
}

NICE_TO_PRIO以及PRIO_TO_NICE宏的作用将进行nice值和进程静态优先级之间的转换。nice也用来表示进程的静态优先级,只不过它与静态优先级的大小范围不同,因此可以将nice看作是static_prio的缩影。

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio)	((prio) - MAX_RT_PRIO - 20)

目前我们已经知道普通进程的静态优先级大小范围是100到139,因此从上面的一些列宏可以得知,nice的取值范围为-20到19。

因此,NICE_TO_PRIO(0)取值为120,也就是说进程时间片分配的两条路线是根据静态优先级120进行划分的。从SCALE_PRIO宏的定义我们可以看到,该宏的作用是取两个数值(具体应该是时间片)的最大者。

#define MAX_PRIO                (MAX_RT_PRIO + 40)
#define USER_PRIO(p)		((p)-MAX_RT_PRIO)
#define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))
#define DEF_TIMESLICE		(100 * HZ / 1000)
#define MIN_TIMESLICE           max(5 * HZ / 1000, 1)
# define HZ             1000  //位于linux/include/asm-i386/param.h
#define SCALE_PRIO(x, prio) \
max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)

从上面的宏定义可知,(MAX_USER_PRIO/2)为20。当进程静态优先级小于120时,x的值为DEF_TIMESLICE*4,具体即为400ms;否则x为100ms。因此对于SCALE_PRIO宏可以用下面的公式来表达:

静态优先级<120,基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)

静态优先级>=120,基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统所规定的最小时间片大小。

2.对可运行队列的操作

在优先级数组结构prio_array中,数组queue用来表示系统中每种优先级进程所形成的可运行队列,而且过期进程和活动进程分别对应这样一个数组。

如果进程仍然处于活动进程队列中,即说明该进程的时间片未用完。当该进程的时间片用完时就需要离开活动进程队列并进入过期进程队列。可运行进程进入进程队列是通过enqueue_task函数完成的,而离开进程队列是通过dequeue_task函数完成的。

每个进程的task_struct结构中都有list_head类型的run_list字段,将进程从可运行队列中删除起始就是对双联表的操作,同时我们需要更新优先级数组结构中活动进程的数目nr_active。如果当前进程优先级所对应的可运行队列已空,那么还要清除优先级位图中该进程优先级所对应的那个位。

如果要进程某个可运行队列,所做的工作基本上跟删除相反。不过该函数首先通过sched_info_queued函数更新该进程最后进入可运行队列的时间戳,并且在最后更新该进程描述符中的array字段,该字段指向当前进程所在的优先级数组。

 static void dequeue_task(struct task_struct *p, prio_array_t *array)
  {
          array->nr_active--;
          list_del(&p->run_list);
          if (list_empty(array->queue + p->prio))
                  __clear_bit(p->prio, array->bitmap);
  }

  static void enqueue_task(struct task_struct *p, prio_array_t *array)
  {
          sched_info_queued(p);
          list_add_tail(&p->run_list, array->queue + p->prio);
          __set_bit(p->prio, array->bitmap);
          array->nr_active++;
         p->array = array;
  }

3.schedule_tick()

schedule_tick函数用来更新进程的时间片,它被调用时本地中断被禁止,该函数的具体操作如下。

1.首先通过相应的函数和宏获得当前处理器的编号、当前可运行队列和当前进程描述符就,再通过sched_clock函数获得最近一次定时器中断的时间戳。如果array没有指向本地活动进程队列,则设置TIF_NEED_RESCHED标志,以便在稍候强制进程重新调度。

void scheduler_tick(void)
{
	int cpu = smp_processor_id();
	runqueue_t *rq = this_rq();
	task_t *p = current;

	rq->timestamp_last_tick = sched_clock();

	if (p == rq->idle) {
		if (wake_priority_sleeper(rq))
			goto out;
		rebalance_tick(cpu, rq, SCHED_IDLE);
		return;
	}
	if (p->array != rq->active) {
		set_tsk_need_resched(p);
		goto out;
	}

2.由于实时进程和普通进程的调度方法不同,因此这两种进程对时间片的更新方式也有所不同,下面仅说明普通进程更新时间片的方式。如果当前进程是普通进程,则递减当前进程的时间片。
3.如果当前进程时间片用完,首先从当前活动进程集合中删除该进程,然后通过set_tsk_need_resched函数设置TIF_NEED_RESCHED标志。

接着通过effective_prio函数更新当前进程的动态优先级,在进程调度的基本原理中我们已经知道进程的动态优先级是以进程的静态优先级(static_prio)为基数,在通过bonus适当的对其惩罚或奖励。

static int effective_prio(task_t *p)
{
	int bonus, prio;

	if (rt_task(p))
		return p->prio;

	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

	prio = p->static_prio - bonus;
	if (prio < MAX_RT_PRIO) 		prio = MAX_RT_PRIO; 	if (prio > MAX_PRIO-1)
		prio = MAX_PRIO-1;
	return prio;
}

通过effective_prio函数,我们可以总结出进程动态优先级的计算规则:

动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)

再通过task_timeslice函数对当前进程重新分配时间片,因为我现在所处的分析环境是进程的时间片已经用完。然后将first_time_slice的值设置为0,说明当前进程的时间片可以用完。

上述过程的代码描述如下:

	if (rt_task(p)) {
		/*
		 *更新实时进程的时间片
		 */
	}
	if (!--p->time_slice) {
		dequeue_task(p, rq->active);
		set_tsk_need_resched(p);
		p->prio = effective_prio(p);
		p->time_slice = task_timeslice(p);
		p->first_time_slice = 0;

4.运行队列结构中的expired_timestamp字段用来描述过期进程队列中最早进程被插入队列的时间,如果本地运行队列中该字段等于0,则说明当前过期进程集合为空。因此将当前的时钟节拍赋值给该字段。

由于当前进程的时间片已经用完,因此接下来应该判定是将当前进程插入活动进程集合还是过期进程集合。可能此时你会有疑惑:既然当前进程的时间片已经用完,就应该直接插入过期进程队列,为何还要进行判断插入那个进程集合?

正如基本原理中所说的,调度程序总偏向交互进程以提高系统的响应能力。因此当交互型进程使用完时间片后,调度程序总是重新填充时间片并把它留在活动进程集合中。但调度程序并不永远都偏向交互型程序,如果最早进入过期进程集合的进程已经等待了很长时间,或过期进程的静态优先级比交互进程的静态优先级高,此时调度程序就会将时间片用完的交互进程转移到过期进程集合中。EXPIRED_STARVING宏完成的工作就是判断上述两种情况,至少其一否和,该宏就产生值1。

如果说当前进程已经移入到过期进程集合中,还需根据当前进程的优先级更新运行队列结构中的best_expired_prio字段,该字段用于记录过期进程集合中最高的静态优先级。

如果当前进程是交互进程,而且不满足EXPIRED_STARVING宏,则直接将该交互进程继续插入活动进程集合中。

		if (!rq->expired_timestamp)
			rq->expired_timestamp = jiffies;
		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
			enqueue_task(p, rq->expired);
			if (p->static_prio < rq->best_expired_prio)
				rq->best_expired_prio = p->static_prio;
		} else
			enqueue_task(p, rq->active);

5.如果当前进程并未使用完时间片,则检查当前进程的剩余时间片是否太长。如果当前进程时间片过长的话,就将该进程的时间片分成若干个更小的时间段,这样可以防止拥有较长时间片的进程长时间霸占CPU。并且调度程序会将这样的进程放入与该进程优先级所对应的活动进程队列的末尾,稍候再次对其集成调度。

	} else {
		if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
			p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
			(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
			(p->array == rq->active)) {

			requeue_task(p, rq->active);
			set_tsk_need_resched(p);
		}
	}

至此,该函数分析完毕。

Linux2.6进程调度分析(2)-调度算法

2011年4月4日

2.数据结构

O(1)调度算法通过几个数据结构可以巧妙的实现常数级的复杂度。

2.1可运行队列

调度程序每次在进程发生切换时,都要在就绪队列中选取一个最佳的进程来运行。Linux内核使用runqueue数据结构(在最新内核中该结构为rq)表示一个可运行队列(也就是就绪队列),每个CPU都有且只有一个这样的结构。该结构不仅描述了每个处理器中处于可运行状态(TASK_RUNNING)的进程链表,而且还描述了该处理器的调度信息。下面对该结构中的部分字段作详细描述。

spinlock_t lock:保护进程链表的自旋锁;
unsigned long nr_running:运行队列链表中进程数量;
unsigned long long nr_switches:CPU执行进程切换的次数;
unsigned long nr_uninterruptible:之前在运行队列链表中而现在处于重度睡眠状态的进程总数;
unsigned long expired_timestamp:过期队列中最老的进程被插入队列的时间;
unsigned long long timestamp_last_tick:最近一次定时器终端的时间;
task_t *curr:指向本地CPU当前正在运行的进程的进程描述符,即current;
task_t *idle:指向本地CPU上的idle进程描述符的指针;
struct mm_struct *prev_mm:在进程进行切换时用来存放被替换进程内存描述符的地址;
prio_array_t *active:指向可运行队列中活动链表;
prio_array_t *expired:指向可运行队列中过期链表;
prio_array_t arrays[2]:该数组的元素分别表示可运行队列中的活动进程集合和过期进程集合;
int best_expired_prio:过期进程中优先级最高的进程;

到目前为止,你可能对上述字段的理解还不是很深,最好的办法是学习完下面的内容后再回过头来重新看这些字段的用途。我们在上面说过,runqueue结构最主要的功能是描述处于可运行状态进程所组成的链表。不过,所谓的可运行队列并不是将一些列的runqueue结构连接在一些,而是由runqueue结构中的arrays数组来体现,该数组的元素为prio_array_t类型。

2.2优先级数组

O(1)算法的另一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程动态优先级的数组queue,它包含了每一种优先级进程所形成的链表。

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define MAX_PRIO                (MAX_RT_PRIO + 40)
typedef struct prio_array prio_array_t;
struct prio_array {
        unsigned int nr_active;
        unsigned long bitmap[BITMAP_SIZE];
        struct list_head queue[MAX_PRIO];
};

由于进程优先级的最大值为139,因此MAX_PRIO的最大值取140(具体的是,普通进程使用100到139的优先级,实时进程使用0到99的优先级)。因此,queue数组中包含140个可运行状态的进程链表,每一条优先级链表上的进程都具有相同的优先级,而不同进程链表上的进程都拥有不同的优先级。

除此之外,prio_array结构中还包括一个优先级位图bitmap。该位图使用一个位(bit)来代表一个优先级,而140个优先级最少需要5个32位来表示,因此BITMAP_SIZE的值取5。起初,该位图中的所有位都被置0,当某个优先级的进程处于可运行状态时,该优先级所对应的位就被置1。

因此,O(1)算法中查找系统最高的优先级就转化成查找优先级位图中第一个被置1的位。与2.4内核中依次比较每个进程的优先级不同,由于进程优先级个数是定值,因此查找最佳优先级的时间恒定,它不会像以前的方法那样受可执行进程数量的影响。

如果确定了优先级,那么选取下一个进程就简单了,只需在queue数组中对应的链表上选取一个进程即可。

2.3活动进程和过期进程

在操作系统原理课上我们知道,当处于运行态的进程用完时间片后就会处于就绪态,此时调度程序再从就绪态的进程中选取一个作为即将要运行的进程。

而在具体Linux内核中,就绪态和运行态统一称为可运行态(TASK_RUNNING)。对于系统内处于可运行状态的进程,我们可以分为三类,首先是正处于执行状态的那个进程;其次,有一部分处于可运行状态的进程则还没有用完他们的时间片,他们等待被运行;剩下的进程已经用完了自己的时间片,在其他进程没有用完它们的时间片之前,他们不能再被运行。

据此,我们将进程分为两类,活动进程,那些还没有用完时间片的进程;过期进程,那些已经用完时间片的进程。因此,调度程序的工作就是在活动进程集合中选取一个最佳优先级的进程,如果该进程时间片恰好用完,就将该进程放入过期进程集合中。

在可运行队列结构中,arrays数组的两个元素分别用来表示刚才所述的活动进程集合和过期进程集合,active和expired两个指针分别直接指向这两个集合。

关于可运行队列和两个优先级数组的关系可参考下面的图:

正如上面分析的那样,可运行队列结构和优先级数组结构使得Q(1)调度算法在有限的时间内就可以完成,它不依赖系统内可运行进程的数量。

3. 调度算法

Linux2.4版本的内核调度算法理解起来简单:在每次进程切换时,内核依次扫描就绪队列上的每一个进程,计算每个进程的优先级,再选择出优先级最高的进程来运行;尽管这个算法理解简单,但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多,花费的时间就越大,时间复杂度为O(n)。伪代码如下:

for (系统中的每个进程) {
	重新计算时间片;
	重新计算优先级;
}

而2.6内核所采用的O(1)算法则很好的解决了这个问题,该算法可以在恒定的时间内为每个进程重新分配好时间片,而且在恒定的时间内可以选取一个最高优先级的进程,重要的是这两个过程都与系统中可运行的进程数无关,这也正是该算法取名为O(1)的缘故。

3.1 O(1)中时间片的计算

O(1)算法采用过期进程数组和活跃进程数组解决以往调度算法所带来的O(n)复杂度问题。过期数组中的进程都已经用完了时间片,而活跃数组的进程还拥有时间片。当一个进程用完自己的时间片后,它就被移动到过期进程数组中,同时这个过期进程在被移动之前就已经计算好了新的时间片。可以看到O(1)调度算法是采用分散计算时间片的方法,并不像以往算法中集中为所有可运行进程重新计算时间片。

当活跃进程数组中没有任何进程时,说明此时所有可运行的进程都用完了自己的时间片。那么此时只需要交换一下两个数组即可将过期进程切换为活跃进程,进而继续被调度程序所调度。两个数组之间的切换其实就是指针之间的交换,因此花费的时间是恒定的。下面的代码说明了两个数组之间的交换:

struct prop_array *array = rq->active;
if (array->nr_active != 0) {
	rq->active = rq->expired;
	rq->expired = array;
}

通过分散计算时间片、交换过期和活跃两个进程集合的方法可以使得O(1)算法在恒定的时间内为每个进程重新计算好时间片。

3.2 O(1)中进程的选择

进程调度的本质就是在当前可运行的进程集合中选择一个最佳的进程,这个最佳则是以进程的动态优先级为选取标准的。不管是过期进程集合还是活跃进程集合,都将每个优先级的进程组成一个链表,因此每个集合就有140个不同优先级的进程链表。同时,两个集合中还采用优先级位图来标记每个优先级链表中是否存在进程。

调度程序在选取最高优先级的进程时,首先利用优先级位图从高到低找到第一个被设置的位,该位对应着一条进程链表,这个链表中的进程是当前系统所有可运行进程中优先级最高的。在该优先级链表中选取头一个进程,它拥有最高的优先级,即为调度程序马上要执行的进程。上述进程的选取过程可用下述代码描述:

struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;

prev = current;
array = rq->active;
idx = sehed_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);
if (prev != next)
	context_switch();

sehed_find_first_bit()用于在位图中快速查找第一个被设置的位。如果prev和next不是一个进程,那么此时进程切换就开始执行。

通过上述的内容可以发现,在恒定的时间重新分配时间片和选择一个最佳进程是Q(1)算法的核心。
参考:

1.深入理解LINUX内核(第三版) ;(美)博韦,西斯特 著; 陈莉君 张琼声 张宏伟译; 中国电力出版社;

2.Linux内核设计与实现;(美)拉芙(Love,R.)著,陈莉君 等译;机械工业出版社;

Linux2.6进程调度分析(1)-调度策略

2011年4月3日

对于分时操作系统而言,表面上看起来是多个进程同时在执行,而在系统内部则进行着从一个进程到另一个进程的切换动作。这样的进程并发执行涉及到进程切换(process switch)和进程调度(process scheduling)两大问题。本文主要说明Linux2.6中的普通进程调度策略(实时进程和普通进程在调度上稍有不同)问题,即系统何时进行进程切换以及选择哪一个进程进行切换。

1.调度策略

理想的进程调度目标应该是:进程响应时间尽可能的快,后台作业吞吐量高,避免某些进程出现饥饿现象,包括低优先级在内的所有进程都有被调度的可能。由此看来,进程调度的工作就是要处理好这几个方面的协调关系,使进程调度的综合性能达到最佳。

与进程调度最为密切的因素是进程的优先级,进程优先级通过一个数值来实现,每个进程都与一个值相关联。调度程序根据进程的优先级将CPU适当的分配给某一个进程。进程的优先级又跟进程的许多因素有关,接下来我们将依次分析这些因素与进程优先级的关系。

1.1进程的分类

进程可以被分为两种类型:I/O消耗型和CPU消耗型。前种类型的进程频繁使用I/O设备,并且大部分时间处于等待状态,以得到新的I/O请求,比如键盘活动等。后一种类型的进程则大部分时间都在占用CPU,对I/O设备并没有过多的需求。

为了使系统有较强的响应能力,I/O消耗型进程必须很快能被唤醒,以实现进程的切换。否则,用户会感到系统反应迟钝。对于CPU消耗型进程,由于它们常常位于后台运行,并且没有过多的I/O需求,因此系统并不需要对这类进程做出快速反应。

正如上面所说的,调度程序通常要处理好这两类进程之间的调度关系:系统既要有迅速的响应能力,又要有最大的CPU利用率(高吞吐量)。这种满足关系其实是矛盾的,如果系统要达到最大利用率,那么CPU就会被一直占用,这样就不能对I/O请求做出迅速响应。调度程序为了调和这种冲突,通常会倾向于I/O消耗型进程。也就是说,调度程序会优先调用这类进程以提高系统的响应能力,而尽量将CPU消耗型进程压后执行。但这并不意味着这类进程就被调度程序忽略。

1.2时间片

Linux的调度是基于分时技术的,多个进程以“时间多路复用”的形式运行,CPU的时间被划分成一小段,即所谓的时间片(slice)。每个进程都会得到一个时间片,在具体某个时间片内,一个进程会独享CPU时间。如果该进程在这个时间片内没有运行完毕,调度程序就会切换该进程使得其他拥有时间片的进程运行。

时间片的划分对系统来说也是一件难事,既不能过长又不能过短。过长的时间片会导致系统的响应能力下降;而过短的时间片会导致系统频繁发生进程切换,由此将带来不必要的处理器消耗。显然,I/O消耗型进程希望时间片越短越好,这样那些等待I/O的进程就能被迅速切换;而CPU消耗型进程则希望时间片越长越好,这样它们就可以一直占用CPU。因此,I/O消耗型进程和CPU消耗型进程的矛盾再一次显现出来。

Linux调度程序解决这种矛盾的方法是,提供一个较长的默认时间片,但是却提高交互进程的优先级,以使得这些进程运行的更频繁。在Linux的调度算法中,每个进程在诞生时总是继承父进程一半的时间片,而之后的时间片则是调度程序根据进程的静态优先级而分配。

1.3优先级

我们上面说过,调度程序在选取下一个执行的进程时依据的是进程的优先级。通过上面对进程的划分可以看出,不同类型的进程应该有不同的优先级。每个进程与生俱来(即从父进程那里继承而来)都有一个优先级,我们将其称为静态优先级。普通进程的静态优先级范围从100到139,100为最高优先级,139为最低优先级。

当进程用完了时间片后,系统就会为该进程分配新的时间片(即基本时间片),静态优先级本质上决定了时间片分配的大小。静态优先级和基本时间片的关系如下:

静态优先级<120,基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)
静态优先级>=120,基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统规定的最小时间片。从该计算公式可以看出,静态优先级越高(值越低),进程得到的时间片越长。其结果是,优先级高的进程会获得更长的时间片,而优先级低的进程得到的时间片则较短。

进程除了拥有静态优先级外,还有动态优先级,其取值范围是100到139。当调度程序选择新进程运行时就会使用进程的动态优先级,动态优先级和静态优先级的关系可参考下面的公式:

动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)

从上面看出,动态优先级的生成是以静态优先级为基础,再加上相应的惩罚或奖励(bonus)。这个bonus并不是随机的产生,而是根据进程过去的平均睡眠时间做相应的惩罚或奖励。

所谓平均睡眠时间(sleep_avg,位于task_struct结构中)就是进程在睡眠状态所消耗的总时间数,这里的平均并不是直接对时间求平均数。平均睡眠时间随着进程的睡眠而增长,随着进程的运行而减少。因此,平均睡眠时间记录了进程睡眠和执行的时间,它是用来判断进程交互性强弱的关键数据。如果一个进程的平均睡眠时间很大,那么它很可能是一个交互性很强的进程。反之,如果一个进程的平均睡眠时间很小,那么它很可能一直在执行。另外,平均睡眠时间也记录着进程当前的交互状态,有很快的反应速度。比如一个进程在某一小段时间交互性很强,那么sleep_avg就有可能暴涨(当然它不能超过MAX_SLEEP_AVG),但如果之后都一直处于执行状态,那么sleep_avg就又可能一直递减。

理解了平均睡眠时间,那么bonus的含义也就显而易见了。交互性强的进程会得到调度程序的奖励(bonus为正),而那些一直霸占CPU的进程会得到相应的惩罚(bonus为负)。其实bonus相当于平均睡眠时间的缩影,此时只是将sleep_avg调整成bonus数值范围内的大小。

参考:

1.深入理解LINUX内核(第三版) ;(美)博韦,西斯特 著; 陈莉君 张琼声 张宏伟译; 中国电力出版社;

2.Linux内核设计与实现;(美)拉芙(Love,R.)著,陈莉君 等译;机械工业出版社;

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key