Linux内核学习：进程

进程基本概念

进程是Unix及其衍生操作系统的根本，通常我们把一个程序的执行称为一个进程，换句话说，进程用于描述程序的执行过程。进程不能笼统地作为程序+执行的结果，从内核的观点看，进程的目的就是担当分配系统资源的实体，也是操作系统进行资源分配的一个基本单位。

进程所涉及的资源一般指：内存地址空间、文件描述符、线程栈和寄存器等。

进程并不仅仅局限于一段可执行的代码段，通常进程还包含各种资源（打开的文件、挂起的信号、内存管理信息、处理器状态、一个或多个内存映射的内存地址空间以及一个或多个线程，当然还包含用来存放全局变量的数据段等）。

总结一句就是：程序本身并不是进程，进程（内核也叫任务）是处于执行期间的程序以及相关的资源的总称。

进程组织结构

进程在Linux中被组织成父子关系，所谓子进程就是父进程使用 fork 可以创建若干新的进程，子进程都是源自它的父进程的一个副本，它会获得父进程的数据段、堆、栈的副本，并且与父进程共享代码段。forK函数用于通过自己的进程号创建自身进程的一个复制，然后调用exec()才能开始执行不同的程序；

• fork 函数在现代Linux中，实际上是由clone()系统调用实现的，它的调用从内核返回两次：一次是回到父进程、另一次回到新产生的子进程。所以fork的实际开销是复制父进程的页表以及子进程创建唯一的进程描述符

• exec 函数负责读取可执行文件，创建新的地址空间并将其载入地址空间开始执行

COW技术是Linx提高进程创建效率的技术

实现进程所必须付出的代价是：进程调度、资源竞争、进程通讯、进程关系等。所以Linux必须进来降低创建进程所带来的消耗。

每一个副本（内存单元）都是独立的，子进程对于属于它的副本的修改对其父进程和兄弟进程都是不可见的。挡子进程对副本修改的时候，Linux使用写时复制COW技术通过添加原有地址空间的引用而非把所有的内容都复制一遍，一旦任何进程有所修改，就会针对这个修改创建一个副本。

子进程和父进程区别仅仅在于PID、PPID和某些资源和统计量（如：挂起信号）

进程是动态实体

在Linx中每个进程时刻都有状态的，也必然处于下图的其中一种

RUNNING（运行）：进程是可执行的；它或者正在执行，或者在运行队列中等待执行。这是进行再用户空间中执行的唯一可能的状；这种状态也可以应用到内核空间中正在执行的进程。

INTERRUPTIBLE（可中断）：进程正在睡眠（也就是说它被阻塞），等待某些条件的达成。一旦这些条件达成，内核就会把进程状态设置为运行。处于此状态的进程也会因为接收到信号而提前被唤醒并随时准备投入与运行。

UNINTERRUPTIBLE（不可中断）：除了就算接收到信号也不会被唤醒或准备投入运行外，这个状态与可中断状态相同。这个状态通常在进程必须在等待时不受干扰或等待事件很快就会发生时出现。由于此状态的任务对信号不做响应，所以较之可中断状态，使用得较少。UNINTERRUPTIBLE最典型的例子是进程等待磁盘I/O操作。

STOPPED（退出）：进程由于特定的信号（如SIGINT、SIGSTOP）而挂起就会处于这个状态，等待恢复信号，比如SINCONT

ZOMBIE（僵尸）：进程在使用exit()系统调用退出以后，父进程应该知道进程终结。在ZOMBIE状态中，进程在等待父进程收到通知并释放所有的数据结构。子进程的退出，父进程要调用wait或waitpid函数等待回收子进程的资源，否则子进程就一直处于“僵尸”状态存在。

进程与线程

Linux使用轻量级进程（lightweight process）对多线程应用提供更好的支持哦，两个轻量级进程基本上可以共享一些资源，诸如地址空间、打开文件等。只要其中一个修改了共享资源，另外一个立即查看到这种修改。

