进程与线程

进程

  • 在任何多道程序设计系统中，CPU由一个进程快速切换至另一个进程，使每个进程各运行几十或几百毫秒。严格地说，在某一个瞬间，CPU只能运行一个进程。但在一分钟内，它可能运行多个进程，这样就产生并行的错误。
  • 操作系统的设计者开发了用于描述并行的一种概念模型（顺序进程），使得并行更容易理解。

进程模型

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

进程的创建

  • 操作系统需要有一种方式来创建进程。
    • 4种主要事件会导致进程的创建：
      1. 系统初始化
        • 启动操作系统时，通常会创建若干个进程。
          • 前台进程：同用户（人类）交互并且替他们完成工作的那些进程
          • 后台进程：具有某些专门的功能。
            • 守护进程：停留在后台处理诸如电子邮件、Web页面、新闻、打印之类活动的进程
      2. 正在运行的程序执行了创建进程的系统调用
        • 一个正在运行的进程经常发出系统调用，以便创建一个或多个新进程协助其工作
      3. 用户请求创建一个新进程
        • 在交互式系统中，输入一个命令或者点（双）击一个图标就可以启动一个程序。
      4. 一个批处理作业的初始化
        • 在这种系统中提交批处理作业，操作系统认为有资源可运行另一个作业时，创建一个新的进程，并运行其输入队列中的下一个作业。
  • 在UNIX系统中，只有一个系统调用可以用来创建新进程：fork。这个系统调用会创建一个与调用进程相同的副本。在调用了fork后，这两个进程（父进程和子进程）拥有相同的内存映像、同样的环境字符串和同样的打开文件。
  • 进程创建之后，父进程和子进程有各自不同的地址空间。如果其中某个进程在其地址空间种修改了一个字，这个修改对其他进程而言是不可见的。
  • 在UNIX中，子进程的初始地址空间是父进程的一个副本，但是这里涉及两个不同的地址空间，不可写的内存区是共享的。某些UNIX的实现使程序正文在两者间共享，因为它不能被修改。或者，子进程共享父进程的所有内存，但这种情况下内存通过写时复制共享，这意味着一旦两者之一想要修改部分内存，则这块内存首先被明确地复制，以确保修改发生在私有内存区域。

进程的终止

  • 进程在创建之后，它开始运行，完成其工作。新的进程会终止，通常由下列条件引起：
    1. 正常退出（自愿的）
    2. 出错退出（自愿的）
    3. 严重错误（非自愿）
    4. 被其他进程杀死（非自愿）
  • 多数进程是由于完成了它们的工作而终止。当编译器完成了所给定程序的编译之后，编译器执行一个系统调用，通知操作系统它的工作已经完成。
  • 进程终止的第二个原因是进程发现了严重错误。
  • 进程终止的第三个原因是由进程引起的错误，通常是由于程序中的错误所致。
  • 第四种终止进程的原因是，某个进程执行了一个系统调用通知操作系统杀死某个其他进程。

进程的层次结构

  • 某些系统中，当进程创建了另一个进程后，父进程和子进程就以某种形式继续保持关联。子进程自身可以创建更多的进程，组成一个进程的层次结构。
  • 在UNIX中，进程和它的所有子进程以及后裔共同组成一个进程组。
  • 在Windows中，所有的进程都是地位相同的。唯一类似于进程层次的暗示是在创建进程的时候，父进程得到一个特别的令牌（称为句柄），该句柄可以用来控制子进程。

进程的状态

  • 尽管每个进程是一个独立的实体，有其自己的程序计数器和内部状态，但是，进程之间经常需要相互作用。
  • 当一个进程在逻辑上不能继续运行时，它就会被阻塞。分为两种情况：
    • 概念上能够运行的进行被迫停止，因为操作系统调用了另一个进程占用了CPU。
    • 由系统技术上的原因引起的（由于没有足够的CPU，所以不能使每个进程都有一台私有的处理器）
  • 进程的三种状态：
    • 运行态（该时刻进程实际占用CPU）
    • 就绪态（可运行，但因为其他进程正在运行而暂时停止）
    • 阻塞态（除非某种外部事件发生，否则进程不能运行）
  • 前两种状态在逻辑上是类似的。处于这两种状态的进程都可以运行，只是对于第二种状态暂时没有CPU分配给他。第三种状态与前两种状态不同，处于该状态的进程不能运行，即使CPU空闲也不行。
  • 进程的三种状态之间有四种可能的转换关系
    1. 运行->阻塞
    2. 运行->就绪
    3. 就绪->运行
    4. 阻塞->就绪

