进程与线程 ​

进程 ​

进程模型 ​

在进程模型中，计算机上所有可运行的软件，通常也包括操作系统，被组织成若干顺序进程，简称进程。一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。

由于 CPU 在各进程之间来回快速切换，所以每个进程执行其运算的速度是不确定的。而且当同一进程再次运行时，其运算速度通常也不可再现。所以，在对进程编程时决不能对时序做任何确定的假设。

进程的创建 ​

有 4 种主要事件导致进程的创建：

• 系统初始化

  启动操作系统时，通常会创建若干个进程。其中有些是前台进程，也就是同用户（人类）交互并且替他们完成工作的那些进程。其他的是后台进程，这些进程与特定的用户没有关系，相反，却具有某些专门的功能。停留在后台处理诸如电子邮件、Web 页面、新闻、打印之类活动的进程称为守护进程

• 执行了正在运行的进程所调用的进程创建系统调用

  一个正在运行的进程经常发出系统调用，以便创建一个或多个新进程协助其工作。在所要从事的工作可以容易地划分成若干相关的但没有相互作用的进程时，创建新的进程就特别有效果。

• 用户请求创建一个新进程

  在交互式系统中，键入一个命令或者点（双）击一个图标就可以启动一个程序。这两个动作中的任何一个都会开始一个新的进程，并在其中运行所选择的程序。

• 一个批处理作业的初始化

  最后一种创建进程的情形仅在大型机的批处理系统中应用。用户在这种系统中（可能是远程地）提交批处理作业。在操作系统认为有资源可运行另一个作业时，它创建一个新的进程，并运行其输入队列中的下一个作业。

在 UNIX 系统中，只有一个系统调用可以用来创建新进程：fork。在调用了 fork 后，这两个进程（父进程和子进程）拥有相同的存储映像、同样的环境字符串和同样的打开文件。

在 Windows 中，一个 Win32 函数调用 CreateProcess 既处理进程的创建，也负责把正确的程序装入新的进程。

在 UNIX 和 Windows 中，进程创建之后，父进程和子进程有各自不同的地址空间。如果其中某个进程在其地址空间中修改了一个字，这个修改对其他进程而言是不可见的。

进程的终止 ​

进程在创建之后，它开始运行，完成其工作。但永恒是不存在的，进程也一样。迟早这个新的进程会终止，通常由下列条件引起：

• 正常退出（自愿的）

  多数进程是由于完成了它们的工作而终止。在 UNIX 中该调用是 exit，而在 Windows 中，相关的调用是 ExitProcess 。

• 出错退出（自愿的）

  进程终止的第二个原因是进程发现了严重错误。

• 严重错误（非自愿）

  进程终止的第三个原因是由进程引起的错误，通常是由于程序中的错误所致。

• 被其他进程杀死（非自愿）

  第四种终止进程的原因是，某个进程执行一个系统调用通知操作系统杀死某个其他进程。在 UNIX 中，这个系统调用是 kill 。在 Win32 中对应的函数是 TerminateProcess 。

进程的层次结构 ​

某些系统中，当进程创建了另一个进程后，父进程和子进程就以某种形式继续保持关联。子进程自身可以创建更多的进程，组成一个进程的层次结构。

在 UNIX 中，进程和它的所有子女以及后裔共同组成一个进程组。

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

UNIX 启动时的初始化 ​

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

进程的状态 ​

进程存在三种状态：

• 运行态（该时刻进程实际占用 CPU）。
• 就绪态（可运行，但因为其他进程正在运行而暂时停止）。
• 阻塞态（除非某种外部事件发生，否则进程不能运行）。

状态间的转化关系为

进程的实现 ​

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

多道程序设计模型 ​

采用多道程序设计可以提高 CPU 的利用率。从概率的角度来看 CPU 的利用率。假设一个进程等待 I/O 操作的时间与其停留在内存中时间的比为 p。当内存中同时有 n 个进程时，则所有 n 个进程都在等待 I/O（此时 CPU 空转）的概率是 pⁿ 。CPU 的利用率由下面的公式给出：

CPU 利用率 = 1-pⁿ

线程 ​

线程的使用原因 ​

人们需要多线程的主要原因是，在许多应用中同时发生着多种活动。其中某些活动随着时间的推移会被阻塞。通过将这些应用程序分解成可以准并行运行的多个顺序线程，程序设计模型会变得更简单。

第二个关于需要多线程的理由是，由于线程比进程更轻量级，所以它们比进程更容易（即更快）创建，也更容易撤销。在许多系统中，创建一个线程较创建一个进程要快 10 ～ 100 倍。

