Linux调度算法分析
本文最后更新于一年前或更久前,其中的信息可能已经有所发展或是发生改变。

基本介绍

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

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

•    单个就绪队列问题,时间片耗尽的进程依然会放进同一个就绪队列中,在不可被调度的情况下,还会参与调度。

•    多处理器问题,多个处理器上的进程放在同一个就绪队列中,因而调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待,使得就绪队列成为一个明显的瓶颈。

•    内核不可抢占问题,如果某个进程,一旦进了内核态那么再高优先级的进程都无法剥夺,只有等进程返回内核态的时候才可以进行调度。缺乏对实时进程的支持。

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

算法介绍

系统中的runqueue是一个PER_CPU变量,也就是说每一个CPU维护这一个runqueue,这样在SMP系统就可以有效的避免多个CPU去访问同一个runqueue。

每一个runqueue运行队列维护两个链表。一个是active链表,表示运行的进程都挂载active链表中;一个是expired链表,表示所有时间片用完的进程都挂载expired链表中。

为了解决O(n)中所有的进程都无序排列在runqueue中,O(1)算法中奖进程按照优先级排列,而且相同优先级的都挂在同等优先级的链表中

同时提供了一个bitmap结构,用来存放那些优先级中有可以运行的进程。当每次pciknext的时候,只需要坚持bitmap,然后去对应的优先级列表中按照优先级策略选择进程。

当acitve中无进程可运行时,说明系统中所有进程的时间片都已经耗光,这时候则只需要调整active和expired的指针即可。

从以上几点来看,可以看出O(1)的算法的改进都是针对O(n)算法存在的问题来修改的。

源代码

//以下是Linux内核中的代码
/**
 * 调度函数。
 */
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;
}

参考资料:

Linux scheduler (uoc.gr)linux-archive/sched.c at master · draveness/linux-archive (github.com)桃花猿记 (szp2016.github.io)

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