第四第四章章 进程通信进程通信124.1 进程的同步与互斥进程的同步与互斥4.1.1 同步与互斥的概念同步与互斥的概念 两个或两个以上的进程要协作完成一个任两个或两个以上的进程要协作完成一个任务，它们之间就要互相配合，需要在某些务，它们之间就要互相配合，需要在某些动作之间进行同步。动作之间进行同步。 进程间另一种关系是互斥，这种关系一进程间另一种关系是互斥，这种关系一般发生在两个或两个以上的进程竞争某些般发生在两个或两个以上的进程竞争某些同时只能被一个进程使用的资源的情况下。同时只能被一个进程使用的资源的情况下。34.1.2 临界段问题临界段问题n在一段时间内只能允许一个进程访问的在一段时间内只能允许一个进程访问的资源称为资源称为临界资源临界资源，如打印机、磁带机、，如打印机、磁带机、光盘刻写机、绘图仪等光盘刻写机、绘图仪等n进程执行的访问临界资源的程序段称为进程执行的访问临界资源的程序段称为临界段临界段或或互斥段互斥段。临界资源与临界段临界资源与临界段4 统计两个进程统计两个进程 P1P1和和P2P2对共享变量对共享变量countcount访问计数：访问计数：P1P1： : : P2P2：: : R1=count R1=count （0 0） R2=countR2=count（1 1） R1=R1+1 R1=R1+1 R2=R2+1R2=R2+1 count=R1 count=R1 （1 1） count=R2count=R2 （2 2） : : : :结果：结果：count2设设count初值初值05两个进程可能的相对执行次序两个进程可能的相对执行次序 P1：R1=count （0 0） R1=R1+1 （1 1） P2：R2=count （0 0） R2=R2+1 （1 1） count=R2 （1 1） P1：count=R1 （1 1）n虽然虽然P1和和P2进程各自都执行了对进程各自都执行了对count加加1的的操作段，但操作段，但结果结果count只增加只增加1。n因此，变量因此，变量count就是临界资源，就是临界资源，P1、P2访问访问count的两个程序段就是临界段，诸进程必须的两个程序段就是临界段，诸进程必须互斥地进入临界段。互斥地进入临界段。64.2 进程间互斥控制方法进程间互斥控制方法 锁可以用于控制临界段的互斥执行。锁有两锁可以用于控制临界段的互斥执行。锁有两个状态，一个是打开状态，另一个是关闭状态，个状态，一个是打开状态，另一个是关闭状态，故锁可以用布尔变量表示。在故锁可以用布尔变量表示。在C中，锁变量可中，锁变量可以定义为以定义为char或或int类型变量。设类型变量。设x为锁变量，为锁变量，则定义：则定义： x = 0 锁的打开状态；锁的打开状态；1 锁的关闭状态。锁的关闭状态。4.2.1 锁的表示和操作锁的表示和操作7v当进程希望进入临界段时，首先要测试当进程希望进入临界段时，首先要测试锁的状态，如锁是打开的，表示无进程锁的状态，如锁是打开的，表示无进程处于临界段，那么可以关闭该锁，并进处于临界段，那么可以关闭该锁，并进入临界段。入临界段。v当该进程处于临界段时，其他试图进入当该进程处于临界段时，其他试图进入临界段的进程由于在测试锁的状态时发临界段的进程由于在测试锁的状态时发现它处于关闭状态，就只能在临界段外现它处于关闭状态，就只能在临界段外等待。等待。用锁变量控制临界段的执行用锁变量控制临界段的执行8用锁操作控制进程对临界段的互斥执行用锁操作控制进程对临界段的互斥执行 (a)LOCK (x) x=0 ?x=1临界段临界段+-UNLOCK (x)临界段临界段x=0(b)94.2.2 锁的安全控制锁的安全控制n锁的关闭操作锁的关闭操作LOCK包括测试和关闭两个包括测试和关闭两个操作步骤，这两个操作步骤涉及临界资源操作步骤，这两个操作步骤涉及临界资源x,故这段程序也是临界段。故这段程序也是临界段。n假定锁是打开的，当一个进程假定锁是打开的，当一个进程P1在测试锁在测试锁的状态后，还没来得及关闭它的一瞬间，的状态后，还没来得及关闭它的一瞬间，发生了中断；发生了中断；n中断返回时，系统可能调度另一个进程中断返回时，系统可能调度另一个进程P2执行。执行。P2执行时也对该锁的状态进行测试，执行时也对该锁的状态进行测试，发觉它处于打开状态，于是关闭该锁，并发觉它处于打开状态，于是关闭该锁，并进入临界段。那么两个进程就同时处于一进入临界段。那么两个进程就同时处于一个临界段之中。个临界段之中。101. 测试并设置指令测试并设置指令test&setn有些计算机提供专门的锁操作指令有些计算机提供专门的锁操作指令test&set，该指令首先测试锁变量的值，该指令首先测试锁变量的值，如为如为1，则重复执行本指令；如为，则重复执行本指令；如为0，则，则立即将锁变量的值置为立即将锁变量的值置为1。n由于由于test&set是一条完整的指令，而在是一条完整的指令，而在一条指令的执行中间是不会被中断的，一条指令的执行中间是不会被中断的，故保证了锁的测试和关闭操作的连续性。故保证了锁的测试和关闭操作的连续性。112. 交换指令交换指令用用8086指令实现锁操作指令实现锁操作check：MOV AL, 1 ；置测试单元寄存器置测试单元寄存器AL的值为的值为1LOCK XCHG X, AL ；在本指令的执行时封锁总线，在本指令的执行时封锁总线， ；交换锁变量交换锁变量X与测试单元的值与测试单元的值TEST AL, AL ；测试测试AL的值的值JNZ check ；如如AL非非0，即原锁处于关闭状态，即原锁处于关闭状态，: ；跳转至；跳转至check，重复测试过程重复测试过程临界段临界段 ；锁变量；锁变量X已置为已置为1123. 开、关中断法开、关中断法 1）这种方法只能用于单这种方法只能用于单CPU系系统。统。 2）如果临界段操作比较复杂，如果临界段操作比较复杂，执行时间较长，那么长时间地关执行时间较长，那么长时间地关闭中断会降低系统对外部中断响闭中断会降低系统对外部中断响应的速度，影响系统处理紧迫事应的速度，影响系统处理紧迫事件的能力；件的能力； 3）采用开、关中断的硬件锁方法采用开、关中断的硬件锁方法禁止了其他无关的进程进入不同禁止了其他无关的进程进入不同的临界段，这种做法显然伤害了的临界段，这种做法显然伤害了很多的很多的“无辜者无辜者”。 关中断关中断 临界临界区区 开开中断中断134. 用硬件锁锁软件锁，用软件锁锁临界段用硬件锁锁软件锁，用软件锁锁临界段n 软件锁的软件锁的LOCK操作包括测试操作包括测试和关闭两个操作步骤，它本身和关闭两个操作步骤，它本身也是一种临界段，故可以用硬也是一种临界段，故可以用硬件锁件锁开、关中断保证软件开、关中断保证软件锁操作的完整性。锁操作的完整性。n 由于软件锁是一种程序长度最由于软件锁是一种程序长度最短的临界段，故用开、关中断短的临界段，故用开、关中断的方法保证锁操作的完整性几的方法保证锁操作的完整性几乎不会影响到系统响应其他的乎不会影响到系统响应其他的中断请求。中断请求。n用软件锁保证临界段执行的独用软件锁保证临界段执行的独占性，不会影响到其他无关进占性，不会影响到其他无关进程进入不同的临界段，这是一程进入不同的临界段，这是一种安全而高效的锁。种安全而高效的锁。LOCK(x) 关中断关中断 开中断开中断 x=0? + x=1 开中断开中断 临界段临界段图图4-3 复合锁的操作流程复合锁的操作流程144.3 信号灯和信号灯和semWait、semSignal操作操作 信号灯定义成具有整型值，并能对其施加以下三信号灯定义成具有整型值，并能对其施加以下三种操作的变量，除了这三种操作之外的任何操作都种操作的变量，除了这三种操作之外的任何操作都不能测试和处理信号灯的值。不能测试和处理信号灯的值。（1）初始化操作，信号灯能初始化为非负的值。）初始化操作，信号灯能初始化为非负的值。（2）semWait操作操作，能减小信号灯的值，如结能减小信号灯的值，如结果值为负，执行果值为负，执行semWait操作的进程就被封锁。操作的进程就被封锁。（3）semSignal操作操作，能增加信号灯的值，如能增加信号灯的值，如果结果值非正，那么原先因执行果结果值非正，那么原先因执行semWait操作而阻操作而阻塞的进程被解除阻塞。塞的进程被解除阻塞。15semWait、semSignal操作两个原语定义操作两个原语定义typedef struct semaphore int value ； Queue queue； Semaphore ；Semaphores；16voidsemSignal(s)semaphores；if ( +s.value = 0 ) 从等待队列从等待队列queue中移出一进程；中移出一进程；将该进程置入就绪队列中；将该进程置入就绪队列中；voidsemWait(s)semaphores ；if ( -s.value 0 ) 将进程置入等待队列将进程置入等待队列queue中；中；封锁进程；封锁进程；转进程调度程序；转进程调度程序；174.4 信号灯的应用信号灯的应用4.4.1 利用信号灯实现互斥利用信号灯实现互斥置信号灯置信号灯s的初值为的初值为1 P1 Pi PnsemWait(s) semWait (s) semWait (s) 临界段临界段临界段临界段 临界段临界段 semSignal(s) semSignal(s) semSignal (s)图图4-4 信号灯用于进程间互斥信号灯用于进程间互斥18信号灯的所有可能取值及意义为：信号灯的所有可能取值及意义为：s = 1 无进程进入临界段无进程进入临界段 0 有一进程进入临界段有一进程进入临界段 -1 有一进程进入临界段，有一进程进入临界段，另一进程被阻塞另一进程被阻塞如有如有n个并发进程涉及一个临界段，则上个并发进程涉及一个临界段，则上式最后一行式最后一行s的取值为的取值为i， -(n-1)-(n-1) i-1i-1，表示当前有表示当前有| |i|i|个进程被阻塞。个进程被阻塞。两个并发进程涉及一个临界段两个并发进程涉及一个临界段194.4.2 4.4.2 阻塞阻塞唤醒协议唤醒协议置信号灯置信号灯s的初值为的初值为0 Pa Pb 计算计算func1( ) 计算计算func2( )L1：semWait(s) 将计算结果存入缓冲区将计算结果存入缓冲区获得获得Pb的计算结果的计算结果 L2：semSignal(s) 计算乘积计算乘积 : :图图4-5 阻塞阻塞唤醒协议的实现唤醒协议的实现20从图中可以看出，当进程从图中可以看出，当进程a a执行到执行到L1L1点时，如进程点时，如进程b b还未执行到还未执行到L2L2点，也即点，也即func2func2函数的计算还未完成，进程函数的计算还未完成，进程a a就就要同步等待进程要同步等待进程b b。而进程而进程b b则不必同步等待进程则不必同步等待进程a a，所所以说这种同步是非对称的，或可以称以说这种同步是非对称的，或可以称为为“半同步半同步”。214.4.3 两个进程间的同步两个进程间的同步 1. 一个全同步的例子一个全同步的例子 设有两个进程设有两个进程Pa和和Pb。进程进程Pa每次执行每次执行一个计算，并将结果存入一个缓冲区；一个计算，并将结果存入一个缓冲区； 进程进程Pb则从缓冲区中取出结果，并将结则从缓冲区中取出结果，并将结果打印出来。果打印出来。22 为了为了实现计算进程和打印进程之间的实现计算进程和打印进程之间的相互同步，就需要设置相互同步，就需要设置2个信号量个信号量S1和和S2。 在在semWait、semSignal操作之前操作之前两个信号量的含义为：两个信号量的含义为：S1表示缓冲区中表示缓冲区中是否已存入进程是否已存入进程Pa的计算结果，也即通的计算结果，也即通知进程知进程Pb是否可取出缓冲区中的信息并是否可取出缓冲区中的信息并送往打印机。送往打印机。 S1值为：值为： 0：Pa没存入新的计算结果没存入新的计算结果 1：Pa已存入新的计算结果已存入新的计算结果23 S2：表示缓冲区中的结果是否已被表示缓冲区中的结果是否已被进程进程Pb取去，也即通知进程取去，也即通知进程Pa是否是否可将新的计算结果再存入缓冲区。可将新的计算结果再存入缓冲区。 S2的值为：的值为： 0：Pb没取走缓冲区中的数据，没取走缓冲区中的数据，缓冲区满缓冲区满 1：Pb已取走缓冲区中的数据，已取走缓冲区中的数据，缓冲区空缓冲区空24信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)25信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)226信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)23(0)27信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)23(0)428信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)23(0)45(0)29信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)2, 63(0)45(0)30信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)2, 63(0), 7(-1)45(0)31信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)2, 63(0), 7(-1)45(0)832信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)2, 63(0), 7(-1)45(0)89（0）33信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1)2, 63(0), 7(-1)45(0)89（0）1034信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1), 11(-1)2, 63(0), 7(-1)45(0)89（0）1035信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1), 11(-1)2, 63(0), 7(-1)4, 125(0)89（0）1036信号灯的初值可设置为：信号灯的初值可设置为： S1为为0：缓冲区还未存入数据缓冲区还未存入数据 S2为为1：缓冲空闲（相当于缓冲空闲（相当于Pb已取走数据）已取走数据） 计算进程计算进程Pa打印进程打印进程Pb computing semWait(s1) semWait(s2) get (result) put (result) semSignal(s2) semSignal(s1) printing图图 4-64-6 两个进程之间的全同步两个进程之间的全同步1(-1), 11(-1)2, 63(0), 7(-1)4, 125(0)89（0）10372.互斥和同步对信号灯操作方法的差异互斥和同步对信号灯操作方法的差异n互斥和同步都是通过对信号灯的互斥和同步都是通过对信号灯的semWait、semSignal操作来实现的，但这两种控制机制对信号操作来实现的，但这两种控制机制对信号灯的操作策略是不同的。灯的操作策略是不同的。n互斥实现是不同的进程对同一信号灯进行互斥实现是不同的进程对同一信号灯进行semWait、semSignal 操作，一个进程在成功地对信号灯执行了操作，一个进程在成功地对信号灯执行了semWait操作后进入临界段，并在退出临界段后，由操作后进入临界段，并在退出临界段后，由该进程本身对这信号灯执行该进程本身对这信号灯执行semSignal操作，表示没操作，表示没有进程处于临界段，可让其他进程进入。有进程处于临界段，可让其他进程进入。n同步的实现由一个进程同步的实现由一个进程Pa对一个信号灯进行对一个信号灯进行semWait操作后，只能由另一个进程操作后，只能由另一个进程Pb对同一个信对同一个信号灯进行号灯进行semSignal操作，使操作，使Pa能继续前进，在这种能继续前进，在这种情况下，进程情况下，进程Pa要同步等待要同步等待Pb。n如进程如进程Pb也要同步等待也要同步等待Pa，则要设置另一个信号灯。则要设置另一个信号灯。384.4.4 生产者和消费者问题生产者和消费者问题n生产者和消费者问题是通过有限的缓冲区（仓库）生产者和消费者问题是通过有限的缓冲区（仓库）将一群生产者将一群生产者P1, P2P1, P2PkPk和一群消费者和一群消费者C1,C2C1,C2CmCm联系起来。可设信号量联系起来。可设信号量nbuffersbuffers的初值为的初值为n n，表示空闲的缓冲区数目。表示空闲的缓冲区数目。nproductsproducts的初值为的初值为0 0，表示已存入缓冲区的产品，表示已存入缓冲区的产品数目。数目。n生产者和消费者问题的一般过程为：生产者在执生产者和消费者问题的一般过程为：生产者在执行行semWait(buffers)semWait(buffers)之后，只要之后，只要buffers0(buffers0(还还有空闲的缓冲区有空闲的缓冲区) )，就可将产品送入。消费者在，就可将产品送入。消费者在执行执行semWait(products)semWait(products)后，只要后，只要products0products0( (产品还未取完产品还未取完) )，就可以从缓冲区中取走产品，就可以从缓冲区中取走产品，并消费之。否则，生产者或消费者进程就被阻塞。并消费之。否则，生产者或消费者进程就被阻塞。39 producers: customers:producers: customers: while ( ) while ( ) produce next product; semWait (products); semWait (buffers); get product from buffers; Put product into buffers; semSignal (buffers) semSignal (products);consume product; 40 producers: customers:producers: customers: while ( ) while ( ) produce next product; semWait (products); semWait (buffers); semWait (mutex); semWait (mutex); get product from buffers; Put product into buffers; semSignal (mutex); semSignal (mutex); semSignal (buffers) semSignal (products);consume product; 请请仔仔细细推推敲敲semWait、semSignal操操作作的的次次序序。这这些些操操作作的的次次序序安安排排得得不不合合理理，就就有有可可能能发发生生“死死锁锁”。414.4.5 读者读者写者问题写者问题 n常会有若干个并发进程对数据对象进行读写的情常会有若干个并发进程对数据对象进行读写的情况。有些进程只要求读数据对象，有些进程则要况。有些进程只要求读数据对象，有些进程则要求修改数据对象。求修改数据对象。n若干个读者可以同时访问数据对象，不需要互斥若干个读者可以同时访问数据对象，不需要互斥也不会产生任何问题，但一个写者不能与任何的也不会产生任何问题，但一个写者不能与任何的读者或者写者同时访问数据对象，否则就可能破读者或者写者同时访问数据对象，否则就可能破坏数据对象的完整性、正确性与一致性。坏数据对象的完整性、正确性与一致性。n可将所有的读进程看成是一类的，但写进程必须可将所有的读进程看成是一类的，但写进程必须和任何其他的写进程和读进程类互斥。和任何其他的写进程和读进程类互斥。42n当有读进程正在访问数据对象时，读进程的个数当有读进程正在访问数据对象时，读进程的个数与互斥要求没有关系。只有当第一个读进程需要与互斥要求没有关系。只有当第一个读进程需要对数据对象访问时，才需要执行对数据对象访问时，才需要执行semWait操作，操作，以判断是否有写进程正在更新数据对象。以判断是否有写进程正在更新数据对象。n只有当最后一个读进程退出访问数据对象的临界只有当最后一个读进程退出访问数据对象的临界段时，才需要执行段时，才需要执行semSignal操作，以便拆除操作，以便拆除“路障路障”，让一个写进程进入。，让一个写进程进入。n需要设置一个跟踪正在临界段访问数据对象的读需要设置一个跟踪正在临界段访问数据对象的读进程个数的全局共享变量进程个数的全局共享变量count。由于该计数器也由于该计数器也是一个临界资源，所以诸进程对它的访问也应当是一个临界资源，所以诸进程对它的访问也应当互斥地进行，为此，还要设置另外一个互斥信号互斥地进行，为此，还要设置另外一个互斥信号灯。灯。43解决读者解决读者写者问题的算法写者问题的算法 信号灯初值：信号灯初值：mutex 为为1 wrt为为1 计数器变量：计数器变量：int count = 0 writors: while ( ) semWait(wrt); write information semSignal(wrt); 44 readers:while ( ) semWait(mutex); if( +count = 1) semWait(wrt); semSignal(mutex); Read information; semWait(mutex); if ( -count = 0 ) semSignal(wrt); semSignal(mutex);454.5 进程间的数据通信进程间的数据通信4.5.1 消息通信消息通信v 消消息息通通信信的的基基本本思思想想是是由由系系统统的的消消息息通通信信机机构构统一管理一组空闲的消息缓冲区。统一管理一组空闲的消息缓冲区。v 一一个个进进程程要要向向另另一一个个进进程程发发送送消消息息，先先要要向向系系统统申申请请一一个个缓缓冲冲区区，填填写写了了消消息息正正文文和和其其他他有有关关消消息息的的特特征征、控控制制信信息息后后，通通过过消消息息通通信信机机构构将将该该消消息送到接收其他消息队列中。息送到接收其他消息队列中。v 接接收收进进程程在在一一个个适适当当时时机机从从消消息息队队列列中中移移出出一一个消息，读取所有的信息后，再释放消息缓冲区个消息，读取所有的信息后，再释放消息缓冲区。v 一一个个消消息息缓缓冲冲区区的的数数据据结结构构中中除除了了要要包包括括消消息息的正文外，一般还要包括其他有关的控制信息。的正文外，一般还要包括其他有关的控制信息。46send_pid：发送进程标识发送进程标识type：消息类型消息类型size：消息长度消息长度next_ptr：下一个消息的指针下一个消息的指针text ： 消息正文消息正文 为了支持消息通信，在进程控制为了支持消息通信，在进程控制PCB中还要增中还要增设有关管理消息的成员，如：设有关管理消息的成员，如：hd_ptr ： 进程已收到消息的队列首指针进程已收到消息的队列首指针mutex ： 对消息队列进行操作的互斥信号灯对消息队列进行操作的互斥信号灯ssm ：接收进程和发送进程之间的同步信接收进程和发送进程之间的同步信号灯，其值表示接收进程消息队列号灯，其值表示接收进程消息队列中的消息数。中的消息数。47n发送进程在发送消息之前，先要在进程自己的内发送进程在发送消息之前，先要在进程自己的内存空间中开辟一个发送缓冲区，将消息正文及有存空间中开辟一个发送缓冲区，将消息正文及有关控制信息填入其中，再调用发送消息的系统调关控制信息填入其中，再调用发送消息的系统调用用msgsnd(sm_ptr)，其中参数其中参数sm-ptr指向进指向进程的发送缓冲区始址。程的发送缓冲区始址。n接收进程在接收消息之前，也先要在进程自己的接收进程在接收消息之前，也先要在进程自己的内存空间中开辟一个接收缓冲区，再调用接收消内存空间中开辟一个接收缓冲区，再调用接收消息的系统调用息的系统调用msgrcv(rm_ptr)，其中参数其中参数rm_ptr指向接收缓冲区始址。指向接收缓冲区始址。msgsnd和和msgrcv系统调用系统调用484.5.2 共享存储区共享存储区n共享存储区机制可以把内存中的一个区域连入多共享存储区机制可以把内存中的一个区域连入多个进程的虚地址空间，当一个进程对该地址空间个进程的虚地址空间，当一个进程对该地址空间写入数据后，另一个进程就可以从自己所连入的写入数据后，另一个进程就可以从自己所连入的虚地址空间直接读出共享存储区中的数据，就如虚地址空间直接读出共享存储区中的数据，就如同进程存取自己的私有数据一样方便。同进程存取自己的私有数据一样方便。n进程要求分配一个共享存储区时，核心先要按进进程要求分配一个共享存储区时，核心先要按进程提供的关键字值查找系统的共享存储区段表，程提供的关键字值查找系统的共享存储区段表，如已存在指定关键字的共享段，则说明该共享段如已存在指定关键字的共享段，则说明该共享段已先由其他进程创建，只要权限允许，可简单地已先由其他进程创建，只要权限允许，可简单地返回该表项的描述符。返回该表项的描述符。49共享存储区（续）共享存储区（续）n如未找到指定关键字的表项，系统就根据进程对如未找到指定关键字的表项，系统就根据进程对共享存储区的大小及存取控制权的要求，分配一共享存储区的大小及存取控制权的要求，分配一个空闲的页表区和空闲的内存块，在共享存储区个空闲的页表区和空闲的内存块，在共享存储区段表中填入共享段的关键字、大小、共享段的页段表中填入共享段的关键字、大小、共享段的页表始址及存取控制权等信息，并返回该表项的描表始址及存取控制权等信息，并返回该表项的描述符。述符。n接下来进程就可以通过该共享存储区的描述字，接下来进程就可以通过该共享存储区的描述字，将共享存储段映射到进程的虚地址空间。将共享存储段映射到进程的虚地址空间。504.5.3 管道通信管道通信n管道是一种信息流缓冲机构，它用于连接发送进管道是一种信息流缓冲机构，它用于连接发送进程和接收进程，以实现它们之间的数据通信。管程和接收进程，以实现它们之间的数据通信。管道以先入先出（道以先入先出（FIFO）的方式组织数据的传输。的方式组织数据的传输。n在发送进程和接收进程之间能传递任意大的信息，在发送进程和接收进程之间能传递任意大的信息，但在实现时所开的缓冲区太小是有限的，故当管但在实现时所开的缓冲区太小是有限的，故当管道写满时，发送进程就被阻塞，只有当接收进程道写满时，发送进程就被阻塞，只有当接收进程从管道中读出一部或全部信息后，发送进程才能从管道中读出一部或全部信息后，发送进程才能继续向管道写信息。继续向管道写信息。n反之也一样，当接收进程读空管道时，就要等待反之也一样，当接收进程读空管道时，就要等待发送进程继续将信息写入管道。发送进程继续将信息写入管道。n在在UNIX中，管道是以文件为基础，再适当考虑中，管道是以文件为基础，再适当考虑其特殊要求而实现的通信机构。其特殊要求而实现的通信机构。514.6 软中断和信号机构软中断和信号机构4.6.1 信号的产生与类型信号的产生与类型 1. 信号的概念信号的概念v UNIX提提供供了了一一组组软软中中断断信信号号，用用于于模模拟拟硬硬件件中中断断，但但它它们们的的实实现现机机制制是是不不同同的的。信信号号是是一一取取值值为为119（MAX_SIGS）的的某某个个整整数数，可可以以在在进进程程之之间间传传送送，用用于于通通知知进进程程发发生生了了某某种种异异常常事事件件，需需要要执执行事先安排好的动作。行事先安排好的动作。v进进程程在在运运行行中中的的某某几几个个时时机机要要主主动动通通过过信信号号机机制制检检查查是是否否有有信信号号到到达达，如如有有，便便中中断断正正在在执执行行的的程程序序，转入对应的事件处理程序。转入对应的事件处理程序。v处处理理完完毕毕，再再返返回回断断点点执执行行原原先先的的程程序序。信信号号处处理理过程与硬件中断处理很相似，故称为过程与硬件中断处理很相似，故称为“软中断软中断”。52 2. 信号的产生信号的产生n 在在UNIX中，中，主要主要在以下几种情况下向进程发送软中在以下几种情况下向进程发送软中断信号：断信号：1）在用户态运行时产生了各种软、硬件故障。）在用户态运行时产生了各种软、硬件故障。2）用户通过键盘按键向与该终端有关的进程发信号）用户通过键盘按键向与该终端有关的进程发信号3）进程之间通过系统调用）进程之间通过系统调用kill传送信号。传送信号。n信号机构将发给进程的信号存放在该进程信号机构将发给进程的信号存放在该进程proc结构的结构的p_sig项。进程收到信号后并不立即进行处理，只有项。进程收到信号后并不立即进行处理，只有当进程从核心态即将返回到用户态时，即系统调用、当进程从核心态即将返回到用户态时，即系统调用、陷入或中断返回时才检查陷入或中断返回时才检查p_sig项，并处理与信号对项，并处理与信号对应的事件。应的事件。n如一个进程处于较低优先级的睡眠状态，那么系统将如一个进程处于较低优先级的睡眠状态，那么系统将唤醒该进程，使其转入就绪状态，并在被调度程序选唤醒该进程，使其转入就绪状态，并在被调度程序选中，转入执行状态时执行信号处理程序。中，转入执行状态时执行信号处理程序。53 3. 信号的类型信号的类型0 没有收到信号没有收到信号1 SIGHUP 终止进程终止进程 终端线挂断终端线挂断2 SIGINT 终止进程终止进程 在键盘上击在键盘上击“ DELETE”键键7 SIGFPE 产生产生core 浮点溢出浮点溢出9 SIGKILL 终止进程终止进程 无条件终止进程无条件终止进程11 SIGSEGV 产生产生core 段违例段违例14 SIGALARM 终止进程终止进程 闹钟闹钟15 SIGTERM 终止进程终止进程 软件终止软件终止16 SIGUSR1 终止进程终止进程 用户自定义用户自定义17 SIGUSR2 终止进程终止进程 用户自定义用户自定义19 SIGPWR 终止进程终止进程 电源故障电源故障544.6.2 信号的处理方式及设置信号的处理方式及设置 1. 信号的处理方式信号的处理方式每一个进程的每一个进程的user结构中有一个长度为结构中有一个长度为NSIG（20）的数组的数组signalNSIG，以信号类型作为该数组的下以信号类型作为该数组的下标索引，元素的值决定了对应信号的处理方式。信标索引，元素的值决定了对应信号的处理方式。信号的处理方式有三类号的处理方式有三类 （1）若数组元素值为）若数组元素值为0，则执行信号机构定义的，则执行信号机构定义的缺省动作。缺省动作。 （2）若数组元素值为）若数组元素值为1（或奇数），则忽略该信（或奇数），则忽略该信号，不执行任何动作。号，不执行任何动作。 （3）若数组元素值为）若数组元素值为偶数偶数（函数入口地址），则（函数入口地址），则作为对应信号处理程序的指针。作为对应信号处理程序的指针。55 2. 信号处理方式的设置信号处理方式的设置n一个进程在创建时，继承了父进程所有的信号处理方式，也一个进程在创建时，继承了父进程所有的信号处理方式，也即其即其signalNSIG各元素的值与父进程完全相同。但此后各元素的值与父进程完全相同。但此后除了除了SIGKIL外，信号表中定义的信号处理方式都可以用系外，信号表中定义的信号处理方式都可以用系统调用统调用signal（sig，func）设置或修改。设置的方法是：设置或修改。设置的方法是： int sig； int func（），（），（*oldptr）（）；）（）； : oldptr = signal（sig，func）；）； :n其中其中sig为信号类型，取值范围为为信号类型，取值范围为119，但不包括，但不包括9（SIGKIL），），func为新的信号处理函数，为新的信号处理函数，oldptr为函数为函数指针，用于保存系统调用指针，用于保存系统调用signal返回的信号返回的信号sig原先处理函原先处理函数入口地址，以便有必要时可恢复原先的信号处理方式。数入口地址，以便有必要时可恢复原先的信号处理方式。56:p_sig ：a:&newfunc:(oldptr)( ):newfunc( ):0 aoldptrprocu.u-signal进程进程Pa的图像的图像图图4-9信号处理方式的设置信号处理方式的设置574.6.3 信号的传送信号的传送n利用信号实施进程间通信的主要方式是使用系统调利用信号实施进程间通信的主要方式是使用系统调用用kill（pid，sig），其功能是将信号其功能是将信号sig传送给由传送给由参数参数pid限定的进程。当：限定的进程。当：n pid为为正值正值时，对应于一个有效的进程标识数，时，对应于一个有效的进程标识数，该信号就发送给这个唯一的进程。该信号就发送给这个唯一的进程。n pid为为0时，将信号发送给受同一终端控制的所有时，将信号发送给受同一终端控制的所有进程。进程。n pid为为-1时，将信号发送给与发送进程用户标识时，将信号发送给与发送进程用户标识数相同的所有进程。数相同的所有进程。n pid -1时，将信号发送给组标识数为时，将信号发送给组标识数为pid的绝的绝对值的所有进程。对值的所有进程。n下面举一个信号机构方法的例子。下面举一个信号机构方法的例子。58# include # include main ( )int status；pid_t pid；void func ( )；signal (SIGUSR1,func)；1 /* 预置信号处理程序预置信号处理程序 */if (pid=fork () ) 2 printf (Parent: will send signal.n)；4 kill (pid, SIGUSR1)； 5/* 发送信号发送信号 */ wait (& status)； 6/* 等待子进程停止等待子进程停止 */ printf (status=%d: Parent finish:n，status)；10 else sleep (10)； 3/* 等待接受信号等待接受信号 */ printf (Child：signal is received.n)；8 exit (0)； 9 59void func () printf (It is signal processing function.n)； 7 在程序的开始部分用系统调用设置信号在程序的开始部分用系统调用设置信号16的处理的处理方式为执行方式为执行func程序，在父进程用程序，在父进程用fork创建子进程创建子进程后，子进程继承了对信号的处理方式。父进程向后，子进程继承了对信号的处理方式。父进程向子进程发送信号后，如子进程处于低优先权睡眠，子进程发送信号后，如子进程处于低优先权睡眠，则将其唤醒。子进程被唤醒后，检查是否收到信则将其唤醒。子进程被唤醒后，检查是否收到信号，发现已收到信号，就执行该信号号，发现已收到信号，就执行该信号（SIGUSR1）所对应的处理程序所对应的处理程序func（）。（）。执行执行完毕后返回，继续执行余下程序段。完毕后返回，继续执行余下程序段。60Solaris的进程通信机制的进程通信机制nSPARC处理机为互斥原语实现了有原子性处理机为互斥原语实现了有原子性test-and-set语义的内存访问指令。如语义的内存访问指令。如cas（compare and swap，比较和交换）指令，比较和交换）指令，如果第一个寄存器与内存单元的内容相同，则交如果第一个寄存器与内存单元的内容相同，则交换内存单元和第二个寄存器的内容。换内存单元和第二个寄存器的内容。n锁以几种不同的形式出现。锁以几种不同的形式出现。Solaris内核中最常内核中最常用的是互斥锁，它可以实现对数据的互斥读写访用的是互斥锁，它可以实现对数据的互斥读写访问。此外还有读问。此外还有读/写锁，它适用于在同一时刻对写锁，它适用于在同一时刻对同一数据可以有多个读操作，但只能有一个写操同一数据可以有多个读操作，但只能有一个写操作的情况。作的情况。n在内核的一些部分，如果获取最佳性能是要追求在内核的一些部分，如果获取最佳性能是要追求的首要目标，为了提高速度，许多锁代码用汇编的首要目标，为了提高速度，许多锁代码用汇编语言实现，而不是语言实现，而不是C语言。语言。 61nSolaris支持支持System V的三种的三种IPC机制（共享机制（共享内存、信号量和消息队列），还支持基于套接内存、信号量和消息队列），还支持基于套接字的进程间通信机制。同时，字的进程间通信机制。同时，Solaris引入了引入了自己独特的自己独特的IPC机制机制Solaris门。门。nSolaris门是一种快速的进程间过程调用，这种门是一种快速的进程间过程调用，这种类似于远程过程调用的机制允许我们快速地调类似于远程过程调用的机制允许我们快速地调用其他进程中的方法。用其他进程中的方法。n一个进程可以通过创建门而成为门服务器，门一个进程可以通过创建门而成为门服务器，门是一个函数，在服务器中以线程的形式存在，是一个函数，在服务器中以线程的形式存在，其他的客户端进程可以调用门。其他的客户端进程可以调用门。Solaris门门62nSolaris门服务器会在线程池中创建一个内核线程以等待门服务器会在线程池中创建一个内核线程以等待客户端的调用，只要门线程池中还有空闲的线程，客户端客户端的调用，只要门线程池中还有空闲的线程，客户端就能马上得到服务，这就使得门函数的调用非常快速。就能马上得到服务，这就使得门函数的调用非常快速。n服务器进程成功创建门时，返回一个门的描述符。门服务服务器进程成功创建门时，返回一个门的描述符。门服务器进程通过创建一个门器进程通过创建一个门(door_create()来使得该进程中来使得该进程中的一个函数可以被客户端的进程所使用。的一个函数可以被客户端的进程所使用。n内核中将门实现为一个伪文件系统内核中将门实现为一个伪文件系统doorfs。进程通过门描。进程通过门描述符来引用门，门描述符在形式和功能上都与文件描述符述符来引用门，门描述符在形式和功能上都与文件描述符相似。服务器必须将创建的门和一个文件系统名字空间的相似。服务器必须将创建的门和一个文件系统名字空间的文伴描述符相关联，服务器端是通过调用文伴描述符相关联，服务器端是通过调用fattach()来将来将一个文件系统路径名和门文件描述符相关联的。一个文件系统路径名和门文件描述符相关联的。 n一旦关联充成，客户端就可以对该路径名进行打开操作，一旦关联充成，客户端就可以对该路径名进行打开操作，并且在并且在door_call()使用打开操作返回的文件捕述符来得使用打开操作返回的文件捕述符来得到一个门的描述符，客户端通过门描述符来找到一个门。到一个门的描述符，客户端通过门描述符来找到一个门。Solaris门门63Solaris中的信号处理中的信号处理nSolaris中的信号处理是进程级别的，但每个线程可以有自中的信号处理是进程级别的，但每个线程可以有自己的信号屏蔽掩码。己的信号屏蔽掩码。n线程可以独立于同一进程中执行的其他线程来选择自己要屏线程可以独立于同一进程中执行的其他线程来选择自己要屏蔽的信号，因而在进程执行的不同时刻可以有不同的线程来蔽的信号，因而在进程执行的不同时刻可以有不同的线程来接收不同的信号。接收不同的信号。n接口接口pthread_sigmask()用来建立每个线程的信号屏蔽掩用来建立每个线程的信号屏蔽掩码。进程中的所有线程共享所有信号的处理及处理例程，那码。进程中的所有线程共享所有信号的处理及处理例程，那么具有默认处理的么具有默认处理的SIGINT信号（作为例子）的产生将会使信号（作为例子）的产生将会使整个进程退出。作为异常的结果产生的同步信号（整个进程退出。作为异常的结果产生的同步信号（SIGFPE、SIGILL等）将被发送到产生异常的线程本身。等）将被发送到产生异常的线程本身。n异步信号是所有没有被定义为异常的其他信号，它们将被传异步信号是所有没有被定义为异常的其他信号，它们将被传递到系统找到的第一个不屏蔽该信号的线程。递到系统找到的第一个不屏蔽该信号的线程。n信号在数据结构中表示为二进制位，例如设置第信号在数据结构中表示为二进制位，例如设置第16位，位，SIGURS1（这实际上是位（这实际上是位15，位的编号是从，位的编号是从0开始的）开始的）。644.7 死锁死锁4.7.1 4.7.1 产生死锁的原因产生死锁的原因图图4-10 过河的相持过河的相持65当两个进程各占了对方所要的一个资源，当两个进程各占了对方所要的一个资源，就会形成死锁就会形成死锁进程进程B等待资源等待资源R1资源资源R1 进程进程B 进程进程A资源资源R2进程进程A占用资源占用资源R1进程进程A等待资源等待资源R2进程进程B占用资源占用资源R2图图4-11两个进程的死锁两个进程的死锁66n系统资源可分为两类，一类是可重复使用的系统资源可分为两类，一类是可重复使用的永久性永久性资源资源，另一类是会被消耗的，另一类是会被消耗的临时性资源临时性资源。可重复用。可重复用的资源在使用后不会减少资源。进程在释放了可重的资源在使用后不会减少资源。进程在释放了可重用资源后，该资源又可被其他进程再次使用。可重用资源后，该资源又可被其他进程再次使用。可重用的资源有处理机、主存、暂存、用的资源有处理机、主存、暂存、I/O通道、打印通道、打印机以及文件、数据库等。机以及文件、数据库等。n可重用的资源又可分为可重用的资源又可分为可剥夺的资源可剥夺的资源和和不可剥夺的不可剥夺的资源资源。最典型的可剥夺的资源是处理机。最普通的。最典型的可剥夺的资源是处理机。最普通的不可剥夺的资源是打印机，当系统把这类资源分配不可剥夺的资源是打印机，当系统把这类资源分配给进程后，只能在使用完毕后由进程自愿释放，系给进程后，只能在使用完毕后由进程自愿释放，系统不能强行收回。统不能强行收回。n涉及到可重用资源的死锁例子是：一个进程占用了涉及到可重用资源的死锁例子是：一个进程占用了打印机，又要申请磁带机，另一个进程占用了磁带打印机，又要申请磁带机，另一个进程占用了磁带机，又要申请打印机，这样每个进程都占用并保持机，又要申请打印机，这样每个进程都占用并保持了一个资源，并等待对方所占用的资源时就发生了了一个资源，并等待对方所占用的资源时就发生了死锁。死锁。674.7.2 产生死锁的条件产生死锁的条件 同时具备下列三个静态的必要条件时，才有可能产生死同时具备下列三个静态的必要条件时，才有可能产生死锁。锁。 (1) 互斥执行互斥执行 每次只能允许一个进程占有和使用一个每次只能允许一个进程占有和使用一个资源，其他申请该资源的进程被阻塞。资源，其他申请该资源的进程被阻塞。(2) 保持并等待保持并等待 当进程等待分配给它新的资源时，保当进程等待分配给它新的资源时，保持占有已分配的资源。持占有已分配的资源。(3) 不可剥夺不可剥夺 不能强迫移去进程占有的未使用完的资不能强迫移去进程占有的未使用完的资源。源。 上述这三个条件是产生死锁的必要条件，但即使存在全上述这三个条件是产生死锁的必要条件，但即使存在全部这三个条件也不一定会发生死锁。要产生死锁必须存在部这三个条件也不一定会发生死锁。要产生死锁必须存在第四个动态条件：第四个动态条件：(4) 循环等待循环等待 存在一个闭合的进程存在一个闭合的进程资源链，以致资源链，以致每一个进程至少占有链中下一个进程所需要的一个资源。每一个进程至少占有链中下一个进程所需要的一个资源。684.7.3 死锁的预防死锁的预防 1互斥执行互斥执行 一般说，第一个条件是不能排除的，如果存取一般说，第一个条件是不能排除的，如果存取一个资源需要互斥执行，那么操作系统就要支一个资源需要互斥执行，那么操作系统就要支持互斥执行。某些资源，例如文件，可以允许持互斥执行。某些资源，例如文件，可以允许多个用户同时读，但对写只能互斥地进行。就多个用户同时读，但对写只能互斥地进行。就是在这个情况，如果一个以上的进程需要进行是在这个情况，如果一个以上的进程需要进行写操作，就可能发生死锁。写操作，就可能发生死锁。 2保持和等待保持和等待 保持和等待条件是能预防的，只要进程一次申保持和等待条件是能预防的，只要进程一次申请它所需要的所有的资源，在所有的需要同时请它所需要的所有的资源，在所有的需要同时满足以前，阻塞自己。满足以前，阻塞自己。69v 有几种方法可预防这个条件。一个方法是，如占有几种方法可预防这个条件。一个方法是，如占有某些资源的进程不能获得进一步的资源，该进程有某些资源的进程不能获得进一步的资源，该进程必须释放原先所占有的资源；如果需要，以后再申必须释放原先所占有的资源；如果需要，以后再申请这些资源。请这些资源。v 另外的方法是，如果一个进程需要申请当前正被另外的方法是，如果一个进程需要申请当前正被其他进程占用的资源，操作系统就要求后者释放它其他进程占用的资源，操作系统就要求后者释放它所占用的这类资源。这种预防死锁的方法只能用在所占用的这类资源。这种预防死锁的方法只能用在后申请资源的进程优先级较高的情况下。后申请资源的进程优先级较高的情况下。v 只有当资源的状态容易保存和便于以后恢复的情只有当资源的状态容易保存和便于以后恢复的情况下，这种方法才是实际可行的。处理机就是这类况下，这种方法才是实际可行的。处理机就是这类资源的例子，如剥夺像打印机那样的资源，就会使资源的例子，如剥夺像打印机那样的资源，就会使输出变得杂乱无章、毫无意义。但借助输出变得杂乱无章、毫无意义。但借助spooling技技术可将独享设备改为虚拟的共享设备，就能破坏本术可将独享设备改为虚拟的共享设备，就能破坏本条件，预防死锁。条件，预防死锁。 3不可剥夺不可剥夺70 4循环等待循环等待采用有序资源使用法可以防止循环等待条件。采用有序资源使用法可以防止循环等待条件。如果一个进程已经分配了类型如果一个进程已经分配了类型R的资源，那么以的资源，那么以后它只能申请在资源顺序表中排在后它只能申请在资源顺序表中排在R后面的资源后面的资源类型。类型。12345数数模模转转换换器器磁磁带带机机打打印印机机光光刻刻机机绘绘图图仪仪71五个哲学家吃通心面五个哲学家吃通心面P1: 思考思考 semWait(f1) 取取 f1 semWait (f2) 取取 f2 吃通心面吃通心面 放下放下f1,f2 semSignal(f1) semSignal(f2)p1f1f2p2f3f4f5p3p4p5P5: 思考思考 semWait (f5) 取取 f5 semWait (f1) 取取 f1 吃通心面吃通心面 放下放下f5,f1 semSignal (f5) semSignal (f1).72五个哲学家吃通心面五个哲学家吃通心面P1: 思考思考 semWait(f1) 取取 f1 semWait (f2) 取取 f2 吃通心面吃通心面 放下放下f1,f2 semSignal(f1) semSignal(f2)p1f1f2p2f3f4f5p3p4p5P5: 思考思考 semWait (f1) 取取 f5 semWait (f5) 取取 f1 吃通心面吃通心面 放下放下f5,f1 semSignal (f5) semSignal (f1).734.7.4 死锁的避免死锁的避免死锁避免的方法允许三个死锁的必要条件都存死锁避免的方法允许三个死锁的必要条件都存在，但要动态地进行审慎的判断，以保证运行不在，但要动态地进行审慎的判断，以保证运行不会到达死锁这一点上。避免死锁主要有以下两个会到达死锁这一点上。避免死锁主要有以下两个判断和处理时机：判断和处理时机：(1) 进程启动时判断进程启动时判断 如果对资源的要求会导如果对资源的要求会导致死锁，就不启动有关进程。这种方法仅仅在当致死锁，就不启动有关进程。这种方法仅仅在当前所有进程对资源的最大请求加上启动进程对资前所有进程对资源的最大请求加上启动进程对资源的请求都满足的情况下，才能启动新进程，故源的请求都满足的情况下，才能启动新进程，故这种避免死锁的策略不会是最优的，因为它假定这种避免死锁的策略不会是最优的，因为它假定的是最坏情况，即所有进程都同时需要最大数量的是最坏情况，即所有进程都同时需要最大数量的资源。的资源。(2) 资源分配时判断资源分配时判断 如果对资源的分配会导如果对资源的分配会导致死锁，就暂不允许进一步为进程分配资源。致死锁，就暂不允许进一步为进程分配资源。74n分配资源时，申请者要把同类资源的最大需求量分配资源时，申请者要把同类资源的最大需求量告诉系统，如系统现存的可用资源数能满足申请告诉系统，如系统现存的可用资源数能满足申请者剩余需求量时，就满足当前的部分或全部申请，者剩余需求量时，就满足当前的部分或全部申请，否则就推迟分配。否则就推迟分配。n这样至少保证有一个申请者能得到所需的全部资这样至少保证有一个申请者能得到所需的全部资源，可执行到结束，然后释放资源供别的申请者源，可执行到结束，然后释放资源供别的申请者使用。使用。n如果系统保证申请者在有限的时间内能获得所需如果系统保证申请者在有限的时间内能获得所需的全部资源，则称系统处于的全部资源，则称系统处于安全状态安全状态，否则称系，否则称系统处于统处于不安全状态不安全状态，并有可能引起死锁。银行家，并有可能引起死锁。银行家算法是在能确保系统处于安全状态时才把资源分算法是在能确保系统处于安全状态时才把资源分配给申请者。配给申请者。银行家算法银行家算法75例例: 有有8个资源供三个进程共享，它们的最大需个资源供三个进程共享，它们的最大需求数分别为求数分别为6、4、7。在某一时刻，资源的分配情。在某一时刻，资源的分配情况如下所示：况如下所示： 最大需求最大需求 当前占有当前占有 还要申请还要申请P0624P1422P2716系统剩余数系统剩余数3这时，系统处于安全状态，因为剩余的资源可这时，系统处于安全状态，因为剩余的资源可以先供进程以先供进程P1使用，使用，P1运行结束后将释放所占全运行结束后将释放所占全部资源，这样系统剩余资源数变为部资源，这样系统剩余资源数变为5，又可保证，又可保证P0的全部申请得到满足。等到的全部申请得到满足。等到P0归还所占资源后，归还所占资源后，就可满足就可满足P2的申请。如此系统存在着一个安全的的申请。如此系统存在着一个安全的资源分配序列。资源分配序列。76但在上述的状态中，如果但在上述的状态中，如果P0要申请要申请2个（而不是个（而不是1个）资源，系统就不能立即分配给它，而要推迟个）资源，系统就不能立即分配给它，而要推迟到一个适当的时机再实施分配过程，否则系统资到一个适当的时机再实施分配过程，否则系统资源的分配情况将变为：源的分配情况将变为：最大需求最大需求当前占有当前占有还要申请还要申请P0642P1422P2716系统剩余数系统剩余数1 这种状态是不安全的，因为剩余的资源数已不这种状态是不安全的，因为剩余的资源数已不能满足任何一个进程还要申请的资源数，如此就能满足任何一个进程还要申请的资源数，如此就可能形成死锁。可能形成死锁。774.7.5 死锁的检测死锁的检测n死锁的预防策略是非常保守的，它是靠限死锁的预防策略是非常保守的，它是靠限制对资源的存取及进程的并发执行程度来制对资源的存取及进程的并发执行程度来实施的。实施的。n与其相反，死锁检测策略不减少对资源的与其相反，死锁检测策略不减少对资源的存取或限制进程的并发运行。使用死锁检存取或限制进程的并发运行。使用死锁检测，只要可能，就将所申请的资源分配给测，只要可能，就将所申请的资源分配给进程。操作系统定期地执行检查算法，以进程。操作系统定期地执行检查算法，以判断是否存在条件判断是否存在条件4的循环等待链。的循环等待链。78占用资源号占用资源号进程号进程号 1 1 2 2 3 4 4 3进程号进程号等待资源号等待资源号 1 2 2 4 3 1 4 2资源分配表资源分配表资源等待表资源等待表s2s3s1s4p1p3p2p4等待资源等待资源占用占用资源资源状态图和状态表状态图和状态表794.7.6 死锁的解除死锁的解除n下面列举了一些解除死锁的方法。下面列举了一些解除死锁的方法。n强迫撤销所有的死锁进程。强迫撤销所有的死锁进程。n将每一个死锁进程退回到一些以前定义的将每一个死锁进程退回到一些以前定义的“检查检查站站”，再启动进程。这需要系统支持进程的回退，再启动进程。这需要系统支持进程的回退和重启动机制。和重启动机制。n逐个撤销死锁进程，直至死锁不存在。终止死锁逐个撤销死锁进程，直至死锁不存在。终止死锁进程的次序应当基于最小代价的标准。每终止一进程的次序应当基于最小代价的标准。每终止一个进程后就调用死锁检测算法，以判定死锁是否个进程后就调用死锁检测算法，以判定死锁是否还存在。还存在。n相继地剥夺进程所占的资源，直至死锁不再存在。相继地剥夺进程所占的资源，直至死锁不再存在。同样，剥夺资源的次序应基于成本方面的考虑。同样，剥夺资源的次序应基于成本方面的考虑。被剥夺资源的进程必需回退到获得该资源之前的被剥夺资源的进程必需回退到获得该资源之前的某个执行点上。某个执行点上。804.9 Solaris的进程通信机制的进程通信机制nSPARC处理机为互斥原语实现了有原子性处理机为互斥原语实现了有原子性test-and-set语义的内存访问指令。如语义的内存访问指令。如cas（compare and swap，比较和交换）指令，比较和交换）指令，如果第一个寄存器与内存单元的内容相同，则交如果第一个寄存器与内存单元的内容相同，则交换内存单元和第二个寄存器的内容。换内存单元和第二个寄存器的内容。n锁以几种不同的形式出现。锁以几种不同的形式出现。Solaris内核中最常内核中最常用的是互斥锁，它可以实现对数据的互斥读写访用的是互斥锁，它可以实现对数据的互斥读写访问。此外还有读问。此外还有读/写锁，它适用于在同一时刻对写锁，它适用于在同一时刻对同一数据可以有多个读操作，但只能有一个写操同一数据可以有多个读操作，但只能有一个写操作的情况。作的情况。n在内核的一些部分，如果获取最佳性能是要追求在内核的一些部分，如果获取最佳性能是要追求的首要目标，为了提高速度，许多锁代码用汇编的首要目标，为了提高速度，许多锁代码用汇编语言实现，而不是语言实现，而不是C语言。语言。n 814.9.2 Solaris中的信号处理中的信号处理nSolaris中的信号处理是进程级别的，但每个线程可以有自中的信号处理是进程级别的，但每个线程可以有自己的信号屏蔽掩码。己的信号屏蔽掩码。n线程可以独立于同一进程中执行的其他线程来选择自己要屏线程可以独立于同一进程中执行的其他线程来选择自己要屏蔽的信号，因而在进程执行的不同时刻可以有不同的线程来蔽的信号，因而在进程执行的不同时刻可以有不同的线程来接收不同的信号。接收不同的信号。n接口接口pthread_sigmask()用来建立每个线程的信号屏蔽掩用来建立每个线程的信号屏蔽掩码。进程中的所有线程共享所有信号的处理及处理例程，那码。进程中的所有线程共享所有信号的处理及处理例程，那么具有默认处理的么具有默认处理的SIGINT信号（作为例子）的产生将会使信号（作为例子）的产生将会使整个进程退出。作为异常的结果产生的同步信号（整个进程退出。作为异常的结果产生的同步信号（SIGFPE、SIGILL等）将被发送到产生异常的线程本身。等）将被发送到产生异常的线程本身。n异步信号是所有没有被定义为异常的其他信号，它们将被传异步信号是所有没有被定义为异常的其他信号，它们将被传递到系统找到的第一个不屏蔽该信号的线程。递到系统找到的第一个不屏蔽该信号的线程。n信号在数据结构中表示为二进制位，例如设置第信号在数据结构中表示为二进制位，例如设置第16位，位，SIGURS1（这实际上是位（这实际上是位15，位的编号是从，位的编号是从0开始的）开始的）。82nSolaris支持支持System V的三种的三种IPC机制（共享机制（共享内存、信号量和消息队列），还支持基于套接内存、信号量和消息队列），还支持基于套接字的进程间通信机制。同时，字的进程间通信机制。同时，Solaris引入了引入了自己独特的自己独特的IPC机制机制Solaris门。门。nSolaris门是一种快速的进程间过程调用，这种门是一种快速的进程间过程调用，这种类似于远程过程调用的机制允许我们快速地调类似于远程过程调用的机制允许我们快速地调用其他进程中的方法。用其他进程中的方法。n一个进程可以通过创建门而成为门服务器，门一个进程可以通过创建门而成为门服务器，门是一个函数，在服务器中以线程的形式存在，是一个函数，在服务器中以线程的形式存在，其他的客户端进程可以调用门。其他的客户端进程可以调用门。4.9.4 Solaris门门83nSolaris门服务器会在线程池中创建一个内核线程以等待门服务器会在线程池中创建一个内核线程以等待客户端的调用，只要门线程池中还有空闲的线程，客户端客户端的调用，只要门线程池中还有空闲的线程，客户端就能马上得到服务，这就使得门函数的调用非常快速。就能马上得到服务，这就使得门函数的调用非常快速。n服务器进程成功创建门时，返回一个门的描述符。门服务服务器进程成功创建门时，返回一个门的描述符。门服务器进程通过创建一个门器进程通过创建一个门(door_create()来使得该进程中来使得该进程中的一个函数可以被客户端的进程所使用。的一个函数可以被客户端的进程所使用。n内核中将门实现为一个伪文件系统内核中将门实现为一个伪文件系统doorfs。进程通过门描。进程通过门描述符来引用门，门描述符在形式和功能上都与文件描述符述符来引用门，门描述符在形式和功能上都与文件描述符相似。服务器必须将创建的门和一个文件系统名字空间的相似。服务器必须将创建的门和一个文件系统名字空间的文伴描述符相关联，服务器端是通过调用文伴描述符相关联，服务器端是通过调用fattach()来将来将一个文件系统路径名和门文件描述符相关联的。一个文件系统路径名和门文件描述符相关联的。 n一旦关联充成，客户端就可以对该路径名进行打开操作，一旦关联充成，客户端就可以对该路径名进行打开操作，并且在并且在door_call()使用打开操作返回的文件捕述符来得使用打开操作返回的文件捕述符来得到一个门的描述符，客户端通过门描述符来找到一个门。到一个门的描述符，客户端通过门描述符来找到一个门。Solaris门门84思考题：思考题：为什么为什么Windows和和Unix等实际操作系等实际操作系统在设计中不采取课程教学中讲过的各统在设计中不采取课程教学中讲过的各种死锁解决方法，而任系统发生死锁呢种死锁解决方法，而任系统发生死锁呢85谢谢各位谢谢各位