进程与线程

一、进程

1、基本概念

计算机上所有可运行的软件，通常也包括操作系统，被组织成若干顺序进程（sequential process），简称进程（process）。 一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。从概念上说，每个进程拥有它自己的虚拟 CPU。当然，实际上真正的 CPU 在各进程之间来回切换。但为了理解这种系统，考虑在（伪）并行情况下运行的进程集，要比试图跟踪 CPU 如何在程序间来回切换简单得多。

在上图 (a) 中可以看到，在一台多道程序计算机的内存中有 4 道程序。
在上图 (b) 中，这 4 道程序被抽象为 4 个各自拥有自已控制流程（即每个程序自己的逻辑程序计数器）的进程，并且每个程序都独立地运行。当然，实际上只有一个物理程序计数器，所以在每个程序运行时，它的逻辑程序计数器被装人实际的程序计数器中。当该程序执行结束（或暂停执行）时，物理程序计数器被保存在内存中该进程的逻辑程序计数器中。
在上图 (c) 中可以看到，在观察足够长的一段时间后，所有的进程都运行了，但在任何一个给定的瞬间仅有一个进程真正在运行。即在单核 CPU 中进程是并发执行的（注意并发与并行的区别）。

为了使参与并发执行的程序（含数据）能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块（Process Control Block, PCB）。操作系统利用 PCB 来描述进程的基本情况和运行情况，进而控制和管理进程。相应地，由程序段、相关数据段和 PCB 三部分构成了进程映像（进程实体）。所谓创建进程，实质上是创建进程映像中的 PCB；而撤销进程，实质上是撤销进程的 PCB。要注意，进程映像是静态的，而进程是动态的。

从不同的角度，进程可以有不同的定义，下面列出一些典型的定义：

进程是程序的一次执行过程。
进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

在介绍了进程映像的相关概念后，可对进程做如下定义：进程是进程映像的运行过程，是系统进行资源分配和调度的一个独立单位。

2、进程的状态

进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化。通常进程有以下5种状态，前3种是进程的基本状态。

就绪（Ready）状态：进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。
运行（Running）状态：进程正在处理机上运行。在单处理机环境下，每个时刻最多只有一个进程处于运行状态。
阻塞（Blocked）状态：进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不能运行。

就绪、运行和阻塞状态的转换关系如下：

创建状态：进程正在被创建，尚未转到就绪态。
结束状态：进程正从系统中消失，可能是进程正常结束或其他原因中断退出运行。

在加入创建和终止状态的转换图如下：

3、进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。在操作系统中，一般把进程控制用的程序称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位。

（1）进程的创建

引起进程创建的事件：

用户登录。在分时系统中，用户在终端键入登录命令后，若登录成功，系统将为该用户建立一个进程，并把它插入就绪队列中。
作业调度。在多道批处理系统中，当作业调度程序按一定的算法调度到某个(些)作业时，便将它(们)装入内存，为它(们)创建进程，并把它(们)插入就绪队列中。
提供服务。当运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务，例如，用户程序要求进行文件打印，操作系统将为它创建一个打印进程，这样不仅可使打印进程与该用户进程并发执行，而且还便于计算为完成打印任务所花费的时间。
应用请求。在上述三种情况下，都是由系统内核为用户创建一个新进程；而这类事件则是由用户进程自己创建新进程，以便使新进程以同创建者进程并发运行的方式完成特定任务。

进程的创建步骤（创建原语）：

申请空白PCB，为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB。
为新进程分配其运行所需的资源，包括各种物理和逻辑资源，如内存、文件、I/O 设备和 CPU 时间等。这些资源或从操作系统或仅从其父进程获得。新进程对这些资源的需求详情一般也要提前告知操作系统或其父进程。注意：若资源不足（如内存空间），则并不是创建失败，而是处于阻塞态，等待内存资源。
初始化进程控制块。PCB 的初始化包括：初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中；初始化处理机状态信息，使程序计数器指向程序的入口地址，使栈指针指向栈项；初始化处理机控制信息，将进程的状态设置为就绪状态或静止就绪状态，对于优先级，通常是将它设置为最低优先级，除非用户以显式方式提出高优先级要求。
如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

（2）进程的终止

引起进程终止的事件：

正常结束。表示进程的任务已经完成，准备退出运行。在任何系统中，都应有一个用于表示进程已经运行完成的指示。
异常结束。是指进程在运行时发生了某种异常事件，使程序无法继续运行。常见的异常事件有：越界错、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障等。
外界干预。是指进程应外界的请求而终止运行。这些干预有：操作员或操作系统干预、父进程请求和父进程终止。

进程的终止步骤（撤销原语）：

