计算机操作系统第四章ppt课件

1、操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM第4章 并发与互斥 根本概念 互斥：软件方法 硬件方法 信号量机制 管程 死 锁 主主 要要 内内 容容操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.1 4.1 根本概念根本概念4.1.1 4.1.1 临界资源和临界区临界资源和临界区 临界资源临界资源Critical ResourcesCritical Resources：一种一次只：一种一次只能为一个进程效力的资源。能为一个进

2、程效力的资源。 临界区临界区Critical SectionCritical Section：进程中访问临界：进程中访问临界资源的程序。每个运用该资源的进程都要包含一资源的程序。每个运用该资源的进程都要包含一个临界区。个临界区。 操作系统在管理可控制资源分配与运用方面，操作系统在管理可控制资源分配与运用方面，该当保证进程对临界资源的访问满足以下该当保证进程对临界资源的访问满足以下3 3点：点： l l 互斥访问要求。互斥访问要求。 l l 不致于产生不致于产生“死锁。死锁。 l l 不能有不能有“饥饿进程。饥饿进程。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一

3、世纪计算机本科教育OPERATING SYSTERM4.1.2 4.1.2 互斥管理准那么互斥管理准那么 空闲让进：当没有进程在临界区时，任何需求进空闲让进：当没有进程在临界区时，任何需求进入临界区的进程都允许立刻进入。入临界区的进程都允许立刻进入。 忙那么等待：在共享同一对象的一切进程中，一忙那么等待：在共享同一对象的一切进程中，一次只能有一个进程进入临界区。其它要求进入临次只能有一个进程进入临界区。其它要求进入临界区的进程只能等待。界区的进程只能等待。 有限等待：任何一个进程经有限时间等待后都能有限等待：任何一个进程经有限时间等待后都能进入临界区，不允许出现进程死锁或饥饿的情况进入临界区，

4、不允许出现进程死锁或饥饿的情况发生。发生。 让权等待：当一个进程不能进入临界区时要立刻让权等待：当一个进程不能进入临界区时要立刻阻塞本人，释放处置机让其它进程运用，防止阻塞本人，释放处置机让其它进程运用，防止“忙忙等。等。 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.2 4.2 互斥：软件方法互斥：软件方法 第一次尝试 算法中设计了一个变量turn保管允许进入临界区的进程编号初值为1，表示进程1可以首先进入。当一个进程要求进入临界区时，先检查turn的值。假设turn保管的不是本人的进程编号就进展循环等待

5、；否那么进入临界区。访问完成后退出临界区，再将turn设置为对方的进程编号。 第二次尝试 算法中定义了一个标志数组flag。当flagi=true，表示进程i正在临界区。初始时Flag的各分量值皆为false，表示尚无进程进入。当一个进程要求进入临界区时，先检查能否有进程已进入。假设有进程进入，就循环等待；否那么，设置本人的标志为真，立刻进入。访问完成后再将本人的标志设为假。4.2.1 Dekker4.2.1 Dekker方法方法操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM算法如下：Process P (1)

6、 Process P (2)Begin begin While (Flag2) do skip; While (Flag1) do skip;Flag1 = true; Flag2 = true;Critical section; Critical section;Flag1 = false; Flag2 = false; end. end.操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM第三次尝试第三次尝试 在第二次尝试的根底上，将其中的两个语句顺序交换，构成了新的算法如下： Process P (1) Pro

7、cess P (2) Begin begin Flag1 = true; Flag2 = true; While (Flag2) do skip;While (Flag1) do skip; Critical section; Critical section; Flag1 = false; Flag2 = false; end. end.操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM 第四次尝试 这是一个“礼让为先的算法，每个进程设置好本人的flag标志，阐明希望进入临界区。但也预备重置flag，以表示谦让。

8、算法如下： Process P (1) Process P (2)Begin begin Flag1 = true; Flag2 = true;While (Flag2) do While (Flag1) do flag1=false; flag2=false; flag1=true; flag2=true;Critical section; Critical section;Flag1 = false; Flag2 = false; end. end.操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM 正确的算法

9、正确的算法 为了防止过度互斥礼让的问题，Dekker运用第一种尝试中的轮盘变量turn，表示哪个进程有权进入临界区。让它在两个进程的活动中规定一个强迫性的顺序。算法如下：Process P (1) Process P (2)Begin begin Flag1 = true; Flag2 = true;While (Flag2) do While (Flag1) do if (turn=2) if (turn=1)flag1=false;flag2=false; while (turn=2) do skip; while (turn=1) do skip; flag1=true; flag2=t

