操作系统课件进程同步

第三章进程的同步与通信3.1进程的同步3.2进程通信第三章进程的同步与通信3.1进程的同步13.1进程的同步3.1.1临界区3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现3.1.3信号量机制进程同步的主要任务：使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的并发执行具有可再现性。3.1进程的同步3.1.1临界区进程同步的23.1.1临界区一、临界区1.临界资源：2.临界区：3.1进程的同步一次仅允许一个进程访问的资源例：进程PA、PB共享内存MS。其中MS分为三个领域，即系统区、进程工作区和数据区。数据区被划分为大小相等的块，每个块中既可能被放有数据，也可能未放有数据。系统区中主要是堆栈S，其中存放那些空数据块的地址。分析其中的临界资源、临界区。访问临界资源的代码段，不允许多个并发进程交叉执行的一段程序3.1.1临界区一、临界区3.1进程的同步一次仅允许一3二、进程间的制约关系

1.间接制约关系(互斥)：2.直接制约关系(同步)：3.1.1临界区由于共享资源引起由于相互合作引起3.1进程的同步受间接制约的各进程在执行顺序上是任意的;一组在异步环境下的并发进程,各自的执行结果互为对方的执行条件,从而限制各进程的执行速度的过程,称为并发进程间的直接制约。二、进程间的制约关系3.1.1临界区由于共享资源引起4三、临界区的进入：

3.1.1临界区临界区必须互斥访问2.同步机制应遵循的准则1.访问过程3.1进程的同步临界区(1)检查临界资源是否被访问，未被访问，转(2)，否则转(1)。(2)进入临界区，并设访问标志恢复访问标志，允许其它进程进入空闲让进忙则等待有限等待让权等待进入区退出区三、临界区的进入：3.1.1临界区临界区必须互斥访问53.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现

可以利用某些硬件指令－－其读写操作由一条指令完成，因而保证读操作与写操作不被打断；这些指令允许对一个字的内容进行检测和修正，或交换两个字的内容。一、利用Test-and-Set指令实现互斥二、利用Swap指令实现进程互斥3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现63.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一、利用Test-and-Set指令实现互斥1.Test-and-Set指令该指令读出标志后设置为TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示资源的两种状态：TRUE表示临界区正被占用（忙），FALSE表示空闲。3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一73.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一、利用Test-and-Set指令实现互斥2.利用TS指令实现进程互斥利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在“进入区”利用TS进行检查：若有进程在临界区时，重复检查；直到其它进程退出时，检查通过；3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一83.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二、利用Swap指令实现进程互斥1.Swap指令交换两个字（字节）的内容voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二93.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二、利用Swap指令实现进程互斥2.利用Swap实现进程互斥每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二103.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现3.1进程的同步硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点循环测试锁状态,损耗CPU时间。可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上(不公平现象)3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现3113.1进程的同步3.1.3信号量机制一、信号量

是对系统中资源及其组织情况的抽象。它由一个记录型数据表示。包含两个数据项:typesemaphore=recordvalue:integer;L:listofprocess;end

其中:value的值表示可用资源的数目;L:为等待此类资源的进程PCB表链。3.1进程的同步3.1.3信号量机制一、信号量123.1进程的同步3.1.3信号量机制二、P—V操作1.P操作：wait(s)功能：请求系统分配一个单位的资源参数：信号量S流程：3.1进程的同步3.1.3信号量机制二、P—V操作1.133.1进程的同步3.1.3信号量机制二、P—V操作2.V操作：signal(s)功能：释放一个单位的资源参数：信号量S流程：3.1进程的同步3.1.3信号量机制二、P—V操作2.143.1进程的同步3.1.3信号量机制三、信号量的应用1.实现进程互斥

进程间由于共享资源而引起的间接制约关系

例如：PA、PB共享一临界资源设互斥信号量S，初值为1，表示没有并发进程使用临界区设信号量赋初值：实现：3.1进程的同步3.1.3信号量机制三、信号量的应用1153.1进程的同步3.1.3信号量机制三、信号量的应用1.实现进程互斥为临界资源设置一个互斥信号量S，其初值为1；在每个进程中将临界区代码置于P(S)和V(S)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏3.1进程的同步3.1.3信号量机制三、信号量的应用1163.1进程的同步3.1.3信号量机制三、信号量的应用1.实现进程互斥