进程的实现

  • 操作系统维护着一张表格（一个结构数组），即进程表。每个进程占用一个进程表象。该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的西悉尼，从而保证该进程随后能再次启动，就像从未被中断过一样。
  • 与每一个I/O类关联的是一个称作中断向量的位置（靠近内存底部的固定区域）。它包含中断服务程序的入口地址。假设当一个磁盘中断发生时，用户进程3正在运行，则中断硬件将程序计数器、程序状态字、有时还有一个或多个寄存器压入堆栈，计算机随机跳转到中断向量所指示的地址，这些是硬件完成的所有操作，然后软件，特别是中断服务例程就接管一切剩余的工作。
  • 所有的中断都从保存寄存器开始，对于当前进程而言，通常是保存在进表项中。随后，会从堆栈中删除由中断硬件机制存入堆栈的那部分信息，并将堆栈指针指向一个由进程处理程序所使用的临时堆栈。一些诸如保存寄存器和设置堆指针等操作，无法用C语言这一类高级语言描述，所以这些操作通过一个短小的汇编语言例程来完成，通常该例程可以供所有的中断使用，因为无论中断是怎样引起的，有关保存寄存器的工作则是完全一样的。

多道程序设计模型

  • 从概率的角度来看CPU的利用率，假设一个进程等待I/O操作的事件与其停留在内存中时间的比为p。当内存中同时有n个进程时，则所有n个进程都在等待I/O（此时CPU空转）的概率为$p^n$。CPU的利用率由下面的公式给出：
    • $CPU利用率=1-p^n$

线程

  • 在传统操作系统中，每个进程有一个地址空间和一个控制线程。事实上，这几乎就是进程的定义。不过，经常存在在同一个地址空间中准并行运行多个控制线程的情形，这些线程就像（差不多）分离的进程（共享地址空间除外）。

线程的使用

  • 为何要有多线程

    • 第一个理由：

      • 有了进程模型的抽象，才不必考虑中断、定时器和上下文切换，而只需考场并行进程。类似的，只是在有了多线程概念之后，才加入了一种新的元素：并行实体拥有共享同一个地址空间和所有可用数据的能力。对于某些应用而言，这些能力是必需的，而这正是多进程模型（它们具有不同的地址空间）所无法表达的。

    • 第二个理由：

      • 线程比进程更轻量级，所以它们比进程更容易（即更快）创建，也更容易撤销。在许多系统中，创建一个线程较创建一个进程要快10~100倍。在有大量线程需要动态和快速修改时，具有这一特性是很有用的。

    • 第三个理由：

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

  • 三个例子

    • 第一个例子：

      • 交互程序。例如，电子表格是允许用户维护矩阵的一种程序，矩阵中的一些元素是用户提供的数据；另一些元素是通过所输入的数据运用可能比较复杂的公式而得出的计算结果。当用户改变一个元素时，许多其他元素就必须重新计算。通过一个后台线程进行重新计算的方式，交互式线程就能够在进行计算的时候，让用户从事更多的工作。类似地，第三个线程可以在磁盘上进行周期性地备份工作。

    • 第二个例子：

      • 把服务器编写为顺序线程的一个集合。在分派线程的程序中包含一个无限循环，把该循环用来获得工作请求并且把工作请求派给工作线程。每个工作线程的代码包含一个从分派线程接收地请求，并且检查Web高速缓存中是否存在所需页面的无限循环。如果存在，就将该页面返回给客户机，接着该工作线程阻塞，等待一个新的请求。如果没有，工作线程就从磁盘调入该页面，将该页面返回给客户机，然后该工作线程阻塞，等待一个新的请求。

      • 服务器会在表格中记录当前请求的状态，然后去处理下一个事件。下一个事件可能是一个新工作的请求，或是磁盘对先前操作地回答。如果是新工作的请求，就开始该工作。如果是磁盘的回答，就从表格中取出对应的信息，并处理该回答。对于非阻塞磁盘I/O而言，这种回答多数会以信号或中断的形式出现。

      • 在这一设计中，每次服务器从为某个请求工作的状态切换到另一个状态时，都必须显示地保存或重新装入相应的计算状态。事实上，以一种苦难的方式模拟了线程及其堆栈。这里，每个计算都有一个被保存的状态，存在一个会发生且使得相关状态发生改变的事件集合，把这类设计称为有限状态机。

        • 模型特性
          多线程并行性、阻塞系统调用
          单线程进程无并行性、阻塞系统调用
          有限状态机并行性，非阻塞系统调用、中断

    • 第三个例子：

      • 处理及大量数据的应用
      • 多线程提供了一种解决方案，有关的进程可以用一个输入线程，一个处理线程和一个输出线程构造。输入线程把数据读入到输入缓冲区中；处理线程从输入缓冲区中取出数据，处理数据，并把结果放到输入缓冲区中；输出线程把这些结果写到磁盘上。按照这种工作方式，输入、处理和输出可以全部同时进行。

