第4章进程同步与通信1

1、第第4章章 进程的同步与通信进程的同步与通信n进程的同步(synchronism)问题，是操作系统的关键问题之一，这个问题解决不好，就有可能导致同一程序运行结果不确定这种不能容忍的错误，关系到操作系统的成败，因此必须认真解决。通信(communication)，指的是处于同一系统的进程之间的信息交换，它也是操作息统必不可少的功能之一。这两个内容有一定的联系，因为从某种意义上讲，同步也是进程间的一种通信，故这两个内容放在同一章讲述。4.1. 互斥与互斥与同步的基本概念同步的基本概念n互斥与同步是同一问题的两个侧面，同步，最基本的含义是相互协调，步伐一致，从这个意义上讲，互斥也是一种同步。n互斥互

2、斥(mutual exclusion)：所谓互斥指的是多个进程之间相互排斥地使用临界资源(CR:Critical Resource)这样一种相互制约关系。而临界资源，就是一次只允许一个进程使用的资源，也就是说，在一个进程未使用完之前，另一个进程不得开始使用。输入机、打印机、磁带机等，是“硬”临界资源的例子；而多个进程共用的数据、表格、队列等则是“软”临界资源的例子。这些资源为什么要互斥使用呢？因为不互斥使用就会出现错误。譬如说打印机，如果不互斥使用，则有可能将两个或多个进程的结果打在同一张纸上，如何区分呢!n再看书上再看书上P55-56经典的关于软临介资源也必须互斥使用的例子经典的关于软临介资

3、源也必须互斥使用的例子。临界区和同类临介区临界区和同类临介区n在上面的举例中，涉及到临界区(CS:Critical Section)和同类临界区的概念。临界区临界区是使用临界资源的程序段，而同类临界区同类临界区是涉及到同一个临界资源的若干个程序段。同类临界区，作为程序不一定是相同的，作为进程程序的一部分也不一定属于同一进程。有了同类临界区的概念后，在实践上互斥使用临界资源的方法是:多个进程之间互斥地进入各自的同多个进程之间互斥地进入各自的同类临界区。类临界区。同步同步(Synchronism)n如上所说，一般意义上的同步，指的是相互协调、步伐一致的关系。这里所说的进程之间的同步，包含有两层意思

4、，一是指有协作关系的若干个进程要协调它们之间的相对速度，二是指有数据相关的若干个进程要正确地确定它们之间的执行顺序。对第一种同步，看书上P56的举例。CP缓冲区进程之间相互协调的举例4.2 解互斥问题的算法解互斥问题的算法n解互斥问题的算法，就是进程之间互斥地进入的同类临界区的算法。正确的解互斥问题的算法要符合以下五条准则: (1) 空闲让进； (2) 忙则等待； (3) 有限等待； (4) 让权等待； (5) 驻留有限。 在这五条里面，最重要的是两条，就是”空闲让进”和”互斥进入”，其它的准则可以由其它机制来实现。算法表示的约定算法表示的约定n首先，用如下所示的方式表示两(多)进程的并发执行

5、：void main（） 公共变量说明； cobegin p0（）； p1（）； coend 接上屏接上屏 其次，用如下的方式表示一个进程进入和退出自己的临介区：void p（int i） while（true） entry code critical section； exit code non-critical section； 错误的和正确的算法错误的和正确的算法n下面给出四个解互斥问题的算法，其中前三个是有这样那样缺陷的，是不完全正确的，第四个是正确的算法。通过这些算法，可以使我们了解人们探索正确算法的过程，也可以在比较中知道错误的为什么错误，正确的为什么正确，以加深对这些算法的理解。

6、不失一般性，这些算法只考虑两个进程(Pi，Pj)的情况，它们很容易推广到多个进程的环境下。算法算法1 void p(int i) while （true） while （turn!i） ； critical section ； turnj ； non-critical section； 该算法的问题是:空闲不让进。例如，当turn=i 时，Pi不想进，这时临介区是空闲的，但Pj不能进。问题就在于，turn值的修改是在进入临介区之后进行。算法2void p(int i) while (true) while (flagj) ； flagitrue； critical section ； flag