问(1)该例中S.value的取值范围(2)PA在临界区访问,PB等待,某时刻PA执行完临界区代码,执行V(S)后,问PB的状态变化?(3)若有n个进程共享一临界资源，则信号量的取值范围?3.1进程的同步3.1.3信号量机制三、信号量的应用1173.1进程的同步3.1.3信号量机制三、信号量的应用2.实现进程同步

进程间由于相互合作而引起的直接制约关系

例如：计算进程和打印进程共享一缓冲区,缓冲区最多放一个数,计算进程反复把每次计算结果放入缓冲区中,而打印进程则把计算进程每次放入缓冲区中的数据通过打印机打印输出。设信号量赋初值：分析：实现：3.1进程的同步3.1.3信号量机制三、信号量的应用2183.1进程的同步3.1.3信号量机制三、信号量的应用

问(1)在该问题中需要考虑互斥吗?为什么?(2)若为缓冲池,池中有多个缓冲块,可放多个产品（数），考虑互斥吗?为什么?----生产者、消费者问题2.实现进程同步结论：若临界区有一个可用资源单位，同步便实现了互斥。若临界区有多个可用资源，必须考虑互斥。3.1进程的同步3.1.3信号量机制三、信号量的应用193.1进程的同步3.1.3信号量机制三、信号量的应用2.实现进程同步例如：设在公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客一方面只有售票员关好车门后司机才能启动车辆，另一方面只有司机到站停车后售票员才能开车门。请分析司机和售票员之间的同步关系，并用信号量的P、V操作来实现。3.1进程的同步3.1.3信号量机制三、信号量的应用2203.1进程的同步3.1.3信号量机制三、信号量的应用2.实现进程同步答：两个同步：关车门----〉启动车辆run=0;到站停车----〉开车门stop=0;司机：售票员：上乘客p(run)关车门启动车辆v(run)正常行车售票到站停车p(stop)v(stop)开车门下乘客3.1进程的同步3.1.3信号量机制三、信号量的应用2213.描述前趋图本题是典型的同步问题。即进程A执行完后才可执行进程B，只需在两进程间设置信号量，当进程A执行结束后执行V操作，通知进程B可以开始，而进程B在开始之前先执行P操作，直到得到进程A的消息。信号量机制三、信号量的应用3.描述前趋图本题是典型的同步问题。即进程A执行完后22同步关系如下：begins12=0;s13=0;s24=0;s36=0;s46=0;s45=0;s57=0;s67=0Parbeginbegins1;v(s12);v(s13);end;beginp(s12);s2;v(s24);end;beginp(s13);s3;v(s36);end;beginp(s24);s4;v(s45);v(s46);end;beginp(s45);s5;v(s57);end;beginp(s46);p(s36);s6;v(s67);end;beginp(s57);p(s67);s7;end;parend;end信号量机制三、信号量的应用3.描述前趋图同步关系如下：信号量机制三、信号量的应用3.描述前趋图234.解决生产者—消费者问题问题描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。三、信号量的应用信号量机制4.解决生产者—消费者问题问题描述：有一群生产者进程在生产产24信号量机制三、信号量的应用4.解决生产者—消费者问题设信号量赋初值：分析：实现：注意：在每个程序中的多个p操作顺序不能颠倒。应先执行对资源信号量的p操作，然后再执行对互斥信号量的p操作，否则可能引起进程死锁。信号量机制三、信号量的应用4.解决生产者—消费者问题设信号量25三、信号量的应用

三个进程P0、P1、P2和三个缓冲区B0、B1、B2。进程间借助于相邻缓冲区传递消息：Pi每次从Bi中取一条消息，经加工送入B（i+1）mod3中，B0、B1、B2分别可存放3、2、2个消息。初始时，仅B0有一个消息。1．分析三个进程间的同步、互斥关系。2．用P、V操作写出P0、P1、P2的同步及互斥流程。例1:信号量机制三、信号量的应用三个进程P0、P1、P2和三个缓冲区26三、信号量的应用

