一基本概念
1 进程和线程
进程就是正在执行的程序代码的实时结果，包括可执行程序代码（代码段），内存地址空间、数据段、打开的文件等资源。即进程是处于执行期的程序以及相关的资源的总称。
线程：是进程中活动的对象，拥有独立的程序计数器、进程栈，进程寄存器。内核调度的对象（最小单位）是线程，而非进程。
Linux内核中也将进程称为任务（task）,且将线程看做一种特殊的进程（没有独立的地址空间而已）。进程是资源分配管理的最小单元，而线程是程序执行（调度）的最小单元。
Linux中使用多线程的好处有：
创建线程的开销远远小于进程的创建（必须给新的进程分配独立的地址空间），而且线程间切换所需的时间也远小于进程切换需要的时间。
线程间通信方便，不同的进程（分别拥有独立的地址空间）之间数据的传递需要通过IPC方式，费时且不方便。而同一个进程下的线程之间共享数据空间，线程间数据的通信使用方便。
2 进程描述符
任务队列（内核中存放进程列表的一个双向循环链表）的(每一项都是)类型为task_struct的结构，其包含了一个具体进程的所有信息。
进程标识值PID一个int类型的数，是进程的唯一标识。所有的进程都是PID为1的init进程的后台，内核在系统启动的最后阶段启动init进程
3.进程上下文 中断上下文
１、内核态，运行于进程上下文，内核代表进程运行于内核空间；
２、内核态，运行于中断上下文，内核代表硬件运行于内核空间；
３、用户态，运行于用户空间。
用户空间的应用程序，通过系统调用，进入内核空间。这个时候用户空间的进程要传递很多变量、参数的值给内核，内核态运行的时候也要保存用户进程的一些寄存器值、变量等。所谓的“进程上下文”，可以看作是用户进程传递给内核的这些参数以及内核要保存的那一整套的变量和寄存器值和当时的环境等。
硬件通过触发信号，导致内核调用中断处理程序，进入内核空间。这个过程中，硬件的一些变量和参数也要传递给内核，内核通过这些参数进行中断处理。所谓的“中断上下文”，其实也可以看作就是硬件传递过来的这些参数和内核需要保存的一些其他环境（主要是当前被打断执行的进程环境）。
Linux内核工作在进程上下文或者中断上下文。提供系统调用服务的内核代码代表发起系统调用的应用程序运行在进程上下文；另一方面，中断处理程序，异步运行在中断上下文。中断上下文和特定进程无关。
运行在进程上下文的内核代码是可以被抢占的（Linux2.6支持抢占）。但是一个中断上下文，通常都会始终占有CPU（当然中断可以嵌套，但我们一般不这样做），不可以被打断。正因为如此，运行在中断上下文的代码就要受一些限制，不能做下面的事情：
1、睡眠或者放弃CPU。 这样做的后果是灾难性的，因为内核在进入中断之前会关闭进程调度，一旦睡眠或者放弃CPU，这时内核无法调度别的进程来执行，系统就会死掉
2、尝试获得信号量 如果获得不到信号量，代码就会睡眠，会产生和上面相同的情况
3、执行耗时的任务中断处理应该尽可能快，因为内核要响应大量服务和请求，中断上下文占用CPU时间太长会严重影响系统功能。
4、访问用户空间的虚拟地址 因为中断上下文是和特定进程无关的，它是内核代表硬件运行在内核空间，所以在中端上下文无法访问用户空间的虚拟地址
二 进程创建
1 fork exec
Linux将进程的创建分为两个单独的函数中：fork和exec。
fork通过copy当前进程创建一个子进程（子进程与父进程仅仅PID 以及一些统计量（挂起的信号）不同），exec负责读取可执行文件并将其载入地址空间开始执行。
2fork函数的写时拷贝
Fork调用时，内核此时并不复制整个进程地址空间，而是让父进程和子进程共享一个拷贝。只有在需要写入的时候，数据才被复制，从而使各个进程拥有各自的拷贝，例如在fork后立即调用exec它们就无需复制了。Fork的实际开销就是复制父进程的页表和为子进程创建唯一的进程描述符。所以UNIX下进程的创建非常迅速。Linux通过clone系统调用实现fork（子进程首先执行）。
3 vfork
与fork唯一不同时不拷贝父进程的页表项，不建议使用。
三 线程机制
Linux内核中线程被视为一个与其他进程共享某些资源的进程，每个线程拥有唯一隶属于自己的task_struct，也称为轻量级进程。这种方式与windows的线程实现机制不同。
内核线程(kernel thread)是由内核自己创建的线程，也叫做守护线程(deamon)。在终端上用命令"ps -Al"列出的所有进程中，名字以k开关以d结尾的往往都是内核线程，比如kthreadd、kswapd。
内核线程与用户线程的相同点是：
都由do_fork()创建，每个线程都有独立的task_struct和内核栈；
都参与调度，内核线程也有优先级，会被调度器平等地换入换出。
不同之处在于：
内核线程只工作在内核态中；
而用户线程则既可以运行在内核态，也可以运行在用户态；
内核线程没有用户空间，所以对于一个内核线程来说，它的0~3G的内存空间是空白的，它的current->mm是空的，与内核使用同一张页表；而用户线程则可以看到完整的0~4G内存空间。（在linux中， 将最高的1G字节（从虚拟地址0xC0000000到0xFFFFFFFF），供内核使用，称为“内核空间”。而将较低的3G字节（从虚拟地址 0x00000000到0xBFFFFFFF），供各个进程使用，称为“用户空间））
四 进程调度
4.1 目的
负责决定将那个进程投入运行，何时运行以及运行多长时间，调度程序是在可运行态进程之间分配有限的处理器资源的内核子系统。
进程调度 基本策略： 分时的调度 必须要 时钟中断， 优先级抢占的 不需要 时钟中断。所以分时进程调度需要时钟中断的参与，linux中具体是scheduler_tick函数（主要用于更新时间片）。
4.2 基本概念
（进程的）时间片：分配给每个可运行进程的处理器时间段
CFS:linux 2.6.23后 版本使用的调度算法，称为完全公平调度算法，取代了之前的O(1)调度算法。
I/O消耗型进程：指进程的大部分时间用来提交I/O请求或者是等待I/O请求。
处理器耗费型进程：时间大多用在执行代码上。
Linux更倾向于有限调度I/O消耗型进程。
进程优先级：linux采用了2种：用nice值和实时优先级。
Nice值：范围是-20到19，默认值为0，值越大表示优先级越低，低nice值的进程可以获得更多的处理器时间。
实时优先级：默认范围是从0到99，数值越高意味着进程优先级越高.
PS:进程的2种优先级会让人不好理解，到底哪个优先级更优先？一个进程同时有2种优先级怎么办？
其实linux的内核早就有了解决办法。
对于第一个问题，到底哪个优先级更优先？
答案是实时优先级高于nice值，在内核中，实时优先级的范围是 0～MAX_RT_PRIO-1 MAX_RT_PRIO的定义参见 include/linux/sched.h
1611 #define MAX_USER_RT_PRIO 100
1612 #define MAX_RT_PRIO MAX_USER_RT_PRIO
nice值在内核中的范围是 MAX_RT_PRIO～MAX_RT_PRIO+40 即 MAX_RT_PRIO～MAX_PRIO
1614 #define MAX_PRIO (MAX_RT_PRIO + 40)
第二个问题，一个进程同时有2种优先级怎么办？
答案很简单，就是一个进程不可能有2个优先级。一个进程有了实时优先级就没有Nice值，有了Nice值就没有实时优先级。
我们可以通过以下命令查看进程的实时优先级和Nice值：(其中RTPRIO是实时优先级，NI是Nice值)
$ ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
S UID PID PPID RTPRIO NI TIME COMMAND
S 0 1 0 - 0 00:00:00 systemd
S 0 2 0 - 0 00:00:00 kthreadd
S 0 3 2 - 0 00:00:00 ksoftirqd/0
S 0 6 2 99 - 00:00:00 migration/0
S 0 7 2 99 - 00:00:00 watchdog/0
S 0 8 2 99 - 00:00:00 migration/1
S 0 10 2 - 0 00:00:00 ksoftirqd/1
S 0 12 2 99 - 00:00:00 watchdog/1
S 0 13 2 99 - 00:00:00 migration/2
S 0 15 2 - 0 00:00:00 ksoftirqd/2
S 0 16 2 99 - 00:00:00 watchdog/2
S 0 17 2 99 - 00:00:00 migration/3
S 0 19 2 - 0 00:00:00 ksoftirqd/3
S 0 20 2 99 - 00:00:00 watchdog/3
S 0 21 2 - -20 00:00:00 cpuset
S 0 22 2 - -20 00:00:00 khelper
4.3 CFS 调度器（参考linux内核设计与实现一书中第四章）
CFS 完全公平调度是一个针对普通进程的调度类，在linux 中称为SCHED_NORMAL；在POSIX中称为SCHED_OTHER..
调度实体(sched entiy)：就是调度的对象，可以理解为进程。
虚拟运行时间(vruntime)：即每个调度实体的运行时间。
公平调度队列(cfs_rq):采取公平调度的调度实体的运行队列。
Linux系统是抢占式的，是否将一个进程投入运行（抢占当前进程），是完全由实时进程优先级和是否有时间片决定的，而linux使用CFS调度器，其抢占时机取决于新的可执行消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，即抢占当前进程，否则将推迟其运行。
CFS在所有可执行进程总数基础上计算一个进程应该运行多久，而不是依靠nice值计算时间片，nice值在cfs中被用作进程获得的处理区运行比的权重，更低的nice值的进程获得更高的处理器使用权重。（只有相对的nice值才会影响处理器时间的分配比例）。在CFS中不再有时间片的概念。
目标延迟：最小粒度默认为1ms。
任何进程获得的处理器时间是有它自己和所有其他可运行线程nice值的相对差值决定的。Nice值对时间片的作用是几何加权（非算数加权）。
调度的实现：
cfs之前的linux调度器一般使用用户设定的静态优先级，加上对于进程交互性的判断来生成动态优先级，再根据动态优先级决定进程被调度的顺序，以及调度后可以运行的时间片。反过来，随着进程的运行，内核可能发现其交互性发生改变，从而调整其动态优先级（奖励睡眠多的交互式进程、惩罚睡眠少的批处理进程）。
cfs原理
cfs定义了一种新的模型，它给cfs_rq（cfs的run queue）中的每一个进程安排一个虚拟时钟，vruntime。如果一个进程得以执行，随着时间的增长（也就是一个个tick的到来），其vruntime将不断增大。没有得到执行的进程vruntime不变。而调度器总是选择vruntime跑得最慢（最小）的那个进程来执行。这就是所谓的“完全公平”。
为了区别不同优先级的进程，优先级高的进程vruntime增长得慢，以至于它可能得到更多的运行机会。
进程调度的主要入口函数是schedule（）:选择那个进程可以运行，何时将其投入运行。每次定时器中断调用的最重要的更新时间片的函数 —— scheduler_tick函数。（当每次时钟节拍到来时（定时器产生中断，OS时间中断处理程序），即我们提到过的timer_interrupt会调用do_timer_interrupt_hook，从而调用do_timer和update_process_times函数，update_process_times则就是用来更新进程使用到的一些跟时间相关的字段，其最重要的是调用scheduler_tick()更新时间片剩余节拍数：）PS:该函数内部会对实时进程和普通进程分别处理，更新它们的时间片。
PS: 1 每个进程的weight值是如何确定的呢？
上面谈到公平的依据，CFS的公平依据就是每个调度实体的权重(weight)，这个权重是有优先级来决定的，即优先级越高权重越高，linux内核采用了nice-prio-weight的一个转换关系来实现了每个调度实体权重的确定。我们来回顾，进程被创建的时候他的优先级是继承自父进程的，如果想改变有优先级，linux内核提供了几个系统调用来改变进程的nice值，从而改变权重，如sys_nice()系统调用，下面来看一下他们之间的转换关系：
#define NICE_TO_PRIO(nice)(MAX_RT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)
#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)
其中，MAX_RT_PRIO=100,nice的值在-20到19之前，那么优先级就在100 - 139之间。
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
2 基于这些weight，CFS又是怎么来体现公平的呢？
CFS可实现几种不同的公平策略，这些策略是根据调度的对象的不同来区分的。
默认的是不开组调度的公平策略，即调度的单位是每个调度实体。我们来详细看一下是怎么调度的：
假设现在系统有A，B，C三个进程，A.weight=1,B.weight=2,C.weight=3.那么我们可以计算出整个公平调度队列的总权重是cfs_rq.weight = 6，很自然的想法就是，公平就是你在重量中占的比重的多少来拍你的重要性，那么，A的重要性就是1/6,同理，B和C的重要性分别是2/6,3/6.很显然C最重要就应改被先调度，而且占用的资源也应该最多，即假设A，B,C运行一遍的总时间假设是6个时间单位的话，A占1个单位，B占2个单位，C占三个单位。这就是CFS的公平策略。
linux内核采用了计算公式：
ideal_time = sum_runtime * se.weight/cfs_rq.weightideal_time:每个进程应该运行的时间
sum_runtime:运行队列中所有任务运行完一遍的时间
se.weight:当前进程的权重
cfs.weight:整个cfs_rq的总权重
这里se.weight和cfs.weight根据上面讲解我们可以算出，sum_runtime是怎们计算的呢，linux内核中这是个经验值，其经验公式是：
(1) sum_runtime=sysctl_sched_min_granularity * nr_running（if 进程数 > 5）
(2) sum_runtime=sysctl_sched_latency = 20 ms （if 进程数 <= 5）
注：sysctl_sched_min_granularity =4ms
linux内核代码中是通过一个叫vruntime的变量来实现上面的原理的。
4.4 linux调度策略
调度程序运行时，要在所有可运行状态的进程中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_struct结构中有以下四项：policy、priority、counter、rt_priority。这四项是选择进程的依据。其中，policy是进程的调度策略，用来区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级；counter是进程剩余的时间片，它的起始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度goodness时起重要作用，因此，counter也可以看作是进程的动态优先级。rt_priority是实时进程特有的，用于实时进程间的选择。 调度方法： 1，SCHED_OTHER 分时调度策略，2，SCHED_FIFO实时调度策略，先到先服务3，SCHED_RR实时调度策略，时间片轮转实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。SHCED_RR和SCHED_FIFO的不同：当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。相同点：RR和FIFO都只用于实时任务。创建时优先级大于0(1-99)。按照可抢占优先级调度算法进行。就绪态的实时任务立即抢占非实时任务。 策略： 调度程序运行时，要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_struct 结构中有这么四项：policy， priority ， counter， rt_priority这四项就是调度程序选择进程的依据.其中，policy是进程的调度策略，用来区分两种进程-实时和普通；priority是进程(实时和普通)的优先级；counter 是进程剩余的时间片，它的大小完全由priority决定；rt_priority是实时优先级，这是实时进程所特有的，用于实时进程间的选择。首先，Linux 根据policy从整体上区分实时进程和普通进程，因为实时进程和普通进程度调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，然后，对于同一类型的不同进程，采用不同的标准来选择进程：对于普通进程，Linux采用动态优先调度，选择进程的依据就是进程counter的大小。进程创建时，优先级priority被赋一个初值，一般为0～70之间的数字，这个数字同时也是计数器counter的初值，就是说进程创建时两者是相等的。字面上看，priority是“优先级”、counter是“计数器”的意思，然而实际上，它们表达的是同一个意思-进程的“时间片”。Priority代表分配给该进程的时间片，counter表示该进程剩余的时间片。在进程运行过程中，counter不断减少，而priority保持不变，以便在counter变为0的时候（该进程用完了所分配的时间片）对counter重新赋值。当一个普通进程的时间片用完以后，并不马上用priority对counter进行赋值，只有所有处于可运行状态的普通进程的时间片(p->；；counter==0)都用完了以后，才用priority对counter重新赋值，这个普通进程才有了再次被调度的机会。这说明，普通进程运行过程中，counter的减小给了其它进程得以运行的机会，直至counter减为0时才完全放弃对CPU的使用，这就相对于优先级在动态变化，所以称之为动态优先调度。至于时间片这个概念，和其他不同操作系统一样的，Linux的时间单位也是“时钟滴答”，只是不同操作系统对一个时钟滴答的定义不同而已（Linux为10ms）。进程的时间片就是指多少个时钟滴答，比如，若priority为20，则分配给该进程的时间片就为20个时钟滴答，也就是20*10ms=200ms。Linux中某个进程的调度策略(policy)、优先级(priority)等可以作为参数由用户自己决定，具有相当的灵活性。内核创建新进程时分配给进程的时间片缺省为200ms(更准确的，应为210ms)，用户可以通过系统调用改变它。对于实时进程，Linux采用了两种调度策略，即FIFO(先来先服务调度)和RR（时间片轮转调度）。因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的counter只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。上面已经看到，每个进程有两个优先级，实时优先级就是用来衡量实时进程是否值得运行的.当policy分别为以下值时：1) SCHED_OTHER：这是普通的用户进程，进程的缺省类型，采用动态优先调度策略，选择进程的依据主要是根据进程goodness值的大小。这种进程在运行时，可以被高goodness值的进程抢先。2) SCHED_FIFO：这是一种实时进程，遵守POSIX1.b标准的FIFO(先入先出)调度规则。它会一直运行，直到有一个进程因I/O阻塞，或者主动释放CPU，或者是CPU被另一个具有更高rt_priority的实时进程抢先。在Linux实现中，SCHED_FIFO进程仍然拥有时间片-只有当时间片用完时它们才*释放CPU。因此，如同POSIX1.b一样，这样的进程就象没有时间片(不是采用分时)一样运行。Linux中进程仍然保持对其时间片的记录（不修改counter）主要是为了实现的方便，同时避免在调度代码的关键路径上出现条件判断语句 if (！(current->；；policy&；；SCHED_FIFO)){...}-要知道，其他大量非FIFO进程都需要记录时间片，这种多余的检测只会浪费CPU资源。（一种优化措施，不该将执行时间占10%的代码的运行时间减少到50%；而是将执行时间占90%的代码的运行时间减少到95%。0.9+0.1*0.5=0.95>；；0.1+0.9*0.9=0.91）3) SCHED_RR：这也是一种实时进程，遵守POSIX1.b标准的RR(循环round-robin)调度规则。除了时间片有些不同外，这种策略与SCHED_FIFO类似。当SCHED_RR进程的时间片用完后，就被放到SCHED_FIFO和SCHED_RR队列的末尾。