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)lock)b
4、oolean 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指令实现互斥指令实现互斥2.2.利用利用TSTS指令实
5、现进程互斥指令实现进程互斥while TS(&lock);lock=FALSE;critical sectionremainder sectionn利用利用TSTS实现进程互斥：每个临界资源设置一个公实现进程互斥：每个临界资源设置一个公共布尔变量共布尔变量locklock，初值为，初值为FALSEFALSEn在在“进入区进入区”利用利用TSTS进行检查：若有进程在临界进行检查：若有进程在临界区时，重复检查；直到其它进程退出时，检查通区时，重复检查；直到其它进程退出时，检查通过；过；3.1 3.1 进进程程的的同同步步3.1.2 3.1.2 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互
6、斥问题互斥的加锁实现互斥的加锁实现二、利用二、利用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 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现二、利用二、利用SwapSwap指令实现进程互斥指令实现进程互斥2.2
7、.利用利用SwapSwap实现进程互斥实现进程互斥 每个临界资源设置一个公共布尔变量每个临界资源设置一个公共布尔变量locklock，初值为，初值为FALSEFALSE。每个进程设置一个私有布尔变量。每个进程设置一个私有布尔变量keykeykey=TRUE;do SWAP(&lock,&key);while(key);lock=FALSE;critical sectionremainder section3.1 3.1 进进程程的的同同步步3.1.2 3.1.2 利用硬件的方法解决进程互斥问题利用硬件的方法解决进程互斥问题互斥的加锁实现互斥的加锁实现3.1 3.1 进进程程的的同同步步n硬件方
8、法的优点硬件方法的优点n适用于任意数目的进程，在单处理器或多处理器上适用于任意数目的进程，在单处理器或多处理器上n简单，容易验证其正确性简单，容易验证其正确性n可以支持进程内存在多个临界区，只需为每个临界可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量区设立一个布尔变量n硬件方法的缺点硬件方法的缺点n循环测试锁状态循环测试锁状态,损耗损耗CPUCPU时间。时间。n可能可能“饥饿饥饿”：从等待进程中随机选择一个进入临：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上界区，有的进程可能一直选不上(不公平现象不公平现象)3.1 3.1 进进程程的的同同步步3.1.3 3.1.
9、3 信号量机制信号量机制一、信号量一、信号量 是对系统中资源及其组织情况的抽象。它由一是对系统中资源及其组织情况的抽象。它由一个记录型数据表示。包含两个数据项个记录型数据表示。包含两个数据项:type semaphore=recordtype semaphore=record value:integer;value:integer;L:list of process;L:list of process;end end 其中其中:valuevalue的值表示可用资源的数目的值表示可用资源的数目;L:L:为等待此类资源的进程为等待此类资源的进程PCBPCB表链。表链。3.1 3.1 进进程程的的同
10、同步步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)signal(s)功能：功能：释放释放一个一个单位的资源单位的资源参数：参数：信号量信号量S S流程：流程：3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信
11、号量的应用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 1；在每个进程中将临界区代码置于在每个进程中将临界区代码置于P(S)P(S)和和V(S)V(S)原语原语之间之间n必须必须成对使用成对使用P P和和V V原语：遗漏原语：遗漏P P原语则不能保证互原语则不能保证互斥访问
12、，遗漏斥访问，遗漏V V原语则不能在使用临界资源之后将原语则不能在使用临界资源之后将其释放（给其他等待的进程）；其释放（给其他等待的进程）；P P、V V原语原语不能次不能次序错误、重复或遗漏序错误、重复或遗漏3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用1.1.实现进程互斥实现进程互斥3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信号量的应用2.2.实现进程同步实现进程同步3.1 3.1 进进程程的的同同步步3.1.3 3.1.3 信号量机制信号量机制三、信号量的应用三、信
13、号量的应用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;到站停车到站停车-开车门开车门 stop=0;stop=0;司机：司机：售票员：售票员：上乘客上乘客 p(run)p(run)关车门关车门 启动车辆启动车辆 v(run)v(run)正常行车正常行车 售票售票 到站停车到站停车 p(st
15、op)p(stop)v(stop)v(stop)开车门开车门 下乘客下乘客3.3.描述前趋图描述前趋图s1s2s3s7s4s5s6信信号号量量机机制制三、信号量的应用三、信号量的应用s1s2s3s7s4s5s6信信号号量量机机制制三、信号量的应用三、信号量的应用3.3.描述前趋图描述前趋图4.4.解决生产者解决生产者消费者问题消费者问题问题描述问题描述：有一群生产者进程在生产产品，并将这些产有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有进程能并发执行，在两者之间设置了
16、一个具有n n个缓冲区个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；区中；消费者进程可从一个缓冲区中取走产品去消费。消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且已装满产品且尚未被取走的缓冲区中投放产品。尚未被取走的缓冲区中投放产品。三、信
17、号量的应用三、信号量的应用信信号号量量机机制制信信号号量量机机制制三、信号量的应用三、信号量的应用4.4.解决生产者解决生产者消费者问题消费者问题在每个程序中的多个在每个程序中的多个 操作顺序不能颠操作顺序不能颠倒。应先执行对资源信号量的倒。应先执行对资源信号量的 操作，然后再操作，然后再执行对互斥信号量的执行对互斥信号量的 操作，否则可能引起进操作，否则可能引起进程死锁程死锁。三、信号量的应用三、信号量的应用 三个进程三个进程P0P0、P1P1、P2P2和三个缓冲区和三个缓冲区B0B0、B1B1、B2B2。进程间借助于相邻缓冲区传递消息：。进程间借助于相邻缓冲区传递消息：PiPi每次每次从从
18、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。进程间借助于相邻缓
19、冲区传递消息：。进程间借助于相邻缓冲区传递消息：PiPi每次每次从从BiBi中取一条消息，经加工送入中取一条消息，经加工送入B B（i+1i+1）mod 3mod 3中，中，B0B0、B1B1、B2B2分别可存放分别可存放3 3、2 2、1 1个消息。初个消息。初始时，仅始时，仅B0B0有一个消息。有一个消息。1 1分析三个进程间的同步、互斥关系。分析三个进程间的同步、互斥关系。2 2用用P P、V V操作写出操作写出P0P0、P1P1、P2P2的同步及互的同步及互斥流程。斥流程。例例2:2:信信号号量量机机制制三、信号量的应用三、信号量的应用 一组生产者进程和一组消费者进程共享一组生产者进程
20、和一组消费者进程共享1010个缓冲区，每个缓冲区可以存放一个整数；个缓冲区，每个缓冲区可以存放一个整数；生产者进程每次一次性向生产者进程每次一次性向3 3个个缓冲区中写入数缓冲区中写入数据，消费者进程每次从缓冲区取出据，消费者进程每次从缓冲区取出一个一个整数。整数。1 1分析进程间的同步、互斥关系。分析进程间的同步、互斥关系。2 2用用P P、V V操作写出进程间的同步及互斥流程。操作写出进程间的同步及互斥流程。例例3:3:信信号号量量机机制制信信号号量量机机制制三、信号量的应用三、信号量的应用5.5.解决读者解决读者写者问题写者问题读者间可同时访问共享资源。读者间可同时访问共享资源。任一写者必须与其它写者或读者互斥访问共享资源任一写者必须与其它写者或读者互斥访问共享资源 3.1 3.1 进进程程的的同同步步3.1.4 3.1.4 信号量集机制信号量集机制一、一、ANDAND型信号量集机制型信号量集机制
