进程的并发控制互斥与同步课件

第三章进程的并发控制

——互斥与同步与时间有关的错误问题进程协调的概念对临界区管理的准则简单的同步机制（标志法）信号量机制（实现进程互斥与同步的控制）第三章进程的并发控制

——互斥与同步与时间有关的错误问13.1程序的两种执行方式程序的顺序执行程序在运行的时独占系统资源，且系统按照程序步骤顺序执行地执行，在该程序执行完之前，其他程序只能等待。程序的并发执行多道程序设计的系统中，若干个作业可以同时执行，这些进程轮流地占用CPU，即一个进程的工作没有全部完成之前，另一个进程就可开始工作，我们说这些执行的进程具有并发性。3.1程序的两种执行方式程序的顺序执行23.1与时间有关的错误问题(1)问题描述：设有一个游乐场设置了一个自动计算机系统，用一个变量count指示在场的人数，当有人进入，则PIN进程完成count++，当有人退出，则POUT进程完成count--进程PINProcessPIN{intR1;R1=count;R1=R1+1;count=R1;}进程POUTProcessPOUT{intR2;R2=count;R2=R2-1;count=R2;}3.1与时间有关的错误问题(1)问题描述：设有一个游乐场设33.1与时间有关的错误问题(1)两个进程的顺序执行（不产生错误）假设某一时刻count=n

intR1;R1=count;R1=R1+1;count=R1;intR2;R2=count;R2=R2-1;count=R2;正确结果count=n不变假设某一时刻count=nintR2;R2=count;R2=R2-1;count=R2;intR1;R1=count;R1=R1+1;count=R1;正确结果count=n不变3.1与时间有关的错误问题(1)两个进程的顺序执行（不产生43.1与时间有关的错误问题(1)并发执行一种错误的可能结果：假设某一时刻count=n

R1=count;count=n

R1=R1+1;PIN进程被挂起R2=count;R2=R2-1;count=n-1

count=R2;POUT进程结束，PIN唤醒count=R1;错误的结果值count=n+1，实际该为n3.1与时间有关的错误问题(1)并发执行一种错误的可能结果：53.1与时间有关的错误问题(1)并发执行另一种错误的可能结果：假设某一时刻count=nR1=count;count=n

R1=R1+1;PIN进程被挂起;R1=n+1R2=count;count=n

R2=R2-1;POUT进程被挂起，PIN唤醒R2=n-1

count=R1;PIN进程结束，POUT唤醒count=n+1count=R2;POUT进程结束，count=n-1错误的结果值count=n-1，实际该为n3.1与时间有关的错误问题(1)并发执行另一种错误的可能结果63.1与时间有关的错误问题(1)分析产生错误的可能原因一个进程运行时由于自身或外界的原因可能被中断，且断点是不固定的。进程执行的相对速度不能由自己来控制两个并发进程使用共享的变量count两个进程在不同时间里访问count变量，可能得到相同的count变量值。3.1与时间有关的错误问题(1)分析产生错误的可能原因73.1与时间有关的错误问题(2)问题描述：设一个飞机航班售票系统有n个售票处，每个售票处通过终端访问系统公共数据区，假定公共数据区中的一些单元Aj（j=1，2，……）分别存放某年某月某日某次航班的剩余票数。设P1，P2，…，Pn表示各个售票处的处理进程，R1，R2，…，Rn表示各进程执行时所用的工作单元，当各售票处有旅客买票时，进程工作如下：3.1与时间有关的错误问题(2)问题描述：设一个飞机航班售票83.1与时间有关的错误问题(2)可能产生的错误结果

可能有若干个旅客在几乎相同的时间里到不同的售票处要求购买同一天同一航班的机票，于是若干进程都要访问同一个Aj，则结果可能出现同一张票卖给几个不同的旅客ProcessPi（i=1，2，…，n）{根据用户需求找到Aj;

Ri=Aj;if(Ri>=1){Ri=Ri-1;Aj=Ri;提示已卖出一张票信息；}else输出“票已售完”；}3.1与时间有关的错误问题(2)可能产生的错误结果Proce93.1与时间有关的错误问题(2)假设某一个时刻三个客户在不同网点但几乎同时到达购票访问的情况进程t1t2t3t4t5P1R1=Aj……R1=R1-1Aj=R1P2R2=Aj……R2=R2-1Aj=R2P3R3=AjR3=R3-1……3.1与时间有关的错误问题(2)假设某一个时刻三个客户在不同103.2进程的协调概念在os支持下，多个进程既独立又并发执行，然而进程之间可能合作完成一项任务，可能共享一种系统资源，可能相互支持和依赖，甚至制约对方，为了协调进程间的关系，os必须进行进程间的协调。

3.2进程的协调概念在os支持下，多个进程既独立又并发执行113.2进程的制约关系直接相互制约关系

源于进程的合作，同步关系如：A、B两个进程通过缓冲区合作完成一项任务，A负责存数据到缓冲区，B负责从缓冲区中取数。间接相互制约关系

源于资源共享，互斥关系如：A、B两个进程共享打印机，若分配给A，则当B需要打印机时被阻塞而等待3.2进程的制约关系直接相互制约关系123.2进程的互斥与同步进程间具有一种互斥关系也就是说对于某个系统资源，如果一个进程正在使用，其他进程就必须等待其用完，不能同时使用。进程间具有一种同步关系即多个相关的进程在执行次序上需要协调，如当两个进程或多个进程合作完成一个任务，在并发执行中，一个进程需等待其合作伙伴发送消息或建立条件再向前执行，这种制约关系通常称为进程的同步。3.2进程的互斥与同步进程间具有一种互斥关系13几个专业术语临界资源一次只允许一个进程使用的资源广义上，包括物理实体资源，如：打印机