7、ifalse ； non-critical section； 该算法的问题是：有可能两个进程同时进入临介区，从而违背了互斥进入的原则。算法3void p(int i) while (true) flagitrue； while (flagj) ； critical section； flagifalse； non-critical section； 该算法的问题是：有可能出现两个都不能进且相互等待的死锁局面。算法4的描述void p(int i) while （true） flagitrue； turn1； while （flagj &（ turn = = j）； critical secti

8、on ； flagifalse ； non-critical section； 要证明该算法的正确性，只要证明两点:空闲让进，互斥进入。4.3 同步与互斥的基本工具同步与互斥的基本工具 -信号量和信号量和P、V操作操作n从上面介绍的几个解互斥问题的算法可以看出，要设计一个正确的算法是不容易的。为了更方便和规范地解同步互斥问题，在总结了各种成果的基础上，Dijkstra于1965年给出了解这一问题的一种工具，即信号灯及其P、V操作。n信号灯信号灯(semaphore)，也叫信号量，是一种记录型数据结构，由信号量的值和信号量的指针量部分组成，如下所示。S.ValueS.pointor；信号量的值，

9、整数；在此信号量上等待的进程队列的队首指针；P、V操作操作n在信号量上只能执行两种操作，即P操作(又称为wait操作)和V操作(又称为signal操作)，这两种操作的定义见P61的说明。n关于P、V操作有两点值得注意，一是执行P(S)操作出现进程阻塞(睡眠)时，被阻塞的进程是调用P(S)的进程，而执行V(S)操作有进程被唤醒时，被唤醒的进程不是调用V(S)的进程，而是在S上睡眠的进程；二是P、V操作是在封中断的情况下执行的，这就保证了在同一信号量上的P、V操作是互斥进行的。这种在执行时不可中断的操作叫”原语操作”，简称”原语”(primitive)。使用信号量和使用信号量和P、V操作解互斥问题

10、操作解互斥问题n有了信号量和P、V操作这一工具，解互斥问题变得 十分简单，其方法是: 1，对与一个临界资源有关的所有同类临介区设置一个互斥信号量(mutex)，置初值为1； 2，在每个同类临介区的前、后分别插入在该信号上的P、V操作，如P62所示；n这一解互斥问题的方案之所以正确，是因为它能确保多个进程互斥地进入各自的同类临介区(解释)。使用信号量和使用信号量和P、V操作解同步问题操作解同步问题n比较而言，使用信号量和P、V操作解同步问题比解互斥问题要难得多，因为它的解法要具体问题具体分析，不像解互斥问题那样简单规范。前已说过，进程同步问题有两种类型，一是协调进程之间的相对运行速度，二是基于进

11、程间的数据相关关系正确地确定进程执行的先后顺序。这两类同步问题都要根据具体情况来求解：设几个信号量？每个信号量的初值是多少？P、V操作如何插入？等等，都要认真地设计。协调进程间相对速度的同步问题协调进程间相对速度的同步问题n还是以前面讲到过的计算进程和打印进程之间的相互关系为例。CP缓冲区 计算进程和打印进程之间的相互制约关系是：仅当计算进程(C)产生了计算结果并送入缓冲区后，打印进程(P)才能运行，打印结果；仅当本次缓冲区的结果打印完后，才能送下一个结果。其解法如右。semaphore synch1=0; synch2=1;cobegin Pc: while(true) : p(synch2

12、); input(buffer); V(synch1); : Pp: while(true) : p(synch1); print(buffer); V(synch2); : coend确定进程之间执行顺序的同步问题确定进程之间执行顺序的同步问题semaphore a=b=c=d=e=f=g=0;cobegin P1: .prog1;V(a);V(b);. p2: .P(a);prog2;V(c);V(d);. p3: .P(b);prog3;V(e);. p4: .P(c);prog4;V(f); . p5: .P(d);prog5;V(g);. p6: .P(f);P(g);P(e);pr

