又来到了一个老生常谈的问题，应用层软件开发的程序员要不要了解和深入学习操作系统呢？ 今天就这个问题开始，来谈谈操作系统中可以说是最重要的一个概念--进程。

      操作系统最主要的两个职能是管理各种资源和为应用程序提供系统调用接口。这其中关键的部分是，cpu到进程的抽象，物理内存到地址空间（虚拟内存）的抽象，磁盘到文件的抽象，而其中后两部分以进程为基础，所以嘛，咱重点来讨论进程，以及与进程密切相关的线程。

一 .先说说概念

进程(process)

狭义的定义：进程就是一段程序的执行过程。

广义定义：进程是一个具有一定独立功能的程序关于某次数据集合的一次运行活动，它是操作系统分配资源的基本单元。

简单来讲进程的概念主要有两点：第一，进程是一个实体。每一个进程都有它自己的地址空间，一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。文本区域存储处理器执行的代码；数据区域存储变量和进程执行期间使用的动态分配的内存；堆栈区域存储着活动过程中调用的指令和本地变量。第二，进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时，它才能成为一个活动的实体，我们称其为进程。

进程状态：进程有三个状态，就绪，运行和阻塞。就绪状态其实就是获取了除cpu外的所有资源，只要处理器分配资源马上就可以运行。运行态就是获取了处理器分配的资源，程序开始执行，阻塞态，当程序条件不够时，需要等待条件满足时候才能执行，如等待I/O操作的时候，此刻的状态就叫阻塞态。

说说程序，程序是指令和数据的有序集合，其本身没有任何运动的含义，是一个静态的概念，而进程则是在处理机上的一次执行过程，它是一个动态的概念。进程是包含程序的，进程的执行离不开程序，进程中的文本区域就是代码区，也就是程序。

线程(thread)

通常在一个进程中可以包含若干个线程，当然一个进程中至少有一个线程，不然没有存在的意义。线程可以利用进程所拥有的资源，在引入线程的操作系统中，通常都是把进程作为分配资源的基本单位，而把线程作为独立运行和独立调度的基本单位，由于线程比进程更小，基本上不拥有系统资源，故对它的调度所付出的开销就会小得多，能更高效的提高系统多个程序间并发执行的程度。

多线程(multiThread)

在一个程序中，这些独立运行的程序片段叫作“线程”（Thread），利用它编程的概念就叫作“多线程处理”。多线程是为了同步完成多项任务，不是为了提高运行效率，而是为了提高资源使用效率来提高系统的效率。线程是在同一时间需要完成多项任务的时候实现的。

最简单的比喻多线程就像火车的每一节车厢，而进程则是火车。车厢离开火车是无法跑动的，同理火车也不可能只有一节车厢。多线程的出现就是为了提高效率。

二、说说区别

1、进程与线程的区别：

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

1) 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.

2) 线程的划分尺度小于进程，使得多线程程序的并发性高。

3) 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

4) 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。

5) 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

三、说说优缺点

线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源的管理和保护；而进程正相反。同时，线程适合于在SMP(多核处理机)机器上运行，而进程则可以跨机器迁移。

四、说说进程和线程的细节，底层构成 和 调度

（一）进程相关的数据结构

为了管理进程，内核必须对每个进程所做的事情进行清楚的描述，例如，内核必须知道进程的优先级，它是在CPU上运行还是因为某些事而被阻塞，给它分配了什么样的地址空间，允许它访问哪个文件等。

这些正是进程描述符的作用---进程描述符都是task_struct 数据结构，它的字段包含了与一个进程相关的所有信息。下图显示了Linux进程描述符

谈谈进程的基本信息。

1）标识一个进程--PID

每个进程都必须拥有它自己的进程描述符；进程和进程描述符之间有非常严格的一一对应关系，所以我们可以方便地使用32位进程描述符地址标识进程。

进程描述符指针（task_struct*）指向这些地址。内核对进程的大部份引用都是通过进程描述符指针进行的。

另一方面，类Unix橾作系统允许用户使用一个叫做进程标识符processID(PID)的数来标识进程，PID存放在task_struct的pid字段中。PID被顺序编号，新创建进程的PID通常是前一个进程的PID加1。不过，PID的值有一个上限，当内核使用的PID达到这个峰值的时候，就必须开始循环使用已闲置的小PID号。在缺省情况下，最大的PID号是32767。

系统管理员可以通过往/proc/sys/kernel/pid_max 这个文件中写入一个更小的值来减小PID的上限值，使PID的上限小于32767。在64位体系结构中，系统管理员可以把PID的上限扩大到4194304。

Linux只支持轻量级进程，不支持线程，但为了弥补这样的缺陷，Linux引入线程组的概念。一个线程组中的所有线程使用和该线程组的领头线程相同的PID，也就是该组中第一个轻量级进程的PID，它被存入进程描述符的tgid字段中。getpid()系统调用返回当前进程的tgid值而不是pid值，因此，一个多线程应用的所有线程共享相同的PID。绝大多数进程都属于一个线程组；而线程组的领头线程其tgid与pid的值相同，因而getpid()系统调用对这类进程所起的作用和一般进程是一样的。

所以，我们得出一个重要的结论，Linux虽不支持线程，但是它有具备支持线程的操作系统的所有特性，后面讲解轻量级进程的概念中还会详细讨论。

2）进程描述符定位

进程是动态实体，其生命周期范围从几毫秒到几个月，因此内核必须同时处理很多进程，并把对应的进程描述符放在动态内存中，而不是放在永久分配给内核的内存区（3G之上的线性地址）。

那么，怎么找到被动态分配的进程描述符呢？我们需要在3G之上线性地址的内存区为每个进程设计一个块—thread_union。

对每个进程来说，我们需要给其分配两个页面，即8192个字节的块，Linux把两个不同数据结构紧凑地存放在一个单独为进程分配的存储区域内：一个是内核态的进程堆栈，另一个是紧挨着进程描述符的小数据结构thread_info，叫做线程描述符。

