os-03进程_进程同步互斥与通信、死锁.ppt

《os-03进程_进程同步互斥与通信、死锁.ppt》由会员分享，可在线阅读，更多相关《os-03进程_进程同步互斥与通信、死锁.ppt（174页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、OS-03进程管理_进程同步互斥与通信、死锁 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望3.6 进程同步与同步进程同步与同步操作系统设计中的核心问题是关于进程和线程的管操作系统设计中的核心问题是关于进程和线程的管操作系统设计中的核心问题是关于进程和线程的管操作系统设计中的核心问题是关于进程和线程的管理理理理 多道程序技术多道程序技术多道程序技术多道程序技术 管理单处理器系统中的多个进程管理单处理器系统中的多个进程管理单处理器系统中的多个进程管理单处理器系统中的

2、多个进程 多处理技术多处理技术多处理技术多处理技术管理多处理器系统中的多个进程管理多处理器系统中的多个进程管理多处理器系统中的多个进程管理多处理器系统中的多个进程 分布处理技术分布处理技术分布处理技术分布处理技术 管理多台分布式计算机系统管理多台分布式计算机系统管理多台分布式计算机系统管理多台分布式计算机系统(集群集群集群集群)中多中多中多中多个进程的执行个进程的执行个进程的执行个进程的执行并发程序并发程序并发是所有问题的基础，也是操作系统设计的基础。并发是所有问题的基础，也是操作系统设计的基础。并发是所有问题的基础，也是操作系统设计的基础。并发是所有问题的基础，也是操作系统设计的基础。它包括

3、很多设计问题它包括很多设计问题它包括很多设计问题它包括很多设计问题 分配给进程的处理器时间等分配给进程的处理器时间等分配给进程的处理器时间等分配给进程的处理器时间等 资源的共享与争用资源的共享与争用资源的共享与争用资源的共享与争用 进程间的通信进程间的通信进程间的通信进程间的通信 多个进程活动的同步多个进程活动的同步多个进程活动的同步多个进程活动的同步并发程序并发程序程序并发可以通过创建进程或线程实现程序并发可以通过创建进程或线程实现程序并发可以通过创建进程或线程实现程序并发可以通过创建进程或线程实现Windows 2000Windows 2000并发程序设计并发程序设计并发程序设计并发程序设

4、计 例子例子例子例子3 37.7.cppcppUnixUnix下的并发程序设计下的并发程序设计下的并发程序设计下的并发程序设计 通过通过通过通过fork()fork()创建子进程创建子进程创建子进程创建子进程 例：例：例：例：a+b=ca+b=cLinuxLinux下的并发程序设计下的并发程序设计下的并发程序设计下的并发程序设计 实验实验实验实验4.34.3 Void main()Void main()Pid=fork();Pid=fork();If pid=0 then If pid=0 then begin begin read(b);read(b);exit(0);exit(0);end

5、;end;Else Else read(a);read(a);Return_pid=wait(&status);Return_pid=wait(&status);c=a+b;c=a+b;Write(c);Write(c);3.6 进程同步与同步进程同步与同步进程并发要解决的主要问题进程并发要解决的主要问题进程并发要解决的主要问题进程并发要解决的主要问题 互斥互斥互斥互斥：支持并发进程的基本需求是实现互斥的能力，即，支持并发进程的基本需求是实现互斥的能力，即，支持并发进程的基本需求是实现互斥的能力，即，支持并发进程的基本需求是实现互斥的能力，即，当一个进程被授予一资源时，在其活动期间，它具有排当