10、rue;Critical section; Critical section;turn=2; turn=1;Flag1 = false; Flag2 = false; end. end.操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.2.2 Peterson4.2.2 Peterson算法算法 变量turn用来保管进程的编号，当turn=i，表示进程i有权进入临界区。数组flag表示哪个进程进入了临界区，Flagi=true，表示进程i已进入。初始时，标志数组flag的各元素值皆为false，表示无进程进入临

11、界区。变量turn可以不设初始值。下面是该算法的主要部分：Process P (1) Process P (2)Begin begin Flag1 = true; Flag2 = true;turn=2; turn=1;While (Flag2turn=2) While (Flag1 turn=1) do skip; do skip;Critical section; Critical section;Flag1 = false; Flag2 = false; end. end操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING S

12、YSTERM4.3 4.3 硬件方法硬件方法4.3.1 4.3.1 交换指令交换指令 将两个指定位置上的数据进展交换，是该指令将两个指定位置上的数据进展交换，是该指令实现的操作。微型机实现的操作。微型机PCPC上对应的指令格式是上对应的指令格式是XCHG XCHG op1op1，op2op2，用于交换两个操作对象的值其中，用于交换两个操作对象的值其中，opiopi是操作对象。是操作对象。 交换指令的功能可描画为下面的过程：交换指令的功能可描画为下面的过程： Procedure XCHG(op1,op2)Procedure XCHG(op1,op2)BeginBeginBoolean temp;

13、Boolean temp;temp = op1;temp = op1;op1 = op2;op1 = op2;op2 = temp;op2 = temp;End End 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.3.2 4.3.2 测试与设置指令测试与设置指令 该指令将形状测试和形状设置集于一条指令中，构成一个原子操作。也就是说，两个操作的执行不受中断信号的干扰。下面将指令格式定义为TS，功能是，读出一个指定变量的值，同时将一个新值置入。 对于逻辑变量，比如lock，TS的测试和设置的功能可描画为下面的

14、函数： Function TS(lock)BeginTS = Lock;Lock = true;End 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM 下面的例子中定义的全局变量是下面的例子中定义的全局变量是mutexmutex，初始值为，初始值为falsefalse表示无人进入。表示无人进入。 利用利用TSTS指令实现的互斥机制描画如下。指令实现的互斥机制描画如下。 Procedure Process (i) Begin While (TSmutex) do skip; / 循环等待 Critical sec

15、tion; mutex = false; End.操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.4 4.4 信号量机制信号量机制 著名的计算机学者Dijkstra经过长期的操作系统研讨与设计，于1965年提出了一种同步机制信号量机制。该机制由一个称为信号量Semaphore，也译为“信号灯的特殊变量和两个被命名为P、V操作的原语组成。在广泛的运用中，该机制得到了迅速开展。 这一机制的根本原理是，为每个临界资源设置一个信号量，担任在多个进程之间转发互斥信息。当一个进程需求互斥运用某个临界资源时，可经过对信号量

16、的P操作，了解该资源的空闲情况。当它运用完该临界资源后，又可经过对相关信号量的V操作，让其它需求该资源的进程感知到它的离去。 假设一个资源被视为临界资源，就该当为它定义一个独立的信号量，对进程访问起“放行和“阻止作用，就像交通管理中每个路口设置的交通灯一样。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.4.1 4.4.1 整型信号量整型信号量整型信号量是Dijkstra最初提出的一种信号量，被定义为整型变量。其取值范围是0，1。其值等于1是放行形状也称作“绿灯，等于0为阻止形状也称作“红灯。整型信号量机制中

17、的P、V操作是两个小巧小巧的过程。它们是操作系统中提供的两个原语，其代码如下图。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM 利用整型信号量机制实现进程互斥访问临界资源时，需求为该资源设一个整型信号量，比如mutex。令其初始值为1，表示它的初始形状空闲。每个要求访问临界资源的进程都要在临界区的前面经过P操作来访问mutex，决议能否可以立刻进入临界区。此外，还要在临界区的后面运用V操作，声明运用终了。程序构造如下所示： process p ( i )beginP(mutex);Critical sectio