软件资源，如：变量、文件等临界区一个进程访问这种临界资源的那段程序代码，称为临界区几个专业术语临界资源14几个专业术语剩余区除临界区外的其余代码说明：进程互斥的再定义，就是两个进程不能同时进入访问同一临界资源的临界区操作系统中实现互斥和同步的机制统称为同步机制几个专业术语剩余区153.3临界区的管理准则－P79操作系统的进程同步机制必须遵循如下准则空闲让进忙则等待有限等待让权等待3.3临界区的管理准则－P79操作系统的进程同步机制必须遵163.3临界区的管理准则空闲让进当无进程处于临界区时，允许一个进程进入忙则等待当有进程在临界区，其他欲进入临界区的进程须等待，否则无需等待（一次至多一个进程能够进入临界区）3.3临界区的管理准则空闲让进173.3临界区的管理准则有限等待对要求进入临界区的进程，应在有限时间内让其进入，避免“死等”（不能让一个进程无限在临界区执行，任何进入临界区的进程必须在有限时间内退出）3.3临界区的管理准则有限等待18临界区的管理准则让权等待临界区让出，必须立即释放CPU，让等待进程进入，避免“忙等”（不能让一个进程无限等待进入，即有进程退出临界区时，应让等待进程进入临界区执行）临界区的管理准则让权等待193.4简单的同步机制－标志位机制进程互斥问题的软件解决方法轮流标志法（单标志法）双标志法三标志法3.4简单的同步机制－标志位机制进程互斥问题的软件解决方法203.4简单的同步机制－单标志位法算法的基本思想设置一个标志变量turn，两个进程P0、P1要进入临界区先要访问该标志，根据标志值决定自己是否进入临界区。例如当turn=0，表示允许P0进程进入，当P0退出临界区后，置turn=1，P1才可进入临界区；反之当turn＝1，表示允许P1进程进入，退出时置turn=0，则P0才可进入。3.4简单的同步机制－单标志位法算法的基本思想213.4简单的同步机制－单标志位法ProcessP0{do{

while(turn!=0);

临界区turn=1;

剩余区}while(1);}ProcessP1{do{

while(turn!=1);

临界区turn=0;

剩余区}while(1);}初始值turn=0;或者turn=1;3.4简单的同步机制－单标志位法ProcessP0Pro223.4简单的同步机制－单标志位法该算法的致命缺点要求进入临界区执行的两个进程必须严格的交替运行。当进程A大于进程B时，将阻塞进程B再次进入临界区（因为交替原则，B必须等待A执行结束），即产生了长进程阻塞短进程的问题。不满足临界区管理的第一个准则，因为存在一个进程当它在剩余区时，也不允许另一个进程进入临界区。3.4简单的同步机制－单标志位法该算法的致命缺点233.4简单的同步机制－双标志位法算法的基本思想先修改后检查算法为每个进程都设置一个标志位，引入数组flag[2]，初始化为false，表示临界区中无进程，欲进入者可以进入。进程Pi欲进入时将自身标志flag[i]置为true，阻止另一个进程进入，接着判定对方的标志是否为false，若是才可以进入临界区，否则必须等待；任一个进程退出临界区后都将自身标志置为false，表示退出临界区，允许对方进程进入临界区。3.4简单的同步机制－双标志位法算法的基本思想243.4简单的同步机制－双标志位法(1)算法的主要伪代码ProcessP0{do{flag[0]=true;

while(flag[1]);

临界区

flag[0]=false;剩余区}while(1);}ProcessP1{do{flag[1]=true;

while(flag[0]);

临界区

flag[1]=false;剩余区}while(1);}初始值flag[i]=false3.4简单的同步机制－双标志位法(1)算法的主要伪代码Pr253.4简单的同步机制－双标志位法(1)算法的特点可以解决两个进程严格交替的问题但当两个进程几乎同时到达时，结果两个进程都不能进入临界区执行产生死锁问题可能导致对方进程的“饥饿”问题，将永远被阻塞不满足管理准则中的“空闲让进”3.4简单的同步机制－双标志位法(1)算法的特点263.4简单的同步机制－双标志位法(2)算法的基本思想先检查算法交换修改与检查语句的顺序，先做while检查，再做true值的设置修改3.4简单的同步机制－双标志位法(2)算法的基本思想273.4简单的同步机制－双标志位法(2)算法的主要伪代码ProcessP0{do{while(flag[1]);flag[0]=true;

临界区flag[0]=false;

剩余区}while(1);}ProcessP1{do{while(flag[0]);flag[1]=true;

临界区flag[1]=false;

剩余区}while(1);}3.4简单的同步机制－双标志位法(2)算法的主要伪代码Pr283.4简单的同步机制－双标志位法(2)算法的致命缺点比前两种方法更差，不能解决互斥问题导致所有进程都可以进入临界区不满足管理准则中的“忙则等待”3.4简单的同步机制－双标志位法(2)算法的致命缺点293.4简单的同步机制－三标志位法算法的基本思想先修改、后检查、后修改者等待算法为了解决两个进程的同时到达问题，将前两者算法结合，在双标志法的基础上再引入turn变量，当两个进程几乎同时到达时，进程根据turn值决定哪一个进程进入临界区，即保证任一个时刻，turn值为0或者为1，使得只有一个进程满足条件而进入临界区。3.4简单的同步机制－三标志位法算法的基本思想303.4简单的同步机制－三标志位法算法的主要伪代码ProcessP0{do{flag[0]=true;turn=1;while(flag[1]&&turn==1);

临界区flag[0]=false;

剩余区}while(1);}ProcessP1{do{flag[1]=true;turn=0;while(flag[0]&&turn==0);

临界区flag[0]=false;

剩余区}while(1);}3.4简单的同步机制－三标志位法算法的主要伪代码Proce313.4简单的同步机制－三标志位法两个进程几乎同时到达的情况flag[0]=true;