根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程。
将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统。
将被终止进程(PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。

（3）阻塞与唤醒

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作可做等。由系统自动执行阻塞原语（Block），使自己由运动态变为阻塞态。可见，进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU），才可能将其转为阻塞态。阻塞原语的执行过程如下：

找到将要被阻塞进程的标识号对应的PCB。
若该进程为运行状态，则保护其现场。将其状态转为阻塞态，停止运行。
把该PCB插入相应事件的等待队列，将处理机资源调度给其它就绪进程。

当被阻塞进程所期待的事件出现时，如它所启动的I/O操作已完成或其所期待的数据已到达，由有关进程（如：释放该I/O设备的进程，或提供数据的进程）调用唤醒原语（Wakeup），将等待该事件的进程唤醒。唤醒原语的执行过程如下：

在该事件的等待队列中找到相应进程的PCB。
将其从等待队列中移出，并置其状态为就绪状态。
把该PCB插入就绪队列，等待调度程序调用。

需要注意的是，Block 原语和 Wakeup 原语是一对作用刚好相反的原语，必须成对使用。Block 原语是由被阻塞进程自我调用实现的，而 Wakeup 原语则是由一个与被唤醒进程合作或被其它相关的进程调用实现的。

（4）挂起与激活

进程的挂起（suspend）

当系统中出现了引起进程挂起的事件时，OS 将利用挂起原语 suspend 将指定进程或处于阻塞状态的进程挂起。 suspend 的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞；为了方便用户或父进程考查该进程的运行情况，而把该进程的 PCB 复制到某指定的内存区域；最后，若被挂起的进程正在执行，则转向调度程序重新调度。

进程的激活（active）

当系统中发生激活进程的事件时，OS 将利用激活原语 active，将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动.就绪;若为静止阻塞，便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有静止就绪进程被激活而插入就绪队列时，便应检查是否要进行重新调度，即由调度程序将被激活的进程与当前进程两者的优先级进行比较，如果被激活进程的优先级低，就不必重新调度;否则，立即剥夺当前进程的运行，把处理机分配给刚刚被激活的进程。

4、进程的层次结构

在操作系统中，允许一个进程创建另一个进程。此时创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获取的资源归还给父进程。此外，在撤销父进程时，必须同时撤销其所有的子进程。子进程自身可以创建更多的进程，组成一个进程的层次结构。

在 UNIX 中，进程和它的所有子进程以及后裔共同组成一个进程组。当用户从键盘发出一个信号时，该信号被送给当前与键盘相关的进程组中的所有成员（它们通常是在当前窗口创建的所有活动进程）。每个进程可以分别捕获该信号、忽略该信号或采取默认的动作，即被该信号杀死。

这里有另一个例子，可以用来说明进程层次的作用，考虑 UNIX 在启动时如何初始化自己。一个称为 init 的特殊进程出现在启动映像中。当它开始运行时，读入一个说明终端数量的文件。接着，为每个终端创建一一个新进程。这些进程等待用户登录。如果有一个用户登录成功，该登录进程就执行一个 shell 准备接收命令。所接收的这些命令会启动更多的进程，以此类推。这样，在整个系统中，所有的进程都属于以 init 为根的一棵树。

相反，Windows 中没有进程层次的概念，所有的进程都是地位相同的。唯一类似于进程层次的暗示是在创建进程的时候，父进程得到一个特别的令牌（称为句柄），该句柄可以用来控制子进程。但是，它有权把这个令牌传送给某个其他进程，这样就不存在进程层次了。在 UNIX 中，进程就不能剥夺其子继承的“继承权”。

5、进程的实现

为了实现进程模型，操作系统维护着一张表格（一个结构数组），即进程表（process table）。每个进程占用一个进程表项（即进程控制块，PCB）该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断过样。

上图展示了在一个典型系统中的关键字段。第一列中的字段与进程管理有关。其他两列分别与存储管理和文件管理有关。应该注意到进程表中的字段是与系统密切相关的，不过该图给出了所需要信息的大致介绍。

二、线程

1、为什么要使用线程

如果说，在 OS 中引入进程的目的是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量，那么，在操作系统中再引入线程（thread），则是为了减少程序在并发执行时所付出的时空开销，使 OS 具有更好的并发性。

2、经典的线程模型

线程最直接的理解就是轻量级进程（lightweight process），它是一个基本的CPU执行单元，也是程序执行流的最小单元。在线程中有一个程序计数器，用来记录接着要执行哪一条指令。线程拥有寄存器，用来保存线程当前的工作变量。线程还拥有一个堆栈，用来记录执行历史，其中每一帧保存了一个已调用的但是还没有从中返回的过程。尽管线程必须在某个进程中执行，但是线程和它的进程是不同的概念，并且可以分别处理。进程用于把资源集中到一起，而线程则是在CPU上被调度执行的实体。

线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。线程也有就绪、阻塞和运行三种基本状态。

例如，在上图(a)中，可以看到三个传统的进程。每个进程有自己的地址空间和单个控制线程。相反，在上图(b)中，可以看到一个进程带有三个控制线程。尽管在两种情形中都有三个线程，但是在上图(a)中，每一个线程都在不同的地址空间中运行，而在上图(b)中，这三个线程全部在相同的地址空间中运行。

3、线程的实现

在介绍线程的实现之前，我们先来简单介绍一下 POSIX 线程。为了实现可移植的线程程序，IEEE 在 IEEE 标准 1003.1c 中定义了线程的标准。它定义的线程包叫作pthread。大部分 UNIX 系统都支持该标准。这个标准定义了超过 60 个函数调用。下面将通过一张表格来介绍一些主要的函数，以说明它是如何工作的。

线程调用	描述
`pthread_create`	创建一个新线程
`pthread_exit`	结束调用的线程
`pthread_join`	等待一个特定的线程退出
`pthread_yield`	释放CPU来运行另外一个线程
`pthread_attr_init`	创建并初始化一个线程的属性结构
`pthread_attr_destroy`	删除一个线程的属性结构

所有pthread线程都有某些特性。每一个都含有一个标识符、一组寄存器（包括程序计数器）和一组存储在结构中的属性。这些属性包括堆栈大小、调度参数以及其他线程需要的项目。

线程的实现可以分为两类：用户级线程（User-Level Thread, ULT）和内核级线程（Kernel-Level Thread, KLT）。这两种方法各有利弊，下面我们将分别详细介绍这两种方法。

（1）用户级线程

在用户级线程中，有关线程管理（线程的创建、撤销和切换等）的所有工作都由应用程序完成，内核意识不到线程的存在。应用程序可以通过使用线程库设计多线程程序。下面将举一个使用pthread线程库编写的一个小程序的案例。

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define NUMBER_OF_THREADS 10

void *print_hello_world(void *tid)
{
    // 本函数输出线程的标识符，然后退出。
    print("Hello World. Greetings from thread %d\n", tid);
    pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
    // 主程序创建10个线程，然后退出。
    pthread_t threads[NUMBER_OF_THREADS];
    int status, i;

    for(i = 0; i < NUMBER_OF_THREADS; i++) {
        printf("Main here. Creating thread %d\n", i);
        status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);

        if (status != 0) {
            printf("Oops. pthread_create returned error code %d\n", status);
        }
        exit(-1);
    }
    exit(NULL);
}

