1. 前言

Linux 2.4中使用goodness()函数，给每个处于可运行状态的进程赋予一个权值（Weight）,使用这个权值衡量一个处于可运行状态的进程值得运行的程度。调度程序以这个权值作为选择进程的唯一依据。

虽然Linux2.4进程调度程序简单有效，但是也有其缺点。

单个就绪队列问题，时间片耗尽的进程依然会放进同一个就绪队列中，在不可被调度的情况下，还会参与调度。
多处理器问题，多个处理器上的进程放在同一个就绪队列中，因而调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待，使得就绪队列成为一个明显的瓶颈。
内核不可抢占问题，如果某个进程，一旦进了内核态那么再高优先级的进程都无法剥夺，只有等进程返回内核态的时候才可以进行调度。缺乏对实时进程的支持。

针对以上问题，Linux 2.6做了较大的改进。针对多处理器问题，为每个CPU设置一个就绪队列。针对单就绪队列问题，设置两个队列组，即active队列组和expired队列组。借助以上队列实现了时间复杂度为O(1)的调度算法。直到Linxu 2.6.23内核版本中，O(1)调度算法才真正替代为CFS（完全公平）调度算法。

2. 就绪队列

O(1)调度器是以进程的动态优先级prio为调度依据的,它总是选择目前就绪队列中优先
级最高的进程作为候选进程 next。由于实时进程的优先级总是比普通进程的优先级高,故能
保证实时进程总是比普通进程先被调度。

Linux2.6 中,优先级 prio 的计算不再集中在调度器选择 next 进程时,而是分散在进程
状态改变的任何时候,这些时机有:

进程被创建时;
休眠进程被唤醒时;
从TASK_INTERRUPTIBLE 状态中被唤醒的进程被调度时;
因时间片耗尽或时间片过长而分段被剥夺 CPU 时;

在这些情况下,内核都会调用 effective_prio()重新计算进程的动态优先级 prio并根据计算结果调整它在就绪队列中的位置。

Linux 2.6为每个cpu定义了一个struck runqueue数据结构，每个就绪队列都有一个自旋锁，从而解决了 2.4 中因只有一个就绪队列而造成的瓶颈。

struct runqueue {
    ...
    prio_array_t *active, *expired, array[2];
    ...
    }

active 是指向活动进程队列的指针；expired 是指向过期进程队列的指针；array[2]是实际的优先级进程队列，其中一个是活跃的一个是过期的，过期数组存放时间片耗完的进程。

每个处理器的就绪队列都有两个优先级数组,它们是 prio_array 类型的结构体。Linux2.6
内核正是因为使用了优先级数组,才实现了 O(1)调度算法。该结构定义在 kernel/sched.c 中:

struct prio_array{
   ...
   unsigned int nr_active;
   //相应 runqueue 中的进程数
   
   unsigned long bitmap[BITMAP_SIZE];
   /*索引位图，BITMAP_SIZE 默认值为 5,5个long(32位)类型，每位代表一个优先级，可以代表160个优先级，但实际中只有140。与下面的queue[]对应。分布0-99对应为实时进程，100-140对应为普通的进程*/
   
   struct list_head queue[MAX_PRIO];
   /*每个优先级的进程队列,MAX_PRIO 是系统允许的最大优先级数,默认值为 140,数值越小优先级越高
   bitmap每一位都与 queue[i]相对应,当 queue[i]的进程队列不为空时,bitmap 相应位为 1,否则就为 0。*/
}

3. 调度算法介绍

选择并运行候选进程，确定next,下一个应该占有 CPU 并运行的进程，schedule()函数是完成进程调度的主要函数，并完成进程切换的工作。schedule()用于确定最高优先级进程的代码非常快捷高效，其性能的好坏对系统性能有着直接影响，它在/kernel/sched.c 中的定义如下:

...
int idx;
...
preempt_disable();
...
idx = sched_find_first_bit( array -> bitmap);
queue = array -> queue + idx;
next = list_entry( queue -> next, task_t, run_list);
...
prev = context_switch( rq, prev, next);
...
}

其中,sched_find_first_bit()能快速定位优先级最高的非空就绪进程链表,运行时间和就绪队列中的进程数无关,是实现O(1)调度算法的一个关键所在。
schedule()的执行流程:
首先,调用 pre_empt_disable(),关闭内核抢占,因为此时要对内核的一些重要数据结构进行操作,所以必须将内核抢占关闭;其次,调用sched_find_first_bit()找到位图中的第1个置1的位，该位正好对应于就绪队列中的最高优先级进程链表;
再者,调用 context_switch()执行进程切换,选择在最高优先级链表中的第 1个进程投入运行;

图中的网格为 140 位优先级数组,queue[7]为优先级为 7 的就绪进程链表。此种算法保证了调度器运行的时间上限,加速了候选进程的定位过程。

Linux2.4 调度系统在所有就绪进程的时间片都耗完以后在调度器中一次性重新计算,其中重算是用for循环相当耗时。

Linux2.6 为每个 CPU 保留 active 和 expired 两个优先级数组, active 数组中包含了有剩余时间片的任务,expired 数组中包含了所有用完时间片的任务。

当一个任务的时间片用完了就会重新计算其时间片,并插入到 expired 队列中,当 active 队列中所有进程用完时间片时,只需交换指向 active 和 expired 队列的指针即可。此交换是实现 O(1)算法的核心,由 schedule()中以下程序来实现:

array = rq ->active;
if (unlikely(!array->nr_active)) {
         rq -> active = rq -> expired;
         rq -> expired = array;
         array = rq ->active;
...
}

4.Linux 2.6调度算法源码

/**
 * 调度函数。
 */
