第三章 进程的同步和通讯
(Synchronization and Communication
Among Processes )
教学目的：
在进程的控制的基础上这课引入进程同步和进程同步机制的概念,它对并发执行进程的推进序列加以限制以保证互斥使用临界资源或协同完成任务,解决程序并发执行时带来结果不可再现问题 。 这课介绍了用软件,硬件,信号量机制,AND型信号量集,一般信号量集等各种解决进程互斥同步问题的方法,
重点介绍了信号量机制的概念和用信号量机制解决进程互斥同步问题的方法 。
2001年 9月 20日 9时 1分 计算机操作系统教学要求：
熟悉 进程间制约关系，掌握临界资源和临界区概念，掌握进程同步和进程同步机制,熟悉 利用 软件方法和硬件技术解决进程同步机制。
熟练掌握信号量和 P,V操作的概念、定义和实质，熟练掌握利用信号量实现进程互斥和同步,熟悉 用信号量 描述前趋关系。
掌握 利用信号量解 生产者 -消费者问题,熟悉 利用信号量解 读者 -写者问题等经典同步问题，掌握进程同步分析方法。
了解 用 AND型 信号集机制、一般信号集机制 解 经典同步问题。
熟悉 进程通讯的 概念和共享存储器系统、消息传送系统、管道通信系统 三类高级 通讯 机制，掌握消息缓冲队列通信机制。
2001年 9月 20日 9时 1分 计算机操作系统
3.1进程同步 (Synchronization of
multiple processes)的基本概念进程间制约关系在多道程序环境下，系统中各进程以不可预测的速度向前推进，进程的异步性会造成了结果的不可再现性。为防止这种现象，异步的进程间推进受到二种限制：
1、资源共享关系（ Cooperation Among Processes by
Sharing）
多进程共享资源，运算上无关，但使用资源有关 ―― ＞
间接关系；
例如：打印机 ―― ＞ 互斥使用。对 CPU也是一种共享。排它性。
2001年 9月 20日 9时 1分 计算机操作系统进程同步的概念 -1
2、相互合作关系（直接关系）
（ Cooperation Among Processes by Communication）
为完成共同任务各个进程之间可能有的关系 ―― ＞ 利用同步机制 加以实现。
例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行，由于这三个进程间存在着相互合作的关系，
即先输入再计算、最后再打印的关系，所以这三个进程在并发执行时推进序列受到限制，要保证其合作关系正确，进程间这种关系称为同步关系。司机与售票员之间的关系。
例,A B（ 可在黑板画图）中间数据 N
3,主要目的：
使并发执行的各个进程之间能有效地共享资源和相互合作 ―― ＞可再现性。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.1 临界资源临界资源象打印机这类资源 一次只允许一个进程使用的资源称为临界资源 。或者：进程之间必须采用互斥方式共享的资源称为临界资源。
硬件资源 打印机、磁带机纸带机、读卡机软件资源 消息缓冲队列变量、中间结果数组缓冲区等共享资源：当然还有一类象磁盘等资源，它允许进程间共享，
即可交替使用。
临界资源又称独享资源。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.1 临界资源对于临界资源的理解：
生产者 -----消费者生产者：产生信息的进程；
消费者：使用 /消耗信息的进程；
例：输入 ---计算计算 ---打印 相对性。
P1 Pm
m
C1 Cq
B0 B1 …,…,.,……… Bn-1
2001年 9月 20日 9时 1分 计算机操作系统
3.1.1 临界资源规则：
（ 1）只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息。
（ 2）只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区。
用一个数组 buffer来表示上述具有 n个缓冲区的缓冲池；
In:表示输入指针；表示下一个可投放数据的缓冲区，每当生产者进程生产并投放一个消息后,in+1;
Out:表示输出指针；表示下一个可获取数据的缓冲区，每当消费者进程消费 /取走一个消息后,out+1;
循环缓冲 0,1,…,n-1; in:=(in+1)mod n;
out:=(out+1)mod n;
Counter:计数器，生产一个消息 -?buffer; +1
buffer-?取走一个消息； -1
解释 P62/p63
2001年 9月 20日 9时 1分 计算机操作系统
3.1.2临界区 (critical sections
临界区：
每个进程中访问临界资源的那段程序段称为临界区（临界段）。
一、临界区 (critical sections)的定义和进入
1、定义：
2001年 9月 20日 9时 1分 计算机操作系统一、临界区 (critical sections)的定义和进入
2、进入（可细讲）
例如进程 A的程序如下 (进程 B的程序类似 )：
A,begin
Input data 1 form I/O 1 ;
Computer…… ;
Print results 1 by printer ; A临界区
end
解决办法：申请进入、退出说明。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.2 临界区二,进程同步机制应遵循的原则进程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。
多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。 所有的进程同步机制应遵循：
空闲让进 。
当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。
忙则等待 。
当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其它试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
有限等待 。
对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入,饥饿,状态。
让权等待 。
当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。
例,p1,p2并发工作，若 P1先进入临界区，则先占用临界资源 R。 时间片到，
P2想进入临界区，就需忙则等待（释放 CPU）,有限等待，若 P1退出，则空闲让进 P2。
2001年 9月 20日 9时 1分 计算机操作系统进程同步机制
一个由临界区和剩余区 1和剩余区 2程序段组成的进程采用进程同步机制后的描述如下：
begin remainder section 1； 剩余区 1
进入区
critical section ； 临界区退出区
remainder section 2 ； 剩余区 2
end
进程同步机制在临界区前加上进入区，它负责对欲访问的临界资源状态进行检查，以决定是允许该进程进入临界区还是等待。同时在临界区后加上退出区，它负责释放临界资源以便其它等待该临界资源的进程使用。
实现进程互斥和同步的信号量机制有软件方法、硬件指令方法、信号量机制和管程等。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.3 利用 软件方法解决 进程互斥 (Mutual
Exclusion )问题问题：有 二个进程 Pi和 Pj互斥共享 临界资源 R，
begin
parbegin
Pi,...…
Pj,.....…
parend
end
下列 算法 只写出进程 Pi程序。
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -1
算法 1
该算法设置了一个公用整型变量 turn,用于指示被允许进入临界区的进程编号，既若 ture=0,表示允许 Pi进程进入临界区。
Pi进程,Pj进程,
repeat repeat
while turn≠i do no op while turn≠j do no op
Critical section Critical section
turn=j turn=i
Remain Section Remain Section
until false until false
该算法可确保每次只允许一个进入临界区。但采用强制两个进程轮流进入临界区，很容易造成资源利用不充分。当 Pi
退出后置 turn为 j,但 Pj并未使用 CS,Pi又想使用时，则无法置 turn= i,不能进入 CS,违背,空闲让进,。
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -2
算法 2:
算法基本思想：在每一个进程访问临界区资源之前，先动查看一下临界资源是否正被访问，若正被访问，该进程需等待，
否则才进入自己的临界区。为此设置了一个布尔型数组 flag[]，
如第 i个元素值为 false--- flag[i]=false----表示 Pi进程未进入临界区，值为 true--- flag[i]=true------表示 Pi进程进入临界区。
Pi:repeat Pj:repeat
while flag[j] do no_op; while flag[i] do no_op;
flag[i]:=true; 2 flag[j]:=true;
critical_section; 1 critical_section;
flag[i]:=false; flag[j]:=false;
remainder section; remainder section;
until false until false
会出现 Pi和 Pj同时 进入临界区错误，违背忙则等待。
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -3
算法 3:
算法 2是先检测对方进程状态标志后再置自己标志，由于在检测和放置中可插入另一个进程时检测操作，会造成二个进程在分别检测后同时进入临界区。为此算法 3采用先设置自己标志后再检测对方状态标志，它的程序如下，布尔型数组 flag[]，
如第 i个元素值为 false--- flag[i]=false----表示 Pi进程未进入临界区，值为 true--- flag[i]=true------表示 Pi进程进入临界区 /要求进入 CS。
Pi:repeat Pj:repeat
flag[i]:=true; 2 flag[j]:=true;
while flag[j] do no_op; while flag[i] do no_op;
critical_section; 1 critical_section;
flag[i]:=false; flag[j]:=false;
remainder section; remainder section;
until false until false
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -4
算法 4(Peterson 1981)：
该算法组合了算法 1和算法 4，为了防止二进程进入临界区而无限期等待，又设置变量 turn,表示允许进入临界区的编号，每个进程在先设置自己标志后再设置 turn标志，不允许另一个进程进入，这时再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当二个进程同时要求进入临界区时，只允许一个进程进入临界区。
Pi,repeat
flag[i]:=true; turn:=j;
while (flag[j] and turn=j) do no_op;
critical_section; 1
flag[i]:=false;
remainder section;
until false
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -4
Pj,repeat
flag[j]:=true; turn:=i;
while (flag[i] and turn=i) do no_op;
critical_section;
flag[j]:=false;
remainder section;
until false
2001年 9月 20日 9时 1分 计算机操作系统
3.1.4 利用 硬件技术实现互斥
1.提高临界区代码执行中断优先级这种方法在 UNIX和 Windows NT中都使用，它是在单机系统中有效地实现互斥的一种方法。
因为在传统操作系统中，打断进程对临界区代码的执行只有中断请求、中断一旦被接受，系统就有可能调用其它进程进入临界区，并修改此全局数据库。所以用提高临界区中断优先级方法就可以屏蔽了其它中断，保证了临界段的执行不被打断，从而实现了互斥。
在多处理机情况下，用提高临界段代码执行的中断优先级方法是无法保证互斥的，因为在一个处理机上提高中断优先级并不能阻止其它处理器上的中断，所以必须采用其它方法。
2001年 9月 20日 9时 1分 计算机操作系统
2,检测和设置（ TS） 硬件指令
许多大型机（如 IBM370等）和微型机（如 Intel × 86等）中都提供了专用的硬件指令，这些指令全部允许对一个字中的内容进行检测和修正，或交换两个字的内容。特别要指出的是这些操作都是在一个存储周期中完成，或者说由一条指令来完成，用这些指令就可以解决临界区问题了。
在单机系统中，由于中断的原因，使得一个进程在对一个公用变量先取来并检测其值，然后修改的这两个动作中，可以插入其它进程对此公用变量的访问和修改，从而破坏了此公用变量数据的完整性和正确性。在多机系统中，多处理机共享主存，因而使得某处理机可插入另一处理机的两个存储访问周期之间，访问并修改此共享变量。
2001年 9月 20日 9时 1分 计算机操作系统检测和设置（ TS） 硬件指令 -1
对于同一主存块访问要求，即使两个处理机同时提出，存储控制逻辑也只能让其中之一先访问，但在一个处理机的两个存储周期间则可以插入另一个处理机的存储周期。现在用一条指令来完成检测和修改两个功能，这样中断和插入另一处理机的存储周期均不可能，所以不会影响此公用变量数据的完整性。
检测和设置（ TS） 的功能可用 PASCAL语言描述如下：
function TS (var lock,boolean):boolean
begin
TS = lock ；
lock:=true ；
end
这条指令在 Z-8000中称为 TEST指令，在 IBM370中称为 TS指令。
每次调用 TS函数，都把 lock置为 true,Lock=false,表示该资源空闲； Lock=true.表示该资源正在被使用。
2001年 9月 20日 9时 1分 计算机操作系统检测和设置（ TS） 硬件指令 -2
用这些硬件指令可以简单有效地实现互斥。其方法是为每个临界段或其它互斥资源设置一个布尔变量，例如称为 lock。
当其值为 false则临界区末被使用，反之则说明正有进程在临界区中执行。于是某进程用 TS指令实现互斥的程序结构为
（设为无限循环进程）：
P1 repeat P2 repeat
...,.,
while TS(lock) do skip ； while TS(lock) do skip ；
进程临界区 CS ； 进程临界区 CS ；
lock,=false ； lock,=false ；
...,..
until false; until false;
WindowsNT 内核用来达到多处理器互斥的机制,转锁,,它类同于 TS指令机制。
分析（略）
2001年 9月 20日 9时 1分 计算机操作系统
3、利用 SWAP指令实现互斥
1 SWAP指令
PROCEDURE SWAP(var a,b:boolean)
VAR temp:boolean;
begin
temp:=a;
a:=b;
b:=temp
end
2 利用 SWAP实现进程互斥
lock:全局变量 TRUE-----有进程在使用 CR；
FALSE------无进程在使用 CR。
表示有无其它进程进入临界区。
2001年 9月 20日 9时 1分 计算机操作系统
3、利用 SWAP指令实现互斥
VAR lock:boolean:=false;
Begin
parbegin
p1,begin p2,begin
repeat repeat
key:=true; key:=true;
repeat repeat
swap(lock,key); swap(lock,key);
until key:=false; until key:=false;
临界区； 临界区；
lock:=false; lock:=false;
剩余代码区； 剩余代码区；
until false until false
parend
End.
无法满足“让权等待”原则。
2001年 9月 20日 9时 1分 计算机操作系统
3.2 信号量 (Semaphores)机制
3.2.1 整型信号量机制一、整型信号量
S,整型信号量 ; 原子操作：
wait(s):while s<=0 do no-op
s:=s-1;（ P操作）
signal(s):s:=s+1; （ V操作）
信号量的使用：必须置一次且只能置一次初值，初值不能为负数，只能执行 P,V操作,P,申请一个资源； V,释放一个资源。资源能否使用由 wait(s)来判断。
二、利用信号量实现互斥
2001年 9月 20日 9时 1分 计算机操作系统
var mutex:=semaphore:=1 ；
begin
parbegin
P1:begin P2:begin
REPEAT REPEAT
…… ； …… ；
wait(mutex) ； wait(mutex) ；
Print results1 by printer; Print results2 by printer;
signal(mutex) ； signal(mutex) ；
until false until false
end end
parend
End.
Semaphore可看作是一个整型信号量的数据类型。
分析（略）
3.2.1 整型信号量机制 ---------二、利用信号量实现互斥
2001年 9月 20日 9时 1分 计算机操作系统
3.2.1 整型信号量机制 ----三、利用信号量描述前趋关系
P70
2001年 9月 20日 9时 1分 计算机操作系统
3.2 信号量 (Semaphores)机制
1965年，荷兰学者 Dijkstra提出信号量机制,它从整型信号量机制发展到记录型信号量机制，进而发展为,信号集,机制。
问题：整型信号量即可描述，为什么要引入记录型？
答案：前者有一致命弱点，无法实现让权等待，一直在空踏步，消耗时间片，并不释放 CPU。
解决方法：进程进入临界区之前先检测临界资源有无，若无 CR,则由执行 ---阻塞，不再空踏步。但有可能出现多个进程等待同一资源情况,----引入记录型,s.value表示资源数； s.L表示阻塞队列。
3.2.2 记录型信号机制
1.记录型信号量结构在信号量机制中信号量是代表资源物理实体的数据结构,记录型信号量的数据结构 描述如下：
type semaphore=record
value,integer;
L,pointer of PCB;
end
信号量的值只能通过两个原子操作,wait/P,signal/V操作来改变，
它代表分配资源和释放资源。
2001年 9月 20日 9时 1分 计算机操作系统
2 信号量的类型信号量按联系进程的关系分成二类：
公用信号量（互斥信号量）,它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加 P,V操作，即都可申请和释放该临界资源，其初始值置为 1。信号量 mutex取值意义如下：
mutex,value ＝ 1 ； 表示资源空闲，可供使用。
＝ 0 ；表示资源已被占用，无其它进程等待。
＝ -n ； 表示资源已被占用，还有 n个进程因等待资源而阻塞。
专用信号量（同步信号量）,它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加 P操作（即可申请资源），而由其合作进程对它施加 V操作（即释放资源）。
2001年 9月 20日 9时 1分 计算机操作系统
3,P-V操作 (wait(s)和 signal(s) 操作 )
对信号量施加 P,V操作代表申请和释放资源。 P-V操作描述如下：
proceduce wait(S)
var S:semaphore ；
begin
S.value=S.value-1 ； 记录型和整型区别：先 -1后判别
If S.value<0 then block(S.L) ；
end
Procefuce signal(S)
Var S:semaphore ； ;
begin
S.value=S.value+1 ；
If s.value≤0 then wakeup(S.L) ；
end
解释（略） (练习 )
2001年 9月 20日 9时 1分 计算机操作系统
（ 4） 利用信号量实现进程互斥为使多个进程能互斥地访问某临界资源，只需为该资源设置一个互斥信号量 mutex,并设其初值为 1，然后将各进程的临界区
CS置于 P（ mutex） 和 V(mutex)操作之间即可。利用信号量实现共享打印机的 A,B两进程互斥的类并行 PASCAL程序描述如下：
此例同整型信号量之例，对照讲。
2001年 9月 20日 9时 1分 计算机操作系统利用记录型信号量实现进程互斥 -1
var mutex:=semaphore:=1 ；
begin
parbegin
P1:begin P2:begin
repeat repeat
wait(mutex) ； wait(mutex) ；
Print results1 by printer; Print results2 by printer;
signal(mutex) ； signal(mutex) ；
Until false; Until false;
end end
parend
end (练习 )
Mutex:记录型信号量，初值为 1。
2001年 9月 20日 9时 1分 计算机操作系统利用记录型信号量实现进程互斥 -2
分析：初始时,mutex.value:=1; mutex.L=NIL 。
设 P2先执行,WAIT(mutex);
mutex.value:= mutex.value:-1:=0-----<0不成立
P2进入临界区执行，未使用完（时间片到）退出执行，
由执行 ----就绪，
P1被调度由就绪 ----执行，执行 WAIT(mutex)，
mutex.value:= mutex.value:-1:=0-1,=-1<0成立，则阻塞 P1----BLOCK（ mutex.L ） **（ 1） 此处与整型信号量不同，
整型信号量中 P1在消耗时间片，未实现“让权”，而此时阻塞，释放 CPU实现“让权等待”。 再次调度
P2从就绪 ---执行，使用临界资源完毕后，执行 signal(mutex)
mutex.value:= mutex.value+1:=0-----<=0成立,wakeup(mutex.L),把
P1唤醒，从阻塞 ----就绪,P2继续执行，时间片用完,P2由执行 -----就绪，
P1调度执行,**（ 2） 此处与整型信号量不同，整型信号量中现场在
WAIT(mutex) 之前，而此时现场在 WAIT(mutex) 之后，不用再执行
WAIT(mutex) 了，直接进入临界区。
2001年 9月 20日 9时 1分 计算机操作系统
(5)利用信号量实现进程同步利用信号量能解决进程间的同步问题，这里以下图所示的计算进程 C和打印进程 P通过缓冲区 Buffer传送数据的同步问题为例说明。
Buffer
C P
2001年 9月 20日 9时 1分 计算机操作系统利用信号量实现进程同步 -1
C和 P两进程基本算法如下：
C,begin P,begin
repeat repeat
Compute next number ; take from Buffer ;
add to Buffer ; print last number ;
until false until false
end end
C和 P两进程并发执行，必须在执行序列上遵循以下规则，才能避免错误。
只有当 C进程把数据送入 Buffer后,P进程才能从 Buffer中取出数据来打印，否则 P进程只能等待。
只有当 P进程从 Buffer中取走数据后,C进程才能将新计算的数据再存入 Buffer,否则 C进程也只能等待。
2001年 9月 20日 9时 1分 计算机操作系统利用信号量实现进程同步 -2
为了实现进程同步，需采用同步信号量。为了满足第一条同步规则，设置一个同步信号量 full,它代表的资源是缓冲器满，它的初值为 0。这个资源是 P进程所拥有,P进程可以申请该资源，对它施加 P操作，如条件满足 P进程可从
Buffer中取数。而 P进程的合作进程 C对 full信号量施加 V
操作，即它可释放该资源。当 C进程将数据存入 Buffer后，
即可释放该资源供 P进程再使用。同样为了满足第二条同步规则，设置另一个同步信号量 empty,它代表的资源是缓冲器空，它的初值为 1 。缓冲器空这个资源是进程 C所拥有，它可以申请该资源，对它施加 P操作。而它的合作进程 P对 empty信号量施加 V操作。
实现 C和 P两进程同步的类 PASCAL程序：
2001年 9月 20日 9时 1分 计算机操作系统
var,empty,full:semaphore:=1,0 ；
begin
parbegin
C,begin
repeat
Compute next number ；
P(empty) ；
Add to buffer ；
V(full) ；
until false
end
P,begin
repeat
P(full) ；
Take from Buffer ；
V(empty) ；
Print last number ；
until false
end
parend
end
2001年 9月 20日 9时 1分 计算机操作系统
(6)利用信号量描述 前趋关系进程间同步关系也可用前趋图表示。 C和 P两进程间先计算好再打印同步关系用前趋图表示如下：
对应这个前趋关系可设置同步信号量 full,它为后继进程
P拥有，初值为 0。它的并发执行程序如下：
var full,semaphore,=0;
begin
parbegin
C,begin Compute ； V(full) ； end
P,begin P(full) ； Print ； end
parend
end
C P
2001年 9月 20日 9时 1分 计算机操作系统
3.2.3 信号量集机制一,AND型 信号集机制以前的规定都是针对共享一个 CR而言，若共享多于一个 CR
A … B …
wait(Dmutex) wait(Emutex)
wait(Emutex) wait(Dmutex)
临界资源 D,E 临界资源 D,E
… …
分析 （略） -----------------死锁。
解决办法,Swait(Dmutex,Emutex),对 2个信号量同时进行检测，
避免死锁。
AND同步机制的主要思想：将进程在整个运行期间所需的所有临界资源，一次性地全部分配给进程，待该进程使用完后一起释放。资源分配也采取原子操作方式。
2001年 9月 20日 9时 1分 计算机操作系统
3.2.3 信号量集机制
Swait,Ssignal操作如下：
Swait(S1,S 2,…,S n )
if S1 >= 1 and …..and S n >=1 then for i:=1 to n do Si =
Si - 1 ; endfor
else
Place the executing process in the waiting queue of the
first Si with Si< 1 and set its program counter to the
beginning of the the Swait operation.
endif
Ssignal(S1,S 2,…,S n )
for i:=1 to n do Si = Si + 1 ;
Remove all the process waiting in the queue associated with
Si into the ready queue.
Endfor **回到现场时从 Swait()前开始执行。
2001年 9月 20日 9时 1分 计算机操作系统
3.2.3 信号量集机制二,一般 信号集机制
1、引入原因：
（ 1）前面所讲的 wait与 signal操作只对信号量做 +1/-1操作，
既每次只能获得 /释放一个单位的临界资源。如果一次需要 N
个资源时，仅需进行 N次 wait操作，效率低下。
（ 2）当资源数目低于某一下限值 T时，不予分配。所以每次分配前，必须测试该资源的数量是否大于测试值 T。
因此引入 一般 信号集机制。
2。定义：
相应的 Swait,Ssignal操作如下：
2001年 9月 20日 9时 1分 计算机操作系统一般 信号集机制 -1
Si （ S1 ~Sn ）,每种 临界资源的数目。
d I（ d 1 ~ d n ）,每次申请的 临界资源数目。
ti（ t 1~ t n）,每个 临界资源对应的下限值。
Swait(S1,t 1,d 1,…,S n,t n,d n )
if S1 >= t 1 and …..and S n >=t n then
for i:=1 to n do Si = Si - d i ;
endfor
else
Place the executing process in the waiting queue of the first Si with Si < t i and
set its program counter to the beginning of the the Swait operation.
endif
Ssignal(S1,d 1,…,S n,d n )
for i:=1 to n do Si = Si + d i ;
Remove all the process waiting in the queue associated with Si into the ready
queue.
endfor
2001年 9月 20日 9时 1分 计算机操作系统一般 信号集机制 -2
特殊情况：
1,Swait(s,d,d):
只有一个资源被申请，即信号量集中只有一个信号量。每次允许申请 d个资源，当系统中现有资源数小于 d时，不允许分配。
2,Swait(s,1,1),1中的特例，只有一个资源被申请，即信号量集中只有一个信号量。每次允许申请 1个资源，当系统中现有资源数小于 1时，不允许分配。
S>1-----------记录型信号量； S=1----------互斥信号量。
3,Swait(s,1,0),只有一个资源被申请，即信号量集中只有一个信号量。每次允许申请 0个资源，当系统中现有资源数小于 1时，不允许分配。换言之,s>=1时，允许多个进程进入某特定 CS,s<1（ s=0） 时，任何进程都不进入该 CS,相当于一个可控开关。
2001年 9月 20日 9时 1分 计算机操作系统
3.3利用信号量解 经典进程同步问题经典进程同步问题是从进程并发执行中归纳的典型例子，这些问题常用来测试新的同步机制可行性。主要的经典同步问题有生产者 -消费者问题、读者 -写者问题、哲学家进餐问题等。
（ 1）生产者 -消费者问题 （ producer-consumer Problem ）
生产者 -消费者问题是最著名的同步问题，它描述一组生产者
（ P1 …… Pm） 向一组消费者（ C1…… Cq） 提供消息。它们共享一个有界缓冲池（ bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息，如下图所示。生产者 -消费者问题是许多相互合作进程的一种抽象。
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -1
假定缓冲池中有 n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，
它只允许一个生产者投入消息 ;
或者一个消费者从中取出消息 ;
即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。
所以必须设置互斥信号量 mutex,它代表缓冲池资源，它的数值为 1。
P1 Pm
m
C1 Cq
B0 B1 …,…,.,……… Bn-1
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -2
与计算打印两进程同步关系相同，生产者和消费者二类进程 P
和 C之间应满足下列二个同步条件：
只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。
只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。
为了满足第一个同步条件，设置一个同步信号量 full,它代表的资源是缓冲区满，它的初始值为 0，它的值为 n时整个缓冲池满。这个资源是消费者类进程 C所拥有,C进程可以申请该资源，对它施加 P操作，而 C进程的合作进程生产者进程 P对它施加 V操作。同样为了满足第二个同步条件，设置另一个同步信号量 empty,它代表的资源是缓冲区空，它的初始值为 n，
表示缓冲池中所有缓冲区空。
用类并行 PASCAL语言和信号量机制解生产者 -消费者问题程序：
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -2
var mutex,empty,full:semaphore:=1,n,o ；
Buffer,array [0…… n-1] of message ；
in,out,o…… n-1:=0,0 ；
begin
parbegin
P,begin
repeat
Produce a new message in nextp ；
P (empty) ；
P (mutex) ；
Buffer[in]=nextp ；
in,=(in+1) mod n ；
V (mutex) ；
V (full) ；
until false
end
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -4
C,begin
repeat
P (full) ；
P (mutex) ；
nextc:= buffer[out] ；
Out,= (out+1) mod n ；
V (mutex) ；
V (empty) ；
Consume message in nextc ；
until false
end
parend
End
利用 AND信号量解决生产者 —消费者问题（ P74）。
2001年 9月 20日 9时 1分 计算机操作系统
（ 2） 读者 -写者问题（ Readers/Writers Problem）
一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称读者，而另一些进程则要求修改数据集内容，它称写者，几个读者可以同时读些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。
设置互斥 信号量 wmutex 表示写者间、读者和写者间互斥，
读者和写者主要 程序如下：
reader,writer:
第一个读者到时 P（ wmutex） P（ wmutex）
Read Text Write Text
最后 一个读者离开时 V（ wmutex） V（ wmutex）
2001年 9月 20日 9时 1分 计算机操作系统读者 -写者问题 -1
用 readcount变量来记录读者数，读者 程序为：
if readcount=0 then P（ wmutex） ;
readcount= readcount+1;
Read Text
readcount= readcount-1;
if readcount=0 then V（ wmutex） ;
由于 readcount是读者间共享变量，属于临界资源，它也需互斥，为此又增设互斥信号量 rmutex.
用类并行 PASCAL语言和信号量机制解读者 -写者问题程序：
2001年 9月 20日 9时 1分 计算机操作系统读者 -写者问题 -2
Var rmutex,wmutex,semaphore:=1,1 ;
readcount,integer,=0 ;
begin
parbegin
reader:begin writer:begin
repeat repeat
P(rmutex) P(wmutex);
if readcount=0 then P(wmutex); Write Text;
readcunt=readcount+1; V(wmutex);
V(rmutex) until false
Read Text end
P(rmutex)
readcount=readcount-1 ;
if readcount=0 then V(wmutex) ;
V(rmutex)
until false
end
parend
end
2001年 9月 20日 9时 1分 计算机操作系统
（ 3） 进程同步的分析
用信号量机制解决进程同步问题需在程序中正确设置信号量和在适当位置安排 P,V操作。例如生产者 -消费者问题中，
用于互斥进入临界区的 P（ mutex）,V(mutex)语句需紧靠着临界区前和后，而生产者用于同步的 P（ empty） 和 V（ full）
(消费者为 P（ full） 和 V(empty))语句相对临界区就在外面一层，格式如上程序所述。如在以上问题中生产者的 P
（ empty） 和 P(mutex)先后位置对调，相应消费者的 P（ full）
和 P（ mutex） 先后位置也对调，则生产者和消费者在并发执行时，在某个执行序列会出现问题。
下面介绍如何寻找会发生问题的那个执行序列,分析方法用下表表示。表左边是生产者和消费者二进程推进序列，此推进序列需用户寻找；表中间是该操作执行后信号量的变化值,表中信号量有 mutex,empty和 full； 表的右边是该操作执行后引起进程 PCB的队列变化 。表中队列有就绪队列 RL，
因分别等待 mutex,empty,full信号量而阻塞的队列 QmL、
QeL,和 QfL。
2001年 9月 20日 9时 1分 计算机操作系统进程同步的分析 -1
在表中已找到一个推进序列。该序列先执行消费者进程，
由于消费者进程交换了 P操作，消费者进程在先后执行 P
（ muyex） 和 P（ full） 后阻塞在等待 full信号量的队列中。
这时只能执行生产者进程，由于生产者进程也交换了 P操作，在生产者进程执行了 P（ mutex） 操作后，生产者进程阻塞在等待 mutex信号量的队列中。这样生产者和消费者两进程分别阻塞在等待 mutex和 full信号量的队列，没有进程可以向前推进，系统进入死锁状态。这说明在生产者
-消费者问题中对同步信号量和互斥信号量的二个 P操作的是不能颠倒，而对互斥信号量和同步信号量的二个 V操作的顺序交换影响不大。
生产者、消费者交换 P操作后发生问题的那个执行序列：
2001年 9月 20日 9时 1分 计算机操作系统进程同步的分析 -2
操 作 操作引起 （信号量）
变化操作引起 ( 队列 ) 变化事件 生产者
(P)
消费者
(C)
m u t e x e m p t y full RL Q mL QeL QfL
0 / / 1 n 0 P,C / / /
C
1
/ P
( m u t e x )
0 n 0 P / / /
C
2
/ P ( f u l l ) 0 n -1 P / / C
P
1
P r a d u c e 0 n -1 / / / C
P
2
P
( m u t e x )
-1 n -1 / P / C
2001年 9月 20日 9时 1分 计算机操作系统
2,用 一般 信号集机制解读者 -写者问题
var RN integer ;---同时最多允许 RN个读者读。
L,mx,semaphore,=RN,1 ;
begin
parbegin
reader,begin writer,begin
repeat repeat
Swait (L,1,1 ) ; Swait (mx,1,1,L,RN,0 );
Swait (mx,1,0 ) ; perform write operation
perform read operation Ssignal (mx,1 ) ;
Ssignal (L,1) ; until false ;
until false ; end
end
parend
end
RN---同时最多允许 RN个读者读。所以引入一个信号量，初值为 RN,通过执行
Swait (L,1,1 )操作，控制读者数目，当有一个读者进入时,L就 -1，
直到 RN个读者全部进入,L为 0,如果有 RN+1个读者进入,L<0,则阻塞。
mx:互斥信号量，写 -写 /读 -写。
2001年 9月 20日 9时 1分 计算机操作系统
3.3.3哲学家进餐问题哲学家就餐问题五个哲学家围坐在一个园桌周围，每个哲学家面前都有一盘通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个盘子间有一把叉子，餐桌如右图。
哲学家的生活包括两种活动：即吃面条和思考。当哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次拿一把，不分先后次序，如果成功，他就开始吃面条，吃完后放下叉子，继续思考。试用信号量写出哲学家行为的程序描述，
要求不能让某个（或某些哲学家饿死） 。
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
0#人
1#人
2#人 4#人
5#人
0#筷
1#筷
2#筷
3#筷
4#筷
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
1、一个简单解法：
用一个信号量表示一只筷子，这五个信号量 ---信号量数组，其描述为：
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
每个哲学家的进程都类似
begin Pi,repeat
parbegin wait(chopstick[i]);
P0; wait(chopstick[i+1] MOD 5);
P1; …
P2; eat;
P3; …
P4; signal(chopstick[i]);
parend signal(chopstick[i+1] MOD 5);
end …
think;
until false;
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题分析,i=0时,0#哲学家拿到 0#筷,0#哲学家时间片退出。设 1#哲学家饿，
i=1时,1#哲学家拿到 1#筷,1#哲学家时间片退出。设 2#哲学家饿，
i=2时,2#哲学家拿到 2#筷,2#哲学家时间片退出。设 3#哲学家饿，
i=3时,3#哲学家拿到 3#筷,3#哲学家时间片退出。设 4#哲学家饿，
i=4时,4#哲学家拿到 4#筷,4#哲学家时间片退出。 0#哲学家回来，
执行 wait(chopstick[i+1] MOD 5);显然阻塞。同理 1,2,3,4被阻塞 -----死锁，如何解决？有 3种办法：
1）仅当哲学家的左右 2只筷子都可用时，才允许他吃饭 -----AND同步问题。
用 AND信号量解决：
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
begin Pi,repeat
parbegin think;
P0; Swait(chopstick[i+1] MOD 5,chopstick[i]);
P1; …
P2; eat;
P3; …
P4; Ssignal(chopstick[i+1] MOD 5,chopstick[i]);
Parend …
end until false;
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
2)至多允许 4个哲学家同时吃饭，以保证至少有一个人可以吃到饭，吃毕 ----2只筷子 ------其它人可以吃了。
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
man:semaphore:=4;{哲学家计数器，初始化为 4，若第五个人到则阻塞 }
begin Pi,repeat
parbegin wait(man);
P0; wait(chopstick[i]);
P1; wait(chopstick[i+1] MOD 5);
P2; eat;
P3; signal(chopstick[i]);
P4; signal(chopstick[i+1] MOD 5);
Parend signal(man);
end until false;
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
3)规定奇数号哲学家先拿他左边的筷子,1#,2#哲学家争夺 1#筷子,
偶数号哲学家先拿他右边的筷子,3#,4#哲学家争夺 3#筷子,
即 5个哲学家都先争夺奇数号筷子，获得后，再去争夺偶数号筷子，最后总有一个哲学家能获得 2只筷子而进餐。
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
begin Pi/奇数,repeat
parbegin …
P0; wait(chopstick[i]);
P1; wait(chopstick[i+4] MOD 5);
P2; eat;
P3; signal(chopstick[i]);
P4; signal(chopstick[i+4] MOD 5);
Parend think;
end until false;
3#人
1#人
2#人
4#人
5#
人
1#筷
2#筷
3#筷
4#筷
5#筷
2001年 9月 20日 9时 1分 计算机操作系统补充题 1：
有十个读者和两个编辑同时处理一篇文章,对于读操作是可以同时进行的,若有读者正在读这篇文章,编辑就不能工作,若编辑正在处理这篇文章,读者就不能作读操作,编辑与编辑的工作也是互斥的,试用信号 量 写出读者与编辑之间协同工作的程序描述 。
2001年 9月 20日 9时 1分 计算机操作系统量
2001年 9月 20日 9时 1分 计算机操作系统解：
mutex:用于读者与编辑、编辑与编辑的互斥信号量，初值为 1；
mutex1:用于对 couter操作的互斥的信号 量,初值为 1。
2001年 9月 20日 9时 1分 计算机操作系统补充题 2：
一个文件 F,只供多个进程读，把进程分为 A,B两类，有规定：
1）只有同类进程才能同时读文件 F。
2） 系统中并发执行的进程数不能超过 N（ N>0） 个。
试用信号量写出 A,B两类进程的算法，并说明所用信号量含义。
2001年 9月 20日 9时 1分 计算机操作系统
3.5进程 通信进程通信指进程之间的信息交换，信息量有多少：
进程的同步与互斥 -----低级通信生产者 — 消费者,同步 /互斥信号量作为通信工具（信号量有多有少）缺点 （ 1）效率低，一次一个消息
---生产者 — 消费者 （ 2）对用户不透明，用户事事亲为,OS只提供共享存储器。编写麻烦，不方便。
高级通信机制可归结为三大类：共享存储器系统，消息传送系统和管道通信系统。
3.5.1进程通信的类型
（ 1）共享存储器系统（内存）
1,基于共享数据结构的通信方式在这种通信方式中，要求诸进程公用某个数据结构，进程通过它们交换信息。如在生产者 -消费者问题中，就是把缓冲池（有界缓冲区）这种数据结构用来作通信的。这种通信方式是低效的，只适用传送少量的数据。
2001年 9月 20日 9时 1分 计算机操作系统基于共享存储区的通信方式 -1
进程 A 进程 B
虚空间 内存空间 虚空间
A正文
A数据
A栈共享存储器
B正文
B数据
B栈
2001年 9月 20日 9时 1分 计算机操作系统
（ 2） 消息传递系统（ Message passing system）
消息传递系统分为直接通信方式和间接通信方式两种。
1,直接通信方式这是指发送进程利用 OS提供的发送命令直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程利用 OS提供的接收命令直接从消息缓冲队列中取得消息。此时要求发送进程和接收进程都以显示的方式提供对方的标识符，通常系统提供下述两条通信原语：
Send(Receiver,message) ；
Receive(Sender,message) ； 或 (Receive (message)) ；
直接通信的实例 -消息缓冲队列通信机制。
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -1
消息缓冲队列通信原理消息缓冲队列通信机制的原理是：由系统管理一组缓冲区，
其中每个缓冲区可以存放一个消息。当发送进程要发送消息时先要向系统申请一个缓冲区，然后把消息写进去，接着把该缓冲区连接到接收进程的消息缓冲队列中。接收进程可以在适当的时候从消息缓冲队列中摘下消息缓冲区，读取消息，
并释放该缓冲区。
消息缓冲队列通信的数据结构有消息缓冲区和进程 PCB中有关通信的扩充数据项，消息缓冲区描述如下：
type message buffer=record
sender ； 发送进程的标识符
size ； 消息长度
text ； 消息正文
next ； 指向下一个消息缓冲区的指针
end
2001年 9月 20日 9时 1分 计算机操作系统图,消息缓冲队列通信的发送和接收过程系统管理的－组缓冲区进程 A
进程 B PCB 进程 B
.
mutex
sm
mq
………,
.
.
send(B,a);
sender,A
size,13
text,
How are
you?
Next
send,A
size,13
text:
How are
you?
Next:
sender,A
size,5
text,Hello
Next,
sender,A
size:13
text:
How are
you?
Next:0
sender,A
size,5
text,Hello
Next:
.
.
receive(b);
sender,A
size,5
text,Hello
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -2
PCB 有关通信的扩充数据项
type PCB = record
.
mutex ； 消息缓冲队列互斥信息量 ；
Sm ； 消息缓冲队列资源信息量 ；
mq ； 消息缓冲队列首指针 ；
,
End
(练习 )
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -3
发送原语
Proceduce send (receiver,a)
begin
getbuf(a.size,i) ；
i.sender = a.sender i.size = a.size ；
i.text = a.text ； i.next = 0 ；
getid (PCB set,receiver,j) ；
P(j.mutex) ；
insert(j.mq,i) ；
V(j.mutex) ；
V(j.Sm) ；
end
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -4
接收原语
proceduce receive(b)
begin
j,= internal name ；
P (j.Sm) ；
P (j.mutex) ；
Remove(j.mq,i ) ；
V(j.mutex) ；
b.sender,=i.sender ；
b.size,=i.size ；
b.text,=i.text ；
Releasebuf(i) ；
end
2001年 9月 20日 9时 1分 计算机操作系统
2.间接通信方式
在间接通信情况，消息不直接从发送者发送到接收者，而是发送到暂存消息的共享数据结构组成的队列，这个实体称为 信箱 （ mailbox）,因此二个进程通信情况，一个进程发送一个消息到某个信箱，而另一个进程从信箱中摘取消息。
间接通信的使用好处是增加了使用消息的灵活性。发送者和接收者的关系可能是一对一、多对一，一对多或多对多。
一对一的关系允许一个专用通信链路用于二个进程间的交互，
它能使俩进程间交互不受其它进程错误干予的影响，多对一的关系对客户／服务器交互特别有用，一个进程对多个其它进程（用户）提供服务。在这种情况信箱经常称作为端口
(port)。 一对多关系允许一个发送进程和多个接收进程交互，
这可用来将消息广播 (broadcast)给一组进程。
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -5
进程与信箱的联系有二种：静态和动态。端口经常与特定的进程保持静态的联系，即端口创建后永久地分配给某个进程。
同样一对一关系是典型地规定为静态的和永久的。当有许多发送者时，一个发送者与信箱的联系可以动态发生，例如联接（ conect） 和去联接原语可以应用于此用途。
对于端口它是接收进程拥有和创建的。当进程撤消时相应端口也撤消。对于一般信箱，操作系统可以提供创建和撤消信箱的服务。
3,UNIX系统消息机制
UNIX系统 V的进程通信软件包 IPC提供了消息机制。
消息机制的数据结构
UNIX系统将消息分为消息首部和消息数据两部分。消息首部和消息头表的关系、消息首部和消息数据的关系见 下图 。
消息首部,在消息首部中记录有消息的类型、大小、指向消息数据区的指针、消息队列的链接指针等。
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -6
消息队列头表,消息队列头表的每一表项是作为一个消息队列的消息头。在消息头中包含了指向消息队列中第一个消息的指针和指向最后一个消息指针，队列中消息的数目、队列中消息数据的总字节数等。
队列 0
.
.
队列 i
消 息 首 部
msgh 0
消息缓冲区 0
消息首部
msgh 8
消 息 缓 冲区 8
消息首部
msgh 3
消息缓冲区 3
消 息 首 部
msgh 2
消息缓冲区 2
2001年 9月 20日 9时 1分 计算机操作系统
(3)管道通信
UNIX系统在 OS的发展上最重要的贡献之一便是该系统首创了管道（ pipes） 。
管道是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称为 pipe文件。 向管道（共享文件）
提供输入的发送进程（即写进程），以字符形式将大量的数据送入管道，而接收管道输出的接收进程（即读进程）可从管道中接收数据。管道通信是基于文件系统形式的一种通信方式。
管道分为无名管道和有名管道两种类型。 无名管道是早期
UNIX版本已提供的，它是一个只存在于打开文件机构中的一个临时文件，从结构上没有文件路径名，不占用文件目录项。
无名管道利用系统调用 pipe(filedes)创建，只用该系统调用所返回的文件描述符 filedes[2]来标识该文件。只有调用
pipe的进程及调用后该进程创建的子孙进程，才能识别此文件描述符，从而才能利用该文件（管道）进行父子或子、子之间通信。
2001年 9月 20日 9时 1分 计算机操作系统管道通信 -1
UNIX系统 V的管道文件最大长度为 10个盘块，核心为它设置了一个读指针和一个写指针。为了确保利用管道使进程间传送数据的正确性。系统在管道读写时设置互斥和同步机制，它首先保证写进程和读进程互斥地进行写和读，同时又要保证写和读的同步。即写进程将数据写入管道后，读进程才能来读取数据，如写进程未将数据写入管道，则读进程必须阻塞等待。如写进程将数据写满管道后读进程未来读，则发出写溢出，此时写进程必须阻塞等待。 与一般文件不同是管道数据的先进先出（ FIFO） 处理方式和管道文件数据不可再现性 。
即被读取的数据在管道中不能再利用，无名管道在关机后自动消失。
在 UNIX,MS-DOS系统中，用户可以在命令级使用管道，这时管道是一个程序的标准输出和另一个程序的标准输入之间的连接，管道命令用符号,|” 表示。
2001年 9月 20日 9时 1分 计算机操作系统父进程管道通信 -2
pipe使用
pipe系统调用的语法格式是,int pipe (filedes)
int filedes [2]；
核心创建一条管道完成下述工作：
a.分配一个隶属于 root文件系统的磁盘和内存索引结点 inode.
b.在系统打开文件表中分别分配一读管道文件表项和一写管道文件表项。
c.在创建管道的进程控制块的文件描述表（进程打开文件表 u-
ofile） 中分配二表项，表项中的偏移量 filedes[o]和 ditedes[1]
分别指向系统打开文件表的读和写管道文件表项。
系统调用所涉及的数据结构如下图所示。
例：
管道 CHAN1
子进程管道 CHAN2
2001年 9月 20日 9时 1分 计算机操作系统例题
有一阅览室,读者进入时必须先在一张登记表上进行登记,
该表为每一座位列一表目,包括座号和读者姓名 。 读者离开时要消掉登记信息,阅览室中共有 100个座位,请问：
为描述读者的动作,应编写几个程序？ 设置几个进程？ 进程与程序间的对应关系如何？
解 1：二个程序 。 管理员 1和管理员 2:管理员 1负责在读者进入时在一张登记表上进行登记,管理员 2负责读者离开时要消掉登记信息 。 二个进程,进程与程序间的对应关系一对一 。
var mutex,empty,full,Semaphore,=﹎﹎ A﹎﹎,﹎﹎ B﹎﹎,﹎﹎ C﹎﹎ 。
begin
parbegin
Manager1：
begin
repeat
Wait a reader in；
﹎﹎﹎ D﹎﹎﹎ ；
2001年 9月 20日 9时 1分 计算机操作系统例题 -1
﹎﹎﹎ E﹎﹎﹎ ；
Login a name in the register；
﹎﹎﹎ F﹎﹎﹎ ；
﹎﹎﹎ G﹎﹎﹎ ；
forever
end
Manager2：
begin
repeat
Wait a reader out；
﹎﹎﹎ H﹎﹎﹎ ；
﹎﹎﹎ I﹎﹎﹎ ；
Logout a name in the register；
﹎﹎﹎ J﹎﹎﹎ ；
﹎﹎﹎ K﹎﹎﹎ ；
forever
end
coend
end
2001年 9月 20日 9时 1分 计算机操作系统例题 -2
解 2：一个读者程序,每一个读者一个进程,进程与程序间的对应关系一对多 。
var empty,Semaphore,=﹎﹎ L﹎﹎；
begin
parbegin
Reader i：
Begin
﹎﹎﹎ M﹎﹎﹎；
Login a name in the register；
Read …,
Logout name in a register；
﹎﹎﹎ N﹎﹎﹎；
end
parend
end
A,B,C,L,(1)0; (2)1; (3)2; (4)100; (5)n;
D---K,M,N,(1)P(mutex); (2)V(mutex); (3)P(empty);(4)V(empty); (5)P(full); (6)V(full); (练习 )
2001年 9月 20日 9时 1分 计算机操作系统习题
1,对于记录型信号量,在执行一次 P操作时,信号量的值应当为﹎﹎ A﹎﹎； 当其值为﹎﹎ B﹎﹎ 时,进程应阻塞 。 在执行 V
操作时,信号量的值应当﹎﹎ C﹎﹎； 当其值为﹎﹎ D﹎﹎ 时,
应唤醒阻塞队列中的进程 。
A,C,(1)不变； (2)加 1； (3)减 1； (4)加指定数值； (5)减指定数值 。
B,D,(1)大于 0； (2)小于 0； (3)大于等于 0； (4)小于等于 0。
(解 )
2001年 9月 20日 9时 1分 计算机操作系统习题 -1
2.在操作系统中，解决进程间的﹎﹎ A﹎﹎ 两种基本关系，往往运用对信号量进行﹎﹎ B﹎﹎ 的﹎﹎ C﹎﹎,例如，为保证系统数据库的完整性，可以把信号量定义为某个库文件（或记录）的锁，初值为 1，任何进程存取该库文件（或记录）之前先对它作一个﹎﹎ D﹎﹎,存取之后对它作一个﹎﹎ E﹎﹎，
从而做到对该文件（或记录）任一时刻只有一个进程可存取，
但要注意使用不当引起的死锁。
A,(1)同步与异步； (2)串行与并行； (3)调度与控制； (4)同步与互斥。
B,(1)消息操作； (2)P-V操作； (3)开关操作； (4)读写操作。
C,(1)通信原语； (2)调度算法； (3)分配策略； (4)进程控制。
D,E,(1)联机操作； (2)V操作； (3)输出操作； (4)读操作；
(5)写操作； (6)P操作； (7)输入操作。
(解 )
2001年 9月 20日 9时 1分 计算机操作系统习题 -2
3。 有一阅览室，读者进入时必须先在一张登记表上进行登记，
该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信息，阅览室中共有 100个座位，请问：
a.为描述读者的动作,应编写几个程序？ 设置几个进程？ 进程与程序间的对应关系如何？
b.用类 Pascal语言和 P,V操作写出这些进程间的同步算法 。
(解 )
4.今有三个并发进程 R,M,P,它们共享一个缓冲区,R负责从输入设备读信息,每读一个记录后,把它存放在缓冲区,M在缓冲区加工读入的记录,P把加工后的记录打印输出,读入的记录经加工输出后,缓冲区中又可存放下一个记录 。 请用 P、
V操作为同步机制写出它们并发执行时能正确工作的程序
5.试述 消息缓冲队列通信机制通信原理 。 (解 )
(Synchronization and Communication
Among Processes )
教学目的：
在进程的控制的基础上这课引入进程同步和进程同步机制的概念,它对并发执行进程的推进序列加以限制以保证互斥使用临界资源或协同完成任务,解决程序并发执行时带来结果不可再现问题 。 这课介绍了用软件,硬件,信号量机制,AND型信号量集,一般信号量集等各种解决进程互斥同步问题的方法,
重点介绍了信号量机制的概念和用信号量机制解决进程互斥同步问题的方法 。
2001年 9月 20日 9时 1分 计算机操作系统教学要求：
熟悉 进程间制约关系，掌握临界资源和临界区概念，掌握进程同步和进程同步机制,熟悉 利用 软件方法和硬件技术解决进程同步机制。
熟练掌握信号量和 P,V操作的概念、定义和实质，熟练掌握利用信号量实现进程互斥和同步,熟悉 用信号量 描述前趋关系。
掌握 利用信号量解 生产者 -消费者问题,熟悉 利用信号量解 读者 -写者问题等经典同步问题，掌握进程同步分析方法。
了解 用 AND型 信号集机制、一般信号集机制 解 经典同步问题。
熟悉 进程通讯的 概念和共享存储器系统、消息传送系统、管道通信系统 三类高级 通讯 机制，掌握消息缓冲队列通信机制。
2001年 9月 20日 9时 1分 计算机操作系统
3.1进程同步 (Synchronization of
multiple processes)的基本概念进程间制约关系在多道程序环境下，系统中各进程以不可预测的速度向前推进，进程的异步性会造成了结果的不可再现性。为防止这种现象，异步的进程间推进受到二种限制：
1、资源共享关系（ Cooperation Among Processes by
Sharing）
多进程共享资源，运算上无关，但使用资源有关 ―― ＞
间接关系；
例如：打印机 ―― ＞ 互斥使用。对 CPU也是一种共享。排它性。
2001年 9月 20日 9时 1分 计算机操作系统进程同步的概念 -1
2、相互合作关系（直接关系）
（ Cooperation Among Processes by Communication）
为完成共同任务各个进程之间可能有的关系 ―― ＞ 利用同步机制 加以实现。
例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行，由于这三个进程间存在着相互合作的关系，
即先输入再计算、最后再打印的关系，所以这三个进程在并发执行时推进序列受到限制，要保证其合作关系正确，进程间这种关系称为同步关系。司机与售票员之间的关系。
例,A B（ 可在黑板画图）中间数据 N
3,主要目的：
使并发执行的各个进程之间能有效地共享资源和相互合作 ―― ＞可再现性。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.1 临界资源临界资源象打印机这类资源 一次只允许一个进程使用的资源称为临界资源 。或者：进程之间必须采用互斥方式共享的资源称为临界资源。
硬件资源 打印机、磁带机纸带机、读卡机软件资源 消息缓冲队列变量、中间结果数组缓冲区等共享资源：当然还有一类象磁盘等资源，它允许进程间共享，
即可交替使用。
临界资源又称独享资源。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.1 临界资源对于临界资源的理解：
生产者 -----消费者生产者：产生信息的进程；
消费者：使用 /消耗信息的进程；
例：输入 ---计算计算 ---打印 相对性。
P1 Pm
m
C1 Cq
B0 B1 …,…,.,……… Bn-1
2001年 9月 20日 9时 1分 计算机操作系统
3.1.1 临界资源规则：
（ 1）只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息。
（ 2）只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区。
用一个数组 buffer来表示上述具有 n个缓冲区的缓冲池；
In:表示输入指针；表示下一个可投放数据的缓冲区，每当生产者进程生产并投放一个消息后,in+1;
Out:表示输出指针；表示下一个可获取数据的缓冲区，每当消费者进程消费 /取走一个消息后,out+1;
循环缓冲 0,1,…,n-1; in:=(in+1)mod n;
out:=(out+1)mod n;
Counter:计数器，生产一个消息 -?buffer; +1
buffer-?取走一个消息； -1
解释 P62/p63
2001年 9月 20日 9时 1分 计算机操作系统
3.1.2临界区 (critical sections
临界区：
每个进程中访问临界资源的那段程序段称为临界区（临界段）。
一、临界区 (critical sections)的定义和进入
1、定义：
2001年 9月 20日 9时 1分 计算机操作系统一、临界区 (critical sections)的定义和进入
2、进入（可细讲）
例如进程 A的程序如下 (进程 B的程序类似 )：
A,begin
Input data 1 form I/O 1 ;
Computer…… ;
Print results 1 by printer ; A临界区
end
解决办法：申请进入、退出说明。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.2 临界区二,进程同步机制应遵循的原则进程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。
多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。 所有的进程同步机制应遵循：
空闲让进 。
当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。
忙则等待 。
当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其它试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
有限等待 。
对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入,饥饿,状态。
让权等待 。
当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。
例,p1,p2并发工作，若 P1先进入临界区，则先占用临界资源 R。 时间片到，
P2想进入临界区，就需忙则等待（释放 CPU）,有限等待，若 P1退出，则空闲让进 P2。
2001年 9月 20日 9时 1分 计算机操作系统进程同步机制
一个由临界区和剩余区 1和剩余区 2程序段组成的进程采用进程同步机制后的描述如下：
begin remainder section 1； 剩余区 1
进入区
critical section ； 临界区退出区
remainder section 2 ； 剩余区 2
end
进程同步机制在临界区前加上进入区，它负责对欲访问的临界资源状态进行检查，以决定是允许该进程进入临界区还是等待。同时在临界区后加上退出区，它负责释放临界资源以便其它等待该临界资源的进程使用。
实现进程互斥和同步的信号量机制有软件方法、硬件指令方法、信号量机制和管程等。
2001年 9月 20日 9时 1分 计算机操作系统
3.1.3 利用 软件方法解决 进程互斥 (Mutual
Exclusion )问题问题：有 二个进程 Pi和 Pj互斥共享 临界资源 R，
begin
parbegin
Pi,...…
Pj,.....…
parend
end
下列 算法 只写出进程 Pi程序。
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -1
算法 1
该算法设置了一个公用整型变量 turn,用于指示被允许进入临界区的进程编号，既若 ture=0,表示允许 Pi进程进入临界区。
Pi进程,Pj进程,
repeat repeat
while turn≠i do no op while turn≠j do no op
Critical section Critical section
turn=j turn=i
Remain Section Remain Section
until false until false
该算法可确保每次只允许一个进入临界区。但采用强制两个进程轮流进入临界区，很容易造成资源利用不充分。当 Pi
退出后置 turn为 j,但 Pj并未使用 CS,Pi又想使用时，则无法置 turn= i,不能进入 CS,违背,空闲让进,。
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -2
算法 2:
算法基本思想：在每一个进程访问临界区资源之前，先动查看一下临界资源是否正被访问，若正被访问，该进程需等待，
否则才进入自己的临界区。为此设置了一个布尔型数组 flag[]，
如第 i个元素值为 false--- flag[i]=false----表示 Pi进程未进入临界区，值为 true--- flag[i]=true------表示 Pi进程进入临界区。
Pi:repeat Pj:repeat
while flag[j] do no_op; while flag[i] do no_op;
flag[i]:=true; 2 flag[j]:=true;
critical_section; 1 critical_section;
flag[i]:=false; flag[j]:=false;
remainder section; remainder section;
until false until false
会出现 Pi和 Pj同时 进入临界区错误，违背忙则等待。
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -3
算法 3:
算法 2是先检测对方进程状态标志后再置自己标志，由于在检测和放置中可插入另一个进程时检测操作，会造成二个进程在分别检测后同时进入临界区。为此算法 3采用先设置自己标志后再检测对方状态标志，它的程序如下，布尔型数组 flag[]，
如第 i个元素值为 false--- flag[i]=false----表示 Pi进程未进入临界区，值为 true--- flag[i]=true------表示 Pi进程进入临界区 /要求进入 CS。
Pi:repeat Pj:repeat
flag[i]:=true; 2 flag[j]:=true;
while flag[j] do no_op; while flag[i] do no_op;
critical_section; 1 critical_section;
flag[i]:=false; flag[j]:=false;
remainder section; remainder section;
until false until false
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -4
算法 4(Peterson 1981)：
该算法组合了算法 1和算法 4，为了防止二进程进入临界区而无限期等待，又设置变量 turn,表示允许进入临界区的编号，每个进程在先设置自己标志后再设置 turn标志，不允许另一个进程进入，这时再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当二个进程同时要求进入临界区时，只允许一个进程进入临界区。
Pi,repeat
flag[i]:=true; turn:=j;
while (flag[j] and turn=j) do no_op;
critical_section; 1
flag[i]:=false;
remainder section;
until false
2001年 9月 20日 9时 1分 计算机操作系统利用 软件方法解决 进程互斥问题 -4
Pj,repeat
flag[j]:=true; turn:=i;
while (flag[i] and turn=i) do no_op;
critical_section;
flag[j]:=false;
remainder section;
until false
2001年 9月 20日 9时 1分 计算机操作系统
3.1.4 利用 硬件技术实现互斥
1.提高临界区代码执行中断优先级这种方法在 UNIX和 Windows NT中都使用，它是在单机系统中有效地实现互斥的一种方法。
因为在传统操作系统中，打断进程对临界区代码的执行只有中断请求、中断一旦被接受，系统就有可能调用其它进程进入临界区，并修改此全局数据库。所以用提高临界区中断优先级方法就可以屏蔽了其它中断，保证了临界段的执行不被打断，从而实现了互斥。
在多处理机情况下，用提高临界段代码执行的中断优先级方法是无法保证互斥的，因为在一个处理机上提高中断优先级并不能阻止其它处理器上的中断，所以必须采用其它方法。
2001年 9月 20日 9时 1分 计算机操作系统
2,检测和设置（ TS） 硬件指令
许多大型机（如 IBM370等）和微型机（如 Intel × 86等）中都提供了专用的硬件指令，这些指令全部允许对一个字中的内容进行检测和修正，或交换两个字的内容。特别要指出的是这些操作都是在一个存储周期中完成，或者说由一条指令来完成，用这些指令就可以解决临界区问题了。
在单机系统中，由于中断的原因，使得一个进程在对一个公用变量先取来并检测其值，然后修改的这两个动作中，可以插入其它进程对此公用变量的访问和修改，从而破坏了此公用变量数据的完整性和正确性。在多机系统中，多处理机共享主存，因而使得某处理机可插入另一处理机的两个存储访问周期之间，访问并修改此共享变量。
2001年 9月 20日 9时 1分 计算机操作系统检测和设置（ TS） 硬件指令 -1
对于同一主存块访问要求，即使两个处理机同时提出，存储控制逻辑也只能让其中之一先访问，但在一个处理机的两个存储周期间则可以插入另一个处理机的存储周期。现在用一条指令来完成检测和修改两个功能，这样中断和插入另一处理机的存储周期均不可能，所以不会影响此公用变量数据的完整性。
检测和设置（ TS） 的功能可用 PASCAL语言描述如下：
function TS (var lock,boolean):boolean
begin
TS = lock ；
lock:=true ；
end
这条指令在 Z-8000中称为 TEST指令，在 IBM370中称为 TS指令。
每次调用 TS函数，都把 lock置为 true,Lock=false,表示该资源空闲； Lock=true.表示该资源正在被使用。
2001年 9月 20日 9时 1分 计算机操作系统检测和设置（ TS） 硬件指令 -2
用这些硬件指令可以简单有效地实现互斥。其方法是为每个临界段或其它互斥资源设置一个布尔变量，例如称为 lock。
当其值为 false则临界区末被使用，反之则说明正有进程在临界区中执行。于是某进程用 TS指令实现互斥的程序结构为
（设为无限循环进程）：
P1 repeat P2 repeat
...,.,
while TS(lock) do skip ； while TS(lock) do skip ；
进程临界区 CS ； 进程临界区 CS ；
lock,=false ； lock,=false ；
...,..
until false; until false;
WindowsNT 内核用来达到多处理器互斥的机制,转锁,,它类同于 TS指令机制。
分析（略）
2001年 9月 20日 9时 1分 计算机操作系统
3、利用 SWAP指令实现互斥
1 SWAP指令
PROCEDURE SWAP(var a,b:boolean)
VAR temp:boolean;
begin
temp:=a;
a:=b;
b:=temp
end
2 利用 SWAP实现进程互斥
lock:全局变量 TRUE-----有进程在使用 CR；
FALSE------无进程在使用 CR。
表示有无其它进程进入临界区。
2001年 9月 20日 9时 1分 计算机操作系统
3、利用 SWAP指令实现互斥
VAR lock:boolean:=false;
Begin
parbegin
p1,begin p2,begin
repeat repeat
key:=true; key:=true;
repeat repeat
swap(lock,key); swap(lock,key);
until key:=false; until key:=false;
临界区； 临界区；
lock:=false; lock:=false;
剩余代码区； 剩余代码区；
until false until false
parend
End.
无法满足“让权等待”原则。
2001年 9月 20日 9时 1分 计算机操作系统
3.2 信号量 (Semaphores)机制
3.2.1 整型信号量机制一、整型信号量
S,整型信号量 ; 原子操作：
wait(s):while s<=0 do no-op
s:=s-1;（ P操作）
signal(s):s:=s+1; （ V操作）
信号量的使用：必须置一次且只能置一次初值，初值不能为负数，只能执行 P,V操作,P,申请一个资源； V,释放一个资源。资源能否使用由 wait(s)来判断。
二、利用信号量实现互斥
2001年 9月 20日 9时 1分 计算机操作系统
var mutex:=semaphore:=1 ；
begin
parbegin
P1:begin P2:begin
REPEAT REPEAT
…… ； …… ；
wait(mutex) ； wait(mutex) ；
Print results1 by printer; Print results2 by printer;
signal(mutex) ； signal(mutex) ；
until false until false
end end
parend
End.
Semaphore可看作是一个整型信号量的数据类型。
分析（略）
3.2.1 整型信号量机制 ---------二、利用信号量实现互斥
2001年 9月 20日 9时 1分 计算机操作系统
3.2.1 整型信号量机制 ----三、利用信号量描述前趋关系
P70
2001年 9月 20日 9时 1分 计算机操作系统
3.2 信号量 (Semaphores)机制
1965年，荷兰学者 Dijkstra提出信号量机制,它从整型信号量机制发展到记录型信号量机制，进而发展为,信号集,机制。
问题：整型信号量即可描述，为什么要引入记录型？
答案：前者有一致命弱点，无法实现让权等待，一直在空踏步，消耗时间片，并不释放 CPU。
解决方法：进程进入临界区之前先检测临界资源有无，若无 CR,则由执行 ---阻塞，不再空踏步。但有可能出现多个进程等待同一资源情况,----引入记录型,s.value表示资源数； s.L表示阻塞队列。
3.2.2 记录型信号机制
1.记录型信号量结构在信号量机制中信号量是代表资源物理实体的数据结构,记录型信号量的数据结构 描述如下：
type semaphore=record
value,integer;
L,pointer of PCB;
end
信号量的值只能通过两个原子操作,wait/P,signal/V操作来改变，
它代表分配资源和释放资源。
2001年 9月 20日 9时 1分 计算机操作系统
2 信号量的类型信号量按联系进程的关系分成二类：
公用信号量（互斥信号量）,它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加 P,V操作，即都可申请和释放该临界资源，其初始值置为 1。信号量 mutex取值意义如下：
mutex,value ＝ 1 ； 表示资源空闲，可供使用。
＝ 0 ；表示资源已被占用，无其它进程等待。
＝ -n ； 表示资源已被占用，还有 n个进程因等待资源而阻塞。
专用信号量（同步信号量）,它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加 P操作（即可申请资源），而由其合作进程对它施加 V操作（即释放资源）。
2001年 9月 20日 9时 1分 计算机操作系统
3,P-V操作 (wait(s)和 signal(s) 操作 )
对信号量施加 P,V操作代表申请和释放资源。 P-V操作描述如下：
proceduce wait(S)
var S:semaphore ；
begin
S.value=S.value-1 ； 记录型和整型区别：先 -1后判别
If S.value<0 then block(S.L) ；
end
Procefuce signal(S)
Var S:semaphore ； ;
begin
S.value=S.value+1 ；
If s.value≤0 then wakeup(S.L) ；
end
解释（略） (练习 )
2001年 9月 20日 9时 1分 计算机操作系统
（ 4） 利用信号量实现进程互斥为使多个进程能互斥地访问某临界资源，只需为该资源设置一个互斥信号量 mutex,并设其初值为 1，然后将各进程的临界区
CS置于 P（ mutex） 和 V(mutex)操作之间即可。利用信号量实现共享打印机的 A,B两进程互斥的类并行 PASCAL程序描述如下：
此例同整型信号量之例，对照讲。
2001年 9月 20日 9时 1分 计算机操作系统利用记录型信号量实现进程互斥 -1
var mutex:=semaphore:=1 ；
begin
parbegin
P1:begin P2:begin
repeat repeat
wait(mutex) ； wait(mutex) ；
Print results1 by printer; Print results2 by printer;
signal(mutex) ； signal(mutex) ；
Until false; Until false;
end end
parend
end (练习 )
Mutex:记录型信号量，初值为 1。
2001年 9月 20日 9时 1分 计算机操作系统利用记录型信号量实现进程互斥 -2
分析：初始时,mutex.value:=1; mutex.L=NIL 。
设 P2先执行,WAIT(mutex);
mutex.value:= mutex.value:-1:=0-----<0不成立
P2进入临界区执行，未使用完（时间片到）退出执行，
由执行 ----就绪，
P1被调度由就绪 ----执行，执行 WAIT(mutex)，
mutex.value:= mutex.value:-1:=0-1,=-1<0成立，则阻塞 P1----BLOCK（ mutex.L ） **（ 1） 此处与整型信号量不同，
整型信号量中 P1在消耗时间片，未实现“让权”，而此时阻塞，释放 CPU实现“让权等待”。 再次调度
P2从就绪 ---执行，使用临界资源完毕后，执行 signal(mutex)
mutex.value:= mutex.value+1:=0-----<=0成立,wakeup(mutex.L),把
P1唤醒，从阻塞 ----就绪,P2继续执行，时间片用完,P2由执行 -----就绪，
P1调度执行,**（ 2） 此处与整型信号量不同，整型信号量中现场在
WAIT(mutex) 之前，而此时现场在 WAIT(mutex) 之后，不用再执行
WAIT(mutex) 了，直接进入临界区。
2001年 9月 20日 9时 1分 计算机操作系统
(5)利用信号量实现进程同步利用信号量能解决进程间的同步问题，这里以下图所示的计算进程 C和打印进程 P通过缓冲区 Buffer传送数据的同步问题为例说明。
Buffer
C P
2001年 9月 20日 9时 1分 计算机操作系统利用信号量实现进程同步 -1
C和 P两进程基本算法如下：
C,begin P,begin
repeat repeat
Compute next number ; take from Buffer ;
add to Buffer ; print last number ;
until false until false
end end
C和 P两进程并发执行，必须在执行序列上遵循以下规则，才能避免错误。
只有当 C进程把数据送入 Buffer后,P进程才能从 Buffer中取出数据来打印，否则 P进程只能等待。
只有当 P进程从 Buffer中取走数据后,C进程才能将新计算的数据再存入 Buffer,否则 C进程也只能等待。
2001年 9月 20日 9时 1分 计算机操作系统利用信号量实现进程同步 -2
为了实现进程同步，需采用同步信号量。为了满足第一条同步规则，设置一个同步信号量 full,它代表的资源是缓冲器满，它的初值为 0。这个资源是 P进程所拥有,P进程可以申请该资源，对它施加 P操作，如条件满足 P进程可从
Buffer中取数。而 P进程的合作进程 C对 full信号量施加 V
操作，即它可释放该资源。当 C进程将数据存入 Buffer后，
即可释放该资源供 P进程再使用。同样为了满足第二条同步规则，设置另一个同步信号量 empty,它代表的资源是缓冲器空，它的初值为 1 。缓冲器空这个资源是进程 C所拥有，它可以申请该资源，对它施加 P操作。而它的合作进程 P对 empty信号量施加 V操作。
实现 C和 P两进程同步的类 PASCAL程序：
2001年 9月 20日 9时 1分 计算机操作系统
var,empty,full:semaphore:=1,0 ；
begin
parbegin
C,begin
repeat
Compute next number ；
P(empty) ；
Add to buffer ；
V(full) ；
until false
end
P,begin
repeat
P(full) ；
Take from Buffer ；
V(empty) ；
Print last number ；
until false
end
parend
end
2001年 9月 20日 9时 1分 计算机操作系统
(6)利用信号量描述 前趋关系进程间同步关系也可用前趋图表示。 C和 P两进程间先计算好再打印同步关系用前趋图表示如下：
对应这个前趋关系可设置同步信号量 full,它为后继进程
P拥有，初值为 0。它的并发执行程序如下：
var full,semaphore,=0;
begin
parbegin
C,begin Compute ； V(full) ； end
P,begin P(full) ； Print ； end
parend
end
C P
2001年 9月 20日 9时 1分 计算机操作系统
3.2.3 信号量集机制一,AND型 信号集机制以前的规定都是针对共享一个 CR而言，若共享多于一个 CR
A … B …
wait(Dmutex) wait(Emutex)
wait(Emutex) wait(Dmutex)
临界资源 D,E 临界资源 D,E
… …
分析 （略） -----------------死锁。
解决办法,Swait(Dmutex,Emutex),对 2个信号量同时进行检测，
避免死锁。
AND同步机制的主要思想：将进程在整个运行期间所需的所有临界资源，一次性地全部分配给进程，待该进程使用完后一起释放。资源分配也采取原子操作方式。
2001年 9月 20日 9时 1分 计算机操作系统
3.2.3 信号量集机制
Swait,Ssignal操作如下：
Swait(S1,S 2,…,S n )
if S1 >= 1 and …..and S n >=1 then for i:=1 to n do Si =
Si - 1 ; endfor
else
Place the executing process in the waiting queue of the
first Si with Si< 1 and set its program counter to the
beginning of the the Swait operation.
endif
Ssignal(S1,S 2,…,S n )
for i:=1 to n do Si = Si + 1 ;
Remove all the process waiting in the queue associated with
Si into the ready queue.
Endfor **回到现场时从 Swait()前开始执行。
2001年 9月 20日 9时 1分 计算机操作系统
3.2.3 信号量集机制二,一般 信号集机制
1、引入原因：
（ 1）前面所讲的 wait与 signal操作只对信号量做 +1/-1操作，
既每次只能获得 /释放一个单位的临界资源。如果一次需要 N
个资源时，仅需进行 N次 wait操作，效率低下。
（ 2）当资源数目低于某一下限值 T时，不予分配。所以每次分配前，必须测试该资源的数量是否大于测试值 T。
因此引入 一般 信号集机制。
2。定义：
相应的 Swait,Ssignal操作如下：
2001年 9月 20日 9时 1分 计算机操作系统一般 信号集机制 -1
Si （ S1 ~Sn ）,每种 临界资源的数目。
d I（ d 1 ~ d n ）,每次申请的 临界资源数目。
ti（ t 1~ t n）,每个 临界资源对应的下限值。
Swait(S1,t 1,d 1,…,S n,t n,d n )
if S1 >= t 1 and …..and S n >=t n then
for i:=1 to n do Si = Si - d i ;
endfor
else
Place the executing process in the waiting queue of the first Si with Si < t i and
set its program counter to the beginning of the the Swait operation.
endif
Ssignal(S1,d 1,…,S n,d n )
for i:=1 to n do Si = Si + d i ;
Remove all the process waiting in the queue associated with Si into the ready
queue.
endfor
2001年 9月 20日 9时 1分 计算机操作系统一般 信号集机制 -2
特殊情况：
1,Swait(s,d,d):
只有一个资源被申请，即信号量集中只有一个信号量。每次允许申请 d个资源，当系统中现有资源数小于 d时，不允许分配。
2,Swait(s,1,1),1中的特例，只有一个资源被申请，即信号量集中只有一个信号量。每次允许申请 1个资源，当系统中现有资源数小于 1时，不允许分配。
S>1-----------记录型信号量； S=1----------互斥信号量。
3,Swait(s,1,0),只有一个资源被申请，即信号量集中只有一个信号量。每次允许申请 0个资源，当系统中现有资源数小于 1时，不允许分配。换言之,s>=1时，允许多个进程进入某特定 CS,s<1（ s=0） 时，任何进程都不进入该 CS,相当于一个可控开关。
2001年 9月 20日 9时 1分 计算机操作系统
3.3利用信号量解 经典进程同步问题经典进程同步问题是从进程并发执行中归纳的典型例子，这些问题常用来测试新的同步机制可行性。主要的经典同步问题有生产者 -消费者问题、读者 -写者问题、哲学家进餐问题等。
（ 1）生产者 -消费者问题 （ producer-consumer Problem ）
生产者 -消费者问题是最著名的同步问题，它描述一组生产者
（ P1 …… Pm） 向一组消费者（ C1…… Cq） 提供消息。它们共享一个有界缓冲池（ bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息，如下图所示。生产者 -消费者问题是许多相互合作进程的一种抽象。
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -1
假定缓冲池中有 n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，
它只允许一个生产者投入消息 ;
或者一个消费者从中取出消息 ;
即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。
所以必须设置互斥信号量 mutex,它代表缓冲池资源，它的数值为 1。
P1 Pm
m
C1 Cq
B0 B1 …,…,.,……… Bn-1
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -2
与计算打印两进程同步关系相同，生产者和消费者二类进程 P
和 C之间应满足下列二个同步条件：
只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。
只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。
为了满足第一个同步条件，设置一个同步信号量 full,它代表的资源是缓冲区满，它的初始值为 0，它的值为 n时整个缓冲池满。这个资源是消费者类进程 C所拥有,C进程可以申请该资源，对它施加 P操作，而 C进程的合作进程生产者进程 P对它施加 V操作。同样为了满足第二个同步条件，设置另一个同步信号量 empty,它代表的资源是缓冲区空，它的初始值为 n，
表示缓冲池中所有缓冲区空。
用类并行 PASCAL语言和信号量机制解生产者 -消费者问题程序：
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -2
var mutex,empty,full:semaphore:=1,n,o ；
Buffer,array [0…… n-1] of message ；
in,out,o…… n-1:=0,0 ；
begin
parbegin
P,begin
repeat
Produce a new message in nextp ；
P (empty) ；
P (mutex) ；
Buffer[in]=nextp ；
in,=(in+1) mod n ；
V (mutex) ；
V (full) ；
until false
end
2001年 9月 20日 9时 1分 计算机操作系统利用信号量解 经典进程同步问题 -4
C,begin
repeat
P (full) ；
P (mutex) ；
nextc:= buffer[out] ；
Out,= (out+1) mod n ；
V (mutex) ；
V (empty) ；
Consume message in nextc ；
until false
end
parend
End
利用 AND信号量解决生产者 —消费者问题（ P74）。
2001年 9月 20日 9时 1分 计算机操作系统
（ 2） 读者 -写者问题（ Readers/Writers Problem）
一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称读者，而另一些进程则要求修改数据集内容，它称写者，几个读者可以同时读些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。
设置互斥 信号量 wmutex 表示写者间、读者和写者间互斥，
读者和写者主要 程序如下：
reader,writer:
第一个读者到时 P（ wmutex） P（ wmutex）
Read Text Write Text
最后 一个读者离开时 V（ wmutex） V（ wmutex）
2001年 9月 20日 9时 1分 计算机操作系统读者 -写者问题 -1
用 readcount变量来记录读者数，读者 程序为：
if readcount=0 then P（ wmutex） ;
readcount= readcount+1;
Read Text
readcount= readcount-1;
if readcount=0 then V（ wmutex） ;
由于 readcount是读者间共享变量，属于临界资源，它也需互斥，为此又增设互斥信号量 rmutex.
用类并行 PASCAL语言和信号量机制解读者 -写者问题程序：
2001年 9月 20日 9时 1分 计算机操作系统读者 -写者问题 -2
Var rmutex,wmutex,semaphore:=1,1 ;
readcount,integer,=0 ;
begin
parbegin
reader:begin writer:begin
repeat repeat
P(rmutex) P(wmutex);
if readcount=0 then P(wmutex); Write Text;
readcunt=readcount+1; V(wmutex);
V(rmutex) until false
Read Text end
P(rmutex)
readcount=readcount-1 ;
if readcount=0 then V(wmutex) ;
V(rmutex)
until false
end
parend
end
2001年 9月 20日 9时 1分 计算机操作系统
（ 3） 进程同步的分析
用信号量机制解决进程同步问题需在程序中正确设置信号量和在适当位置安排 P,V操作。例如生产者 -消费者问题中，
用于互斥进入临界区的 P（ mutex）,V(mutex)语句需紧靠着临界区前和后，而生产者用于同步的 P（ empty） 和 V（ full）
(消费者为 P（ full） 和 V(empty))语句相对临界区就在外面一层，格式如上程序所述。如在以上问题中生产者的 P
（ empty） 和 P(mutex)先后位置对调，相应消费者的 P（ full）
和 P（ mutex） 先后位置也对调，则生产者和消费者在并发执行时，在某个执行序列会出现问题。
下面介绍如何寻找会发生问题的那个执行序列,分析方法用下表表示。表左边是生产者和消费者二进程推进序列，此推进序列需用户寻找；表中间是该操作执行后信号量的变化值,表中信号量有 mutex,empty和 full； 表的右边是该操作执行后引起进程 PCB的队列变化 。表中队列有就绪队列 RL，
因分别等待 mutex,empty,full信号量而阻塞的队列 QmL、
QeL,和 QfL。
2001年 9月 20日 9时 1分 计算机操作系统进程同步的分析 -1
在表中已找到一个推进序列。该序列先执行消费者进程，
由于消费者进程交换了 P操作，消费者进程在先后执行 P
（ muyex） 和 P（ full） 后阻塞在等待 full信号量的队列中。
这时只能执行生产者进程，由于生产者进程也交换了 P操作，在生产者进程执行了 P（ mutex） 操作后，生产者进程阻塞在等待 mutex信号量的队列中。这样生产者和消费者两进程分别阻塞在等待 mutex和 full信号量的队列，没有进程可以向前推进，系统进入死锁状态。这说明在生产者
-消费者问题中对同步信号量和互斥信号量的二个 P操作的是不能颠倒，而对互斥信号量和同步信号量的二个 V操作的顺序交换影响不大。
生产者、消费者交换 P操作后发生问题的那个执行序列：
2001年 9月 20日 9时 1分 计算机操作系统进程同步的分析 -2
操 作 操作引起 （信号量）
变化操作引起 ( 队列 ) 变化事件 生产者
(P)
消费者
(C)
m u t e x e m p t y full RL Q mL QeL QfL
0 / / 1 n 0 P,C / / /
C
1
/ P
( m u t e x )
0 n 0 P / / /
C
2
/ P ( f u l l ) 0 n -1 P / / C
P
1
P r a d u c e 0 n -1 / / / C
P
2
P
( m u t e x )
-1 n -1 / P / C
2001年 9月 20日 9时 1分 计算机操作系统
2,用 一般 信号集机制解读者 -写者问题
var RN integer ;---同时最多允许 RN个读者读。
L,mx,semaphore,=RN,1 ;
begin
parbegin
reader,begin writer,begin
repeat repeat
Swait (L,1,1 ) ; Swait (mx,1,1,L,RN,0 );
Swait (mx,1,0 ) ; perform write operation
perform read operation Ssignal (mx,1 ) ;
Ssignal (L,1) ; until false ;
until false ; end
end
parend
end
RN---同时最多允许 RN个读者读。所以引入一个信号量，初值为 RN,通过执行
Swait (L,1,1 )操作，控制读者数目，当有一个读者进入时,L就 -1，
直到 RN个读者全部进入,L为 0,如果有 RN+1个读者进入,L<0,则阻塞。
mx:互斥信号量，写 -写 /读 -写。
2001年 9月 20日 9时 1分 计算机操作系统
3.3.3哲学家进餐问题哲学家就餐问题五个哲学家围坐在一个园桌周围，每个哲学家面前都有一盘通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个盘子间有一把叉子，餐桌如右图。
哲学家的生活包括两种活动：即吃面条和思考。当哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次拿一把，不分先后次序，如果成功，他就开始吃面条，吃完后放下叉子，继续思考。试用信号量写出哲学家行为的程序描述，
要求不能让某个（或某些哲学家饿死） 。
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
0#人
1#人
2#人 4#人
5#人
0#筷
1#筷
2#筷
3#筷
4#筷
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
1、一个简单解法：
用一个信号量表示一只筷子，这五个信号量 ---信号量数组，其描述为：
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
每个哲学家的进程都类似
begin Pi,repeat
parbegin wait(chopstick[i]);
P0; wait(chopstick[i+1] MOD 5);
P1; …
P2; eat;
P3; …
P4; signal(chopstick[i]);
parend signal(chopstick[i+1] MOD 5);
end …
think;
until false;
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题分析,i=0时,0#哲学家拿到 0#筷,0#哲学家时间片退出。设 1#哲学家饿，
i=1时,1#哲学家拿到 1#筷,1#哲学家时间片退出。设 2#哲学家饿，
i=2时,2#哲学家拿到 2#筷,2#哲学家时间片退出。设 3#哲学家饿，
i=3时,3#哲学家拿到 3#筷,3#哲学家时间片退出。设 4#哲学家饿，
i=4时,4#哲学家拿到 4#筷,4#哲学家时间片退出。 0#哲学家回来，
执行 wait(chopstick[i+1] MOD 5);显然阻塞。同理 1,2,3,4被阻塞 -----死锁，如何解决？有 3种办法：
1）仅当哲学家的左右 2只筷子都可用时，才允许他吃饭 -----AND同步问题。
用 AND信号量解决：
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
begin Pi,repeat
parbegin think;
P0; Swait(chopstick[i+1] MOD 5,chopstick[i]);
P1; …
P2; eat;
P3; …
P4; Ssignal(chopstick[i+1] MOD 5,chopstick[i]);
Parend …
end until false;
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
2)至多允许 4个哲学家同时吃饭，以保证至少有一个人可以吃到饭，吃毕 ----2只筷子 ------其它人可以吃了。
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
man:semaphore:=4;{哲学家计数器，初始化为 4，若第五个人到则阻塞 }
begin Pi,repeat
parbegin wait(man);
P0; wait(chopstick[i]);
P1; wait(chopstick[i+1] MOD 5);
P2; eat;
P3; signal(chopstick[i]);
P4; signal(chopstick[i+1] MOD 5);
Parend signal(man);
end until false;
2001年 9月 20日 9时 1分 计算机操作系统哲学家就餐问题
3)规定奇数号哲学家先拿他左边的筷子,1#,2#哲学家争夺 1#筷子,
偶数号哲学家先拿他右边的筷子,3#,4#哲学家争夺 3#筷子,
即 5个哲学家都先争夺奇数号筷子，获得后，再去争夺偶数号筷子，最后总有一个哲学家能获得 2只筷子而进餐。
VAR chopstick:array[0..4] of semophore:=(1,1,1,1);
begin Pi/奇数,repeat
parbegin …
P0; wait(chopstick[i]);
P1; wait(chopstick[i+4] MOD 5);
P2; eat;
P3; signal(chopstick[i]);
P4; signal(chopstick[i+4] MOD 5);
Parend think;
end until false;
3#人
1#人
2#人
4#人
5#
人
1#筷
2#筷
3#筷
4#筷
5#筷
2001年 9月 20日 9时 1分 计算机操作系统补充题 1：
有十个读者和两个编辑同时处理一篇文章,对于读操作是可以同时进行的,若有读者正在读这篇文章,编辑就不能工作,若编辑正在处理这篇文章,读者就不能作读操作,编辑与编辑的工作也是互斥的,试用信号 量 写出读者与编辑之间协同工作的程序描述 。
2001年 9月 20日 9时 1分 计算机操作系统量
2001年 9月 20日 9时 1分 计算机操作系统解：
mutex:用于读者与编辑、编辑与编辑的互斥信号量，初值为 1；
mutex1:用于对 couter操作的互斥的信号 量,初值为 1。
2001年 9月 20日 9时 1分 计算机操作系统补充题 2：
一个文件 F,只供多个进程读，把进程分为 A,B两类，有规定：
1）只有同类进程才能同时读文件 F。
2） 系统中并发执行的进程数不能超过 N（ N>0） 个。
试用信号量写出 A,B两类进程的算法，并说明所用信号量含义。
2001年 9月 20日 9时 1分 计算机操作系统
3.5进程 通信进程通信指进程之间的信息交换，信息量有多少：
进程的同步与互斥 -----低级通信生产者 — 消费者,同步 /互斥信号量作为通信工具（信号量有多有少）缺点 （ 1）效率低，一次一个消息
---生产者 — 消费者 （ 2）对用户不透明，用户事事亲为,OS只提供共享存储器。编写麻烦，不方便。
高级通信机制可归结为三大类：共享存储器系统，消息传送系统和管道通信系统。
3.5.1进程通信的类型
（ 1）共享存储器系统（内存）
1,基于共享数据结构的通信方式在这种通信方式中，要求诸进程公用某个数据结构，进程通过它们交换信息。如在生产者 -消费者问题中，就是把缓冲池（有界缓冲区）这种数据结构用来作通信的。这种通信方式是低效的，只适用传送少量的数据。
2001年 9月 20日 9时 1分 计算机操作系统基于共享存储区的通信方式 -1
进程 A 进程 B
虚空间 内存空间 虚空间
A正文
A数据
A栈共享存储器
B正文
B数据
B栈
2001年 9月 20日 9时 1分 计算机操作系统
（ 2） 消息传递系统（ Message passing system）
消息传递系统分为直接通信方式和间接通信方式两种。
1,直接通信方式这是指发送进程利用 OS提供的发送命令直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程利用 OS提供的接收命令直接从消息缓冲队列中取得消息。此时要求发送进程和接收进程都以显示的方式提供对方的标识符，通常系统提供下述两条通信原语：
Send(Receiver,message) ；
Receive(Sender,message) ； 或 (Receive (message)) ；
直接通信的实例 -消息缓冲队列通信机制。
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -1
消息缓冲队列通信原理消息缓冲队列通信机制的原理是：由系统管理一组缓冲区，
其中每个缓冲区可以存放一个消息。当发送进程要发送消息时先要向系统申请一个缓冲区，然后把消息写进去，接着把该缓冲区连接到接收进程的消息缓冲队列中。接收进程可以在适当的时候从消息缓冲队列中摘下消息缓冲区，读取消息，
并释放该缓冲区。
消息缓冲队列通信的数据结构有消息缓冲区和进程 PCB中有关通信的扩充数据项，消息缓冲区描述如下：
type message buffer=record
sender ； 发送进程的标识符
size ； 消息长度
text ； 消息正文
next ； 指向下一个消息缓冲区的指针
end
2001年 9月 20日 9时 1分 计算机操作系统图,消息缓冲队列通信的发送和接收过程系统管理的－组缓冲区进程 A
进程 B PCB 进程 B
.
mutex
sm
mq
………,
.
.
send(B,a);
sender,A
size,13
text,
How are
you?
Next
send,A
size,13
text:
How are
you?
Next:
sender,A
size,5
text,Hello
Next,
sender,A
size:13
text:
How are
you?
Next:0
sender,A
size,5
text,Hello
Next:
.
.
receive(b);
sender,A
size,5
text,Hello
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -2
PCB 有关通信的扩充数据项
type PCB = record
.
mutex ； 消息缓冲队列互斥信息量 ；
Sm ； 消息缓冲队列资源信息量 ；
mq ； 消息缓冲队列首指针 ；
,
End
(练习 )
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -3
发送原语
Proceduce send (receiver,a)
begin
getbuf(a.size,i) ；
i.sender = a.sender i.size = a.size ；
i.text = a.text ； i.next = 0 ；
getid (PCB set,receiver,j) ；
P(j.mutex) ；
insert(j.mq,i) ；
V(j.mutex) ；
V(j.Sm) ；
end
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -4
接收原语
proceduce receive(b)
begin
j,= internal name ；
P (j.Sm) ；
P (j.mutex) ；
Remove(j.mq,i ) ；
V(j.mutex) ；
b.sender,=i.sender ；
b.size,=i.size ；
b.text,=i.text ；
Releasebuf(i) ；
end
2001年 9月 20日 9时 1分 计算机操作系统
2.间接通信方式
在间接通信情况，消息不直接从发送者发送到接收者，而是发送到暂存消息的共享数据结构组成的队列，这个实体称为 信箱 （ mailbox）,因此二个进程通信情况，一个进程发送一个消息到某个信箱，而另一个进程从信箱中摘取消息。
间接通信的使用好处是增加了使用消息的灵活性。发送者和接收者的关系可能是一对一、多对一，一对多或多对多。
一对一的关系允许一个专用通信链路用于二个进程间的交互，
它能使俩进程间交互不受其它进程错误干予的影响，多对一的关系对客户／服务器交互特别有用，一个进程对多个其它进程（用户）提供服务。在这种情况信箱经常称作为端口
(port)。 一对多关系允许一个发送进程和多个接收进程交互，
这可用来将消息广播 (broadcast)给一组进程。
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -5
进程与信箱的联系有二种：静态和动态。端口经常与特定的进程保持静态的联系，即端口创建后永久地分配给某个进程。
同样一对一关系是典型地规定为静态的和永久的。当有许多发送者时，一个发送者与信箱的联系可以动态发生，例如联接（ conect） 和去联接原语可以应用于此用途。
对于端口它是接收进程拥有和创建的。当进程撤消时相应端口也撤消。对于一般信箱，操作系统可以提供创建和撤消信箱的服务。
3,UNIX系统消息机制
UNIX系统 V的进程通信软件包 IPC提供了消息机制。
消息机制的数据结构
UNIX系统将消息分为消息首部和消息数据两部分。消息首部和消息头表的关系、消息首部和消息数据的关系见 下图 。
消息首部,在消息首部中记录有消息的类型、大小、指向消息数据区的指针、消息队列的链接指针等。
2001年 9月 20日 9时 1分 计算机操作系统消息传递系统 -6
消息队列头表,消息队列头表的每一表项是作为一个消息队列的消息头。在消息头中包含了指向消息队列中第一个消息的指针和指向最后一个消息指针，队列中消息的数目、队列中消息数据的总字节数等。
队列 0
.
.
队列 i
消 息 首 部
msgh 0
消息缓冲区 0
消息首部
msgh 8
消 息 缓 冲区 8
消息首部
msgh 3
消息缓冲区 3
消 息 首 部
msgh 2
消息缓冲区 2
2001年 9月 20日 9时 1分 计算机操作系统
(3)管道通信
UNIX系统在 OS的发展上最重要的贡献之一便是该系统首创了管道（ pipes） 。
管道是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称为 pipe文件。 向管道（共享文件）
提供输入的发送进程（即写进程），以字符形式将大量的数据送入管道，而接收管道输出的接收进程（即读进程）可从管道中接收数据。管道通信是基于文件系统形式的一种通信方式。
管道分为无名管道和有名管道两种类型。 无名管道是早期
UNIX版本已提供的，它是一个只存在于打开文件机构中的一个临时文件，从结构上没有文件路径名，不占用文件目录项。
无名管道利用系统调用 pipe(filedes)创建，只用该系统调用所返回的文件描述符 filedes[2]来标识该文件。只有调用
pipe的进程及调用后该进程创建的子孙进程，才能识别此文件描述符，从而才能利用该文件（管道）进行父子或子、子之间通信。
2001年 9月 20日 9时 1分 计算机操作系统管道通信 -1
UNIX系统 V的管道文件最大长度为 10个盘块，核心为它设置了一个读指针和一个写指针。为了确保利用管道使进程间传送数据的正确性。系统在管道读写时设置互斥和同步机制，它首先保证写进程和读进程互斥地进行写和读，同时又要保证写和读的同步。即写进程将数据写入管道后，读进程才能来读取数据，如写进程未将数据写入管道，则读进程必须阻塞等待。如写进程将数据写满管道后读进程未来读，则发出写溢出，此时写进程必须阻塞等待。 与一般文件不同是管道数据的先进先出（ FIFO） 处理方式和管道文件数据不可再现性 。
即被读取的数据在管道中不能再利用，无名管道在关机后自动消失。
在 UNIX,MS-DOS系统中，用户可以在命令级使用管道，这时管道是一个程序的标准输出和另一个程序的标准输入之间的连接，管道命令用符号,|” 表示。
2001年 9月 20日 9时 1分 计算机操作系统父进程管道通信 -2
pipe使用
pipe系统调用的语法格式是,int pipe (filedes)
int filedes [2]；
核心创建一条管道完成下述工作：
a.分配一个隶属于 root文件系统的磁盘和内存索引结点 inode.
b.在系统打开文件表中分别分配一读管道文件表项和一写管道文件表项。
c.在创建管道的进程控制块的文件描述表（进程打开文件表 u-
ofile） 中分配二表项，表项中的偏移量 filedes[o]和 ditedes[1]
分别指向系统打开文件表的读和写管道文件表项。
系统调用所涉及的数据结构如下图所示。
例：
管道 CHAN1
子进程管道 CHAN2
2001年 9月 20日 9时 1分 计算机操作系统例题
有一阅览室,读者进入时必须先在一张登记表上进行登记,
该表为每一座位列一表目,包括座号和读者姓名 。 读者离开时要消掉登记信息,阅览室中共有 100个座位,请问：
为描述读者的动作,应编写几个程序？ 设置几个进程？ 进程与程序间的对应关系如何？
解 1：二个程序 。 管理员 1和管理员 2:管理员 1负责在读者进入时在一张登记表上进行登记,管理员 2负责读者离开时要消掉登记信息 。 二个进程,进程与程序间的对应关系一对一 。
var mutex,empty,full,Semaphore,=﹎﹎ A﹎﹎,﹎﹎ B﹎﹎,﹎﹎ C﹎﹎ 。
begin
parbegin
Manager1：
begin
repeat
Wait a reader in；
﹎﹎﹎ D﹎﹎﹎ ；
2001年 9月 20日 9时 1分 计算机操作系统例题 -1
﹎﹎﹎ E﹎﹎﹎ ；
Login a name in the register；
﹎﹎﹎ F﹎﹎﹎ ；
﹎﹎﹎ G﹎﹎﹎ ；
forever
end
Manager2：
begin
repeat
Wait a reader out；
﹎﹎﹎ H﹎﹎﹎ ；
﹎﹎﹎ I﹎﹎﹎ ；
Logout a name in the register；
﹎﹎﹎ J﹎﹎﹎ ；
﹎﹎﹎ K﹎﹎﹎ ；
forever
end
coend
end
2001年 9月 20日 9时 1分 计算机操作系统例题 -2
解 2：一个读者程序,每一个读者一个进程,进程与程序间的对应关系一对多 。
var empty,Semaphore,=﹎﹎ L﹎﹎；
begin
parbegin
Reader i：
Begin
﹎﹎﹎ M﹎﹎﹎；
Login a name in the register；
Read …,
Logout name in a register；
﹎﹎﹎ N﹎﹎﹎；
end
parend
end
A,B,C,L,(1)0; (2)1; (3)2; (4)100; (5)n;
D---K,M,N,(1)P(mutex); (2)V(mutex); (3)P(empty);(4)V(empty); (5)P(full); (6)V(full); (练习 )
2001年 9月 20日 9时 1分 计算机操作系统习题
1,对于记录型信号量,在执行一次 P操作时,信号量的值应当为﹎﹎ A﹎﹎； 当其值为﹎﹎ B﹎﹎ 时,进程应阻塞 。 在执行 V
操作时,信号量的值应当﹎﹎ C﹎﹎； 当其值为﹎﹎ D﹎﹎ 时,
应唤醒阻塞队列中的进程 。
A,C,(1)不变； (2)加 1； (3)减 1； (4)加指定数值； (5)减指定数值 。
B,D,(1)大于 0； (2)小于 0； (3)大于等于 0； (4)小于等于 0。
(解 )
2001年 9月 20日 9时 1分 计算机操作系统习题 -1
2.在操作系统中，解决进程间的﹎﹎ A﹎﹎ 两种基本关系，往往运用对信号量进行﹎﹎ B﹎﹎ 的﹎﹎ C﹎﹎,例如，为保证系统数据库的完整性，可以把信号量定义为某个库文件（或记录）的锁，初值为 1，任何进程存取该库文件（或记录）之前先对它作一个﹎﹎ D﹎﹎,存取之后对它作一个﹎﹎ E﹎﹎，
从而做到对该文件（或记录）任一时刻只有一个进程可存取，
但要注意使用不当引起的死锁。
A,(1)同步与异步； (2)串行与并行； (3)调度与控制； (4)同步与互斥。
B,(1)消息操作； (2)P-V操作； (3)开关操作； (4)读写操作。
C,(1)通信原语； (2)调度算法； (3)分配策略； (4)进程控制。
D,E,(1)联机操作； (2)V操作； (3)输出操作； (4)读操作；
(5)写操作； (6)P操作； (7)输入操作。
(解 )
2001年 9月 20日 9时 1分 计算机操作系统习题 -2
3。 有一阅览室，读者进入时必须先在一张登记表上进行登记，
该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信息，阅览室中共有 100个座位，请问：
a.为描述读者的动作,应编写几个程序？ 设置几个进程？ 进程与程序间的对应关系如何？
b.用类 Pascal语言和 P,V操作写出这些进程间的同步算法 。
(解 )
4.今有三个并发进程 R,M,P,它们共享一个缓冲区,R负责从输入设备读信息,每读一个记录后,把它存放在缓冲区,M在缓冲区加工读入的记录,P把加工后的记录打印输出,读入的记录经加工输出后,缓冲区中又可存放下一个记录 。 请用 P、
V操作为同步机制写出它们并发执行时能正确工作的程序
5.试述 消息缓冲队列通信机制通信原理 。 (解 )