考虑到效率问题，内核让这8k的空间占据连续两个页框并让第一个页框的起始地址是2^13的倍数。当几乎没有可用的动态内存空间时，就会很难找到这样的两个连续页框，因为空闲空间可能存在大量的碎片（注意，这里是物理空间，见“伙伴系统算法”博文）。因此，在80x86体系结构中，在编译时可以进行设置，以使内核栈和线程描述符跨越一个单独的页框（因为主要存在的单页的碎片）。在“Linux中的分段”的博文中我们已经知道，内核态的进程访问处于内核数据段的栈，也就是我们Linux在3G以上内存空间为每个进程设计这么一个栈的目的，这个栈不同于用户态的进程所用的栈。因为内核控制路径使用很少的栈，因此只需要几千个字节的内核态堆栈。所以，对栈和thread_info来说，8KB足够了。不过，如果只使用一个页框存放这两个结构的话，内核要采用一些额外的栈以防止中断和异常的深度嵌套而引起的溢出。

下图显示了在2页（8KB）内存区中存放两种数据结构的方式。线程描述符驻留于这个内存区的开始位置，而栈从末端向下增长。该图还显示了如何通过task字段与task_struct结构相互关联。

struct thread_info {

struct task_struct    *task;        /* main task structure */

struct exec_domain    *exec_domain;    /* execution domain */

unsigned long        flags;        /* low level flags */

unsigned long        status;        /* thread-synchronous flags */

__u32            cpu;        /* current CPU */

__s32            preempt_count; /* 0 => preemptable, <0 => BUG */

mm_segment_t        addr_limit;    /* thread address space:0-0xBFFFFFFF for user-thead  0-0xFFFFFFFF for kernel-thread*/

struct restart_block    restart_block;

unsigned long           previous_esp;   /* ESP of the previous stack in caseof nested (IRQ) stacks*/

__u8            supervisor_stack[0];

};

esp为CPU栈指针寄存器，用来存放栈顶单元的地址。在80x86系统中，栈起始于末端，并朝这个内存区的起始方向增长。从用户态切换到内核态以后，进程的内核栈总是空的，因此，esp寄存器指向这个栈的顶端。

一旦数据写入堆栈，esp的值就递减。特别要注意，这里的数据是指内核数据，其实用得很少，所以大多数时候这个内核栈是空的。因为thread_info

结构是52个字节的长度，所以内核栈能扩展到8140个字节。C语言使用下列联合结构，方便地表示一个进程的线程描述符和内核栈：

union thread_union {

struct thread_info thread_info;

unsigned long stack[2048]; /* 1024 for 4KB stacks */

};

内核使用alloc_thread_info 和 free_thread_info宏分配和释放存储thread_info结构和内核栈的内存区。

3）标识当前进程

我们再从效率的观点来看，刚才所讲的thread_info结构与内核态堆栈之间的紧密结合提供的主要好处还在：内核很容易从esp寄存器的值获得当前在CPU上正在运行进程的thread_info结构的地址。事实上，如果thread_union的长度是8K（213字节），则内核屏蔽掉esp的低13位有效位就可以获得thread_info结构的基地址；而如果thread_union的长度是4K，内核需要蔽掉esp的低12位有效位。这项工作由current_thread_info()函数来完成，它产生如下一些汇编指令：

movl $0xffffe000,%ecx /* or 0xfffff000 for 4KB stacks */

andl %esp,%ecx

movl %ecx,p

这三条指令执行后，p就是在执行指令的CPU上运行的当前进程的thread_info结构的指针。不过，进程最常用的是进程描述符的地址，而不是thread_info结构的地址。为了获得当前在CPU上运行进程的描述符指针，内核要调用current宏，该宏本质上等价于current_thread_info( )->task，它产生如下汇编指令：

movl $0xffffe000,%ecx /* or 0xfffff000 for 4KB stacks */

andl %esp,%ecx

movl (%ecx),p

因为task字段在thread_info结构中的偏移量为0，所以执行完这三条指令之后，p就是CPU上运行进程的描述符指针。

current宏经常作为进程描述符字段的前缀出现在内核代码中，例如，current->pid返回在CPU上正在执行CPU的进程的PID。

4）进程链表

Linux内核把进程链表把所有进程的描述符链接起来。每个task_struct结构都包含一个list_head类型的tasks字段，这个类型的prev和next字段分别指向前面和后面的的task_struct元素。

进程链表的头是init_task描述符，它是所谓的0进程或swapper进程的进程描述符。init_task的tasks.prev字段指向链表中最后插入的进程描述符的tasks字段。

SET_LINKS 和 REMOVE_LINKS 宏分别用于从进程链表中插入和删除一个进程描述符。这些宏考虑了进程间的父子关系。

另外，还有一个很有用的宏就是for_each_process，它的功能是扫描整个进程链表，其定义如下：

#define for_each_process(p) /

for (p=&init_task; (p=list_entry((p)->tasks.next, /

struct task_struct, tasks) /

) != &init_task; )

5）state字段

进程描述符task_struct结构的state字段描述了进程当前所处的状态。它由一组标志组成，其中每个标志描述一种可能的进程状态。在当前的Linux版本中，这些状态是互斥的，因此，严格意义上来说，只能设置一种状态，其余的标志位将被清除。下面是可能的状态：

可运行状态（TASK_RUNNING）

进程要么在CPU上执行，要么准备执行。

可中断的等待状态（TASK_INTERRUPTIBLE）

进程被挂起（睡眠），直到某个条件变为真。产生一个硬件中断、释放进程正在等待的系统资源、或传递一个信号都是可以唤醒进程的条件（把进程状态放回到TASK_RUNNING）。

不可中断的等待状态（TASK_UNINTERRUPTIBLE）