所有的这类实现都有同样的通用结构，如下图所示。线程在一个运行时系统的上层运行，该运行时系统是一个管理线程的过程的集合。

在用户空间管理线程时，每个进程需要有其专用的线程表（thread table），用来跟踪该进程中的线程。这些表和内核中的进程表类似，不过它仅仅记录各个线程的属性，如每个线程的程序计数器、堆栈指针、寄存器和状态等。该线程表由运行时系统管理。当一个线程转换到就绪状态或阻塞状态时，在该线程表中存放重新启动该线程所需的信息，与内核在进程表中存放进程的信息完全一样。

（2）内核级线程

在内核级线程中，线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口。内核为进程及其内部的每个线程维护上下文信息，调度也在内核基于线程架构的基础上完成。下图说明了内核级线程的实现方式。

当使用内核级线程时就不再需要运行时系统了。另外，每个进程中也没有线程表。相反，在内核中有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它进行一个系统调用，这个系统调用通过对线程表的更新完成线程创建或撤销工作。

内核的线程表保存了每个线程的寄存器、状态和其他信息。这些信息和在用户空间中（在运行时系统中）的线程是一样的，但是现在保存在内核中。这些信息是传统内核所维护的每个单线程进程信息（即进程状态）的子集。另外，内核还维护了传统的进程表，以便跟踪进程的状态。

（3）混合实现

有些系统使用混合方式进行实现，简单来说就是使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来，如下图所示。

如果采用这种方法，编程人员可以决定有多少个内核级线程和多少个用户级线程彼此多路复用。这一模型带来最大的灵活度。采用这种方法，内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。如同在没有多线程能力操作系统中某个进程中的用户级线程一样，可以创建、撤销和调度这些用户级线程。在这种模型中，每个内核级线程有一个可以轮流使用的用户级线程集合。

4、多线程模型

有些系统同时支持用户线程和内核线程，由此产生了不同的多线程模型，即实现用户级线程和内核级线程的连接方式。

（1）多对一模型

将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见（即透明）。

优点：线程管理是在用户空间进行的，因而效率比较高。

缺点：一个线程在使用内核服务时被阻塞，整个进程都会被阻塞；多个线程不能并行地运行在多处理机上。

（2）一对一模型

将每个用户级线程映射到一个内核级线程。

优点：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。

缺点：每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建的线程开销比较大，会影响到应用程序的性能。

（3）多对多模型

将 n 个用户级线程映射到 m 个内核级线程上，要求 $m \le n$。

特点：多对多模型是多对一模型和一对一模型的折中，既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有多对一模型和一对一模型各自的优点，可谓集两者之所长。