【Linux系统内核探索】进程调度

进程调度

什么是进程调度？

进程调度是操作系统内核的核心功能之一，负责在多个进程之间分配CPU时间，使得系统能够同时运行多个进程。因为计算机的CPU资源有限，操作系统需要决定在任何时刻哪个进程能够使用CPU执行任务，这个过程就是进程调度。
Linux进程调度经历了多个阶段的优化，目前主流的Linux内核使用的是完全公平调度器。CFS调度器的核心思想是通过精确计算每个进程的“虚拟运行时间”来决定调度的公平性。CFS调度器不会简单依赖于时间片，而是通过调度树来快速查找下一个应运行的进程。
现代的Linux调度主要依赖于Linux的CFS调度器，在2.6版本之前主要用的是Linux内核O(1)调度算法，这次我们的重点在于Linux内核O(1)调度算法。

进程调度算法

我们打开Linux内核源码版本是2.5.18，打开源码后搜索runqueue。

struct runqueue {
	spinlock_t lock;

	/*
	 * 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[3];
#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];
	int best_expired_prio;
	atomic_t nr_iowait;

#ifdef CONFIG_SMP
	struct sched_domain *sd;

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

	task_t *migration_thread;
	struct list_head migration_queue;
	int cpu;
#endif

#ifdef CONFIG_SCHEDSTATS
	/* latency stats */
	struct sched_info rq_sched_info;

	/* sys_sched_yield() stats */
	unsigned long yld_exp_empty;
	unsigned long yld_act_empty;
	unsigned long yld_both_empty;
	unsigned long yld_cnt;

	/* schedule() stats */
	unsigned long sched_switch;
	unsigned long sched_cnt;
	unsigned long sched_goidle;

	/* try_to_wake_up() stats */
	unsigned long ttwu_cnt;
	unsigned long ttwu_local;
#endif
};

这次我们关注的主要属性是：active，expired，arrays。
这结果属性分别是：

1. active：表示活跃进程。
2. expired：表示过期进程。
3. arrays：表示一个结构体数组，活跃进程指向数组的第一个元素，过期进程指向数组的第二个元素。
   这里我们只讨论后四十个，因为前面100个是实时进程。

简化过后我们就得到了一个非常简洁的结构体：
这里我们用queue来简化前面的类型

struct runqueue
{
	struct queue* active;
	struct queue* expired;
	struct queue arrays[2];
}

接下来我们进一步来讨论结构体queue：

struct prio_array {
	unsigned int nr_active;
	unsigned long bitmap[BITMAP_SIZE];
	struct list_head queue[MAX_PRIO];
};

上面是Linux内核源码
nr_active表示的是当前运行runqueue中的有效进程的数量。
queue表示一个队列，这个队列是一个链表的队列

bit_map表示位图，因为每次，我们根据优先级遍历的时候都需要从前面到后面一次遍历，这样时间复杂度来到了O(N)，如果我们引入了位图的话，如果这个位上有进程挂着，那么对应比特位就应该被标记为1，如果这个点queue对应的位置没有一个进程，那么就用0来表示，在查找的时候我们就可以进行下面循环了：

for(int i=0;i<5;i++)
{
	if(bit_map[i]==0)continue;
	else //bit_map[i]！=0表示对应的32个比特位上对应的位子上有进程
}

原本O(N)的算法，运用位图之后，将时间复杂度缩减为了常数级别，因为，我们每次查找都是以32为单位，如果这32个bit位没有一个1我们可以直接跳到下面32个比特位上。
为什么这里是5个？

因为对应的队列就只有160空间，5*32恰好为160，所以这里开辟5个刚好合适。

接下来我们就来具体画一下这个结构的简图：
我们将前面100个位置给省略了，因为前面一百个空间是事实进程。

大致的简图就是上面这幅图，active指针指向的是arrays[0]，expired指针指向的是arrays[1]。
CPU在调度的时候一般只会在active中调度，在调度中有三种情况：

1. 进程退出
2. 不退出，进程时间片到了
3. 有新建进程产生

我们先来看第三种：有新进程产生，假设这个新进程的优先级很高，而且有很多新进程，比如说新进程的优先级是80，那么不断有新进程产生，那么是不是后面优先级低的是不是迟迟调度不到。
还有一种情况是不退出时间片到了的情况，如果时间片到了，我们就直接将这个进程插入到这个位置的队尾，那么这个位置调度完一轮回之后又来到了这个进程，那么还是迟迟调度不到后面的优先级的进程。

所以这里就产生了两个问题：

1. 优先级高的，就表示就一定要优先吗？
2. 优先级低的，就表示就一直不回被调度吗？
   这是一个饥饿问题，为了解决这个问题，我们引入了expired这个数组，为的就是让调度公平，当调度完一个进程之后，这个进程不会直接回到队列的尾部，因为后面的进程就不会被调度，所以刚调度完的进程会直接来到expired中，active永远都是一个存量进程的情况，还有创建的新的进程，也不会直接到active中，创建的新的队列还是会直接来到expired当中，当active中的进程调度完之后，只需要进行一步操作即可。

swap(&active,&expired)

只需要将两个队列交换即可，所以何时交换？就由nr_active控制，当active中的没有任何有效进程的时候，就将expired和active直接交换。
swap之前：按照优先级调度
swap之后，给了其他优先级的进程调度机会。
这样就实现了Linux内核O(1)调度算法。

task_struct的链式结构

接下来讨论完调度算法之后我们来讨论一下每个进程之间到底是如何连接起来的，我们知道task_struct是以链式结构来完成的。
Linux中的task_struct是用双线链表来连接的。
我们熟知的链式结构就是：

struct node
{
	type Data;
	struct node* next;
	struct node* prev;
}

但是这里Linux内核中的链式结构不是这样的，他只有连接关系，没有属性，我们来看看原码：

可以看见确实是这样的，说明task_struct的结构是这样的：
内部套了一层双链表的数据结构，然后把数据属性放在外面。
在写代码的过程中，我们知道，我们一般都是用外层的结构体来访问内层的成员，但是在这里，我们只知道成员，我们该如何访问其他数据呢，在C语言阶段，我们知道结构体的存储是有偏移的。
我们假设有下面一个结构体：

struct A
{
	int a;
	char b;
	double c;
	float d;
}

上面这个结构体存储的时候大概是下面的简图：

假设我们有一个结构体：struct A obj
$\&obj=\&obj\to a$
从上面这个我们可以得知求出a的地址就可以求出整个结构体的地址。
利用这个公式：$(structA\ast )(\&c-偏移量)\to 成员变量$
结构体的地址等于成员变量的地址减去对应的偏移量，最后就可以结构体的地址了。那么问题又来了，偏移量该怎么求，利用下面公式求出偏移量：$\&(structA\ast )0->c$ 这样求出的地址就是相当于0位置的地址，再用c的地址减去即可，最后强转为$structA\ast$的类型。


task_struct内部的属性就是这样找到的。

总结

通过本篇博客的介绍，我们深入了解了Linux内核中的进程调度机制。进程调度作为操作系统的核心功能之一，决定了系统的响应速度和整体性能表现。不同的调度算法在特定场景下展现出了各自的优势，比如时间共享调度适用于多任务环境，而实时调度则更关注任务的及时性。掌握这些调度原理不仅能帮助我们更好地理解操作系统的工作方式，还能为优化系统性能、开发高效的应用程序提供有力的支持。在未来的学习中，进一步探索内核的其他模块将帮助我们更全面地掌握Linux系统的复杂性与强大之处。