18、n;V(mutex);end;操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.4.2 4.4.2 记录型信号量记录型信号量 记录型信号量机制是在整型信号量机制的根底上开展起来的，它实现了“让权等待功能。一个记录型信号量包含两个分量：信号量的值、信号量的等待队列指针，描画如下：type semaphore = recordvalue: integer;*L: integer;end. 记录型信号量的取值范围是-N，+M。其值大于0时为放行形状也称作“绿灯形状，小于等于0时为阻止形状也称作“红灯形状。进程可经过执

19、行P操作来了解临界资源的形状，假设发现当前为阻止形状时，就将进程阻塞起来。颇像是交通管理系统中的汽车过路口排队等候一样。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM消费者消费者- -消费者问题消费者问题系统里有假设干个协作的进程，其中，nn0个消费者进程， mm0个消费者进程，以及由PP0个缓冲区组成的缓冲区环。任何一个消费者进程都可以将本人的产品存入环内的一个缓冲区中；任何一个消

20、费者可以将环内的一个产品取出。消费者源源不断地消费并存入产品；消费者周而复始地从环内取出产品并掉。假定运用的约束条件是：1) 当环中有空闲缓冲区时，允许任一消费者进程把它的产品存入。 (2) 当环中无空闲缓冲区时，那么试图将产品存入缓冲区环的任何消费者进程必需等待。 (3) 当环中尙有未取出的产品时，允许任一个消费者进程把其中的一个产品取出。4 当环中没有未取出的产品时，试图从该环内取出产品的任何消费者进程必需等待。 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM图中，左侧的进程P1Pn为消费者进程，右侧的S1

21、Sm为消费者进程。图中的缓冲区环内有8P=8个缓冲区，每个缓冲区可以存入一件产品。环上设有存入指针和读取指针，都按顺时针方向挪动。 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM消费者进程的同步控制程序描画为下述过程： Semaphore: mutex,Sin,Sout1,8,0; Integer: in,out0,0; Parbegin Producer( ); Consumer( ) Parend. Process Producer( ) Begin While (true) Begin Produce_a

22、n_Item()_in_NextP1;/计算一个数据 P(Sin); P(mutex); BufferinNextP1;/临界区 in(in+1) MOD 8; V(mutex); V(Sout);操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM EndEndProcess Consumer( ) Begin While (true) Begin P(Sout); P(mutex); NextP2Bufferout; / 临界区 out(out+1) MOD 8; V(mutex); V(Sin); Consum

23、e_an_Item()_in_NextP2; / 消费一个数据 EndEnd操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM 读者读者- -写者问题写者问题 有一个数据块被多个用户共享，其有一个数据块被多个用户共享，其中部分用户是读者，另一部分是写者。我中部分用户是读者，另一部分是写者。我们规定：读者对数据块是只读的，而且允们规定：读者对数据块是只读的，而且允许多个读者同时读；写者对数据块是只写许多个读者同时读；写者对数据块是只写的，当一个写者正在向数据块写信息的时的，当一个写者正在向数据块写信息的时候，不允许其

24、他用户运用，无论是读还是候，不允许其他用户运用，无论是读还是写。写。 该问题中的数据块作为多个用户共该问题中的数据块作为多个用户共享的资源，只需有读者运用时就不允许任享的资源，只需有读者运用时就不允许任何一个写者运用。当一个写者运用时，不何一个写者运用。当一个写者运用时，不允许其它写者或读者运用。因此，可以将允许其它写者或读者运用。因此，可以将数据块访问的程序视为临界区。但是，数数据块访问的程序视为临界区。但是，数据块不是绝对的临界资源，由于它允许多据块不是绝对的临界资源，由于它允许多个读者用户同时运用。个读者用户同时运用。 这一问题是由这一问题是由CourtoisCourtois等人提出理等

25、人提出理处理方案。首先，运用一个互斥信号量处理方案。首先，运用一个互斥信号量mutexmutex，实现读者与写者、写者与写者之间，实现读者与写者、写者与写者之间的互斥。由于读者可以同时访问数据块，的互斥。由于读者可以同时访问数据块，因此我们让第一个预备进入临界区的读者，因此我们让第一个预备进入临界区的读者，经过经过P Pmutexmutex侵占临界资源，以便排斥侵占临界资源，以便排斥写者访问。当最后一个读者分开临界区时，写者访问。当最后一个读者分开临界区时，经过经过V Vmutexmutex将临界资源释放，以便其将临界资源释放，以便其它用户运用。它用户运用。 其次，设计一个专为读者共享的变其次