经典的线程模型

  • 理解进程的一个角度：用某种方法把相关的资源集中在一起。进程有存放程序正文和数据以及其他资源的地址空间。这些资源中包括打开的文件、子进程、即将发生的定时器、信号处理程序、账号信息等。
  • 另一个概念是，进程拥有一个执行的线程，通常简称为线程。在线程中有一个程序计数器，用来记录接着执行哪一条指令。线程拥有寄存器，用来保存线程当前的工作变量。线程还拥有一个堆栈，用来记录执行理事，其中每一帧保存了一个已调用的但是还没有从中返回的过程。尽管线程必须在某个进程中执行，但是线程和它的进程是不同的概念，并且可以分别处理。进程用于把资源集中到一起，而线程则是在CPU上被调度执行的实体。
  • 线程给进程模型增量了一项内容，即在同一个进程环境中，允许彼此之间有较大独立性的多个线程执行。在同一个进程中并行多个线程，是对在同一台计算机上并行多个进程的模拟。在前一种情绪下，多个线程共享同一个地址空间和其他资源。而在后一种情形中，多个进程共享物理内存、磁盘、打印机和其他资源。由于线程具有进程的某些性质，所以有时被称为轻量级进程。多线程这个术语，也用来描述在用一个进程中允许多个线程的情形。
  • 进程中的不同线程不像不同进程之间那样存在很大的独立性。所有的线程都有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于各个线程都可以访问进程地址空间中的每一个内存地址，所以一个线程可以读、写或甚至清楚另一个线程的堆栈。线程之间是没有保护的，原因是
    1. 不可能
    2. 没有必要
  • 这与不同进程是有差别的，不同的进程会来自不同的用户，它们彼此之间可能有敌意。一个进程总是由某个用户所拥有，该用户创建多个线程应该是为了它们之间的合作而不是彼此间争斗。除了共享地址空间之外，所有线程还共享同一个打开文件集、子进程、定时器以及相关信息等。
  • 线程概念试图实现的是，共享一组资源的多个线程的执行能力，以便这些线程可以为完成某一任务而共同工作。

在用户空间中实现线程

  • 有两种主要的方法实现线程包：在用户空间中和在内核中。这两种方法互有利弊，不过混合实现方式也是可能的。

    • 是把整个线程包放在用户空间中，内核对线程包一无所知。从内核角度看，就是按正常的方式管理，即单线程进程。这种方法第一个也是最明显的优点是，用户级线程包可以在不支持线程的操作系统上实现。
    • 在用户空间管理线程时，每个进程需要有其专用的线程表，用来跟踪该进程中的线程。这些表和内核中的进程表类似，不给过它仅仅记录各个线程的属性，如每个线程的程序计数器、堆栈指针、寄存器和状态等。该线程表由运行时系统管理。当一个线程转换到就绪状态或组赛状态时，在该线程表中存放重新启动该线程所需的信息，与内核在进程表中存放进程的信息完全一致。

