第3章并发控制互斥与同步

1、1第第3章章 并发控制并发控制互斥与同步互斥与同步清华大学清华大学 本章知识点：本章知识点： 3.1 并发原理并发原理 3.2 互斥互斥软件解决方法软件解决方法 3.3 互斥互斥硬件解决方法硬件解决方法 3.4 信号量信号量 3.5 管程管程 3.6 消息传递消息传递 3.7 读者读者/写者问题写者问题 3.8 系统举例（略）系统举例（略） 23.1 并发原理并发原理 在单处理机多道程序的系统中，进程的并发执行方式是插入执行，表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进

2、程的数据和物理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关。33.1.1 进程间的相互作用进程间的相互作用进程之间常常相互作用，存在某种彼此依赖或相互制约的关系：同步和互斥关系。 根据进程意识到其他进程的存在程度不同，可将进程间的相互作用划分为：进程互不觉察、进程间接觉察、进程直接觉察。43.1.2 进程间的相互竞争进程间的相互竞争 并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题： 互斥 死锁 饥饿 竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求 。53.1.3 进程间的相互合作进程

3、间的相互合作 1.通过共享合作 这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜在的控制问题。63.1.3 进程间的相互合作进程间的相互合作2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。 73.1.4 互斥的要求互斥的要求 并发进程的成功完成需要有定义临界段和实现互斥的能力，这是任何并发进程方案的基础。解决互斥问题必须满足以

4、下要求： 互斥执行 执行非临界段的进程不能受到其他进程的干扰 有限的等待 没有进程相对速度和数目的假设 进程进入到临界段中的时间有限 83.2 互斥互斥软件解决方法软件解决方法 软件方法对并发进程不提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误，但有利于深刻理解并发的复杂性。 93.2.1 dekker算法算法 dekker算法的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束，其中最基本的约束是任一时刻只能有一个进程访问内存中

5、某一位置。 103.2.1 dekker算法算法 1.第1种途径 这种方法保证了互斥，但它只记住了允许哪个进程进入其临界段，未记住每个进程的状态。 var turn: 0.1; turn为共享的全局变量process 0 process 1 while turn0 do nothing while turn1 do nothing；critical section; critical section;turn: =1; turn: =0; 113.2.1 dekker算法算法2.第2种途径这种解决方法依赖于进程执行的相对速度共享的全局变量是：var flag: array0.1of boole

6、an;它被初始化为falseprocess 0 process 1 while flag1do nothing; while flag0do nothing;flag0: =true; flag1: =true;critical section; critical section;flag0: =false; flag1: =false; 123.2.1 dekker算法算法3.第3种途径这种方法保证了互斥但会导致死锁问题。 process 0 process 1 flag0: =true; flag1: =true;while flag1 do nothing; while flag0 do

7、 nothing;critical section; critical section;flag0: =false; flag1: =false; 133.2.1 dekker算法算法4.第4种途径process 0 process 1 flag0: =true; flag1: =true;while flag1 do nothing; while flag0 do nothing;begin begin flag0: =false; flag1: =false; delay for a short time; delay for a short time; flag0: =true; fla

8、g1: =true;end; end;critical section; critical section;flag0: =false； flag1: =false; 143.2.1 dekker算法算法5.一个正确的解决方法 设计一个“指示”小屋，小屋内的黑板标明“turn”，当p0想进入其临界段时，置自己的flag为“true”，这时它去查看p1的flag，如果是“false”，则p0就立即进入自己的临界段，反之p0去查看“指示”小屋，如果turn=0，那么它知道自己应该坚持并不时去查看p1的小屋， p1将觉察到它应该放弃并在自己的黑板上写上“false”，以允许p0继续执行。 p0执行完

9、临界段后，它将flag置为“false”以释放临界段，并且将turn置为1，将进入权交给p1 。153.2.2 peterson算法算法 dekker算法可以解决互斥问题，但是，其复杂的程序难于理解，其正确性难于证明。peterson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法，进一步可将peterson算法推广到多个进程的情况。 163.2.2 peterson算法算法var flag: array0.1 of boolean; flag1: =true; turn: 0.1; turn: =0;procedure p0; while flag0 and turn=0 do no

10、thing;begin critical section; repeat flag1: =false; flag0: =true; remainder turn: =1; foreverwhile flag1 and turn=1 do nothing; end; critical section; begin flag0: =false; flag0: =false; remainder flag1: =false; forever turn: =1;end; parbeginprocedure p1; p0; p1begin parend repeat end.173.3 互斥互斥硬件解决

