进程分为I/O消耗性和处理器消耗性进程。Linux为了保证交互式应用，对进程响应做了优化（缩短响应时间），倾向于优先调度i/o消耗性进程。
Linux实现了一种基于动态优先级的调度方法，一开始，先设置基本的优先级，然而它允许调度程序根据需要加减优先级，如果进程在IO等待上小号的时间杜宇其运行时间，那么该进程属于IO消耗性进程。动态优先级会动态提高，如果一个进程的全部时间片一下子被耗尽，那么该进程属于处理器消耗型进程，动态优先级会被动态降低。
nice值-20到+19 默认值是0，nice值越大优先级越低。nice值为-20的进程获得的时间片最长，nice为19获得时间片最短。
另外，如果我们打上了RT-patch,打开top，nice列的值是rt，这类的优先级高于普通进程。
在我研究的linux-3.11.8中调度模块位置是kernel/sched/core.c
调度程序中最基本的数据结构就是runqueue，定义在kernel/sche.h中line 400-528
struct rq {
/* runqueue lock: */
raw_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 int nr_running;
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
unsigned long last_load_update_tick;
#ifdef CONFIG_NO_HZ_COMMON
u64 nohz_stamp;
unsigned long nohz_flags;
#endif
#ifdef CONFIG_NO_HZ_FULL
unsigned long last_sched_tick;
#endif
int skip_clock_update;
/* capture load from *all* tasks on this cpu: */
struct load_weight load;
unsigned long nr_load_updates;
u64 nr_switches;
struct cfs_rq cfs;
struct rt_rq rt;
#ifdef CONFIG_FAIR_GROUP_SCHED
/* list of leaf cfs_rq on this cpu: */
struct list_head leaf_cfs_rq_list;
#ifdef CONFIG_SMP
unsigned long h_load_throttle;
#endif /* CONFIG_SMP */
#endif /* CONFIG_FAIR_GROUP_SCHED */
#ifdef CONFIG_RT_GROUP_SCHED
struct list_head leaf_rt_rq_list;
#endif
/*
* 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;
struct task_struct *curr, *idle, *stop;
unsigned long next_balance;
struct mm_struct *prev_mm;
u64 clock;
u64 clock_task;
atomic_t nr_iowait;
#ifdef CONFIG_SMP
struct root_domain *rd;
struct sched_domain *sd;
unsigned long cpu_power;
unsigned char idle_balance;
/* For active balancing */
int post_schedule;
int active_balance;
int push_cpu;
struct cpu_stop_work active_balance_work;
/* cpu of this runqueue: */
int cpu;
int online;
struct list_head cfs_tasks;
u64 rt_avg;
u64 age_stamp;
u64 idle_stamp;
u64 avg_idle;
#endif
#ifdef CONFIG_IRQ_TIME_ACCOUNTING
u64 prev_irq_time;
#endif
#ifdef CONFIG_PARAVIRT
u64 prev_steal_time;
#endif
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
u64 prev_steal_time_rq;
#endif
/* calc_load related fields */
unsigned long calc_load_update;
long calc_load_active;
#ifdef CONFIG_SCHED_HRTICK
#ifdef CONFIG_SMP
int hrtick_csd_pending;
struct call_single_data hrtick_csd;
#endif
struct hrtimer hrtick_timer;
#endif
#ifdef CONFIG_SCHEDSTATS
/* latency stats */
struct sched_info rq_sched_info;
unsigned long long rq_cpu_time;
/* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
/* sys_sched_yield() stats */
unsigned int yld_count;
/* schedule() stats */
unsigned int sched_count;
unsigned int sched_goidle;
/* try_to_wake_up() stats */
unsigned int ttwu_count;
unsigned int ttwu_local;
#endif
#ifdef CONFIG_SMP
struct llist_head wake_list;
#endif
struct sched_avg avg;
};
其中cpu_rq(processor)用于返回给定处理器可执行队列，this_rq（）返回当前处理器的可自行队列。在调度中对调度队列进行操作，要使用task_rq_lock（）与task_rq_unlock（）的配合，防止特定任务在运行。在调度中，一个cpu至少对应两个队列，一个是可运行队列(active)，另一个是过期队列（expire）。同时对二者上锁解锁，就要涉及到顺序的问题，否则会出现死锁。
linux中提供了double_rq_lock()与double_rq_unlock（）完成上述操作。
当然我们通过看上面的rq结构信息，发现有一个unsigned int nr_running;主要保存该队列中的运行进程的数目。
过去的OS进行进程时间片计算的时候，使用for结构计算每个进程的优先级，并重新计算时间片。这样会耗费相当长的时间。现在由于存在两个队列，一个可运行，另一个是过期队列。只要过期就把进程移到过期队列，然后把时间片重置，如果nr_running为0就把expire值赋给rq_running.上代码！
struct rt_prio_array {
DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
struct list_head queue[MAX_RT_PRIO];
};
struct rt_prio_array *array = rq->active
if(!array->nr_active)
{
rq->active = rq->expire;
rq->expire = array
}//等于两个队列指向的队列互换，达到O(1)的时间复杂度。
选取下一个进程，一般使用空间换时间的方式，优先级放在一个总数是140bitmap中，使用sched_find_first_bit（）来找到bitmap中第一个置为一的进程，加入到运行队列。
在计算时间片上，每个进程拥有初始的优先级nice值，然后再通过动态优先级调整算法，在struct_rq结构体里有一个struct sched_avg avg;它会根据曾经睡眠的状况来判断是IO密集型还是计算密集型。
但是再怎么调整也是有限度的，下面这个表是每个时间片的极限
对于交互性程序，如果nice值为-19,进程会很容易加到运行队列中准备调度。
另外休眠有两种状态：TASK_INTERRUPTIBLE与TASK_UNINTERRUPTBLE区别在于是否忽略SIG
在新版的linux调度程序文件被放置在了kernel/sched/proc.c中这一块还没来的及细看，放假前要把这个文件过一遍
调度的总过程在kernel/sched/core.c 2389-2473
实时调度中主要使用FIFO与RR算法，算法思想不再赘述，我们在top中看到实时的优先级是0-MAX_RT_PRIO（100）-1，对应的非实时进程是MAX_RT_PRIO到MAX_RT_PRIO+40