flag[1]=true;

turn=1;

while(flag[1]&&turn==1);//P0被挂起turn=0;//后修改者即P1

while(flag[0]&&turn==0);//P1被挂起，P0被解除

临界区//P0进入临界区flag[0]=false;//P0退出，P1可被解除

剩余区//P0的剩余区

…………3.4简单的同步机制－三标志位法两个进程几乎同时到达的情况323.4简单的同步机制－三标志位法两个进程几乎同时到达的情况flag[0]=true;

flag[1]=true;

turn=1;turn=0;//后修改者P1

while(flag[0]&&turn==0);//P1被挂起

while(flag[1]&&turn==1);//P0被批准进入

临界区//P0进入临界区flag[0]=false;//P0退出，P1可被解除

剩余区//P0的剩余区

…………3.4简单的同步机制－三标志位法两个进程几乎同时到达的情况333.4简单的同步机制－三标志位法两个进程几乎同时到达的情况flag[0]=true;

flag[1]=true;

turn=0;turn=1;//后修改者P0

while(flag[1]&&turn==1);//P0被挂起

while(flag[0]&&turn==0);//P1被批准进入

临界区//P1进入临界区flag[1]=false;//P1退出，P0可被解除

剩余区//P1的剩余区

…………3.4简单的同步机制－三标志位法两个进程几乎同时到达的情况343.4简单的同步机制－三标志位法算法的特点满足管理准则，空闲让进，忙则等待等解决进程的互斥与并发实现较复杂系统开销大3.4简单的同步机制－三标志位法算法的特点353.4简单的同步机制四个算法的共同缺点只适合解决两进程的互斥问题不能处理进程的同步问题3.4简单的同步机制四个算法的共同缺点363.5信号量机制信号量协调机制可实现2个或2个以上的进程协调。既可用与互斥，也可用用于同步。信号量（semaphore）是由荷兰计算机科学家E.W.Dijkstra于1965年提出的，它取自交通管理中的信号灯的概念。3.5信号量机制信号量协调机制可实现2个或2个以上的进程协373.5信号量机制信号量的基本概念信号量是用于控制进程互斥与同步的物理变量信号量S（通常用S表示）是一个整型变量，初始值为非负数每个信号量S对应设置了一个等待队列对信号量的操作只能通过PV操作进行3.5信号量机制信号量的基本概念383.5信号量机制－－PV操作P操作和V操作都是不可分割的原子操作，也叫原语P操作可以记为P(S)，wait(S)或者down(S)V操作可以记为V(S)，signal(S)或者up(S)为减化，我们用P(S)和V(S)表示，教材采用wait()和signal()表示3.5信号量机制－－PV操作P操作和V操作都是不可分割的原393.5信号量机制－－PV操作Dijkstra把互斥和同步的关键含义抽象成信号量(semaphore)概念，并引入在信号量上的P、V操作作为同步原语(P和V分别是荷兰文的“等待”和“发信号”两词的首字母)。PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。3.5信号量机制－－PV操作Dijkstra把互斥和同步的403.5信号量机制－－P操作P(S)操作的定义S值减一若S<0，阻塞当前进程，将其插入到等待S的队列若S>=0，当前进程继续运行(说明等待队列无进程，当前进程可继续不阻塞)P操作的伪代码P(ints){s--;if(s<0)wait();//当前被挂起return;//当前继续}3.5信号量机制－－P操作P(S)操作的定义P操作的伪代码413.5信号量机制－－V操作V(S)操作的定义S值加一；若S<=0，从等待S的队列中移出一个进程，由阻塞态转为就绪态，插入就绪队列若S>0，当前进程继续执行（说明等待队列无进程，无需执行唤醒操作）V操作的伪代码V(ints){s++;if(s<=0)wakeup();

//移出一个进程，插入就绪队列，相当唤醒return;//当前继续}3.5信号量机制－－V操作V(S)操作的定义V操作的伪代码423.5信号量机制－－解决互斥问题如果有若干个进程都调用P操作(提出申请)，则只有第一个调用P操作的进程不成为等待状态而可以继续执行P操作第一次调用后，S的值成为“0”，以后的进程调用P操作时，S值总小于0（S<0,因为S--），进程被阻塞置为等待状态而不能继续执行直到有一个进程退出临界区，调用一次V操作后，才释放一个等待者。设S=1;{P(S);临界区V(S);}3.5信号量机制－－解决互斥问题如果有若干个进程都调用P操433.5信号量机制－－解决互斥问题能实现对临界区管理的要求当无进程在临界区时，若有进程要进入临界区则允许一个进程立即进入它的临界区；当有一个进程在临界区执行时，其他试图进入临界区的进程必须等待；当有一个进程离开临界区时，若有等待进入临界区的进程，则允许其中一个进程进入它的临界区。系统中的共享资源均有一个信号量与之对应，OS按其状态对进程和资源进行管理3.5信号量机制－－解决互斥问题能实现对临界区管理的要求443.5信号量机制－－解决互斥问题实现互斥的方法首先判断临界资源其次判断相关的代码即临界区定义信号量的个数设置信号量初始值在进入临界区之前调用P操作，相当申请进入临界区。在退出临界区之后调用V操作，相当唤醒等待进程进入临界区3.5信号量机制－－解决互斥问题实现互斥的方法453.5信号量机制－－游乐场问题游乐场关于计数的两个进程进程P2Processp2{intR2;R2=count;R2=R2-1;count=R2;}进程P1Processp1{intR1;R1=count;R1=R1+1;count=R1;}3.5信号量机制－－游乐场问题游乐场关于计数的两个进程进程463.5信号量机制－－游乐场问题分析上述进程，找到临界资源即count这个全局共享变量分析有关对count变量进行操作的代码即临界区，包括三条语句一个共享资源count变量对应一个信号量，信号量S表示由于每次只能让一个进程使用，且共享的资源个数为1，所以信号量S的初始值为13.5信号量机制－－游乐场问题分析上述进程，找到临界资源即473.5信号量机制－－游乐场问题 互斥信号量S初值为1说明了任意时刻只允许一个进程进入临界区，其他想进入的进程只能等待Processp2{intR2;

P(S);R2=count;R2=R2-1;count=R2;

V(S);}Processp1{intR1;

P(S);R1=count;R1=R1+1;count=R1;V(S);}SemaphoreS;S=1;3.5信号量机制－－游乐场问题 互斥信号量S初值为1说明了483.5信号量机制－－游乐场问题这是两个进程互斥的问题对信号量S的分析S＝1，表示当前共享资源只有一个可供使用，一次只能允许一个进程使用。（且任何时刻只能一个进程进入临界区，其他欲进入的进程必须等待——互斥概念）S＝0，表示有一个进程在临界区，无可用资源，无等待进程3.5信号量机制－－游乐场问题这是两个进程互斥的问题对信号493.5信号量机制－－游乐场问题这是两个进程互斥的问题S＝-1，表示有一个等待的进程S的取值范围：（1，0，-1）|S|的含义：表示有|S|个进程在等待3.5信号量机制－－游乐场问题这是两个进程互斥的问题503.5信号量机制－－订票系统问题飞机订票系统关于联网订票的进程Processpi{intR;根据用户需求找到Aj;if(Aj>=1){R=Aj;R=R-1;Aj=R;提示已卖出一张票信息；}else输出票已售完；}3.5信号量机制－－订票系统问题飞机订票系统关于联网订票的513.5信号量机制－－订票系统问题解决互斥方法一Processpi{intR;根据用户需求找到Aj;if(Aj>=1){P(S);R=Aj;R=R-1;Aj=R;V(S);提示已卖出一张票信息；}else输出票已售完；}SemaphoreS=1;思考：互斥问题是否得到解决？如果没有，原因在哪？3.5信号量机制－－订票系统问题解决互斥方法一Proces523.5信号量机制－－订票系统问题法一的问题分析表面上看实现互斥的管理，实际上仍然存在读取相同Aj值的情况分析判定共享资源应该是：Aj变量分析判定临界区：包括所有对Aj变量操作的代码区注意：若查询结果是无票，虽不影响临界区的使用，不产生错误，但存在潜在的错误3.5信号量机制－－订票系统问题法一的问题分析533.5信号量机制－－订票系统问题互斥解法二SemaphoreS=1;Processpi（修改进程的表示）{intR;根据用户需求找到Aj；R=Aj;if(R>=1){R=R-1;Aj=R;提示已卖出一张票信息；}else输出票已售完；}Processpi（I=1，2，……n）{intR;根据用户需求找到Aj；

P(S);R=Aj;if(R>=1){R=R-1;Aj=R;

V(S);提示已卖出一张票信息；}else输出票已售完；}3.5信号量机制－－订票系统问题互斥解法二Semaphor543.5信号量机制－－订票系统问题法二的问题分析PV操作没有成对出现对第一个查询结果无票的进程而言，能顺利退出临界区，但后续进程均被挂起，不能得到响应导致系统内部存在“饥饿”进程3.5信号量机制－－订票系统问题法二的问题分析553.5信号量机制－－订票系统问题正确的解法SemaphoreS=1;Processpi{intR;

P(S);根据用户需求找到Aj；R=Aj;if(R>=1){R=R-1;Aj=R;

V(S);提示已卖出一张票信息；}else{V(S);输出票已售完}}说明：准确判断临界区是非常重要的，但要注意在退出临界区是否执行了V操作，要注意PV操作的成对性3.5信号量机制－－订票系统问题正确的解法Semaphor563.5信号量机制－－订票系统问题对信号量S的分析S＝1，表示当前共享资源只有一个可供使用。（且任何时刻只能一个进程进入临界区，其他欲进入的进程必须等待——互斥概念）S＝0，表示有一个进程在临界区，无可用资源S＝-1，-2……表示有1个、2个…等待的进程S的取值范围：(-(n-1)～1)|S|的含义：表示有|S|个进程在等待这是n个进程的互斥问题3.5信号量机制－－订票系统问题对信号量S的分析这是n个进573.5信号量机制－－同步问题假设缓冲区一次只能放一个物品缓冲区进程B（消费者）进程A（生产者）存取读加工问题：如果两个进程不相互制约的话会造成什么错误？3.5信号量机制－－同步问题假设缓冲区一次只能放一个物品缓583.5信号量机制－－同步问题问题分析在B还没来得及从缓冲区中取走当前数据之前，A又存入一个新记录，则引起数据被覆盖的错误在A还没来得及生产新的数据之前，B又从缓冲区中取走相同的数据，导致重复取记录的错误3.5信号量机制－－同步问题问题分析593.5信号量机制－－同步问题错误的原因AB两个进程的执行速度不同步造成，A比B快，或B比A快，所以AB进程需同步，需要协调说明：进程的同步关系源于进程的合作（协作）3.5信号量机制－－同步问题错误的原因603.5信号量机制－－解决同步问题问题提出要实现进程同步就必须提供一种机制，该机制能测试进程所需的消息是否到达，也能把它所需的消息发送出去实现思想用一个信号量与一个消息联系起来，当信号量的值为“0”时，表示期望的消息还没有产生，当信号量的值为非“0”时表示期望的消息已经存在。3.5信号量机制－－解决同步问题问题提出61实现方法通过调用P操作可以测试自己所期望的消息是否到达（相当申请进入临界区）而任何进程要向其它进程发送消息时（相当唤醒下一个进程进入临界区）可以调用V操作3.5信号量机制－－解决同步问题实现方法3.5信号量机制－－解决同步问题623.5信号量机制－－解决同步问题实现原理P操作的理解用信号量S表示一种消息，如果消息还没有产生，则S＝0，调用P(S)操作后，调用者将成为等待状态，申请进入临界区失败。如果消息已经存在，则S>0,调用P(S)操作后，调用者不会成为等待状态，即申请进入临界区成功。3.5信号量机制－－解决同步问题实现原理633.5信号量机制－－解决同步问题实现原理V操作的理解若调用V(S)操作前S＝0，表示消息还没有产生也没有等待消息的进程，这时调用V(S)操作后，S!=0，调用V(S)后，意味着消息产生，即相当通知或者唤醒操作。若调用V操作前S<0，表示消息还没有产生且有进程在等待该消息，这时调用V(S)操作后将释放一个在等待消息的进程，即调用V(S)操作的进程把消息发给在等待消息的进程且允许它继续进行，即相当通知或者唤醒操作。3.5信号量机制－－解决同步问题实现原理643.5经典同步问题