11、方法硬件解决方法 完全利用软件方法来解决进程互斥进入临界区的问题有一定的难度，且有很大局限性，现在有许多计算机提供了一些可以解决临界区问题的特殊的硬件指令。硬件方法通过特殊的机器指令实现互斥，可以降低开销。183.3.1 禁止中断禁止中断 在单处理机中，禁止进程被中断即可保证互斥，通过操作系统内核定义的禁止和允许中断的原语就可获得这种能力。进程执行临界段时不能被中断。 优点：在单处理机中可保证互斥。 缺点：代价较高，使执行效率显著降低在多处理机系统中，禁止中断不能保证互斥193.3.2 使用机器指令使用机器指令1.特殊的机器指令 在多处理机系统中，多个处理机共享一个共同的主存，这里并没有主/从

12、关系，也没有实现互斥的中断机制。许多系统都提供了一些特殊的硬件指令，允许我们在一个存储周期内去测试和修改一个字的内容（test and set指令），或者交换两个字的内容（exchange指令）等等。这些特殊指令可以用来解决临界段问题。 203.3.2 使用机器指令使用机器指令2.机器指令方法的特性优点： 可用于含有任意数量进程的单处理机或共享主存的多处理机； 比较简单，易于验证； 可支持多个临界段，每个临界段用各自的变量加以定义。缺点： 采用busy-waiting技术，进程等待进入临界段时耗费处理机时间； 可能产生饥饿； 可能产生死锁。213.4 信号量信号量 信号量是一个整型变量，除对其

13、初始化外，它可由两个不可中断的p、v操作存取。不论是采用一般信号量还是二元信号量，进程都将排队等候信号量，但这并不意味着进程移出的顺序与队列次序相同。 基本原则：两个或多个进程可通过单一的信号量展开合作，即进程在某一特定的地方停止执行，直到某个特定的信号量到来为止。通过信号量，任何复杂的合作要求都可被满足。 223.4.1 用信号量解决互斥问题用信号量解决互斥问题 信号量的互斥算法可以用小屋模型来描述。除了黑板外，小屋中还有一个大冰箱。某进程进入小屋后执行wait操作将黑板上的数减1，这时，如果黑板上的值非负，它就进入临界段，反之它就进入冰箱内冬眠。这时，就允许另一进程进入小屋。当一个进程完成

14、其临界段后，它进入小屋执行signal，将黑板上的值加1，这时如果黑板上的值为非正数，它就从冰箱中唤醒一个进程。 233.4.2 用信号量解决生产者用信号量解决生产者/消费者消费者问题问题 问题描述如下：一个或更多的生产者生产出某种类型的数据(记录、字符)，并把它们送入缓冲区，惟一的一个消费者一次从缓冲区中取走一个数据，系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。 243.4.2 用信号量解决生产者用信号量解决生产者/消费者消费者问题问题 用二元信号量来解决此问题。在任何时候生产者(p)都可向缓冲区中添加数据，在添加数据前，p执行waitb(s)，然后执

15、行signalb(s)以防止在添加过程中，别的消费者(c)或p访问缓冲区。在进入到临界段时，p将增加n的值，如果n=1则在此次添加数据前缓冲区为空，于是p执行signalb(delay)并将这个情况通知c。c最初执行waitb(delay)来等待p生产出第一个数据，然后取走数据并在临界段中减小n的值。如果p总保持在c前面，那么c就不会因为信号量delay而阻塞，因为n总是正数，这样p和c都能顺利地工作。这个方法也存在缺陷有可能导致死锁。 253.4.2 用信号量解决生产者用信号量解决生产者/消费者消费者问题问题 解决这个问题的一个方法是引入一个附加变量，它在消费者的临界段中设置。这样，就不会出

16、现死锁了。 使用一般信号量可以得到另一种解决方法，变量n是一个信号量，它的值等于缓冲区中的数据项数。 263.4.3 信号量的实现信号量的实现 wait和signal操作都必须作为原子操作实现。显然，用硬件方法或固件方法都可解决这一问题，而且还有其他解决方法。尽管wait和signal操作执行的时间较短，但因包含了忙-等，故忙-等占用的时间是主要的。 对单处理机系统而言，可以在wait和signal操作期间屏蔽中断，而且这些操作的执行时间相对较短。273.4.4 用信号量解决理发店问题用信号量解决理发店问题 理发店问题是使用信号量实现并发的另一个例子，它同操作系统中的实际问题非常相似。如图示理