26、，设计一个专为读者共享的变量量countercounter，让它记录读数据块的人数。，让它记录读数据块的人数。CounterCounter应视为临界资源，应有一个互斥信应视为临界资源，应有一个互斥信号量，比如号量，比如RmutexRmutex。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM程序构造如下：程序构造如下： var mutex: Semaphore := 1, Rmutex: Semaphore : var mutex: Semaphore := 1, Rmutex: Semaphore : = 1;

27、= 1; var counter: Integer := 0 ; var counter: Integer := 0 ; Parbegin Writer(i) Parbegin Writer(i)；Reader(j)Reader(j)； Parend.Parend. Procedure Writer(i) Procedure Writer(i) Begin Begin while (true) while (true) Begin Begin caculate_an_data(); caculate_an_data();/计算一个数据计算一个数据 P(mutex);P(mutex); Writ

28、e_the_data(); Write_the_data();/临界区临界区 V(mutex);V(mutex); End; End; End End；操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERMProcess Reader(j) Begin While (true) Begin P(Rmutex); If counter=0 then P(mutex); counter = counter+1; V(Rmutex); Read_operation();/临界区 P(Rmutex); If counter=1

29、 then V(mutex); counter = counter-1; V(Rmutex); End;End;操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM哲学家用餐问题哲学家用餐问题 在该问题中想象有5位哲学家，他们共同坐在一张餐桌前用餐，用餐过后开场思索问题。他们的生活方式可描画为一个单调的循环：思索-饥饿-用餐-再思索。知餐桌上摆的是面条，每个人必需左右手各拿到一把叉子才可以开场进餐。而餐桌上只需5把叉子，任两个哲学家之间有一把，见图所示。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统

30、操作系统二十一世纪计算机本科教育OPERATING SYSTERM第i位哲学家的行为过程可描画为下面的方式。 Process Philosopher ( i ) Begin While (true) Begin Thinking( ); P(mutexi);/恳求左叉子 P(mutexi+1 mod 5); /恳求右叉子 E a t i n g ( ) ; /用餐过程 V(mutexi); /释放左叉子 V(mutexi+1 mod 5);/释放右叉子 End; End;操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYST

31、ERM4.4.3 4.4.3 信号量集机制信号量集机制该机制可分为两类：AND型信号量集机制和普通型信号量集机制。 一、AND型信号量集机制这种机制中，让P原语具有同时给多个信号量减1的功能。不过，它要先判别各个信号量能否都是“绿灯。假设是，那么将各个信号量的值减1，立刻进入临界区。假设其中至少有一个信号量是“红灯，进程就要让权等待。并将P原语的第1条指令作为断点地址，保管到该进程的PCB信息维护区中，等恢复运转时重执P原语。 二、普通型信号量集机制 我们为每一种临界资源设一个记录型信号量Si，并让Si的值域表示当前的可用资源数量。当一个进程根据需求，一次性地恳求Si类型的资源di台时，可让它

32、的P原语作Si = Si - di 操作。 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM3种信号量机制进展比较 整型信号量机制比较简单，适用面较窄 记录型信号量机制较为灵敏，可用于多种同步场所 信号量集机制可以简化运用程序的设计，但系统的开销较大 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.5 4.5 管程管程 这是一种具有面向对象程序设计思想的同步机制。它提供了与信号量机制一样的功能。管程Monitor概念是著名学者H

33、ore于1974年提出的，并在很多系统中得到实现，诸如Pascal、Java、Modula-3等。 管程是由部分数据构造、多个处置过程和一套初始化代码组成的模块。 管程的特征为： 1管程内的数据构造只能被管程内的过程访问，任何外部访问都是不允许的； 2进程可经过调用管程的一个过程进入管程； 3任何时间只允许一个进程进入管程，其他要求进入管程的进程统统被阻塞到等待管程的队列上。 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM以下图是管程的一个构造模型操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统

34、操作系统二十一世纪计算机本科教育OPERATING SYSTERMl Pc：当遇到同步约束，就将进程阻塞在条件变量c关联的等待队列上。l Vc：从条件变量c关联的等待队列上唤醒一个进程，让它恢复运转。假设队列上没有进程在等待，就什么也不做。管程的言语构造可描画为下属方式： Type 管程名 = Monitor Begin 数据构造定义； 部分变量定义； 条件变量定义； Porcedure 过程名方式参数 Begin / 过程体 End; End;操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM利用管程PC处理消费