与可中断的等待状态类似，但有一个例外，把信号传递到该睡眠进程时，不能改变它的状态。这种状态很少用到，但在一些特定条件下（进程必须等待，直到一个不能被中断的时事件发生），这种状态是很有用的。例如，当进程打开一个设备文件，其相应的设备驱动程序开始探测相应的硬件设备时会用到这种状态。探测完成以前，设备驱动程序不能被中断，否则，硬件设备会处于不可预知的状态。

暂停状态（TASK_STOPPED）

进程的执行被暂停。当进程接收到SIGSTOP、SIGTSTP、SIGTTIN或SIGTTOU信号后，进人暂停状态。

跟踪状态（TASK_TRACED）

进程的执行已由debugger程序暂停。当一个进程被另一个进程监控时（例如debugger执行ptrace()系统调用监控一个测试程序）任何信号都可以把这个进程置于TASK_TRACED状态。

还有两个进程状态既可以存放在进程描述符的state字段啊中，也可以存放在exit_state中字段中。从这两个字段的名称可以看出，只有当进程的执行被终止时，进程的状态才会变成此两种中的一种：

僵死状态（EXIT_ZOMBIE）

进程的执行被终止，但是父进程还没发布wait4()或waitpid()系统调用来返回有关死亡进程的信息。发布wait()类系统调用前，内核不能丢弃包含在死进程描述符中的数据，因为父进程可能还需要它。

僵死撤销状态（EXIT_DEAD）

终状态：由于父进程刚发出wait4()或waitpid()系统调用，因而进程由系统删除。为了防止其他执行线程在同一个进程上也执行wait()类系统调用（这也是一种竞争条件），而把进程的状态由僵死（EXIT_ZOMBIE）状态改为僵死撤销状态（EXIT_DEAD）

state字段的值通常用一个简单的赋值语句设置，例如：

p->state = TASK_RUNNING;

内核也使用set_task_state和set_current_state宏：它们分别设置指定进程的状态和当前执行进程的状态。此外，这些宏确保编译程序或CPU控制单元不把赋值操作和其他指令混合。混合指令的顺序有时会导致灾难性的后果。

6）TASK_RUNNING状态的进程链表

当内核寻找到一个新进程在CPU上运行时，必须只考虑可运行进程（即处在TASK_RUNNING状态的进程）。

早先的Linux版本把所有的可运行进程都放在同一个叫做运行队列（runqueue）的链表中，由于维持链表中的进程优先级排序的开销过大，因此，早期的调度程序不得不为选择“最佳”可运行进程而扫描整个队列。

Linux 2.6实现的运行队列有所不同。其目的是让调度程序能在固定的时间内选出“最佳”可运行队列，与进程中可运行的进程数无关。

提高调度程序运行速度的诀窍是建立多个可运行进程链表，每种进程优先级对应一个不同的链表。每个task_struct描述符包含一个list_head类型的字段run_list。如果进程的优先权等于k（其取值范围从0到139），run_list字段就把该进程的优先级链入优先级为k的可运行进程的链表中。此外，在多处理器系统中，每个CPU都有它自己的运行队列，即它自己的进程链表集。这是一个通过使数据结构更复杂来改善性能的典型例子：调度程序的操作效率的确更高了，但运行队列的链表却为此被拆分成140个不同的队列！

内核必须为系统中每个运行队列保存大量的数据，不过运行队列的主要数据结构还是组成运行队列的进程描述符链表，所有这些链表都由一个单独的prio_array_t数据结构来实现。

enqueue_task(p,array)函数把进程描述符（p参数）插入到某个运行队列的链表（基于prio_array_t结构的array参数），其代码本质上等同于如下代码：

list_add_tail(&p->run_list, &array->queue[p->prio]);

__set_bit(p->prio, array->bitmap);

array->nr_active++;

p->array = array;

进程描述符的prio字段存放进程的动态优先权，而array字段是一个指针，指向当前运行队列的proo_array_t数据结构。类似地，dequeue_task(p,array)函数从运行队列的链表中删除一个进程的描述符。

7）进程间关系

父子兄弟关系：

程序创建的进程具有父/子关系。如果一个进程创建多个子进程时，则子进程之间具有兄弟关系。进程0和进程1是由内核创建的；进程1（init）是所有进程的祖先。

在进程描述符中引入几个字段来表示这些关系，我们假设拥有该task_struct结构的这个进程叫P：

real_parent——指向创建了P进程的描述符，如果进程P的父进程不存在，就指向进程1的描述符（因此，如果用户运行了一个后台进程而且退出了shell，后台进程就会变成init的子进程）。

parent——指向P的当前父进程（这种进程的子进程终止时，必须向父进程发信号）。它的值通常与reak_parent一致，但偶尔也可以不同，例如，当另一个进程发出监控P的ptrace系统调用请求时。

children——链表的头部，链表中所有的元素都是P创建的子进程。

sibling——指向兄弟进程链表中的下一个元素或前一个元素的指针，这些兄弟进程的父进程跟P是一样的。

下图显示了一组进程间的亲属关系，进程P0创建了P1，P2，P3，进程P3又创建了P4。

其他关系：此外，进程之间还存在其他关系：一个进程可能是一个进程组或登录会话的领头进程，也可能是一个线程组的领头进程，他还可能跟踪其他进程的执行，下面就列出进程描述符中的一些字段，这些字段建立起了进程P和其他进程之间的关系：

group_leader——P所在进程组的领头进程的描述符指针

signal->pgrp——P所在进程组的领头进程的PID

tgid——P所在线程组的领头进程的PID

signal->session——P的登录会话领头进程的PID

ptrace_children——链表的头，该链表包含所有被debugger程序跟踪的P的子进程

ptrace_list——指向所跟踪进程其实际父进程链表的前一个和下一个元素（用于P被跟踪的时候）

8）PID定位task_struct