6、一个进程被授予一资源时，在其活动期间，它具有排当一个进程被授予一资源时，在其活动期间，它具有排当一个进程被授予一资源时，在其活动期间，它具有排斥所有其他进程使用该资源的能力斥所有其他进程使用该资源的能力斥所有其他进程使用该资源的能力斥所有其他进程使用该资源的能力并发的基本需求并发的基本需求并发的基本需求并发的基本需求 实现互斥包括软件方法实现互斥包括软件方法实现互斥包括软件方法实现互斥包括软件方法(“(“忙等待忙等待忙等待忙等待”技术技术技术技术)和支持互斥的和支持互斥的和支持互斥的和支持互斥的硬件机制等硬件机制等硬件机制等硬件机制等 同步同步同步同步：进程间的活动有相互依赖和合作的关系：进程

7、间的活动有相互依赖和合作的关系：进程间的活动有相互依赖和合作的关系：进程间的活动有相互依赖和合作的关系 通信通信通信通信：信号量、管程、消息：信号量、管程、消息：信号量、管程、消息：信号量、管程、消息实现同步、互斥的三方法实现同步、互斥的三方法实现同步、互斥的三方法实现同步、互斥的三方法3.6 进程同步与同步进程同步与同步并发的例子及并发后的问题并发的例子及并发后的问题并发的例子及并发后的问题并发的例子及并发后的问题 并发并发并发并发 在同一时间段内，多个进程同时运行；宏观上并在同一时间段内，多个进程同时运行；宏观上并在同一时间段内，多个进程同时运行；宏观上并在同一时间段内，多个进程同时运行；

8、宏观上并发，微观上顺序执行。发，微观上顺序执行。发，微观上顺序执行。发，微观上顺序执行。并发后产生了并发后产生了并发后产生了并发后产生了资源的竞争和共享资源的竞争和共享资源的竞争和共享资源的竞争和共享问题，而且进程问题，而且进程问题，而且进程问题，而且进程的执行速度及进程的执行序列都是不可预测的的执行速度及进程的执行序列都是不可预测的的执行速度及进程的执行序列都是不可预测的的执行速度及进程的执行序列都是不可预测的 一个例子一个例子一个例子一个例子3.6 进程同步与同步进程同步与同步考虑下面一个字符回显的的过程考虑下面一个字符回显的的过程考虑下面一个字符回显的的过程考虑下面一个字符回显的的过程

9、void echo()void echo()chin=getchar();chin=getchar();chout=chin;chout=chin;putchar(chout);putchar(chout);从键盘获得输入，每击一下键，输入字符就保存在变量从键盘获得输入，每击一下键，输入字符就保存在变量从键盘获得输入，每击一下键，输入字符就保存在变量从键盘获得输入，每击一下键，输入字符就保存在变量chinchin中，然后传送给变量中，然后传送给变量中，然后传送给变量中，然后传送给变量choutchout，并回送显示器，并回送显示器，并回送显示器，并回送显示器任何程序可以重复地调用此过程，接收用

10、户输入，并在用户任何程序可以重复地调用此过程，接收用户输入，并在用户任何程序可以重复地调用此过程，接收用户输入，并在用户任何程序可以重复地调用此过程，接收用户输入，并在用户的屏幕上显示的屏幕上显示的屏幕上显示的屏幕上显示3.6 进程同步与同步进程同步与同步考虑一个支持单用户单处理器、多道程序设计系统考虑一个支持单用户单处理器、多道程序设计系统考虑一个支持单用户单处理器、多道程序设计系统考虑一个支持单用户单处理器、多道程序设计系统将其当作一个共享过程，载入到所有应用程序公将其当作一个共享过程，载入到所有应用程序公将其当作一个共享过程，载入到所有应用程序公将其当作一个共享过程，载入到所有应用程序公

11、用的全局存储区中。这样每个应用程序都能使用用的全局存储区中。这样每个应用程序都能使用用的全局存储区中。这样每个应用程序都能使用用的全局存储区中。这样每个应用程序都能使用这个过程，由于每个应用程序只需使用这个过程，由于每个应用程序只需使用这个过程，由于每个应用程序只需使用这个过程，由于每个应用程序只需使用echoechoechoecho过程过程过程过程的一个副本，从而节省空间的一个副本，从而节省空间的一个副本，从而节省空间的一个副本，从而节省空间进程间共享主存是非常有用的，它允许进程间有效而紧进程间共享主存是非常有用的，它允许进程间有效而紧进程间共享主存是非常有用的，它允许进程间有效而紧进程间共

12、享主存是非常有用的，它允许进程间有效而紧密的交互，有利于进程的相互通信。但是，共享也可能密的交互，有利于进程的相互通信。但是，共享也可能密的交互，有利于进程的相互通信。但是，共享也可能密的交互，有利于进程的相互通信。但是，共享也可能会带来一些问题会带来一些问题会带来一些问题会带来一些问题 void echo()void echo()chin=getchar();chin=getchar();chout=chin;chout=chin;putchar(chout);putchar(chout);3.6 进程同步与同步进程同步与同步考虑下面的顺序考虑下面的顺序考虑下面的顺序考虑下面的顺序 进程进程

13、进程进程P1P1调用调用调用调用echoecho过程，并在过程，并在过程，并在过程，并在getchargetchar函数结束后立即被中函数结束后立即被中函数结束后立即被中函数结束后立即被中断，此时，最近输入的字符断，此时，最近输入的字符断，此时，最近输入的字符断，此时，最近输入的字符x x被保存在变量被保存在变量被保存在变量被保存在变量 chinchin中中中中 进程进程进程进程P2P2被激活并调用被激活并调用被激活并调用被激活并调用echoecho过程，过程，过程，过程，echoecho过程运行得出结果，过程运行得出结果，过程运行得出结果，过程运行得出结果，输入然后在屏幕上显示单个的字符输入

14、然后在屏幕上显示单个的字符输入然后在屏幕上显示单个的字符输入然后在屏幕上显示单个的字符 y y 进程进程进程进程P1P1被恢复。此时被恢复。此时被恢复。此时被恢复。此时chinchin中值中值中值中值x x被写覆盖，因此已丢失，被写覆盖，因此已丢失，被写覆盖，因此已丢失，被写覆盖，因此已丢失，而而而而chinchin中的值中的值中的值中的值y y被传送给被传送给被传送给被传送给choutchout并显示出来并显示出来并显示出来并显示出来 第一个字符丢失，第第一个字符丢失，第第一个字符丢失，第第一个字符丢失，第2 2个字符被显示了两次个字符被显示了两次个字符被显示了两次个字符被显示了两次 voi

15、d echo()void echo()chin=getchar();chin=getchar();chout=chin;chout=chin;putchar(chout);putchar(chout);getchargetchar（）（）（）（）chinchinchoutchout putcharputchar（）（）（）（）P1P2getchargetchar（）（）（）（）XXgetchargetchar（）（）（）（）YYYputcharputchar（）（）（）（）YYY？echoecho3.6 进程同步与同步进程同步与同步解决方案：解决方案：解决方案：解决方案：一次只允许一个进程调用

16、一次只允许一个进程调用一次只允许一个进程调用一次只允许一个进程调用echoecho过程：过程：过程：过程：进程进程进程进程P1P1P1P1调用调用调用调用echoechoechoecho过程，并在过程，并在过程，并在过程，并在getchargetchargetchargetchar函数结束后立即被中断，函数结束后立即被中断，函数结束后立即被中断，函数结束后立即被中断，此时，最近输入的字符此时，最近输入的字符此时，最近输入的字符此时，最近输入的字符x x x x被保存在变量被保存在变量被保存在变量被保存在变量chinchinchinchin中中中中 进程进程进程进程P2P2P2P2被激活并调用被

17、激活并调用被激活并调用被激活并调用echoechoechoecho过程。但是，由于过程。但是，由于过程。但是，由于过程。但是，由于P1P1P1P1仍然在仍然在仍然在仍然在echoechoechoecho过程中，尽管当前过程中，尽管当前过程中，尽管当前过程中，尽管当前P1P1P1P1处于就绪状态，处于就绪状态，处于就绪状态，处于就绪状态，P2P2P2P2仍被阻塞，不能进仍被阻塞，不能进仍被阻塞，不能进仍被阻塞，不能进入这个过程。因此，入这个过程。因此，入这个过程。因此，入这个过程。因此，P2P2P2P2被阻塞，等待被阻塞，等待被阻塞，等待被阻塞，等待echoechoechoecho过程可用过程可

18、用过程可用过程可用 一段时间后进程一段时间后进程一段时间后进程一段时间后进程P1P1P1P1被恢复，完成被恢复，完成被恢复，完成被恢复，完成echoechoechoecho的执行，显示出正确的执行，显示出正确的执行，显示出正确的执行，显示出正确的字符的字符的字符的字符x x x x P1P1P1P1退出退出退出退出echoechoechoecho后，解除了后，解除了后，解除了后，解除了P2P2P2P2的阻塞，的阻塞，的阻塞，的阻塞，P2P2P2P2被恢复，成功地调用被恢复，成功地调用被恢复，成功地调用被恢复，成功地调用echoechoechoecho过程过程过程过程 void echo()vo

19、id echo()chin=getchar();chin=getchar();chout=chin;chout=chin;putchar(chout);putchar(chout);P1 void echo()void echo()chin=getchar();chin=getchar();chout=chin;chout=chin;putchar(chout);putchar(chout);调用调用调用调用echoecho超时，就绪超时，就绪超时，就绪超时，就绪P2调用调用调用调用echoecho资源资源资源资源正忙正忙正忙正忙阻塞状态阻塞状态阻塞状态阻塞状态调度运行调度运行调度运行调度运行

20、释放释放释放释放echoecho唤唤 醒醒获取资源获取资源获取资源获取资源就绪状态就绪状态就绪状态就绪状态调度运行调度运行调度运行调度运行3.6 进程同步与同步进程同步与同步由此可见，解决共享资源的保护，唯一的办法是由此可见，解决共享资源的保护，唯一的办法是由此可见，解决共享资源的保护，唯一的办法是由此可见，解决共享资源的保护，唯一的办法是互斥的使用互斥的使用互斥的使用互斥的使用共享资源共享资源共享资源共享资源（如变量，代码等）（如变量，代码等）（如变量，代码等）（如变量，代码等）即：一次只允许一个进程访问共享资源即：一次只允许一个进程访问共享资源即：一次只允许一个进程访问共享资源即：一次只允

21、许一个进程访问共享资源临界资源和临界区：临界资源和临界区：临界资源和临界区：临界资源和临界区：临界资源临界资源临界资源临界资源 某些在一段时间内只允许一个进程使用的共享资源称为临某些在一段时间内只允许一个进程使用的共享资源称为临某些在一段时间内只允许一个进程使用的共享资源称为临某些在一段时间内只允许一个进程使用的共享资源称为临界资源界资源界资源界资源 临界区（段）临界区（段）临界区（段）临界区（段）访问临界资源的程序段称为临界区。即互斥执行的程序段访问临界资源的程序段称为临界区。即互斥执行的程序段访问临界资源的程序段称为临界区。即互斥执行的程序段访问临界资源的程序段称为临界区。即互斥执行的程序

22、段p53p533.6 进程同步与同步进程同步与同步进程进程进程进程P1P1和和和和P2P2共享同一打印机资源，其操作流程如共享同一打印机资源，其操作流程如共享同一打印机资源，其操作流程如共享同一打印机资源，其操作流程如下：下：下：下：p1:entry codep1:entry codep1:entry codep1:entry code使用打印机使用打印机使用打印机使用打印机exit codeexit codeexit codeexit code p2:entry code p2:entry code p2:entry code p2:entry code使用打印机使用打印机使用打印机使用打印

23、机exit codeexit codeexit codeexit code系统打印机即为系统打印机即为系统打印机即为系统打印机即为临界资源临界资源临界资源临界资源P1P1和和和和p2p2的访问临界资源打印机的代码即为的访问临界资源打印机的代码即为的访问临界资源打印机的代码即为的访问临界资源打印机的代码即为临临临临界区界区界区界区3.6 进程同步与同步进程同步与同步进程的通信方式之一进程的通信方式之一进程的通信方式之一进程的通信方式之一同步与互斥同步与互斥同步与互斥同步与互斥 同步同步同步同步：进程间必须互相合作的协同关系，有前后次序的等：进程间必须互相合作的协同关系，有前后次序的等：进程间必须

24、互相合作的协同关系，有前后次序的等：进程间必须互相合作的协同关系，有前后次序的等待和信息交换关系待和信息交换关系待和信息交换关系待和信息交换关系,这种进程间的直接制约关系称为进程这种进程间的直接制约关系称为进程这种进程间的直接制约关系称为进程这种进程间的直接制约关系称为进程同步同步同步同步(p60)(p60)(p60)(p60)互斥互斥互斥互斥：两个进程，当一个进程进入临界区时，另一个进程：两个进程，当一个进程进入临界区时，另一个进程：两个进程，当一个进程进入临界区时，另一个进程：两个进程，当一个进程进入临界区时，另一个进程不能进入该临界区，这种进程间的间接制约关系称为进程不能进入该临界区，这

25、种进程间的间接制约关系称为进程不能进入该临界区，这种进程间的间接制约关系称为进程不能进入该临界区，这种进程间的间接制约关系称为进程互斥互斥互斥互斥(p53)(p53)(p53)(p53)3.6 进程同步与同步进程同步与同步互斥：硬件的支持互斥：硬件的支持互斥：硬件的支持互斥：硬件的支持 中断禁用中断禁用中断禁用中断禁用 在单处理器机器中，并发进程不能重叠在单处理器机器中，并发进程不能重叠在单处理器机器中，并发进程不能重叠在单处理器机器中，并发进程不能重叠,只能交只能交只能交只能交替。此外，一个进程将一直运行，直到它调用了一个操作替。此外，一个进程将一直运行，直到它调用了一个操作替。此外，一个进

26、程将一直运行，直到它调用了一个操作替。此外，一个进程将一直运行，直到它调用了一个操作系统服务或被中断。因此，为保证互斥，只需要保证一个系统服务或被中断。因此，为保证互斥，只需要保证一个系统服务或被中断。因此，为保证互斥，只需要保证一个系统服务或被中断。因此，为保证互斥，只需要保证一个进程不被中断就可以进程不被中断就可以进程不被中断就可以进程不被中断就可以 当一个计算机系统包括多个处理器时，在这种情况下，禁当一个计算机系统包括多个处理器时，在这种情况下，禁当一个计算机系统包括多个处理器时，在这种情况下，禁当一个计算机系统包括多个处理器时，在这种情况下，禁止中断不能保证互斥止中断不能保证互斥止中断

27、不能保证互斥止中断不能保证互斥3.6 进程同步与同步进程同步与同步互斥：硬件的支持互斥：硬件的支持互斥：硬件的支持互斥：硬件的支持 专门的机器指令专门的机器指令专门的机器指令专门的机器指令 在硬件级，对存储器单元的访问排斥到相同单元的其他访在硬件级，对存储器单元的访问排斥到相同单元的其他访在硬件级，对存储器单元的访问排斥到相同单元的其他访在硬件级，对存储器单元的访问排斥到相同单元的其他访问。基于这一点，处理器的设计者提出了一些机器指令，问。基于这一点，处理器的设计者提出了一些机器指令，问。基于这一点，处理器的设计者提出了一些机器指令，问。基于这一点，处理器的设计者提出了一些机器指令，用于保证两

28、个动作的原子性，如在一个取指令周期中对一用于保证两个动作的原子性，如在一个取指令周期中对一用于保证两个动作的原子性，如在一个取指令周期中对一用于保证两个动作的原子性，如在一个取指令周期中对一个存储器单元的读和写或者读和测试。由于这些动作个存储器单元的读和写或者读和测试。由于这些动作个存储器单元的读和写或者读和测试。由于这些动作个存储器单元的读和写或者读和测试。由于这些动作在一在一在一在一个指令周期中执行个指令周期中执行个指令周期中执行个指令周期中执行，它们不会受到其他指令的干扰，它们不会受到其他指令的干扰，它们不会受到其他指令的干扰，它们不会受到其他指令的干扰 如：如：如：如：test-and

29、-settest-and-set指令，指令，指令，指令，swapswap指令等指令等指令等指令等3.6 进程同步与同步进程同步与同步实现同步、互斥的三种主要方法：实现同步、互斥的三种主要方法：实现同步、互斥的三种主要方法：实现同步、互斥的三种主要方法：信号量信号量信号量信号量 管程管程管程管程 消息传递消息传递消息传递消息传递进程间的同步与互斥一般用通信原语来实现进程间的同步与互斥一般用通信原语来实现进程间的同步与互斥一般用通信原语来实现进程间的同步与互斥一般用通信原语来实现 低级通信原语低级通信原语低级通信原语低级通信原语加锁；加锁；加锁；加锁；P P、V V操作操作操作操作 高级通信原语高

30、级通信原语高级通信原语高级通信原语消息缓冲机制消息缓冲机制消息缓冲机制消息缓冲机制3.6 进程同步与同步进程同步与同步Lock和和unlock 关锁和开锁是加锁机制的关锁和开锁是加锁机制的关锁和开锁是加锁机制的关锁和开锁是加锁机制的2 2个基本操作。在其中设个基本操作。在其中设个基本操作。在其中设个基本操作。在其中设置一公共变量置一公共变量置一公共变量置一公共变量 x x 代表某个临界资源的状态代表某个临界资源的状态代表某个临界资源的状态代表某个临界资源的状态 X X X X1 1 1 1 表示资源可用表示资源可用表示资源可用表示资源可用 X X X X0 0 0 0 表示资源正在被使用表示资

31、源正在被使用表示资源正在被使用表示资源正在被使用 进程使用临界资源必须做如下三个不可分割的操进程使用临界资源必须做如下三个不可分割的操进程使用临界资源必须做如下三个不可分割的操进程使用临界资源必须做如下三个不可分割的操作作作作Lock和和unlock 1)1)1)1)检查检查检查检查 x x x x 的值。的值。的值。的值。x=0 x=0 x=0 x=0，资源正在使用，返回继续进行检查；资源正在使用，返回继续进行检查；资源正在使用，返回继续进行检查；资源正在使用，返回继续进行检查；x=1x=1x=1x=1，资源可以使用，置资源可以使用，置资源可以使用，置资源可以使用，置 x x x x 为为为