三个进程P0、P1、P2和三个缓冲区B0、B1、B2。进程间借助于相邻缓冲区传递消息：Pi每次从Bi中取一条消息，经加工送入B（i+1）mod3中，B0、B1、B2分别可存放3、2、1个消息。初始时，仅B0有一个消息。1．分析三个进程间的同步、互斥关系。2．用P、V操作写出P0、P1、P2的同步及互斥流程。例2:信号量机制三、信号量的应用三个进程P0、P1、P2和三个缓冲区27三、信号量的应用一组生产者进程和一组消费者进程共享10个缓冲区，每个缓冲区可以存放一个整数；生产者进程每次一次性向3个缓冲区中写入数据，消费者进程每次从缓冲区取出一个整数。1．分析进程间的同步、互斥关系。2．用P、V操作写出进程间的同步及互斥流程。例3:信号量机制三、信号量的应用一组生产者进程和一组消费者进程共28信号量机制三、信号量的应用5.解决读者—写者问题问题描述：

读者间可同时访问共享资源。任一写者必须与其它写者或读者互斥访问共享资源设信号量赋初值：分析：实现：信号量机制三、信号量的应用5.解决读者—写者问题问题描述：设293.1进程的同步3.1.4信号量集机制一、AND型信号量集机制1.引入：执行时3.1进程的同步3.1.4信号量集机制一、AND型信号30第三章进程的同步与通信3.1进程的同步3.2进程通信第三章进程的同步与通信3.1进程的同步313.1进程的同步3.1.1临界区3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现3.1.3信号量机制进程同步的主要任务：使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的并发执行具有可再现性。3.1进程的同步3.1.1临界区进程同步的323.1.1临界区一、临界区1.临界资源：2.临界区：3.1进程的同步一次仅允许一个进程访问的资源例：进程PA、PB共享内存MS。其中MS分为三个领域，即系统区、进程工作区和数据区。数据区被划分为大小相等的块，每个块中既可能被放有数据，也可能未放有数据。系统区中主要是堆栈S，其中存放那些空数据块的地址。分析其中的临界资源、临界区。访问临界资源的代码段，不允许多个并发进程交叉执行的一段程序3.1.1临界区一、临界区3.1进程的同步一次仅允许一33二、进程间的制约关系

1.间接制约关系(互斥)：2.直接制约关系(同步)：3.1.1临界区由于共享资源引起由于相互合作引起3.1进程的同步受间接制约的各进程在执行顺序上是任意的;一组在异步环境下的并发进程,各自的执行结果互为对方的执行条件,从而限制各进程的执行速度的过程,称为并发进程间的直接制约。二、进程间的制约关系3.1.1临界区由于共享资源引起34三、临界区的进入：

3.1.1临界区临界区必须互斥访问2.同步机制应遵循的准则1.访问过程3.1进程的同步临界区(1)检查临界资源是否被访问，未被访问，转(2)，否则转(1)。(2)进入临界区，并设访问标志恢复访问标志，允许其它进程进入空闲让进忙则等待有限等待让权等待进入区退出区三、临界区的进入：3.1.1临界区临界区必须互斥访问353.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现

可以利用某些硬件指令－－其读写操作由一条指令完成，因而保证读操作与写操作不被打断；这些指令允许对一个字的内容进行检测和修正，或交换两个字的内容。一、利用Test-and-Set指令实现互斥二、利用Swap指令实现进程互斥3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现363.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一、利用Test-and-Set指令实现互斥1.Test-and-Set指令该指令读出标志后设置为TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示资源的两种状态：TRUE表示临界区正被占用（忙），FALSE表示空闲。3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一373.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一、利用Test-and-Set指令实现互斥2.利用TS指令实现进程互斥利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在“进入区”利用TS进行检查：若有进程在临界区时，重复检查；直到其它进程退出时，检查通过；3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现一383.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二、利用Swap指令实现进程互斥1.Swap指令交换两个字（字节）的内容voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二393.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二、利用Swap指令实现进程互斥2.利用Swap实现进程互斥每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key3.1进程的同步3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现二403.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现3.1进程的同步硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点循环测试锁状态,损耗CPU时间。可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上(不公平现象)3.1.2利用硬件的方法解决进程互斥问题—互斥的加锁实现3413.1进程的同步3.1.3信号量机制一、信号量

是对系统中资源及其组织情况的抽象。它由一个记录型数据表示。包含两个数据项:typesemaphore=recordvalue:integer;L:listofprocess;end