再来，内核必须能从进程的PID导出对应的进程描述符指针。例如，为kill()系统调用提供服务时就会发生这种情况：当进程P1希望向另一个进程P2发送一个信号时，P1调用kill()系统调用，其参数为P2的PID，内核从这个PID导出其对应的进程描述符，然后从该task_struct中取出记录挂起信号的数据结构指针。

那么如何得到这个task_struct呢？首先想到for_each_process(p)。不行，虽然顺序扫描进程链表并检查进程描述符的pid字段是可行的，但相当低效。为了加速查找，Linux内核引入了4个散列表。需要4个散列表是因为进程描述符包含了表示不同类型PID的字段，而且每种类型的PID需要它自己的散列表：

PIDTYPE_PID    pid    进程的PID

PIDTYPE_TGID    tgid    线程组领头进程的PID

PIDTYPE_PGID    pgrp    进程组领头进程的PID

PIDTYPE_SID    session    会话领头的PID

内核初始化期间动态地为4个散列表分配空间，并把它们的地址存入pid_hash数组。一个散列表的长度依赖于可用的RAM的容量，例如：一个系统拥有512MB的RAM，那么每个散列表就被存在4个页框中，可拥有2048个表项。

用pid_hashfn宏把PID转化为表索引：

#define pid_hashfn(x) hash_long((unsigned long) x, pidhash_shift)

变量pidhash_shift用来存放表索引的长度（以位为单位的长度，在我们这里是11位）。很多散列函数都使用hash_long()，在32位体系结构中它基本等价于：

unsigned long hash_long(unsigned long val, unsigned int bits)

{

unsigned long hash = val * 0x9e370001UL;

return hash >> (32 - bits);

}

因为我们这里的pidhash_shift等于11，所以pid_hashfn的取值范围是0到2^11 - 1=2047。

正如计算机科学的基础课程所阐述的那样，散列函数并不总能确保PID与表的索引一一对应。两个不同的PID散列到相同的表索引称为冲突（colliding）。Linux利用链表来处理冲突的PID：每个表项是由冲突的进程描述符组成的双向循环链表

（二）进程调度

1）进程调度的目标

1.高效性：高效意味着在相同的时间下要完成更多的任务，调度程序会被频繁的执行，所以调度程序要尽可能高效。

2.加强交互性能：在系统相当的负载下，也要保证系统的响应时间

3.保证公平和避免饥渴

4.SMP调度：调度程序必须支持多处理系统

5.软实时调度：系统必须有效的调用实时进程，但不保证一定满足其要求。

2）进程优先级

进程提供了两种优先级，一种是普通的进程优先级，一种是实时进程优先级。

前者适用SCHED_NORMAL调度策略，后者可选SCHED_FIFO或SCHED_RR调度策略，任何时候，实时进程的优先级都高于普通进程，实时进程只会被更高级的实时进程抢占，同级实时进程之间是按照FIFO（一次机会做完）或者RR（多次轮转）规则调度的。

实时进程，只有静态优先级，因为内核不会再根据休眠等因素对其静态优先级做调整，其范围在0~MAX_RT_PRIO-1间。默认MAX_RT_PRIO配置为100，也即，默认的实时优先级范围是0~99。而nice值，影响的是优先级在MAX_RT_PRIO~MAX_RT_PRIO+40范围内的进程。

不同与普通进程，系统调度时，实时优先级高的进程总是先于优先级低的进程执行，直到实时优先级高的实时进程无法执行。实时进程总是被认为处于活动状态。如果有数个 优先级相同的实时进程，那么系统就会按照进程出现在队列上的顺序选择进程，假设当前CPU运行的实时进程A的优先级为a，而此时有个优先级为b的实时进程B进入可运行状态，那么只要b<a,系统将中断A的执行，而优先执行B，直到B无法执行（无论A，B为何种实时进程）。

不同调度策略的实时进程只有在相同优先级时才有可比性：

1. 对于FIFO的进程，意味着只有当前进程执行完毕才会轮到其他进程执行。由此可见相当霸道。

2. 对于RR的进程。一旦时间片消耗完毕，则会将该进程置于队列的末尾，然后运行其他相同优先级的进程，如果没有其他相同优先级的进程，则该进程会继续执行。

总而言之，对于实时进程，高优先级的进程就是大爷。它执行到没法执行了，才轮到低优先级的进程执行。

普通进程的调度

Linux对于普通的进程，根据动态优先级进行调度，而动态优先级是由静态优先级调整而来，Linux下，静态优先级是用户不可见的，隐藏在内核中，而内核提供给用户一个可以影响静态优先级的接口，那就是nice值。

关系如下：

static_prio =MAX_RT_PRIO+nice+20

nice值的范围是-20~19，因而静态优先级范围在100~139之间,nice数值越大就使得static_prio越大，最终进程优先级就越低。

我们前面也说了，系统调度时，还会考虑其他因素，因而会计算出一个叫进程动态优先级的东西，根据此来实施调度。因为，不仅要考虑静态优先级，也要考虑进程

的属性。例如如果进程属于交互式进程，那么可以适当的调高它的优先级，使得界面反应地更加迅速，从而使用户得到更好的体验。Linux2.6

在这方面有了较大的提高。Linux2.6认为，交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多，则越有

可能属于交互式进程。则系统调度时，会给该进程更多的奖励（bonus），以便该进程有更多的机会能够执行。奖励（bonus）从0到10不等。

系统会严格按照动态优先级高低的顺序安排进程执行。动态优先级高的进程进入非运行状态，或者时间片消耗完毕才会轮到动态优先级较低的进程执行。动态优先级的计算主要考虑两个因素：静态优先级，进程的平均睡眠时间也即bonus。计算公式如下，

dynamic_prio = max (100, min (static_prio - bonus + 5, 139))

为什么根据睡眠和运行时间确定奖惩分数是合理的