—生产者/消费者问题生产者与消费者问题描述现假定有一个生产者和一个消费者，他们共用一个缓冲器，生产者不断地生产物品，每生产一件物品就要存入缓冲器，但缓冲器中每次只能存入一件物品，只有当消费者把物品取走后，生产者才能把第二件物品存入缓冲器。同样地，消费者不断地取出物品去消费，当缓冲器中有物品时他就可以去取，每取走一件物品后必须等生产者放入一件物品才可再取。3.5经典同步问题

653.5经典同步问题

—生产者/消费者问题生产者进程和消费者进程（未采用同步机制前的主要代码）Processproducer{L1:produceaproduct;

Buffer=product;gotoL1;}Processconsumer{L1:takeaproduct

fromBuffer;consume;gotoL1;}3.5经典同步问题

663.5经典同步问题

—生产者/消费者问题问题分析消息的个数：2个需要的信号量两个，定义两个变量SP、SG分别表示生产者和消费者的信号量(私有信号量)两个进程生产和消费各自独立，并发执行两个进程只在访问公共的缓冲器把物品存入或取出时才要互通消息3.5经典同步问题

673.5经典同步问题

—生产者/消费者问题信号量初值的分析初始状态，缓冲器为空，允许生产者生产的物品存入缓冲器，相当于通知消费者进程取物品的消息已经到了，代表此消息的信号量SP初值应该为“1”。初始状态，缓冲区为空，不能取数消费，也就不能通知再生产，所以对应信号量SG的初值应该为“0”。3.5经典同步问题