需要多线程的第三个原因涉及性能方面的讨论。若多个线程都是 CPU 密集型的，那么并不能获得性能上的增强，但是如果存在着大量的计算和大量的 I/O 处理，拥有多个线程允许这些活动彼此重叠进行，从而会加快应用程序执行的速度。

线程模型 ​

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

线程给进程模型增加了一项内容，即在同一个进程环境中，允许彼此之间有较大独立性的多个线程执行。在同一个进程中并行运行多个线程，是对在同一台计算机上并行运行多个进程的模拟。

在用户空间中实现线程 ​

把整个线程包放在用户空间中，内核对线程包一无所知。从内核角度考虑，就是按正常的方式管理，即单线程进程。线程在一个运行时系统的顶部运行，这个运行时系统是一个管理线程的过程的集合。我们已经见过其中的四个过程：pthread_create ，pthread_exit ，pthread_join 和 pthread_yield 。不过，一般还会有更多的过程。

在用户空间管理线程时，每个进程需要有其专用的线程表，用来跟踪该进程中的线程。这些表和内核中的进程表类似。该线程表由运行时系统管理。当一个线程转换到就绪状态或阻塞状态时，在该线程表中存放重新启动该线程所需的信息，与内核在进程表中存放进程的信息完全一样。

优点

1. 用户级线程包可以在不支持线程的操作系统上实现。

2. 线程的切换可以在几条指令内完成。进行类似于这样的线程切换至少比陷入内核要快一个数量级（或许更多）。

3. 保存线程状态的过程和调度程序都只是本地过程，所以启动它们比进行内核调用效率更高。另一方面，不需要陷阱，不需要上下文切换，也不需要对内存高速缓存进行刷新，这就使得线程调度非常快捷。

4. 它允许每个进程有自己定制的调度算法。

缺点

1. 第一个问题是如何实现阻塞系统调用。假设在还没有任何击键之前，一个线程读取键盘。让该线程实际进行该系统调用是不可接受的，因为这会停止所有的线程。

2. 页面故障问题。如果有一个线程引起页面故障，内核由于甚至不知道有线程存在，通常会把整个进程阻塞直到磁盘 I/O 完成为止，尽管其他的线程是可以运行的。

3. 如果一个线程开始运行，那么在该进程中的其他线程就不能运行，除非第一个线程自动放弃 CPU 。

4. 通常在经常发生线程阻塞的应用中才希望使用多个线程。对于那些基本上是 CPU 密集型而且极少有阻塞的应用程序而言，没有很大的意义。

在内核中实现线程 ​

在内核中实现线程时，内核中有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它进行一个系统调用，这个系统调用通过对线程表的更新完成线程创建或撤销工作。内核的线程表保存了每个线程的寄存器、状态和其他信息。

所有能够阻塞线程的调用都以系统调用的形式实现，这与运行时系统过程相比，代价是相当可观的。当一个线程阻塞时，内核根据其选择，可以运行同一个进程中的另一个线程（若有一个就绪线程）或者运行另一个进程中的线程。而在用户级线程中，运行时系统始终运行自己进程中的线程，直到内核剥夺它的 CPU （或者没有可运行的线程存在了）为止。

混合实现 ​

人们已经研究了各种试图将用户级线程的优点和内核级线程的优点结合起来的方法。一种方法是使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来。

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

调度程序激活机制 ​

调度程序激活工作的目标是模拟内核线程的功能，但是为线程包提供通常在用户空间中才能实现的更好的性能和更大的灵活性。

使该机制工作的基本思路是，当内核了解到一个线程被阻塞之后，内核通知该进程的运行时系统，。内核通过在一个已知的起始地址启动运行时系统，从而发出了通知，这个机制称为上行调用。一旦如此激活，运行时系统就重新调度其线程。

调度程序激活机制的一个目标是作为上行调用的信赖基础，这是一种违反分层次系统内在结构的概念。

弹出式线程 ​

一个消息的到达导致系统创建一个处理该消息的线程，这种线程称为弹出式线程。

弹出式线程的关键好处是，由于这种线程相当新，没有历史这样，就有可能快速创建这类线程。对该新线程指定所要处理的消息。使用弹出式线程的结果是，消息到达与处理开始之间的时间非常短。

进程间通信 ​

进程间通信需要关注的三个问题：

1. 一个进程如何把信息传递给另一个。
2. 如何确保两个或更多的进程在关键活动中不会出现交叉。
3. 正确的顺序。

