如果说，有人问你，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_RUNNING0 //表示进程正在执行或者准备执行，即资源已分配只等待CPU的分配这是系统中进程可能出现的状态，见名知意。
#define TASK_INTERRUPTIBLE1 //表示进程被阻塞，有一个条件限制，只有当这个条件成立后，变状态为TASK_RUNNING;可通过信号来通知
#define TASK_UNINTERRUPTIBLE2 //表示进程被阻塞，不可通过信号来通知，所以只能等条件达成后进入TASK_RUNNING状态
#define __TASK_STOPPED4 //表示进程被停止
#define __TASK_TRACED8 //表示进程被debugger监视
/* in tsk->exit_state */
#define EXIT_DEAD16
#define EXIT_ZOMBIE32
#define EXIT_TRACE(EXIT_ZOMBIE | EXIT_DEAD)
/* in tsk->state again */
#define TASK_DEAD64 //表示进程的最终状态
#define TASK_WAKEKILL128
#define TASK_WAKING256
#define TASK_PARKED512
#define TASK_STATE_MAX1024
#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;很想知道root_task_group是什么类型，它有什么含义，什么作用？
ptr += nr_cpu_ids * sizeof(void **);
root_task_group.cfs_rq = (struct cfs_rq **)ptr;
ptr += nr_cpu_ids * sizeof(void **);
/*联系前后，不难得知这个结构体其实就是用来描述进程组的信息，其中有进程实体se和运行队列cfs_rq，然后，struct sched_entity结构体中的成员cfs_rq的类型又引起了我的好奇，于是查看struct cfs_rq
* Default task group.
* Every task in system belongs to this group at bootup.
*/
struct task_group root_task_group;
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_SCHEDstruct 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()函数，最重要的就是这个
先要从红黑树书中找到下一进程实体，也即是红黑树的最左边的叶子结点；然后摘掉它，设置运行队列中的实体；如果被调度的进程仍属于当前组，则选取下一个所能被调度的任务，以保证组建调度的公平性。
上面这些文字，仅代表我个人的观点，才开始看内核源码，很多地方不懂，还在摸索。。。