GroupBlog

如果说，有人问你，Linux操作系统对进程的调度是采用什么方式？也许，你会回答说，不就是优先级和时间片么？对，没错，我们所知道的就是这两种方法。但是，在Linux内核中到底对这两种方法是如何诠释的呢？那么就得看看源码了，下面的内容纯属自己对进程调度的理解，如有错误，烦请提出～

看源码，如何看？首先你得下个源码包，我这里看的是linux-3.18.21版本的源码，而我们今天所要看的进程调度的源码是在linux-3.18.21/kernel/sched这个目录中的一些文件，因为在之前也有老师的研究生过来讲过O(1)和CFS算法，我比较笨，并没有听懂他讲了什么，也不好意思问，因为没看过源码没有话语权。。。所以先看看源码吧

要说进程调度，就得先看看描述进程信息的结构体：struct task_struct，在linux-3.18.21/include/linux/sched.h中，其结构体中的部分内容如下：

值得注意的是结构体中的volatile int state;这个变量标示的是进程的当前状态，同样在这个结构体中也有宏定义的进程的状态如下：

#define TASK_RUNNING		0         //表示进程正在执行或者准备执行，即资源已分配只等待CPU的分配                
#define TASK_INTERRUPTIBLE	1         //表示进程被阻塞，有一个条件限制，只有当这个条件成立后，变状态为TASK_RUNNING;可通过信号来通知
#define TASK_UNINTERRUPTIBLE	2         //表示进程被阻塞，不可通过信号来通知，所以只能等条件达成后进入TASK_RUNNING状态
#define __TASK_STOPPED		4         //表示进程被停止
#define __TASK_TRACED		8         //表示进程被debugger监视
/* in tsk->exit_state */
#define EXIT_DEAD		16         
#define EXIT_ZOMBIE		32
#define EXIT_TRACE		(EXIT_ZOMBIE | EXIT_DEAD)
/* in tsk->state again */
#define TASK_DEAD		64          //表示进程的最终状态
#define TASK_WAKEKILL		128
#define TASK_WAKING		256
#define TASK_PARKED		512
#define TASK_STATE_MAX		1024

#define TASK_STATE_TO_CHAR_STR "RSDTtXZxKWP"

这是系统中进程可能出现的状态，见名知意。

而且为了保证进程的有序性、执行的高效性、才有的结构体中的变量prio，用来保存动态优先级；变量static_prio用来保存静态优先级；rt_prio用来保存实时优先级；变量normal_prio的值取决于static_prio和调度策略SCHED_FIFO、SCHED_NORMAL、SCHED_RR。

图片中对结构体中各变量的含义已经解释的比较清楚了，需要注意的是：

struct task_struct __rcu *real_parent;           //指向该进程的真正的父进程,如果其父进程不存在，则指向pid为1的进程
//一般情况下real_parent和parent指向同一个进程
struct task_struct __rcu *parent;               //指向创建该进程的进程，当它终止时，必须向它的父进程发送信号

感觉东西好多，有时候真的就不知道从哪里入手了，，，

一般情况下，内核源码中都会有一个init函数来定义某个功能的初始化，在core.c文件中我看到了sched_init这样一个函数，一步一步看源码，发现

root_task_group.se = (struct sched_entity **)ptr;
ptr += nr_cpu_ids * sizeof(void **);

root_task_group.cfs_rq = (struct cfs_rq **)ptr;
ptr += nr_cpu_ids * sizeof(void **);

很想知道root_task_group是什么类型，它有什么含义，什么作用？

/*
 * Default task group.
 * Every task in system belongs to this group at bootup.
 */
struct task_group root_task_group;

联系前后，不难得知这个结构体其实就是用来描述进程组的信息，其中有进程实体se和运行队列cfs_rq，然后，struct sched_entity结构体中的成员cfs_rq的类型又引起了我的好奇，于是查看struct cfs_rq

struct cfs_rq {
	struct load_weight load;/*运行负载*/
	unsigned long nr_running;/*运行进程个数*/

	u64 exec_clock;
	u64 min_vruntime;/*保存的最小运行时间*/

	struct rb_root tasks_timeline;/*运行队列树根*/
	struct rb_node *rb_leftmost;/*保存的红黑树最左边的
	节点，这个为最小运行时间的节点，当进程
	选择下一个来运行时，直接选择这个*/

	struct list_head tasks;
	struct list_head *balance_iterator;

	/*
	 * 'curr' points to currently running entity on this cfs_rq.
	 * It is set to NULL otherwise (i.e when none are currently running).
	 */
	struct sched_entity *curr, *next, *last;

	unsigned int nr_spread_over;

#ifdef CONFIG_FAIR_GROUP_SCHED
	struct rq *rq;	/* cpu runqueue to which this cfs_rq is attached */

	/*
	 * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
	 * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
	 * (like users, containers etc.)
	 *
	 * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
	 * list is used during load balance.
	 */
	struct list_head leaf_cfs_rq_list;
	struct task_group *tg;	/* group that "owns" this runqueue */

#ifdef CONFIG_SMP
	/*
	 * the part of load.weight contributed by tasks
	 */
	unsigned long task_weight;

	/*
	 *   h_load = weight * f(tg)
	 *
	 * Where f(tg) is the recursive weight fraction assigned to
	 * this group.
	 */
	unsigned long h_load;

	/*
	 * this cpu's part of tg->shares
	 */
	unsigned long shares;

	/*
	 * load.weight at the time we set shares
	 */
	unsigned long rq_weight;
#endif
#endif
};

此时的cfs已经不具有时间片的概念了，而是通过另一种更加公平的策略，底层是通过红黑树来实现的；对于普通进程来说，有一个虚拟的时间min_vruntime，cfs算法通过运行队列中的虚拟时间来为进程分配适当的时间。在选择需要调度的进程时，内核搜索这个红黑树，找到虚拟运行时间小的进程，并摘除，一般情况下对应的进程也就是红黑树中最左侧的叶子结点。至于红黑树的思想，网上有很多，可以去google～

__schedule()想必就是所谓的进程调度函数了

因为之前听老师的研究生说过pick_next_task()函数是选择下一进程，也是比较有趣一个函数，所以就着重看了下这个函数，也是一知半解的，没有搞太清楚，就先说说自己的理解吧

其实对函数pick_next_task()的调用其实是调用了pick_next_task_fair()函数，最重要的就是这个

先要从红黑树书中找到下一进程实体，也即是红黑树的最左边的叶子结点；然后摘掉它，设置运行队列中的实体；如果被调度的进程仍属于当前组，则选取下一个所能被调度的任务，以保证组建调度的公平性。

上面这些文字，仅代表我个人的观点，才开始看内核源码，很多地方不懂，还在摸索。。。