• / 56
  • 下载费用:10 金币  

操作系统4-2.ppt

关 键 词:
操作系统4-2.ppt
资源描述:
1,第八讲 同步与互斥实现方法,目的与要求:理解互斥问题的硬件实现方法;掌握信号量机制及使用它解决进程同步互斥问题的方法。 重点与难点:信号量实现及使用。,2,1. 互斥与同步的基本概念,进程同步的主要任务是使并发执行的进程之间能有效地共享资源和相互合作,从而使程序的执行具有可再现性。 互斥:当一个进程正在访问某共享资源时,就不允许其他进程对其访问,这种相互制约关系称为互斥。 临界资源:一段时间内仅允许一个进程使用的资源称为临界资源。 应互斥使用的资源有:打印机、输入机、磁带机;共享变量、共享数据结构等。,3,共享变量例,P1: P2: R1=C; R2=C; R1=R1+1; R2=R2+1; C=R1; C=R2; 如果先执行P1再执行P2,则C值增加2。 若按顺序R1=C;R2=C;R1=R1+1;C=R1;R2=R2+1;C=R2;则C值增加1。这种错误称为“与时间有关的错误”,产生的原因是没有互斥使用共享变量。,4,临界区,临界区:进程中访问临界资源的那段代码称为临界区,又称临界段。 同类临界区:所有与同一临界资源相关联的临界区。,5,同步,同步:多个相关进程在执行次序上的协调。 同步例:计算进程与打印进程共享一个单缓冲区。,C,P,,,缓冲区,6,4.2 解互斥问题的算法,互斥问题的软件解法就是让多个进程互斥地进入各自的同类临界区。,7,解互斥问题应遵循的原则,空闲让进:若无进程处于临界区时,应允许一个进程进入临界区。 忙则等待:当已有进程进入临界区,其他进程必须等待。 有限等待:应保证要求进入临界区的进程在有限时间内进入临界区。 让权等待:当进程不能进入自己的临界区时,应释放处理机。 驻留有限:进程驻留在临界区中的时间有限。,8,用软件方法实现互斥,假设互斥在两个进程间进行,两进程的并发执行表示如下: void main(){ 公共变量说明; cobegin p0();p1();coend },9,访问临界资源的进程描述,void p(int i) {while(true){ 进入代码;临界区;退出代码;非临界区;} },10,算法1的思想,设置一个公用整型变量turn,用来指示允许进入临界区的进程标识。 若turn为0,则允许进程p0进入临界区;否则循环检查该变量,直到turn变为本进程标识;在退出区,修改允许进入进程的标识为1。 进程p1的算法与此类似。两个进程的程序结构如下:,11,算法1的描述,int turn=0;p0: while (true) {while (turn!=0);进程p0的临界区代码cs0 ;turn=1 ;进程p0的其他代码;},12,算法1的描述(续),p1: while (true){while (turn!=1);进程p1的临界区代码cs1;turn=0 ;进程p1的其他代码;},13,算法1存在的问题,此算法可以保证互斥访问临界资源,但两个进程必须以交替次序进入临界区。 此算法不能保证实现空闲让进准则。,14,算法2的思想,设置标志数组flag[ ]表示进程是否在临界区中执行,初值均为假。 在每个进程访问临界资源之前,先检查另一个进程是否在临界区中,若不在则修改本进程的临界区标志为真并进入临界区,在退出临界区时修改本进程临界区标志为假。,15,算法2的描述,enum boolean {false,true}; boolean flag[2]={false,false};p0: while (true){while (flag[1]);flag[0]=true;进程p0的临界区代码cs0 ;flag[0]=false ;进程p0的其他代码;},16,算法2的描述(续),p1: while (true){while (flag[0]);flag[1]=true;进程p1的临界区代码cs1 ;flag[1]=false ;进程p1的其他代码;},17,算法2存在的问题,此算法解决了空闲让进的问题,但有可能两个进程同时进入临界区。 当两个进程都未进入临界区时,它们各自的访问标志值都为false,若此时刚好两个进程同时都想进入临界区,并且都发现对方标志值为false,于是两个进程同时进入了各自的临界区,这就违背了临界区的访问原则“忙则等待”。,18,算法3的思想,本算法仍然设置标志数组flag[ ],但标志用来表示进程是否希望进入临界区。 在每个进程访问临界资源之前,先将自己的标志设置为真,表示进程希望进入临界区,然后再检查另一个进程的标志。若另一个进程的标志为真,则进程等待;否则进入临界区。,19,算法3的描述,enum boolean {false,true}; boolean flag[2]={false,false};p0: while (true){ flag[0]=true;while (flag[1]);进程p0的临界区代码cs0 ;flag[0]=false;进程p0的其他代码;},20,算法3的描述(续),p1: while (true){flag[1]=true;while (flag[0]);进程p1的临界区代码cs1 ;flag[1]=false;进程p1的其他代码;},21,算法3存在的问题,该算法可以有效地防止两个进程同时进入临界区,但存在两个进程都进不了临界区的问题。 当两个进程同时想进入临界区时,它们分别将自己的标志位设置为true,并且同时去检查对方的状态,发现对方也要进入临界区,于是双方互相谦让,结果谁也进不了临界区。,22,算法4的思想,本算法的基本思想是算法3和算法1的结合,是一个正确的算法。 标志数组flag[ ]表示进程是否希望进入临界区或是否正在临界区中执行。还设置了一个turn变量,用于指示允许进入临界区的进程标识。,23,算法4的描述,enum boolean {false,true}; boolean flag[2] ={false,false}; int turn;p0: while (true) { flag[0]=true; turn=1;while (flag[1] && turn = = 1);进程p0的临界区代码cs0 ;flag[0]=false ;进程p0的其他代码;},24,算法4的描述(续),p1: while (true){flag[1]=true;turn=0;while (flag[0] && turn = = 0);进程p1的临界区代码cs1 ;flag[1]=false ;进程p1的其他代码;},25,4.2.3实现临界段的硬件方法,利用处理机提供的特殊指令实现临界区加锁 单处理机系统常见硬件指令有: 一.屏蔽中断 ParbeginA(amount){disableInterrupt();R1=balance;R2=amount;R1=R1+R2;balance=R1;enableInterrupt(); };,,26,B(amount) {disableInterrupt();R1=balance;R2=amount;R1=R1-R2;balance=R1;enableInterrupt(); }; Parend;,27,多处理机系统硬件指令有:,一、“Test_and_Set”指令。 该指令功能描述为: Function Test_and_Set(Var target:boolean) :boolean; begin Test_and_Set = target; Target = true; end;,28,设Lock为全局布尔变量,利用Test&Set指令,即可实现对临界区的加锁与解锁:,29,“test&set” 读后置1指令实例:T&S Ri,Aj 解释为将(Aj)地址所指内存单元内容读到Ri寄存器中,同时将1置入Aj所指的内存单元中.设Lock为临界段锁变量,则安排如下指令,即可实现加锁与解锁:*,30,临界段,,非临界段,A1= (If (R1=1)then goto Loop ),A1 =(0置Lock内存单元),31,二、“Swap”指令。 该指令功能描述为: Procedure Swap(Var a,b:boolean); Var temp:boolean; begin temp = a; a = b; b = temp; end;,32,设Lock为全局布尔变量(初值为假),每个进程设一个局部布尔变量Key。利用Swap指令,可实现对临界区的加锁与解锁。,Repeat key = true;repeatSwap (lock, key);until key = false;critical sectionlock = false;non-critical section Until false;,,,33,4.2.4 信号量,信号量机构:“信号量”、“P、V操作”。信号量S为一整型变量:P(S): While S≤0 do skip ;S = S-1 ;V(S):S = S+1;P、V操作是两条原语,即保证P、V操作对变量S的访问是互斥操作。,34,一. 原语概念与实现 原语:指完成某种功能且不被分割或不被中断执行的操作序列。 原语可通过硬件实现不可中断性;或通过实现临界段的元方法达到不被中断。 实现临界段的元方法: 屏蔽中断(只用于单机) 加硬锁。,35,下面我们用屏蔽中断方法实现P(s)和V(s)的原子性。P(s){DisableInterrupt(); while (s≤0)do{ enableInterrupt();DisableInterrupt(); };s = s - 1;enableInterrupt();}V(s){DisableInterrupt(); s = s +1;enableInterrupt();},36,二、信号量的使用(互斥与同步)互斥:用于n个进程的临界段互斥,n进程共享一个信号量mutex,初值为1,任一进程Pi的结构为:,P(mutex),V(mutex),临界段,非临界段,repeat,Until false,37,同步:有P1、P2 两进程,必须在P1执行完S1语句后,P2才能执行S2。需同步的两进程共享信号量synch,初值为0。,Parbegin,P2: begin,P1: begin,……,S1;,V(synch);,……,end;,……,P(synch);,S2;,……,end;,Parend;,38,,,,请用并行语句和PV操作描述,39,操作系统实现信号量时与进程调度相结合,消除忙等待现象。原则是:在P操作循环等待的地方加入放弃处理机/挂入等待队列动作,在V操作时,从等待队列中摘取进程变为就绪态。 (P、V原语本身的互斥操作通过屏敝中断或为信号量加硬锁实现),三.信号量的具体实现,40,1、信号量定义type Semaphore=recordvalue:integer; 一个数型变量L:List of process;一个PCB队列end; 2、P操作P(S):S.Value=S.value –1;If S.value0 then 保存现场,将本进程挂入S.L队列,重新调度。 3、V操作V(S):S.value:=value+1If S.value ≤0 then 从S.L队列取一进程,挂入就绪队列。,41,利用信号量实现前驱关系,例如:P1、P2、P3、P4、P5、P6为一组合作进程,其前驱图如下所示,试用P、V操作完成这六个进程的同步。,P1,P2,P6,P4,P3,,,,,P5,,,,42,解法1,设七个同步信号量a、b、c、d、e、f、g分别表示进程之间的前驱关系,如图所示,其初值均为0。这六个进程的同步描述如下:,P1,P2,P6,P4,P3,,,,,P5,,,,a,b,c,d,f,e,g,43,解法1(1),P1() { ┆v(a);v(b);},P1,P2,P6,P4,P3,,,,,P5,,,,a,b,c,d,f,e,g,44,解法1(2),P2() {p(a);┆v(c);v(d);},P1,P2,P6,P4,P3,,,,,P5,,,,a,b,c,d,f,e,g,45,解法1(3),P3() {p(b);┆v(e); },P1,P2,P6,P4,P3,,,,,P5,,,,a,b,c,d,f,e,g,46,解法1(4),P4() {p(c);┆v(f); },P1,P2,P6,P4,P3,,,,,P5,,,,a,b,c,d,f,e,g,47,解法1(5),P5() {p(d);┆v(g); },P1,P2,P6,P4,P3,,,,,P5,,,,a,b,c,d,f,e,g,48,解法1(6),P6() {p(e);p(f);p(g);┆ },P1,P2,P6,P4,P3,,,,,P5,,,,a,b,c,d,f,e,g,49,解法2,设五个同步信号量f1、f2、f3、f4、f5分别表示进程P1、P2、P3、P4、P5是否执行完成,其初值均为0。这六个进程的同步描述如下:,50,解法2(1),P1() { ┆v(f1);v(f1);},P1,P2,P6,P4,P3,,,,,P5,,,,51,解法2(2),P2() {p(f1);┆v(f2);v(f2);},P1,P2,P6,P4,P3,,,,,P5,,,,52,解法2(3),P3() {p(f1);┆v(f3); },P1,P2,P6,P4,P3,,,,,P5,,,,53,解法2(4),P4() {p(f2);┆v(f4); },P1,P2,P6,P4,P3,,,,,P5,,,,54,解法2(5),P5() {p(f2);┆v(f5); },P1,P2,P6,P4,P3,,,,,P5,,,,55,解法2(6),P6() {p(f3);p(f4);p(f5);┆ },P1,P2,P6,P4,P3,,,,,P5,,,,56,同步描述要求,上述同步描述还应增加以下内容: main( ) { semaphore f1=f2=f3=f4=f5=0;cobegin p1(); p2();p3(); p4();p5(); p6();coend },
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:操作系统4-2.ppt
链接地址:https://www.weizhuannet.com/p-9819044.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开