并发性：互斥和同步课件

计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第5章 并发：互斥与同步Chapter 5 Concurrency:Mutual Exclusion and Synchronization内容提要n并发原理n互斥的软硬件实现n信号量（semaphore，旗语/信号灯）nmonitor，监视器/监控程序）n消息传递n读者-写者问题1计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月操作系统设计的核心问题n进程与线程的管理（本章中的进程也代表线程）n多道程序设计技术管理单核处理器系统中的多个进程n多处理技术管理多核处理器系统中的多个进程n分布式处理技术管理多台分布式计算机系统中的多个进程n并发（concurrency）多道程序设计/多任务处理n所有问题的基础/根源n操作系统设计的基础n并发发生的上下文n多个应用程序（多道）n结构化应用程序（模块）n操作系统结构（结构化/模块）2计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月并发相关术语n原子操作（atomic operation）不可分割n临界区（critical section）不允许多个进程同时进入的一段访问共享资源的代码代码n死锁（deadlock）两个及以上进程，因每个进程都在等待其他进程做完某事（如释放资源），而不能继续执行n活锁（livelock）两个及以上进程，为响应其他进程中的变化，而不断改变自己的状态，但是没有做任何有用的工作n互斥（mutual exclusion）当一个进程在临界区访问共享资源时，不允许其他进程进入访问n竞争条件（race condition）多个进程/线程读写共享数据，其结果依赖于它们执行的相对速度n饥饿（starvation）可运行的进程长期未被调度执行3计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月上篇并发性引发的问题并发性引发的问题 资源竞争共享、分配管理困难难调试（不可再现）进程的相互作用进程的相互作用 通过共享的竞争 通过共享的合作 通过通信的合作|进程的互斥机制进程的互斥机制软件方法（Dekker算法、Peterson算法）硬件件方法（关中断、专用指令TestSet/Exchange）4计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月5.1 并发的原理5计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月并发的基本特征n并发并发n在同一时间间隔内发生的进程或线程，在此期间，它们可能交替地共享相同的资源n异步性n相对执行速度不可预测是多道程序系统的基本特性n影响进程执行速度的因素n其他进程的活动nOS处理中断的方式nOS的调度策略n存在的问题n全局资源的共享充满危险nOS对资源分配的管理难以达到最优n调试程序设计错误非常困难（不可再现性）6计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月5.1.1 与执行速度有关的错误n解决办法:n控制访问全局共享资源的代码！void echo()chin=getchar();chout=chin;putchar(chout);Process P1Process P2 chin=getchar();chin=getchar();chout=chin;putchar(chout);chout=chin;putchar(chout);P1中chin的值在赋值给chout前被P2修改7计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月5.1.2 竞争条件n在并发环境中发生n多个进程共享数据n多个进程读取且至少一个进程写入n共享数据的最终结果取决于进程执行的相对速度最终结果取决于进程执行的相对速度8计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月5.1.3 OS必须考虑的问题n并发环境中跟踪每个进程，知道它们的状态n为每个进程分配和回收各种资源（管理资源）n处理机（进程调度）n存储器（内存管理）n文件（文件系统）nI/O设备（I/O管理）n保护进程拥有的数据和物理资源n保证进程的结果与相对执行速度无关（逻辑上的正确性）保证进程的结果与相对执行速度无关（逻辑上的正确性）9计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月5.1.4 进程间的相互作用n间接作用间接作用n因为共享而竞争n通过共享实现合作n直接作用直接作用n通过通信的合作10计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月进程间的竞争现象n特点：n独立设计的进程，每个进程不知道其他进程的存在（“萍水相逢”、“我不知道你是谁”）n两个或更多进程在各自的执行过程中需要访问相同的资源（I/O设备、存储器、CPU、时钟等）（“独木桥上，狭路相逢”）n进程之间没有信息交换的要求（“井水不犯河水”）n相互间产生的影响：n执行结果不会受影响n执行时间受影响n竞争引发的控制问题n互斥(mutual exclusion)n死锁(deadlock)n饥饿(starvation)11计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月互斥的关联概念n互斥（互斥（mutual exclusion）n多个进程需要访问一个不可共享的资源不可共享的资源时，任何时候只能有一个访问这个资源n临界资源（临界资源（critical resource）n不可共享的资源不可共享的资源n临界区（临界区（critical section）n访问临界资源的那部分代码代码n死锁死锁(deadlock)n一组进程中，每个进程都无限等待该组进程中另一进程所占用的资源n饥饿饥饿(starvation)n一组进程中，某个或某些进程无限等待该组进程中其他进程所占用的资源12计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月互斥机制原理程序框架void P1()while(true)/*preceding code*/entercritical(Ra);/*critical section Ra*/exitcritical(Ra);/*following code*/void P2().void main()parbegin(P1(),P2(),Pn();void Pn().竞争资源Ra的临界区13计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月进程间通过共享的合作n特点特点n没有意识到其他进程的存在，但知道要维护数据的完整性n共享变量、文件或数据库等n相互间产生的影响：n执行结果可能会受影响n执行时间受影响n共享引发的控制问题n互斥n死锁n饥饿n数据的一致性P1:P2:a=a+1;b=2*b;b=b+1;a=2*a;14计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月进程间通过通信的合作n特点n进程直接知道合作伙伴n采用消息传送的方式通信（发送/接收消息）n相互间产生的影响：同“通过共享的合作”n引发的控制问题:n死锁n饥饿15计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月5.1.5 互斥的要求 n在具有相同资源或共享对象的临界区的所有进程中，一次只允许一个进程进入临界区（强制排它强制排它）n一个在非临界区停止的进程必须不干涉其他进程（充分充分并发并发）n没有进程在临界区中时，任何需要访问临界区的进程必须能够立即进入（空闲让进空闲让进）n决不允许出现一个需要访问临界区的进程被无限延迟（有限等待有限等待）n相关进程的执行速度和处理机数目没有任何要求或限制（满足异步满足异步）n当进程不能进入临界区，应该立即释放处理机，防止进程忙等待（让权等待让权等待）16计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月 实现互斥的方法n软件方法nDekker算法nPeterson算法n硬件方法nTestSet指令nExchange指令nOS或程序设计语言的支持n信号量n管程n消息机制17计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第一种尝试的方案用turn序来轮流18计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第一种尝试的特点n可以保证互斥可以保证互斥n硬性规定进入的顺序硬性规定进入的顺序n两个进程轮流进入临界区n存在问题存在问题n忙等待忙等待(busy waiting):为了等待一事件的发生，重复执行一段循环代码-白白消耗CPU时间n必须轮流进入临界区-不合理，限制推进速度n如果一个进程失败，另一个将被永远阻塞n结论结论n难以支持并发处理19计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第二种尝试的方案用flagi标志进程i进入临界区20计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第二种尝试的特点n每个进程应有自己进入临界区的每个进程应有自己进入临界区的“钥匙钥匙”n进程设置标志表示自己进入和离开n可以检查对方标志n先查对方标志再设置自己进入临界区的标志n存在问题存在问题n一个进程在临界区内失败，另一进程永远被阻塞n不能保证互斥!（见示意图）n结论结论n错误方案，不能保证进程的运行结果与执行速度无关21计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第二种尝试的失效示意图P0:while(Flag1)/*do nothing*/;Flag0=true;/*critical section*/Flag0=false;P1:while(Flag0)/*do nothing*/;Flag1=true;/*critical section*/Flag1=false;如果在红线处被切换，则可能两个进程同时进入临界区22计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第三种尝试的方案将flagi标志的设置，提前到循环等待之前23第三种尝试的特点n先表示自己想进入临界区，再检查对方是否已进入n可以保证互斥可以保证互斥n问题问题n可能导致死锁!n死锁产生的原因死锁产生的原因n两进程都坚持要进入（见示意图）第三种尝试的死锁时序P1:Flag0=true;while(Flag1);P2:Flag1=true;while(Flag0);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第四种尝试的方案在循环等待中用延时给其他进程进入的机会26计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月第四种尝试的特点n解决思路解决思路 n礼让，等一会.n可以保证互斥可以保证互斥n问题问题n会导致活锁n死锁与活锁死锁与活锁n死锁:都想进入临界区，但都不能进入n活锁:本来可以进入临界区，但都进入不了27第四种尝试的活锁时序P0:Flag0=true;while(Flag1)Flag0=false;delay();Flag0=true;/*critical section*/Flag0=false;P1:Flag1=true;while(Flag0)Flag1=false;delay();Flag1=true;/*critical section*/Flag1=false;计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月boolean flag2;int turn;void P0()while(true)flag0=true;/自己想进临界区 /flag1=false时进入临界区 while(flag1)/flag1=true时等待 if(turn=1)/turn=1时礼让 flag0=false;while(turn=1)/*do nothing*/;flag0=true;/*critical section*/turn=1;flag0=false;/*remainder*/Dekker算法n1965年荷兰数学家T.J.Dekker（德克）n避免“无原则”的礼让n规定各进程进入临界区的顺序n用全局数组变量flag表示互斥进程的位置n用全局变量turn解决同时发生的冲突n参见附录A“并发主题”中的A.1.1（P502）Dekker算法描述29计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月Dekker算法描述（续）void P1()while(true)flag1=true;/自己想进临界区 /flag0=false时进入临界区 while(flag0)/flag0=true时等待 if(turn=0)/turn=0时礼让 flag1=false;while(turn=0)/*do nothing*/;flag1=true;/*critical section*/turn=0;flag1=false;/*remainder*/void main()flag0=false;flag1=false;turn=1;parbegin(P0,P1);n算法的问题n逻辑复杂n正确性难证明n存在轮流问题n存在忙等待30计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月boolean flag 2;int turn;void P0()while(true)flag 0=true;turn=1;while(flag 1&turn=1)/*do nothing*/;/*critical section*/flag 0=false;/*remainder*/Peterson算法n1981年数学家G.L.Peterson（彼得森）n简单出色（不存在轮流问题）nflag和turn的含义同Dekker的n但先设turn=别人，且只有“flag别人”和“turn=别人”同时为真时才循环等待n参见附录A“并发主题”中的A.1.2（P505）Peterson算法描述31计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月Peterson算法描述（续）void P1()while(true)flag 1=true;turn=0;while(flag 0&turn=0)/*do nothing*/;/*critical section*/flag 1=false;/*remainder*/void main()flag 0=false;flag 1=false;parbegin(P0,P1);32计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月硬件实现方法关中断n中断禁用的（关中断）原理n单CPU体系结构n如果进程访问临界资源时（执行临界区代码）不被中断，就能保证互斥地访问n途径n使用关/开中断指令nx86的开/关指令为STI/CLIn缺点n限制了处理器交替执行各进程的能力n不能用于多核处理器结构关中断指令临界区开中断指令33计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月硬件实现方法专用指令n适用范围n单处理器或共享主存多核处理器结构n对同一存储单元的访问是互斥的n软件算法第二种尝试失败的原因n如果测flag1和置位flag0在一个指令周期完成就不会出错34计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月比较和交换指令n原子指令一个指令周期内完成,不会被中断n由两部分构成：比较内存单元与测试值，不同则产生交换n检查内存单元*word的值是否与测试值testval相等，若相等就用newval取代该值，否则保持不变n总是返回旧内存单元的值。若返回值=测试值，则表示该内存单元已经被更新n486以上的x86/x64 CPU的对应指令为CMPXCHG，可用于操作系统支持并发计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月比较和交换指令的定义（等价代码段）int compare_and_swap(int*word,int testval,int newval)int oldval;oldval=*wordif(oldval=testval)*word=newval;return oldval;例如：(bolt=门闩/锁条)If(compare_and_s,0,1)=0)/*critical section*/计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月TestSet指令(TS)n定义（逻辑）比较并交换指令的bool特例n原子指令n等价代码段：boolean testset(int i)if(i=0)i=l;return true;elsereturn false;37计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月TestSet指令 解决方案/*program mutualexclusion*/const int n=/*number of processes*/;int bolt;void p(int i)while(true)while(!testset(bolt)/*do nothing*/;/*critical section*/bolt=0;/*remainder*/void main()bolt=0;parbegin(p(1),p(2),p(n);n 第二种尝试的专用指令版n 只有测试bolt=0的进程才能进入临界区(bolt=门闩/锁条)38计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月exchange指令n定义（逻辑）交换一个寄存器和内存单元的内容n原子操作nx86 CPU的对应指令为XCHGn等价代码段：void exchange(int register,int memory)int temp;temp=memory;memory=register;register=temp;39计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月exchange指令解决方案/*program mutualexclusion*/const int n=/*number of processes*/int bolt;void p(int i)int keyi=1;while(true)do exchange(keyi,bolt);while(keyi!=0);/*critical section*/bolt=0;/*remainder*/void main()bolt=0;parbegin(p(1),p(2),p(n);n 只有发现bolt=0的进程才能进入临界区n 算法的本质：bolt+keyi=nn bolt=0：临界区无进程n bolt=1：只有keyi=0的进程在临界区40计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月机器指令方法的优缺点n优点优点n适用于单处理器或共享主存多核处理器系统，进程数目任意n简单且易于证明n可以使用多个变量支持多个临界区n缺点缺点n忙等待（busy waiting）/自旋等待（spin waiting）n可能饥饿n可能死锁41计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月下篇n信号量（semaphore）n管程（monitor）n消息传递n读者-写者问题42计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月常用并发机制并发机制并发机制说明说明信号量信号量用于进程间传递信号的一个整数值，只有初始化、增、减三种原子操作，可阻塞/解除阻塞进程二元信号量 取值只为0和1的信号量互斥量似二元信号量，但要求为其加锁和解锁的须是同一进程条件变量一种数据类型，用于阻塞进程/线程，直到特定条件为真管程管程一种编程语言结构，封装了代表临界区的若干过程事件标志用于同步机制的内存字，其每个位关联不同的事件信箱信箱/消息消息进程间交换信息的一种方法，也可用于同步自旋锁一种互斥机制，进程在一无条件循环中执行，等待锁变量值变为可用43计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月445.3 信号量(semaphore)nsemaphoresemf:(r)信号灯/机/量、旗语、（铁道）臂板信号装置 n信号量机制n由（1972年的图灵奖获得者，实现了ALGOL60的编译器、提出了图论中最短路径的Dijkstra算法的）荷兰计算机科学家E.W.Dijkstra提出(1965)，是解决并发进程问题的第一个重要进展，需要OS支持n两个或多个进程可以通过传递信号信号进行合作，从而可以迫使进程在某指定位置停住，直到它收到特定信号n信号量机制可以满足任何复杂的合作要求n信号量的（整数）值在并发中常用来表示可用资源的数目n信号量机制的组成信号量机制的组成n由OS提供的用于进程并发控制的一种特殊数据结构n含有一个整数变量和三个专门操作：初始化、P（荷兰语proberen，测试/通过）操作和V（荷兰语verhogen，增量/释放）操作Edsger Wybe Dijkstra(1930-2002)计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月45对信号量的操作n初始化n通常将信号量的值初始化为非负整数（=可用资源数）nP操作/semWait操作/Down操作n信号量的值减1n若信号量的值变成负数，则执行P操作的进程被阻塞nV操作/semSignal操作/Up操作n信号量的值加1n如果信号量的值不是正数（其绝对值=现被阻塞的进程数等待队列的长度），则使一个因执行P操作被阻塞的进程解除阻塞（唤醒）n此外，没有其他检查和修改信号量值的操作计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月46信号量和P、V操作原语的描述struct semaphore/定义结构 int count;queueType*queue;s;void P(semaphore s)/P操作 s.count-;if(s.count0)Block(CurruntProcess,s.queue);void V(semaphore s)/V操作 s.count+;if(s.count=0)WakeUp(s.queue);/初始化s.count=nr;s.queue=malloac(m*sizeof(queueType);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月47信号量和wait、signal原语的描述(P&V)struct semaphore int count;queueType queue;void semWait(semaphore s)s.count-;if(s.count 0)/*place this process in s.queue*/*block this process*/void semSignal(semaphore s)s.count+;if(s.count=0)/*remove a process P from s.queue*/*place process P on ready list*/计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月48二元信号量n信号量的取值只能是0或1n和一般信号量具有相同的表达能力n因count不能=0n进程执行P(s)/semWait(s)操作n申请一个单位的资源(s.count-)n当s.count 0时，资源已分配完毕，进程自己阻塞在s的队列上-让权等待n进程执行V(s)/semSignal(s)操作n释放一个单位资源(s.count+)n若s.count=0：可用的资源数/可以执行P(s)而不会阻塞的进程数n0：|s.count|为在队列中等待的进程数计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月52信号量的实现n基本要求n保证 P/semWait 和 V/semSignal操作的原子性，以保证信号量操作的互斥n软件方案nDekker算法nPeterson算法n硬件支持方案n可以采用TS指令n关中断计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月53信号量的TestSet指令实现方案struct semaphore int flag;int count;queueType*queue;s;void semWaitT(semaphore s)while(!testset(s.flag);s.count-;if(s.count0)Block(CurruntProcess,s.queue);s.flag=0;void semSignalT(semaphore s)while(!testset(s.flag);s.count+;if(s.count=0)WakeUp(s.queue);s.flag=0;临界区计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月54信号量的关中断实现方案struct semaphore int count;queueType*queue;s;void semWaitI(semaphore s)inhibit interrupts;s.count-;if(s.count0)Block(CurruntProcess,s.queue);allow interrupts;void semSignalI(semaphore s)inhibit interrupts;s.count+;if(s.count=0，则进程进入临界区n若s0，则进程被阻塞不能进入临界区，加入等待队列n进程离开临界区时执行V操作ns+n若s=0，则唤醒一个被阻塞的进程，将其移出等待队列，置为就绪状态，使其在下次操作系统调度时可进入临界区n这样可以保证最多只有一个进程在临界区，从而实现了共享资源的互斥访问57计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月58用信号量实现互斥（续）n一种可能的执行情况计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月用信号量实现进程同步n进程的同步（synchronization）n指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于阻塞状态，获得消息后被唤醒进入就绪态。司机(P1)售票员(P2)REPEAT REPEAT 启动 关门 正常行驶 售票 到站停车 开门UNTIL FALSE UNTIL FALSE 59计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月60用信号量实现进程同步-举例n例:有三个进程并发运行，合作完成输入数据、计算和打印输出工作n进程PI将输入的数据写入缓冲区B1,n进程PC读出B1中的数据，完成计算，把结果写入缓冲区B2n进程PP读出B2中的结果，打印输出n同步要求:（读出数据后缓冲区为空）n(1)先写后读（不能读空缓冲区）n(2)未读完不能写（不能写非空缓冲区）计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月61用信号量实现进程同步（续）n设置四个信号量：empty1、full1、empty2、full2n初始分别为：1、0、1、0（即两个缓冲区都为空）n三个进程的描述P PI:I:while(1)while(1)P(empty1);P(empty1);输输 入入 数数 据据 写写 到到B1;B1;V(full1);V(full1);P PP P:while(1)while(1)P(full2);P(full2);读读取取B2B2中中的的结结果果并输出到打印机并输出到打印机;V(empty2);V(empty2);P PC:C:while(1)while(1)P(full1);P(full1);从从B1B1中读取数据中读取数据;V(empty1);V(empty1);计算计算;P(empty2);P(empty2);结果写到结果写到B2;B2;V(full2);V(full2);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月625.3.2 生产者/消费者问题n并发处理的最常见问题类型n问题描述n若干进程通过无限/有限的共享缓冲区交换数据n一组“生产者”进程不断写入n另一组“消费者”进程不断读出n共享缓冲区无限/共有N个n任何时刻只能有一个进程可对共享缓冲区进行操作计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月63无限缓冲区的(二元信号量)解决方案int n;/*缓冲区中产品数*/Binary_semaphore s=1;/*互斥*/Binary_semaphore delay=0;/*等待*/void producer()while(true)produce();semWaitB(s);append();n+;if(n=1)semSignalB(delay);semSignalB(s);void consumer()semWaitB(delay);while(true)semWaitB(s);take();n-;semSignalB(s);consume();if(n=0)semWaitB(delay);少执行一次 void main()n=0;parbegin(producer,consumer);n存在漏洞：超前消费切换切换计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月64基于二元信号量的正确解决方案int n;Binary_semaphore s=1;Binary_semaphore delay=0;void producer()while(true)produce();semWaitB(s);append();n+;if(n=1)semSignalB(delay);semSignalB(s);void consumer()int m;semWaitB(delay);while(true)semWaitB(s);take();n-;m=n;semSignalB(s);consume();if(m=0)semWaitB(delay);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月65基于计数信号量的正确解决方案semaphore n=0;/*缓冲区中的产品数*/semaphore s=1;/*互斥*/void producer()while(true)produce();semWait(s);append();semSignal(s);semSignal(n);void consumer()while(true)semWait(n);semWait(s);take();semSignal(s);consume();void main()parbegin(producer,consumer);颠倒顺序后颠倒顺序后会产生死锁会产生死锁计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月有限缓冲区的生产者/消费者问题对象对象被阻塞事件被阻塞事件解除阻塞事件解除阻塞事件生产者插入满缓冲区消费者移出一项消费者从空缓冲区移出 生产者插入一项66计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月67有限循环缓冲区的解决方案const int sizebuffer=Nsemaphore n=0;/*产品数*/semaphore s=1;/*互斥*/semaphore e=N;/*空闲数*/void producer()while(true)produce();semWait(e);semWait(s);append();semSignal(s);semSignal(n);void consumer()while(true)semWait(n);semWait(s);take();semSignal(s);semSignal(e);consume();void main()parbegin(producer,consumer);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月68理发店问题n用信号量或管程实现并发的经典例子（参见P511的附录A.3）n问题描述：3个理发师、3张理发椅、一张沙发4个位、一个收银机、室内最多容纳20个顾客、共有50个顾客，有位则坐，无位则站计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月69n动机n同步机制与同步策略的分离是灵活的，同时也是危险的n集中管理（封装）以策安全n管程(monitor)是一种封装同步机制与同步策略的程序设计语言结构程序设计语言结构nAda 95、并发Pascal、Modula-3、Java、C#、Delphi、Python、Ruby、Mesa等n1972年由英国计算机科学家C.A.R.Hoare和美籍丹麦计算机科学家P.B.Hansen发明5.4 管程计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月70n1974年Hoare提出的管程方案n1975年Hansen在并发Pascal上实现 n主要特点：n本地变量只能由管程过程访问（封装）n进程通过调用管程过程进入管程（调用）n每次只能一个进程在执行相关管程的过程（互斥）n主要缺陷n可能增加了两次多余的进程切换n对进程调度有特殊要求（不允许插队）5.4.1 使用信号的管程计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月管程的结构和应用n管程软件模块的组成n若干过程n一个初始化序列n局部数据n条件变量n管程提供的互斥机制n管程中的数据每次只能被一个进程访问n可将共享数据结构放入管程以得到保护n可用这些数据代表临界资源n管程对同步的支持n通过cwait(c)、csignal(c)操作管程中的条件变量实现同步71计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月72有限缓冲区生产者/消费者的管程解决方案Amonitor boundedbuffer /*管程体*/char bufferN;int nextin,nextout;/*局部数据*/int count;/*产品数*/cond notfull,notempty;/*条件变量*/void append(char x)/*添加过程*/if(count=N)cwait(notfull);buffernextin=x;nextin=(nextin+1)%N;count+;csignal(notempty);void take(char x)/*取出过程*/if(count=0)cwait(notempty);x=buffernextout;nextout=(nextout+1)%N;count-;csignal(notfull);nextin=0;nextout=0;count=0;/*初始化*/void producer()char x;/*产品=字符*/while(true)produce(x);append(x);void comsumer()管程过程调用 char x;while(true)take(x);comsume(x);void main()parbegin(producer,consumer);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月使用信号的管程存在的问题n定义要求在条件队列中至少有一个进程?n当另一进程为该条件产生csignal信号时，则产生此信号的进程必须立即退出管程（或阻塞在管程上），以便让队列中被唤醒的进程能够立即进入管程运行n如果产生csignal信号的进程在管程内的运行还未结束，则需要两次额外的进程切换（阻塞以让被唤醒的进程运行，等其运行结束后再恢复运行）n进程调度程序必须保证在激活被唤醒的进程前没有其他进程进入管程，否则可能造成永久阻塞n解决办法：采用使用通知和广播的管程计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月74n1980年2月美国计算机科学家B.W.Lampson和D.D.Redell为Mesa语言开发的一种管程方案（也可用于Modula-3）n主要特点：n用cnotify原语代替原来的csignal操作（发通知的进程不需立即退出管程，接到通知的进程也不立即被唤醒，只是转为就绪，等待合适的时候再进入管程运行）n用while循环代替if判断（有额外的条件变量检查，但可避免额外的两次进程切换）n等待条件增加计时器，等待超时的进程将被转为就绪n cnotify原语n通知特定等待条件队列中的第一个等待进程，但当前执行cnotify原语的进程继续执行n被通知的等待进程转为就绪，但必须重新检查条件。ncbroadcast原语n通知特定等待条件队列中的所有等待进程，但当前执行cnotify原语的进程继续执行5.4.2 使用通知和广播的管程计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月75有限缓冲区生产者/消费者的管程解决方案Bmonitor boundedbuffer char bufferN;int nextin,nextout;int count;cond notfull,notempty;void append(char x)while(count=N)cwait(notfull);buffernextin=x;nextin=(nextin+1)%N;count+;cnotify(notempty);void take(char x)while(count=0)cwait(notempty);x=buffernextout;nextout=(nextout+1)%N;count-;cnotify(notfull);nextin=0;nextout=0;count=0;void producer()char x;while(true)produce(x);append(x);void comsumer()char x;while(true)take(x);comsume(x);void main()parbegin(producer,consumer);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月765.5 消息传递n进程交互的两个基本要求进程交互的两个基本要求n同步：互斥进程间需同步。同步指对进程执行时序的约束，包括互斥和时序的先后限制n通信：合作进程间交换信息n消息传递消息传递n进程通信的一种常用方法进程通信的一种常用方法n适用范围广，可用于多核、SMP和分布式系统n由原语对“send（发送）和receive（接收）”提供主要功能：nsend(目的,信息)nreceive(源,信息)n实现形式有多种计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月775.5.1 消息传递的同步n消息传递自然地隐含了同步n只有当一个进程发送消息之后，接收者才能收到消息n调用send原语的两种可能结果n发送者进程被阻塞，直到这个消息被接收n发送者进程不被阻塞n调用receive原语的两种可能结果n接收者进程接收消息时，消息已已发出，接收者不阻塞n接收者进程接收消息时，消息未未发出，接收者被阻塞，直到发送者进程发出此消息计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月78三种三种组合方式合方式n消息传递实现的三种常用组合方式消息传递实现的三种常用组合方式n“阻塞send，阻塞receive”方式，即“会合”原则，适用于进程间的紧密同步（如打电话）n“无阻塞send，阻塞receive”方式，最有用的组合（如收发短信）n“无阻塞send，无阻塞receive”方式，不要求任何一方等待。危险：信息可能会丢失（如贴/看小广告）n“无阻塞send”是最自然的选择。但错误可能会导致进程重复传递消息，消耗系统资源。且必须使用应答消息以证实收到消息n“阻塞receive”是常用的选择。但若消息丢失或发送者进程失效，会导致接收者进程被长期阻塞计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月795.5.2 消息传递的寻址nsend原语中指明接收者是必要的nreceive原语有时也指明发送者n直接寻址方案n发送者在发送时给出了接收者进程的具体标识号，如进程IDn间接寻址方案n发送者将消息发送到共享的信箱中临时保管，接收者从信箱中获得这些消息n耦合方式：“一对一”、“多对一”、“一对多”或“多对多”n进程与信箱的关联：静态方式（端口）和动态方式（使用连接原语connect和disconnect）计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月805.5.3 消息格式n取决于运行环境n单机系统n分布式系统n两类格式n定长格式n变长格式n消息格式n消息头消息类型、目标ID、源ID、消息长度、控制信息n消息体消息内容消息类型消息内容目标ID源ID消息长度控制信息消息头消息体5.5.4 排队原则n先进先出（FIFO）原则n优先级原则计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月81用于进程间通信和同步的消息系统设计n同步nsend阻塞、无阻塞nreceive阻塞、无阻塞、测试是否到达n寻址n直接nsendnreseive显式、隐式n间接n静态n动态n所有权n格式n内容n长度固定、可变n排队规则nFIFOn优先级计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月825.5.5 消息传递实现互斥n使 用“无 阻 塞 send，阻 塞receive”组合n一组进程共享一个信箱box，信箱被初始化为一条无内容的空消息（代表进入临界区的钥匙）n每个进程在进入临界区前，首先尝试接收消息，离开临界区时将接收到的消息放回信箱n每次只有接收到消息的那个进程才可以进入临界区（互斥）n消息函数似在进程间传递一个可使用临界区的令牌/*program mutualexclusion*/const int n=/*进程数*/;void P(int i)/*进程i*/message msg;while(true)receive(box,msg);/*信箱空时被阻塞*/*临界区*/;send(box,msg);/*其余部分*/;void main()create_mailbox(box);send(box,null);parbegin(P(1),P(n);计算机科学系计算机科学系 操作系统课程组操作系统课程组 李才伟李才伟&凌应标制作凌应标制作 2016年年4月月83 消息传递实现生产者-消费者问题/*互斥程序*/const int capacity=N;/*缓冲区容量*/;message null=/*空消息*/;void producer()message pmsg;while(true)receive(mayproduce,pmsg);pmsg=produce();send(maycomsume,pmsg);void comsumer()message cmsg;while(true)receive(mayconsume,cmsg);consume(cmsg);send(mayproduce,null);void main()create_mailbox(mayproduce);create_mailbox(mayconsume);for(int i=1;i最大可能的读进程数）n每接收一条读请求消息时count-n每接收一条写请求消息时count-100n每接收一条读完成消息时count+n控制进程的处理方案：ncount0（count没有-100）：表示还没有接收写者进程的写请求（从而无写者进程在数据区），可能有读者进程正在读，也可能有读者和写者进程已经发出请求正在等待应答。此时，控制进程先处理读者进程的完成消息；若无读完成消息，则优先处理写请求消息（接收写请求，count-=100）；只有在既无读完成消息，也无写请求消息时，最后才处理读请求消息（发送应答消息“OK”，允许读者进程进入数据区）void controller()/count用于互斥 int count=100;/最大可能的读进程数 message msg;while(true)if(count0)/无写进程进入数据区 if(!empty(finished)/可能正在读 receive(finished,msg);count+;else if(!empty(writerequest)/优先写 receive(writerequest,msg);write_id=msg.id;count=count-100;else if(!empty(readreques