第3章进程同步

第三章进程同步在以多道程序设计技术为基础的现代操作系统中，多个进程由于同时存在于内存中，竞争使用处理机等资源，因此它们之间必定会存在一定的相互依赖、相互制约性，进而产生了同步、互斥等关系；为此，操作系统在实现处理机管理时，必须设计一个专门的机制，来保证进程之间正确的同步与互斥。进程同步机制是操作系统中一个非常重要的内容。本章将结合一些经典的进程同步问题，重点讲述进程的同步、互斥关系，以及其在操作系统中的设计与实现方法。

第三章进程同步3.1进程同步的基本概念3.2实现进程互斥的基本方法3.3信号量机制3.4典型进程同步机制问题3.1进程同步的基本概念3.1.1进程之间的关系3.1.2临界资源与临界区3.1.3进程同步机制的准则3.1进程同步的基本概念3.1.1进程之间的关系直接与间接直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相关进程间间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相关进程之间，也可发生在无关进程之间从另一个角度来看进程间的相互关系，可以将进程之间的关系提炼为同步（synchronism）和互斥（mutex）两种。3.1.1进程之间的关系同步（synchronism）与互斥（mutex）同步是一种直接作用。是指系统中的多个进程之间存在某种时序关系，需要相互协作，才能共同完成一项任务。互斥是一种间接作用。当有若干进程都要使用某一共享资源时，最多允许一个进程使用，而其它要使用该资源的进程必须阻塞，直到占用该资源的进程释放了该资源为止。为此，操作系统必须提供一个机制，来管理进程之间的这两种相互作用；这一管理机制就是进程同步机制。它包括两个方面：一是进程之间同步关系的管理，另一是进程之间互斥关系的管理。换句话说，进程的同步与互斥都被统一纳入到进程同步机制的管理之下；这时，进程同步就是进程间的协作型同步，进程互斥就是进程间的互斥型同步。3.1.2临界资源与临界区临界资源（criticalresource）

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量P1:R1=count;

R1=R1+1;

count=R1;P2:R2=count;

R2=R2+1;

count=R2;P1和P2都各自对count做一次加1操作。其中，count是P1、P2的共享变量，R1、R2都是寄存器。3.1.2临界资源与临界区并发进程的程序结构3.1.3进程同步机制的准则（一）使用互斥区的原则-“空进忙等，不忙等不死等”空闲让进：当无进程处于临界区时，相应的临界资源处于空闲状态。这时，如果有一个进程申请使用该临界资源，则允许该进程进入自己的临界区、使用该临界资源。忙则等待：当已有进程处于临界区时，说明该进程正使用着相应的临界资源。这时，如果有其它进程试图进入自己的临界区，则它必须等待（阻塞），以保证临界资源的互斥使用。让权等待：对于等待进入临界区的进程而言，既然它目前不能进入自己的临界区，它必须立即释放处理机，以避免进程“忙等”（即占有处理机等待）而降低处理机的利用率。有限等待：对要求进入临界区的进程，应能让它在有限时间内进入，以免陷入"死等"（即等待时间过长）。3.1.3进程同步机制的准则（二）进程同步管理的准则为实现进程之间正确的协作型同步，要求系统保证相互协作的进程在执行次序上的正确性。也就是说，如果进程P1在条件C下，其执行必须先于进程P2；则为防止出现错误的执行次序，必须在系统中设置专门的管理机制来协调进程P1、P2之间正确的执行次序。这一管理机制应遵循下面的准则：（1）条件C不满足时，无需考虑P1、P2之间执行次序的协调；（2）条件C成立时，必须保证进程P1一定先于进程P2执行。3.2实现进程互斥的基本方法booleanturn; //进入临界区的进程标志//TRUE：P进入临界区//FALSE：Q进入临界区

P：……while(!turn);

临界区；turn=FALSE;……Q:……while(turn);

临界区;turn=TRUE;……基本思想：强制地让P和Q两个进程轮流进入各自的临界区，这样就完全可以保证进程在有限的时间内进入自己的临界区。为此，在算法中设置了一个变量turn。

缺点：这样强制轮转很容易造成资源利用不充分。例如，P进程退出临界区之后，如果又需要进入，但此时轮到Q访问临界区；这时，如果Q一直不想访问临界区，算法也不能将资源让给P，而必须等到Ｑ需要进入临界区后再退出时才能让P再次进入。显然这没有遵循“空闲让进”的原则。

3.3信号量机制信号量机制是在1965年由荷兰学者Dijkstra提出的，它是一种公认的卓有成效的进程同步机制。

信号量机制的基本原理是：多个进程可以通过简单的信号量进行某种形式的合作，一个进程可以被迫在某一时刻停止，直到它接收到一个特定的信号量。3.3信号量机制用信号量正确解决进程互斥、同步问题的关键包括：设置什么样的信号量？信号量最起码要反映对应临界资源当前的可用状态；提供哪些针对信号量的标准操作？这些操作将被进程所调用；如何正确调用上述的标准操作，使进程能够正确地互斥与同步？对应信号量机制的这些关键点，不同的信号量机制设置了不同的信号量类型（如互斥信号量、整型信号量、记录型信号量等），并设计了相应的标准操作（P、V）；当然，对所有信号量机制，它们实现进程正确互斥与同步的方法是一致的。其中，P、V分别是荷兰语的test(proberen)和increment(verhogen)。

