《现代操作系统》-读书笔记-第二章-进程与线程

《现代操作系统》-读书笔记-第二章-进程与线程

进程

操作系统中最核心的概念是进程:这是对正在运行程序的一个抽象。

严格的说,在某一个瞬间,CPU只能运行一个进程。但在1秒钟内,它可以运行多个进程,这样就产生并行的错觉。

进程模型

一个进程就是一个正在执行程序的实例,包括程序计数器、寄存器和变量的当前值。真正的CPU在各个进程之间来回切换,称为多道程序设计

一个进程说某种类型的一个活动,它有程序、输入、输出以及状态。单个处理器可以被若干进程共享,它使用某种调度算法决定何时停止一个进程的工作,并转而为另一个进程提供服务。

值得注意的是,如果一个程序运行了两遍,则算作两个进程。

进程的创建

以下四种事件会导致进程的创建:

  • 系统初始化
  • 正在运行的程序执行了创建进程的系统调用
  • 用户请求创建一个新进程
  • 一个批处理作业的初始化

在UNIX系统中,只有一个系统调用可以用来创建新的进程:folk

在进程创建之后,父进程和子进程有个字不同的地址空间。如果其中某个进程在其地址空间中修改了一个字,这个修改对其他进程而言是不可见的。可写的内存对于进程而言,是不可以共享的。

进程的终止

进程的终止,通常由下列条件引起:

  • 正常退出(自愿的)

  • 出错退出(自愿的)

  • 严重错误(非自愿)

  • 被其他进程杀死(非自愿)

进程的层次结构

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

相反,在Windows中没有进程层次的概念,所有的进程都是地位相同的。

进程的状态

使用以下shell命令为例:

cat chapter1 chapter2 chapter3 | grep tree

第一个进程运行cat,将三个文件连接并输出。第二个进程运行grep,它从输入中选择所有包含单词“tree”的那些行。根据这两个进程的相对速度(这取决于这两个程序的相对复杂度和个各自分配到的CPU时间),可能发生这种情况:grep准备就绪可以运行,但输入还没有完成。于是必须阻塞grep,直到输入到来。

当一个进程在逻辑上不能继续运行时,它就会被阻塞。

进程的三种状态:

  1. 运行态(该时刻进程实际占用CPU)

  2. 就绪态(可运行,但因为其他进程正在运行而暂时停止)

  3. 阻塞态(除非某种外部事件发生,否则进程不能运行)

前两种状态类似,只是对于第二种状态暂时没有CPU分配给它。第三种即使CPU空闲也不能运行。

如上图所示,进程的三种状态之间有四种可能的转换关系。

在操作系统发现进程不能继续运行下去,发生转换1。

转换2、3由进程调度程序引起的。

当等待的一个外部事件发生时(如一些输入到达),则发生转换4。如果测试没有其他进程运行,则立即触发转换3,该进程便开始运行。否则该进程将处于就绪态,等待CPU空闲并且轮到它运行。

进程的实现