在内核中实现线程

  • 第二种方式：
    • 内核的线程表保存了每个线程的寄存器、状态和其他信息。这些信息和在用户空间中（在运行时系统中）的线程是一样的，但是现在保存在内核中。这些信息是传统内核所维护的每个单线程进程信息（即进程状态）的子集。另外，内核还维护了传统的进程表，以便跟踪进程的状态。
    • 由于在内核中创建或撤销进程的代价比较大，某些系统采取“环保”的处理方式，回收其线程。当某个线程被撤销时，就把它标志为不可运行的，但是其内核数据结构没有受到影响。稍后，在必须创建一个新线程时，就重新启动某个旧线程，从而节省了一些开销。在用户级线程中线程回收也是可能的，但是由于其线程管理的代价很小，所以没有必要进行这项工作。

混合实现

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

调度程序激活机制

  • 调度程序激活工作的目标是模拟内核线程的功能，但是为线程包提供通常在用户空间中才能实现的更好的性能和更大的灵活性。如果线程组赛在某个系统调用或页面故障上，只要在同一个进程中有任何就绪的进程，就应该有可能运行其他的进程。
  • 由于避免了在用户空间和内核空间之间的不必要转换，从而提高了效率。例如，如果某个线程由于等待另一个线程的工作而阻塞，此时没有理由请求内核，这样就减少了内核-用户转换的开销。用户空间的运行时系统可以阻塞同步的线程而另外调度一个新线程。
  • 当使用调度程序激活机制时，内核给每个进程安排一定数量的虚拟处理器，并且让（用户空间）运行时系统将线程分配到处理器上。这一机制也可以用在多处理器中，此时虚拟处理器可能成为真实的CPU。分配给一个进程的虚拟处理器的初始数量是一个，但是该进程可以申请更多的处理器并且在不用时退回。内核也可以取回已经分配出去的虚拟处理器，以便把它们分给需要更多处理器的进程。
  • 该机制工作的基本思路是：当内核了解到一个线程被阻塞之后，内核通知该进程的运行时系统，并且在堆栈中以参数形式传递有问题的线程编号和所发生事件的一个描述。内核通过在一个已知的起始地址启动运行时系统，从而发出了通知，这是对UNIX中信号的一种粗略模拟，这个机制称为上行调用。
  • 一旦如此激活，运行时系统就重新调度其线程，这个过程通常是这样的：把当前线程标记为阻塞并从就绪表中取出另一个线程，设置其寄存器，然后再启动之。稍后，当内核直到原来的线程又可运行时，内核就又一次上行调用运行时系统，通知它这一事件。此时该运行时系统按照自己的判断，或者立即重启被阻塞的线程，或者把它放入就绪表中稍后运行。

弹出式线程

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

使单线程代码多线程化

  • 一个线程的代码就像进程一样，通常包含多个过程，会有局部变量、全局变量和过程参数。局部变量和参数不会引起任何问题，但是有一个问题是，对线程而言是全局变量，并不是对整个程序也是全局的。有许多变量之所以是全局的，是因为线程中的许多过程都使用它们，但是其他线程在逻辑上和这些变量无关。
    • 一种解决方案是：为每个线程赋予其私有的全局变量。
    • 另一种解决方案是，为每个过程提供一个包装器，该包装器设置一个二进制位从而标志某个库处于使用中。在先前的调用还没有完成之前，任何试图使用该库的其他线程都会被阻塞。

进程间通信

  • 进程经常需要与其他进程通信。有三个问题：
    1. 一个进程如何把信息传递给另一个
    2. 确保两个或更多的进程在关键活动中不会出现交叉
    3. 正确的顺序有关，比如，如果进程A产生数据而进程B打印数据，那么B在打印之前必须等待，直到A已经产生一些数据。
  • 这三个问题中的两个问题对于线程来说是同样适用的。第一个问题（即传递信息）对线程而言比较容易，因为它们共享一个地址空间。但是另外两个问题同样适用于线程。同样的问题可用同样的方法解决。

竞争条件

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

临界区

  • 要避免竞争条件，通过找出某种途径来阻止多个进程同时读写共享的数据，换言之，需要的是互斥，即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。
  • 避免竞争条件的问题也可以用一种抽象的方式进行描述。一个进程的一部分时间做内部计算或另外一些不会引发竞争条件的操作。在某些时候进程可能需要访问共享内存或共享文件，或执行另外一些会导致竞争的操作。我们把对共享内存进行访问的程序片段称作临界区域或临界区。
  • 尽管这样的要求避免了竞争条件，但它还布恩那个保证使用共享数据的开发进程能够正确和高效地进行协作。对于一个好的解决方案，需要满足以下4个条件：
    1. 任何两个进程不能同时处于其临界区
    2. 不应对CPU地速度和数量做任何假设
    3. 临界区外运行的进程不得阻塞其他进程
    4. 不得使进程无限期等待进入临界区

