一：Linux进程的四大要素:
1：一段供进程执行的程序，该程序可以被多个进程执行。
2：独立的内核堆栈。
3：进程控制快（task_struct：有了这个数据结构，进程才能成为内核调度的一个基本单位接受内核的调度。同时，这个结构还记录着进程所占用的各项资源。)
4：独立的存储空间：即拥有专有的用户空间，除了前面的内核空间还有用户空间。
★Note:与线程线程不同的是线程只有前三条，没有第四条。内核线程完全没有用户空间。用户线程：共享用户空间。
二：Linux进程分类：
1：交互式进程：这些进程经常和用户发生交互，所以花费一些时间等待用户的操作。当有输入时，进程必须很快的激活。通常，要求延迟在50-150毫秒。典型的交互式进程有：控制台命令，文本编辑器，图形应用程序。
2：批处理进程（Batch Process）：不需要用户交互，一般在后台运行。所以不需要非常快的反应，他们经常被调度期限制。典型的批处理进程:编译器，数据库搜索引擎和科学计算。
3：实时进程：对调度有非常严格的要求，这种类型的进程不能被低优先级进程阻塞，并且在很短的时间内做出反应。典型的实时进程：音视频应用程序，机器人控制等。
批处理进程可能与I/O或者CPU有关，但是实时进程完全通过Linux的调度算法识别。
其实交互式进程和批处理进程很难区别。
三：Linux进程优先级
1：静态优先级(priority): 被称为“静态”是因为它不随时间而改变，只能由用户进行修改。它指明了在被迫和其它进程竞争CPU之前该进程所应该被允许的时间片的最大值（20）。
每个普通进程都一个静态优先级，内核为其分配的优先级数为：100（高优先级）-139（低优先级）。数值越大，优先级越低。新创建的进程一般继承父进程的优先级，但是用户可以通过给nice()函数传递“nice value“或者setpriority()改变优先级。
++++++++++++++++++++++++
★附：nice()讲解见附录。
++++++++++++++++++++++++
2: 动态优先级(counter): counter 即系统为每个进程运行而分配的时间片，Linux兼用它来表示进程的动态优先级。只要进程拥有CPU，它就随着时间不断减小；当它为0 时，标记进程重新调度。它指明了在当前时间片中所剩余的时间量（最初为20）事实上，在进程在调度的时候，调度器只察看动态优先级，其值为100-139。通过下面的公式可以根据静态优先计算出相应的动态优先级。
Dynamicy priority = max (100, min (static priority - bonus + 5, 139))
Bonus:0-10，比5小，降低动态优先级，反之，可以提高动态优先级。Bonus和进程的平均睡眠时间有关。
3: 实时优先级（rt_priority）：值为1000。Linux把实时优先级与counter值相加作为实时进程的优先权值。较高权值的进程总是优先于较低权值的进程，如果一个进程不是实时进程，其优先权就远小于1000，所以实时进程总是优先。
4：Base time quantum：是由静态优先级决定，当进程耗尽当前Base time quantum，kernel会重新分配一个Base time quantum给它。静态优先级和Base time quantum的关系为：
（1）当静态优先级小于120
Base time quantum（in millisecond）= (140 – static priority) * 20
（2）当静态优先级大于等于120
Base time quantum（in millisecond）= (140 – static priority) * 5
四：Linux 进程的调度算法
1．时间片轮转调度算法(round-robin)：SCHED_RR,用于实时进程。系统使每个进程依次地按时间片轮流执行的方式。
2．优先权调度算法：SCHED_NORMAL,用于非实时进程。系统选择运行队列中优先级最高的进程运行。Linux 采用抢占式的优级算法，即系统中当前运行的进程永远是可运行进程中优先权最高的那个。
3．FIFO(先进先出)调度算法：SCHED_FIFO,实时进程按调度策略分为两种。采用FIFO的实时进程必须是运行时间较短的进程，因为这种进程一旦获得CPU 就只有等到它运行完或因等待资源主动放弃CPU时其它进程才能获得运行机会。
五：Linux 进程的调度时机
1．进程状态转换时： 如进程终止，睡眠等；
2．可运行队列中增加新的进程时；
3．当前进程的时间片耗尽时；
4．进程从系统调用返回到用户态时；
5．内核处理完中断后，进程返回到用户态；
六：进程队列：(对队列都有初始化、添加、删除等功能。)
1：运行队列：Linux系统为处于就绪态的进程的队列，只有在这个队列中的进程才有机会获得CPU。
2：等待队列：，Linux系统也为处于睡眠态的进程组建了一个队列。
七：调度使用的数据结构
1：runqueue
Runqueu是调度器中非常重要的一个数据结构，每个CPU都有自己的runqueue。
requeue:
Type
Name
Description
spinlock_t
lock
保护进程列表的自旋锁
unsigned long
nr_running
runqueue 列表中可运行进程数。
unsigned long
cpu_load
基于runqueue平均进程数的CPU 加载因子
unsigned long
nr_switches
CPU运行的进程切换次数
unsigned long
nr_uninterruptible
曾经在runqueue但是现在处于 TASK_UNINTERRUPTIBLE 状态的进程数
unsigned long
expired_timestamp
老进程已经插入expired列表中的时间
unsigned long long
timestamp_last_tick
最后一次时钟中断的Timestamp值
task_t *
curr
当前运行进程描述符的指针
task_t *
idle
进程描述符指针，指向当前CPU的swappe进程
struct mm_struct *
prev_mm
在进程却换工程中，保存正被替换的进程的地址空间
prio_array_t *
active
指向激活进程列表(arrays 中的一个）
prio_array_t *
expired
指向expired进程列表(arrays 中的一个）
prio_array_t [2]
arrays
激活和expired进程的2维数组,每个prio_array_t代表一组可运行进程，140个双向列表，静态bitmap以及这组进程的counter.
int
best_expired_prio
在expired进程中最低的静态优先级
atomic_t
nr_iowait
曾经在runqueue但是现在正在等待I/O操作完成的进程数
struct sched_domain *
sd
指向当前CPU的基本调度域
int
active_balance
标志一些进程将被从一个requeue转移到其他requeue队列
int
push_cpu
没有使用
task_t *
migration_thread
内核转移线程的进程描述符
struct list_head
migration_queue
将被从requeue中转移的进程列表
九：调度使用的重要函数
调度需要一系列函数配合完成调度这一功能，其中最重要的如下：
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scheduler_tick() :
更新当前进程的time_slice,该函数有两种调用途径：
1：timer，调用频率为HZ，并且在关中断的情况下调用。
2：fork代码，当改变父进程的timeslice时。
try_to_wake_up():
唤醒sleep进程。当进程不在可运行队列时，将其放在可运行队列。
recalc_task_prio():
更新进程的动态优先级。
schedule()：
选择一个进程运行。
load_balance():
保持多系统下runqueue平衡。检查当前CPU，保证一个域中runqueue平衡。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1：在进程切换前，scheduler做的事情：
Schedule所作的事情是用某一个进程替换当前进程。
（1)关闭内核抢占，初始化一些局部变量。
*******************
need_resched:
preempt_disable( );
prev = current;
rq = this_rq( );
当前进程current被保存在prev,和当前CPU相关的runqueue的地址保存在rq中。
*******************
（2）检查prev有没有持有big kernel lock.
****************************
if (prev->lock_depth >= 0)
up(&kernel_sem);
Schedule没有改变lock_depth的值，在prev唤醒自己执行的情况下，如果lock_depth的值不是负的，prev需要重新获取kernel_flag自旋锁。所以大内核锁在进程切换过程中是自动释放的和自动获取的。
****************************
（3）调用sched_clock()，读取TSC，并且将TSC转换成纳秒，得到的timestamp保存在now中，然后Schedule计算prev使用的时间片。
****************************
now = sched_clock( );
run_time = now - prev->timestamp;
if (run_time > 1000000000)
run_time = 1000000000;
****************************
(4）在察看可运行进程的时候，schedule必须关闭当前CPU中断，并且获取自旋锁保护runqueue.
****************************
spin_lock_irq(&rq->lock);
****************************
（5）为了识别当前进程是否已经终止，schedule检查PF_DEAD标志。
****************************
if (prev->flags & PF_DEAD)
prev->state = EXIT_DEAD;
****************************
（6）Schedule检查prev的状态，如果它是不可运行的，并且在内核态没有被抢占，那么从runqueue删除它。但是，如果prev有非阻塞等待信号并且它的状态是TASK_INTERRUPTBLE,设置其状态为TASK_RUNNING，并且把它留在runqueue中。该动作和分配CPU给prev不一样，只是给prev一个重新选择执行的机会。
********************************************************************
if (prev->state != TASK_RUNNING &&
!(preempt_count() & PREEMPT_ACTIVE)) {
if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev))
prev->state = TASK_RUNNING;
else {
if (prev->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
deactivate_task(prev, rq);
}
}
deactivate_task( )是从runqueue移除进程：
......................................
rq->nr_running--;
dequeue_task(p, p->array);
p->array = NULL;
......................................
*******************************************************************
（7)检查runqueue中进程数，
A:如果有多个可运行进程，调用dependent_sleeper()函数。一般情况下，该函数立即返回0，但是如果内核支持超线程技术，该函数检查将被运行的进程是否有比已经运行在同一个物理CPU上一个逻辑CPU上的兄弟进程的优先级低。如果是，schedule拒绝选择低优先级进程，而是执行swapper进程。
*******************************************************************
if (rq->nr_running) {
if (dependent_sleeper(smp_processor_id( ), rq)) {
next = rq->idle;
goto switch_tasks;
}
}
B:如果没有可运行进程，调用idle_balance()，从其他runqueue队列中移动一些进程到当前runqueue，idle_balance()和load_balance()相似。
...................................................................
if (!rq->nr_running) {
idle_balance(smp_processor_id(), rq);
if (!rq->nr_running) {
next = rq->idle;
rq->expired_timestamp = 0;
wake_sleeping_dependent(smp_processor_id(), rq);
if (!rq->nr_running)
goto switch_tasks;
}
}
如果idle_balance()移动一些进程到当前runqueue失败，schedule()调用wake_sleeping_dependent( )重新唤醒空闲CPU的可运行进程。
.....................................................................
假设schedule()已经决定runqueue中有可运行进程，那么它必须检查可运行进程中至少有一个进程是激活的。如果没有，交换runqueue中active 和expired域的内容，所有expired进程变成激活的，空数组准备接受以后expire的进程。
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;
}
*******************************************************************
（8）查找在active prio_array_t数组中的可运行进程。Schedule在active数组的位掩码中查找第一个非0位。当优先级列表不为0的时候，相应的位掩码被设置，所以第一个不为0的位标示一个有最合适进程运行的列表。然后列表中第一个进程描述符被获取。
********************************************************
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
现在next指向将替换prev的进程描述符。
********************************************************
（9）检查next->activated，它标示唤醒进程的状态。
（10）如果next是一个普通进程，并且是从TASK_INTERRUPTIBLE 或者TASK_STOPPED状态唤醒。Scheduler在进程的平均睡眠时间上加从进程加入到runqueue开始的等待时间。
*******************************************************************************
if (!rt_task(next) && next->activated > 0) {
unsigned long long delta = now - next->timestamp;
if (unlikely((long long)(now - next->timestamp) < 0))
delta = 0;
if (next->activated == 1)
delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
array = next->array;
new_prio = recalc_task_prio(next, next->timestamp + delta);
if (unlikely(next->prio != new_prio)) {
dequeue_task(next, array);
next->prio = new_prio;
enqueue_task(next, array);
} else
requeue_task(next, array);
}
next->activated = 0;
*******************************************************************************
Scheduler区分被中断或者被延迟函数唤醒的进程与被系统调用服务程序或者内核线程唤醒的进程。前者，Scheduler加整个runqueue等待时间，后者只加一部分时间。
2：进程却换时，Scheduler做的事情：
现在，Scheduler已经确定要运行的进程。
（1）访问next的thread_info,它的地址保存在next进程描述符的顶部。
**************************************************
switch_tasks:
if (next == rq->idle)
schedstat_inc(rq, sched_goidle);
prefetch(next)
**************************************************
（2）在替换prev前，执行一些管理工作
***************************************
clear_tsk_need_resched(prev);
rcu_qsctr_inc(task_cpu(prev));
clear_tsk_need_resched清除prev的TIF_NEED_RESCHED，该动作只发生在Scheduler是被间接调用的情况。
***************************************
（3）减少prev的平均睡眠时间到进程使用的cpu时间片。
***************************************
prev->sleep_avg -= run_time;
if ((long)prev->sleep_avg <= 0)
prev->sleep_avg = 0;
prev->timestamp = prev->last_ran = now;
***************************************
(4）检查是否prev和next是同一个进程，如果为真，放弃进程切换，否则，执行（5）
***************************************
if (prev == next) {
spin_unlock_irq(&rq->lock);
goto finish_schedule;
}
***************************************
（5）真正的进程切换
********************************************************
next->timestamp = now;
rq->nr_switches++;
rq->curr = next;
++*switch_count;
prepare_task_switch(rq, next);
prev = context_switch(rq, prev, next);
context_switch建立了next的地址空间，进程描述符的active_mm指向进程使用的地址空间描述符，而mm指向进程拥有的地址空间描述符，通常二者是相同的。但是内核线程没有自己的地址空间，mm一直为NULL。如果next为内核线程，context_switch保证next使用prev的地址空间。如果next是一个正常的进程，context_switch使用next的替换prev的地址空间。
struct mm_struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
if (unlikely(!mm)) {
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next);
} else
switch_mm(oldmm, mm, next);
如果prev是一个内核线程或者正在退出的进程，context_switch在runqueue的prev_mm中保存prev使用的内存空间。
if (unlikely(!prev->mm)) {
prev->active_mm = NULL;
WARN_ON(rq->prev_mm);
rq->prev_mm = oldmm;
}
调用switch_to(prev, next, prev)进行prev和next的切换。（参见“进程间的切换“）。
3：进程切换后的工作
（1） finish_task_switch()：
struct mm_struct *mm = rq->prev_mm;
unsigned long prev_task_flags;
rq->prev_mm = NULL;
prev_task_flags = prev->flags;
finish_arch_switch(prev);
finish_lock_switch(rq, prev);
if (mm)
mmdrop(mm);
if (unlikely(prev_task_flags & PF_DEAD))
put_task_struct(prev)
如果prev是内核线程，runqueue的prev_mm保存prev的内存空间描述符。Mmdrop减少内存空间的使用数，如果该数为0，该函数释放内存空间描述符，以及与之相关的页表和虚拟内存空间。
finish_task_switch()还释放runqueue的自选锁，开中断。
（2）最后
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;
schedule获取大内核块，重新使内核可以抢占，并且检查是否其他进程设置了当前进程的TIF_NEED_RESCHED，如果真，重新执行schedule，否则该程序结束。
附一：
【命令】nice — 调整程序运行的优先级
【格式】nice [OPTION] [command [arguments...]]
【说明】
在当前程序运行优先级基础之上调整指定值得到新的程序运行优先级，用新的程序运行优先级运行命令行"command [arguments...]"。优先级的范围为-20 ～ 19 等40个等级，其中数值越小优先级越高，数值越大优先级越低，既-20的优先级最高， 19的优先级最低。若调整后的程序运行优先级高于-20，则就以优先级-20来运行命令行；若调整后的程序运行优先级低于19，则就以优先级19来运行命令行。若 nice命令未指定优先级的调整值，则以缺省值10来调整程序运行优先级，既在当前程序运行优先级基础之上增加10。
若不带任何参数运行命令nice，则显示出当前的程序运行优先级。
例1：
1. # nice
2. 0
3. #
在例1中，不用任何参数执行命令"nice"(见第1行)，所以显示出当前的程序运行优先级为0(见第2行)。由此可知系统缺省的程序运行优先级为0。
例2：
1. # nice nice
2. 10
3. #
在例2中，第1个nice命令以缺省值来调整第2个nice命令运行的优先级，既在系统缺省的程序运行优先级0的基础之上增加10，得到新的程序运行优先级10，然后以优先级10来运行第2个nice命令；第2个nice命令显示当前程序运行的优先级为10。
例3：
1. # nice nice nice
2. 19
3. #
在例3中，第1个nice命令以缺省值来调整第2个nice命令运行的优先级，既在系统缺省的程序运行优先级0的基础之上增加10，得到新的程序运行优先级10，然后以优先级10来运行第2个nice命令；第2个nice命令又以缺省值来调整第3个nice命令运行的优先级，既在第2个nice命令运行优先级基础之上再增加10，得到新的程序运行优先级20，但20大于最高程序运行优先级19，所以以优先级19来运行第3个nice命令；第3个nice命令显示当前程序运行的优先级为19。
【参数说明】
-n, --adjustment=ADJUST 指定程序运行优先级的调整值。
优先级的范围为-20~19，当调整后的优先级小于-20时，以优先级-20 来运行程序(见例4)；当调整后的优先级大于19时，则以19的优先级运行程序(见例5)。
例4：
1. # nice -n -21 nice
2. -20
3. #
在例4中，以参数“-n”的形式指定程序运行优先级的调整值，系统缺省优先级0加上调整值-21得到新的优先级-21(小于-20)，因此程序最终的运行优先级为-20。
例5：
1. # nice --adjustment=20 nice
2. 19
3. #
在例5中，以参数“--adjustment=ADJUST”的形式指定程序运行优先级的调整值，系统缺省优先级0加上调整值20得到新的优先级20(大于19)，因此程序最终的运行优先级为19。
注意：在使用“--adjustment=ADJUST”形式指定程序运行优先级的调整值时，中间的等号可以省略。在例5中，也可运行命令行“nice --adjustment 20 nice”。
还可以使用参数“-ADJUST”的形式来指定程序运行优先级的调整值，其中，ADJUST为指定的程序运行优先级调整值，可以为负数，也可以为正数，如例6所示。
例6：
1. # nice --1 nice
2. -1
3. # nice -+1 nice
4. 1
5. # nice -1 nice
6. 1
7. #
在例6中，参数“--1”、“-+1”和 “-1”中的第一个字符“-”都是语法定义的指定程序运行优先级调整值的标志符，第一个字符“-”之后的值为指定的程序运行优先级的调整值。
在nice命令中，可以同时指定多个程序运行优先级调整值，但只有最后一次指定的数值有效，如例7所示。
例7：
1. # nice -n -20 --adjustment +19 -3 nice
2. 3
3. #
在例7中，通过命令行同时指定了优先级调整值“-20”、“+9”和“3”，但最后生效的程序运行优先级调整值为最后指定的数值“3”。
注意：只有具有root权限的用户才可以调整高程序运行的优先级，既指定的调整值可以为负数，如例8所示。
例8：
1. # su thinkerABC
2. $ nice -n -1 nice
3. nice: cannot set priority: Permission denied
4. $ nice -n 1 nice
5. 1
6. $
在例8中，我们将用户改为非root用户权限的thinkerABC，这时调高程序运行优先级1个级别时操作失败，系统提示权限不足。而调低优先级1个级别时，操作就可以成功。
--help 显示nice命令的帮助信息，详见例9。
例9：
1. # nice --help
2. Usage: nice [OPTION] [COMMAND [ARG]...]
3. Run COMMAND with an adjusted scheduling priority.
4. With no COMMAND, print the current scheduling priority. ADJUST is 10
5. by default. Range goes from -20 (highest priority) to 19 (lowest).
6.
7. -n, --adjustment=ADJUST increment priority by ADJUST first
8. --help display this help and exit
9. --version output version information and exit
10.
11. Report bugs to <bug-sh-utils@gnu.org>.
12. #
在例9中，用参数“--help”执行nice命令，则显示该命令的帮助信息，见例9的第2行～第11行。
--version 输出nice命令的版本信息，详见例10。
例10：
1. # nice --version
2. nice (GNU sh-utils) 2.0.12
3. Written by David MacKenzie.
4.
5. Copyright (C) 2002 Free Software Foundation, Inc.
6. This is free software; see the source for copying conditions. There is NO
7. warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
8. #
在例10中，用参数“--version”运行nice命令，则显示该命令的版本信息，见例10的第2行～第7行。(注：本例是在Red Hat 8.0下运行的结果。)
参考文献：
[1] Linux man pages