683.5经典同步问题

—生产者/消费者问题信号量的定义SemaphoreSP,SG;SP=1;SG=0;SP：表示是否可以把物品存入缓冲区，由于缓冲区每次只能放一个物品，所以初值为1。SG：表示缓冲区是否存在有物品，显然初值为0，表示开始还没有物品在缓冲区。3.5经典同步问题

693.5经典同步问题

—生产者/消费者问题实现的基本方法生产者进入缓冲区前调用P操作判断消息是否到达，或者说申请进入的消息是否允许通过，退出缓冲区时，调用V操作发送消息通知消费者，相当唤醒消费者消费者在进入缓冲区前，首先调用P操作判断是否可以取数，即通知取数的消息是否到达，当取数后退出缓冲区，调用V操作，发送消息，通知生产者3.5经典同步问题

703.5经典同步问题

—生产者/消费者问题将PV操作加入到原来的伪代码中，结果如下SemaphoreSP,SG;SP=1;SG=0;intBuffer;Processproducer{L1:produceaproduct;

P(SP);

Buffer=product;

V(SG);gotoL1;}Processconsumer{L1:

P(SG);

takeaproduct

fromBuffer;

V(SP);

consume;gotoL1;}3.5经典同步问题

713.5经典同步问题

—生产者/消费者问题分析下列几种情况，看PV操作是否能管理：先生产再消费，然后再生产再消费的同步过程(可以)先生产，然后想再生产，是否可行？（不行）如果再次生产失败则转为消费，消费后再生产，但如果消费后企图再消费是否可行？（不行）一开始就要消费，是否可行？(不行)开始没有产品，不能消费，结果必然转为生产3.5经典同步问题

723.5经典同步问题

—生产者/消费者问题分析SP和SG的取值范围缓冲器任何时候只允许一个进程使用。两个进程，当生产者/消费者在缓冲器内，消费者/生产者只能等待，所以等待的进程个数最多一个。取值范围(-1，0,1)3.5经典同步问题

