《进程同步与通信xiugai》由会员分享，可在线阅读，更多相关《进程同步与通信xiugai（70页珍藏版）》请在金锄头文库上搜索。
1、第3章 进程同步与通信 进程同步与互斥 经典进程同步问题 管程 AND信号量 进程通信 本章要点本章要点取空闲块的进程Getspace:Begin局部变量 gg=stacktoptop=top1返回值为gEnd释放数据块ad的进程Release(ad):Begintop=top1stacktop=adEnd设t0时刻，top=3。假设执行顺序为：先执行Release(ad)的第一条： top=top1 = 31= 4再执行Getspace： g=stack4，top=top1= 3再执行Release(ad)的第二条： stack3=ad 3.1 进程的同步与互斥 3.1 进程的同步与互斥同步
2、与互斥的引入 OS引入进程后，由于进程的异步性， 可能会导致程序执行结果的不确定性， 使程序执行时出现不可再现性。 进程互斥与同步的主要任务是使并发执 行的诸进程之间能有效地共享资源和相 互合作，从而使程序的执行具有可再现 性。程序的制约方式有如下两种 ： （1）间接制约方式。互斥 这是由于竞争相同资源而引起的，得到资 源的程序段可以投入运行，而得不到资源 的程序段就是暂时等待，直至获得可用资 源时再继续运行。 （2）直接制约方式。同步 这通常是在那些逻辑上相关的程序段之间 发生的。一般是由于各种程序段要求共享 信息引起的。进程同步的基本概念 同步：指多个进程中发生的事件存在着某种时 序关系，
3、它们必须按规定时序执行，以共同完成 一项任务 。 互斥：多个进程不能同时使用同一资源。 临界资源：某段时间内仅允许一个进程使用的 资源。 临界区：每个进程中访问临界资源的那段代码 。例：P1，P2两进程共 享变量COUNT（ COUNT的初值为5 ） P1:R1=COUNT;R1=R1+1;COUNT=R1; P2:R2=COUNT;R2=R2+1;COUNT=R2; 分析： 1执行顺序P2P1 执行结果 P1：COUNT为7， P2：COUNT为6。 2执行顺序P1：R1=COUNT P2：R2=COUNT P1：R1=R1+1；COUNT=R1 P2：R2=R2=1；COUNT=R2 执行
4、结果 P1：COUNT为6， P2：COUNT为6。临界资源实例例：P1，P2两线程共 享变量COUNT（ COUNT的初值为5 ） P1:R1=COUNT;R1=R1+1;COUNT=R1; P2:R2=COUNT;R2=R2+1;COUNT=R2; 用Bernstein条件考察 R（P1）=R1，COUNT W（P1）=R1，COUNT R（P2）=R2，COUNT W（P2）=R2，COUNTR（P1）W（P2）临界资源实例 P1、P2不符合Bernstein条件 必须对程序的执行顺序施加某种限制While(1) 空闲让进当无进程处于临界区时，临界资源 处于空闲状态。此时允许进程进入 临
5、界区。 忙则等待当已有进程进入临界区时，临界资 源正在被访问，其他想进入临界区 的进程必须等待。 有限等待对于要求访问临界资源的进程，应 保证在有效的时间内进入，以免进 入“死等”状态。 让权等待当进程不能进入临界区时，应立即 释放处理机，以免进程进入“忙等 ”。进入区临界区退出区剩余区同步机制应遵循的准则访问临界资源的进程描述为互斥实现的硬件方法 禁止中断 专用机器指令 TS（Test and Set）指令 Swap指令/TS指令： boolean TS(lock); boolean lock; boolean temp; temp = lock; lock = true; return t
6、emp; Lock有两种状态： 当lock=false时，表示资源空闲; 当lock=true时，表示资源正在被使用。 为了实现互斥，设布尔变量lock，其初值为false, 表示资源空闲。利用TS指令实现互斥。 缺点：没有做到：“让权等待”。/TS指令的使用 while (TS(lock) /*什么也不做*/; 临界区; lock = false; 剩余区;TS（Test and Set）指令互斥实现的软件方法/进程0 while (turn!=0) /什么都不做; 临界区; turn = 1; 剩余区;/进程1 while (turn!=1) do/什么都不做; 临界区; turn = 0
7、; 剩余区; 设置公共整型变量 turn，用于指示进 入临界区的进程编 号i(i=0,1)。使P0 、P1轮流访问临界 资源。 缺点：强制性轮流 进入临界区，不能 保证“空闲让进” 。单标志算法/进程0 while (flag1)/什么都不做 ; flag0=true; 临界区; flag0 =false; 剩余区;/进程1 while ( flag0) /什么都不做 ; flag1=true; 临界区; flag1 =false; 剩余区; 设置数组flag，初始时设 每个元素为false,表示 所有进程都未进入临界 区。若flagi=true, 表示进程进入临界区执 行。 在每个进程进入临
8、界区时 ，先查看临界资源是否 被使用，若正在使用， 该进程等待，否则才可 进入。解决了“空闲让 进”问题。 缺点：可能同时进入临界 区，不能保证“忙则等 待”。用软件方法解决互斥问题双标志、先检查算法/进程0 flag0=true; while (flag1)/什么也不做; 临界区; flag0 =false;剩余区; 两进程先后同时作flagi=true; 缺点：保证了不同时进入临界区，但 又可能都进不去。不能保证“有空让 进”。/进程1 flag1=true; while (flag0)/什么也不做; 临界区; flag1 =false ; 剩余区;双标志、先修改后检查算法用软件方法解决互
9、斥问题/进程0 flag0=true; turn=1; while (flag1) 临界区; flag0 =false ; 剩余区;保证了“有空让进”和“忙则等待”。/进程1 flag1=true; turn=0; while (flag0) 临界区; flag1 =false ; 剩余区;先修改、后检查、后修改算法用软件方法解决互斥问题信号量和PV操作 1965年，荷兰学者Dijkstra提出了信号灯机 制，卓有成效地解决了进程同步问题。 记录型信号灯的定义 struct semaphoreint value;struct PCB *queue; 信号灯的PV操作void wait(sema
10、phore s) s.value = s.value - 1;if (s.value 0是sem0返回P原语V原语sem为互斥信号量，取值（1，0，-1）。sem=1表示有一个空闲资源。即，进程PA和PB都没进临界区。sem=0表示有0个空闲资源。即，某进程已经进入临界区sem=-1表示差一个空闲资源。即，某进程已经进入临界区， 但另有一进程已经做了P原语，正在等待。 Pb:P(sem)V(sem);可具体化用信号灯解决互斥问题用信号灯解决互斥问题semaphore mutex=1; P1:while (1) P(mutex); 临界区; V(mutex); 剩余区;P2:while (1)
11、P(mutex); 临界区 V(mutex); 剩余区;A：测试，直到buf为空计算计算结果bufgoto A计算进程Pc打印进程PpB：测试，直到buf满打印buf中的数据清除buf中的数据goto B这里假定已经对公有缓冲区buf进行了互斥措施。缺点：用“测试”来实现同步，消耗大量CPU时间。用“测试”来实现同步A：wait(Bufempty)计算计算结果bufBufempty=falsesignal(Buffull=true)goto A计算进程Pc打印进程PpB：wait(Buffull)打印buf中的数据清除buf中的数据Buffull=falsesignal(Bufempty=tr
12、ue)goto B1、设消息名Bufempty表示buf空，消息名Buffull表示buf满。2、初始化Bufempty=true，Buffull=false。wait的时候，可处于等待状态。 不消耗CPU。返回节目录用wait和signal实现同步私用信号量公有信号量：用于互斥。表示公有资源是否可用。私用信号量：用于同步。例如，Bufempty是计算进程 的私用信号量，Buffull是打印进程的私用信号量。用P，V原语实现同步1、设Bufempty为进程Pa的私用信号量，Buffull为Pb的私用信号量2、初始化：Bufempty=n；Buffull=0。Pa：deposit(data)局部
13、变量xP(Bufempty)选择一个空区Buf(x)Buf(x) dataBuf(x)置满标记V(Buffull)发送进程Pa接收进程PbB：remove(data)局部变量xP(Buffull)选择一个空区Buf(x)data Buf(x)Buf(x)置空标记V(Bufempty)问题：需要考虑互斥吗？用信号灯解决同步问题semaphore a,b=0,0;s1; V(a); V(b)P(a); s2P(b); s3 生产者消费者问题 读者写者问题 哲学家进餐问题 打磕睡的理发师问题 3.2经典进程同步问题生产者-消费者问题 指有两组进程共享一个环形的缓冲池。一组进程被称为 生产者，另一组进
14、程被称为消费者。 缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲 区可以容纳一个产品。 生产者进程不断地将生产的产品放入缓冲池，消费者进 程不断地将产品从缓冲池中取出。 用信号量解决“生产者-消费者”问题void consumer()/消费者进程 while (true) P(full);P(mutex);data_c = bufferj;j = (j + 1) % n;V(mutex);V(empty);consume the item in data_c;semaphore mutex =1; semaphore empty = n; semaphore full = 0;int i,j
15、; ITEM buffern; ITEM data_p, data_c; void producer() /生产者进程while (true)produce an item in data_p;P(empty);P(mutex);bufferi = data_p;i = (i + 1) % n;V(mutex);V(full);读者-写者问题 一个数据对象若被多个并发进程所共享， 且其中一些进程只要求读该数据对象的内容 ，而另一些进程则要求写操作，对此，我们 把只想读的进程称为“读者”，而把要求写的 进程称为“写者”。 问题描述： 读者可同时读； 读者读时，写者不可写； 写者写时，其他的读者、写者均不可进 入。读者进程： while(true) 有人要读 P(Wmutex);读;无人读了 V(Wmutex); 写者进程： while(true) P(Wmutex); 写; V(Wmutex); semaphore Wmutex=1;用信号量解决读者-写者问题void reader() /*读者进程*/ w
