1、 与时间有关的错误问题与时间有关的错误问题 进程协调的概念进程协调的概念 对临界区管理的准则对临界区管理的准则 简单的同步机制（简单的同步机制（标志法标志法）信号量机制信号量机制（实现进程互斥（实现进程互斥与同步的控制）与同步的控制）程序的程序的顺序顺序执行执行 程序在运行的时独占系统资源，且系统按照程序步程序在运行的时独占系统资源，且系统按照程序步骤顺序执行地执行，在该程序执行完之前，其他程骤顺序执行地执行，在该程序执行完之前，其他程序只能序只能等待等待。程序的程序的并发并发执行执行 多道程序设计的系统中，若干个作业可以多道程序设计的系统中，若干个作业可以同时同时执行，执行，这些进程这些进程
2、轮流轮流地占用地占用CPU，即一个进程的工作没有，即一个进程的工作没有全部完成之前，另一个进程就可开始工作，我们说全部完成之前，另一个进程就可开始工作，我们说这些这些执行的进程具有并发性执行的进程具有并发性。问题描述问题描述：设有一个游乐场设置了一个自动计算：设有一个游乐场设置了一个自动计算机系统，用一个变量机系统，用一个变量count指示在场的人数，当指示在场的人数，当有人进入，则有人进入，则PIN进程完成进程完成count+，当有人退出，当有人退出，则则POUT进程完成进程完成count-进程进程PINProcess PIN int R1;R1=count;R1=R1+1;count=R1
3、;进程进程POUTProcess POUT int R2;R2=count;R2=R2-1;count=R2;两个进程的顺序执行（不产生错误）两个进程的顺序执行（不产生错误）假设某一时刻假设某一时刻count=n int R1;R1=count;R1=R1+1;count=R1;int R2;R2=count;R2=R2-1;count=R2;正确结果正确结果count=n不变不变假设某一时刻假设某一时刻count=nint R2;R2=count;R2=R2-1;count=R2;int R1;R1=count;R1=R1+1;count=R1;正确结果正确结果count=n不变不变 并发执
4、行一种错误的可能结果：并发执行一种错误的可能结果：假设某一时刻假设某一时刻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，实际该为，实际该为n 并发执行另一种错误的可能结果：并发执行另一种错误的可能结果：假设某一时刻假设某一时刻count=n R1=count;count=n R1=R1+1;PIN进程被挂起进程被挂起;R1=n+1 R2=count;count=n R2=
5、R2-1;POUT进程被挂起，进程被挂起，PIN唤醒唤醒 R2=n-1 count=R1;PIN进程结束，进程结束，POUT唤醒唤醒 count=n+1 count=R2;POUT进程结束，进程结束，count=n-1错误错误的结果值的结果值count=n-1，实际该为，实际该为n 分析产生错误的可能原因分析产生错误的可能原因 一个进程运行时由于自身或外界的原因可能一个进程运行时由于自身或外界的原因可能被中断，且被中断，且断点是不固定断点是不固定的。的。进程执行的相对速度进程执行的相对速度不能不能由自己来控制由自己来控制 两个并发进程使用两个并发进程使用共享共享的变量的变量count 两个进程
6、在两个进程在不同时间不同时间里访问里访问count变量，可变量，可能得到能得到相同的相同的count变量值。变量值。问题描述：设一个飞机航班售票系统有问题描述：设一个飞机航班售票系统有n个售个售票处，每个售票处通过终端访问系统公共数据票处，每个售票处通过终端访问系统公共数据区，假定公共数据区中的一些单元区，假定公共数据区中的一些单元Aj（j=1，2，）分别存放某年某月某日某次航班的）分别存放某年某月某日某次航班的剩余票数剩余票数。设。设P1，P2，Pn表示各个售票表示各个售票处的处理进程，处的处理进程，R1，R2，Rn表示各进程表示各进程执行时所用的工作单元，当各售票处有旅客买执行时所用的工作
7、单元，当各售票处有旅客买票时，进程工作如下：票时，进程工作如下：可能产生的可能产生的错误结果错误结果 可能有若干个旅客在几乎相可能有若干个旅客在几乎相同的时间里到不同的售票处同的时间里到不同的售票处要求购买同一天同一航班的要求购买同一天同一航班的机票，于是若干进程都要机票，于是若干进程都要访访问同一个问同一个Aj，则结果可能，则结果可能出现同一张票卖给几个不同出现同一张票卖给几个不同的旅客的旅客Process Pi（i=1，2，n）根据用户需求根据用户需求找到找到Aj;Ri=Aj;if(Ri=1)Ri=Ri-1;Aj=Ri;提示已卖出一张票信息；提示已卖出一张票信息；else 输出输出“票已售
8、完票已售完”；假设某一个时刻三个客户在不同网点但几乎同假设某一个时刻三个客户在不同网点但几乎同时到达购票访问的情况时到达购票访问的情况进程进程t1t2t3t4t5P1R1=AjR1=R1-1Aj=R1P2R2=AjR2=R2-1Aj=R2P3R3=AjR3=R3-1 在在os支持下，多个进程既独立又并发执支持下，多个进程既独立又并发执行，然而进程之间可能行，然而进程之间可能合作合作完成一项任完成一项任务，可能务，可能共享共享一种系统资源，可能相互一种系统资源，可能相互支持和依赖，甚至制约对方，为了协调支持和依赖，甚至制约对方，为了协调进程间的关系，进程间的关系，os必须进行必须进行进程间的协进
9、程间的协调调。直接直接相互制约关系相互制约关系 源于进程的源于进程的合作合作，同步关系，同步关系 如：如：A、B两个进程通过缓冲区合作完成一项任务，两个进程通过缓冲区合作完成一项任务，A负责存数据到缓冲区，负责存数据到缓冲区，B负责从缓冲区中取数。负责从缓冲区中取数。间接间接相互制约关系相互制约关系 源于资源源于资源共享共享，互斥关系，互斥关系 如：如：A、B两个进程共享打印机，若分配给两个进程共享打印机，若分配给A，则当，则当B需需要打印机时被阻塞而等待要打印机时被阻塞而等待 进程间具有一种进程间具有一种互斥关系互斥关系 也就是说对于某个系统资源，如果一个进程正在也就是说对于某个系统资源，如
10、果一个进程正在使用，其他进程就使用，其他进程就必须等待必须等待其用完，不能同时使其用完，不能同时使用。用。进程间具有一种进程间具有一种同步关系同步关系 即多个相关的进程在即多个相关的进程在执行次序执行次序上上需要协调需要协调，如当，如当两个进程或多个进程合作完成一个任务，在并发两个进程或多个进程合作完成一个任务，在并发执行中，一个进程执行中，一个进程需等待需等待其合作伙伴发送消息或其合作伙伴发送消息或建立条件再向前执行，这种制约关系通常称为建立条件再向前执行，这种制约关系通常称为进进程的同步程的同步。临界资源临界资源 一次只允许一个进程使用的资源一次只允许一个进程使用的资源 广义上，包括广义上
11、，包括物理实体物理实体资源，如：打印机资源，如：打印机 软件资源软件资源，如：变量、文件等，如：变量、文件等 临界区临界区 一个进程访问这种临界资源的那段程序代码，一个进程访问这种临界资源的那段程序代码，称为称为临界区临界区 剩余区剩余区 除临界区外的其余代码除临界区外的其余代码 说明说明：进程互斥的：进程互斥的再定义再定义，就是两个进，就是两个进程不能同时进入访问同一临界资源的临程不能同时进入访问同一临界资源的临界区界区 操作系统中实现互斥和同步的机制统称操作系统中实现互斥和同步的机制统称为为同步机制同步机制操作系统的操作系统的进程同步机制进程同步机制必须遵循如下准则必须遵循如下准则 空闲让
12、进空闲让进 忙则等待忙则等待 有限等待有限等待 让权等待让权等待 空闲让进空闲让进 当无进程处于临界区时，允许一个进程进入当无进程处于临界区时，允许一个进程进入 忙则等待忙则等待 当有进程在临界区，其他欲进入临界区的进程当有进程在临界区，其他欲进入临界区的进程须等待，否则无需等待须等待，否则无需等待 （一次至多一个进程能够进入临界区）（一次至多一个进程能够进入临界区）有限等待有限等待 对要求进入临界区的进程，应在对要求进入临界区的进程，应在有限时有限时间间内让其进入，避免内让其进入，避免“死等死等”（不能让一个进程无限在临界区执行，任（不能让一个进程无限在临界区执行，任何进入临界区的进程必须在
13、有限时间内何进入临界区的进程必须在有限时间内退出）退出）让权等待让权等待 临界区让出，必须临界区让出，必须立即释放立即释放CPU，让等，让等待进程进入，避免待进程进入，避免“忙等忙等”（不能让一个进程无限等待进入，即有进（不能让一个进程无限等待进入，即有进程退出临界区时，应让等待进程进入临程退出临界区时，应让等待进程进入临界区执行）界区执行）进程互斥问题的进程互斥问题的软件解决软件解决方法方法 轮流标志法（单标志法）轮流标志法（单标志法）双标志法双标志法 三标志法三标志法算法的基本思想算法的基本思想 设置一个标志变量设置一个标志变量turn，两个进程，两个进程P0、P1要进要进入临界区先要访问
14、该标志，根据标志值决定自入临界区先要访问该标志，根据标志值决定自己是否进入临界区。例如当己是否进入临界区。例如当turn=0，表示允许，表示允许P0进程进入，当进程进入，当P0退出临界区后，置退出临界区后，置turn=1，P1才可进入临界区；反之当才可进入临界区；反之当turn1，表示允，表示允许许P1进程进入，退出时置进程进入，退出时置turn=0，则，则P0才可进才可进入。入。Process P0 do while(turn!=0);临界区 turn=1;剩余区 while(1);Process P1 do while(turn!=1);临界区 turn=0;剩余区 while(1);初始
15、值 turn=0;或者 turn=1;该算法的致命缺点该算法的致命缺点 要求进入临界区执行的两个进程必须要求进入临界区执行的两个进程必须严格严格的交的交替运行。替运行。当进程当进程A大于大于进程进程B时，将阻塞进程时，将阻塞进程B再次进入再次进入临界区（因为交替原则，临界区（因为交替原则，B必须等待必须等待A执行结执行结束），即产生了束），即产生了长进程阻塞短进程长进程阻塞短进程的问题。的问题。不满足临界区管理的第一个准则，因为存在一不满足临界区管理的第一个准则，因为存在一个进程当它在剩余区时，也不允许另一个进程个进程当它在剩余区时，也不允许另一个进程进入临界区。进入临界区。算法的基本思想算法
16、的基本思想 先修改后检查算法先修改后检查算法 为每个进程都设置一个标志位，引入数组为每个进程都设置一个标志位，引入数组flag2，初始化为初始化为false，表示临界区中无进程，欲进入，表示临界区中无进程，欲进入者可以进入。进程者可以进入。进程Pi欲进入时将自身标志欲进入时将自身标志flagi置为置为true，阻止另一个进程进入，接着判定对方，阻止另一个进程进入，接着判定对方的标志是否为的标志是否为false，若是才可以进入临界区，若是才可以进入临界区，否则必须等待；任一个进程退出临界区后都将否则必须等待；任一个进程退出临界区后都将自身标志置为自身标志置为false，表示退出临界区，允许对，表
17、示退出临界区，允许对方进程进入临界区。方进程进入临界区。Process P0 do flag0=true;while(flag1);临界区 flag0=false;剩余区 while(1);Process P1 do flag1=true;while(flag0);临界区 flag1=false;剩余区 while(1);初始值 flagi=false算法的特点算法的特点 可以解决两个进程严格交替的问题可以解决两个进程严格交替的问题 但当两个进程几乎同时到达时，结果两但当两个进程几乎同时到达时，结果两个进程都不能进入临界区执行个进程都不能进入临界区执行 产生死锁问题产生死锁问题 可能导致对方进
18、程的可能导致对方进程的“饥饿饥饿”问题，将问题，将永远被阻塞永远被阻塞 不满足不满足管理准则中的管理准则中的“空闲让进空闲让进”算法的基本思想算法的基本思想 先检查先检查算法算法 交换修改与检查语句的顺序，先做交换修改与检查语句的顺序，先做while检查，再做检查，再做true值的设置修改值的设置修改 算法的主要伪代码算法的主要伪代码Process P0 do while(flag1);flag0=true;临界区 flag0=false;剩余区 while(1);Process P1 do while(flag0);flag1=true;临界区 flag1=false;剩余区 while(1
19、);算法的基本思想算法的基本思想 先修改、后检查、先修改、后检查、后修改者等待后修改者等待算法算法 为了解决两个进程的同时到达问题，将前两者为了解决两个进程的同时到达问题，将前两者算法结合，在双标志法的基础上再引入算法结合，在双标志法的基础上再引入turn变变量，当两个进程几乎同时到达时，进程根据量，当两个进程几乎同时到达时，进程根据turn值决定哪一个进程进入临界区，即保证任值决定哪一个进程进入临界区，即保证任一个时刻，一个时刻，turn值为值为0或者为或者为1，使得只有一个，使得只有一个进程满足条件而进入临界区。进程满足条件而进入临界区。Process P0 do flag0=true;t
20、urn=1;while(flag1&turn=1);临界区 flag0=false;剩余区 while(1);Process P1 do flag1=true;turn=0;while(flag0&turn=0);临界区 flag0=false;剩余区 while(1);flag0=true;flag1=true;turn=1;while(flag1&turn=1);/P0被挂起 turn=0;/后修改者即P1 while(flag0&turn=0);/P1被挂起，P0被解除 临界区 /P0进入临界区 flag0=false;/P0退出，P1可被解除 剩余区 /P0的剩余区 flag0=tru
21、e;flag1=true;turn=1;turn=0;/后修改者P1 while(flag0&turn=0);/P1被挂起 while(flag1&turn=1);/P0被批准进入 临界区 /P0进入临界区 flag0=false;/P0退出，P1可被解除 剩余区 /P0的剩余区 flag0=true;flag1=true;turn=0;turn=1;/后修改者P0 while(flag1&turn=1);/P0被挂起 while(flag0&turn=0);/P1被批准进入 临界区 /P1进入临界区 flag1=false;/P1退出，P0可被解除 剩余区 /P1的剩余区 算法的特点算法的特
22、点 满足管理准则，空闲让进，忙则等待等满足管理准则，空闲让进，忙则等待等 解决进程的互斥与并发解决进程的互斥与并发 实现较复杂实现较复杂 系统开销大系统开销大四个算法的共同缺点四个算法的共同缺点 只适合解决两进程的互斥问题只适合解决两进程的互斥问题 不能处理进程的同步问题不能处理进程的同步问题 信号量协调机制可实现信号量协调机制可实现2个或个或2个以上个以上的的进程协调。既可用与进程协调。既可用与互斥互斥，也可用用于，也可用用于同步同步。信号量（信号量（semaphore）是由荷兰计算机科）是由荷兰计算机科学家学家E.W.Dijkstra于于1965年提出的，它取年提出的，它取自交通管理中的自
23、交通管理中的信号灯信号灯的概念。的概念。信号量的基本概念信号量的基本概念 信号量是用于控制进程互斥与同步的信号量是用于控制进程互斥与同步的物物理变量理变量 信号量信号量S（通常用（通常用S表示）是一个表示）是一个整型整型变变量，初始值为量，初始值为非负数非负数 每个信号量每个信号量S对应设置了一个对应设置了一个等待等待队列队列 对信号量的操作只能通过对信号量的操作只能通过PV操作操作进行进行 P操作和操作和V操作都是操作都是不可分割不可分割的原子操作，的原子操作，也叫也叫原语原语 P操作操作可以记为可以记为P(S)，wait(S)或者或者down(S)V操作操作可以记为可以记为V(S)，sig
24、nal(S)或者或者up(S)为减化，我们用为减化，我们用P(S)和和V(S)表示，教材表示，教材采用采用wait()和和signal()表示表示 Dijkstra把互斥和同步的关键含义抽象成把互斥和同步的关键含义抽象成信号量信号量(semaphore)概念，并引入在信号概念，并引入在信号量上的量上的P、V操作作为同步原语操作作为同步原语(P和和V分分别是荷兰文的别是荷兰文的“等待等待”和和“发信号发信号”两两词的首字母词的首字母)。PV操作对于每一个进程来说，都只能进操作对于每一个进程来说，都只能进行行一次一次，而且必须，而且必须成对成对使用。使用。P(S)操作的定义操作的定义 S值减一值减
25、一 若若S=0，当前进程，当前进程继继续运行续运行(说明等待队列说明等待队列无进程，当前进程可无进程，当前进程可继续不阻塞继续不阻塞)P操作的伪代码P(int s)s-;if(s0)wait();/当前被挂起 return;/当前继续V(S)操作的定义操作的定义 S值加一；值加一；若若S0，当前进程，当前进程继续继续执行执行（说明等待队列无（说明等待队列无进程，无需执行唤醒操进程，无需执行唤醒操作）作）V操作的伪代码V(int s)s+;if(s=0)wakeup();/移出一个进程，插入就绪队列，相当唤醒 return;/当前继续如果有若干个进程都调用如果有若干个进程都调用P操作操作(提提出
26、申请出申请)，则只有，则只有第一个第一个调用调用P操作操作的进程不成为等待状态而可以继续的进程不成为等待状态而可以继续执行执行P操作第一次调用后，操作第一次调用后，S的值成为的值成为“0”，以后的进程调用，以后的进程调用P操作时，操作时，S值值总小于总小于0（S=1)R=Aj;R=R-1;Aj=R;提示已卖出一张票信息；提示已卖出一张票信息；else 输出票已售完；输出票已售完；Process pi int R;根据用户需求找到根据用户需求找到Aj;if(Aj=1)P(S);R=Aj;R=R-1;Aj=R;V(S);提示已卖出一张票信息；提示已卖出一张票信息；else 输出票已售完；输出票已售
27、完；Semaphore S=1;思考：互斥问题是否得到解决？如果没有，原因在哪？法一的问题分析法一的问题分析 表面上看实现互斥的管理，实际上仍然存在读表面上看实现互斥的管理，实际上仍然存在读取相同取相同Aj值的情况值的情况 分析判定分析判定共享资源共享资源应该是：应该是：Aj变量变量 分析判定分析判定临界区临界区：包括所有对：包括所有对Aj变量操作的代变量操作的代码区码区 注意：若查询注意：若查询结果是无票结果是无票，虽不影响临界区的，虽不影响临界区的使用，不产生错误，但存在潜在的错误使用，不产生错误，但存在潜在的错误Semaphore S=1;Process pi（修改进程的表示）（修改进程
28、的表示）int R;根据用户需求找到根据用户需求找到Aj；R=Aj;if(R=1)R=R-1;Aj=R;提示已卖出一张票信息；提示已卖出一张票信息；else 输出票已售完；输出票已售完；Process pi（I=1，2，n）int R;根据用户需求找到根据用户需求找到Aj；P(S);R=Aj;if(R=1)R=R-1;Aj=R;V(S);提示已卖出一张票信息；提示已卖出一张票信息；else 输出票已售完；输出票已售完；法二的问题分析法二的问题分析 PV操作没有操作没有成对成对出现出现 对第一个查询结果无票的进程而言，能对第一个查询结果无票的进程而言，能顺利退出临界区，但后续进程均被挂起，顺利退
29、出临界区，但后续进程均被挂起，不能得到响应不能得到响应 导致系统内部存在导致系统内部存在“饥饿饥饿”进程进程Semaphore S=1;Process pi int R;P(S);根据用户需求找到根据用户需求找到Aj；R=Aj;if(R=1)R=R-1;Aj=R;V(S);提示已卖出一张票信息；提示已卖出一张票信息；else V(S);输出票已售完输出票已售完 说明说明：准确判断临：准确判断临界区是非常重要的，界区是非常重要的，但要注意在退出临但要注意在退出临界区是否执行了界区是否执行了V操作，要注意操作，要注意PV操操作的成对性作的成对性对信号量对信号量S的分析的分析 S1，表示当前共享资源
30、只有一个可供使用。（且，表示当前共享资源只有一个可供使用。（且任何时刻只能一个进程进入临界区，其他欲进入的任何时刻只能一个进程进入临界区，其他欲进入的进程必须等待进程必须等待互斥概念）互斥概念）S0，表示有一个进程在临界区，无可用资源，表示有一个进程在临界区，无可用资源 S-1，-2表示有表示有1个、个、2个个等待的进程等待的进程 S的的取值范围取值范围：(-(n-1)1)|S|的含义：表示有的含义：表示有|S|个进程在等待个进程在等待 这是这是n个进程的互斥问题个进程的互斥问题假设缓冲区一次只能放一个物品缓冲区进程B（消费者）进程A（生产者）存取读加工问题：如果两个进程不相互制约的话会造成什
31、么错误？要实现进程同步就必须提供一种机制，该机制能测试要实现进程同步就必须提供一种机制，该机制能测试进程所需的消息是否到达，也能把它所需的消息发送进程所需的消息是否到达，也能把它所需的消息发送出去出去 用一个信号量与一个消息联系起来用一个信号量与一个消息联系起来，当信号量的值为，当信号量的值为“0”时，表示期望的消息还没有产生，当信号量的值时，表示期望的消息还没有产生，当信号量的值为非为非“0”时表示期望的消息已经存在。时表示期望的消息已经存在。通过调用通过调用P操作操作可以测试自己所期望的消息是可以测试自己所期望的消息是否到达（相当否到达（相当申请申请进入临界区）进入临界区）而任何进程要向其
32、它进程发送消息时（相当而任何进程要向其它进程发送消息时（相当唤唤醒醒下一个进程进入临界区）可以调用下一个进程进入临界区）可以调用V操作操作 P操作的理解操作的理解 用信号量用信号量S表示一种消息，如果消息表示一种消息，如果消息还没有还没有产生，则产生，则S0，调用，调用P(S)操作后，调用者操作后，调用者将成为将成为等待等待状态，申请进入临界区失败。状态，申请进入临界区失败。如果消息已经如果消息已经存在存在，则，则S0,调用调用P(S)操作操作后，调用者不会成为等待状态，即申请进入后，调用者不会成为等待状态，即申请进入临界区成功。临界区成功。V操作的理解操作的理解 若调用若调用V(S)操作操作
33、前前S0，表示消息还没有产生也，表示消息还没有产生也没有等待没有等待消息的进程，这时调用消息的进程，这时调用V(S)操作后，操作后，S!=0，调用，调用V(S)后，意味着消息产生，即相当通后，意味着消息产生，即相当通知或者唤醒操作。知或者唤醒操作。若调用若调用V操作操作前前S0，表示消息还没有产生且有进，表示消息还没有产生且有进程在程在等待等待该消息，这时调用该消息，这时调用V(S)操作后将操作后将释放释放一一个在等待消息的进程，即调用个在等待消息的进程，即调用V(S)操作的进程把操作的进程把消息发给在等待消息的进程且允许它继续进行，消息发给在等待消息的进程且允许它继续进行，即相当通知或者唤醒
34、操作。即相当通知或者唤醒操作。生产者与消费者问题描述 现假定有一个生产者和一个消费者，他们现假定有一个生产者和一个消费者，他们共用一个缓共用一个缓冲器冲器，生产者，生产者不断不断地生产物品，每生产一件物品就要存入地生产物品，每生产一件物品就要存入缓冲器，但缓冲器中每次只能缓冲器，但缓冲器中每次只能存入一件物品存入一件物品，只有当消费，只有当消费者把物品取走后，生产者才能把第二件物品存入缓冲器。者把物品取走后，生产者才能把第二件物品存入缓冲器。同样地，消费者同样地，消费者不断不断地取出物品去消费，当缓冲器中有物地取出物品去消费，当缓冲器中有物品时他就可以去取，每取走一件物品后品时他就可以去取，每
35、取走一件物品后必须等生产者必须等生产者放入放入一件物品才可一件物品才可再取再取。生产者进程和消费者进程生产者进程和消费者进程（未采用同步机制前的主要代码）（未采用同步机制前的主要代码）Process producer L1:produce a product;Buffer=product;goto L1;Process consumer L1:take a product from Buffer;consume;goto L1;问题分析问题分析 消息的个数：消息的个数：2个个 需要的信号量两个，定义两个变量需要的信号量两个，定义两个变量SP、SG分分别表示生产者和消费者的信号量别表示生产者和消
36、费者的信号量(私有信号量私有信号量)两个进程生产和消费各自独立，两个进程生产和消费各自独立，并发并发执行执行 两个进程只在两个进程只在访问公共访问公共的缓冲器把物品存入或的缓冲器把物品存入或取出时才要互通消息取出时才要互通消息信号量初值的分析信号量初值的分析 初始状态，缓冲器为初始状态，缓冲器为空空，允许生产者生产的物，允许生产者生产的物品存入缓冲器，相当于品存入缓冲器，相当于通知通知消费者进程取物品消费者进程取物品的的消息消息已经已经到了到了，代表此消息的信号量，代表此消息的信号量SP初值初值应该应该为为“1”。初始状态，缓冲区为初始状态，缓冲区为空空，不能取数消费，也就，不能取数消费，也就
37、不能通知不能通知再生产，所以对应信号量再生产，所以对应信号量SG的初值的初值应该应该为为“0”。Semaphore SP,SG;SP=1;SG=0;SP：表示是否可以把物品存入缓冲区，由于缓冲区：表示是否可以把物品存入缓冲区，由于缓冲区每次只能放一个物品，所以初值为每次只能放一个物品，所以初值为1。SG：表示缓冲区是否存在有物品，显然初值为：表示缓冲区是否存在有物品，显然初值为0，表，表示开始还没有物品在缓冲区。示开始还没有物品在缓冲区。实现的基本方法实现的基本方法 生产者生产者进入缓冲区前调用进入缓冲区前调用P操作操作判断消息是否判断消息是否到达，或者说申请进入的消息是否允许通过，到达，或者
38、说申请进入的消息是否允许通过，退出缓冲区时，调用退出缓冲区时，调用V操作操作发送消息通知消费发送消息通知消费者，相当唤醒消费者者，相当唤醒消费者 消费者消费者在进入缓冲区前，首先调用在进入缓冲区前，首先调用P操作操作判断判断是否可以取数，即通知取数的消息是否到达，是否可以取数，即通知取数的消息是否到达，当取数后退出缓冲区，调用当取数后退出缓冲区，调用V操作操作，发送消息，发送消息，通知生产者通知生产者 将将PV操作加入到原来的伪代码中，结果如下操作加入到原来的伪代码中，结果如下Semaphore SP,SG;SP=1;SG=0;int Buffer;Process producer L1:pr
39、oduce a product;P(SP);Buffer=product;V(SG);goto L1;Process consumer L1:P(SG);take a product from Buffer;V(SP);consume;goto L1;分析下列几种情况，看分析下列几种情况，看PV操作是否能管理操作是否能管理：先生产再消费，然后再生产再消费的同步过程先生产再消费，然后再生产再消费的同步过程(可以可以)先生产，然后想再生产，是否可行？（先生产，然后想再生产，是否可行？（不行不行）如果再次生产失败则转为消费，消费后再生产，如果再次生产失败则转为消费，消费后再生产，但如果消费后企图再消
40、费是否可行？（但如果消费后企图再消费是否可行？（不行不行）一开始就要消费，是否可行？一开始就要消费，是否可行？(不行不行)开始没有产品，不能消费，结果必然转为生产开始没有产品，不能消费，结果必然转为生产分析分析SP和和SG的取值范围的取值范围 缓冲器任何时候只允许一个进程使用。缓冲器任何时候只允许一个进程使用。两个进程，当生产者两个进程，当生产者/消费者在缓冲器内，消费者在缓冲器内，消费者消费者/生产者只能等待，所以生产者只能等待，所以等待等待的进的进程个数最多一个。程个数最多一个。取值范围取值范围(-1，0,1)问题变为问题变为：一个生产者和一个消费者共享一个生产者和一个消费者共享容量容量为
41、为n的缓冲区的缓冲区的同步问题的同步问题生产生产k取数取数t 变量变量 k 和和 t 的理解的理解由于缓冲区的容量为由于缓冲区的容量为n，则必须，则必须考虑考虑：生产：生产者生产的物品存入缓冲区的哪个者生产的物品存入缓冲区的哪个位置位置，以及消，以及消费者取出的物品来自缓冲区的哪个位置，因此费者取出的物品来自缓冲区的哪个位置，因此相应需要增加相应需要增加 k 和和 t 两个变量表示生产者往缓两个变量表示生产者往缓冲区存物品和消费者从缓冲区中取物品的冲区存物品和消费者从缓冲区中取物品的相对相对位置位置，它们的，它们的初值为初值为“0”。生产者和消费者的生产者和消费者的进程表示进程表示如下：如下：
42、(还没有实现同步机制前还没有实现同步机制前)Process producer L1：produce a product;Bk=product;k=(k+1)%n;goto L1;Process consumer L1：take a product from Bt;t=(t+1)%n;goto L1;信号量的定义信号量的定义 需要传送的需要传送的消息个数消息个数：2个（不变）个（不变）定义定义2个信号量个信号量：分别用：分别用SP，SG表示表示 信号量的初始化信号量的初始化 SP：初值为：初值为“n”，表示开始有，表示开始有n个空闲区可个空闲区可以放置物品以放置物品 SG：初值为：初值为“0”，
43、表示开始没有物品在缓，表示开始没有物品在缓冲区中冲区中 问题提出问题提出：在：在PV操作之前必须准确判断临界操作之前必须准确判断临界区，这里的临界区在哪？区，这里的临界区在哪？Process producer L1：produce a product;Bk=product;k=(k+1)%n;goto L1;Process consumer L1：take a product from Bt;t=(t+1)%n;goto L1;int Bn,k=0,t=0;Semaphore SP=n,SG=0;Process producer L1：produce a product;P(SP);Bk=pr
44、oduct;k=(k+1)%n;V(SG);goto L1;Process consumer L2：P(SG);take a product from Bt;t=(t+1)%n;V(SP);goto L2;例例2：假定有三个进程假定有三个进程R，W1，W2共享一个共享一个缓冲器缓冲器B，而而B中每次只能存放一个数。当缓冲器中无数时，进程中每次只能存放一个数。当缓冲器中无数时，进程R可将从输入设备上读入的数存放到缓冲器可将从输入设备上读入的数存放到缓冲器B中。若存放中。若存放到缓冲器中的是到缓冲器中的是奇数奇数，则允许进程，则允许进程W1将其取出打印；若将其取出打印；若存放到缓冲器中的是存放到缓
45、冲器中的是偶数偶数，则允许进程，则允许进程W2将其取出打印。将其取出打印。同时规定：进程同时规定：进程R必须等缓冲器中的数取出打印后才能必须等缓冲器中的数取出打印后才能再存放一个数；进程再存放一个数；进程W1或或W2对每次存入缓冲器中的数对每次存入缓冲器中的数只能打印一次只能打印一次；W1和和W2都都不能从空不能从空的缓冲器中取数，的缓冲器中取数，写出这三个并发进程能正确工作的程序。写出这三个并发进程能正确工作的程序。进程R的伪代码描述Process R int x;L1:take a number from device;/读数 x=number;B=x;/读数后存入缓冲区 if(B=奇数)
46、通知w1进程 else 通知w2进程;goto L1;进程进程w1,w2的伪代码描述：的伪代码描述：Process W1 int y;L2:y=B ;/取数 print the number y;goto L2;Process W2 int z;L3:z=B ;print the number z;goto L3;分析问题分析问题 哪个进程看成是生产者，哪个是消费者？哪个进程看成是生产者，哪个是消费者？把把R看成是生产者，把进程看成是生产者，把进程W1和和W2看成消看成消费者。费者。生产者生产者(R进程进程)生产不同的产品生产不同的产品(奇数或偶数奇数或偶数)，存入缓冲器存入缓冲器B，供不同的
47、消费者，供不同的消费者(W1和和W2进进程程)取用。取用。需要发送的消息是什么以及消息个数需要发送的消息是什么以及消息个数?当进程当进程R读入的是奇数，则要把有奇数的消读入的是奇数，则要把有奇数的消息发送给进程息发送给进程W1；当进程当进程R读入的是偶数，则要把有偶数的消读入的是偶数，则要把有偶数的消息发送给息发送给W2。在进程在进程W1和和W2从缓冲器中取出数后，应把从缓冲器中取出数后，应把缓冲器中又可以缓冲器中又可以存一个数的消息存一个数的消息告诉给告诉给进程进程R。分析信号量个数及其分别代表的含义分析信号量个数及其分别代表的含义通过上述分析得知，需要发送三个消息，所以需要定通过上述分析得
48、知，需要发送三个消息，所以需要定义三个信号量，分别用义三个信号量，分别用S，SO，SE表示如下：表示如下：S：表示是否可以把数存入缓冲器，由于缓冲器中：表示是否可以把数存入缓冲器，由于缓冲器中每次只能存放一个数，初始缓冲区为空，所以它的每次只能存放一个数，初始缓冲区为空，所以它的初值为初值为“1”SO：表示缓冲器中是否有奇数，：表示缓冲器中是否有奇数，初值为初值为“0”，表示，表示开始无奇数开始无奇数 SE：表示缓冲器中是否有偶数，：表示缓冲器中是否有偶数，初值为初值为“0”，表示，表示开始无偶数开始无偶数 根据上面的分析，根据上面的分析，得出信号量的定义得出信号量的定义和变量定义如下：和变量
49、定义如下：int B;Semaphore S,SO,SE;S=1;SO=0;SE=0;Process R int x;L1:take a number from device;x=number;P(S);B=x;if(B=奇数)V(SO);else V(SE);goto L1;Process W1 int y;L2:P(SO);y=B ;V(S);print the number y;goto L2;Process W2 int z;L3:P(SE);z=B ;V(S);print the number z;goto L3;总结总结 进程的互斥实际上是进程同步的一种进程的互斥实际上是进程同步的
50、一种特殊特殊情况，情况，若干进程互斥使用资源时，一个等待使用资源的若干进程互斥使用资源时，一个等待使用资源的进程在等待占用资源的进程进程在等待占用资源的进程发出发出“归还资源归还资源”的的消息消息后，它就可去使用资源。因此互斥使用资源后，它就可去使用资源。因此互斥使用资源的进程实际上也存在一种一个进程依赖另一个进的进程实际上也存在一种一个进程依赖另一个进程发出消息的制约关系。程发出消息的制约关系。把用来解决进程互斥与同步的机制（如把用来解决进程互斥与同步的机制（如PV操作）操作）称为称为同步机制同步机制3.5 进程的同步与互斥混合进程的同步与互斥混合 生产者与消费者生产者与消费者 问题叙述问题