竞争条件 ​

两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件。

临界区 ​

在某些时候进程可能需要访问共享内存或共享文件，或执行另外一些会导致竞争的操作。我们把对共享内存进行访问的程序片段称作临界区域或临界区。如果我们能够适当地安排，使得两个进程不可能同时处于临界区中，就能够避免竞争条件。

对于保证使用共享数据的并发进程能够正确和高效地进行协作，一个好的解决方案，需要满足以下 4 个条件：

• 任何两个进程不能同时处于其临界区。
• 不应对 CPU 的速度和数量做任何假设。
• 临界区外运行的进程不得阻塞其他进程。
• 不得使进程无限期等待进入临界区。

忙等待的互斥 ​

（1） 屏蔽中断 ​

在单处理器系统中，最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也被屏蔽。CPU 只有发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断之后 CPU 将不会被切换到其他进程。于是，一旦某个进程屏蔽中断之后，它就可以检查和修改共享内存，而不必担心其他进程介入。

缺点：

1. 若一个进程屏蔽中断后不再打开中断，整个系统可能会因此终止。
2. 如果系统是多处理器（有两个或可能更多的处理器），则屏蔽中断仅仅对执行 disable 指令的那个 CPU 有效。其他 CPU 仍将继续运行，并可以访问共享内存。

但是对内核来说，当它在更新变量或列表的几条指令期间将中断屏蔽是很方便的。

所以结论是：屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。

（2） 锁变量 ​

设想有一个共享（锁）变量，其初始值为 0。当一个进程想进入其临界区时，它首先测试这把锁。如果该锁的值为 0，则该进程将其设置为 1 并进入临界区。若这把锁的值已经为 1，则该进程将等待直到其值变为 0。于是，0 就表示临界区内没有进程，1 表示已经有某个进程进入临界区。

缺点：锁变量的读写不是原子操作，可能被其他进程中断

假设一个进程读出锁变量的值并发现它为 0，而恰好在它将其值设置为 1 之前，另一个进程被调度运行，将该锁变量设置为 1。当第一个进程再次能运行时，它同样也将该锁设置为 1，则此时同时有两个进程进入临界区中。

（3）严格轮换法 ​

定义一个整型变量 turn ，初始值为 0，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。开始时，进程 0 检查 turn ，发现其值为 0，于是进入临界区。进程 1 也发现其值为 0，所以在一个等待循环中不停地测试 turn ，看其值何时变为 1。连续测试一个变量直到某个值出现为止，称为忙等待。

只有在有理由认为等待时间是非常短的情形下，才使用忙等待。用于忙等待的锁，称为自旋锁（spin lock）。

缺点：

1. 采用忙等待的方式，会浪费 CPU 时间。

2. 该方案要求两个进程严格地轮流进入它们的临界区，会造成一个临界区外运行的进程阻塞其他进程的情况。

（4）Peterson 解法 ​

在使用共享变量（即进入其临界区）之前，各个进程使用其进程号 0 或 1 作为参数来调用 enter_region 。该调用在需要时将使进程等待，直到能安全地进入临界区。在完成对共享变量的操作之后，进程将调用 leave_region ，表示操作已完成，若其他的进程希望进入临界区，则现在就可以进入。

（5）TSL 指令 ​

TSL 指令是硬件支持的一种方案，称为测试并加锁，它将一个内存字 lock 读到寄存器 RX 中，然后在该内存地址上存一个非零值。

读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行 TSL 指令的 CPU 将锁住内存总线，以禁止其他 CPU 在本指令结束之前访问内存。因此不会出现前面第二种方法锁变量的问题。

为了使用 TSL 指令，要使用一个共享变量 lock 来协调对共享内存的访问。当 lock 为 0 时，任何进程都可以使用 TSL 指令将其设置为 1，并读写共享内存。当操作结束时，进程用一条普通的 move 指令将 lock 的值重新设置为 0。

一个可替代 TSL 的指令是 XCHG ，它原子性地交换了两个位置的内容，它本质上与 TSL 的解决办法一样。所有的 Intel x86 CPU 在低层同步中使用 XCHG 指令。

缺点：

1. 采用忙等待的方式，会浪费 CPU 时间。

睡眠与唤醒 ​

Peterson 解法和 TSL 或 XCHG 解法都是正确的，但它们都有忙等待的缺点。这种方法不仅浪费了 CPU 时间，而且还可能引起预想不到的结果。

我们可以使用睡眠与唤醒的机制，使它们在无法进入临界区时将阻塞，而不是忙等待。

