并发控制互斥与同步.ppt

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

2、之间常常相互作用，存在某种彼此依赖或相互制约的关系：同步和互斥关系。 根据进程意识到其他进程的存在程度不同，可将进程间的相互作用划分为：进程互不觉察、进程间接觉察、进程直接觉察。,4,3.1.2 进程间的相互竞争,并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题： 互斥 死锁 饥饿 竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求 。,5,3.1.3 进程间的相互合作,1.通过共享合作 这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一

3、个潜在的控制问题。,6,3.1.3 进程间的相互合作,2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。,7,3.1.4 互斥的要求,并发进程的成功完成需要有定义临界段和实现互斥的能力，这是任何并发进程方案的基础。解决互斥问题必须满足以下要求： 互斥执行 执行非临界段的进程不能受到其他进程的干扰 有限的等待 没有进程相对速度和数目的假设 进程进入到临界段中的时间有限,8,3.2 互斥软件解决方法,软件方法对并发进程

4、不提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误，但有利于深刻理解并发的复杂性。,9,3.2.1 Dekker算法,Dekker算法的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束，其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。,10,3.2.1 Dekker算法,1.第1种途径 这种方法保证了互斥，但它只记住了允许哪个进程进入其临界段，未记住每个进程的状态。,var turn: 0.1; turn为共享的全局变

5、量 PROCESS 0 PROCESS 1 while turn0 do nothing while turn1 do nothing；critical section; critical section; turn: =1; turn: =0; ,11,3.2.1 Dekker算法,2.第2种途径 这种解决方法依赖于进程执行的相对速度,共享的全局变量是：var flag: array0.1of boolean; 它被初始化为false PROCESS 0 PROCESS 1 while flag1do nothing; while flag0do nothing; flag0: =true;

6、 flag1: =true; critical section; critical section; flag0: =false; flag1: =false; ,12,3.2.1 Dekker算法,3.第3种途径 这种方法保证了互斥但会导致死锁问题。,PROCESS 0 PROCESS 1 flag0: =true; flag1: =true; while flag1 do nothing; while flag0 do nothing; critical section; critical section; flag0: =false; flag1: =false; ,13,3.2.1 D

7、ekker算法,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; flag1: =true; end; end; critical section; critical section; flag0: =false； flag1: =f

8、alse; ,14,3.2.1 Dekker算法,5.一个正确的解决方法 设计一个“指示”小屋，小屋内的黑板标明“turn”，当P0想进入其临界段时，置自己的flag为“true”，这时它去查看P1的flag，如果是“false”，则P0就立即进入自己的临界段，反之P0去查看“指示”小屋，如果turn=0，那么它知道自己应该坚持并不时去查看P1的小屋， P1将觉察到它应该放弃并在自己的黑板上写上“false”，以允许P0继续执行。 P0执行完临界段后，它将flag置为“false”以释放临界段，并且将turn置为1，将进入权交给P1 。,15,3.2.2 Peterson算法,Dekker算法

9、可以解决互斥问题，但是，其复杂的程序难于理解，其正确性难于证明。Peterson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法，进一步可将Peterson算法推广到多个进程的情况。,16,3.2.2 Peterson算法,var flag: array0.1 of boolean; flag1: =true; turn: 0.1; turn: =0; procedure P0; while flag0 and turn=0 do nothing; begin critical section; repeat flag1: =false; flag0: =true; remainder

10、 turn: =1; forever while flag1 and turn=1 do nothing; end; critical section; begin flag0: =false; flag0: =false; remainder flag1: =false; forever turn: =1; end; parbegin procedure P1; P0; P1 begin parend repeat end.,17,3.3 互斥硬件解决方法,完全利用软件方法来解决进程互斥进入临界区的问题有一定的难度，且有很大局限性，现在有许多计算机提供了一些可以解决临界区问题的特殊的硬件指令

11、。硬件方法通过特殊的机器指令实现互斥，可以降低开销。,18,3.3.1 禁止中断,在单处理机中，禁止进程被中断即可保证互斥，通过操作系统内核定义的禁止和允许中断的原语就可获得这种能力。进程执行临界段时不能被中断。 优点： 在单处理机中可保证互斥。 缺点： 代价较高，使执行效率显著降低 在多处理机系统中，禁止中断不能保证互斥,19,3.3.2 使用机器指令,1.特殊的机器指令 在多处理机系统中，多个处理机共享一个共同的主存，这里并没有主/从关系，也没有实现互斥的中断机制。许多系统都提供了一些特殊的硬件指令，允许我们在一个存储周期内去测试和修改一个字的内容（Test and Set指令），或者交换

12、两个字的内容（Exchange指令）等等。这些特殊指令可以用来解决临界段问题。,20,3.3.2 使用机器指令,2.机器指令方法的特性 优点： 可用于含有任意数量进程的单处理机或共享主存的多处理机； 比较简单，易于验证； 可支持多个临界段，每个临界段用各自的变量加以定义。 缺点： 采用busy-waiting技术，进程等待进入临界段时耗费处理机时间； 可能产生饥饿； 可能产生死锁。,21,3.4 信号量,信号量是一个整型变量，除对其初始化外，它可由两个不可中断的P、V操作存取。不论是采用一般信号量还是二元信号量，进程都将排队等候信号量，但这并不意味着进程移出的顺序与队列次序相同。 基本原则：两

