进程同步第三章

1、第三章第三章 进程的同步与通信进程的同步与通信3.1 3.1 进程的同步进程的同步3.2 3.2 进程通信进程通信3.1 3.1 进程的同步进程的同步3.1.1 3.1.1 临界区临界区3.1.2 3.1.2 利用硬件的方法解决进程互利用硬件的方法解决进程互 斥问题斥问题互斥的加锁实现互斥的加锁实现3.1.3 3.1.3 信号量机制信号量机制3.1.1 3.1.1 临界区临界区一、临界区一、临界区3.1 3.1 进进程程的的同同步步例例二、进程间的制约关系二、进程间的制约关系3.1.1 3.1.1 临界区临界区3.1 3.1 进进程程的的同同步步三、临界区的进入：三、临界区的进入：3.1.1

2、3.1.1 临界区临界区2.2.同步机制应遵循的准则同步机制应遵循的准则1.1.访问过程访问过程3.1 3.1 进进程程的的同同步步空闲让进空闲让进忙则等待忙则等待有限等待有限等待让权等待让权等待3.1.2 3.1.2 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现 可以利用某些硬件指令其读写操作由一条可以利用某些硬件指令其读写操作由一条指令完成，因而保证读操作与写操作不被打断；指令完成，因而保证读操作与写操作不被打断；这些指令允许对一个字的内容进行检测和修正，这些指令允许对一个字的内容进行检测和修正，或交换两个字的内容。或交换两个字的内容。一、利用一

3、、利用Test-and-SetTest-and-Set指令实现互斥指令实现互斥二、利用二、利用SwapSwap指令实现进程互斥指令实现进程互斥3.1 3.1 进进程程的的同同步步3.1.2 3.1.2 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现一、利用一、利用Test-and-SetTest-and-Set指令实现互斥指令实现互斥1. Test-and-Set1. Test-and-Set指令指令该指令读出标志后设置为该指令读出标志后设置为TRUETRUEboolean TS(boolean boolean TS(boolean * *lock)

4、lock) boolean boolean old; old; old = old = * *lock; lock; * *lock = TRUE;lock = TRUE; return old; return old; locklock表示资源的两种状态：表示资源的两种状态：TRUETRUE表示临界区正被表示临界区正被占用（忙），占用（忙），FALSEFALSE表示空闲。表示空闲。3.1 3.1 进进程程的的同同步步3.1.2 3.1.2 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现一、利用一、利用Test-and-SetTest-and-Set指

5、令实现互斥指令实现互斥2.2.利用利用TSTS指令实现进程互斥指令实现进程互斥while TS(&lock);lock = FALSE;critical sectionremainder sectionn利用利用TSTS实现进程互斥：每个临界资源设置一个公实现进程互斥：每个临界资源设置一个公共布尔变量共布尔变量locklock，初值为，初值为FALSEFALSEn在在“进入区进入区”利用利用TSTS进行检查：若有进程在临界进行检查：若有进程在临界区时，重复检查；直到其它进程退出时，检查通区时，重复检查；直到其它进程退出时，检查通过；过；3.1 3.1 进进程程的的同同步步3.1.2 3

6、.1.2 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现二、利用二、利用SwapSwap指令实现进程互斥指令实现进程互斥1. Swap1. Swap指令指令交换两个字（字节）的内容交换两个字（字节）的内容void SWAP(int void SWAP(int * *a, int a, int * *b) b) int int temp; temp; temp = temp = * *a; a; * *a = a = * *b; b; * *b = temp;b = temp; 3.1 3.1 进进程程的的同同步步3.1.2 3.1.2 利用硬件的方法解

7、决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现二、利用二、利用SwapSwap指令实现进程互斥指令实现进程互斥2. 2. 利用利用SwapSwap实现进程互斥实现进程互斥 每个临界资源设置一个公共布尔变量每个临界资源设置一个公共布尔变量locklock，初值为，初值为FALSEFALSE。每个进程设置一个私有布尔变量。每个进程设置一个私有布尔变量keykeykey = TRUE;do SWAP(&lock, &key); while (key);lock = FALSE;critical sectionremainder section3.1 3.1

8、进进程程的的同同步步3.1.2 3.1.2 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现3.1 3.1 进进程程的的同同步步n硬件方法的优点硬件方法的优点n适用于任意数目的进程，在单处理器或多处理器上适用于任意数目的进程，在单处理器或多处理器上n简单，容易验证其正确性简单，容易验证其正确性n可以支持进程内存在多个临界区，只需为每个临界可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量区设立一个布尔变量n硬件方法的缺点硬件方法的缺点n循环测试锁状态循环测试锁状态, ,损耗损耗CPUCPU时间。时间。n可能可能“饥饿饥饿”：从等待进程中随机选

9、择一个进入临：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上界区，有的进程可能一直选不上( (不公平现象不公平现象) )3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制一、信号量一、信号量 是对系统中资源及其组织情况的抽象。它由一是对系统中资源及其组织情况的抽象。它由一个记录型数据表示。包含两个数据项个记录型数据表示。包含两个数据项: :type semaphore=recordtype semaphore=record value:integer;value:integer; L:list of process; L:list of process