asmlinkage void __sched schedule(void)
{
	long *switch_count;
	/**
	 * next指向被选中的进程，这个进程将取代当前进程在CPU上执行。
	 * 如果系统中没有优先级高于当前进程，那么next会和current相等。不发生任何切换。
	 */
	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)) {
		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;
	/**
	 * 释放大内核锁。当内核抢占打开时，并且当前中断正在抢占当前进程，那么会将lock_depth置为-1.
	 * 这样，不会释放内核锁。只有当进程获得了大内核锁并且是主动调度出来时，才会释放锁。
	 * 注意，释放锁并不会修改lock_depth。当进程恢复执行后，如果lock_depth>=0，就会再次获得大内核锁。
	 */
	release_kernel_lock(prev);
need_resched_nonpreemptible:
	rq = this_rq();

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

	schedstat_inc(rq, sched_cnt);
	/**
	 * 计算当前进程的运行时间。不超过1秒。
	 */
	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 charged proportionately less run_time at high sleep_avg to
	 * delay them losing their interactive status
	 */
	/**
	 * 对有较长睡眠时间的进程，进行一定奖励。
	 */
	run_time /= (CURRENT_BONUS(prev) ? : 1);

	/**
	 * 在开始寻找可运行进程之前，需要关中断并获得保护运行队列的自旋锁。
	 */
	spin_lock_irq(&rq->lock);

	/**
	 * 当前进程可能是一个正在准备被终止的进程。可能现在是通过do_exit进入schedule函数。
	 */
	if (unlikely(prev->flags & PF_DEAD))
		prev->state = EXIT_DEAD;

	switch_count = &prev->nivcsw;
	/**
	 * 如果进程不是TASK_RUNNING状态，并且没有被内核抢占。就把该进程从运行队列中删除。
	 */ 
	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		switch_count = &prev->nvcsw;
		/**
		 * 如果进程是被信号打断的，就将它设置成TASK_RUNNING
		 */
		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，从另外一个运行队列迁移一些可运行进程到本地运行队列中。
		 */
		idle_balance(cpu, rq);
		if (!rq->nr_running) {/* 没有迁移新进程到本运行队列。 */
			next = rq->idle;
			rq->expired_timestamp = 0;
			/**
			 * wake_sleeping_dependent重新调度空闲CPU中的可运行进程。主要是处于超线程的情况。
			 */
			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)/* 如果支持超线程，并且其他逻辑CPU也没有可运行进程，那么只好运行IDLE进程了。 */
				goto switch_tasks;
		}
	} else {/* 有可能运行的进程 */
		/**
		 * dependent_sleeper一般返回为0,但是如果内核支持超线程技术，函数检查要被选中执行的进程。
		 * 其优先级是否比当前已经在相同物理CPU的逻辑CPU上运行的兄弟进程的优先级，如果新进程优先级低，就拒绝选择低优先级进程，而去执行swapper进程。
		 */
		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)) {
		/**
		 * 活动队列中没有可运行进程了。交换活动集合和过期集合。
		 */
		/*
		 * 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);

	/**
	 * 现在开始在活动集合中搜索一个可运行的进程。
	 * 首先搜索第一个非0位，并找到对应的链表。
	 */
	idx = sched_find_first_bit(array->bitmap);
	queue = array->queue + idx;
	/**
	 * 将下一个可运行进程描述符放到next中
	 */
	next = list_entry(queue->next, task_t, run_list);

	/**
	 * 如果进程是一个普通进程，并且是从TASK_INTERRUPTIBLE或者TASK_STOPPED状态被唤醒。
	 * 就把自从进程插入运行队列开始所经过的纳秒数加到平均睡眠时间中。
	 */
	if (!rt_task(next) && next->activated > 0) {
		unsigned long long delta = now - next->timestamp;

		/**
		 * 如果是被系统调用服务例程或者内核线程所唤醒，就只增加部分睡眠时间(30%)
		 * 否则增加100%的睡眠时间。这样，交互式进程由于经常被中断打断，它的睡眠时间会增加得更快。
		 */
		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提示CPU控制单元把next的进程描述符的第一部分字段的内容装入硬件高速缓存。
	 * 这改善了schedule的性能。
	 */
	prefetch(next);
	/**
	 * 清除TIF_NEED_RESCHED标志。
	 */
	clear_tsk_need_resched(prev);
	/**
	 * 记录CPU正在经历静止状态。主要与RCU相关。
	 */
	rcu_qsctr_inc(task_cpu(prev));

	/**
	 * 减少prev的平均睡眠时间
	 */
	prev->sleep_avg -= run_time;
	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;
		++*switch_count;

		prepare_arch_switch(rq, next);
		/**
		 * context_switch执行真正的进程切换
		 */
		prev = context_switch(rq, prev, next);

		/**
		 * 当进程再次被切换进来后，以下代码被接着运行。
		 * 但是此时prev并不指向当前进程，而是指代码从哪一个进程切换到本进程。
		 * 由于此时已经进行了进程空间的切换，寄存器中缓存的变量等都不再有效，所以用barrier产生一个优化屏障。
		 */
		barrier();

		/**
		 * 对前一个进程进行一些收尾工作，比如减少它的mm_struct,task_struct的引用计数等。
		 */
		finish_task_switch(prev);
	} else/* 如果prev和next是同一个进程，就不做进程切换。当prev仍然是当前活动集合中的最高优先级进程时，这是有可能发生的。 */
		spin_unlock_irq(&rq->lock);

	/**
	 * 在前几句中(context_switch之后)，prev代表的是从哪个进程切换到本进程。
	 * 在继续进行调度之前(因此在context_switch中开了中断，可能刚切回本进程就来了中断，并需要重新调度)，将prev设置成当前进程。
	 */
	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;
}

szp2016.github.io

Linux 2.6进程O(1)调度算法

1. 前言

2. 就绪队列

3. 调度算法介绍

4.Linux 2.6调度算法源码