733.5经典同步问题

—生产者/消费者共享容量n的缓冲区问题变为：一个生产者和一个消费者共享容量为n的缓冲区的同步问题0123456……n-2n-1生产k取数t3.5经典同步问题

—生产743.5经典同步问题

—生产者/消费者共享容量n的缓冲区变量k和t的理解 由于缓冲区的容量为n，则必须考虑：生产者生产的物品存入缓冲区的哪个位置，以及消费者取出的物品来自缓冲区的哪个位置，因此相应需要增加k和t两个变量表示生产者往缓冲区存物品和消费者从缓冲区中取物品的相对位置，它们的初值为“0”。即定义intk=0,t=0;3.5经典同步问题

—生产753.5经典同步问题

—生产者/消费者共享容量n的缓冲区生产者和消费者的进程表示如下：

(还没有实现同步机制前)Processproducer{L1：produceaproduct;B[k]=product;

k=(k+1)%n;gotoL1;}Processconsumer{L1：takeaproductfromB[t];t=(t+1)%n;gotoL1;}3.5经典同步问题

—生产763.5经典同步问题

—生产者/消费者共享容量n的缓冲区信号量的定义需要传送的消息个数：2个（不变）定义2个信号量：分别用SP，SG表示信号量的初始化SP：初值为“n”，表示开始有n个空闲区可以放置物品SG：初值为“0”，表示开始没有物品在缓冲区中3.5经典同步问题

—生产773.5经典同步问题

—生产者/消费者共享容量n的缓冲区问题提出：在PV操作之前必须准确判断临界区，这里的临界区在哪？Processproducer{L1：produceaproduct;B[k]=product;

k=(k+1)%n;gotoL1;}Processconsumer{L1：takeaproductfromB[t];

t=(t+1)%n;gotoL1;}3.5经典同步问题

—生产783.5经典同步问题

—生产者/消费者共享容量n的缓冲区intB[n],k=0,t=0;SemaphoreSP=n,SG=0;Processproducer{L1：produceaproduct;

P(SP);

B[k]=product;k=(k+1)%n;

V(SG);gotoL1;}Processconsumer{L2：P(SG);

takeaproductfromB[t];t=(t+1)%n;

V(SP);gotoL2;}3.5经典同步问题

—生产793.5经典同步问题

—补充例子 例2：假定有三个进程R，W1，W2共享一个缓冲器B，而B中每次只能存放一个数。当缓冲器中无数时，进程R可将从输入设备上读入的数存放到缓冲器B中。若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。同时规定：进程R必须等缓冲器中的数取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器中的数只能打印一次；W1和W2都不能从空的缓冲器中取数，写出这三个并发进程能正确工作的程序。3.5经典同步问题

803.5经典同步问题