最简单的是 sleep 和 wakeup 。 sleep 是一个将引起调用进程阻塞的系统调用，即被挂起，直到另外一个进程将其唤醒。wakeup 调用有一个参数，即要被唤醒的进程。

缺点：

参考生产者-消费者问题，发给一个（尚）未睡眠进程的 wakeup 信号会出现丢失，从而出现生产者和消费者同时睡眠的情况。

一种快速的弥补方法是修改规则，加上一个唤醒等待位。当一个 wakeup 信号发送给一个清醒的进程信号时，将该位置 1。随后，当该进程要睡眠时，如果唤醒等待位为 1，则将该位清除，而该进程仍然保持清醒。但原则上讲，这并没有从根本上解决问题。

信号量 ​

信号量是一个整型变量用来累计唤醒次数，供以后使用。一个信号量的取值可以为 0（表示没有保存下来的唤醒操作）或者为正值（表示有一个或多个唤醒操作）。

对信号量一共有两种操作：down 和 up （分别为一般化后的 sleep 和 wakeup ）。

对一信号量执行 down 操作，则是检查其值是否大于 0。若该值大于 0，则将其值减 1（即用掉一个保存的唤醒信号）并继续；若该值为 0，则进程将睡眠，而且此时 down 操作并未结束。

对一信号量执行 up 操作，会对信号量的值增 1。如果一个或多个进程在该信号量上睡眠，信号量的值仍旧是 0，但在其上睡眠的进程会被唤醒一个。

检查数值、修改变量值以及可能发生的睡眠和唤醒操作均作为一个单一的、不可分割的原子操作完成。所谓原子操作，是指一组相关联的操作要么都不间断地执行，要么都不执行。

互斥量 ​

如果不需要信号量的计数能力，有时可以使用信号量的一个简化版本，称为互斥量（mutex）。互斥量仅仅适用于管理共享资源或一小段代码。由于互斥量在实现时既容易又有效，这使得互斥量在实现用户空间线程包时非常有用。

互斥量是一个可以处于两态之一的变量：解锁和加锁。当一个线程（或进程）需要访问临界区时，它调用 mutex_lock 。如果该互斥量当前是解锁的（即临界区可用），此调用成功，调用线程可以自由进入该临界区。另一方面，如果该互斥量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用 mutex_unlock 。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。

enter_region 和 mutex_lock 的代码很相似，但有一个关键的区别。

当 enter_region 进入临界区失败时，它始终重复测试锁（忙等待）。实际上，由于时钟超时的作用，会调度其他进程运行。这样迟早拥有锁的进程会进入运行并释放锁。

在（用户）线程中，情形有所不同，因为没有时钟停止运行时间过长的线程。结果是通过忙等待的方式来试图获得锁的线程将永远循环下去，决不会得到锁，因为这个运行的线程不会让其他线程运行从而释放锁。因此当 mutex_lock 取锁失败时，它调用 thread_yield 将 CPU 放弃给另一个线程。这样，就没有忙等待。在该线程下次运行时，它再一次对锁进行测试。

条件变量 ​

条件变量允许线程由于一些未达到的条件而阻塞。

与条件变量相关的最重要的两个操作是 pthread_cond_wait 和 pthread_cond_signal 。前者阻塞调用线程直到另一其他线程向它发信号（使用后一个调用）。

条件变量（不像信号量）不会存在内存中。如果将一个信号量传递给一个没有线程在等待的条件变量，那么这个信号就会丢失。

管程 ​

管程是一种高级同步原语，管程有一个很重要的特性，即任一时刻管程中只能有一个活跃进程，这一特性使管程能有效地完成互斥。

当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果

管程提供了一种实现互斥的简便途径，通过临界区互斥的自动化，管程比信号量更容易保证并行编程的正确性。

消息传递 ​

这种进程间通信的方法使用两条原语 send 和 receive ，它们像信号量而不像管程，是系统调用而不是语言成分。

前一个调用向一个给定的目标发送一条消息，后一个调用从一个给定的源（或者是任意源，如果接收者不介意的话）接收一条消息。如果没有消息可用，则接收者可能被阻塞，直到一条消息到达，或者，带着一个错误码立即返回。

屏障 ​

在有些应用中划分了若干阶段，并且规定，除非所有的进程都就绪准备着手下一个阶段，否则任何进程都不能进入下一个阶段。可以通过在每个阶段的结尾安置屏障来实现这种行为。当一个进程到达屏障时，它就被屏障阻拦，直到所有进程都到达该屏障为止。