3.3.1单信号量机制（一）单信号量互斥型信号量互斥型信号量也称作二元信号量或0/1信号量，它的值只能取0/1或FALSE/TRUE，描述出临界资源当前是否可用；其中取值为1或TRUE表示临界资源当前可用。互斥型信号量定义为：booleanbinary_semaphore;//互斥信号量定义3.3.1单信号量机制其对应的P、V操作可分别描述如下：voidP(booleanbinary_semaphore){while(!binary_semaphore);//若信号量为0，表示资源不可用，反复测试binary_semaphore=FALSE；//若信号量为1，表示有资源，则调用进程继续}voidV(booleanbinary_semaphore){binary_semaphore=TRUE；}整型信号量互斥信号量已经能够初步地表达临界资源的使用情况；但是对于多个进程并发的情况，采用整型信号量将具有更强的表达能力。对整型信号量S，其取值不仅能够表达临界资源是否空闲，还具有如下的物理意义：S>0：表示目前有S个资源可用；S=0：表示目前无资源可用，也没有等待此资源的进程；S<0：表示目前有|S|个进程在等待此资源。3.3.1单信号量机制P、V操作也将得到对应的物理意义：P(S)：表示申请一个资源；V(S)：表示释放一个资源。整型信号量S的初值应该大于等于0。

整型信号量可定义为：

intint_semaphore;//整型信号量定义3.3.1单信号量机制3.3.1单信号量机制整型信号量对应的P、V操作可描述如下：voidP(intint_semaphore){ int_semaphore--；

while(int_semaphore<=0)；/*若信号量小于等于0，表示无

资源，反复测试*/

}

voidV(intint_semaphore){ int_semaphore++；

}3.3.1单信号量机制注意：P、V操作为原语操作（primitiveoratomicaction）。原语是完成某种特定功能的一段程序，具有不可分割性或不可中断性；即原语的执行必须是连续的，在执行过程中不允许被中断，这可以通过屏蔽中断来实现。整型信号量的使用需要注意以下原则：1）必须置一次且只能置一次初值；2）初值不能为负数；3）只能执行P、V操作。如果进程之间互斥的临界资源只有一种，单信号量机制是合适的。而如果进程之间同时共享着多种临界资源，单信号量机制在实现相应的进程同步与互斥管理时就不太合适了（因为容易出现死锁）。这时，可以采用多信号量机制。3.3.2多信号量机制(略)3.4典型进程同步机制问题3.4.1生产者-消费者问题3.4.2读者-写者问题3.4.3哲学家就餐问题3.4典型进程同步机制问题3.4.1生产者-消费者问题生产者-消费者(Producer-Consumer)问题是最著名的进程同步机制问题。它描述了一组生产者P向一组消费者C提供消息，它们共享一个有界缓冲池B，生产者P向其中存入消息，消费者C从中取得消息。根据生产者、消费者、缓冲区的数目可以划分为：单生产者-单消费者-单缓冲区问题单生产者-单消费者-多缓冲区问题多生产者-多消费者-多缓冲区问题3.4.1生产者-消费者问题（二）单生产者-单消费者-多缓冲区问题3.4.1生产者-消费者问题其中的同步与互斥问题进程互斥问题同上一问题。缓冲区B是临界资源，进程P和C不能同时对缓冲区B进行操作，即P和C必须互斥进入各自的临界区进程同步问题进程P不能往“满”的缓冲区中放产品，进程C不能从“空”的缓冲区中取产品。即：当缓冲区为“满”时，进程C必须先于进程P执行；当缓冲区为“空”时，进程P必须先于进程C执行。但是，这里的缓冲区的大小为n，所以不方便使用简单的互斥型信号量来表示3.4.2读者-写者问题(略)3.4.3哲学家就餐问题3.4.3哲学家就餐问题哲学家竞争的资源筷子是哲学家进餐竞争的临界资源。5支筷子应分别用一个信号量描述，这5个信号量构成一个信号量组，初值分别为1，表示开始时5支筷子均可被申请使用且只能互斥使用3.4.3哲学家就餐问题假如5个哲学家同时感到饥饿而各自执行第一个P操作，申请并获得左手的一根筷子后，使5个信号量chopstick[i]均为0当他们继续各自执行第2个P操作申请拿右手筷子时，均因无筷子而阻塞等待。所有的5个哲学家将永远阻塞，因为没有哲学家能执行释放筷子的V操作，因此5个哲学家进程进入死锁状态。3.4.3哲学家就餐问题不会发生死锁的解法采取的措施最多允许4个哲学家同时坐在桌子周围就餐仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子给所有哲学家编号，偶数号的哲学家必须首先拿右边的筷子，奇数号的哲学家则反之3.5本章小结现