35、者-消费者问题的算法如下。Procedure Producer() Begin Var char: x; While (true) Begin Produce_an_item_in_x(); PUT(x); End; End;Procedure Consumer() Begin Var char: x; While (true) Begin GET(x); Consume_the_item_in_x(); End End;操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.6 4.6 进程通讯进程通讯4.1.1

36、4.1.1 共享存储器系统共享存储器系统 这种通讯需求在内存中开辟一个共享的存储空这种通讯需求在内存中开辟一个共享的存储空间，供进程之间进展数据传送。比如计算进程将间，供进程之间进展数据传送。比如计算进程将所得的结果送入内存共享区的缓冲区环中，打印所得的结果送入内存共享区的缓冲区环中，打印进程从中将结果取出来，就是一个利用共享存储进程从中将结果取出来，就是一个利用共享存储器进展通讯的例子。这种通讯方式在器进展通讯的例子。这种通讯方式在UNIXUNIX、LinuxLinux、WindowsWindows及及OS/2OS/2等系统中都有详细的实现。等系统中都有详细的实现。 共享存储器系统中，共享的

37、空间普通该当是共享存储器系统中，共享的空间普通该当是需求互斥访问的临界资源。诸多进程为了防止丧需求互斥访问的临界资源。诸多进程为了防止丧失数据或反复取数，需求执行特定的同步协议。失数据或反复取数，需求执行特定的同步协议。 在利用共享存储器进展通讯之前，信息的发在利用共享存储器进展通讯之前，信息的发送者和接纳者都要将共享空间纳入到本人的虚地送者和接纳者都要将共享空间纳入到本人的虚地址空间中，让它们都能访问该区域。存储器管理址空间中，让它们都能访问该区域。存储器管理模块将共享空间映射成实践的内存空间。模块将共享空间映射成实践的内存空间。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统

38、 操作系统二十一世纪计算机本科教育OPERATING SYSTERM1创建或删除共享存储区2共享存储区的附接与断接 3共享存储区形状查询 4共享存储区管理 共享存储器系统的特点： 利用共享存储器系统进展通讯的效率特别高，适用于通讯速度要求特别高的场所。 这种同步与互斥机制的实现普通要由程序员来承当，系统仅仅提供一个共享内存空间的管理机制。 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.6.2 管道通讯 管道Pipe是可供进程共享的一种外存文件，主要用于衔接一个写入进程和一个读出进程，以实现它们之间的数据通讯

39、。写入进程按字符流的方式将数据写入管道文件中，让读出进程从中获得数据。由于管道机制特别适用于大容量数据的通讯，因此在许多操作系统中被采用。管道通讯机制中的协调内容包括： 1互斥问题。 2同步问题 3形状测试 管道通讯机制分为无名管道和有名管道 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.6.3 4.6.3 音讯传送音讯传送 系统中的进程在交互传送数据时，涉及到对数据构造的互斥运用问题。为实施互斥，进程之间需求同步。提供这写功能的一个好方法是音讯传送。还有一个优点是，音讯传送可较容易地在单处置机系统、分布式

40、系统、共享存储器的多处置机系统中实现。 音讯传送中的管理机制由操作系统提供，主要表达为以下两个原语。 发送原语：send(destination, message)，其中，destination为音讯的目的地接纳进程名。该原语表示发送音讯到进程destination。 接纳原语：receive(source, message)，其中，source是音讯发出地发送进程名。该原语表示从进程source接纳音讯。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM一、实现同步的方法一、实现同步的方法 在这种方式中要处理的关

41、键问题依然是同步问题：仅当一条音讯从某个进程发送后，其他进程才能够接纳到音讯。那么，音讯发送者经过send原语发出一条音讯后，该当如何处置呢？有两种选择：要么将发送进程阻塞起来，直到音讯被接纳为止，再把它唤醒；要么不阻塞发送进程。 同样地，音讯接纳者经过receive原语要接纳一条音讯时，假设能立刻收到，可继续运转。假设音讯尚未发出的话，也有两种选择：要么阻塞发送进程等待音讯；要么不阻塞发送进程，放弃接纳。 这样一来，系统可选择的处置有以下几种： 会合renezvous方式 宽松同步方式 不阻塞发送者，只阻塞接纳者方式 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二