我们现在写用户空间的代码时只认识进程和线程，因为用户空间是内核的接口产品，用户的程序员对整个世界的认识例如用户空间看到进程和线程时，大部分程序员都能说出进程与线程的区别，但在内核，线程和进程没有太大的区别，从内核的角度上看，它没有线程这个概念，线程被一样拥有自己的task_struct，它在内核眼中只是一个与其它进程共享某些资源的进程（用户空间看到它们之间的区别其实就是被伪造出来的）。

Linux内核调度的对象是线程，不是进程！线程是进程中的活动对象，是调度的最小单元。每个线程都拥有独立的资源空间（程序计数器、进程栈和一些寄存器）。

线程机制是现代编程技术中常用的一种抽象概念，改机制提供了在同一程序内共享地址运行的一组线程，这些资源还可以共享打开的文件和其它资源。

内核线程拥有独立的地址空间，它表示内核在后台执行的一些任务（刷新磁盘高速缓存、交换出不同的页框、维护网络连接等）

进程描述符

内核把进程的列表存放在任务队列（task list）的双向循环链表中，这个链表中的每一项为进程描述符，类型为 task_struct，这个文件描述符是存在于动态内存中，而不是永久分配给内核的内存区。

task_struct也被称为进程描述符，为了对象服用、缓存着色等目的，Linux通过Slab分配器进程分配的。

在内核中进程（任务）的访问通常需要获得task_struct的指针，例如在X86架构的内核栈的尾端创建thread_info结构，通过计算偏移间接地查找task_struct结构

进程和进程描述符之间有这非常严格的一一对应关系

进程上下文

程序执行过程中，进程的信息存放在处理器的寄存器和缓存中。部分执行中进程存放在寄存器中的数据就叫做context（上下文）。所谓的进程上下文切换是指正在处理的进程上下文被保存起来，把下一个要执行的进程的上下文恢复到寄存器。

相关工作图如下：

进程调度

调度基本概念

当前Linux内核使用的是O(1)而不是O(n)来实现CPU调度，这种基于O(1)的是一种静态算法：处理器选择和调用进程开始执行的时间是一个常数，不论多少进程数量的情况都是如此。

通过调度器在各个进程之间尽可能公平地共享CPU时间，而同时又要考虑不同的进程（任务）优先级，达到有效地分配CPU时间片的目的；调度器调度的是CPU资源，按照特定的规则分配给特定的进程，然后进程会去申请或使用硬件资源。

在介绍Linux内核的调度器之前，我们先列出调度器需要涉及的两类问题

• 对于调度器

  • 调度程序在运行时，如何确定哪一个程序会被调度使用CPU资源
  • 如何不让任何一个进程饥饿
  • 如何更快地定位和响应交互式进程
  • 单个CPU只有一个流水线，能否一次调度多个进程，同时使用多个CPU的物理资源
  • 调度来的CPU如何让其释放资源？是任其释放还是有相关回收机制？

• 对于希望被调度的进程

  • 如何定义自己被调度的概率
  • 如何等待的同时接收信号
  • 如何避免自己希望占用的资源在没有被调度时不被别的进程占用

调度策略

Linux的调度作用于 分时系统 和 实时系统;Linux的调度往往也是基于分时系统的，所谓的分时就是指多个进程以“时间多路复用”的方式运行。Linx本身不是实时系统，但实现了相关的接口。

对于整个这个内核而言，调度的策略可以分为四种：

• SCHED_NORMAL：针对普通进程，每个普通进程都有自己的静态优先级，调度程序使用静态优先级来评估普通进程之间调度的程度，静态优先级越高，基本时间片越长。

• SCHED_FIFO：除非主动释放，否则最高优先级的进程用于不释放CPU；如果没有其它可运行的更高的优先级实时进程，进程就会继续使用CPU，想用多久就用多久

• SCHED_RR：即使最高优先级的进程，在时间片用完，也会释放CPU；基于时间片轮转的实时进程，保证相同优先级的实时进程公平地分配CPU时间

• SCHED_BATCH：例如磁盘整理操作，GCC编译等也是这种策略的

实时进程基本时间片的长度与实时进程的优先级无关，而依赖进程的静态优先级。

普通进程的静态优先级全部为0，区别普通调度程序可以使用动态优先级（nice 1~99）

