孙钟秀操作系统第三章同步、通信与死锁1

1第三章同步、通信与死锁23.1进程的同步与互斥在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。一、进程间制约关系1.竞争关系源于资源共享，多个不存在逻辑关系的进程因共享资源而产生制约关系。若一个进程要求使用某一资源，而该资源正被另一个进程使用，并且这一资源不允许两个进程同时访问，那么该进程只有等待，只有这一资源释放后才能使用。2.协作关系源于进程间的协作。一组进程为完成共同任务分工协作，各进程都独立以不可预知速度推进，在执行的先后次序就有约束，在一些关键点上协调工作。若一个进程运行到某关键点时，在尚未收到另一协作进程发来的信息前应阻塞自己，等协作进程发来消息后方可继续执行。进程——资源——进程进程——进程3进程间这种相互依赖又相互制约，相互协作又相互竞争的关系，主要表现在进程互斥和进程同步两方面二、进程互斥引例：宿舍电话的使用打印机的使用1、临界资源一次仅允许一个进程使用的资源称为临界资源。引例中的电话和打印机都属于临界资源。还有光盘刻录机、绘图仪、共享变量、共享的数据结构等等也是临界资源。2、临界区：每个进程中访问临界资源的那段程序段称为临界区。（临界段）4例：统计两个进程P1和P2对共享变量count的访问计数。P1：….P2:….R1=count;R2=count;R1=R1+1;R2=R2+1;count=R1;count=R2;….….两进程并发执行，可能的执行顺序为：P1:R1=count;R1=R1+1;P2:R2=count;R2=R2+1;count=R2;P1:count=R1;虽然两个进程各自都执行了对count加1的操作，但结果为何count只增加1？count是临界资源，P1、P2访问count的两个程序段就是临界区，两个进程必须互斥的进入临界区,否则就可能出与时间有关的错误.5３、进程互斥进程应互斥访问同一临界资源，即进程应互斥的进入临界区。当一进程正在访问某临界区时，就不允许其它进程进入，试图进入临界区的另一进程必须等待。进程之间的这种相互制约的关系称为进程互斥。4、进入临界区的准则：每次至多有一个进程进入临界区内执行；若已有进程在临界区中，试图进入此临界区的其他进程应等待；进入临界区的进程应在有限时间内退出，以便让等待队列中的一个进程进入。6三、进程同步引例：两位同学约好星期天去玩，早上8:00在校门口，不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一起去玩。互斥的概念来自于诸进程对临界资源的竞争，同步来源于多个进程的协作。在人类社会中竞争与协作是永恒的。进程同步：几个进程相互协作，一个进程到达某点后，若另一进程尚未完成某些操作，就必须停下来等待，只有等另一进程的这些操作完成了才能继续执行。协作进程间需要在某些关键点上排定执行先后次序而等待、传递信号或消息所产生的协作关系称为进程同步。7例：计算fun1(X)*fun2(y)两进程合作完成任务进程1：计算fun1(X)。进程2：计算fun2(X)；与进程1结果相乘。进程1和进程2并发执行。83.2进程互斥的实现一、实现进程互斥的软件算法现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解到，在早期进程互斥问题的解决并不是一件很简单的事。9尝试(1)boolinside1=false;//P1不在其临界区内boolinside2=false;//P2不在其临界区内cobeginprocessP1()processP2(){{while(inside2);while(inside1);inside1=true;inside2=true;{临界区};{临界区};inside1=false;inside2=false;}}coendP1和P2可能同时进入临界区10尝试(2)boolinside1=false;//P1不在其临界区内boolinside2=false;//P2不在其临界区内cobeginprocessP1()processP2(){{inside1=true;inside2=true;while(inside2);while(inside1);{临界区};{临界区};inside1=false;inside2=false;}}coendP1和P2可能永远等待。11processP0(){inside[0]=true;turn=1;while(inside[1]&&turn==1);{临界区};inside[0]=false;}processP1(){inside[1]=true;turn=0;while(inside[0]&&turn==0);{临界区};inside[1]=false;}cobegincoendboolinside[2];inside[0]=false;inside[1]=false;enum{0,1}turn;Peterson算法12为每一进程设标志位inside[i]，当inside[i]=true时，表示进程pi要求进入，或正在临界区中执行。此外再设一个变量turn，用于指示允许进入的进程编号。进程0为了进入先置inside[0]=true，并置turn为1，表示应轮到p1进入。接着再判断inside[1]&&turn==1的条件是否满足,若不满足则可进入。或者说当inside[1]=false或者turn==0时，进程可以进入。前者表示p1未要求进入，后者表示仅允许p0进入.13软件解法的缺点1.忙等待2.实现过于复杂，需要较高的编程技巧14二、实现进程互斥的硬件设施用软件解决很难，现代计算机大多提供一些硬件指令。利用关中断实现进程互斥利用Test-and-Set指令实现互斥利用swap指令实现进程互斥151.利用关中断实现进程互斥进程进入临界区时关中断，在进程退出临界区时开中断。关中断方法简单有效关中断方法的缺点162.Test-and-Set（TS）指令实现互斥TS指令boolTS(bool&x){if(x){x=false;returntrue;}elsereturnfalse;}17TS指令实现进程互斥bools=true;cobeginprocessPi(){//i=1,2,...,nwhile(!TS(s));//上锁{临界区};s=true;//开锁}coend变量s代表了临界资源的状态，可把它看成一把锁。S初值设为true，表示没有进程在临界区，资源可用。进入临界区前，首先用TS指令测试s，若没有进程在临界区，则可进入，否则循环测试直至s的值为true；当进程退出临界区时，把s的值置为true。183.swap指令实现进程互斥swap指令又称交换指令，在Intelx86中称为XCHG。功能是交换两个字的内容。voidSWAP(bool&a,bool&b){booltemp=a;a=b;b=temp;}19利用swap实现进程互斥为每一临界资源设置一个全局布尔变量lock，其初值为false，表示无进程在临界区内。在每个进程中有局部布尔变量keyi。boollock=false;cobeginProcessPi(){//i=1,2,...,nboolkeyi=true;do{SWAP(keyi,lock);}while(keyi);//上锁{临界区};SWAP(keyi,lock);//开锁}coend20实现进程互斥的软件算法太过复杂，效率低下；实现进程互斥的硬件方法虽简单有效，但采用忙式等待，白白浪费cpu时间；将测试能否进入临界区的责任推卸给各进程，会削弱系统的可靠性，加重用户的编程负担；且这些方案只能解决进程互斥问题，却不能解决进程同步问题。213.3信号量与PV操作一、信号量的概念信号量的概念是由荷兰科学家Dijkstra于1965年提出的。管理和控制铁路和公路交通的重要工具是信号灯，利用信号灯的颜色控制各种车辆的正常通行。在操作系统中引入了信号灯（信号量）的概念，让多个进程通过信号量展开交互。221.信号量的定义是一个结构型数据结构，定义如下：structsemaphore{intvalue;//信号量的值structpcb*list;//信号量队列的头指针}信号量说明：semaphores;信号量必须置一次且只能置一次初值，初值不能为负数。对信号量只能执行P、V操作232.P、V操作对信号量仅能执行P、V操作。对信号量的P操作记为：P(S)，P操作是一个原子操作。对信号量的V操作记为：V(S),V操作是一个原子操作。在实际系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。24P(s)：s.value--；若s.value≥0，则执行P(s)的进程继续执行；若s.value0，则执行P(s)的进程被阻塞，并把它插入到等待信号量s的阻塞队列中。V(s)：s.value++；若s.value0，则执行V(s)的进程继续执行；若s.value≤0，则执行V(s)的进程从等待信号量s的阻塞队列中唤醒头一个进程，然后自己继续执行。操作系统正是利用信号量的状态对进程和资源进行管理。从物理意义上理解，P操作相当于申请资源；V操作相当于释放资源。25二、用信号量实现进程互斥1.两个进程间的互斥semaphoreS；S=1；cobeginProcessP1()ProcessP2(){……{……P（S）P（S）V（S）V（S）…………}}coend临界区临界区26对于两个并发进程，互斥信号量的值仅取1、0和-1三个值若S＝1表示没有进程进入临界区若S＝0表示有一个进程进入临界区若S＝-1表示一个进程进入临界区，另一个进程等待进入。27例：有一个售票厅只能容纳300人，当少于300人时，可以进入购票；否则在外等待。若将每一个购票者看作一个进程，请用P、V操作编程实现。semaphoreS；S=300；ProcessPi()（i=1，2，3，……）{P(S)；进入购票厅；购票；离开购票厅；V(S)；}28思考：对于n个并发进程，如何实现互斥；信号量的取值范围是什么，有什么含义。设置互斥信号量S=m（m为某种临界资源可用数量）cobeginprocessP1processP2……processpn{……{……{……P（S）P（S）P（S）V（S）V（S）V（S）………………}}}coend临界区临界区临界区互斥信号量联系一组并发进程，各进程对此信号量执行P、V操作，因此又称为公用信号量。29信号量取值范围：m~m-n信号量的含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数30三、用信号量实现进程的同步1.进程同步模型进程P1到达L1这一点时，若进程P2还未执行到L2点，进程P1就必须停下来等待，等到进程P2到达L2这一点时，P1才能继续运行。也就是进程P1在L1这一点要与进程P2同步。（P1等待P2）semaphores；S=0CobeginprocessP1（）processP2（）{……{……L1:P(s)…………L2:V(s)…………}}coend总结：P1在L1点等待P2进程执行到L2点才能继续执行。设置信号量s=0P1进程L1点：P(S)P2进程L2点：V(S)31在操作系统中，同步有各种各样，归纳起来有两类：保证一组合作进程按确定的次序执行保证共享缓冲区的合作进程的同步。2.合作进程的执行次序若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求。为了描述方便，可以用一个图来描述诸进程合作完成某一任务的次序。——进程流图3233进程流图是实际例子抽象出来的。例：(a+b)*(c+d)+c*fP2P1P3P4P5SFP1P2P3P4P534例：试用信号量实现这三个并发进程按确定的次序执行。a、分析进程的同步关系进程P1、P2可并发执行，P3的执行必须等待P1、P2