进程经常需要与其他进程通常,一种好的方式是不使用中断。进程间通信(Inter Process Communication IPC) 要解决三个问题:
- 一个进程如何把信息传递给另一个
- 确保两个或更多的进程在关键活动中不会出现交叉(两个进程同时竞争同一资源)
- 程序的正确运行顺序(B运行时A必须运行完成)
以上三个问题对于线程同样适用,其中传递信息对于线程来说相对较为容易,因为其共享地址空间。另外两个问题的解决方案同样适用于线程。
1. 竞争条件
出现两个或多个进程同时读写某些共享数据(共享文件或共享地址空间),而最后的结果取决于进程运行的精确时序,这种情况称为竞争条件(race condition) 。调试包含竞争情况(条件)的程序是一件十分艰辛的是。
竞争条件这个翻译相当烂,原文描述的其实是一种进程间的竞争情况,英文中codition翻译成情况我认为也没有不可。翻译成竞争条件反而会误导一些朴实的阅读者。
2. 临界区 Critical Region
凡是涉及共享内存、共享文件以及共享任何资源的情况都会引发类似的错误,要避免此类错误,关键是要找出某种途径来阻止多个进程同时读写共享数据。换言之,我们需要的是互斥(murual exclusion) ,即以某种手段确保当一个进程在使用一个共享变量或文件时,其他进程不能做同样的操作。
为此,我们将程序中对内存进行访问的程序片段称为临界区域(critical region) 或临界区(critical section) 。critical region直译为争议区或批判区。注意:临界区实际上是程序中出现内存访问的代码片段。
虽然可以简单控制两个进程不同时处于临界区,但此做法对并发并不友好,优雅的解决方案要满足以下4个条件:
- 任何两个进程不能同时处于其临界区
- 不应对CPU的速度和数量做任何假设
- 临界区外运行的进程不得阻塞其他进程
- 不得使进程无限期等待进入临界区
3. 忙等待的互斥
忙等待的互斥(Mutual Exclusion with Busy Waiting) :一下几种方案中,当一个进程在临界区中更新共享内存时,其他进程将不会进入其临界区。
3.1 屏蔽中断 Disabling Interrupts
在单处理系统中,最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断,并在就要离开之前再打开中断。这样在屏蔽中断之后CPU将不会被切换到其他进程,因此,一旦某个进程屏蔽中断后它就可以访问和修改共享内存,不必担心其他进程的介入。
不过,由于屏蔽中断这种方法会造成:1. 若进程屏蔽中断后不再打开中断,整个系统将会终止;2. 若使多处理器系统,屏蔽中断仅仅对执行disable指令的那个CPU有效,其他的CPU有可能会仍然访问共享内存。等问题,所以结论是:屏蔽中断对于操作系统本身而言是一项很有用的技术,但对于用户进程则并不是一种合适的通用互斥机制。
3.2 锁变量 Lock Variables
锁变量是一种软件解决方案,设想有一个共享(锁)变量,其初始值为0,当一个进程想要进入临界区时,首先检测这把锁,若该锁值为0,则将其设置为1并进入临界区;若为1,则此进程将等待直到其值变为0。 其中,0表示临界区没有进程,1表示临界区有进程。
此方案有一个严重问题:当一个进程读出锁变量的值为0时,如果恰好在该进程将其设置为1之前,另一个进程被调度运行,将其设置为1,当第一个进程再次运行时,同样会将该锁设置为1,此时会有两个进程同时进入临界区 。
3.3 严格轮换法 Strict Alternation
严格轮换法实现了两个需要进入临界区的进程的严格轮换,当其中一个进程进入临界区时,另一个进程将会不停的确认锁变量turn是否变为1或者0。连续测试一个变量直到某个值出现为止,称为忙等待(busy waiting)。由于忙等待会浪费CPU时间,所以一般需要避免,只有有理由认为忙等待的等待时间非常短才能使用忙等待。用于忙等待的锁,称为自旋锁(spin lock) 。
严格轮换法的缺点在于:如果一个进程比两一个慢了很多的话,轮流进入临界区将会导致两个进程都很慢。而且由于如果一个进程长时间运行在非临界区而另一个进程想要进入临界区时会造成该进程被一个非临界区的进程阻塞,违反了前述条件3,并不是一个很优雅的解决方案。
3.4 Peterson解法 Peterson‘s Solusion
1981年,G. L. Peterson发现了一个简易的且不需要严格轮换的软件互斥算法。该算法使用ANSI C编写。
3.5 TSL指令 The TSL Instruction
一种需要硬件支持的解决方案是使用TSL指令,在许多多处理器计算机中,都有一下指令:
- TSL RX, LOCK
该指令称为测试并加锁(test and set lock) ,该指令的机制为将内存字lock读入寄存器RX中,然后将内存字lock置入一个非零值。 在TSL指令中,读写操作保证是不可分割的,该指令结束前,其他处理器无法访问该内存字。执行TSL指令的CPU将锁住内存总线,以禁止其他CPU在本指令结束之前访问内存 。进程在进入临界区时先忙等待lock为空闲,直到返回拿到锁。
下图用JNE跳转到函数初始位置构造循环,从而构造忙等待。
一种可替代TSL的指令为XCHG,该指令将会原子性的交换两个位置的内容 。解法如下,本质与TSL的解决办法一样。所有Intel x86 CPU在底层同步中使用XCHG指令。
4. 睡眠与唤醒
虽然Peterson解法和TSL或XCHG解法都是较为优秀的,但其共同缺点是忙等待,会浪费CPU时间 。在考虑进程优先级之后,这类解法会产生优先级反转的问题:当一个低优先级L 的进程正处于临界区,高优先级H 进程此时进入就绪队列,此时高优先级开始忙等(等待L离开临界区),此时由于高优先级进程优先调度,此时L不会被调度运行,所以L无法离开临界区,此时会造成H永远忙等下去。
操作系统设计了几条进程间通信的原语,作用是在进程无法进入临界区时将进程阻塞,而不是忙等待。其中最简单的是:
- sleep:将调用进程阻塞的系统调用,即挂起进程,直到被另外进程唤醒
- wakeup:唤醒某个进程,参数为指定进程
· 生产者消费者问题
生产者消费者问题(producer-consumer problem) 也被称为有界缓冲区问题(bounded-buffer problem) ,是一个使用进程间通信原语的例子。两个进程共享一个公共的固定大小的缓冲区,其中一个进程为生产者,将信息放入缓冲区;另一个为消费者,从缓冲区取出信息。
- 当缓冲区满了时,让生产者睡眠,等待消费者从中取出一个或多个时再唤醒它;
- 当消费者发现缓冲区为空时,让消费者睡眠,直到生产者放入数据后唤醒它。
5. 信号量
信号量(Semaphores) 是E. W. Dijkstra 在1965年提出的一种方法,使用一个整形变量来累计唤醒次数,供以后使用。信号量是一种新的变量类型。一个信号量的取值可以是0(表示没有保存下来的唤醒操作)或正值(表示有一个或多个唤醒操作)。
Dijkstra建议设置两种操作:down和up(一般化后的sleep和wakeup)
- down:先检测信号量是否大于0,若该值大于0,则将其减1(即用掉一个保存的唤醒信号)并继续;若其值为0,则将调用进程睡眠,此时down操作并未完成。
- up:将信号量的值增1;如果有1个或多个进程在该信号量上睡眠,无法完成先前的down操作,则由系统选择其中一个睡眠的进程唤醒并允许该进程完成其down操作,此时,虽然有一次up操作,但信号量的值仍然为0。
注意:在down操作中,检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成的。 所谓原子操作即是要么这一组关联操作不间断执行要么都不执行。在up操作中,信号量的值增1和唤醒一个进程同样是不可分割的。
信号量解决生产者消费者问题
前一种生产者消费者问题的解决方案由于有严重竞争条件而会产生wakeup丢失的问题。为确保信号量正常工作,重要的是采用一种不可分割的方式来实现它,通常是将up和down作为系统调用实现。在以下情况暂时屏蔽全部中断:检测信号量、更新信号量和在需要时使某个进程睡眠。如果使用多个CPU,则每个信号量则应由一个锁变量进行保护。通过使用TSL或XCHG指令来确保同一时刻只有一个CPU在对信号量进行操作。
注意:使用TSL或XCHG指令来防止多个CPU同时访问一个信号量,这与生产者或消费者使用忙等待来等待对方腾出或填充缓冲区是有本质区别的。信号量的操作仅需要几毫秒,忙等待需要大量消耗CPU时间。
注意:其中信号量mutex用于确保消费者和生产者不会同时访问缓冲区。像mutex,供两个或多个进程使用的信号量,且初值为1,确保只有同时只有一个进程可以进入临界区,称作二元信号量(binary semaphore) ,即取值只有0和1两种。
信号量的另一种用途是用于实现同步(synchronization) ,在本例中的full和empty信号量就是为了保证某种事件的顺序发生或不发生。这种用法与互斥是不同的。
6. 互斥量
若不需要信号量的计数能力,可以使用一个信号量的简化版本,称为互斥量(mutex) 。互斥量仅适用于管理共享资源或一小段代码(因为只有两种状态)。由于互斥量在实现时既容易又有效,使得互斥量在实现用户线程包时非常有用。
互斥量是一个可以处于两种状态之一的变量:解锁和加锁。因此,可以只用一个二进制位表示它,不过实际一般适用整形变量,0表示解锁,其他所有值表示加锁。
当一个线程或进程需要访问临界区时,调用mutex_lock,如果该互斥量当前时解锁的,即临界区可用,则此调用成功,调用线程进入临界区;如果该互斥量已经加锁,则调用线程阻塞,直到在临界区中的线程完成执行并调用mutex_unlock。如果多个线程被阻塞在该互斥量上,则将随机选择一个线程并允许它获得锁。
由于互斥量非常简单,所以如果TSL或XCHG指令可用,就可很容易在用户空间实现它。
mutex_lock的代码虽然与enter_region代码十分相似,但其实有本质区别,enter_region进入临界区失败时,会循环测试锁而忙等待,而mutex_lock则会调用thread_yield来将CPU放弃给另一个线程,没有忙等待。
由于thread_yield只是在用户空间中对线程调度程序的一个调用,所以运行十分快捷,mutex_lock和mutex_unlock都不需要任何内核调用。
现在的关键问题是:如何在多个线程或进程中共享锁变量?
-
快速用户区互斥量futex
快速用户区互斥量(fast user space mutex, futex),futex是Linux的一个特性,实现了基本的锁,除非必须陷入内核,否则避免陷入内核,因此改善了性能。futex包含两个部分:一个内核服务和一个用户库 。内核服务提供一个等待队列,允许多个进程在一个锁上等待。在没有竞争时,内核不会参与其中,futex将完全工作在用户空间中。 如果出现竞争,futex不会自旋,而是使用一个系统调用将后进线程放在内核的等待队列中。 如果有线程在等待队列中,刚使用完锁的线程会通知内核对等待队列中的一个或多个进程或线程解除阻塞。 -
pthread中的互斥量
Pthread提供了许多可以用来同步线程的函数,其基本机制是使用一个可以被锁定和解锁的互斥量来保护临界区 。
Pthread提供除另一个除互斥量外的同步机制:条件变量(condition variables) 。互斥量在允许或阻塞对临界区的访问上是很有用的,条件变量则允许线程由于一些未达到的条件而阻塞。
7. 管程
尽管使用互斥量和信号量可以实现进程间的通信了,但由于在编写程序时,一不小心就会出现死锁(dead lock) 的现象。为了更容易编写正确的程序,Brinch Hansen(1973)和Hoare(1974)提出了一种高级同步原语,称为管程(monitor) 。
一个管程由一个过程、变量及数据结构等组成的一个集合,它们组成特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程,但进程不能再管程之外声明的过程中直接访问管程内的数据结构。
管程的一个重要特性是:任意时刻管程中只能有一个活跃进程。这一特性使管程有效的完成互斥。当一个进程调用管程过程中,该过程中的前几条指令将检查再管程中是否有其他活跃进程,如果有,调用进程将被挂起,直到另一个进程离开管程才将其唤醒,如果没有,则调用进程进入。进入管程的互斥由编译器负责。因此出错的可能性会小很多。
Java支持管程,支持用户级线程,只要将synchronized加入到方法声明中,Java将保证同一时刻只有一个线程执行此方法。Java中的同步方法与其他经典管程有本质差别:Java没有内嵌条件变量。而是提供两个过程wait和notify来进行线程的休眠和唤醒。
通过使临界区互斥的自动化,管程比信号量更容易保证并行编程的正确性。管程是一个编程语言概念,编译器必须要识别管程并采用某种方式实现互斥。
此外,管程和信号量的共同问题是:这些方法都只解决了访问同一个内存的多个CPU的互斥问题,如果存在多个内存空间,则这些原语将会失效。比如,如果一个分布式系统具有多个CPU,并且每个CPU拥有自己的私有内存,它们之间是用局域网相连,则这些原语将会失效。这里的结论是:信号量太低级了,而管程在少数几种编程语言之外又无法使用,并且,这些原语均未提供机器之间的信息交互方法。
8. 消息传递
实现不同机制之间的互斥的一种方法是消息传递(message passing) 。消息传递的进程通信的方法是使用两条原语send和receive,消息传递像信号量而不像管程,是系统调用而不是语言成分。
-
send(destination, &message)
向指定目标发送一条消息 -
reveive(source, &message)
从一个给定源接收一条消息,如果没有消息可用,则接收者可能被阻塞,直到一条消息到达。
8.1 消息传递系统的设计要点
消息传递系统(Message-Passing Systems) 面临比信号量和管程所未涉及的许多设计难点,例如消息有可能被网络丢失 。
为了防止消息丢失,发送方和接收方可以达成如下一致:一旦接收到消息,接收方马上回送一条特殊的确认(acknowledgment)消息。如果发送方在一段时间间隔内未收到确实,则重发。
此外,如果发送给发送方的确实消息丢失,接收方就将收到两次相同的消息。如何区分新老消息对接收方很重要。通常采用在每一条原始消息中嵌入一个连续的序号来解决此问题。如果接收方收到一条具有与此前收到的消息的相同序号,就可以忽略该消息。
消息系统还需解决进程命名的问题,在send和receive调用中所指定的进程必须是没有二义性的,此外,身份验证(authentication) 也是一个问题。
8.2 用消息传递解决生产者-消费者问题
9. 屏障
屏障(Barriers) 同步机制是一种用于进程组而不是用于像生产者消费者问题的双进程情形的。在有些应用场景中,需要分出一些阶段来处理问题,例如解压缩,可以在同一时刻分配多个线程分别解压多个部分,但要在所有线程全部解压完毕之后,合并线程才能执行。此类问题可以在每个阶段的结尾安置屏障来实现这种行为。当一个进程达到屏障时,它将被屏障阻拦,直到所有进程都达到该屏障为止。
10. 避免锁:读-复制-更新
众所周知,最快的锁就是根本没有锁 。我们可以使用读-复制-更新(Read-Copy-Update,RCU) 来实现,RCU将更新过程中的移除和再分配过程分离开来。