忙等待的互斥

屏蔽中断

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

锁变量

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

严格轮换法

  • 整形变量turn，初始值为0，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。开始时，进程0检查turn，发现其值为0，于是进入临界区。进程1也发现其值为0，所以在一个等待循环中不停地测试turn，看其值何时变为1.连续测试一个变量直到某个值出现为止，称为忙等待。由于这种方式浪费CPU时间，所以通常应该避免。只有在有理由认为等待时间是非常短的情形下，才使用忙等待。用于忙等待的锁，称为自旋锁。

    #进程0
while(TRUE){
	while(turn!=0); /* 循环 */
	critical_region();
	turn=1;
	noncritical_region();
}

#进程1
while(TRUE){
	while(turn!=1); /* 循环 */
	critical_region();
	turn=0;
	noncritical_region();
}

Peterson解法

  • 一开始，没有任何进程处于临界区中，现在进程0调用enter_region。它通过设置其数组元素和将turn置为0来标识它希望进入临界区。由于进程1并不想进入临界区，所以enter_region很快便返回。如果进程1现在调用enter_region，进程1将在此处挂起直到interested[0]变成FALSE，该事件只有在进程0调用leave_region退出临界区才会发生。

    #define FALSE 0
#define TRUE 1
#define N 2 /*进程数量*/

int turn; /*现在轮到谁?*/
int interested[N]; /*所有初始值为0（FALSE）*/

void enter_region(int process)  /*进程是0或1*/
{
	int other;  /*另一进程号*/

	other = 1 - process;  /*另一个进程*/
	interedted[process] = TRUE; /*表示感兴趣*/
	turn = process; /*设置标志*/
	while(turn == process && interested[other] == TRUE);/*空语句*/
}

void leave_region(int process) /*进程：谁离开?*/
{
	interested[process] = FALSE; /*表示谁离开临界区*/
}

TSL指令

  • TSL RX,LOCK称为测试并加锁，它将一个内存字lock读到寄存器RX中，然后再该内存低智商存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存子。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存

    enter_region
  TSL REGISTER,LOCK |复制锁到寄存器并将锁设为1
  CMP REGISTER,#0 | 锁是零吗？
  JNE enter_region | 若不是零，说明锁已被设置，所以循环
  RET | 返回调用者，进入了临界区

leave_region:
  MOVE LOCK,#0 | 在锁中存入0
  RET | 返回调用者

睡眠与唤醒

  • Peterson解法和TSL或XCHG解法都是正确的，但它们都有忙等待的缺点。这些解法在本质上是这样的：当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。
  • 这种方法不仅浪费了CPU事件，而且还可能引起预想不到的结果。考虑一台计算机有两个进程，H优先级较高，L优先级较低。调度规则规定，只要H处于就绪态就可以运行。在某一时刻，L处于临界区中，此时H变到就绪态，准备运行。现在H开始忙等待，但由于当H就绪时L不会被调度，也就无法离开临界区，所以H将永远忙等待下去。这种情况有时被称作优先级反转问题。
  • 考察几条进程间通信愿语，它们在无法进入临界区时将阻塞，而不是忙等待。最简单的是sleep和weakup。sleep是一个将引起调用进程组赛的系统调用，即被挂起，直到另外一个进程将其唤醒。weakup调用有一个参数，即要被唤醒的进程。另一种方法是让sleep和weakup各有一个参数，即有一个用于匹配sleep和weakup的内存地址。

生产者-消费者问题

  • 生产者-消费者问题，也称作有界缓冲区问题。两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息。

  • 问题在于当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的情况。其解决办法是让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样的，当消费者试图从缓冲区中取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒。

    #define N 100 /*缓冲区中的槽数目*/
int count = 0; /*缓冲区中的数据项数目*/