睡眠和CPU耗时反应了进程IO密集和CPU密集两大瞬时特点，不同时期，一个进程可能即是CPU密集型也是IO密集型进程。对于表现为IO密集的进程，应该经常运行，但每次时间片不要太长。对于表现为CPU密集的进程，CPU不应该让其经常运行，但每次运行时间片要长。交互进程为例，假如之前其其大部分时间在于等待CPU，这时为了调高相应速度，就需要增加奖励分。另一方面，如果此进程总是耗尽每次分配给它的时间片，为了对其他进程公平，就要增加这个进程的惩罚分数。可以参考CFS的virtutime机制.

3）现代方法CFS

不再单纯依靠进程优先级绝对值，而是参考其绝对值，综合考虑所有进程的时间，给出当前调度时间单位内其应有的权重，也就是，每个进程的权重X单位时间=应获cpu时间，但是这个应得的cpu时间不应太小（假设阈值为1ms），否则会因为切换得不偿失。但是，当进程足够多时候，肯定有很多不同权重的进程获得相

同的时间——最低阈值1ms，所以，CFS只是近似完全公平。

4）Linux进程状态机

进程是通过fork系列的系统调用（fork clone，vfork）来创建的，内核，内核模块也可以通过kernel_thread函数创建内核进程，这些创建子进程的函数本质上都完成了相同的功能——将调用进程复制一份，得到子进程。（可以通过选项参数来决定各种资源是共享、还是私有。）那么既然调用进程处于TASK_RUNNING状态（否则，它若不是正在运行，又怎么进行调用？），则子进程默认也处于TASK_RUNNING状态。

另外，在系统调用clone和内核函数kernel_thread也接受CLONE_STOPPED选项，从而将子进程的初始状态置为 TASK_STOPPED。

进程创建后，状态可能发生一系列的变化，直到进程退出。而尽管进程状态有好几种，但是进程状态的变迁却只有两个方向——从TASK_RUNNING状态变为非TASK_RUNNING状态、或者从非TASK_RUNNING状态变为TASK_RUNNING状态。总之，TASK_RUNNING是必经之路，不可能两个非RUN状态直接转换。

也就是说，如果给一个TASK_INTERRUPTIBLE状态的进程发送SIGKILL信号，这个进程将先被唤醒（进入TASK_RUNNING状态），然后再响应SIGKILL信号而退出（变为TASK_DEAD状态）。并不会从TASK_INTERRUPTIBLE状态直接退出。

进程从非TASK_RUNNING状态变为TASK_RUNNING状态，是由别的进程（也可能是中断处理程序）执行唤醒操作来实现的。执行唤醒的

进程设置被唤醒进程的状态为TASK_RUNNING，然后将其task_struct结构加入到某个CPU的可执行队列中。于是被唤醒的进程将有机会被

调度执行。

而进程从TASK_RUNNING状态变为非TASK_RUNNING状态，则有两种途径：

1、响应信号而进入TASK_STOPED状态、或TASK_DEAD状态；

2、执行系统调用主动进入TASK_INTERRUPTIBLE状态（如nanosleep系统调用）、或TASK_DEAD状态（如exit系统调用）；或由于执行系统调用需要的资源得不到满　　　　 足，而进入TASK_INTERRUPTIBLE状态或TASK_UNINTERRUPTIBLE状态（如select系统调用）。

显然，这两种情况都只能发生在进程正在CPU上执行的情况下。

通过ps命令我们能够查看到系统中存在的进程，以及它们的状态：R(TASK_RUNNING)，可执行状态。

只有在该状态的进程才可能在CPU上运行。而同一时刻可能有多个进程处于可执行状态，这些进程的task_struct结构（进程控制块）被放入对应CPU的可执行队列中（一个进程最多只能出现在一个CPU的可执行队列中）。进程调度器的任务就是从各个CPU的可执行队列中分别选择一个进程在该CPU上运行。

只要可执行队列不为空，其对应的CPU就不能偷懒，就要执行其中某个进程。一般称此时的CPU“忙碌”。对应的，CPU“空闲”就是指其对应的可执行队列为空，以致于CPU无事可做。

有人问，为什么死循环程序会导致CPU占用高呢？因为死循环程序基本上总是处于TASK_RUNNING状态（进程处于可执行队列中）。除非一些非常极端情况（比如系统内存严重紧缺，导致进程的某些需要使用的页面被换出，并且在页面需要换入时又无法分配到内存……），否则这个进程不会睡眠。所以CPU的可执行队列总是不为空（至少有这么个进程存在），CPU也就不会“空闲”。

很多操作系统教科书将正在CPU上执行的进程定义为RUNNING状态、而将可执行但是尚未被调度执行的进程定义为READY状态，这两种状态在linux下统一为 TASK_RUNNING状态。

S(TASK_INTERRUPTIBLE)，可中断的睡眠状态。

处于这个状态的进程因为等待某某事件的发生（比如等待socket连接、等待信号量），而被挂起。这些进程的task_struct结构被放入对应事件的等待队列中。当这些事件发生时（由外部中断触发、或由其他进程触发），对应的等待队列中的一个或多个进程将被唤醒。

通过ps命令我们会看到，一般情况下，进程列表中的绝大多数进程都处于TASK_INTERRUPTIBLE状态（除非机器的负载很高）。毕竟CPU就这么一两个，进程动辄几十上百个，如果不是绝大多数进程都在睡眠，CPU又怎么响应得过来。

D(TASK_UNINTERRUPTIBLE)，不可中断的睡眠状态。

与TASK_INTERRUPTIBLE状态类似，进程处于睡眠状态，但是此刻进程是不可中断的。不可中断，指的并不是CPU不响应外部硬件的中断，而是指进程不响应异步信号。

绝大多数情况下，进程处在睡眠状态时，总是应该能够响应异步信号的。否则你将惊奇的发现，kill -9竟然杀不死一个正在睡眠的进程了！于是我们也很好理解，为什么ps命令看到的进程几乎不会出现TASK_UNINTERRUPTIBLE状态，而总是TASK_INTERRUPTIBLE状态。

