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

第三章 进程的并发控制 互斥与同步互斥与同步 与时间有关的错误问题与时间有关的错误问题 进程协调的概念进程协调的概念 对临界区管理的准则对临界区管理的准则 简单的同步机制（简单的同步机制（标志法标志法）信号量机制信号量机制（实现进程互斥（实现进程互斥与同步的控制）与同步的控制）第三章 进程的并发控制 互斥与同步与时间有关的错误问13.1 程序的两种执行方式 程序的程序的顺序顺序执行执行 程序在运行的时独占系统资源，且系统按照程序步程序在运行的时独占系统资源，且系统按照程序步程序在运行的时独占系统资源，且系统按照程序步程序在运行的时独占系统资源，且系统按照程序步骤顺序执行地执行，在该程序执行完之前，其他程骤顺序执行地执行，在该程序执行完之前，其他程骤顺序执行地执行，在该程序执行完之前，其他程骤顺序执行地执行，在该程序执行完之前，其他程序只能序只能序只能序只能等待等待等待等待。程序的程序的并发并发执行执行 多道程序设计的系统中，若干个作业可以多道程序设计的系统中，若干个作业可以多道程序设计的系统中，若干个作业可以多道程序设计的系统中，若干个作业可以同时同时同时同时执行，执行，执行，执行，这些进程这些进程这些进程这些进程轮流轮流轮流轮流地占用地占用地占用地占用CPUCPU，即一个进程的工作没有，即一个进程的工作没有，即一个进程的工作没有，即一个进程的工作没有全部完成之前，另一个进程就可开始工作，我们说全部完成之前，另一个进程就可开始工作，我们说全部完成之前，另一个进程就可开始工作，我们说全部完成之前，另一个进程就可开始工作，我们说这些这些这些这些执行的进程具有并发性执行的进程具有并发性执行的进程具有并发性执行的进程具有并发性。3.1 程序的两种执行方式程序的顺序执行23.1 与时间有关的错误问题(1)问题描述问题描述问题描述问题描述：设有一个游乐场设置了一个自动计算：设有一个游乐场设置了一个自动计算：设有一个游乐场设置了一个自动计算：设有一个游乐场设置了一个自动计算机系统，用一个变量机系统，用一个变量机系统，用一个变量机系统，用一个变量countcount指示在场的人数，当有指示在场的人数，当有指示在场的人数，当有指示在场的人数，当有人进入，则人进入，则人进入，则人进入，则PINPIN进程完成进程完成进程完成进程完成count+count+，当有人退出，当有人退出，当有人退出，当有人退出，则则则则POUTPOUT进程完成进程完成进程完成进程完成count-count-进程进程PINProcess PIN int R1;R1=count;R1=R1+1;count=R1;进程进程POUTProcess POUT int R2;R2=count;R2=R2-1;count=R2;3.1 与时间有关的错误问题(1)问题描述：设有一个游乐场设33.1 与时间有关的错误问题(1)两个进程的顺序执行（不产生错误）两个进程的顺序执行（不产生错误）假设某一时刻假设某一时刻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不变不变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=n R1=count;count=n R1=R1+1;PIN进程被挂起进程被挂起;R1=n+1 R2=count;count=n R2=R2-1;POUT进程被挂起，进程被挂起，PIN唤醒唤醒 R2=n-1 count=R1;PIN进程结束，进程结束，POUT唤醒唤醒 count=n+1 count=R2;POUT进程结束，进程结束，count=n-1错误错误的结果值的结果值count=n-1，实际该为，实际该为n3.1与时间有关的错误问题(1)并发执行另一种错误的可能结果63.1与时间有关的错误问题(1)分析产生错误的可能原因分析产生错误的可能原因一个进程运行时由于自身或外界的原因可能一个进程运行时由于自身或外界的原因可能一个进程运行时由于自身或外界的原因可能一个进程运行时由于自身或外界的原因可能被中断，且被中断，且被中断，且被中断，且断点是不固定断点是不固定断点是不固定断点是不固定的。的。的。的。进程执行的相对速度进程执行的相对速度进程执行的相对速度进程执行的相对速度不能不能不能不能由自己来控制由自己来控制由自己来控制由自己来控制两个并发进程使用两个并发进程使用两个并发进程使用两个并发进程使用共享共享共享共享的变量的变量的变量的变量countcount两个进程在两个进程在两个进程在两个进程在不同时间不同时间不同时间不同时间里访问里访问里访问里访问countcount变量，可变量，可变量，可变量，可能得到能得到能得到能得到相同的相同的相同的相同的countcount变量值。变量值。变量值。变量值。3.1与时间有关的错误问题(1)分析产生错误的可能原因73.1与时间有关的错误问题(2)问题描述：设一个飞机航班售票系统有问题描述：设一个飞机航班售票系统有问题描述：设一个飞机航班售票系统有问题描述：设一个飞机航班售票系统有n n个售个售个售个售票处，每个售票处通过终端访问系统公共数据票处，每个售票处通过终端访问系统公共数据票处，每个售票处通过终端访问系统公共数据票处，每个售票处通过终端访问系统公共数据区，假定公共数据区中的一些单元区，假定公共数据区中的一些单元区，假定公共数据区中的一些单元区，假定公共数据区中的一些单元AjAj（j=1j=1，2 2，）分别存放某年某月某日某次航班的）分别存放某年某月某日某次航班的）分别存放某年某月某日某次航班的）分别存放某年某月某日某次航班的剩剩剩剩余票数余票数余票数余票数。设。设。设。设P1P1，P2P2，PnPn表示各个售票处表示各个售票处表示各个售票处表示各个售票处的处理进程，的处理进程，的处理进程，的处理进程，R1R1，R2R2，RnRn表示各进程执表示各进程执表示各进程执表示各进程执行时所用的工作单元，当各售票处有旅客买票行时所用的工作单元，当各售票处有旅客买票行时所用的工作单元，当各售票处有旅客买票行时所用的工作单元，当各售票处有旅客买票时，进程工作如下：时，进程工作如下：时，进程工作如下：时，进程工作如下：3.1与时间有关的错误问题(2)问题描述：设一个飞机航班售票83.1与时间有关的错误问题(2)可能产生的可能产生的可能产生的可能产生的错误结果错误结果错误结果错误结果 可能有若干个旅客在几乎相可能有若干个旅客在几乎相可能有若干个旅客在几乎相可能有若干个旅客在几乎相同的时间里到不同的售票处同的时间里到不同的售票处同的时间里到不同的售票处同的时间里到不同的售票处要求购买同一天同一航班的要求购买同一天同一航班的要求购买同一天同一航班的要求购买同一天同一航班的机票，于是若干进程都要机票，于是若干进程都要机票，于是若干进程都要机票，于是若干进程都要访访访访问同一个问同一个问同一个问同一个AjAj，则结果可能出，则结果可能出，则结果可能出，则结果可能出现同一张票卖给几个不同的现同一张票卖给几个不同的现同一张票卖给几个不同的现同一张票卖给几个不同的旅客旅客旅客旅客Process Pi（i=1，2，n）根据用户需求根据用户需求找到找到Aj;Ri=Aj;if(Ri=1)Ri=Ri-1;Aj=Ri;提示已卖出一张票信息；提示已卖出一张票信息；else 输出输出“票已售完票已售完”；3.1与时间有关的错误问题(2)可能产生的错误结果Proce93.1与时间有关的错误问题(2)假设某一个时刻三个客户在不同网点但几乎同假设某一个时刻三个客户在不同网点但几乎同假设某一个时刻三个客户在不同网点但几乎同假设某一个时刻三个客户在不同网点但几乎同时到达购票访问的情况时到达购票访问的情况时到达购票访问的情况时到达购票访问的情况进程进程进程进程t1t1t2t2t3t3t4t4t5t5P1P1R1=AjR1=AjR1=R1-1R1=R1-1Aj=R1Aj=R1P2P2R2=AjR2=AjR2=R2-1R2=R2-1Aj=R2Aj=R2P3P3R3=AjR3=AjR3=R3-1R3=R3-13.1与时间有关的错误问题(2)假设某一个时刻三个客户在不同103.2 进程的协调概念 在在os支持下，多个进程既独立又并发执支持下，多个进程既独立又并发执行，然而进程之间可能行，然而进程之间可能合作合作完成一项任完成一项任务，可能务，可能共享共享一种系统资源，可能相互一种系统资源，可能相互支持和依赖，甚至制约对方，为了协调支持和依赖，甚至制约对方，为了协调进程间的关系，进程间的关系，os必须进行必须进行进程间的协进程间的协调调。3.2 进程的协调概念在os支持下，多个进程既独立又并发执行113.2 进程的制约关系 直接直接直接直接相互制约关系相互制约关系相互制约关系相互制约关系 源于进程的源于进程的源于进程的源于进程的合作合作合作合作，同步关系，同步关系，同步关系，同步关系 如：如：如：如：A A、B B两个进程通过缓冲区合作完成一项任务，两个进程通过缓冲区合作完成一项任务，两个进程通过缓冲区合作完成一项任务，两个进程通过缓冲区合作完成一项任务，A A负责存数据到缓冲区，负责存数据到缓冲区，负责存数据到缓冲区，负责存数据到缓冲区，B B负责从缓冲区中取数。负责从缓冲区中取数。负责从缓冲区中取数。负责从缓冲区中取数。间接间接间接间接相互制约关系相互制约关系相互制约关系相互制约关系 源于资源源于资源源于资源源于资源共享共享共享共享，互斥关系，互斥关系，互斥关系，互斥关系 如：如：如：如：A A、B B两个进程共享打印机，若分配给两个进程共享打印机，若分配给两个进程共享打印机，若分配给两个进程共享打印机，若分配给A A，则当，则当，则当，则当B 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 简单的同步机制单标志位法算法的基本思想算法的基本思想 设置一个标志变量设置一个标志变量设置一个标志变量设置一个标志变量turnturn，两个进程，两个进程，两个进程，两个进程P0P0、P1P1要进要进要进要进入临界区先要访问该标志，根据标志值决定自入临界区先要访问该标志，根据标志值决定自入临界区先要访问该标志，根据标志值决定自入临界区先要访问该标志，根据标志值决定自己是否进入临界区。例如当己是否进入临界区。例如当己是否进入临界区。例如当己是否进入临界区。例如当turn=0turn=0，表示允许，表示允许，表示允许，表示允许P0P0进程进入，当进程进入，当进程进入，当进程进入，当P0P0退出临界区后，置退出临界区后，置退出临界区后，置退出临界区后，置turn=1turn=1，P1P1才可进入临界区；反之当才可进入临界区；反之当才可进入临界区；反之当才可进入临界区；反之当turnturn1 1，表示允，表示允，表示允，表示允许许许许P1P1进程进入，退出时置进程进入，退出时置进程进入，退出时置进程进入，退出时置turn=0turn=0，则，则，则，则P0P0才可进才可进才可进才可进入。入。入。入。3.4 简单的同步机制单标志位法算法的基本思想213.4 简单的同步机制单标志位法Process P0 do while(turn!=0);临界区 turn=1;剩余区 while(1);Process P1 do while(turn!=1);临界区 turn=0;剩余区 while(1);初始值 turn=0;或者 turn=1;3.4 简单的同步机制单标志位法Process P0Pro223.4 简单的同步机制单标志位法该算法的致命缺点该算法的致命缺点 要求进入临界区执行的两个进程必须要求进入临界区执行的两个进程必须要求进入临界区执行的两个进程必须要求进入临界区执行的两个进程必须严格严格严格严格的交的交的交的交替运行。替运行。替运行。替运行。当进程当进程当进程当进程A A大于大于大于大于进程进程进程进程B B时，将阻塞进程时，将阻塞进程时，将阻塞进程时，将阻塞进程B B再次进入再次进入再次进入再次进入临界区（因为交替原则，临界区（因为交替原则，临界区（因为交替原则，临界区（因为交替原则，B B必须等待必须等待必须等待必须等待A A执行结束）执行结束）执行结束）执行结束），即产生了，即产生了，即产生了，即产生了长进程阻塞短进程长进程阻塞短进程长进程阻塞短进程长进程阻塞短进程的问题。的问题。的问题。的问题。不满足临界区管理的第一个准则，因为存在一不满足临界区管理的第一个准则，因为存在一不满足临界区管理的第一个准则，因为存在一不满足临界区管理的第一个准则，因为存在一个进程当它在剩余区时，也不允许另一个进程个进程当它在剩余区时，也不允许另一个进程个进程当它在剩余区时，也不允许另一个进程个进程当它在剩余区时，也不允许另一个进程进入临界区。进入临界区。进入临界区。进入临界区。3.4 简单的同步机制单标志位法该算法的致命缺点233.4 简单的同步机制双标志位法算法的基本思想算法的基本思想 先修改后检查算法先修改后检查算法先修改后检查算法先修改后检查算法 为每个进程都设置一个标志位，引入数组为每个进程都设置一个标志位，引入数组为每个进程都设置一个标志位，引入数组为每个进程都设置一个标志位，引入数组flag2flag2，初始化为，初始化为，初始化为，初始化为falsefalse，表示临界区中无进程，欲进入，表示临界区中无进程，欲进入，表示临界区中无进程，欲进入，表示临界区中无进程，欲进入者可以进入。进程者可以进入。进程者可以进入。进程者可以进入。进程PiPi欲进入时将自身标志欲进入时将自身标志欲进入时将自身标志欲进入时将自身标志flagiflagi置为置为置为置为truetrue，阻止另一个进程进入，接着判定对方，阻止另一个进程进入，接着判定对方，阻止另一个进程进入，接着判定对方，阻止另一个进程进入，接着判定对方的标志是否为的标志是否为的标志是否为的标志是否为falsefalse，若是才可以进入临界区，否，若是才可以进入临界区，否，若是才可以进入临界区，否，若是才可以进入临界区，否则必须等待；任一个进程退出临界区后都将自身则必须等待；任一个进程退出临界区后都将自身则必须等待；任一个进程退出临界区后都将自身则必须等待；任一个进程退出临界区后都将自身标志置为标志置为标志置为标志置为falsefalse，表示退出临界区，允许对方进程，表示退出临界区，允许对方进程，表示退出临界区，允许对方进程，表示退出临界区，允许对方进程进入临界区。进入临界区。进入临界区。进入临界区。3.4 简单的同步机制双标志位法算法的基本思想243.4 简单的同步机制双标志位法(1)算法的主要伪代码算法的主要伪代码Process P0 do flag0=true;while(flag1);临界区 flag0=false;剩余区 while(1);Process P1 do flag1=true;while(flag0);临界区 flag1=false;剩余区 while(1);初始值 flagi=false3.4 简单的同步机制双标志位法(1)算法的主要伪代码Pr253.4简单的同步机制双标志位法(1)算法的特点算法的特点 可以解决两个进程严格交替的问题可以解决两个进程严格交替的问题 但当两个进程几乎同时到达时，结果两但当两个进程几乎同时到达时，结果两个进程都不能进入临界区执行个进程都不能进入临界区执行 产生死锁问题产生死锁问题 可能导致对方进程的可能导致对方进程的“饥饿饥饿”问题，将问题，将永远被阻塞永远被阻塞 不满足不满足管理准则中的管理准则中的“空闲让进空闲让进”3.4简单的同步机制双标志位法(1)算法的特点263.4 简单的同步机制双标志位法(2)算法的基本思想算法的基本思想 先检查先检查算法算法 交换修改与检查语句的顺序，先做交换修改与检查语句的顺序，先做while检查，再做检查，再做true值的设置修改值的设置修改3.4 简单的同步机制双标志位法(2)算法的基本思想273.4 简单的同步机制双标志位法(2)算法的主要伪代码算法的主要伪代码Process P0 do while(flag1);flag0=true;临界区 flag0=false;剩余区 while(1);Process P1 do while(flag0);flag1=true;临界区 flag1=false;剩余区 while(1);3.4 简单的同步机制双标志位法(2)算法的主要伪代码Pr283.4 简单的同步机制双标志位法(2)算法的致命缺点算法的致命缺点 比前两种方法更差，不能解决互斥问题比前两种方法更差，不能解决互斥问题 导致所有进程都可以进入临界区导致所有进程都可以进入临界区 不满足不满足管理准则中的管理准则中的“忙则等待忙则等待”3.4 简单的同步机制双标志位法(2)算法的致命缺点293.4 简单的同步机制三标志位法算法的基本思想算法的基本思想算法的基本思想算法的基本思想 先修改、后检查、先修改、后检查、先修改、后检查、先修改、后检查、后修改者等待后修改者等待后修改者等待后修改者等待算法算法算法算法 为了解决两个进程的同时到达问题，将前两者为了解决两个进程的同时到达问题，将前两者为了解决两个进程的同时到达问题，将前两者为了解决两个进程的同时到达问题，将前两者算法结合，在双标志法的基础上再引入算法结合，在双标志法的基础上再引入算法结合，在双标志法的基础上再引入算法结合，在双标志法的基础上再引入turnturn变变变变量，当两个进程几乎同时到达时，进程根据量，当两个进程几乎同时到达时，进程根据量，当两个进程几乎同时到达时，进程根据量，当两个进程几乎同时到达时，进程根据turnturn值决定哪一个进程进入临界区，即保证任值决定哪一个进程进入临界区，即保证任值决定哪一个进程进入临界区，即保证任值决定哪一个进程进入临界区，即保证任一个时刻，一个时刻，一个时刻，一个时刻，turnturn值为值为值为值为0 0或者为或者为或者为或者为1 1，使得只有一个，使得只有一个，使得只有一个，使得只有一个进程满足条件而进入临界区。进程满足条件而进入临界区。进程满足条件而进入临界区。进程满足条件而进入临界区。3.4 简单的同步机制三标志位法算法的基本思想303.4 简单的同步机制三标志位法 算法的主要伪代码Process P0 do flag0=true;turn=1;while(flag1&turn=1);临界区 flag0=false;剩余区 while(1);Process P1 do flag1=true;turn=0;while(flag0&turn=0);临界区 flag0=false;剩余区 while(1);3.4 简单的同步机制三标志位法算法的主要伪代码Proce313.4 简单的同步机制三标志位法 两个进程几乎同时到达的情况 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的剩余区 3.4 简单的同步机制三标志位法两个进程几乎同时到达的情况323.4 简单的同步机制三标志位法 两个进程几乎同时到达的情况 flag0=true;flag1=true;turn=1;turn=0;/后修改者P1 while(flag0&turn=0);/P1被挂起 while(flag1&turn=1);/P0被批准进入 临界区 /P0进入临界区 flag0=false;/P0退出，P1可被解除 剩余区 /P0的剩余区 3.4 简单的同步机制三标志位法两个进程几乎同时到达的情况333.4 简单的同步机制三标志位法 两个进程几乎同时到达的情况 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的剩余区 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值减一值减一值减一值减一 若若若若S0S=0S=0，当前进程，当前进程，当前进程，当前进程继继继继续运行续运行续运行续运行(说明等待队列说明等待队列说明等待队列说明等待队列无进程，当前进程可无进程，当前进程可无进程，当前进程可无进程，当前进程可继续不阻塞继续不阻塞继续不阻塞继续不阻塞)P操作的伪代码P(int s)s-;if(s0)wait();/当前被挂起 return;/当前继续3.5 信号量机制P操作P(S)操作的定义P操作的伪代码413.5 信号量机制V操作V(S)V(S)操作的定义操作的定义操作的定义操作的定义 S S值加一；值加一；值加一；值加一；若若若若S=0S0S0，当前进程，当前进程，当前进程，当前进程继续继续继续继续执行执行执行执行（说明等待队列无（说明等待队列无（说明等待队列无（说明等待队列无进程，无需执行唤醒操进程，无需执行唤醒操进程，无需执行唤醒操进程，无需执行唤醒操作）作）作）作）V操作的伪代码V(int s)s+;if(s=0)wakeup();/移出一个进程，插入就绪队列，相当唤醒 return;/当前继续3.5 信号量机制V操作V(S)操作的定义V操作的伪代码423.5 信号量机制解决互斥问题 如果有若干个进程都调用如果有若干个进程都调用如果有若干个进程都调用如果有若干个进程都调用P P操作操作操作操作(提提提提出申请出申请出申请出申请)，则只有，则只有，则只有，则只有第一个第一个第一个第一个调用调用调用调用P P操作操作操作操作的进程不成为等待状态而可以继续的进程不成为等待状态而可以继续的进程不成为等待状态而可以继续的进程不成为等待状态而可以继续执行执行执行执行 P P操作第一次调用后，操作第一次调用后，操作第一次调用后，操作第一次调用后，S S的值成为的值成为的值成为的值成为“0”“0”，以后的进程调用，以后的进程调用，以后的进程调用，以后的进程调用P P操作时，操作时，操作时，操作时，S S值值值值总小于总小于总小于总小于0 0（S0,S=1)R=Aj;R=R-1;Aj=R;提示已卖出一张票信息；提示已卖出一张票信息；else 输出票已售完；输出票已售完；3.5 信号量机制订票系统问题飞机订票系统关于联网订票的513.5 信号量机制订票系统问题 解决互斥方法一解决互斥方法一Process pi int R;根据用户需求找到根据用户需求找到Aj;if(Aj=1)P(S);R=Aj;R=R-1;Aj=R;V(S);提示已卖出一张票信息；提示已卖出一张票信息；else 输出票已售完；输出票已售完；Semaphore S=1;思考：互斥问题是否得到解决？如果没有，原因在哪？3.5 信号量机制订票系统问题解决互斥方法一Proces523.5 信号量机制订票系统问题法一的问题分析法一的问题分析法一的问题分析法一的问题分析 表面上看实现互斥的管理，实际上仍然存在读表面上看实现互斥的管理，实际上仍然存在读表面上看实现互斥的管理，实际上仍然存在读表面上看实现互斥的管理，实际上仍然存在读取相同取相同取相同取相同AjAj值的情况值的情况值的情况值的情况 分析判定分析判定分析判定分析判定共享资源共享资源共享资源共享资源应该是：应该是：应该是：应该是：AjAj变量变量变量变量 分析判定分析判定分析判定分析判定临界区临界区临界区临界区：包括所有对：包括所有对：包括所有对：包括所有对AjAj变量操作的代变量操作的代变量操作的代变量操作的代码区码区码区码区 注意：若查询注意：若查询注意：若查询注意：若查询结果是无票结果是无票结果是无票结果是无票，虽不影响临界区的，虽不影响临界区的，虽不影响临界区的，虽不影响临界区的使用，不产生错误，但存在潜在的错误使用，不产生错误，但存在潜在的错误使用，不产生错误，但存在潜在的错误使用，不产生错误，但存在潜在的错误3.5 信号量机制订票系统问题法一的问题分析533.5 信号量机制订票系统问题 互斥解法二互斥解法二Semaphore S=1;Process pi（修改进程的表示）（修改进程的表示）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 输出票已售完；输出票已售完；3.5 信号量机制订票系统问题互斥解法二Semaphor543.5 信号量机制订票系统问题法二的问题分析法二的问题分析 PV操作没有操作没有成对成对出现出现 对第一个查询结果无票的进程而言，能对第一个查询结果无票的进程而言，能顺利退出临界区，但后续进程均被挂起，顺利退出临界区，但后续进程均被挂起，不能得到响应不能得到响应 导致系统内部存在导致系统内部存在“饥饿饥饿”进程进程3.5 信号量机制订票系统问题法二的问题分析553.5 信号量机制订票系统问题 正确的解法正确的解法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操操作的成对性作的成对性3.5 信号量机制订票系统问题正确的解法Semaphor563.5 信号量机制订票系统问题对信号量对信号量对信号量对信号量S S的分析的分析的分析的分析 S S1 1，表示当前共享资源只有一个可供使用。（且，表示当前共享资源只有一个可供使用。（且，表示当前共享资源只有一个可供使用。（且，表示当前共享资源只有一个可供使用。（且任何时刻只能一个进程进入临界区，其他欲进入的任何时刻只能一个进程进入临界区，其他欲进入的任何时刻只能一个进程进入临界区，其他欲进入的任何时刻只能一个进程进入临界区，其他欲进入的进程必须等待进程必须等待进程必须等待进程必须等待互斥概念）互斥概念）互斥概念）互斥概念）S S0 0，表示有一个进程在临界区，无可用资源，表示有一个进程在临界区，无可用资源，表示有一个进程在临界区，无可用资源，表示有一个进程在临界区，无可用资源 S S-1-1，-2-2表示有表示有表示有表示有1 1个、个、个、个、2 2个个个个等待的进程等待的进程等待的进程等待的进程 S S的的的的取值范围取值范围取值范围取值范围：(-(n-1)(-(n-1)1)1)|S|S|的含义：表示有的含义：表示有的含义：表示有的含义：表示有|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”时，表示期望的消息还没有产生，当信号量的值时，表示期望的消息还没有产生，当信号量的值时，表示期望的消息还没有产生，当信号量的值时，表示期望的消息还没有产生，当信号量的值为非为非为非为非“0”“0”时表示期望的消息已经存在。时表示期望的消息已经存在。时表示期望的消息已经存在。时表示期望的消息已经存在。3.5 信号量机制解决同步问题问题提出61实现方法实现方法 通过调用通过调用通过调用通过调用P P操作操作操作操作可以测试自己所期望的消息是可以测试自己所期望的消息是可以测试自己所期望的消息是可以测试自己所期望的消息是否到达（相当否到达（相当否到达（相当否到达（相当申请申请申请申请进入临界区）进入临界区）进入临界区）进入临界区）而任何进程要向其它进程发送消息时（相当而任何进程要向其它进程发送消息时（相当而任何进程要向其它进程发送消息时（相当而任何进程要向其它进程发送消息时（相当唤唤唤唤醒醒醒醒下一个进程进入临界区）可以调用下一个进程进入临界区）可以调用下一个进程进入临界区）可以调用下一个进程进入临界区）可以调用V V操作操作操作操作3.5 信号量机制解决同步问题实现方法3.5 信号量机制解决同步问题623.5 信号量机制解决同步问题实现原理实现原理 P操作的理解操作的理解用信号量用信号量用信号量用信号量S S表示一种消息，如果消息表示一种消息，如果消息表示一种消息，如果消息表示一种消息，如果消息还没有还没有还没有还没有产生，则产生，则产生，则产生，则S S0 0，调用，调用，调用，调用P(S)P(S)操作后，调用者将操作后，调用者将操作后，调用者将操作后，调用者将成为成为成为成为等待等待等待等待状态，申请进入临界区失败。状态，申请进入临界区失败。状态，申请进入临界区失败。状态，申请进入临界区失败。如果消息已经如果消息已经如果消息已经如果消息已经存在存在存在存在，则，则，则，则S0S0,调用调用调用调用P(S)P(S)操作操作操作操作后，调用者不会成为等待状态，即申请进入后，调用者不会成为等待状态，即申请进入后，调用者不会成为等待状态，即申请进入后，调用者不会成为等待状态，即申请进入临界区成功。临界区成功。临界区成功。临界区成功。3.5 信号量机制解决同步问题实现原理633.5 信号量机制解决同步问题实现原理实现原理 V V操作的理解操作的理解操作的理解操作的理解 若调用若调用若调用若调用V(S)V(S)操作操作操作操作前前前前S S0 0，表示消息还没有产生也，表示消息还没有产生也，表示消息还没有产生也，表示消息还没有产生也没有等待没有等待没有等待没有等待消息的进程，这时调用消息的进程，这时调用消息的进程，这时调用消息的进程，这时调用V(S)V(S)操作后，操作后，操作后，操作后，S!=0S!=0，调用，调用，调用，调用V(S)V(S)后，意味着消息产生，即相当通后，意味着消息产生，即相当通后，意味着消息产生，即相当通后，意味着消息产生，即相当通知或者唤醒操作。知或者唤醒操作。知或者唤醒操作。知或者唤醒操作。若调用若调用若调用若调用V V操作操作操作操作前前前前S0S0，表示消息还没有产生且有进，表示消息还没有产生且有进，表示消息还没有产生且有进，表示消息还没有产生且有进程在程在程在程在等待等待等待等待该消息，这时调用该消息，这时调用该消息，这时调用该消息，这时调用V(S)V(S)操作后将操作后将操作后将操作后将释放释放释放释放一一一一个在等待消息的进程，即调用个在等待消息的进程，即调用个在等待消息的进程，即调用个在等待消息的进程，即调用V(S)V(S)操作的进程把操作的进程把操作的进程把操作的进程把消息发给在等待消息的进程且允许它继续进行，消息发给在等待消息的进程且允许它继续进行，消息发给在等待消息的进程且允许它继续进行，消息发给在等待消息的进程且允许它继续进行，即相当通知或者唤醒操作。即相当通知或者唤醒操作。即相当通知或者唤醒操作。即相当通知或者唤醒操作。3.5 信号量机制解决同步问题实现原理643.5 经典同步问题 生产者/消费者问题 生产者与消费者问题描述 现假定有一个生产者和一个消费者，他们现假定有一个生产者和一个消费者，他们共用一个缓共用一个缓冲器冲器，生产者，生产者不断不断地生产物品，每生产一件物品就要存入地生产物品，每生产一件物品就要存入缓冲器，但缓冲器中每次只能缓冲器，但缓冲器中每次只能存入一件物品存入一件物品，只有当消费，只有当消费者把物品取走后，生产者才能把第二件物品存入缓冲器。者把物品取走后，生产者才能把第二件物品存入缓冲器。同样地，消费者同样地，消费者不断不断地取出物品去消费，当缓冲器中有物地取出物品去消费，当缓冲器中有物品时他就可以去取，每取走一件物品后品时他就可以去取，每取走一件物品后必须等生产者必须等生产者放入放入一件物品才可一件物品才可再取再取。3.5 经典同步问题 653.5 经典同步问题 生产者/消费者问题生产者进程和消费者进程生产者进程和消费者进程生产者进程和消费者进程生产者进程和消费者进程（未采用同步机制前的主要代码）（未采用同步机制前的主要代码）（未采用同步机制前的主要代码）（未采用同步机制前的主要代码）Process producer L1:produce a product;Buffer=product;goto L1;Process consumer L1:take a product from Buffer;consume;goto L1;3.5 经典同步问题 663.5 经典同步问题 生产者/消费者问题问题分析问题分析 消息的个数：消息的个数：消息的个数：消息的个数：2 2个个个个 需要的信号量两个，定义两个变量需要的信号量两个，定义两个变量需要的信号量两个，定义两个变量需要的信号量两个，定义两个变量SPSP、SGSG分分分分别表示生产者和消费者的信号量别表示生产者和消费者的信号量别表示生产者和消费者的信号量别表示生产者和消费者的信号量(私有信号量私有信号量私有信号量私有信号量)两个进程生产和消费各自独立，两个进程生产和消费各自独立，两个进程生产和消费各自独立，两个进程生产和消费各自独立，并发并发并发并发执行执行执行执行 两个进程只在两个进程只在两个进程只在两个进程只在访问公共访问公共访问公共访问公共的缓冲器把物品存入或的缓冲器把物品存入或的缓冲器把物品存入或的缓冲器把物品存入或取出时才要互通消息取出时才要互通消息取出时才要互通消息取出时才要互通消息3.5 经典同步问题 673.5 经典同步问题 生产者/消费者问题信号量初值的分析信号量初值的分析 初始状态，缓冲器为初始状态，缓冲器为初始状态，缓冲器为初始状态，缓冲器为空空空空，允许生产者生产的物，允许生产者生产的物，允许生产者生产的物，允许生产者生产的物品存入缓冲器，相当于品存入缓冲器，相当于品存入缓冲器，相当于品存入缓冲器，相当于通知通知通知通知消费者进程取物品消费者进程取物品消费者进程取物品消费者进程取物品的的的的消息消息消息消息已经已经已经已经到了到了到了到了，代表此消息的信号量，代表此消息的信号量，代表此消息的信号量，代表此消息的信号量SPSP初值初值初值初值应该应该应该应该为为为为“1”“1”。初始状态，缓冲区为初始状态，缓冲区为初始状态，缓冲区为初始状态，缓冲区为空空空空，不能取数消费，也就，不能取数消费，也就，不能取数消费，也就，不能取数消费，也就不能通知不能通知不能通知不能通知再生产，所以对应信号量再生产，所以对应信号量再生产，所以对应信号量再生产，所以对应信号量SGSG的初值应的初值应的初值应的初值应该该该该为为为为“0”“0”。3.5 经典同步问题 683.5 经典同步问题 生产者/消费者问题 信号量的定义信号量的定义Semaphore SP,SG;SP=1;SG=0;SP：表示是否可以把物品存入缓冲区，由于缓冲区：表示是否可以把物品存入缓冲区，由于缓冲区每次只能放一个物品，所以初值为每次只能放一个物品，所以初值为1。SG：表示缓冲区是否存在有物品，显然初值为：表示缓冲区是否存在有物品，显然初值为0，表，表示开始还没有物品在缓冲区。示开始还没有物品在缓冲区。3.5 经典同步问题 693.5 经典同步问题 生产者/消费者问题实现的基本方法实现的基本方法实现的基本方法实现的基本方法 生产者生产者生产者生产者进入缓冲区前调用进入缓冲区前调用进入缓冲区前调用进入缓冲区前调用P P操作操作操作操作判断消息是否判断消息是否判断消息是否判断消息是否到达，或者说申请进入的消息是否允许通过，到达，或者说申请进入的消息是否允许通过，到达，或者说申请进入的消息是否允许通过，到达，或者说申请进入的消息是否允许通过，退出缓冲区时，调用退出缓冲区时，调用退出缓冲区时，调用退出缓冲区时，调用V V操作操作操作操作发送消息通知消费发送消息通知消费发送消息通知消费发送消息通知消费者，相当唤醒消费者者，相当唤醒消费者者，相当唤醒消费者者，相当唤醒消费者 消费者消费者消费者消费者在进入缓冲区前，首先调用在进入缓冲区前，首先调用在进入缓冲区前，首先调用在进入缓冲区前，首先调用P P操作操作操作操作判断判断判断判断是否可以取数，即通知取数的消息是否到达，是否可以取数，即通知取数的消息是否到达，是否可以取数，即通知取数的消息是否到达，是否可以取数，即通知取数的消息是否到达，当取数后退出缓冲区，调用当取数后退出缓冲区，调用当取数后退出缓冲区，调用当取数后退出缓冲区，调用V V操作操作操作操作，发送消息，发送消息，发送消息，发送消息，通知生产者通知生产者通知生产者通知生产者3.5 经典同步问题 703.5 经典同步问题 生产者/消费者问题 将将将将PVPV操作加入到原来的伪代码中，结果如下操作加入到原来的伪代码中，结果如下操作加入到原来的伪代码中，结果如下操作加入到原来的伪代码中，结果如下Semaphore SP,SG;SP=1;SG=0;int Buffer;Process producer L1:produce a product;P(SP);Buffer=