13、个或多个进程可通过单一的信号量展开合作，即进程在某一特定的地方停止执行，直到某个特定的信号量到来为止。通过信号量，任何复杂的合作要求都可被满足。,22,3.4.1 用信号量解决互斥问题,信号量的互斥算法可以用小屋模型来描述。除了黑板外，小屋中还有一个大冰箱。某进程进入小屋后执行wait操作将黑板上的数减1，这时，如果黑板上的值非负，它就进入临界段，反之它就进入冰箱内冬眠。这时，就允许另一进程进入小屋。当一个进程完成其临界段后，它进入小屋执行signal，将黑板上的值加1，这时如果黑板上的值为非正数，它就从冰箱中唤醒一个进程。,23,3.4.2 用信号量解决生产者/消费者问题,问题描述如下：一个

14、或更多的生产者生产出某种类型的数据(记录、字符)，并把它们送入缓冲区，惟一的一个消费者一次从缓冲区中取走一个数据，系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。,24,3.4.2 用信号量解决生产者/消费者问题,用二元信号量来解决此问题。在任何时候生产者(P)都可向缓冲区中添加数据，在添加数据前，P执行waitB(s)，然后执行signalB(s)以防止在添加过程中，别的消费者(C)或P访问缓冲区。在进入到临界段时，P将增加n的值，如果n=1则在此次添加数据前缓冲区为空，于是P执行signalB(delay)并将这个情况通知C。C最初执行waitB(del

15、ay)来等待P生产出第一个数据，然后取走数据并在临界段中减小n的值。如果P总保持在C前面，那么C就不会因为信号量delay而阻塞，因为n总是正数，这样P和C都能顺利地工作。这个方法也存在缺陷有可能导致死锁。,25,3.4.2 用信号量解决生产者/消费者问题,解决这个问题的一个方法是引入一个附加变量，它在消费者的临界段中设置。这样，就不会出现死锁了。 使用一般信号量可以得到另一种解决方法，变量n是一个信号量，它的值等于缓冲区中的数据项数。,26,3.4.3 信号量的实现,wait和signal操作都必须作为原子操作实现。显然，用硬件方法或固件方法都可解决这一问题，而且还有其他解决方法。尽管wai

16、t和signal操作执行的时间较短，但因包含了忙-等，故忙-等占用的时间是主要的。 对单处理机系统而言，可以在wait和signal操作期间屏蔽中断，而且这些操作的执行时间相对较短。,27,3.4.4 用信号量解决理发店问题,理发店问题是使用信号量实现并发的另一个例子，它同操作系统中的实际问题非常相似。如图示,28,3.5 管程,信号量为实现互斥和进程间的协调提供了一个功能强大而灵活的工具，然而，使用信号量来编制正确的程序是困难的。 作为程序设计语言中的一种结构，管程(Monitor)提供了与信号量相同的表达能力，但它更容易控制。,29,3.5.1 带信号量的管程,管程是一种并发性的结构，它包

17、括用于分配一个特定的共享资源或一组共享资源的数据和过程。管程由三部分组成： 局部于管程的共享变量说明。 对该数据结构进行操作的一组过程。 对局部于管程的数据设置初始值的语句。此外，还需为该管程赋予一个名字。,30,3.5.1 带信号量的管程,管程最主要的特点如下： 只能通过管程中的过程而不能用其他外部过程访问其局部数据变量。 进程通过调用管程的过程而进入管程。 每一时刻只能有一个进程在管程中执行，任何其他调用管程的进程将被挂起直至管程可用为止。,31,3.5.2 用管程解决生产者/消费者问题,管程模块控制着缓冲区。管程包括两个条件变量：当缓冲区中还有空位置时，变量notfull为true，如果

18、缓冲区中至少有一个字符存在，则变量notempty为true。生产者只能通过管程中的过程append向缓冲区添加字符，生产者不能直接访问缓冲区。这个例子比较了管程和信号量。,32,3.6 消息传递,进程间的相互作用必须满足两个条件：同步和通信，进程需要同步来实现互斥，进程间的协同需要交换信息，一个能解决上述两个问题的方法是消息传递(message passing)。消息传递还有一个优点是，它的适应性很强，能在分布式系统、共享存储器的多处理机系统以及单处理机系统等不同系统中实现。,33,3.6.1 消息传递原语,原语： send (destination, message) receive (s

19、ource, message),34,3.6.2 用消息传递实现同步,无论是发送方还是接收方都可能被阻塞。下面有三种最一般的组合，任何特定系统都实现了其中的一种或两种： 阻塞发送，阻塞接收。 无阻塞发送，阻塞接收。 无阻塞发送，无阻塞接收。,35,3.6.3 寻址方式,1. 直接寻址 对直接寻址方式，send原语中明确标明了目的进程。receive原语有两种方式：第一种方式接收进程预先知道发送消息的源进程，另一种方式则不可能预先知道源进程。,36,3.6.3 寻址方式,2. 间接寻址 消息不直接由发送方传给接收方，而是通过一个共享的数据结构，包括临时存放消息的队列（邮箱式端口）。这种方法有很大

20、的灵活性。进程与邮箱的关系可以是静态的或动态的，端口通常与一个特定的进程相关联。端口通常由接收进程产生并为其所有。,37,3.6.4 消息格式,消息格式依赖于消息系统的用途和消息系统是在单个计算机上运行还是在分布式系统中运行，一些操作系统选择了较短的定长消息以减小处理和存储的开销，如果有大量的数据需要传递，那么可以将数据存入文件并把文件作为消息传递，一种更为灵活的方法是允许变长消息。,38,3.6.4 消息格式,支持变长消息的操作系统中的消息格式,39,3.6.5 排队规则,最简单的排队规则是先进先出，但这远远不够。一个改进的方法是由发送方或接收方基于消息的类型标明消息的优先权；另一个改进方法

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