04第四章互斥同步与通讯11

第四章第四章 互斥、同步与通讯互斥、同步与通讯n并发进程并发进程(concurrent processes)n进程互斥进程互斥(mutual exclusion)n进程同步进程同步(synchronization)n进程高级通讯进程高级通讯(communication)4.1并发进程并发进程n4.1.1前驱图的定义前驱图的定义 前驱图(precedence graph)是一个有向无环图，图中的每个结点表示一条语句、一个计算步骤或一个进程。结点间的有向边表示偏序或前驱关系（precedence relation）“”，=（pi，pj） pi必须在pj启动之前完成。 （pi，pj） 可记为pi pj，称pi是pj的前驱， pj是pi的后继。4.1并发进程并发进程n在前驱图中没有前驱的结点称为初始结点，没有后继的结点称为终止结点。每个结点可以有一个权重（weight），它表示该结点所包含的程序量或计算时间。n前驱关系满足传递性，即若p1 p2，p2 p3，则必有p1 p3。4.1 并发进程并发进程n4.1.2 顺序程序及其特性顺序程序及其特性n顺序性顺序性n内部顺序性：对于一个进程来说，它的所有指令是按顺序执行的。内部顺序性：对于一个进程来说，它的所有指令是按顺序执行的。P1: a1,a2,a3; P2: b1,b2,b3n外部顺序性：对于多个进程来说，所有进程的活动是依次执行的。外部顺序性：对于多个进程来说，所有进程的活动是依次执行的。a1,a2,a3,b1,b2,b3; b1,b2,b3,a1,a2,a3n顺序程序特性顺序程序特性:n (1)顺序性顺序性: 指令逐条执行指令逐条执行n (2)封闭性封闭性: 不受其它程序及外界因素影响不受其它程序及外界因素影响n (3)可再现性可再现性: 结果与推进速度无关结果与推进速度无关4.1 并发进程并发进程n4.1.3 并发程序及其特性并发程序及其特性n并发性并发性n内部并发性：指程序内部的并发性。例如：内部并发性：指程序内部的并发性。例如：S1：a:=x+2;S2: b:=y+4;S3: c:=a+b;S4: d:=c-6;S5: e:=c+6;S6: f:=c-e;经分析知道经分析知道S3必须在必须在S1和和S2之后执行，之后执行，S4和和S5必须在必须在S3之后执行，之后执行，S6必须在必须在S3和和S5之后执行；而之后执行；而S1和和S2可以并发执行，可以并发执行，S4和和S5可以并发可以并发执行，执行，S4和和S6可以并发执行。可以并发执行。4.1并发进程并发进程n外部并发性：外部并发性是指多个程序的并发性。例如外部并发性：外部并发性是指多个程序的并发性。例如P1: a1,a2,a3; P2: b1,b2,b3 执行次序可以是如下情况：执行次序可以是如下情况：a1,b1,b2,a2,a3,b3; b1,b2,a1,b3,a2,a3n并发程序特性并发程序特性:n(1)间断性间断性:多个程序是交叉执行的，处理器在执行一个程序的过程中有多个程序是交叉执行的，处理器在执行一个程序的过程中有可能被中断，并转而执行另一个程序，有些交叉可能导致错误结果可能被中断，并转而执行另一个程序，有些交叉可能导致错误结果n(2)非封闭性非封闭性:一个进程的运行环境受其他程序影响一个进程的运行环境受其他程序影响n(3)不可再现性不可再现性:由于交叉的随机性，并发程序的多次执行可能对应不同由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，从而使得两次运行结果可能不同即不能期望从新运行的程序能的交叉，从而使得两次运行结果可能不同即不能期望从新运行的程序能够再现上次运行时产生的结果。够再现上次运行时产生的结果。4.1并发进程并发进程n4.1.4程序并发执行的条件程序并发执行的条件 并发是人们所期望的，但并发带来一个明显的问题就是程序执行的非封闭性，而人们却要求在非封闭性的条件下保持可再现性，因为只有可再现的结果才是正确的。令：令： R(pi)=a1,a2,am表示程序pi在执行期间所读取的所有变量的集合，称为“读集”。 W(pi)=b1,b2,bn表示程序pi在执行期间所修改的所有变量的集合，称为“写集”。Bernstein条件（1966年由Bernstein提出）： 若两个程序p1、p2满足以下条件，则能够保持可再现性，可以并发执行，条件是： R(p1) W(p2) R(p2) W(p1) W(p1) W(p2) = 4.1并发进程并发进程n并发程序的表示 并发程序常用并发语cobegin(concurrent begin)coend(concurrent end)来表示，令S1、S2、Sn为n条语句，它们可以并发执行，则用并发语句表示为： cobegin S1；S2； Sn coend； 有时也用并行语parallelbegin(parallel begin)parallelend(parallel end)来表示 当遇到并发或并行语句时，同时n创建个进程（线程），分别执行S1、S2、Sn 。当它们都结束时，并发和并行语句结束。4.1.6 与时间有关的错误与时间有关的错误例：图书借阅系统例：图书借阅系统 （x: :某种书册数，设当前某种书册数，设当前x=1.=1.）终端终端1： 终端终端2：do do 等待借书者；等待借书者； 等待借书者；等待借书者； if x=1 if x=1 _ _ x:=x-1; x:=x-1; _ _ 借书借书 借书借书 else 无书无书 else 无书无书 while(1) while(1) (a)CR1 (b)CR2 12344.1.6 与时间有关的错误与时间有关的错误(Cont.)错误原因之错误原因之1： 进程执行交叉进程执行交叉(interleave);错误原因之错误原因之2： 涉及公共变量涉及公共变量(x)。Remarks: 某些交叉结果不正确某些交叉结果不正确; 必须去掉导致不正确结果的交叉。必须去掉导致不正确结果的交叉。4.2 进程互斥进程互斥(mutual exclusion)n4.2.1 共享变量与临界区共享变量与临界区n4.2.2 临界区域与进程互斥临界区域与进程互斥n4.2.3 进程互斥的实现进程互斥的实现n4.2.4 多处理机环境下的互斥多处理机环境下的互斥4.2.1 共享变量与临界区域共享变量与临界区域n共享变量共享变量（shared variable）或公共变量n多个进程都需要访问的变量。多个进程都需要访问的变量。n临界区域临界区域（critical region）或临界段(critical section)n访问共享变量的程序段访问共享变量的程序段。 一组公共变量一组公共变量CR1CR2CRn.4.2.1 共享变量与临界区域共享变量与临界区域n临界区是于1965年首先提出的。在上例中的CR1和CR2。临界区可能有多个。为了清晰起见，通常把临界区与所对应的共享变量联系起来，称为关于某一组共享变量的临界区。如上例CR1和CR2是关于共享变量x的临界区。n关于同一组共享变量的临界区可能有一个也可能有多个，它们的关系可以用上图表示。n共享变量既可能属于操作系统空间，也可能属于用户空间。对于前者，其临界区也属于操作系统空间；同样后者对应的临界区也属于用户空间。共享变量和临界区的表示共享变量和临界区的表示共享变量共享变量: shared 临界区域临界区域: region do 语句语句临界资源：一次只允许一个进程使用的资源临界资源：一次只允许一个进程使用的资源例子：例子：shared x1,x2; region x1,x2 do region x1,x2 do (访问访问B） （访问（访问B） 4.2.2 临界区域与进程互斥临界区域与进程互斥定义定义：多个进程不能同时进入关于同一组共享变量的临多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥为进程互斥二层涵义：二层涵义： （1）任何时刻最多只能有一个进程处于同一组共）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域；享变量的相同的临界区域； （2）任何时刻最多只能有一个进程处于同一组共）任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域享变量的不同的临界区域。Remarks: 互斥是相对于公共变量而言的。互斥是相对于公共变量而言的。嵌套临界区域嵌套临界区域 shared x; shared y; region x do region y do _ _ region y do region x do . . 一个临界区程序段可能调用另一个临界区程序段，称发生了临界区的嵌套。一个临界区程序段可能调用另一个临界区程序段，称发生了临界区的嵌套。4.2.3 进程互斥的实现进程互斥的实现nframeworkdo critical section remainder section while(1)entry sectionexit section4.2.3 进程互斥的实现进程互斥的实现nRequirements:nmutual exclusion: 一次只允许一个进程活动在关一次只允许一个进程活动在关于同一组公共变量的临界区中于同一组公共变量的临界区中；nprogress: 临界区空闲时，多个竞争者在有限时间临界区空闲时，多个竞争者在有限时间内确定下一个进入者内确定下一个进入者；nbounded waiting: 一个想要进入临界区的进程在等一个想要进入临界区的进程在等待有限个进程进入并离开临界区后获得进入临界区待有限个进程进入并离开临界区后获得进入临界区的机会的机会。4.2.3 进程互斥的实现进程互斥的实现n调度原则： 1.关于同一组共享变量的所有临界区均为空闲时，一个要求进入改组共享变量某一临界区的进程应当能够立即进入。 2.当关于某一组共享变量的某一临界区被占用时，一个要求进入改组共享变量某一临界区的进程应当等待。 3.当某一进程离开关于某一组共享变量的某一临界区时，应当允许某一个等待进入该组共享变量某一临界区的进程进入。4.2.3.1 进程互斥的软件实现进程互斥的软件实现n完全用程序实现，不需特殊硬件指令支完全用程序实现，不需特殊硬件指令支持。持。n可用于单可用于单CPU和多和多CPU环境中。环境中。n有忙式等待问题。有忙式等待问题。Busy waiting“运行运行”或或“就绪就绪”Dekker互斥算法n是由荷兰数学家T.Dekker给出的第一个正确实现互斥的软件算法，算法针对两个进程P0和P1定义的两个数据结构： int flag2;/初值为0 int turn;/初值为0或1算法：Dekker互斥算法nP0: do flag0=1; while flag1 do if (turn=1) flag0=0; while turn=1 do skip; flag0=1;Dekker互斥算法 临界区 turn=1; flag0=0; 其余代码 while(1)Dekker互斥算法nP1: do flag1=1; while flag0 do if (turn=0) flag1=0; while turn=0 do skip; flag1=1;Dekker互斥算法 临界区 turn=0; flag1=0; 其余代码 while(1)Lamport面包店算法面包店算法算法思想算法思想：算法的基本思想源于顾客在面包店中购买面包：算法的基本思想源于顾客在面包店中购买面包时的排队原理。设置一个发号者，按时的排队原理。设置一个发号者，按0,1,2, 发号。想进发号。想进入临界区（面包店）的进程先抓号，抓到号之后按由小到入临界区（面包店）的进程先抓号，抓到号之后按由小到大的次序依次进入大的次序依次进入。Problem: 两个进程可能抓到相同的号。两个进程可能抓到相同的号。Why? 为保证抓到不同的号，需要互斥机制。为保证抓到不同的号，需要互斥机制。Resolution: 若抓到相同的号，按进程编号由小到大依次若抓到相同的号，按进程编号由小到大依次进入。进入。Definition: (a,b)(c,d) iff (ac)or(a=c and bd)Lamport面包店算法面包店算法n算法需要以下两个数据结构 int choosingn; int numbern; 前者表示进程是否正在抓号choosingi=1表示进程正在抓号，否则为0，其初值为0.后者用来表示进程抓到号码，初值也为0.n算法描述方便需要定义以下表示方法 (a,b)(c,d),如果 ac or(a=c and bd)成立。Lamport面包店算法面包店算法doPi 进入进入：1. choosingi=1;2. numberi=maxnumber0,numbern-1+1;3. choosingi=0;4. for(j=0;jn; j+)5. While choosingj skip;6. While (numberj0)&7. (numberj,j)(numberi,i) skip8. (1)P0抓到1未赋值(2)P1抓到1进入临界区(3)P2抓到2进入临界区 Lamport面包店算法面包店算法(Cont.) 临界区；临界区； numberi=0；while(1);变量变量choosing的作用：的作用：P0：抓到：抓到1; P1：抓到：抓到1; 正确次序：正确次序：P0，P1，P2P2：抓到：抓到2; 可能按可能按P1,P2,P0次序进入次序进入！满足临界区管理原则满足临界区管理原则n互斥性互斥性(mutual exclusion)n如果进程如果进程pi在临界区内在临界区内,且进程且进程pk(ki)已抓到号已抓到号numberk0, 则有则有(numberi,i)(numberk,k). 进进程程Pk将在第二个将在第二个while循环处等待循环处等待, 直到直到pi离开该临界区离开该临界区.n有限等待性有限等待性(bounded waiting)n竞争进程按竞争进程按FIFO的次序进入临界区的次序进入临界区, 而进程个数是有限的而进程个数是有限的, 因因而进程不会无限期等待进入临界区而进程不会无限期等待进入临界区.n进展性进展性(progress)n多个进程竞争进入临界区时多个进程竞争进入临界区时, 下述条件之一成立下述条件之一成立: (1)一个进程一个进程抓到最小号抓到最小号, (2)若干进程抓到最小号若干进程抓到最小号. 情形情形(1)抓到最小号的抓到最小号的进程获准进入临界区进程获准进入临界区; 情形情形(2)编号最小抓到最小号的进程获编号最小抓到最小号的进程获准进入临界区准进入临界区, 因而确定进入临界区进程的决策将在有限时间因而确定进入临界区进程的决策将在有限时间内确定内确定.Eisenberg/Mcguire算法算法enum flagn (idle, want_in, in_cs);初值初值idle int turn;/in the range of (0,n-1); 初始任意初始任意0 i turnn-1先于先于i先于先于iflagi=idle: 进程进程Pi不想进入临界区不想进入临界区flagi=want_in: 进程进程Pi想进入临界区想进入临界区flagi=in_cs: 进程进程Pi想进入或已进入临界区想进入或已进入临界区Eisenberg/Mcguire算法算法Pi进入进入:do do flagi=want_in; j=turn; While (j!=i) if (flagj!=idle) j=turn; else j=(j+1)% n; flagi=in_cs; j=0; While (jn)&(j=i flagj!=in_cs) j+; while(j!=n); turn=i;Eisenberg/Mcguire算法算法Pi离开：离开：j=(turn+1)% n;While (flagj=idle) j=(j+1)% n;turn=j;flagi=idle;while(1)CS满足临界区管理原则满足临界区管理原则n互斥性互斥性n仅当对所有仅当对所有ji, flagj in_cs时时, 进程进程Pi才进入临界区域才进入临界区域, 因而满足互斥性因而满足互斥性.n进展性进展性n如果没有进程正处于临界区或离开临界区如果没有进程正处于临界区或离开临界区, turn值不变值不变, 竞争竞争进程将按进程将按turn, turn+1, , n-1, 1, turn-1的次序进入临界的次序进入临界区区, 因而满足进展性原则因而满足进展性原则.n有限等待性有限等待性n进程离开临界区时进程离开临界区时,按循环次序确定唯一一个竞争进程为其后按循环次序确定唯一一个竞争进程为其后继继, 所以一个进程最多等待所以一个进程最多等待n-1个进程进入并离开临界区后一个进程进入并离开临界区后一定能进入临界区定能进入临界区, 因而满足有限等待性因而满足有限等待性.4.2.3.2 进程互斥的硬件实现进程互斥的硬件实现1. 硬件提供硬件提供“测试并建立测试并建立”指令指令 int test_and_set(int &target) int temp; temp=target; &target=1; return(temp) 对一组公共变量，对一组公共变量，int lock（初始（初始=0); Pi进入：进入：While test_and_set(lock) skip; Pi离开：离开：lock=0;4.2.3.2 进程互斥的硬件实现进程互斥的硬件实现n基于“测试并设置”指令的公平性硬件互斥算法 定义全局变量为： int waitingn; int lock; 其中变量的初值都为0. 每个进程定义的局部变量为： int j; int key;4.2.3.2 进程互斥的硬件实现进程互斥的硬件实现do waitingi=1; key=1; while ( waitingi & key) key=test_and_set(&lock); waitingi=0; CR j=(i+1)% n; while (j!=i) & (! waitingj) j=(j+1)% n; if (j=i) lock=0; else waitingj=0; REMAIN while (1)4.2.3.2 进程互斥的硬件实现进程互斥的硬件实现2. 硬件提供硬件提供“交换交换”指令指令 void swap(int &a,&b) int temp; temp=*a; *a=b; *b=temp ; 对一组公共变量对一组公共变量：int lock (初始初始=0); 对一个进程空间对一个进程空间：int key; Pi进入进入：key=1; do swap(&lock,&key)while (key=1); Pi离开离开：lock=0;4.2.3.2进程互斥的硬件实现进程互斥的硬件实现Remarks：(1) test_and_set指令和指令和swap指令是原子的，指令是原子的，不可中断的不可中断的(在单在单CPU情况下情况下)。(2) test_and_set实际上是：将内存中一个单实际上是：将内存中一个单元的内容取出，再送一个新值。元的内容取出，再送一个新值。(3) swap实际上是：交换内存两个单元的内容实际上是：交换内存两个单元的内容。4.2.3.2进程互斥的硬件实现进程互斥的硬件实现n基于“交换”指令的公平性硬件互斥算法 定义全局变量为： int waitingn; int lock; 其中变量的初值都为0. 每个进程定义的局部变量为： int j; int key;4.2.3.2进程互斥的硬件实现进程互斥的硬件实现do waitingi=1; key=1; while ( waitingi & key) key=swap(&lock, &key); waitingi=0; CR j=(i+1)% n; while (j!=i) & (! waitingj) j=(j+1)% n; if (j=i) lock=0; else waitingj=0; REMAIN while (1)4.2.3.2进程互斥的硬件实现进程互斥的硬件实现3. 硬件提供硬件提供“关中断关中断”和和“开中断开中断”指指令令 关中断关中断 Critical Region 开中断开中断Remarks: (1) 开关中断只在单开关中断只在单CPU系统中有效系统中有效;(why?) (2) 影响并发性。影响并发性。Assignment #11. 进程切换时需要保存哪些现场信息？请尽量考虑完全。2. 进程切换时，现场信息为何不能保存在下降进程的系统栈中,而必须传送到PCB中？Assignment #2Consider the following program:var blocked: array0.1of boolean; turn:0.1;procedure P(id:integer);begin repeat blockedid:=true; while turnid do begin while blocked1-id do nothing turn:=id end; blockedid:=false; until falseend;begin blocked0:=false; blocked1:=false; turn:=0; parbegin P(0); P(1) parend;end.This is a software solution to the mutual exclusion problem proposed by Hyman. Find a counter example to demonstrate that this solution is incorrect. It is interesting to note that even the Communication of the ACM was fooled on this one.4.3 进程同步进程同步4.3.1 进程同步的概念进程同步的概念例：司机例：司机-售票员问题售票员问题 司机活动：司机活动： 售票员活动：售票员活动： do do 启动车辆启动车辆 关车门关车门 正常行驶正常行驶 售售 票票 到站停车到站停车 开车门开车门 while( (1) ) while( (1) )4.3.1 进程同步的概念进程同步的概念定义：定义：一组进程，为协调其推进速度，在某些关一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步相互制约的关系称为进程同步(synchronization)。P1:P2:synchronize后先4.3.2 进程同步机制进程同步机制n定义：定义：用于实现进程同步的工具称为同用于实现进程同步的工具称为同步机制步机制（synchronization mechanism）又称同步设施。n同步机制要求：同步机制要求：n描述能力够用描述能力够用;n可实现可实现;n高效高效;n使用方便使用方便.典型同步机制典型同步机制 n信号灯与信号灯与PV操作操作( (semaphore and PV operations) )n管程管程( (monitor) )n会合会合( (rendezvous) )n条件临界区条件临界区( (conditional critical region) )n路径表达式路径表达式( (path expression) )n事件事件( (traditional UNIX) )4.3.3 信号量与信号量与PV操作操作E.W.Dijkstra, 1965.4.3.3.1 信号量信号量0与与PV操作的定义操作的定义 struct semaphore int value; point_to_PCB queue; ; semaphore s;Remarks:(1) semaphore is pre-defined data type,(2) s can be declared as needed, eg. var s1,s2:semaphore; 信号量信号量S-valueS-queueS-valueS-queuePCBPCBPCBSemaphore s;FIFOP操作原语操作原语P操作原语操作原语：void P(semaphore *s) s-value-; if (s-valuequeue) asleep(s-queue)是标准函数:(1) 执行此操作进程的执行此操作进程的PCB入入s-queue尾（状态改为等尾（状态改为等待）；待）；(2) 转处理机调度程序。转处理机调度程序。 Primitive: a piece of code un-interruptibleV操作原语操作原语V操作原语：操作原语：void V(semaphore *s) s-value+; if (s-valuequeue); wakeup(s-queue)是标准函数：是标准函数：（1）执行次操作系统将队列）执行次操作系统将队列s-queue头部的进程的头部的进程的PCB移出等待队列，并将其插入就绪队列。移出等待队列，并将其插入就绪队列。（2）将移出进程的状态改为就绪。）将移出进程的状态改为就绪。 Primitive: a piece of code un-interruptible规定和结论规定和结论n对于信号量变量的规定：对于信号量变量的规定：n必须置一次初值，只能置一次初值，初值必须置一次初值，只能置一次初值，初值=0;n只能执行只能执行P操作和操作和V操作，所有其它操作非法。操作，所有其它操作非法。n几个有用的结论几个有用的结论：n当当s-value0时，时，s-queue为空；为空；n当当s-valuevalue|为队列为队列s-queue的长度；的长度；n当当s.value初=1时，可以实现进程互斥；时，可以实现进程互斥；n当当s.value初=非1正整数时，可以用来管理同种组合资源，申请时，可以用来管理同种组合资源，申请资源执行一次资源执行一次P操作，归还资源执行一次操作，归还资源执行一次V操作；操作；n当当s.value初=0时，可以实现进程同步。时，可以实现进程同步。semaphore mutex; (初值初值=1） shared int x,y,z; CR1 CR2 CRn用信号量实现进程互斥用信号量实现进程互斥semaphore mutex; (初值初值=1） shared int x,y,z;P(mutex) P(mutex) P(mutex) CR1 CR2 CRnV(mutex) V(mutex) V(mutex)互斥例子：借书系统互斥例子：借书系统(revisited)nsemaphore mutex=1; n终端终端1： 终端终端2：ndo don 等待借书者等待借书者； 等待借书者等待借书者；n if x1 if x1 n x=x-1; x=x-1;n n 借书借书 借书借书n n else 无书无书; else 无书无书; n while(1) while(1)互斥例子：借书系统互斥例子：借书系统(revisited)semaphore mutex=1; 终端终端1： 终端终端2：do do 等待借书者等待借书者； 等待借书者等待借书者； P(mutex) P(mutex) if x1 if x 1 x=x-1; x=x-1; V(mutex) V(mutex) 借书借书 借书借书 else V(mutex);无书无书; else V(mutex);无书无书; while(1) while(1)用信号灯实现进程同步用信号灯实现进程同步 后动作后动作先动作先动作 P1:P2:用信号量实现进程同步用信号量实现进程同步 P(S)后动作后动作先动作先动作 V(S)P1:P2:用信号量实现进程同步用信号量实现进程同步n例子：司机例子：司机-售票员问题：售票员问题：n司机活动：司机活动： 售票员活动：售票员活动：n Do Don 关车门关车门n 启动车辆启动车辆 n 正常行驶正常行驶 售售 票票n 到站停车到站停车 n 开车门开车门n While(1) While(1)用信号量实现进程同步用信号量实现进程同步例子：司机例子：司机-售票员问题：售票员问题：semaphore s1=0,s2=0; 司机活动：司机活动： 售票员活动：售票员活动： Do Do P(S1) 关车门关车门 启动车辆启动车辆 V(S1) 正常行驶正常行驶 售售 票票 到站停车到站停车 P(S2) V(S2) 开车门开车门 While(1) While(1)用开关中断实现用开关中断实现P、V操作操作void P(semaphore *s) disable interrupt; s-value-; if (s-valuequeue) enable interrupt; goto CPU dispatcher; else enable interrupt; 用开关中断实现用开关中断实现P、V操作操作void V(semaphore *s) disable interrupt; s-value+; if (s-value0) wakeup(s-queue) else enable interrupt; 用开关中断实现用开关中断实现P、V操作操作nasleep(s-queue):set this process status to blocked;place this process in s-queue.nwakeup(s-queue):remove a process from s-queue;place the process in ready list.用用TS、swap指令实现指令实现P、V操作操作void P(semaphore *s) while(TS(s-flag); s-value-; if (s-valuequeue) s-flag=0; goto CPU dispatcher; else s-flag=0; 用用TS、swap指令实现指令实现P、V操作操作void V(semaphore *s) while(TS(s-flag); s-value+; if (s-value0) wakeup(s-queue) else s-flag=0;Classical synchronization problems1. Producers and consumers problem2. Readers and writers problem3. Dining philosophers problem4. Cigarette smokers problem5. Sleepy barbers problemetc. 例例1. 生产者生产者/消费者问题消费者问题预备知识：预备知识：组合资源组合资源：若干相对独立的资源构成的资源集合，其中：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。每个相对独立的资源称为子资源。同种组合资源同种组合资源：相同类型子资源构成的组合资源。：相同类型子资源构成的组合资源。管理：管理：semaphore s; (初值初值=子资源个数）子资源个数）例子：例子：2台打印机台打印机 semaphore s=2; 申请：申请：P（S）；）； 释放：释放：V（S）；）；自动机描述自动机描述210-1-2P(S)P(S)P(S)P(S)P(S)V(S) V(S) V(S) V(S) V(S) S-value=空闲资源数空闲资源数 S-queue=空空|S-value|=等待进程数等待进程数 空闲资源数空闲资源数=0.P(S): 申请一台打印机申请一台打印机, 分配分配, 空闲打印机减空闲打印机减1P(S): 申请一台打印机申请一台打印机, 等待等待, 等待进程数加等待进程数加1 2自动机描述自动机描述10-1-2P(S)P(S)P(S)P(S)P(S)V(S) V(S) V(S) V(S) V(S) S-value=空闲资源数空闲资源数 S-queue=空空|S-value|=等待进程数等待进程数 空闲资源数空闲资源数=0.V(S): 释放一台打印机释放一台打印机, 唤醒一个等待者唤醒一个等待者, 打印机分给被唤醒进程打印机分给被唤醒进程, 等待进程数减等待进程数减1V(S): 释放一台打印机释放一台打印机, 空闲打印机数量增空闲打印机数量增1 例例1. 生产者生产者/消费者问题消费者问题 0 1 k-1箱子，容量箱子，容量k itemType bufferk生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之环形缓冲区环形缓冲区10K-1in(in+1)% kout(out+1)% k问题分析生产者活动生产者活动： 消费者活动消费者活动： do do 加工一件物品加工一件物品 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 消耗这件物品消耗这件物品 while(1) while(1)资源：箱子（同种组合）资源：箱子（同种组合） 资源：物品（同种组合）资源：物品（同种组合） semaphore s1; semaphore s2; s1.value=k; s2.value=0;放前：放前：P（S1） 取前：取前：P（S2）放后：放后：V（S2） 取后：取后：V（S1）同步同步生产者活动生产者活动： 消费者活动消费者活动： Do Do 加工一件物品加工一件物品 P(S2) P(S1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(S1) V(S2) 消耗这件物品消耗这件物品 While(1) While(1)对对B和和in,out的互斥的互斥：semaphore mutex=1; 考虑互斥的生产者和消费者问题考虑互斥的生产者和消费者问题生产者活动：生产者活动： 消费者活动：消费者活动： do do 加工一件物品加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗这件物品消耗这件物品 while(1) while(1)程序void producers_consumers; itemType bufferk; semaphore s1=k,s2=0,mutex=1; int in=0; int out=0;void producer() while(1) produceitem(&item) P(S1); P(mutex); bufferin=item; in=(in+1)%k; V(mutex); V(S2) void consumer() while(1) P(s2); P(mutex); x=bufferout; out=(out+1)%k; V(mutex); V(S1); consumeitem(x); 程序程序Cobegin fork(producer,0); ;fork(producer,m-1); fork(consumer,0); ;fork(consumer,n-1);Coend;并发性提高策略并发性提高策略生产者和消费者：不操作生产者和消费者：不操作buffer的相同分的相同分量量生产者的共享变量生产者的共享变量： Bin, in消费者的共享变量消费者的共享变量： Bout, outin=out: 满或空,semaphore mutex1=1,mutex2=1; 并发性提高策略并发性提高策略生产者活动：生产者活动： 消费者活动：消费者活动： do do 加工一件物品加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗这件物品消耗这件物品 while(1) while(1)P、V顺序不当会发生死锁顺序不当会发生死锁生产者活动：生产者活动： 消费者活动：消费者活动： do do 加工一件物品加工一件物品 P(S2) P(mutex) P(mutex) P(S1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗这件物品消耗这件物品 while(1) while(1)例例2. 读者读者/写者问题写者问题P. J. Courtois 1971首先提出并解决的问题首先提出并解决的问题Communication of the ACM, Vol.14, 667-669.ACM: Association for Computing Machinery解法解法1：写者可能饿死：写者可能饿死解法解法2：写者优先：写者优先例例2. 读者读者/写者问题写者问题Problem Statement: 一组公共数据一组公共数据DB R1 Rm W1 . Wn要求要求：（：（1）R-R可以同时可以同时 （2）R-W不可同时不可同时 （3）W-W不可同时不可同时accessingSolution1: 不考虑不考虑R-R不互斥不互斥semaphore r_w_w=1; Reader： Writer: P(r_w_w); P(r_w_w) 读操作读操作 写操作写操作 V(r_w_w); V(r_w_w)分析：（分析：（1）写者活动正确；（）写者活动正确；（2）R-R不能同时。不能同时。改进：最先进入的改进：最先进入的R执行执行P；最后离开的；最后离开的R执行执行V；Solution2: 考虑考虑R-R不互斥不互斥int read_count=0; Reader: read_count=read_count+1; If (read_count=1) P(r_w_w); 读操作读操作 read_count=read_count-1; If (read_count=0) V(r_w_w);问题：对问题：对Read_count操作的互斥问题。操作的互斥问题。Solution3: 正确解法正确解法semaphore mutex=1; Reader: P(mutex); read_count=read_count+1; If(read_count=1) P(r_w_w); V(mutex); 读操作读操作 P(mutex); read_count=read_count-1; If(read_count=0) V(r_w_w); V(mutex); 读者等待在何处？读者等待在何处？ 读者如何被唤醒？读者如何被唤醒？程序程序semaphore r_w_w=1; semaphore mutex=1;int read_count=0;viod writer(0) while(1) P(r_w_w); write ops V(r_w_w) 程序（程序（Cont.）viod reader()While(1) P(&mutex); read_count=read_count+1; If(read_count=)1 P(&r_w_w); V(&mutex); read operations P(&mutex); read_count=read_count-1; If(read_count=0) V(&r_w_w); V(mutex); 程序（程序（Cont.）cobegin fork(reader,0); ;fork(reader,m-1); fork(writer,0); ; fork(writer,n-1) coend分析：问题问题：读者源源不断，：读者源源不断，read_count不归不归0，写者，写者会被饿死。会被饿死。策略策略：一旦有写者等待，新到达读者等待，正在：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。读的读者都结束后，写者进入。 Further improvement is left to interested students.写者优先算法写者优先算法 Reader: writer: p(m) 1 p(k) p(w) 2 if(wc=0) p(w) 4 p(mutex) wc=wc+1 if(rc=0) p(s) v(k) rc=rc+1 p(s) 5 v(mutex) v(w) 3 v(s) v(m) p(k) wc=wc-1 p(mutex) if(wc=0) v(w) 6 rc=rc-1 v(k) if(rc=0) v(s) 7 v(mutex)程序程序int readcount=0, writecount=0; semaphore m=1,w=1,s=1,k=1,mutex=1; reader() writer( ) while(1) while(1) p(m); p(k); p(w); if writecount= =0 then p(w); p(mutex); writecount= writecount+1; if readcount= =0 then p(s); v(k); readcount=readcount+1; p(s); v(mutex); v(w); v(s); V(m); p(k); writecount=writecount-1; P(mutex); if writecount = =0 then v(w); Readcount=readcount-1; v(k); If readcount= =0 then v(s); V(mutex); 例例4. 3台打印机管理台打印机管理n设有3台类型相同的打印机，其编号分别为1、2、3，编写一个申请函数require和一个释放函数return。前者要求当有打印机空闲时，返回分的的打印机的编号；当无打印机空闲时则等待，但被唤醒后返回分得的打印机的编号。后者用于释放指定编号的打印机，并当有申请者等待时将其唤醒。例例4. 3台打印机管理台打印机管理enum lp1.3of (free,used); /initial value is freesemaphore s; /initial value is 3semaphore mutex; /initial value is 1void require; void return(i:1.3); P(S); P(mutex); P(mutex); lpi:=free; for(i=1,i=t1 & & Sn=tn ) for(i=1;i=n;i+) Si=Si-di;else (1) place the executing process in the waiting queue for the first Si with Siti, (2)and set the program counter to the beginning of the SP operation so that all conditions will be reexamined when the process is reactivated. Simultaneous V-operationSV(S1,d1;Sn,dn); for(i=1;i=n;i+) Si=Si+di; take out the all of processes in the Si list,and put them into the ready list. 应用应用SP操作解决吸烟者问题操作解决吸烟者问题semaphore t,m,w,s; /0,0,0,1Process X process Y process Z P(s); P(s); P(s);SV(t,1;m,1); SV(m,1;w,1); SV(w,1;t,1);Process A Process B process CSP(m,1,1;w,1,1); SP(w,1,1;t,1,1); SP(t,1,1;m,1,1); smoke; smoke; smoke; V(s); V(s); V(s);4.3.4 条件临界区条件临界区Conditional Critical Regionn背景背景nPV操作低级，容易用错操作低级，容易用错n条件临界区形式条件临界区形式nregion r when b do sn执行执行s条件条件n没有其它进程处于与没有其它进程处于与r相关的条件临界区中相关的条件临界区中n进入进入s时时b为为true条件临界区条件临界区n实现互斥实现互斥nregion r when true do snCCR与与PV操作的等价性操作的等价性( (证明从略）证明从略）n用用CCR可以实现可以实现PV操作操作n用用PV操作可以实现操作可以实现CCR用条件临界区解决有限缓冲区用条件临界区解决有限缓冲区itemtype buffern;int count,in,out;void producer() region buffer when ( count0) temp=bufferout; out=(out+1)%n; count-;while(1)用条件临界区解决简单批处理过程n简单批处理是由作业读入、执行、打印结果这3个相对独立的部分组成。这三者之间是同步关系，用条件临界区实现程序如下：Program batch; type buffer=RECORD slots；ARRAY0.n-1of T; head,tail:0.n-1 initial(0,0); size:0.n initial(0); end;Var inbuff：buffer(cardimage); outbuff:buffer(lineimage);Resource ib:inbuff; ob: outbuff;用条件临界区解决简单批处理过程cobegin process reader: var card: cardimage; loop read card from cardreader; region ib when inbuff.size0 do card:= inbuff.slotsinbuff.head; inbuff.size:=inbuff.size-1; inbuff.head:=(inbuff.head+1)mod n; enddo process card and generate line用条件临界区解决简单批处理过程 region ob when outbuff.size0 do line:= outbuff.slotsoutbuff.head; outbuff.size:=outbuff.size-1; outbuff.head:=(outbuff.head+1)mod n; enddo print line on lineprinter; endloopendprocess4.3.5 管程（管程（Monitor）nPV操作：操作： n分散式同步机制：共享变分散式同步机制：共享变量操作，量操作，PV操作，分散在操作，分散在整个系统中或各个进程中。整个系统中或各个进程中。n缺点：缺点：n可读性差；可读性差；n正确性不易保证；正确性不易保证；n不易修改。不易修改。n优点：优点：n高效，灵活。高效，灵活。n管程：管程：n集中式同步工具：共享变集中式同步工具：共享变量及其所有相关操作集中量及其所有相关操作集中在一个摸块中。在一个摸块中。n优点：优点：n可读性好；可读性好；n正确性易于保证；正确性易于保证；n易于修改。易于修改。n缺点：缺点：n不甚灵活，效率略低不甚灵活，效率略低。4.3.5.1 管程的提出管程的提出n70年代初年代初, BynE.W.Dijkstra, C.A.R.Hoare, P.B.Hansen.n背景背景: Structured programmingn基于管程的语言基于管程的语言nConcurrent Pascal (Hansen)nModula (With)nMesanMod*nConcurrent EuclidnX