而TASK_UNINTERRUPTIBLE状态存在的意义就在于，内核的某些处理流程是不能被打断的。如果响应异步信号，程序的执行流程中就会被插入一段用于处理异步信号的流程（这个插入的流程可能只存在于内核态，也可能延伸到用户态），于是原有的流程就被中断了（参见《linux异步信号handle浅析》）。

在进程对某些硬件进行操作时（比如进程调用read系统调用对某个设备文件进行读操作，而read系统调用最终执行到对应设备驱动的代码，并与对应的物理设备进行交互），可能需要使用TASK_UNINTERRUPTIBLE状态对进程进行保护，以避免进程与设备交互的过程被打断，造成设备陷入不可控的状态。（比如read系统调用触发了一次磁盘到用户空间的内存的DMA，如果DMA进行过程中，进程由于响应信号而退出了，那么DMA正在访问的内存可能就要被释放了。）这种情况下的TASK_UNINTERRUPTIBLE状态总是非常短暂的，通过ps命令基本上不可能捕捉到。

linux系统中也存在容易捕捉的TASK_UNINTERRUPTIBLE状态。执行vfork系统调用后，父进程将进入TASK_UNINTERRUPTIBLE状态，直到子进程调用exit或exec。

通过下面的代码就能得到处于TASK_UNINTERRUPTIBLE状态的进程：

#include

void main() {

if (!vfork()) sleep(100);

}

向进程发送一个SIGSTOP信号，它就会因响应该信号而进入TASK_STOPPED状态（除非该进程本身处于TASK_UNINTERRUPTIBLE状态而不响应信号）。（SIGSTOP与SIGKILL信号一样，是非常强制的。不允许用户进程通过signal系列的系统调用重新设置对应的信号处理函数。）

向进程发送一个SIGCONT信号，可以让其从TASK_STOPPED状态恢复到TASK_RUNNING状态。

当进程正在被跟踪时，它处于TASK_TRACED这个特殊的状态。“正在被跟踪”指的是进程暂停下来，等待跟踪它的进程对它进行操作。比如在gdb中对被跟踪的进程下一个断点，进程在断点处停下来的时候就处于TASK_TRACED状态。而在其他时候，被跟踪的进程还是处于前面提到的那些状态。

对于进程本身来说，TASK_STOPPED和TASK_TRACED状态很类似，都是表示进程暂停下来。

而TASK_TRACED状态相当于在TASK_STOPPED之上多了一层保护，处于TASK_TRACED状态的进程不能响应SIGCONT信号而被唤醒。只能等到调试进程通过ptrace系统调用执行PTRACE_CONT、PTRACE_DETACH等操作（通过ptrace系统调用的参数指定操作），或调试进程退出，被调试的进程才能恢复TASK_RUNNING状态。

Z(TASK_DEAD - EXIT_ZOMBIE)，退出状态，进程成为僵尸进程。

进程在退出的过程中，处于TASK_DEAD状态。

在这个退出过程中，进程占有的所有资源将被回收，除了task_struct结构（以及少数资源）以外。于是进程就只剩下task_struct这么个空壳，故称为僵尸。

之所以保留task_struct，是因为task_struct里面保存了进程的退出码、以及一些统计信息。而其父进程很可能会关心这些信息。比如在shell中，$?变量就保存了最后一个退出的前台进程的退出码，而这个退出码往往被作为if语句的判断条件。

当然，内核也可以将这些信息保存在别的地方，而将task_struct结构释放掉，以节省一些空间。但是使用task_struct结构更为方便，因为在内核中已经建立了从pid到task_struct查找关系，还有进程间的父子关系。释放掉task_struct，则需要建立一些新的数据结构，以便让父进程找到它的子进程的退出信息。

父进程可以通过wait系列的系统调用（如wait4、waitid）来等待某个或某些子进程的退出，并获取它的退出信息。然后wait系列的系统调用会顺便将子进程的尸体（task_struct）也释放掉。

子进程在退出的过程中，内核会给其父进程发送一个信号，通知父进程来“收尸”。这个信号默认是SIGCHLD，但是在通过clone系统调用创建子进程时，可以设置这个信号。

通过下面的代码能够制造一个EXIT_ZOMBIE状态的进程：

#include

void main() {

if (fork())

while(1) sleep(100);

}

编译运行，然后ps一下：

kouu@kouu-one:~/test$ ps -ax | grep a\.out

10410 pts/0      S+      0:00 ./a.out

10411 pts/0      Z+      0:00 [a.out]

10413 pts/1      S+      0:00 grep a.out

只要父进程不退出，这个僵尸状态的子进程就一直存在。那么如果父进程退出了呢，谁又来给子进程“收尸”？

当进程退出的时候，会将它的所有子进程都托管给别的进程（使之成为别的进程的子进程）。托管给谁呢？可能是退出进程所在进程组的下一个进程（如果存在的话），或者是1号进程。所以每个进程、每时每刻都有父进程存在。除非它是1号进程。

1号进程，pid为1的进程，又称init进程。

linux系统启动后，第一个被创建的用户态进程就是init进程。它有两项使命：

1、执行系统初始化脚本，创建一系列的进程（它们都是init进程的子孙）；

2、在一个死循环中等待其子进程的退出事件，并调用waitid系统调用来完成“收尸”工作；

init进程不会被暂停、也不会被杀死（这是由内核来保证的）。它在等待子进程退出的过程中处于TASK_INTERRUPTIBLE状态，“收尸”过程中则处于TASK_RUNNING状态。

X(TASK_DEAD - EXIT_DEAD)，退出状态，进程即将被销毁。