42、十一世纪计算机本科教育OPERATING SYSTERM二、直接通讯和间接通讯二、直接通讯和间接通讯 在音讯传送中，发送者需求明确音讯发往哪里，接纳者需求指明音讯的来源。通常，按send和receive原语的实现方式可分为直接寻址和间接寻址两类。 1. 直接寻址Direct Addressing 实现直接寻址的一个较为简单的方案是，让send原语明确指出接纳者的进程号，receive原语明确指出发送者的进程号，系统根据这两个原语实现直接通讯。这种一对一的通讯，用来处置并发进程之间的协作是相当有效的。 2. 间接寻址Indirect Addressing 在间接寻址方式中，音讯并不直接从发送进程

43、传到接纳进程，而是要经过一个中间介质暂时保管音讯的队列，通常称为“信箱。因此，两个通讯进程的操作是，一个进程将音讯发到信箱中，另一个从信箱中取音讯。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.7 4.7 死死 锁锁 死锁死锁Dead LockDead Lock，是指系统中存在一组进程，是指系统中存在一组进程，其中每一个进程都在等待组内别的进程占有的资源，其中每一个进程都在等待组内别的进程占有的资源，这样一来，该组进程都不能向前推进，堕入等待形状。这样一来，该组进程都不能向前推进，堕入等待形状。 系统死锁系

44、统死锁, ,是系统中是系统中n nn1n1个进程因资源恳求个进程因资源恳求得不到满足，皆无法运转而出现的一种无限期等待景得不到满足，皆无法运转而出现的一种无限期等待景象。这是一种极其浪费的景象，它给系统带来的损失象。这是一种极其浪费的景象，它给系统带来的损失有时比出现某些硬件缺点还要大。假设不给予有效地有时比出现某些硬件缺点还要大。假设不给予有效地制止，这种形状将永远不能终了。制止，这种形状将永远不能终了。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.7.1 4.7.1 产生死锁的缘由产生死锁的缘由 当系统

45、同时满足以下4个必要条件时，会产生死锁。 (1) 互斥条件。 进程恳求的资源属于临界资源，每一瞬间只能由一个进程运用。假设有多个进程同时恳求运用同一个临界资源时，只能允许一个运用，其它进程等待。 (2) 不剥夺条件。进程获得某资源后，便不断占有它，直到用完为止才可以释放。其它进程不可以剥夺某个进程已占有的资源，即使该进程目前无法运转。 (3) 恳求和坚持条件。允许一个进程在坚持已有资源不放弃的情况下，进一步恳求新资源，当恳求资源得不到满足而被阻塞时，也不会释放已占有的资源。 (4) 环路条件。 一组进程P1,Pn的占有资源情况与恳求资源情况构成了一个环型链，比如P1等待P2的资源，P2等待P3

46、的资源Pn等待P1的资源。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM定义：资源分配图定义：资源分配图G=NG=E是一个有向图，是一个有向图，N N是结点集，是结点集，E E是边集。其中：是边集。其中： N=PR N=PR，P P为进程集，为进程集，R R为资源集。为资源集。 E=E1E2 E=E1E2，E1E1为资源占有边集，为资源占有边集，E2E2为资源恳求为资源恳求边集。边集。 我们用圆圈表示进程我们用圆圈表示进程pPpP、矩形表示资源、矩形表示资源rRrR，同时，用，同时，用rprp表示资源表示资源r

47、 r被进程被进程p p占有，占有，prpr表示进程表示进程p p恳求资源恳求资源r r。那么两个进程那么两个进程P1P1和和P2P2竞争资源竞争资源R1R1和和R2R2，及，及P1P1、P2P2和和P3P3竞竞争争R1R1、R2R2和和R3R3的环路如下图。的环路如下图。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.7.2 4.7.2 死锁预防死锁预防 预防死锁的主要任务就是使系统不断坚持在平安形状下运转。预防措施可从死锁的4个必要条件去思索。 1资源静态分配方案 2. 资源可剥夺方案 3. 资源有序运用方案操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM4.7.3 4.7.3 死锁防止死锁防止一、平安形状 为了研讨如何防止死锁，我们先来看一下系统的形状变化情况。比如，有两个进程P1和P2竞争资源R1和R2，如图。操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操作系统二十一世纪计算机本科教育OPERATING SYSTERM二、银行家算法二、银行家算法 该算法需求建立多种数据构造予以支持，分别为：可用资源数组