10、; end end 其中其中: : valuevalue的值表示可用资源的数目的值表示可用资源的数目; ; L: L:为等待此类资源的进程为等待此类资源的进程PCBPCB表链。表链。3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制二、二、P PV V操作操作1.1.P P操作：操作：wait(s)wait(s)功能：功能：请求系统分配请求系统分配一个一个单位的资源单位的资源参数：参数：信号量信号量S S流程：流程：3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制二、二、P PV V操作操作2.2.V V操作：操作：signal(s

11、)signal(s)功能：功能：释放释放一个一个单位的资源单位的资源参数：参数：信号量信号量S S流程：流程：3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用1.1.实现进程互斥实现进程互斥PA: P(S) critical section V(S)PB: P(S) critical section V(S)3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用1.1.实现进程互斥实现进程互斥n为临界资源设置一个为临界资源设置一个互斥信号量互斥信号量 ，其，其初值为初值为1

12、 1；在每个进程中将临界区代码置于在每个进程中将临界区代码置于P(S)P(S)和和V(S)V(S)原语原语之间之间n必须必须成对使用成对使用P P和和V V原语：遗漏原语：遗漏P P原语则不能保证互原语则不能保证互斥访问，遗漏斥访问，遗漏V V原语则不能在使用临界资源之后将原语则不能在使用临界资源之后将其释放（给其他等待的进程）；其释放（给其他等待的进程）；P P、V V原语原语不能次不能次序错误、重复或遗漏序错误、重复或遗漏3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用1.1.实现进程互斥实现进程互斥3.1 3.1 进进程程的

13、的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用2.2.实现进程同步实现进程同步3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用2.2.实现进程同步实现进程同步3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用2.2.实现进程同步实现进程同步例如：设在公共汽车上，司机和售票员的活动分别是：例如：设在公共汽车上，司机和售票员的活动分别是：司机：司机： 售票员：售票员： 启动车辆启动车辆 上乘客上乘客 正常行车正常行车 关车门关车门 到

14、站停车到站停车 售票售票 开车门开车门 下乘客下乘客 一方面只有售票员关好车门后司机才能启动车辆，另一方面只有售票员关好车门后司机才能启动车辆，另一方面只有司机到站停车后售票员才能开车门。请分析一方面只有司机到站停车后售票员才能开车门。请分析司机和售票员之间的同步关系，并用信号量的司机和售票员之间的同步关系，并用信号量的P P、V V操作操作来实现。来实现。3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用2.2.实现进程同步实现进程同步答：两个同步：关车门答：两个同步：关车门-启动车辆启动车辆 run=0; run=0; 到站停车

15、到站停车-开车门开车门 stop=0; stop=0; 司机：司机： 售票员：售票员： 上乘客上乘客 p(run) p(run) 关车门关车门 启动车辆启动车辆 v(run) v(run) 正常行车正常行车 售票售票 到站停车到站停车 p(stop)p(stop) v(stop) v(stop) 开车门开车门 下乘客下乘客3.3.描述前趋图描述前趋图s1s2s3s7s4s5s6信信号号量量机机制制三、信号量的应用三、信号量的应用s1s2s3s7s4s5s6信信号号量量机机制制三、信号量的应用三、信号量的应用3.3.描述前趋图描述前趋图4.4.解决生产者解决生产者消费者问题消费者问题问题描述问题

16、描述：有一群生产者进程在生产产品，并将这些产有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有进程能并发执行，在两者之间设置了一个具有n n个缓冲区个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；区中； 消费者进程可从一个缓冲区中取走产品去消费。消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，

17、即不允许消费者进程行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且已装满产品且尚未被取走的缓冲区中投放产品。尚未被取走的缓冲区中投放产品。 三、信号量的应用三、信号量的应用信信号号量量机机制制信信号号量量机机制制三、信号量的应用三、信号量的应用4.4.解决生产者解决生产者消费者问题消费者问题在每个程序中的多个在每个程序中的多个 操作顺序不能颠操作顺序不能颠倒。应先执行对资源信号量的倒。应先执行对资源信号量的 操作，然后再操作，然后再执行对互斥信号量的执行对互斥信号量的 操作，否则可能引起

18、进操作，否则可能引起进程死锁程死锁。三、信号量的应用三、信号量的应用 三个进程三个进程P0P0、P1P1、P2P2和三个缓冲区和三个缓冲区B0B0、B1B1、B2B2。进程间借助于相邻缓冲区传递消息：。进程间借助于相邻缓冲区传递消息：PiPi每次每次从从BiBi中取一条消息，经加工送入中取一条消息，经加工送入B B（i+1i+1）mod 3mod 3中，中，B0B0、B1B1、B2B2分别可存放分别可存放3 3、2 2、2 2个消息。初个消息。初始时，仅始时，仅B0B0有一个消息。有一个消息。 1 1分析三个进程间的同步、互斥关系。分析三个进程间的同步、互斥关系。 2 2用用P P、V V操作写出操作写出P0P0、P1P1、P2P2的同步及互的同步及互斥流程。斥流程。 例例1:1:信信号号量量机机制制三、信号量的应用三、信号量的应用 三个进程三个进程P0P0、P1P1、P2P2和三个缓冲区和三个缓冲区B0B0、B1B1、B2B2。进程间借助于相邻缓冲区传递消息：。进程间借助于相邻缓冲区传递消息：PiPi每次每次从从BiBi中取一条消息，经加工送入中取一条消息，经加工送入B B（i+1i+1）mod 3mod 3中，中，