—补充例子进程R的伪代码描述ProcessR{intx;L1:takeanumberfromdevice;//读数x=number;

B=x;//读数后存入缓冲区if(B==奇数)通知w1进程else通知w2进程;gotoL1;}3.5经典同步问题

813.5经典同步问题

—补充例子进程w1,w2的伪代码描述：ProcessW1{inty;L2:

y=B;//取数printthenumbery;gotoL2;}ProcessW2{intz;L3:

z=B;printthenumberz;gotoL3;}3.5经典同步问题

823.5经典同步问题

—补充例子分析问题哪个进程看成是生产者，哪个是消费者？把R看成是生产者，把进程W1和W2看成消费者。生产者(R进程)生产不同的产品(奇数或偶数)，存入缓冲器B，供不同的消费者(W1和W2进程)取用。3.5经典同步问题

833.5经典同步问题

—补充例子需要发送的消息是什么以及消息个数?当进程R读入的是奇数，则要把有奇数的消息发送给进程W1；当进程R读入的是偶数，则要把有偶数的消息发送给W2。在进程W1和W2从缓冲器中取出数后，应把缓冲器中又可以存一个数的消息告诉给进程R。3.5经典同步问题

843.5经典同步问题

—补充例子分析信号量个数及其分别代表的含义 通过上述分析得知，需要发送三个消息，所以需要定义三个信号量，分别用S，SO，SE表示如下：S：表示是否可以把数存入缓冲器，由于缓冲器中每次只能存放一个数，初始缓冲区为空，所以它的初值为“1”SO：表示缓冲器中是否有奇数，初值为“0”，表示开始无奇数SE：表示缓冲器中是否有偶数，初值为“0”，表示开始无偶数3.5经典同步问题

853.5经典同步问题

—补充例子根据上面的分析，得出信号量的定义和变量定义如下：intB;SemaphoreS,SO,SE;S=1;SO=0;SE=0;ProcessR{intx;L1:takeanumberfromdevice;x=number;

P(S);B=x;if(B==奇数)

V(SO);

elseV(SE);gotoL1;}3.5经典同步问题

863.5经典同步问题

—补充例子ProcessW1{inty;L2:

P(SO);y=B;

V(S);printthenumbery;gotoL2;}ProcessW2{intz;L3:

P(SE);z=B;

V(S);printthenumberz;gotoL3;}3.5经典同步问题

873.5经典同步问题

—总结总结进程的互斥实际上是进程同步的一种特殊情况，若干进程互斥使用资源时，一个等待使用资源的进程在等待占用资源的进程发出“归还资源”的消息后，它就可去使用资源。因此互斥使用资源的进程实际上也存在一种一个进程依赖另一个进程发出消息的制约关系。把用来解决进程互斥与同步的机制（如PV操作）称为同步机制3.5经典同步问题

883.5经典同步问题

—总结进程互斥与进程同步是有区别的进程的互斥是进程间竞争共享资源的使用权，这种竞争没有固定的必然联系。哪个进程竞争到使用权则共享资源就归哪个进程使用，直到不需要使用时再归还使用权任何进程可竞争使用空闲的共享资源，即使该进程刚刚使用过该共享资源。若此时无其它进程要使用这个共享资源，那么该进程仍可再次使用该共享资源。3.5经典同步问题

893.5经典同步问题

—总结进程互斥与进程同步是有区别的而进程的同步就不同了，涉及共享资源的并发之间有一种必然的依赖关系。当进程必须同步时，即使没有进程在使用共享资源，还没有得到同步消息的进程也不能去使用这个资源3.5经典同步问题

903.5进程的同步与互斥混合

—生产者与消费者问题叙述 讨论m个生产者和r个消费者怎样共享容量为n的缓冲器，假定每个生产者都要把各自生产的物品存入缓冲器，而每个消费者也都要从缓冲器中取出物品去消费。得出结论 在这个问题中，不仅生产者与消费者之间存在同步，而且m个生产者之间，r个消费者之间还必须互斥的访问缓冲器。3.5进程的同步与互斥混合

913.5进程的同步与互斥混合

—生产者与消费者问题提出 我们发现生产者和消费者之间应该同步这是显而易见的，只有互通消息才能知道是否可以存放物品或者是否可以从缓冲器中取出物品。为什么生产者和消费者之间需要互斥访问缓冲器呢？3.5进程的同步与互斥混合

923.5进程的同步与互斥混合

—生产者与消费者intB[n],k=0,t=0;SemaphoreSP=n,SG=0;Processproduceri(i=1,2…n){L1：produceaproduct;

P(SP);B[k]=product;k=(k+1)%n;

V(SG);gotoL1;}Processproducerj(j=1,2,…n){L2：P(SG);takeaproductfromB[t];t=(t+1)%n;

V(SP);gotoL2;}分析：如果不进行互斥，结果会产生什么样的错误？3.5进程的同步与互斥混合

933.5进程的同步与互斥混合

—生产者与消费者分析理由－生产者如果m个生产者各自生产了物品都要存入缓冲器中，当第一个生产者按指针k指示的位置放入了一件物品，但在改变指针之前可能被打断执行，于是当第二个生产者要存放物品时将仍按原先的指针值所指的位置存放物品，这样两件物品被重复存放在同一位置上由于系统进程生产的物品往往是数据，当重复的在一个位置存放数据，必定是后者覆盖了前者，造成数据的丢失，所以存放物品时必须互斥。3.5进程的同步与互斥混合

943.5进程的同步与互斥混合

—生产者与消费者分析理由－消费者同理，r个消费者都要取物品时，也可能出现从指针t相同的位置取物品，造成一件物品被重复多次取出，这也是错的，因此取物品时也必须互斥。3.5进程的同步与互斥混合

953.5进程的同步与互斥混合

—生产者与消费者同步信号量分析m个生产者和r个消费者之间进行同步操作需要互通的消息还是两个：即缓冲器中是否可以存放物品和缓冲器中是否已经有物品。仍用SP和SG表示，SP的初值为“n”，(n表示缓冲区的空闲个数)，SG的初值仍为“0”。3.5进程的同步与互斥混合

963.5进程的同步与互斥混合

—生产者与消费者互斥信号量分析共享变量k、t是临界资源对共享变量k与t的操作必须互斥，所以定义两个用于互斥的信号量S1和S2信号量S1用于m个生产者之间互斥的往缓冲器中存放物品信号量S2用于r个消费者之间互斥的从缓冲器中取物品S1、S2初值都为“1”，表示开始无进程进入临界区。3.5进程的同步与互斥混合

973.5进程的同步与互斥混合

—生产者与消费者intB[n],k=0,t=0;SemaphoreSP=n,SG=0，S1＝1，S2＝1；Processproduceri(i=1,2…n){L1：produceaproduct;

P(SP);P(S1);B[k]=product;k=(k+1)%n;

V(S1);

V(SG);gotoL1;}Processproducerj(j=1,2,…n){L2：P(SG);P(S2);takeaproductfromB[t];t=(t+1)%n;

V(S2);V(SP);consume;gotoL2;}3.5进程的同步与互斥混合

983.5进程的同步与互斥混合

—生产者与消费者互斥信号量与同步信号量的位置可以交换Processproduceri(i=1,2…n){L1：produceaproduct;

P(S1);

P(SP);B[k]=product;k=(k+1)%n;

V(SG);V(S1);gotoL1;}Processproducerj(j=1,2,…n){L2：P(S2);

P(SG);takeaproductfromB[t];t=(t+1)%n;

V(SP);V(S2);consume;gotoL2;}3.5进程的同步与互斥混合

993.5读者与写者问题问题描述假定有某个共享文件F，系统允许进程对文件F读和写，规定读者与写者互斥，写者与写者互斥，多个读者可以同时读。读者与写者进程的伪代码ProcessReader{readfileF;}ProcessWriter{writefileF;}3.5读者与写者问题问题描述ProcessReaderP1003.5读者与写者问题问题分析共享资源：文件F临界区：读、写文件ProcessReader{

readfileF;}ProcessWriter{

writefileF;}3.5读者与写者问题问题分析ProcessReaderP1013.5读者与写者问题情况一不考虑多个读者可以同时读，或假设只有一个读者，则问题转为简单的互斥问题实现读者与写者的互斥，读者与读者的互斥，写者与写者的互斥，即全互斥问题信号量的分析因只有一个共享资源F，定义一个互斥信号量即可，用S表示信号量S的初始值为”1”3.5读者与写者问题情况一1023.5读者与写者问题情况一的解决方法

SemaphoreS=1;ProcessReader{

P(S);readfileF;

V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}3.5读者与写者问题情况一的解决方法ProcessRea1033.5读者与写者问题情况二再考虑多个读者允许同时读，以及多个读者与写者的互斥情况则第一个读者与写者存在互斥关系，即只要有一个读者正在读文件，则写者不能进行写操作当没有读者的时候，允许写者进程写操作3.5读者与写者问题情况二1043.5读者与写者问题问题的分析读者是否在读决定写进程是否可以写，所以需要引入一个变量count来记录读者的个数当第一个读者进行读操作，写进程就不能执行，当读者个数为“0”，写进程才可以执行当一个读者进行读文件操作，则读者个数加一，当一个读者退出，则个数减一3.5读者与写者问题问题的分析1053.5读者与写者问题修改后进程的伪代码ProcessReader(i=1,2,3…n){

count++;P(S);readfileF;

count--;V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}读写进程的互斥关系不变存在问题：没有实现多个读者同时读操作3.5读者与写者问题修改后进程的伪代码ProcessRe1063.5读者与写者问题问题的提出对于读者进程，第一个进程需要通过P操作来申请进入临界区，而后续读进程可以直接进入临界区读进程释放临界资源的条件是：所有读进程都退出临界区后V操作的执行应该是读者个数为0的时候3.5读者与写者问题问题的提出1073.5读者与写者问题修改后进程的伪代码ProcessReader(i=1,2,3…n){

count++;

if(count==1)P(S);

readfileF;

count--;

if(count==0)V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}读写进程的互斥关系不变3.5读者与写者问题修改后进程的伪代码ProcessRe1083.5读者与写者问题读进程P(S)、V(S)操作的理解ProcessReader(i=1,2,3…n){

count++;

if(count==1)P(S);(申请进入临界区,相当阻 止写进程)

readfileF;

count--;

if(count==0)V(S);(退出临界区，相当归还 资源，允许写进程)}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}读写进程的互斥关系不变3.5读者与写者问题读进程P(S)、V(S)操作的理解Pr1093.5读者与写者问题信号量的分析读者进入与退出需要对count变量进行修改所以当多个读者进程对count变量值进行修改时必须互斥，否则会一起count变量值的不确定性定义一个与共享变量count有关的互斥信号量用SC表示又读者与写者之间要互斥，信号量S不变3.5读者与写者问题信号量的分析1103.5读者与写者问题信号量初始值的分析两个信号量主要用于控制互斥操作，所以SC和S的初始值都为1。SC初值为1，互斥的count变量一个，且初始读者还没有开始进行读操作，可用Ｓ初值为１，表示一个可用资源(文件Ｆ)可以使用，表示初始读写进程都可以进入临界区。3.5读者与写者问题信号量初始值的分析1113.5读者与写者问题考虑对读进程的互斥处理ProcessReader(i=1,2,3…n){

count++;

if(count==1)P(S);

readfileF;

count--;

if(count==0)V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}Semaphore

