《第2章进程同步演示-》由会员分享,可在线阅读,更多相关《第2章进程同步演示-(16页珍藏版)》请在金锄头文库上搜索。
1、22 进程间通信221 竞争条件 并发进程的相关性 资源共享方式:a)内存,CPU,设备,文件,系统分配和协调;b)小量软资源,共享队列,通过手段协调。 进程合作。1间接相互制约方式2直接相互制约方式这些关系可以归结为两种关系:互斥和同步。互斥(mutual exclusion)-共享某资源的各进程不能同时进行同一操作。竞争条件-(race condition,书P24)即两个或多个进程读写某些数据,而最后的结果取决于进程运行的精确时序,就称为竞争条件。这就是为什么会产生与时间有关的错误的原因。同步(synchronization)-关于进程间合作时操作的时间顺序的限制。互斥和同步的区别:一个
2、只要不同时发生就行,谁先谁后看排队、优先级;一个是动作要有严格的时间顺序。下面我们先讨论互斥的问题222 临界区(Critical Section)我们把一次仅允许一个进程使用的资源称为临界资源(Critical Resource)。如打印机,绘图仪,磁带机等,公共变量,公用表格,公用队列等。访问临界资源的那段程序称为临界区。它能够从概念上分离出来,而,或叫临界段(互斥段)。例1:有两个进程共享一个变量count。P1:R1:=COUNT;| R1:=R1+1;| COUNT:=R1;|P2:R2:=COUNT;| R2:=R2+1;| COUNT:=R2;此时两个进程各自对count作了加操
3、作,而count增加了2。如果执行是另一种顺序。P1:R1:=COUNT;| 发生时钟中断P2:R2:=COUNT;|P2:R2:=R2+1;|COUNT:=R2;|P1:R1:=R1+1;|COUNT:=R1;虽然两个进程也各自对count作了加一操作,但count却只增加了一。例2:两个进程在系统中共用一个缓冲队列。如果程序顺序是p1:return ptr1:=ptr;获得第一个缓冲区的PTR ptr:=tail(ptr);指针指向下一个p2:reture ptr2:=ptr;获得第二个缓冲区的PTRptr:=tail(ptr);指针指向第三个但如果程序顺序是:p1:return ptr1
4、:=ptr;获得第一个缓冲区的PTR发生时钟中断:p2:reture ptr2:=ptr;也获得第一个缓冲区的PTRp1:ptr:=tail(ptr);指针指向第二个PTRp2:ptr:=tail(ptr);指针指向第三个PTR执行结果造成p1,p2共得一个缓冲区,第二个缓冲区丢失,第三个缓冲区成为首部。设置准则:P24 任何两个进程不能同时处于临界区。 不应对CPU的速度和数目作任何假设。 临界区外的进程不得阻塞其它进程。 不得使进程在临界区外无休止地等待。223 忙等待的互斥2231 关闭中断2332 设置锁变量在测试与设置方法中,设置个变量w来代表某种临界资源的状态,因此w又成为锁或锁位
5、。w=0 表示资源空闲(可用)w=1 表示资源已被使用关锁原语: lock(w);关中断L:if w=1 then goto L else w:=1开中断开锁原语: unlock(w);w:=0;大家注意:由于原语执行时不能中断。考虑三个进程P1:P2:P3:lock(w);lock(w);lock(w);执行临界段1;执行临界段2;执行临界段3;unlock(w);unlock(w);unlock(w);2233 严格轮换法(书P25)2234 Peterson解决方案(书P26)2235 TSL指令例1:IBM360/370采用汇编实现LOCK(X)TSX 测锁位并置1,送PSW(条件码)
6、BNZ -4 不为0,往回跳4字节,继续执行TSX。UNLOCK(X)MOI X,00例2:Intel 8086/8088 汇编指令也能实现锁原语。LOCK PROC FAR汇编语言的过程保留字MOV AL,1;将1送入AL寄存器AGAIN:XCHG AL,FLAG ;交换指令,状态进入AL,FLAG=1关锁TEST AL,AL;测试AL,看状态是什么JNZ AGAIN;AL=1时回跳(FLAG=1)RET;返回主程序UNLOCK PROC FAR;开锁MOV FLAG ,0;FLAG=0RET;修改后的关锁和开锁原语为:lock w:begin if w=1 then begin block
7、(n); insert(wL,n); scheduler end else w:=1end;unlock w:begin if wn then begin remove(wL,q); states(q):=readya; insert(RL,q) end; w:=0end;225 信号量(semaphores machini)一、信号量信号量是表示资源的物理实体,是一个与队列有关的整型变量。在类pascal中,将它表示为一个记录。type semaphore=record val:integer;值域 L:pointer;指针域end;信号量实际是一个计数锁(广义锁),它的值只能由P、V操作来
8、改变。二、P、V操作(计数信号量机制)procedure p(s);var s:semphore;beginLock out interrupt;关中断 s.value=s.value-1; if s.value0 then beginstates(q):=blockeda;活动阻塞insert(wL,q);插入等待队列unlock interrupt;开中断scheduler; 重新分配CPUend else unlock interrupt;开中断end;procedure v(s)var s:semaphore;begin lock out interrupt;关中断 s.value:=
9、s.value+1; if s.value=0等待队列不空 then beginremove(wl,r);从wl队中摘下rstates(r):=readya;活动就绪insert(rl,r);插入就绪队列length(rl):=length(rl)+1endl; unlock interrupt开中断end;P、V操作必须是原语,执行期间不可分割。P、V操作的物理意义:P操作:信号量s可以看成一个资源量。例如有几台打印机,即信号量 s.value初值=n,如果有进程对s进行P操作就是申请该资源的一个单位(申请一台打印机),所以进行一次P操作,s.value要减1(减少一个资源)。进行到最后S分
10、配完毕(s.value=0),再有进程申请资源(进行P(s),使s.value0 其值为剩余(尚有)资源s.value=0 无资源,无等待进程s.value0 s.value的绝对值即为等待该资源的进程数。V操作:表示释放资源,s.value=s.value+1。如果s.value=1 then x:=x-1; write(x); V(mutex)end;procedure t2(x); var x:integer; begin P(mutex);read(x);if x=1 then x:=x-1;write(x);V(mutex);end;Hansen提出并行PASCAL语言之前,Dijk
11、stra提出: COBEGIN S1;S2;S3;;Sn COENDP、V操作在这里起到了lock和unlock的作用,实现了互斥。2利用信号量实现进程同步例1:有一个缓冲区,有计算进程和打印进程同时并行工作,计算进程将结果放在缓冲区,放之前要申请缓冲区空,打印进程负责把结果打印出来,做之前要申请缓冲区满,这是一个同步问题,初始,一定要计算进程先动作,先缓冲区写入,然后再打印进程工作。在缓冲区满时,计算进程不能写。在缓冲区空时,打印进程不能读。打印进程计算进程 缓冲区我们可以设空、满信号量 empty:=1; full:=0;P计算:P打印:RepeatRepeatP(empty);P(ful
12、l); 写入数据;输出数据;V(full);V(empty);Until false;Until false;用P、V操作,实现了题意要求*生产者-消费者问题(producer-consumer problems)生产者和消费者问题,是从操作系统中许多实际同步问题中抽象出来的具有代表性的问题。它反映了操作系统中典型的同步例子。生产者进程生产信息,例如它可以是计算进程;消费者进程使用信息,它可以是输出打印进程。由于生产者和消费者进程彼此独立,且运行速度不确定,可能出现生产者已生产了信息,而消费者却没有来得及接受的情况,为此引入了一个或若干个存储单元组成的临时存储区,以便存放生产者所产生的信息,以平滑