13、og6;.coend prog1 prog2 prog6prog4 prog3prog5abcdfeg4.4 经典的互斥、同步问题经典的互斥、同步问题n本节讨论几个经典的互斥、同步问题及其解法。这些问题都是操作系统中实际的同步、互斥问题的抽象模型，深入地分析和透彻地理解这些问题的解法，对于全面解决操作系统的同步问题有重要的指导意义。这些问题是: 1，生产者消费者问题； 2，读者写者问题； 3，哲学家进餐问题。4.4.1. 生产者生产者消费者问题消费者问题 (PCP:ProducerConsumer Program)n生产者消费者问题是最著名的进程同步问题，它描述了一组生产者进程向一组消费者进程

14、提供产品的产、消关系。它们共享一个由n个缓冲区组成的有界缓冲池，每个缓冲区可以存放一个产品，生产者进程不断生产产品并将产品放入缓冲池中，消费者进程不断从缓冲池内取出产品并消费；n这是一个既有互斥问题又有同步问题的模型，互斥存在于所有进程之间，其临界资源是有界缓冲池；同步存在于生产者和消费者两类进程之间；生产者生产者消费者问题示意图消费者问题示意图n生产者消费者问题如下图所示 ：p0p1p2pk-1c0c1c2cm-1 0 1 2 3 4 5有界缓冲池生产者消费者问题示意图生产者生产者-消费者问题的解消费者问题的解 生产一个产品； p(empty)； p(mutex)； 将一个产品送入缓冲池的某

15、个缓冲区； v(mutex)； v(full)； p(full)； p(mutex)； 从缓冲池的某个缓 冲区中取一个产品； v(mutex)； v(empty)； 消费一个产品；具体的程序见P64说明说明n此解中设置了三个信号量，mutex=1是互斥信号量，empty=0，full=n是同步信号量(也叫资源信号量)；nin=(in+1) % n操作实际是对n取模；n若生产者进程因执行P(empty)操作在empty上睡眠，要由消费者进程的V(empty)操作唤醒；若消费者进程因执行P(full)操作在full上睡眠，要由生产者进程的V(full)操作唤醒；n资源信号量和互斥信号量上的两个P操

16、作不能互换，否则有可能出现死锁。(解释解释)4.4.2. 读者读者写者问题写者问题(RWP:ReaderWriter Problem)n读者写者问题是一个基于使用方式的不同对某一共享对象要么可以同时使用要么必须互斥使用的问题。这里的共享对象是数据文件；n对磁盘上的共享文件，有的进程要求读而有的进程要求写，我们把只要求读的进程称之为“读者”，而把其它进程称之为“写者”；n读者写者问题就是：多个读者进程可以“同时”读一个文件，但写者进程对文件的使用必须互斥进行；n有两种类型的读者写者问题：即读者优先的读者写者问题(第一类读者写者问题)和写者优先的读者写者问题(第二类读者写者问题)，它们的区别在于：

17、当写者提出使用要求后，是否还允许新的读者进来?读者读者写者问题的图示写者问题的图示reader0reader1reader2readern-1writerj共享文件读者读者写者问题的解写者问题的解n为解决读者-写者问题，应设置两个信号量和一个共享变量：n互斥信号量mutex，用于使读者进程互斥地访问共享变量readcount，初值为1；n写互斥信号量wrt，用于实现一个写者进程与其它进程的互斥，初值为1；n共享变量readcount，用于记录当前同时进入的读者进程数，初值为0。读者读者写者问题的解写者问题的解 Readeri: p(mutex)； readcount+； if (readcou

18、nt=1) p(wrt)； v(mutex)； 执行读操作； p(mutex) ； readcount - -； if (readcount=0) v(wrt)； v(mutex)；Writerj:P(wrt)；执行写操作；V(wrt)；讨论：讨论：1，为什么要互斥使用 readcount?2，此解允许多个读者 同时进入吗?3，此解能使写者互斥吗?4，此解是第几类RWP的解?5，解读P67的一段话；4。4。3 哲学家进餐问题哲学家进餐问题n哲学家进餐问题是对多个进程竞争使用系统有限资源的一种抽象和比喻。其描述是：有五个哲学家，他们的生活方式是交替地进行思考和进餐；他们共用一张圆桌，分别坐在周围

