计算机操作系统第四章.ppt

1,第4章并发与互斥,基本概念互斥：软件方法硬件方法信号量机制管程死锁,主要内容,2,4.1基本概念,4.1.1临界资源和临界区临界资源（CriticalResources）：一种一次只能为一个进程服务的资源。临界区（CriticalSection）：进程中访问临界资源的程序。每个使用该资源的进程都要包含一个临界区。操作系统在管理可控制资源分配与使用方面，应当保证进程对临界资源的访问满足以下3点：l互斥访问要求。l不致于产生“死锁”。l不能有“饥饿”进程。,3,4.1.2互斥管理准则,空闲让进：当没有进程在临界区时，任何需要进入临界区的进程都允许立即进入。忙则等待：在共享同一对象的所有进程中，一次只能有一个进程进入临界区。其它要求进入临界区的进程只能等待。有限等待：任何一个进程经有限时间等待后都能进入临界区，不允许出现进程死锁或饥饿的情况发生。让权等待：当一个进程不能进入临界区时要立即阻塞自己，释放处理机让其它进程使用，避免“忙等”。,4,4.2互斥：软件方法,第一次尝试算法中设计了一个变量turn保存允许进入临界区的进程编号（初值为1，表示进程1可以首先进入）。当一个进程要求进入临界区时，先检查turn的值。若turn保存的不是自己的进程编号就进行循环等待；否则进入临界区。访问完成后退出临界区，再将turn设置为对方的进程编号。第二次尝试算法中定义了一个标志数组flag。当flagi=true，表示进程i正在临界区。初始时Flag的各分量值皆为false，表示尚无进程进入。当一个进程要求进入临界区时，先检查是否有进程已进入。若有进程进入，就循环等待；否则，设置自己的标志为真，立即进入。访问完成后再将自己的标志设为假。,4.2.1Dekker方法,5,算法如下：ProcessP(1)ProcessP(2)BeginbeginWhile(Flag2)doskip;While(Flag1)doskip;Flag1=true;Flag2=true;Criticalsection;Criticalsection;Flag1=false;Flag2=false;end.end.,6,第三次尝试,在第二次尝试的基础上，将其中的两个语句顺序交换，形成了新的算法如下：ProcessP(1)ProcessP(2)BeginbeginFlag1=true;Flag2=true;While(Flag2)doskip;While(Flag1)doskip;Criticalsection;Criticalsection;Flag1=false;Flag2=false;end.end.,7,第四次尝试,这是一个“礼让为先”的算法，每个进程设置好自己的flag标志，表明希望进入临界区。但也准备重置flag，以表示谦让。算法如下：ProcessP(1)ProcessP(2)BeginbeginFlag1=true;Flag2=true;While(Flag2)doWhile(Flag1)doflag1=false;flag2=false;flag1=true;flag2=true;Criticalsection;Criticalsection;Flag1=false;Flag2=false;end.end.,8,正确的算法,为了避免过度互斥礼让的问题，Dekker使用第一种尝试中的轮盘变量turn，表示哪个进程有权进入临界区。让它在两个进程的活动中规定一个强制性的顺序。算法如下：ProcessP(1)ProcessP(2)BeginbeginFlag1=true;Flag2=true;While(Flag2)doWhile(Flag1)doif(turn=2)if(turn=1)flag1=false;flag2=false;while(turn=2)doskip;while(turn=1)doskip;flag1=true;flag2=true;Criticalsection;Criticalsection;turn=2;turn=1;Flag1=false;Flag2=false;end.end.,9,4.2.2Peterson算法,变量turn用来保存进程的编号，当turn=i，表示进程i有权进入临界区。数组flag表示哪个进程进入了临界区，Flagi=true，表示进程i已进入。初始时，标志数组flag的各元素值皆为false，表示无进程进入临界区。变量turn可以不设初始值。下面是该算法的主要部分：ProcessP(1)ProcessP(2)BeginbeginFlag1=true;Flag2=true;turn=2;turn=1;While(Flag2turn=2)While(Flag1turn=1)doskip;doskip;Criticalsection;Criticalsection;Flag1=false;Flag2=false;end.end,10,4.3硬件方法,4.3.1交换指令将两个指定位置上的数据进行交换，是该指令实现的操作。微型机PC上对应的指令格式是XCHGop1，op2，用于交换两个操作对象的值（其中，opi是操作对象）。交换指令的功能可描述为下面的过程：ProcedureXCHG(op1,op2)BeginBooleantemp;temp=op1;op1=op2;op2=temp;End,11,4.3.2测试与设置指令,该指令将状态测试和状态设置集于一条指令中，形成一个原子操作。也就是说，两个操作的执行不受中断信号的干扰。下面将指令格式定义为TS（），功能是，读出一个指定变量的值，同时将一个新值置入。对于逻辑变量，比如lock，TS（）的测试和设置的功能可描述为下面的函数：FunctionTS(lock)BeginTS=Lock;Lock=true;End,12,下面的例子中定义的全局变量是mutex，初始值为false表示无人进入。利用TS指令实现的互斥机制描述如下。,ProcedureProcess(i)BeginWhile(TS（mutex）)doskip;/循环等待Criticalsection;mutex=false;End.,13,4.4信号量机制,著名的计算机学者Dijkstra通过长期的操作系统研究与设计，于1965年提出了一种同步机制信号量机制。该机制由一个称为信号量（Semaphore，也译为“信号灯”）的特殊变量和两个被命名为P、V操作的原语组成。在广泛的应用中，该机制得到了迅速发展。这一机制的基本原理是，为每个临界资源设置一个信号量，负责在多个进程之间转发互斥信息。当一个进程需要互斥使用某个临界资源时，可通过对信号量的P操作，了解该资源的空闲情况。当它使用完该临界资源后，又可通过对相关信号量的V操作，让其它需要该资源的进程感知到它的离去。若一个资源被视为临界资源，就应当为它定义一个独立的信号量，对进程访问起“放行”和“阻止”作用，就像交通管理中每个路口设置的交通灯一样。,14,4.4.1整型信号量,整型信号量是Dijkstra最初提出的一种信号量，被定义为整型变量。其取值范围是0，1。其值等于1是放行状态（也称作“绿灯”），等于0为阻止状态（也称作“红灯”）。整型信号量机制中的P、V操作是两个小巧玲珑的过程。它们是操作系统中提供的两个原语，其代码如图所示。,15,利用整型信号量机制实现进程互斥访问临界资源时，需要为该资源设一个整型信号量，比如mutex。令其初始值为1，表示它的初始状态空闲。每个要求访问临界资源的进程都要在临界区的前面通过P操作来访问mutex，决定是否可以立即进入临界区。此外，还要在临界区的后面使用V操作，声明使用完毕。程序结构如下所示：processp(i)beginP(mutex);Criticalsection;V(mutex);end;,16,4.4.2记录型信号量,记录型信号量机制是在整型信号量机制的基础上发展起来的，它实现了“让权等待”功能。一个记录型信号量包含两个分量：信号量的值、信号量的等待队列指针，描述如下：typesemaphore=recordvalue:integer;*L:integer;end.记录型信号量的取值范围是-N，+M。其值大于0时为放行状态（也称作“绿灯”状态），小于等于0时为阻止状态（也称作“红灯”状态）。进程可通过执行P操作来了解临界资源的状态，如果发现当前为阻止状态时，就将进程阻塞起来。颇像是交通管理系统中的汽车过路口排队等候一样。,17,P原语具有“阻塞”功能，当某个临界资源被其他进程占用时，就将自己阻塞；V原语具有“唤醒”功能，它能将等待该资源的进程唤醒。,18,生产者-消费者问题,系统里有若干个合作的进程，其中，n（n0）个生产者进程，m（m0）个消费者进程，以及由P（P0）个缓冲区组成的缓冲区环。任何一个生产者进程都可以将自己的产品存入环内的一个缓冲区中；任何一个消费者可以将环内的一个产品取出。生产者源源不断地生产并存入产品；消费者周而复始地从环内取出产品并掉。假定使用的约束条件是：（1)当环中有空闲缓冲区时，允许任一生产者进程把它的产品存入。(2)当环中无空闲缓冲区时，则试图将产品存入缓冲区环的任何生产者进程必须等待。(3)当环中尙有未取出的产品时，允许任一个消费者进程把其中的一个产品取出。（4）当环中没有未取出的产品时，试图从该环内取出产品的任何消费者进程必须等待。,19,图中，左侧的进程P1Pn为生产者进程，右侧的S1Sm为消费者进程。图中的缓冲区环内有8（P=8）个缓冲区，每个缓冲区可以存入一件产品。环上设有存入指针和读取指针，都按顺时针方向移动。,20,生产者进程的同步控制程序描述为下述过程：Semaphore:mutex,Sin,Sout1,8,0;Integer:in,out0,0;ParbeginProducer();Consumer()Parend.ProcessProducer()BeginWhile(true)BeginProduce_an_Item()_in_NextP1;/计算一个数据P(Sin);P(mutex);BufferinNextP1;/临界区in(in+1)MOD8;V(mutex);V(Sout);,21,EndEndProcessConsumer()BeginWhile(true)BeginP(Sout);P(mutex);NextP2Bufferout;/临界区out(out+1)MOD8;V(mutex);V(Sin);Consume_an_Item()_in_NextP2;/消费一个数据EndEnd,22,读者-写者问题有一个数据块被多个用户共享，其中部分用户是读者，另一部分是写者。我们规定：读者对数据块是只读的，而且允许多个读者同时读；写者对数据块是只写的，当一个写者正在向数据块写信息的时候，不允许其他用户使用，无论是读还是写。该问题中的数据块作为多个用户共享的资源，只要有读者使用时就不允许任何一个写者使用。当一个写者使用时，不允许其它写者或读者使用。因此，可以将数据块访问的程序视为临界区。但是，数据块不是绝对的临界资源，因为它允许多个读者用户同时使用。这一问题是由Courtois等人提出了解决方案。首先，使用一个互斥信号量mutex，实现读者与写者、写者与写者之间的互斥。由于读者可以同时访问数据块，因此我们让第一个准备进入临界区的读者，通过P（mutex）强占临界资源，以便排斥写者访问。当最后一个读者离开临界区时，通过V（mutex）将临界资源释放，以便其它用户使用。其次，设计一个专为读者共享的变量counter，让它记录读数据块的人数。Counter应视为临界资源，应有一个互斥信号量，比如Rmutex。,23,程序结构如下：varmutex:Semaphore:=1,Rmutex:Semaphore:=1;varcounter:Integer:=0;ParbeginWriter(i)；Reader(j)；Parend.ProcedureWriter(i)Beginwhile(true)Begincaculate_an_data();/计算一个数据P(mutex);Write_the_data();/临界区V(mutex);End;End；,24,ProcessReader(j)BeginWhile(true)BeginP(Rmutex);Ifcounter=0thenP(mutex);counter=counter+1;V(Rmutex);Read_operation();/临界区P(Rmutex);Ifcounter=1thenV(mutex);counter=counter-1;V(Rmutex);End;End;,25,哲学家用餐问题,在该问题中设想有5位哲学家，他们共同坐在一张餐桌前用餐，用餐过后开始思考问题。他们的生活方式可描述为一个单调的循环：思考-饥饿-用餐-再思考。已知餐桌上摆的是面条，每个人必须左右手各拿到一把叉子才可以开始进餐。而餐桌上只有5把叉子，任两个哲学家之间有一把，见图所示。,26,第i位哲学家的行为过程可描述为下面的形式。ProcessPhilosopher(i)BeginWhile(true)BeginThinking();P(mutexi);/请求左叉子P(mutexi+1mod5);/请求右叉子Eating();/用餐过程V(mutexi);/释放左叉子V(mutexi+1mod5);/释放右叉子End;End;,27,4.4.3信号量集机制,该机制可分为两类：AND型信号量集机制和一般型信号量集机制。一、AND型信号量集机制这种机制中，让P原语具有同时给多个信号量减1的功能。不过，它要先判断各个信号量是否都是“绿灯”。若是，则将各个信号量的值减1，立即进入临界区。若其中至少有一个信号量是“红灯”，进程就要让权等待。并将P原语的第1条指令作为断点地址，保存到该进程的PCB（信息保护区）中，等恢复运行时重执P原语。二、一般型信号量集机制我们为每一种临界资源设一个记录型信号量Si，并让Si的值域表示当前的可用资源数量。当一个进程根据需要，一次性地请求Si类型的资源di台时，可让它的P原语作Si=Si-di操作。,28,3种信号量机制进行比较,整型信号量机制比较简单，适用面较窄记录型信号量机制较为灵活，可用于多种同步场合信号量集机制能够简化应用程序的设计，但系统的开销较大,29,4.5管程,这是一种具有面向对象程序设计思想的同步机制。它提供了与信号量机制相同的功能。管程（Monitor）概念是著名学者Hore于1974年提出的，并在很多系统中得到实现，诸如Pascal、Java、Modula-3等。管程是由局部数据结构、多个处理过程和一套初始化代码组成的模块。管程的特征为：（1）管程内的数据结构只能被管程内的过程访问，任何外部访问都是不允许的；（2）进程可通过调用管程的一个过程进入管程；（3）任何时间只允许一个进程进入管程，其他要求进入管程的进程统统被阻塞到等待管程的队列上。,30,下图是管程的一个结构模型,31,lP（c）：当遇到同步约束，就将进程阻塞在条件变量c关联的等待队列上。lV（c）：从条件变量c关联的等待队列上唤醒一个进程，让它恢复运行。若队列上没有进程在等待，就什么也不做。管程的语言结构可描述为下属形式：Type管程名=MonitorBegin数据结构定义；局部变量定义；条件变量定义；Porcedure过程名（形式参数）Begin/过程体End;End;,32,利用管程PC解决生产者-消费者问题的算法如下。ProcedureProducer()BeginVarchar:x;While(true)BeginProduce_an_item_in_x();PUT(x);End;End;,ProcedureConsumer()BeginVarchar:x;While(true)BeginGET(x);Consume_the_item_in_x();EndEnd;,33,4.6进程通信,4.1.1共享存储器系统这种通信需要在内存中开辟一个共享的存储空间，供进程之间进行数据传递。比如计算进程将所得的结果送入内存共享区的缓冲区环中，打印进程从中将结果取出来，就是一个利用共享存储器进行通信的例子。这种通信方式在UNIX、Linux、Windows及OS/2等系统中都有具体的实现。共享存储器系统中，共享的空间一般应当是需要互斥访问的临界资源。诸多进程为了避免丢失数据或重复取数，需要执行特定的同步协议。在利用共享存储器进行通信之前，信息的发送者和接收者都要将共享空间纳入到自己的虚地址空间中，让它们都能访问该区域。存储器管理模块将共享空间映射成实际的内存空间。,34,（1）创建或删除共享存储区（2）共享存储区的附接与断接（3）共享存储区状态查询（4）共享存储区管理共享存储器系统的特点：利用共享存储器系统进行通信的效率特别高，适用于通信速度要求特别高的场合。这种同步与互斥机制的实现一般要由程序员来承担，系统仅仅提供一个共享内存空间的管理机制。,35,4.6.2管道通信,管道（Pipe）是可供进程共享的一种外存文件，主要用于连接一个写入进程和一个读出进程，以实现它们之间的数据通信。写入进程按字符流的形式将数据写入管道文件中，让读出进程从中获得数据。由于管道机制特别适用于大容量数据的通信，因此在许多操作系统中被采用。管道通信机制中的协调内容包括：（1）互斥问题。（2）同步问题（3）状态测试管道通信机制分为无名管道和有名管道,36,4.6.3消息传递,系统中的进程在交互传送数据时，涉及到对数据结构的互斥使用问题。为实施互斥，进程之间需要同步。提供这写功能的一个好方法是消息传递。还有一个优点是，消息传递可较容易地在单处理机系统、分布式系统、共享存储器的多处理机系统中实现。消息传递中的管理机制由操作系统提供，主要体现为以下两个原语。发送原语：send(destination,message)，其中，destination为消息的目的地（接收进程名）。该原语表示发送消息到进程destination。接收原语：receive(source,message)，其中，source是消息发出地（发送进程名）。该原语表示从进程source接收消息。,37,一、实现同步的方法,在这种方式中要解决的关键问题仍然是同步问题：仅当一条消息从某个进程发送后，其他进程才可能接收到消息。那么，消息发送者通过send原语发出一条消息后，应当如何处理呢？有两种选择：要么将发送进程阻塞起来，直到消息被接收为止，再把它唤醒；要么不阻塞发送进程。同样地，消息接收者通过receive原语要接收一条消息时，如果能立即收到，可继续运行。如果消息尚未发出的话，也有两种选择：要么阻塞发送进程等待消息；要么不阻塞发送进程，放弃接收。这样一来，系统可选择的处理有以下几种：会合（renezvous）方式宽松同步方式不阻塞发送者，只阻塞接收者方式,38,二、直接通信和间接通信,在消息传递中，发送者需要明确消息发往哪里，接收者需要指明消息的来源。通常，按send和receive原语的实现方式可分为直接寻址和间接寻址两类。1.直接寻址（DirectAddressing）实现直接寻址的一个较为简单的方案是，让send原语明确指出接收者的进程号，receive原语明确指出发送者的进程号，系统根据这两个原语实现直接通信。这种一对一的通信，用来处理并发进程之间的合作是相当有效的。2.间接寻址（IndirectAddressing）在间接寻址方式中，消息并不直接从发送进程传到接收进程，而是要经过一个中间介质临时保存消息的队列，通常称为“信箱”。因此，两个通信进程的操作是，一个进程将消息发到信箱中，另一个从信箱中取消息。,39,4.7死锁,死锁（DeadLock），是指系统中存在一组进程，其中每一个进程都在等待组内别的进程占有的资源，这样一来，该组进程都不能向前推进，陷入等待状态。系统死锁,是系统中n（n1）个进程因资源请求得不到满足，皆无法运行而出现的一种无限期等待现象。这是一种极其浪费的现象，它给系统带来的损失有时比出现某些硬件故障还要大。如果不给予有效地制止，这种状态将永远不能结束。,40,4.7.1产生死锁的原因,当系统同时满足以下4个必要条件时，会产生死锁。(1)互斥条件。进程请求的资源属于临界资源，每一瞬间只能由一个进程使用。若有多个进程同时请求使用同一个临界资源时，只能允许一个使用，其它进程等待。(2)不剥夺条件。进程获得某资源后，便一直占有它，直到用完为止才可以释放。其它进程不可以剥夺某个进程已占有的资源，即使该进程目前无法运行。(3)请求和保持条件。允许一个进程在保持已有资源不放弃的情况下，进一步请求新资源，当请求资源得不到满足而被阻塞时，也不会释放已占有的资源。(4)环路条件。一组进程P1,Pn的占有资源情况与请求资源情况构成了一个环型链，比如P1等待P2的资源，P2等待P3的资源Pn等待P1的资源。,41,定义：资源分配图G=是一个有向图，N是结点集，E是边集。其中：N=PR，P为进程集，R为资源集。E=E1E2，E1为资源占有边集，E2为资源请求边集。我们用圆圈表示进程pP、矩形表示资源rR，同时，用rp表示资源r被进程p占有，pr表示进程p请求资源r。那么两个进程P1和P2竞争资源R1和R2，及P1、P2和P3竞争R1、R2和R3的环路如图所示。,42,4.7.2死锁预防,预防死锁的主要工作就是使系统一直保持在安全状态下运行。预防措施可从死锁的4个必要条件去考虑。1资源静态分配方案2.资源可剥夺方案3.资源有序使用方案,43,4.7.3死锁避免,一、安全状态为了研究如何避免死锁，我们先来看一下系统的状态变化情况。比如，有两个进程P1和P2竞争资源R1和R2，如图。,44,二、银行家算法,该算法需要建立多种