void producer(void)
{
	int item;

	while(TRUE){  /*无限循环*/
		item produce_item();  /*产生下一新数据项*/
		if(count == N) sleep();  /*如果缓冲区满了，就进入休眠状态*/
		insert_item(item); /*将(新)数据项放入缓冲区中*/
		count = count+1; /*将缓冲区的数据项计数器增1*/
		if(count == 1) wakeup(consumer); /*缓冲区空吗？*/
	}
}

void consumer(void)
{
	int item;

	while(TRUE){  /*无限循环*/
		if(count == 0) sleep(); /*如果缓冲区空，则进入休眠状态*/
		item = remove_item(); /*从缓冲区中取出一个数据项*/
		count = count - 1;  /*将缓冲区的数据项计数器减1*/
		if(count == N - 1) wakeup(producer); /*缓冲区满吗?*/
		consume_item(item); /*打印数据项*/
	}
}
    • 这里有可能会出现竞争条件，其原因是对count的访问未加限制，有可能出现以下情况：缓冲区为空，消费者刚刚读取count的值发现它为0。此时调度程序决定暂停消费者并启动运行生产者。生产者向缓冲区中加入一个数据项，count加1。现在count的值变成了1.
    • 但是，消费者此时在逻辑上并未睡眠，所以weakup信号丢失。当消费者下次运行时，它将测试先前读到的count值，发现它为0，于是睡眠。生产者迟早会填满整个缓冲区，然后睡眠。这样一来，两个进程都将永远睡眠下去。
    • 问题的实质在于发给一个（尚）未睡眠进程的weakup信号丢失了。如果它没有丢失，则一切都很正常。一种快速的弥补方法是修改规则，加上一个唤醒等待位。当一个weakup信号发给一个清醒的进程信号时，将该位置1。随后，当该进程要睡眠时，如果唤醒等待位为1，则将该位清除，而该进程仍然保持清醒。唤醒等待位实际上就是wakeup信号的一个小仓库。

信号量

  • 使用一个整形变量来累计唤醒次数，供以后使用。在他的建议中引入了一个新的变量类型，称作信号量。一个信号量的取值可以为0或者为正值。
  • 设立两种操作：down和up
    • 对一信号量执行down操作，则是检查其值是否大于0.若该值大于0，则将其值减1并继续；若该值为0，则进程将睡眠，而且此时down操作并未结束。检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是绝对必要的。
    • up操作对信号量的值增1。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的down操作，则由系统选择其中的一个（如随机挑选）并允许该进程完成它的down操作。于是，对一个有进程在其上的睡眠的信号量执行一次up操作之后，该信号量的值仍旧是0，但在其上睡眠的进程缺少了一个。

用信号量解决生产者-消费者问题

  • 用信号量解决丢失的wakeup问题。为确保信号量能正确工作，最重要的是要采用一种不可分割的方式来实现它。通常是将up和down作为系统调用实现，而且操作系统只需在执行以下操作时暂时屏蔽全部中断：测试信号量、更新信号量以及在需要时使某个进程睡眠。由于这些动作只需要几条指令，所以屏蔽中断不会带来什么副作用。如果使用多个CPU，则每个信号量应由一个锁变量进行保护。通过TSL或XCHG指令来确保同一时刻只有一个CPU在对信号量进行操作。
  • 使用TSL或XCHG指令来防止几个CPU同时访问一个信号量，这与生产者或消费者使用忙等待来等待对方腾出或填充缓冲区是完全不同的。信号量操作仅需几个毫秒，而生产者或消费者则可能需要任意长的时间。
  • 该解决方案使用了三个信号量：一个称为full，用来记录充满的缓冲槽数目；一个称为empty，记录空的缓冲槽数目；一个称为mutex，用来确保生产者和消费者不会同时访问缓冲区。full的初值为0，empty的初值为缓冲区中槽的数据，mutex初值为1。供两个或多个进程使用的信号量，其初值为1，保证同时只有一个进程可以进入临界区，称作二元信号量。如果每个进程在进入临界区前都执行一个down操作，并在刚刚退出时候执行一个up操作，就能够实现互斥。
  • 信号量的另一种用途是用于实现同步。信号量full和empty用来保证某种事件的顺序发生或不发生。