而进程在退出过程中也可能不会保留它的task_struct。比如这个进程是多线程程序中被detach过的进程（进程？线程？参见《linux线程浅析》）。或者父进程通过设置SIGCHLD信号的handler为SIG_IGN，显式的忽略了SIGCHLD信号。（这是posix的规定，尽管子进程的退出信号可以被设置为SIGCHLD以外的其他信号。）

此时，进程将被置于EXIT_DEAD退出状态，这意味着接下来的代码立即就会将该进程彻底释放。所以EXIT_DEAD状态是非常短暂的，几乎不可能通过ps命令捕捉到。

5）调度触发的时机

调度的触发主要有如下几种情况：

1、当前进程（正在CPU上运行的进程）状态变为非可执行状态。

进程执行系统调用主动变为非可执行状态。比如执行nanosleep进入睡眠、执行exit退出、等等；

进程请求的资源得不到满足而被迫进入睡眠状态。比如执行read系统调用时，磁盘高速缓存里没有所需要的数据，从而睡眠等待磁盘IO；

进程响应信号而变为非可执行状态。比如响应SIGSTOP进入暂停状态、响应SIGKILL退出、等等；

2、抢占。进程运行时，非预期地被剥夺CPU的使用权。这又分两种情况：进程用完了时间片、或出现了优先级更高的进程。

优先级更高的进程受正在CPU上运行的进程的影响而被唤醒。如发送信号主动唤醒，或因为释放互斥对象（如释放锁）而被唤醒；

内核在响应时钟中断的过程中，发现当前进程的时间片用完；

内核在响应中断的过程中，发现优先级更高的进程所等待的外部资源的变为可用，从而将其唤醒。比如CPU收到网卡中断，内核处理该中断，发现某个socket可读，于是唤醒正在等待读这个socket的进程；再比如内核在处理时钟中断的过程中，触发了定时器，从而唤醒对应的正在nanosleep系统调用中睡眠的进程；

6）内核抢占

理想情况下，只要满足“出现了优先级更高的进程”这个条件，当前进程就应该被立刻抢占。但是，就像多线程程序需要用锁来保护临界区资源一样，内核中也存在很多这样的临界区，不大可能随时随地都能接收抢占。

linux 2.4时的设计就非常简单，内核不支持抢占。进程运行在内核态时（比如正在执行系统调用、正处于异常处理函数中），是不允许抢占的。必须等到返回用户态时才会触发调度（确切的说，是在返回用户态之前，内核会专门检查一下是否需要调度）；

linux 2.6则实现了内核抢占，但是在很多地方还是为了保护临界区资源而需要临时性的禁用内核抢占。

也有一些地方是出于效率考虑而禁用抢占，比较典型的是spin_lock。spin_lock是这样一种锁，如果请求加锁得不到满足（锁已被别的进程占有），则当前进程在一个死循环中不断检测锁的状态，直到锁被释放。

为什么要这样忙等待呢？因为临界区很小，比如只保护“i+=j++;”这么一句。如果因为加锁失败而形成“睡眠-唤醒”这么个过程，就有些得不偿失了。

那么既然当前进程忙等待（不睡眠），谁又来释放锁呢？其实已得到锁的进程是运行在另一个CPU上的，并且是禁用了内核抢占的。这个进程不会被其他进程抢占，所以等待锁的进程只有可能运行在别的CPU上。（如果只有一个CPU呢？那么就不可能存在等待锁的进程了。）

而如果不禁用内核抢占呢？那么得到锁的进程将可能被抢占，于是可能很久都不会释放锁。于是，等待锁的进程可能就不知何年何月得偿所望了。

对于一些实时性要求更高的系统，则不能容忍spin_lock这样的东西。宁可改用更费劲的“睡眠-唤醒”过程，也不能因为禁用抢占而让更高优先级的进程等待。比如，嵌入式实时linux montavista就是这么干的。

由此可见，实时并不代表高效。很多时候为了实现“实时”，还是需要对性能做一定让步的。

7）多处理器下的负载均衡

前面我们并没有专门讨论多处理器对调度程序的影响，其实也没有什么特别的，就是在同一时刻能有多个进程并行地运行而已。那么，为什么会有“多处理器负载均衡”这个事情呢？

如果系统中只有一个可执行队列，哪个CPU空闲了就去队列中找一个最合适的进程来执行。这样不是很好很均衡吗？

的确如此，但是多处理器共用一个可执行队列会有一些问题。显然，每个CPU在执行调度程序时都需要把队列锁起来，这会使得调度程序难以并行，可能导致系统性能下降。而如果每个CPU对应一个可执行队列则不存在这样的问题。

另外，多个可执行队列还有一个好处。这使得一个进程在一段时间内总是在同一个CPU上执行，那么很可能这个CPU的各级cache中都缓存着这个进程的数据，很有利于系统性能的提升。

所以，在linux下，每个CPU都有着对应的可执行队列，而一个可执行状态的进程在同一时刻只能处于一个可执行队列中。

于是，“多处理器负载均衡”这个麻烦事情就来了。内核需要关注各个CPU可执行队列中的进程数目，在数目不均衡时做出适当调整。什么时候需要调整，以多大力度进程调整，这些都是内核需要关心的。当然，尽量不要调整最好，毕竟调整起来又要耗CPU、又要锁可执行队列，代价还是不小的。

另外，内核还得关心各个CPU的关系。两个CPU之间，可能是相互独立的、可能是共享cache的、甚至可能是由同一个物理CPU通过超线程技术虚拟出来的……CPU之间的关系也是实现负载均衡的重要依据。关系越紧密，进程在它们之间迁移的代价就越小。参见《linux内核SMP负载均衡浅析》。

优先级继承

由于互斥，一个进程（设为A）可能因为等待进入临界区而睡眠。直到正在占有相应资源的进程（设为B）退出临界区，进程A才被唤醒。

可能存在这样的情况：A的优先级非常高，B的优先级非常低。B进入了临界区，但是却被其他优先级较高的进程（设为C）抢占了，而得不到运行，也就无法退出临界区。于是A也就无法被唤醒。