32、为 0(0(0(0(关锁关锁关锁关锁)2)2)2)2)进入临界区，访问临界资源进入临界区，访问临界资源进入临界区，访问临界资源进入临界区，访问临界资源 3)3)3)3)释放资源释放资源释放资源释放资源,退出临界区，置退出临界区，置退出临界区，置退出临界区，置 x x x x 为为为为 1(1(1(1(开锁开锁开锁开锁)通过分析，给出关锁和开锁操作的描述通过分析，给出关锁和开锁操作的描述通过分析，给出关锁和开锁操作的描述通过分析，给出关锁和开锁操作的描述 关锁关锁关锁关锁 lockxlockx L:if x=0 then go to L else x:=0;L:if x=0 then go to

33、 L else x:=0;开锁开锁开锁开锁 unlockxunlockxx:=1;x:=1;简单的加锁机制不能彻底解决互斥问题，因为当同时有几个简单的加锁机制不能彻底解决互斥问题，因为当同时有几个简单的加锁机制不能彻底解决互斥问题，因为当同时有几个简单的加锁机制不能彻底解决互斥问题，因为当同时有几个进程调用进程调用进程调用进程调用lockxlockx时，在时，在时，在时，在x:=0 x:=0语句执行前，可能已经有语句执行前，可能已经有语句执行前，可能已经有语句执行前，可能已经有2 2个以个以个以个以上的进程由于上的进程由于上的进程由于上的进程由于x=1x=1而进入临界区了。因此必须加入一些机制

34、，而进入临界区了。因此必须加入一些机制，而进入临界区了。因此必须加入一些机制，而进入临界区了。因此必须加入一些机制，保证第保证第保证第保证第1 1步和第步和第步和第步和第2 2步的执行具有不可分离性步的执行具有不可分离性步的执行具有不可分离性步的执行具有不可分离性加锁机制虽然可以实现进程之间的互斥，但执行效率低、浪加锁机制虽然可以实现进程之间的互斥，但执行效率低、浪加锁机制虽然可以实现进程之间的互斥，但执行效率低、浪加锁机制虽然可以实现进程之间的互斥，但执行效率低、浪费处理机资源。因为任何进程都不能直接进入临界区，必须费处理机资源。因为任何进程都不能直接进入临界区，必须费处理机资源。因为任何进

35、程都不能直接进入临界区，必须费处理机资源。因为任何进程都不能直接进入临界区，必须不停地循环检查不停地循环检查不停地循环检查不停地循环检查 x x 的值，等待锁位变为的值，等待锁位变为的值，等待锁位变为的值，等待锁位变为 1,1,消耗了有价值的消耗了有价值的消耗了有价值的消耗了有价值的CPUCPU时间。时间。时间。时间。加锁机制存在不公平性，导致某些进程一直优先进入临界区，加锁机制存在不公平性，导致某些进程一直优先进入临界区，加锁机制存在不公平性，导致某些进程一直优先进入临界区，加锁机制存在不公平性，导致某些进程一直优先进入临界区，而某些进程可能一直无法进入临界区而某些进程可能一直无法进入临界区

36、而某些进程可能一直无法进入临界区而某些进程可能一直无法进入临界区引入信号量机制引入信号量机制引入信号量机制引入信号量机制P/V P/V 操作操作操作操作信号量机制信号量机制信号量机制信号量机制信号量（信号量（信号量（信号量（semaphoresemaphore）：）：）：）：一个与资源有关的，初一个与资源有关的，初一个与资源有关的，初一个与资源有关的，初值为非负数的整型变量称为信号量。用值为非负数的整型变量称为信号量。用值为非负数的整型变量称为信号量。用值为非负数的整型变量称为信号量。用S S表示，初表示，初表示，初表示，初值和资源有关值和资源有关值和资源有关值和资源有关P P、V V操作操作

37、操作操作：定义在信号量：定义在信号量：定义在信号量：定义在信号量S S上的一组操作，由上的一组操作，由上的一组操作，由上的一组操作，由P P原原原原语和语和语和语和V V原语组成，能对信号量原语组成，能对信号量原语组成，能对信号量原语组成，能对信号量s s进行修改进行修改进行修改进行修改信号量是一种特殊的变量，只能由信号量是一种特殊的变量，只能由信号量是一种特殊的变量，只能由信号量是一种特殊的变量，只能由P P P P，V V V V操作进行访操作进行访操作进行访操作进行访问问问问P P 原语原语原语原语 P(S)P(S)S:=S-1S:=S-1；如果如果如果如果 S =0S =0，则表示有资

38、源，该进程继续执行；则表示有资源，该进程继续执行；则表示有资源，该进程继续执行；则表示有资源，该进程继续执行；如果如果如果如果 S 0S 0S 0，则该进程继续执行，则该进程继续执行，则该进程继续执行，则该进程继续执行 如果如果如果如果 S S 0 S 0 S 0 S 0 时，时，时，时，S S S S 的值表示某类资源可用的数量的值表示某类资源可用的数量的值表示某类资源可用的数量的值表示某类资源可用的数量l lS 0S 0S 0S 1 then if count 1 then V(entry);V(entry);P(wait);P(wait);else else V(entry)V(entr

39、y);V(barber);V(barber);“Shave”“Shave”P(entry);P(entry);count:=count 1;count:=count 1;if count 0 then V(wait);if count 0 then V(wait);V(entry);V(entry);理发室理发室理发室理发室椅子椅子椅子椅子入口入口入口入口出口出口出口出口等候室等候室等候室等候室理发室理发室理发室理发室椅子椅子椅子椅子入口入口入口入口出口出口出口出口等候室等候室等候室等候室简单理发店问题简单理发店问题barberbarberbarberbarber信号量队列信号量队列信号量队列

40、信号量队列waitwaitwaitwait信号量队列信号量队列信号量队列信号量队列entryentryentryentry信号量队列信号量队列信号量队列信号量队列理发师理发师理发师理发师P P（barberbarber）P P（entryentry）P P（entryentry）countcount=0=0=1=1v v（entryentry）唤唤唤唤醒醒醒醒count=1count=1v v（entryentry）Count=2Count=2P P（waitwait）V V（barberbarber）QQQQQQQQ王国的简单理发店问题王国的简单理发店问题王国的简单理发店问题王国的简单理发店

41、问题理发师理发师barberbarberbarberbarber信号量队列信号量队列信号量队列信号量队列waitwaitwaitwait信号量队列信号量队列信号量队列信号量队列entryentryentryentry信号量队列信号量队列信号量队列信号量队列P P（entryentry）count=5count=5QQQQQQQQ王国的简单理发店问题王国的简单理发店问题王国的简单理发店问题王国的简单理发店问题V V（entryentry）P P（entryentry）count=5count=5count=4count=4V V（entryentry）V V（waitwait）V V（barbe

42、rbarber）解解解解:var a,b,c,d,e,f,g,h:semaphore (var a,b,c,d,e,f,g,h:semaphore (初值初值初值初值=0)=0)parbeginparbeginbegin S1;V(a);V(b);V(c);end;begin S1;V(a);V(b);V(c);end;begin P(a);S2;V(d);V(e);end;begin P(a);S2;V(d);V(e);end;begin P(b);S3;V(f);end;begin P(b);S3;V(f);end;begin P(c);P(d);S4;V(g);end;begin P(c

43、);P(d);S4;V(g);end;begin P(e);P(f);S5;V(h);end;begin P(e);P(f);S5;V(h);end;begin P(g);P(h);S6;end;begin P(g);P(h);S6;end;parendparend习习 题题例例例例:考虑右图所示的优先图，请用并发语句和信号量表达该考虑右图所示的优先图，请用并发语句和信号量表达该考虑右图所示的优先图，请用并发语句和信号量表达该考虑右图所示的优先图，请用并发语句和信号量表达该优先图。优先图。优先图。优先图。S1S1S1S1S3S3S3S3S4S4S4S4S6S6S6S6S5S5S5S5S2S2S

44、2S2a ab bc cd de ef fh hg g习习 题题桌上有一个空盘，允许存放一个水果。父亲可向盘中桌上有一个空盘，允许存放一个水果。父亲可向盘中桌上有一个空盘，允许存放一个水果。父亲可向盘中桌上有一个空盘，允许存放一个水果。父亲可向盘中放苹果，也可向盘中放橘子，儿子专等吃盘中的橘放苹果，也可向盘中放橘子，儿子专等吃盘中的橘放苹果，也可向盘中放橘子，儿子专等吃盘中的橘放苹果，也可向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时一次放子，女儿专等吃盘中的苹果。规定当盘空时一次放子，女儿专等吃盘中的苹果。规定当盘空时一次放子，女儿专等吃盘中的苹果。规定当盘空时一次放

45、一个水果供吃者取用，请用一个水果供吃者取用，请用一个水果供吃者取用，请用一个水果供吃者取用，请用P P，V V原语实现父亲、儿原语实现父亲、儿原语实现父亲、儿原语实现父亲、儿子、女儿三个并发进程的同步。子、女儿三个并发进程的同步。子、女儿三个并发进程的同步。子、女儿三个并发进程的同步。分析同步分析同步分析同步分析同步/互斥关系：互斥关系：互斥关系：互斥关系：父亲和儿子之间父亲和儿子之间父亲和儿子之间父亲和儿子之间同步同步同步同步 父亲和女儿之间父亲和女儿之间父亲和女儿之间父亲和女儿之间同步同步同步同步习习 题题设置信号量设置信号量设置信号量设置信号量父亲的私有信号量父亲的私有信号量父亲的私有信

46、号量父亲的私有信号量s s，表示盘子是否可用，初值为表示盘子是否可用，初值为表示盘子是否可用，初值为表示盘子是否可用，初值为1 1儿子的私有信号量儿子的私有信号量儿子的私有信号量儿子的私有信号量orangeorange，表示是否有橘子可吃，表示是否有橘子可吃，表示是否有橘子可吃，表示是否有橘子可吃，初值为初值为初值为初值为0 0女儿的私有信号量女儿的私有信号量女儿的私有信号量女儿的私有信号量appleapple，表示是否有苹果可吃，表示是否有苹果可吃，表示是否有苹果可吃，表示是否有苹果可吃，初值为初值为初值为初值为0 0习习 题题fatherfather进程：进程：进程：进程：L1L1：P(S

47、)P(S)；将水果放入盘中；将水果放入盘中；将水果放入盘中；将水果放入盘中；if(if(放入是橘子放入是橘子放入是橘子放入是橘子)V(V(orangeorange)；else V(else V(appleapple)；goto L1goto L1；daughterdaughter进程：进程：进程：进程：L2L2：P(P(appleapple)；从盘中取出苹果；从盘中取出苹果；从盘中取出苹果；从盘中取出苹果；V(S)V(S)；吃苹果；吃苹果；吃苹果；吃苹果；goto L2goto L2；sonson进程：进程：进程：进程：L3L3：P(P(orangeorange)；从盘中取出橘子；从盘中取出橘

48、子；从盘中取出橘子；从盘中取出橘子；V(S)V(S)；吃橘子；吃橘子；吃橘子；吃橘子；goto L3goto L3；习习 题题 题：有题：有题：有题：有P P，QQ，R R 三个进程，三个进程，三个进程，三个进程，P P读入数据后传递给读入数据后传递给读入数据后传递给读入数据后传递给QQ，QQ进行一些处理后将数据传递给进行一些处理后将数据传递给进行一些处理后将数据传递给进行一些处理后将数据传递给R R，R R整理好数据后整理好数据后整理好数据后整理好数据后输出，请用输出，请用输出，请用输出，请用pvpv操作实现三者的同步关系。操作实现三者的同步关系。操作实现三者的同步关系。操作实现三者的同步关

49、系。l l进程进程进程进程P,QP,QP,QP,Q共享一个缓冲区，进程共享一个缓冲区，进程共享一个缓冲区，进程共享一个缓冲区，进程Q,RQ,RQ,RQ,R共享一个缓冲共享一个缓冲共享一个缓冲共享一个缓冲区区区区l l进程进程进程进程P,QP,QP,QP,Q共享一个有共享一个有共享一个有共享一个有m m m m个缓冲区的缓冲池，进程个缓冲区的缓冲池，进程个缓冲区的缓冲池，进程个缓冲区的缓冲池，进程Q,RQ,RQ,RQ,R共享一个有共享一个有共享一个有共享一个有n n n n个缓冲区缓冲池个缓冲区缓冲池个缓冲区缓冲池个缓冲区缓冲池习习 题题 (1).(1).进程进程进程进程P,QP,Q共享一个缓冲

50、区，进程共享一个缓冲区，进程共享一个缓冲区，进程共享一个缓冲区，进程Q,RQ,R共享一个缓冲区共享一个缓冲区共享一个缓冲区共享一个缓冲区 分析分析分析分析：P,QP,Q之间是相互依赖协作的关系之间是相互依赖协作的关系之间是相互依赖协作的关系之间是相互依赖协作的关系同步同步同步同步 Q,RQ,R之间也是相互依赖协作的关系之间也是相互依赖协作的关系之间也是相互依赖协作的关系之间也是相互依赖协作的关系同步同步同步同步 设置信号量设置信号量设置信号量设置信号量：假设初始两个缓冲区都为空：假设初始两个缓冲区都为空：假设初始两个缓冲区都为空：假设初始两个缓冲区都为空 P P的私有信号量的私有信号量的私有信