互斥量

  • 如果不需要信号量的技术能力，有时可以使用信号量的一个简化版本，称为互斥量。
  • 互斥量是一个可以处于两态之一的变量：解锁和加锁。这样，只需要一个二进制位来表示它，不过实际上，常常使用一个整形量，0表示解锁，而其他所有的值则表示加锁。互斥量使用两个过程。当一个线程（或进程）需要访问临界区时，它调用mutex_lock。如果该互斥量当前是解锁的，此调用成功，调用线程可以自由进入该临界区。
  • 另一方面，如果过该互斥量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。

快速用户区互斥量futex

  • 一个futex包含两个部分：一个内核服务和一个用户库。内核服务提供一个等待队列，它允许多个进程在一个锁上等待。它们将不会运行，除非内核明确地对它们解除阻塞。

pthread中的互斥量

  • Pthread提供许多可以用来同步线程的函数。其基本机制是使用一个可以被锁定和解锁的互斥量来保护每个临界区。一个线程如果想要进入临界区，它首先尝试锁住相关的互斥量。如果互斥量没有加锁，那么这个线程可以立即加入，并且该互斥量被自动锁定以防止其他线程进入。
  • 提供了另一种同步机制：条件变量。互斥量在允许或阻塞对临界区的访问上是很有用的，条件变量则允许线程由于一些未达到的条件而阻塞。绝大部分情况下这两种方法是一起使用的。

管程

  • 管程有一个很重要的特性，即任一时刻管程中只能由一个活跃进程，这一特性使管程能有效地完成互斥。典型的处理方法是，当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程，则该调用进程可以进入。
  • 尽管管程提供了一种实现互斥的简便途径，但这还不够，还需要一种办法使得进程在无法继续运行时被阻塞。
  • 解决的方法是引入了条件变量以及相关的两个操作：wait和signal。当一个管程过程发现它无法继续运行时，它会在某个条件变量上执行wait操作。该操作导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程。

消息传递

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

屏障

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

避免锁：读-复制-更新

  • 确保每个读操作要么读取旧的数据版本，要么读取新的数据版本，但绝不能是新旧数据的一些奇怪组合。将更新过程中的移除和再分配过程分离来。

调度

  • 当计算机系统是躲到程序设计系统时，通常就会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法称为调度算法。

调度算法分类

  1. 批处理
  2. 交互式
  3. 实时

调度算法的目标

  • 所有系统
    • 公平——给每个进程公平的CPU份额
    • 策略强制执行——保证规定的策略被执行
    • 平衡——保持系统的所有部分都忙碌
  • 批处理系统
    • 吞吐量——每小时最大作业数
    • 周转时间——从提交到终止间的最小时间
    • CPU利用率——保持CPU始终忙碌
  • 交互式系统
    • 响应时间——快速响应请求
    • 均衡性——满足用户的期望
  • 实时系统
    • 满足截止时间——避免丢失数据
    • 可预测性——再多媒体系统中避免品质降低

批处理系统中的调度

  1. 先来先服务
  2. 最短作业优先
  3. 最短剩余时间优先

交互式系统中的调度

  1. 轮转调度
  2. 优先级调度
  3. 多级队列
  4. 最短进程优先
  5. 保证调度
  6. 彩票调度
  7. 公平分享调度

小结

  1. 为了隐藏中断的影响，操作系统提供了一个并行执行串行进程的概念模型。进程可以动态地创建和终止，每个进程都有自己的地址空间。
  2. 对于某些应用而言，在一个进程中使用多个线程是有益的。这些线程被独立调度并且有独立的栈，但是再一个进程中的所有线程共享一个地址空间。线程可以在用户态实现，也可以在内核态实现。
  3. 进程之间通过进程间通信原语来交换信息，如信号量、管程和消息。这些原语用来确保不会有两个进程同时在临界区中，以避免出现混乱。一个进程可以处在运行、就绪或阻塞状态，当该进程或其他进程执行某个进程间通信原语时，可以改变其状态。线程间的通信也类似。
  4. 进程间通信原语可以用来解决诸如生产者——消费者问题。但即使有了这些原语，也要仔细设计才能避免出错和死锁。
  5. 目前已经有大量成熟的调度算法。一些算法主要用于批处理系统中，如最短作业优先调度算法。其他算法在批处理系统和交互式系统中都很常见，如轮转调度、优先级调度、多级队列调度、有保证调度、彩票调度以及公平分享调度等。有些系统清晰地分离了调度策略和调度机制，使用户可以配置调度算法。