A有着很高的优先级，但是现在却沦落到跟B一起，被优先级并不太高的C抢占，导致执行被推迟。这种现象就叫做优先级反转。

出现这种现象是很不合理的。较好的应对措施是：当A开始等待B退出临界区时，B临时得到A的优先级（还是假设A的优先级高于B），以便顺利完成处理过程，退出临界区。之后B的优先级恢复。这就是优先级继承的方法。

中断处理线程化

在linux下，中断处理程序运行于一个不可调度的上下文中。从CPU响应硬件中断自动跳转到内核设定的中断处理程序去执行，到中断处理程序退出，整个过程是不能被抢占的。

一个进程如果被抢占了，可以通过保存在它的进程控制块（task_struct）中的信息，在之后的某个时间恢复它的运行。而中断上下文则没有task_struct，被抢占了就没法恢复了。

中断处理程序不能被抢占，也就意味着中断处理程序的“优先级”比任何进程都高（必须等中断处理程序完成了，进程才能被执行）。但是在实际的应用场景中，可能某些实时进程应该得到比中断处理程序更高的优先级。

于是，一些实时性要求更高的系统就给中断处理程序赋予了task_struct以及优先级，使得它们在必要的时候能够被高优先级的进程抢占。但是显然，做这些工作是会给系统造成一定开销的，这也是为了实现“实时”而对性能做出的一种让步。

（三）进程同步与互斥

多进程系统中避免不了进程之间的相互关系，最主要是两种关系--同步和互斥。

进程同步 是进程间直接的相互作用，是合作进程间的有意识的行为。我们也要有一定的同步机制保证它们的执行次序。

进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段称为临界区。两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。互斥问题可以用硬件方法解决，也可以用软件方法。

同步是说进程的合作关系，互斥是说进程对资源的竞争关系。

信号量、管程

二，管程：参考自http://hi.baidu.com/zucenaa/blog/item/e63d22277c9d9c09918f9de2.html

信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。因此后

来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联

系清晰，便于维护和修改，易于保证正确性。

管程作为一个模块，它的类型定义如下：

monitor_name = MoNITOR;

共享变量说明;

define 本管程内部定义、外部可调用的函数名表;

use 本管程外部定义、内部可调用的函数名表;

内部定义的函数说明和函数体

{

共享变量初始化语句;

}

从语言的角度看，管程主要有以下特性：

（1）模块化。管程是一个基本程序单位，可以单独编译;

（2）抽象数据类型。管程是中不仅有数据，而且有对数据的操作;

（3）信息掩蔽。管程外可以调用管程内部定义的一些函数，但函数的具体实现外部不可见;

对于管程中定义的共享变量的所有操作都局限在管程中，外部只能通过调用管程的某些函数来间接访问这些变量。因此管程有很好的封装性。

为了保证共享变量的数据一致性，管程应互斥使用。 管程通常是用于管理资源的，因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列，称为入口等待队列。当一个已进入管程的进程等待时，就释放管程的互斥使用权；当已进入管程的一个进程唤醒另一个进程时，两者必须有一个退出或停止使用管程。在管程内部，由于执行唤醒操作，可能存在多个等待进程（等待使用管程），称为紧急等待队列，它的优先级高于入口等待队列。

因此，一个进程进入管程之前要先申请，一般由管程提供一个enter过程；离开时释放使用权，如果紧急等待队列不空，则唤醒第一个等待者，一般也由管程提供外部过程leave。

管程内部有自己的等待机制。管程可以说明一种特殊的条件型变量：var c:condition；实际上是一个指针，指向一个等待该条件的PCB队列。对条件型变量可执行wait和signal操作：（联系P和V； take和give）

wait(c):若紧急等待队列不空，唤醒第一个等待者，否则释放管程使用权。执行本操作的进程进入C队列尾部；

signal(c):若C队列为空，继续原进程，否则唤醒队列第一个等待者，自己进入紧急等待队列尾部。

（四）进程间通信（IPC）

进程间通信主要包括 管道，系统IPC(包括消息队列,信号量,共享内存), SOCKET.

管道分为有名管道和无名管道，无名管道只能用于亲属进程之间的通信，而有名管道则可用于无亲属关系的进程之间。

消息队列用于运行于同一台机器上的进程间通信，与管道相似；

消息队列用于运行于同一台机器上的进程间通信，与管道相似；

共享内存通常由一个进程创建，其余进程对这块内存区进行读写。得到共享内存有两种方式：映射/dev/mem设备和内存映像文件。前一种方式不给系统带来额外的开销，但在现实中并不常用，因为它控制存取的是实际的物理内存；

本质上，信号量是一个计数器，它用来记录对某个资源（如共享内存）的存取状况。一般说来，为了获得共享资源，进程需要执行下列操作：

（1）测试控制该资源的信号量；

（2）若此信号量的值为正，则允许进行使用该资源，进程将进号量减1；

（3）若此信号量为0，则该资源目前不可用，进程进入睡眠状态，直至信号量值大于0，进程被唤醒，转入步骤（1）；

（4）当进程不再使用一个信号量控制的资源时，信号量值加1，如果此时有进程正在睡眠等待此信号量，则唤醒此进程。

套接字通信并不为Linux所专有，在所有提供了TCP/IP协议栈的操作系统中几乎都提供了socket，而所有这样操作系统，对套接字的编程方法几乎是完全一样的。

管道：速度慢，容量有限，只有父子进程能通讯

FIFO（命名管道）：任何进程间都能通讯，但速度慢，命名管道可用于非父子进程，命名管道就是FIFO，管道是先进先出的通讯方式

消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题

信号量：不能传递复杂消息，只能用来同步

共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存。

线程

线程是CPU调度的最小单位，多个线程共享一个进程的地址空间。

线程包含线程ID，程序计数器，寄存器和栈。

（一）线程调度

（二）线程同步