其中:value的值表示可用资源的数目;L:为等待此类资源的进程PCB表链。3.1进程的同步3.1.3信号量机制一、信号量423.1进程的同步3.1.3信号量机制二、P—V操作1.P操作：wait(s)功能：请求系统分配一个单位的资源参数：信号量S流程：3.1进程的同步3.1.3信号量机制二、P—V操作1.433.1进程的同步3.1.3信号量机制二、P—V操作2.V操作：signal(s)功能：释放一个单位的资源参数：信号量S流程：3.1进程的同步3.1.3信号量机制二、P—V操作2.443.1进程的同步3.1.3信号量机制三、信号量的应用1.实现进程互斥

进程间由于共享资源而引起的间接制约关系

例如：PA、PB共享一临界资源设互斥信号量S，初值为1，表示没有并发进程使用临界区设信号量赋初值：实现：3.1进程的同步3.1.3信号量机制三、信号量的应用1453.1进程的同步3.1.3信号量机制三、信号量的应用1.实现进程互斥为临界资源设置一个互斥信号量S，其初值为1；在每个进程中将临界区代码置于P(S)和V(S)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏3.1进程的同步3.1.3信号量机制三、信号量的应用1463.1进程的同步3.1.3信号量机制三、信号量的应用1.实现进程互斥

问(1)该例中S.value的取值范围(2)PA在临界区访问,PB等待,某时刻PA执行完临界区代码,执行V(S)后,问PB的状态变化?(3)若有n个进程共享一临界资源，则信号量的取值范围?3.1进程的同步3.1.3信号量机制三、信号量的应用1473.1进程的同步3.1.3信号量机制三、信号量的应用2.实现进程同步

进程间由于相互合作而引起的直接制约关系

例如：计算进程和打印进程共享一缓冲区,缓冲区最多放一个数,计算进程反复把每次计算结果放入缓冲区中,而打印进程则把计算进程每次放入缓冲区中的数据通过打印机打印输出。设信号量赋初值：分析：实现：3.1进程的同步3.1.3信号量机制三、信号量的应用2483.1进程的同步3.1.3信号量机制三、信号量的应用

问(1)在该问题中需要考虑互斥吗?为什么?(2)若为缓冲池,池中有多个缓冲块,可放多个产品（数），考虑互斥吗?为什么?----生产者、消费者问题2.实现进程同步结论：若临界区有一个可用资源单位，同步便实现了互斥。若临界区有多个可用资源，必须考虑互斥。3.1进程的同步3.1.3信号量机制三、信号量的应用493.1进程的同步3.1.3信号量机制三、信号量的应用2.实现进程同步例如：设在公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客一方面只有售票员关好车门后司机才能启动车辆，另一方面只有司机到站停车后售票员才能开车门。请分析司机和售票员之间的同步关系，并用信号量的P、V操作来实现。3.1进程的同步3.1.3信号量机制三、信号量的应用2503.1进程的同步3.1.3信号量机制三、信号量的应用2.实现进程同步答：两个同步：关车门----〉启动车辆run=0;到站停车----〉开车门stop=0;司机：售票员：上乘客p(run)关车门启动车辆v(run)正常行车售票到站停车p(stop)v(stop)开车门下乘客3.1进程的同步3.1.3信号量机制三、信号量的应用2513.描述前趋图本题是典型的同步问题。即进程A执行完后才可执行进程B，只需在两进程间设置信号量，当进程A执行结束后执行V操作，通知进程B可以开始，而进程B在开始之前先执行P操作，直到得到进程A的消息。信号量机制三、信号量的应用3.描述前趋图本题是典型的同步问题。即进程A执行完后52同步关系如下：begins12=0;s13=0;s24=0;s36=0;s46=0;s45=0;s57=0;s67=0Parbeginbegins1;v(s12);v(s13);end;beginp(s12);s2;v(s24);end;beginp(s13);s3;v(s36);end;beginp(s24);s4;v(s45);v(s46);end;beginp(s45);s5;v(s57);end;beginp(s46);p(s36);s6;v(s67);end;beginp(s57);p(s67);s7;end;parend;end信号量机制三、信号量的应用3.描述前趋图同步关系如下：信号量机制三、信号量的应用3.描述前趋图534.解决生产者—消费者问题问题描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程