17、发椅沙发收款台出口入口顾客休息区283.5 管程管程 信号量为实现互斥和进程间的协调提供了一个功能强大而灵活的工具，然而，使用信号量来编制正确的程序是困难的。 作为程序设计语言中的一种结构，管程(monitor)提供了与信号量相同的表达能力，但它更容易控制。 293.5.1 带信号量的管程带信号量的管程 管程是一种并发性的结构，它包括用于分配一个特定的共享资源或一组共享资源的数据和过程。管程由三部分组成：局部于管程的共享变量说明。对该数据结构进行操作的一组过程。对局部于管程的数据设置初始值的语句。此外，还需为该管程赋予一个名字。 303.5.1 带信号量的管程带信号量的管程管程最主要的特点如下

18、： 只能通过管程中的过程而不能用其他外部过程访问其局部数据变量。 进程通过调用管程的过程而进入管程。 每一时刻只能有一个进程在管程中执行，任何其他调用管程的进程将被挂起直至管程可用为止。313.5.2 用管程解决生产者用管程解决生产者/消费者消费者问题问题 管程模块控制着缓冲区。管程包括两个条件变量：当缓冲区中还有空位置时，变量notfull为true，如果缓冲区中至少有一个字符存在，则变量notempty为true。生产者只能通过管程中的过程append向缓冲区添加字符，生产者不能直接访问缓冲区。这个例子比较了管程和信号量。 323.6 消息传递消息传递 进程间的相互作用必须满足两个条件：同

19、步和通信，进程需要同步来实现互斥，进程间的协同需要交换信息，一个能解决上述两个问题的方法是消息传递(message passing)。消息传递还有一个优点是，它的适应性很强，能在分布式系统、共享存储器的多处理机系统以及单处理机系统等不同系统中实现。 333.6.1 消息传递原语消息传递原语原语： send (destination, message) receive (source, message)343.6.2 用消息传递实现同步用消息传递实现同步 无论是发送方还是接收方都可能被阻塞。下面有三种最一般的组合，任何特定系统都实现了其中的一种或两种： 阻塞发送，阻塞接收。 无阻塞发送，阻塞接收

20、。 无阻塞发送，无阻塞接收。 353.6.3 寻址方式寻址方式1. 直接寻址 对直接寻址方式，send原语中明确标明了目的进程。receive原语有两种方式：第一种方式接收进程预先知道发送消息的源进程，另一种方式则不可能预先知道源进程。363.6.3 寻址方式寻址方式2. 间接寻址 消息不直接由发送方传给接收方，而是通过一个共享的数据结构，包括临时存放消息的队列（邮箱式端口）。这种方法有很大的灵活性。进程与邮箱的关系可以是静态的或动态的，端口通常与一个特定的进程相关联。端口通常由接收进程产生并为其所有。 373.6.4 消息格式消息格式 消息格式依赖于消息系统的用途和消息系统是在单个计算机上运

21、行还是在分布式系统中运行，一些操作系统选择了较短的定长消息以减小处理和存储的开销，如果有大量的数据需要传递，那么可以将数据存入文件并把文件作为消息传递，一种更为灵活的方法是允许变长消息。 383.6.4 消息格式消息格式支持变长消息的操作系统中的消息格式 消 息 源目 的 地消息长度控制信息消息类型消息头消息体消息的内容393.6.5 排队规则排队规则 最简单的排队规则是先进先出，但这远远不够。一个改进的方法是由发送方或接收方基于消息的类型标明消息的优先权；另一个改进方法是允许接收方检查消息队列并选择要接收的消息。 403.6.6 用消息传递实现互斥用消息传递实现互斥 假设使用阻塞receiv

22、e原语和无阻塞send原语，并发进程集共享一个邮箱mutex，将邮箱初始化为仅包含一个空消息，欲进入临界段的进程首先要接收相应的消息，如果邮箱为空则该进程被阻塞，一旦进程得到消息它就执行其临界段，然后再将消息放回邮箱，这样消息就如同令牌一样在进程之间传递。 413.6.6 用消息传递实现互斥用消息传递实现互斥 这种解决方法是，假设有多于一个进程并发执行receive操作，则有： 如果仅有一个消息，那么它只可传递给一个进程，其他进程将被阻塞。 如果邮箱为空，则所有的进程将被阻塞。当消息可用时，仅有一个阻塞进程被激活并得到消息。423.6.6 用消息传递实现互斥用消息传递实现互斥 使用消息传递所支持的互斥和信号量不具备传递数据的能力可以解决带有界缓冲区的生产者/消费者问题。 这个方法非常灵活