Sc=1;S=1;3.5读者与写者问题考虑对读进程的互斥处理Process1123.5读者与写者问题PV操作处理后进程的伪代码ProcessReader(i=1,2,3…n){

P(SC);count++;if(count==1)P(S)；

V(SC);readfileF;

P(SC);count--;if(count==0)V(S);

V(SC);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}Semaphore

Sc=1;S=1;3.5读者与写者问题PV操作处理后进程的伪代码Proces1133.5读者与写者问题总结对每个共享资源（变量）都要设置相应的信号量对每个信号量的PV操作都要成对出现。读者写者问题，关键是理解第一个读者与写者的互斥关系，所以需要读者个数的统计变量，从而产生对共享变量操作引起的互斥问题3.5读者与写者问题总结114第三章进程的并发控制

——互斥与同步与时间有关的错误问题进程协调的概念对临界区管理的准则简单的同步机制（标志法）信号量机制（实现进程互斥与同步的控制）第三章进程的并发控制

——互斥与同步与时间有关的错误问1153.1程序的两种执行方式程序的顺序执行程序在运行的时独占系统资源，且系统按照程序步骤顺序执行地执行，在该程序执行完之前，其他程序只能等待。程序的并发执行多道程序设计的系统中，若干个作业可以同时执行，这些进程轮流地占用CPU，即一个进程的工作没有全部完成之前，另一个进程就可开始工作，我们说这些执行的进程具有并发性。3.1程序的两种执行方式程序的顺序执行1163.1与时间有关的错误问题(1)问题描述：设有一个游乐场设置了一个自动计算机系统，用一个变量count指示在场的人数，当有人进入，则PIN进程完成count++，当有人退出，则POUT进程完成count--进程PINProcessPIN{intR1;R1=count;R1=R1+1;count=R1;}进程POUTProcessPOUT{intR2;R2=count;R2=R2-1;count=R2;}3.1与时间有关的错误问题(1)问题描述：设有一个游乐场设1173.1与时间有关的错误问题(1)两个进程的顺序执行（不产生错误）假设某一时刻count=n

intR1;R1=count;R1=R1+1;count=R1;intR2;R2=count;R2=R2-1;count=R2;正确结果count=n不变假设某一时刻count=nintR2;R2=count;R2=R2-1;count=R2;intR1;R1=count;R