19、的五把椅子上，在圆桌上有五个碗和五支筷子；平时哲学家进行思考，饥饿时便试图取其左、右两边的筷子，只有在他拿到两支筷子时才能进餐；进餐完毕，放下筷子又继续思考。哲学家进餐问题的解哲学家进餐问题的解 philosopheri: while (true) p(sticki)； p(stick(i+1) % 5)； 进餐； v(sticki)； v(stick(i+1) % 5)； 思考； 此解的问题是可能会产生死锁：当五个哲学家同时拿起其左边的筷子时，就造成了一种无限等待的局面。为避免这种死锁有三种解决办法：1，至多允许4个哲学家同 时坐在桌子的周围；2，仅当一个哲学家左右两 边的筷子同时可用时才

20、允许其拿起筷子；3，将哲学家编号，然后规 定，奇数号哲学家先拿 起左边的筷子，偶数号 哲学家先拿起右边的筷 子。4.5 管程（管程（monitor）机制）机制n5。4。1 管程的引入管程的引入 管程(monitor)是并发程序设计语言的三大构件（进程(process) 管程(monitor)类程(class)）之一。之所以要引入管程，是为了将程序员从设计同步算法的负担中解放出来，并防止人为的算法设计错误（见P69），其基本思想是要把互斥进入同类临界区这一相互制约关系交由并发程序设计语言的编译系统来实现，这样既可减轻负担又可避免错误。n5。4。2 管程概念管程概念 什么是管程？从概念上讲，就是管

21、理一组共享数据的机制，它好像一堵围墙把共享数据围起来，只留一道门进出，且必须互斥进入，以达到互斥使用共享数据的目的；它也好像是一个“秘书”，每一个想使用共享数据的进程都必须得到该“秘书”的允许，而“秘书”的原则是，每次只允许一个进程使用。1973年，Hansan对管程所下的定义是：“一个管程定义了一个数据结构和在该结构上能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据”。从实际上说，管程就是同类临界区的集合体，而互斥进入该集合体中的临界区的控制机制不是由程序员去设计，而是由并发程序设计语言的编译系统自动生成。管程的组成管程的组成n一个管程在结构上由三部分组成：一个管程在结构上

22、由三部分组成： 1，一组共享数据，这些数据是对临界资源的抽象； 2，建立在该数据上的一组操作（函数或过程），相当于是若干个同类临界区； 3，对上述数据置初值的语句。一组共享数据一组操作初始化语句进入队列进入队列条件队列条件队列“进入队列进入队列”是在互斥信号量上排队等待的进程队列；“条件队列条件队列”是在资源信号量排队等待的进程队列；管程的语法管程的语法Monitor monitor _name； /*管程名*/variable declarations； /*共享变量说明*/void Entry P0(.) /*一组操作函数*/ void Entry P1(.) void Pn-1(.) initialization code; /*置初值语句*/ 管程的基本特性管程的基本特性n局部于管程的数据只能被局部于管程内的函数所访问；n一个进程只有通过调用管程内的函数才能进入管程访问共享数据；n每次仅允许一个进程在管程内执行某个函数；n由于管程是一个语言成分，所以管程的互斥访问完全由编译程序在编译时自动添加上，无需程序员关心，而且保证正确。条件变量条件变量n由于在管程内部没有了PV操作，为了实现进程间在资源信号量上的同步，在管程内增设了条件变量和在条件