为了实现进程模型,操作系统维护着一张表格(一个数据结构数组),即进程表(process table)。每个进程占用一个进程表项。(有些作者称这些表项为进程控制块

在了解进程表后,就可以对在单个(或每一个)CPU上如何维护多个顺序进程的错觉做更多的阐述。与每一I/O类关联的是一个称为中断向量(interrupt vector)的位置(靠近内存底部的固定区域)。它包含中断服务程序入口地址。假设当一个磁盘中断发生时,用户进程3正在运行,则中断硬件将程序计数器、程序状态字、有时还有一个或多个寄存器压入堆栈,计算机随即跳转到中断向量的地址。这些是硬件完成的所有操作,然后软件,特别是中断服务例程就接管一切剩余工作。

一个进程在执行过程中可能被中断数千次,但关键是每次中断后,被中断的进程返回到与中断发生前完全相同的状态。

多道程序设计模型

采用多道程序设计可以提高CPU的利用率。

线程

线程的使用

为什么人们需要在一个进程中再有一类进程?

  • 在许多应用中同时发生着多种活动。其中某些活动随着时间的推移会被阻塞。通过将这些应用程序分解成可用准并行的多个顺序线程,程序设计模型会变得更简单。
  • 线程比进程更轻量级,所以它们比进程更容易(即更快)创建,也更容易撤销。在许多系统中,创建一个线程较创建一个进程要快10~100倍。
  • 性能方面,如果多个线程都是CPU密集型的,那么并不能获得性能上的增强,但是如果存在着大量的计算和大量的I/O处理,拥有多个线程允许这些活动彼此重叠进行,从而会加快应用程序执行的速度。
  • 在多CPU系统中,真正的并行有了实现的可能

经典的线程模型

线程概念试图实现的是,共享一组资源的多个线程的执行能力,以便这些线程可以为完成某一任务而共同工作。

线程的状态:运行、阻塞、就绪、终止

每个线程会调用不同的过程,从而有一个各自不同的执行历史,所以每个线程有其自己的堆栈

通常而言,线程是有益的,但是线程也在程序设计模式中引入了某种程度的复杂性。要使多线程的程序正确工作,就需要仔细思考和设计。

POSIX线程

为了实现可移植的线程程序,IEEE在IEEE标准1003.1c中定义了线程的标准。它定义的线程包叫做pthread。大部分UNIX系统都支持该标准。以下就是一些主要函数:

在用户空间中实现线程

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

第一种方法是把整个线程包放在用户空间中,内核对线程包一无所知。从内核角度考虑,就是按正常的方式管理,即单线程进程。优点是,用户级线程包可以在不支持线程的操作系统上实现。

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

不过,线程与进程有一个关键的差别。在线程完成运行时,例如,在它调用thread-yield时,pthread-yield代码可以把该线程的信息保存在线程表中,进而,它可以调用线程调度程序来选择另一个要运行的线程。保存该线程状态的过程和调度程序都只是本地过程,所以启动它们比进行内核调用效率更高。另一方面,不需要陷入内核,不需要上下文切换,也不需要对内存高速缓存进行刷新,这就使得线程调度非常快捷

用户级线程还有另一个优点。它允许每个进程有自己定制的调度算法。例如,在某些应用程序中,那些有垃圾收集线程的应用程序就不用担心线程会在不合适的时刻停止,这是一个长处。用户级线程还具有较好的可扩展性,这是因为在内核空间中内核线程需要一些固定表格空间和堆栈空间,如果内核线程的数量非常大就会出现问题。

存在问题是,如何实现阻塞系统调用以及缺页中断的问题。另外还有,如果一个线程开始运行,那么在该进程中的其他线程就不能运行,除非第一个线程自动放弃CPU。在一个单独的进程内部,没有时钟中断,所以不可能用轮转调度(轮流)的方式调度线程。

在内核中实现线程

内核中用来记录系统中所有线程的线程表。当某个线程希望创建一个线程或撤销一个已有线程时,它进行一个系统调用,这个系统调用通过对线程表的更新完成线程创建或撤销工作。

内核的线程表保存了每个线程的寄存器、状态和其他信息。这些信息和在用户空间(在运行时系统中)的线程是一样的,但是现在保存在内核中。

虽然使用内核线程可以解决很多问题,但也不回解决所有问题,例如创建新的进程,该如何处理?信号如何处理?

混合实现

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

在这种模型中,每个内核级线程有一个可以轮流使用的用户级线程集合。

调度程序激活机制

尽管内核级线程在一些关键点上优于用户级线程,但无可争议的是内核级线程很慢。因此研究人员一直在寻找在保持其优良特性的前提下改进其速度的方法。如:调度程序激活(scheduler activation)机制。

调度程序激活工作的目标是模拟内核线程的功能,但是为线程包提供通常在用户空间中才能实现的更好的性能和更大的灵活性。特别地,如果用户线程从事某种系统调用时是安全的,那就不应该进行专门的非阻塞调用或者进行提前检查。无论如何,如果线程阻塞在某个系统调用或页面故障上,只要在同一个进程中有任何就绪的线程,就应该有可能运行其他的线程。

由于避免了在用户空间和内核空间之间的不必要转换,从而提高了效率。例如,如果某个线程由于等待另一个线程的工作而阻塞,此时没有理由请求内核,这样就减少了内核-用户转换的开销。用户空间的运行时系统可以阻塞同步的线程而另外调度一个新线程。

当使用调度程序激活机制时,内核给每个进程安排一定数量的虚拟处理器,并且让(用户空间)运行时系统将线程分配到处理器上。这一机制也可以用在多处理器中,此时虚拟处理器可能成为真实的CPU,分配给一个进程的虚拟处理器的初始数量是一个,但是该进程可以申请更多的处理器并且在不用时退回。内核也可以取回已经分配出去的虚拟处理器,以便把它们分给需要更多处理器的进程。

使该机制工作的基本思路是,当内核了解到一个线程被阻塞之后(例如,由于执行了一个阻塞系统调用或者产生了一个页面故障),内核通知该进程的运行时系统,并且在堆栈中以参数形式传递有问题的线程编号和所发生事件的一个描述。内核通过在一个已知的起始地址启动运行时系统,从而发出了通知,这是对UNIX中信号的一种粗略模拟。这个机制称为上行调用(upcall)。

一旦如此激活,运行时系统就重新调度其线程,这个过程通常是这样的:把当前线程标记为阻塞并从就绪表中取出另一个线程,设置其寄存器,然后再启动之。稍后,当内核知道原来的线程又可运行时(例如,原先试图读取的管道中有了数据,或者已经从磁盘中读入了故障的页面)内核就又一次上行调用运行时系统,通知它这一事件。此时该运行时系统按照自己的判断,或者立即重启动被阻塞的线程,或者把它放入就绪表中稍后运行。

弹出式线程

在分布式系统中经常使用线程。一个有意义的例子是如何处理到来的消息。

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

优点是:创建速度快,消息达到与处理开始之间的时间非常短。

使单线程代码多线程化

许多已有的程序是为单线程进程编写的。把这些程序改成多线程需要更高的技巧。

需要考虑的问题有:

线程使用的全局变量

许多库的过程并不是可重入的。也就是说,对于任何给定的过程,当前面的调用尚没有结束之前,不能进行第二次调用。

堆栈管理

进程间通信

进程经常需要与其他进程通信。关于进程间通信(Inter Process Communication,IPC)的问题:

  • 一个进程如何把消息传递给另一个
  • 如何确保两个或更多的进程在关键活动中不会出现交叉
  • 如何保证顺序的正确

对于线程来说,第一个问题对于线程而言比较容易,因为它们共享一个地址空间(在不同地址空间需要通信的线程属于不同进程之间通信的情形)。另外两个问题和解决方法同样适用线程。

竞争条件

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

临界区

怎样避免竞争条件?实际上凡涉及共享内存、共享文件以及共享任何资源的情况都会引发与前面类,似的错误,要避免这种错误,关键是要找出某种途径来阻止多个进程同时读写共享的数据。换言之,我们需要的是互斥(mutual exclusion),即以某种手段确保当一个进程在使用一个共享变量或文件时,其他进程不能做同样的操作。前述问题的症结就在于,在进程A对共享变量的使用未结束之前进程B就使用它。为实现互斥而选择适当的原语是任何操作系统的主要设计内容之一。

避免竞争条件的问题也可以用一种抽象的方式进行描述。一个进程的一部分时间做内部计算或另外,一些不会引发竞争条件的操作。在某些时候进程可能需要访问共享内存或共享文件,或执行另外一些会导致竞争的操作。我们把对共享内存进行访问的程序片段称作临界区域(critical region)或临界区( criticalsection),如果我们能够适当地安排,使得两个进程不可能同时处于临界区中,就能够避免竞争条件。

尽管这样的要求避免了竞争条件,但它还不能保证使用共享数据的并发进程能够正确和高效地进行协作。对于一个好的解决方案,需要满足以下4个条件:

  1. 任何两个进程不能同时处于其临界区。

  2. 不应对CPU的速度和数量做任何假设。

  3. 临界区外运行的进程不得阻塞其他进程。

  4. 不得使进程无限期等待进入临界区。

忙等待的互斥

几种实现互斥的方案:

  • 屏蔽中断:最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断,并在就要离开之前再打开中断。但这个方案不好,因为把屏蔽中断的权利交给用户进程是不明智的。而且如果是多处理器,则屏蔽中断仅仅对执行disable指令的那个cpu有效。

  • 锁变量:设想有一个共享(锁)变量,其初始值为 0。当一个进程想进入其临界区时,它首先测试这把锁。如果该锁的值为 0,则该进程将其设置为 1 并进入临界区。若这把锁的值已经为 1,则该进程将等待直到其值变为 0。于是,0 就表示临界区内没有进程,1 表示已经有某个进程进入临界区。但是,假设一个进程读出锁变量的值并发现它为 0,而恰好在它将其值设置为 1 之前,另一个进程被调度运行,将该锁变量设置为 1。当第一个进程再次运行时,它同样也将该锁设置为 1,则此时同时有两个进程进人临界区中。

    可能读者会想,先读出锁变量,紧接着在改变其值之前再检查-遍它的值,这样便可以解决问题。但这实际上无济于事,如果第二个进程恰好在第一个进程完成第二次检查之后修改了锁变量的值,则同样还会发生竞争条件

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

    在一个进程比另一个慢了很多的情况下,轮流进入临界区并不是一个好办法。

  • Peterson解法:Peterson 的算法如图 2- 24 所示。该算法由两个用 ANSI C 编写的过程组成。ANSI C 要求为所定义和使用的所有函数提供函数原型。不过,为了节省篇幅,这里和后续的例子中我们都不会给出函数原型。

  • TSL指令:需要硬件支持的一种方案。在某些计算机中,特别是那些设计为多处理器的计算机,都有以下的一条指令:

    TSL RX,LOCK
    

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

    一个可替代TSL的指令是XCHG,它原子性的交换了两个位置的内容。

睡眠与唤醒

Peterson解法和TSL或XCHG解法都是正确的,但它们都有忙等待的缺点。这些解法本质上是这样的:

当一个进程想进入临界区时,先检查是否允许进入,如不允许,则该进程将原地等待,知道允许为止。

这种方法不仅浪费了 CPU 时间,而且还可能引起预想不到的结果。考虑一台计算机有两个进程,H 优先级较高,L 优先级较低。调度规则规定,只要 H 处于就绪态它就可以运行。在某一时刻,L 处于临界 区中,此时H变到就绪态,准备运行(例如,一条I/O操作结束)。现在H开始忙等待,但由于当H就绪时 L 不会被调度,也就无法离开临界区,所以 H 将永远忙等待下去。这种情况有时被称作优先级反转问题(priority inversion problem)。

现在来考察几条进程间通信原语,它们在无法进入临界区时将阻塞,而不是忙等待。最简单的是 sleep 和 wakeup。sleep 是一个将引起调用进程阻塞的系统调用,即被挂起,直到另外一个进程将其唤醒。wakeup 调用有一个参数,即要被唤醒的进程。另一种方法是让 sleep 和 wakeup 各有一个参数,即有一个用于匹配 sleep 和 wakeup 的内存地址。

生产者-消费者问题

作为使用这些原语的一个例子,我们考虑生产者-消费者(producer-consumer)问题,也称作有界缓冲区(bounded-buffer)问题。两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者,将信息放入缓冲区;另一个是消费者,从缓仲区中取出信息。(也可以把这个问题一般化为 m 个生产者和 n 个消费者问题,但是这里只讨论一个生产者和一个消费者的情况,这样可以简化解决方案。)

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

这个方法听起来很简单,但它包含与前边假脱机目录问题一样的竞争条件。为了跟踪缓冲区中的数据项数,需要一个变量 count。如果缓冲区最多存放 N 个数据项,则生产者代码将首先检查 count 是否达到 N,若是,则生产者睡眠;否则生产者向缓冲区中放人一个数据项并增量 count 的值。

消费者的代码与此类似:首先测试 count 是否为 0,若是,则睡眠;否则从中取走一个数据项并递减 count 的值。每个进程同时也检测另一个进程是否应被唤醒,若是则唤醒之。生产者和消费者的代码如下图所示。

含有严重竞争条件的生产者-消费者问题

现在回到竞争条件的问题。这里有可能会出现竞争条件,其原因是对 count 的访问未加限制。有可能出现以下情况:缓冲区为空,消费者刚刚读取 count 的值发现它为 0。此时调度程序决定暂停消费者并启动运行生产者。生产者向缓冲区中加入一一个数据项,count 加 1。现在 count 的值变成了 1。它推断认为由于 count 刚才为 0,所以消费者此时一一定在睡眠,于是生产者调用 wakeup 来唤醒消费者。

但是,消费者此时在逻辑上并未睡眠,所以 wakeup 信号丢失。当消费者下次运行时,它将测试先前读到的 count 值,发现它为 0,于是睡眠。生产者迟早会填满整个缓冲区,然后睡眠。这样一来,两个进程都将永远睡眠下去。

问题的实质在于发给一个(尚)未睡眠进程的 wakeup 信号丟失了。如果它没有丢失,则一切都很正常。一种快速的弥补方法是修改规则,加上一个唤醒等待位。当一个 wakeup 信号发送给一个清醒的进程信号时,将该位置 1。随后,当该进程要睡眠时,如果唤醒等待位为 1,则将该位清除,而该进程仍然保持清醒。唤醒等待位实际上就是 wakeup 信号的一个小仓库。

尽管在这个简单例子中用唤醒等待位的方法解决了问题,但是我们可以很容易就构造出一些例子,其中有三个或更多的进程,这时一个唤醒等待位就不够使用了。于是我们可以再打一个补丁,加入第二个唤醒等待位,甚至是 8 个、32 个等,但原则上讲,这并没有从根本上解决问题。

信号量

信号量是 E. W. Dijkstra 在 1965 年提出的一种方法,它使用一个整型变量来累计唤醒次数,供以后使用。在他的建议中引入了一个新的变量类型,称作信号量(semaphore)。一个信号量的取值可以为 0(表示没有保存下来的唤醒操作)或者为正值(表示有一个或多个唤醒操作)。

Dijkstra 建议设立两种操作:down 和 up(分别为一般化后的 sleep 和 wakeup)。对一信号量执行 down 操作,则是检查其值是否大于 0。若该值大于 0,则将其值减 1(即用掉一个保存的唤醒信号)并继续;若该值为 0,则进程将睡眠,而且此时 down 操作并未结束。检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始,则在该操作完成或阻塞之前,其他进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是绝对必要的。所谓原子操作,是指一组相关联的操作要么都不间断地执行,要么都不执行。原子操作在计算机科学的其他领域也是非常重要的。

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

用信号量解决丢失的 wakeup 问题,如下图所示。为确保信号量能正确工作,最重要的是要采用一种不可分割的方式来实现它。通常是将 up 和 down 作为系统调用实现,而且操作系统只需在执行以下操作时暂时屏蔽全部中断:测试信号量、更新信号量以及在需要时使某个进程睡眠。由于这些动作只需要儿条指令,所以屏蔽中断不会带来什么副作用。如果使用多个 CPU,则每个信号量应由一个锁变量进行保护。通过 TSL 或 XCHG 指令来确保同一时刻只有一个 CPU 在对信号量进行操作。

信号量的另一种用途是用于实现同步(synchronization)。信号量 full 和 empty 用来保证某种事件的顺序发生或不发生。在本例中,它们保证当缓冲区满的时候生产者停止运行,以及当缓冲区空的时候消费者停止运行。这种用法与互斥是不同的。

互斥量

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

互斥量是一个可以处于两态之一的变量:解锁和加锁。这样,只需要一个二进制位表示它,不过实际上,常常使用一个整型量,0 表示解锁,而其他所有的值则表示加锁。互斥量使用两个过程。当一个线程(或进程)需要访问临界区时,它调用 mutex_ lock。如果该互斥量当前是解锁的(即临界区可用),此调用成功,调用线程可以自由进人该临界区。

另一方面,如果该互斥量已经加锁,调用线程被阻塞,直到在临界区中的线程完成并调用 mutex_ unlock。如果多个线程被阻塞在该互斥量上,将随机选择一个线程并允许它获得锁。

由于互斥量非常简单,所以如果有可用的 TSL 或 XCHG 指令,就可以很容易地在用户空间中实现它们。用于用户级线程包的 mutex_ lock 和 mutex_ unlock 。XCHG 解法本质上是相同的。

  • 快速用户区互斥量 futex

随着并行的增加,有效的同步和锁机制对性能而言非常重要。如果等待时间短的话,自旋锁会很快但如果等待时间长,则会浪费 CPU 周期。如果有很多竟争,那么阻塞此进程,并仅当锁被释放的时候让内核解除阻塞会更加有效。然而,这却带来了相反的问题:它在竟争激烈的情况下效果不错,但如果一开始只有很小的竟争,那么不停地内核切换将花销很大。更糟的是,预测锁竞争的数量并不容易。

一个引人注意的致力于结合两者优点的解决方案称作“futex“,或者“快速用户空间互斥”。futex 是 Linux 的一个特性,它实现了基本的锁(很像互斥锁),但避免了陷入内核,除非它真的不得不这样做。因为来回切换到内核花销很大,所以这样做可观地改善了性能。

  • Pthreads 中的互斥量

Pthread 提供许多可以用来同步线程的函数。其基本机制是使用一个可以被锁定和解锁的互斥量来保护每个临界区。一个线程如果想要进入临界区,它首先尝试锁住相关的互斥量。如果互斥量没有加锁那么这个线程可以立即进入,并且该互斥量被自动锁定以防止其他线程进入。如果互斥量已经被加锁,则调用线程被阻塞,直到该互斥量被解锁。如果多个线程在等待同一个互斥量,当它被解锁时,这些等待的线程中只有一个被允许运行并将互斥量重新锁定。这些互斥锁不是强制性的,而是由程序员来保证线程正确地使用它们。

除互斥量之外,pthread 提供了另一种同步机制:条件变量。互斥量在允许或阻塞对临界区的访问上是很有用的,条件变量则允许线程由于一些未达到的条件而阻塞。绝大部分情况下这两种方法是一起使用的。现在让我们进一步地研究线程、互斥量、条件变量之间的关联。

管程

为了更易于编写正确的程序,Brinch Hansen (1973) 和 Hoare (1974) 提出了一种高级同步原语,称为管程(monitor)。他们两人提出的方案略有不同。一个管程是一个由过程、变量及数据结构等组成的一个集合,它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程,但它们不能在管程之外声明的过程中直接访问管程内的数据结构。图 2-33 展示了用一种抽象的、类 Pascal 语言描述的管程。这里不能使用 C 语言,因为管程是语言概念而 C 语言并不支持它。

管程有一个很重要的特性,即任一时刻管程中只能有一个活跃进程,这一特性使管程能有效地完成互斥。

进入管程时的互斥由编译器负责,但通常的做法是用一个互斥量或元信号量。因为是由编译器而非程序员来安排互斥,所以出错的可能性要小得多。在任一时刻,写管程的人无须关心编译器是如何实现互斥的。他只需知道将所有的临界区转换成管程过程即可,决不会有两个进程同时执行临界区中的代码。

尽管管程提供了一种实现互斥的简便途径,但这还不够,还需要一种办法使得进程在无法继续运行时被阻塞。在生产者-消费者问题中,很容易将针对缓冲区满和缓冲区空的测试放到管程过程中,但是生产者在发现缓冲区满的时候如何阻塞呢?

解决的方法是引入条件变量(condition variables)以及相关的两个操作:wait 和 signal。当一个管程过程发现它无法继续运行时(例如,生产者发现缓冲区满),它会在某个条件变量上(如 full)执行 wait 操作。该操作导致调用进程自身阻塞,并且还将另一个以前等在管程之外的进程调入管程。在前面介绍 pthread 时我们已经看到条件变量及其操作了。

消息传递

消息传递(messagepassing)。这种进程间通信的方法使用两条原语 send 和 receive,它们像信号量而不像管程,是系统调用而不是语言成分。因此,可以很容易地将它们加入到库例程中去。例如:

send (destination, &message);

receive (source, &message);

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

  1. 消息传递系统的设计要点

    消息传递系统面临着许多信号量和管程所未涉及的问题和设计难点,特别是位于网络中不同机器上的通信进程的情况。例如,消息有可能被网络丢失。为了防止消息丢失,发送方和接收方可以达成如下一致:一旦接收到信息,接收方马上回送一条特殊的确认(acknowledgement)消息。如果发送方在一段时间间隔内未收到确认,则重发消息。

    消息系统还需要解决进程命名的问题,在 send 和 receive 调用中所指定的进程必须是没有二:义性的。身份认证(authentication)也是一个问题,比如,客户端怎么知道它是在与一个真正的文件服务器通信,而不是与一个冒充者通信?

  2. 用消息传递解决生产者-消费者问题

    现在我们来考察如何用消息传递而不是共享内存来解决生产者-消费者问题。假设所有的消息都有同样的大小,并且在尚未接收到发出的消息时,由操作系统自动进行缓冲。在该解决方案中共使用 N 条消息,这就类似于一块共享内存缓冲区中的 N 个槽。消费者首先将 N 条空消息发送给生产者。当生产者向消费者传递一个数据项时,它取走一条空消息并送回一条填充了内容的消息。通过这种方式,系统中总的消息数保持不变,所以消息都可以存放在事先确定数量的内存中。

屏障

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

避免锁:读 – 复制 – 更新

读-复制-更新(Read-Copy-Update, RCU),将更新过程中的移除和再分配过程分离开来。

调度

调度简介

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

在个人计算机出现之后,整个情形向两个方面发展。首先,在多数时间内只有一个活动进程。

其次,同 CPU 是稀缺资源时的年代相比,现在计算机速度极快。

调度程序还要考虑 CPU 的利用率,因为进程切换的代价是比较高的。首先用户态必须切换到内核态;然后要保存当前进程的状态,包括在进程表中存储寄存器值以便以后重新装载。在许多系统中,内存映像(例如,页表内的内存访问位)也必须保存;接着,通过运行调度算法选定一个新进程;之后,应该将新进程的内存映像重新装入 MMU;最后新进程开始运行。除此之外,进程切换还要使整个内存高速缓存失效,强迫缓存从内存中动态重新装入两次(进入内核一次,离开内核一次)。总之,如果每秒钟切换进程的次数太多,会耗费大量 CPU 时间,所以有必要提醒注意。

  1. 进程行为

    几乎所有进程的(磁盘或网络)I/O请求和计算都是交替突发的

    前者称为计算密集型(compute -bound),后者称为I/O密集型(I/O-bound)。

  2. 何时调度

  • 创建一个新进程后;
  • 进程退出时,从就绪进程集中选择另外某个进程;
  • 当一个进程阻塞在 IO 和信号量上或由于其他原因阻塞时,必须选择另一个进程运行;
  • 在一个I/O中断发生时,必须做出调度决策;

    如果硬件时钟提供 50 Hz、60 Hz 或其他频率的周期性中断,可以在每个时钟中断或者在每 k 个时钟中断时做出调度决策。根据如何处理时钟中断,可以把调度算法分为两类。非抢占式调度算法挑选一个进程,然后让该进程运行直至被阻塞(阻塞在I/O上或等待另一个进程),或者直到该进程自动释放CPU。即使该进程运行了若千个小时,它也不会被强迫挂起。这样做的结果是,在时钟中断发生时不会进行调度。在处理完时钟中断后,如果没有更高优先级的进程等待到时,则被中断的进程会继续执行。

    相反,抢占式调度算法挑选一个进程,并且让该进程运行某个固定时段的最大值。如果在该时段结束时,该进程仍在运行,它就被挂起,而调度程序挑选另一个进程运行(如果存在一个就绪进程)。进行抢占式调度处理,需要在时间间隔的末端发生时钟中断,以便把 CPU 控制返回给调度程序。如果没有可用的时钟,那么非抢占式调度就是唯一的选择了。

  1. 调度算法分类

    毫无疑问,不同的环境需要不同的调度算法。之所以出现这种情形,是因为不同的应用领域(以及不同的操作系统)有不同的目标。换句话说,在不同的系统中,调度程序的优化是不同的。这里有必要划分出三种环境:

  • 批处理
  • 交互式
  • 实时
  1. 调度算法目标

批处理系统中的调度

1. 先来先服务

在所有调度算法中,最简单的是非抢占式的先来先服务(first-come first-served)算法。使用该算法,进程按照它们请求 CPU 的顺序使用 CPU。基本上,有一个就绪进程的单一队列。

这个算法的主要优点是易于理解并且便于在程序中运用。

不过,先来先服务也有明显的缺点。假设有一个一次运行 1 秒钟的计算密集型进程和很少使用 CPU 但是每个都要进行1000次磁盘读操作才能完成的大量I/O密集型进程存在。计算密集进程运行1秒钟,接 着读一个磁盘块。所有的I/O进程开始运行并读磁盘。当该计算密集进程获得其磁盘块时,它运行下一个 1 秒钟, 紧跟随着的是所有I/O进程。

这样做的结果是,每个I/O进程在每秒钟内读到一个磁盘块,要花费1000秒钟才能完成操作。如果 有一个调度算法每10ms抢占计算密集型进程,那么I/O进程将在10秒钟内完成而不是1000秒钟,而且还不会对计算密集型进程产生多少延迟。

2. 最短作业优先

适用于运行时间可以预知的另一个非抢占式的批处理调度算法。

3. 最短剩余时间优先

最短作业优先的抢占式版本是最短剩余时间优先(shortest remaining time next)算法。使用这个算法,调度程序总是选择剩余运行时间最短的那个进程运行。再次提醒,有关的运行时间必须提前掌握。当一个新的作业到达时,其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间,当前进程就被挂起,而运行新的进程。这种方式可以使新的短作业获得良好的服务。

交互式系统中的调度

1. 轮转调度

一种最古老、最简单、最公平且使用最广的算法是轮转调度(round robin)。每个进程被分配一个时间段,称为时间片(quantum),即允许该进程在该时间段中运行。如果在时间片结束时该进程还在运行,则将剥夺 CPU 并分配给另一个进程。如果该进程在时间片结束前阻塞或结束,则 CPU 立即进行切换。时间片轮转调度很容易实现,调度程序所要做的就是维护一张可运行进程列表,如图 2-42 a 所示。当一个进程用完它的时间片后,就被移到队列的末尾,如图 2-42 b 所示。

时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间进行管理事务处理的一保存和装人寄存器值及内存映像、更新各种表格和列表、清除和重新调人内存高速缓存等。假如进程切换(process switch),有时称为上下文切换(context switch),需要 1 ms,包括切换内存映像、清除和重新调人高速缓存等。再假设时间片设为 4 ms。有了这些参数,则 CPU 在做完 4 ms 有用的工作之后,CPU 将花费(即浪费)lms 来进行进程切换。因此,CPU 时间的 20%浪费在管理开销上。很明显,管理时间太多了。

可以归结如下结论:时间片设得太短会导致过多的进程切换,降低了 CPU 效率;而设得太长又可能引起对短的交互请求的响应时间变长。将时间片设为 20 ~ 50 ms 通常是一个比较合理的折中。

2. 优先级调度

轮转调度做了一个隐含的假设,即所有的进程同等重要,而拥有和操作多用户计算机系统的人对此常有不同的看法。例如,在一所大学里,等级顺序可能是教务长首先,然后是教授、秘书、后勤人员,最后是学生。这种将外部因素考虑在内的需要就导致了优先级调度其基本思想很清楚:每个进程被赋予一个优先级,允许优先级最高的可运行进程先运行。

优先级可以是静态赋予或动态赋予。

为达到某种目的,优先级也可以由系统动态确定。

可以很方便地将一-组进程按优先级分成若千类,并且在各类之间采用优先级调度,而在各类进程的内部采用轮转调度。图 2-43 给出了一个有 4 类优先级的系统,其调度算法如下:只要存在优先级为第 4 类的可运行进程,就按照轮转法为每个进程运行一个时间片,此时不理会较低优先级的进程。若第 4 类进程为空,则按照轮转法运行第 3 类进程。若第 4 类和第 3 类均为空,则按轮转法运行第 2 类进程。如果不偶尔对优先级进行调整,则低优先级进程很可能会产生饥饿现象。

3. 多级队列

4. 最短进程优先

对于批处理系统而言,由于最短作业优先常常伴随着最短响应时间,所以如果能够把它用于交互进程,那将是非常好的。在某种程度上,的确可以做到这一点。交互进程通常遵循下列模式:等待命令、执行命令、等待命令、执行命令,如此不断反复。如果将每一条命令的执行看作是一个独立的“作业”,则我们可以通过首先运行最短的作业来使响应时间最短。这里唯一的问题是如何从当前可运行进程中找出最短的那一个进程。

一种办法是根据进程过去的行为进行推测,并执行估计运行时间最短的那一个。

有时把这种通过当前测量值和先前估计值进行加权平均而得到下一个估计值的技术称作老化(aging)。它适用于许多预测值必须基于先前值的情况。老化算法在a= 1/2时特别容易实现,只需将新值加到当前估计值上,然后除以 2(即右移一位)。

5. 保证调度

一种完全不同的调度算法是向用户作出明确的性能保证,然后去实现它。一种很实际并很容易实现的保证是:若用户工作时有n个用户登录,则用户将获得CPU处理能力的1/n。类似地,在一个有n个进程运行的单用户系统中,若所有的进程都等价,则每个进程将获得1/n的CPU时间。看上去足够公平了。

6. 彩票调度

给用户一个保证,然后兑现之,这是个好想法,不过很难实现。但是,有一个既可给出类似预测结果而又有非常简单的实现方法的算法,这个算法称为彩票调度(lottery scheduling; Waldspurger 和 Weihl, 1994)。

其基本思想是为进程提供各种系统资源(如 CPU 时间)的彩票。一旦需要做出一-项调度决策时,就随机抽出一张彩票,拥有该彩票的进程获得该资源。在应用到 CPU 调度时,系统可以掌握每秒钟 50 次的一种彩票,作为奖励每个获奖者可以得到 20 ms 的 CPU 时间。

7. 公平分享调度

在这种模式中,每个用户分配到 CPU 时间的一部分,而调度程序以一种强制的方式选择进程。这样,如果两个用户都得到获得 50% CPU 时间的保证,那么无论一个用户有多少进程存在,每个用户都会得到应有的 CPU 份额。

实时系统中的调度

实时系统是一种时间起着主导作用的系统。典型地,一种或多种外部物理设备发给计算机一个服务请求,而计算机必须在一个确定的时间范围内恰当地做出反应。例如,在 CD 播放器中的计算机获得从驱动器而来的位流,然后必须在非常短的时间间隔内将位流转换为音乐。如果计算时间过长,那么音乐就会听起来有异常。其他的实时系统例子还有,医院特别护理部门的病人监护装置、飞机中的自动驾驶系统以及自动化工厂中的机器人控制等。在所有这些例子中,正确的但是迟到的应答往往比没有还要糟糕。

实时系统通常可以分为硬实时(hard real time)和软实时(soft real time),前者的含义是必须满足绝对的截止时间,后者的含义是虽然不希望偶尔错失截止时间,但是可以容忍。

实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流。根据每个事件需要处理时间的长短,系统甚至有可能无法处理完所有的事件。

实时系统的调度算法可以是静态或动态的。前者在系统开始运行之前作出调度决策;后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时,静态调度才能工作,而动态调度算法不需要这些限制。

策略和机制

调度机制(scheduling mechanism)与调度策略(scheduling policy)分离这个一贯的原则(Levin 等人,1975)。也就是将调度算法以某种形式参数化,而参数可以由用户进程填写。再次考虑数据库的例子。假设内核使用优先级调度算法,并提供了一条可供进程设置(并改变)优先级的系统调用。这样,尽管父进程本身并不参与调度,但它可以控制如何调度子进程的细节。在这里,调度机制位于内核,而调度策略则由用户进程决定。策略与机制分离是一一种关键性思路。

线程调度

当若干进程都有多个线程时,就存在两个层次的并行:进程和线程。在这样的系统中调度处理有本质差别,这取决于所支持的是用户级线程还是内核级线程(或两者都支持)。

首先考虑用户级线程。由于内核并不知道有线程存在,所以内核还是和以前一样地操作,选取一个进程,假设为 A,并给予 A 以时间片控制。A 中的线程调度程序决定哪个线程运行,假设为 Al。由于多道线程并不存在时钟中断,所以这个线程可以按其意愿任意运行多长时间。如果该线程用完了进程的全部时间片,内核就会选择另一个进程运行。

现在考虑使用内核级线程的情形。内核选择一个特定的线程运行。它不用考虑该线程属于哪个进程,不过如果有必要的话,它可以这样做。对被选择的线程赋予一个时间片,而且如果超过了时间片,就会强制挂起该线程。

用户级线程和内核级线程之间的差别在于性能。用户级线程的线程切换需要少量的机器指令,而内核级线程需要完整的上下文切换,修改内存映像,使高速缓存失效,这导致了若干数量级的延迟。另一 方面,在使用内核级线程时,一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。

另一个重要因素是用户级线程可以使用专为应用程序定制的线程调度程序。

经典IPC问题

哲学家就餐问题

1965 年,Dijkstra 提出并解决了一个他称之为哲学家就餐的同步问题。从那时起,每个发明新的同步原语的人都希望通过解决哲学家就餐问题来展示其同步原语的精妙之处。这个问题可以简单地描述如下:五个哲学家围坐在一张圆桌周围,每个哲学家面前都有一盘通心粉。由于通心粉很滑,所以需要两把叉子才能夹住。相邻两个盘子之间放有一把叉子,餐桌如图 2-45 所示。

问题是:能为每一个哲学家写一段描述其行为的程序,且决不会死锁吗?

解答:使用一个二元信号量对调用 think 之后的五个语句进行保护。在开始拿又子之前,哲学家先对互斥量 mutex 执行 down 操作。在放回又子后,他再对 mutex 执行 p 操作。从理论上讲,这种解法是可行的。但从实际角度来看,这里有性能上的局限:在任何一时刻只能有一位哲学家进餐。而五把又子实际上可以允许两位哲学家同时进餐。这样既不会发生死锁又不会产生饥饿(starvation)。

图 2-47 中的解法不仅没有死锁,而且对于任意位哲学家的情况都能获得最大的并行度。算法中使用个数组 statei 眼踪毎一个哲学家是在进餐、思考还是饥饿状态(正在试图拿又子)。一个哲学家只有在两个邻居都没有进餐时オ允许进入到进餐状态。第冷哲学家的邻居则由宏 LEFT 和 RIGHT 定义,换言之若 i 为 2, 则 LEFT 为 1, RIGHT 为 3。

该程序使用了一个信号量数组,每个信号量对应一位哲学家,这样在所需的又子被占用时,想进餐的哲学家就被阻塞。注意,每个进程将过程 philosopher 作为主代码运行,而其他过程 take_ forks put_ forks 和 test 只是普通的过程,而非单独的进程。

读者 – 写着问题

哲学家就餐问题对于互斥访问有限资源的竞争问题(如I/O设备) 一类的建模过程十分有用。另一个著名的问题是读者一写者问题(Courtois 等人,1971),它为数据库访问建立了一个模型。例如,设想一个飞机订票系统,其中有许多竞争的进程试图读写其中的数据。多个进程同时读数据库是可以接受的,但如果一个进程正在更新(写)数据库,则所有的其他进程都不能访问该数据库,即使读操作也不行。

有关进程和线程的研究

,本章先从有关进程的研究开始。虽然这些问题最终都将得到解决,但总有一些问题会比其他问题的解决方案更成熟。多数研究工作不再继续围绕有数十年历史的问题,而是针对新的问题。

例如,进程问题就已经有了成熟的解决方案。几乎所有系统都把进程视为一个容器,用以管理相关资源,如地址空间、线程、打开的文件、权限保护等。不同的系统管理进程资源的基本想法大致相同,只是在工程处理上略有差别,相关领域也很少有新的研究。

线程是比进程更新的概念,但也同样经过了深人的思考。现在线程的相关研究仍然时常出现,例如,多处理器上的线程集群(Tam 等人,2007)、Linux 等现代操作系统对于海量线程在多核处理器上的可扩展性(Boyd-Wickizer, 2010)。

进程执行过程的记录和重放也是一个非常活跃的研究领域(Viennot 等人,2013)。重放技术可以帮助开发者追踪-些难以发现的程序漏洞,也有助于程序安全领域的专家对程序进行检查。

目前还有许多研究操作系统安全问题的工作。大量事实表明,为了抵御攻击者(偶尔也需要防护用户自身的误操作),用户需要更完善的保护措施。一种方法是详细地跟踪并且。谨慎地限制操作系统中的信息流(Giffin 等人,2012)。

调度问题(包括单处理器和多处理器)也是研究者感兴趣的课题,一些正在研究的主题包括移动设备上的低能耗调度(Yuan 和 Nahrstedt, 2006)、超线程级调度(Bulpin 和 Pratt, 2005) 和偏置意识调度(Koufaty, 2010)。智能手机上的计算量逐渐增加,而其电池容量又十分有限,一些研究者提出在可能的时候将进程迁移到云上某个更强大的服务器上执行(Gordon 等人,2012)。但实际系统的设计者很少会因为没有合适的线程调度算法而苦恼,所以这似乎是一个由研究者推动而不是由需求推动的研究类型。总而言之,进程、线程与调度已经不再是研究的热点,功耗管理、虚拟化、云计算和安全问题成为了新的热点主题。

小结

为了隐藏中断的影响,操作系统提供了一个并行执行串行进程的概念模型。进程可以动态地创建和终止,每个进程都有自己的地址空间。

对于某些应用而言,在一个进程中使用多个线程是有益的。这些线程被独立调度并且有独立的栈,但是在一个进程中的所有线程共享一个地址空间。线程可以在用户态实现,也可以在内核态实现。

进程之间通过进程间通信原语来交换信息,如信号量、管程和消息。这些原语用来确保不会有两个进程同时在临界区中,以避免出现混乱。一个进程可以处在运行、就绪或阻塞状态,当该进程或其他进程执行某个进程间通信原语时,可以改变其状态。线程间的通信也类似。

进程间通信原语可以用来解决诸如生产者-消费者问题、哲学家就餐问题、读者一写者问题和睡眠理发师问题等。但即便有了这些原语,也要仔细设计才能避免出错和死锁。

目前已经有大量成熟的调度算法。一些算法主要用于批处理系统中,如最短作业优先调度算法。其他算法在批处理系统和交互式系统中都很常见,如轮转调度、优先级调度、多级队列调度、有保证调度、彩票调度以及公平分享调度等。有些系统清晰地分离了调度策略和调度机制,使用户可以配置调度算法。

说点什么

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
提醒