调度策略也是根据进程的优先级（动态）对它们进行分类的：调度器跟踪它们，并周期性地调整它们的优先级。

动态优先级在调度程序在选择新的进程来运行程序的时候会使用它。

动态优先级 = max(100, min(静态优先级 - bonus + 5, 139))

bonus的范围是（0~10），与进程的平均睡眠时间有关（并非对过去的时间求平均值）；平均睡眠也被调度程序确认一个给定的进程还是交互进程还是批处理进程

SCHED_FIFO 与 SCHED_RR 主要针对实时进程，Linux2.6实现了基于进程过去行为的启发算法，以确定进程应该被当做是交互式还是批处理式进程对待，因为Linx是抢占式的，如果进程进入了TASK_RUNNING状态，内核就会检查它的动态优先级是否大于当前的运行优先级，如果是，当前的进程会被中断，并调用调度器程序选择另外一个进程执行，当然进程在它的时间片到期也是可以被强占的。

被强占的进程并没有被挂起，因为它还处于TASK_RUNNING，只不过不再使用CPU。

调度策略通常要在两个矛盾的目标中寻找平衡：进程响应速度和最大系统利用率，换句话说就是时间片的长短对系统很关键，不能太长，也不能太短。如果太长看起来就不是并发执行了，如果太短了，切换的开销很高。

Linux采用单凭经验的方式：尽可能长，同时保持良好的响应时间一个时间片。为什么进可能长没问题？因为时间片哪怕长不会降低交互式进程的响应时间，由于交互式进行相对拥有很好的优先级，很快地强占批处理进程的任务

Linux的调度经历了从 O(n) 到 O(1) 再到公平调度等的阶段发展，下文主要介绍当前比较常见的CFS公平调度处理的介绍

数据结构runqueue

runqueue在linux2.6调度程序中最重要的数据结构，系统中每个CPU都有自己的runqueue。

CFS进程公平调度

传统的进程取代机制是当一个进程用完时间片，它应该被还没用完时间片的优先级进程取代，并划分为活动进程和过期进程的机制，后来，Linux改用基于比例的划分模型，而不是基于绝对时间片的方案。

CFS调用使用了完全公平的方法来实现不公平，简单地说就是：目前有多少个进程，用总的CPU资源除以进程个数就知道每个进程需要占用多久的时间片了。如果需要定义更高优先级进程，可以让它占用多份时间；这种叫完全公平的调度算法是整个系统不公平的解决的基础。

进程饥饿指等待时间的进程推进和响应带来明显影响行为

Linx支持可插入的调度模块，用于实现完全调度和POSIX软实时调度策略，调度器会判断何时再进程间切换。

CFS引入的背景：

• 复杂的经验公式。

• 交互进程会长久霸占活跃数组，使得过期数组里的进程产生饥饿。

• 过期数组里如有高优先级进程，则饥饿现象更恶劣。

• O(1)的优势是挑选下一个的过程效率很高，但损失了公平性。

Liunx公平调度器的一个特战是：它不需要时间片的概念，至少不需要传统的时间片；Linux的CFS调度器并没有直接分配时间片到进程，它是将处理器的 使用比 （权重）划分给了进程（进一步受nice值影响）；这样通过所能分配的计算能力，向系统中的各个进程提供最大的公平性。

CFS主要针对普通进程的调度类型（SCHED_NORMAL）,它没有将任务维护在传统的循环双向链表中，它抛弃了active/expired数组，它采用把所有的进程都按时间在一个红黑树中排序，所谓时间即等待时间；

CFS完全公平调度算法依赖虚拟时钟（虚拟运行时）用以量度等待进程在完全公平系统中所能得到的CPU时间，当所有的进程随着时间调整自己的虚拟运行时，就能做到公平。CFS确保了进程调度中能有恒定的公平性，而将切换频率置于不断变化中。

当然CFS也不是完美的调度公平，原因是：处理器时间无法突破“最小粒度”，所谓“虽小粒度”（默认1ms）指即使进程数接近无穷，所获得的处理时间片底线。不过一般情况下。操作系统只有几百个可运行进程，所有CFS基本做到了“相对”完全公平的调度处理