计算机操作系统课件

计算机操作系统

OperatingSystemofComputer

第四章进程同步

♦:♦主要内容：

小进程的同步与互斥

8经典进程同步问题

8管程机制

8进程通信。

知识点及要求：

8要求掌握用P、V操作解决进程同步问题，了解

进程间的通信。

4.1进程的同步

。在多道程序系统中，由于资源共享或进程合作，使

进程间形成间接相互制约和直接相互制约关系，这

需要用进程互斥与同步机制来协调两种制约关系。

进程同步的主要任务是使并发执行的进程间有效的

共享资源和相互合作，从而使程序的执行具有可再

现性。

进程的同步机制—信号量及P.V操作（解决进程同

步互斥问题）

1.进程间的关系

♦:♦直接作用（相互合作）：

进程间的相互联系是有意识的安排的,

直接作用只发生在相交进程间

。间接作用（资源共享）：

进程间要通过某种中介发生联系，是

无意识安排的，可发生在相交进程之

间，也可发生在无关进程之间

相互感知程度交互关系一个进程对其他进

程的影响

相互不感知（完全不竞争(competition)一个进程的操作对

了解其它进程的存其他进程的结果无

在）影响

间接感知（双方都与通过共享进行协作一个进程的结果依

第三方交互，如共赖于从其他进程获

享资源）得的信息

直接感知（双方直接通过通信进行协作一个进程的结果依

交互，如通信）赖于从其他进程获

得的信息

2.进程的同步（直接作用）

指系统中多个进程中发生的事件

存在某种时序关系，需要相互合作，

共同完成一项任务。具体说，一个进

程运行到某一点时要求另一伙伴进程

为它提供消息，在未获得消息之前，

该进程处于等待状态，获得消息后被

唤醒进入就绪状态。

3.进程的互斥（间接作用）

由于各进程要求共享资源，而有些资

源需要互斥使用，因此各进程间竞争使用

这些资源，进程的这种关系为进程的互斥。

临界资源：

系统中某些资源一次只允许一个进程使用,

称这样的资源为临界资源或互斥资源或共

享变量

4.基本概念

♦:♦进程互斥：指在多道程序环境下，每次只

允许一个进程对临界资源进行访问。

♦:♦进程同步：指多个相关进程在执行次序上

的协调。

❖临界资源:一次仅供一个进程使用的资源。

在进程中涉及到临界资源的程序段叫临界

区

❖多个进程访问同一资源的临界区称为相关

临界区

共享变量

5.使用互斥区的原则

♦:♦空闲让进：当无进程在互斥区时，任何

有权使用互斥区的进程可进入

♦:♦忙则等待：不允许两个以上的进程同时

进入互斥区

孝有限等待：任何进入互斥区的要求应在

有限的时间内得到满足

♦:♦让权等待：处于等待状态的进程应放弃

占用CPU,以使其他进程有机会得到CPU

的使用权

使用互斥区的原则

前提：任何进程无权停止其它进程的运行

进程之间相对运行速度无硬性规定

进程互斥的解决有两种做法：

•由竞争各方平等协商

•引入进程管理者，由管理者来协调竞争各方对互

斥资源的使用

具体方法：

硬件（利用Test-and-Set指令或利用swap指令

实现）

软件（用编程解决，但常常忙等待）

6.进程互斥的软件方法

♦：♦通过平等协商方式实现进程互斥的最初方法

是软件方法

其基本思路是在进入区检查和设置一些标志,

如果已有进程在临界区，则在进入区通过循

环检查进行等待；在退出区修改标志

其中的主要问题是设置什么标志和如何检查

软彳牛》法的缺点：

L忙等待

2.实现过于复杂

3.需要高的编程技巧

软件解法⑴

free:表示临界区标志

true:有进程在临界区

false:无进程在临界区（初值）

while(free);

free=true;

临界区

free=false;

软件解法⑵

turn:trueP进入临界区

falseQ进入临界区

••••

P:while(notturn);

临界区

turn=false;

Q:while(turn);

临界区-

turn=true;

软件解法⑶

pturn,qturn:初值为false

P进入临界区的条件：pturnAnotqturn

Q进入临界区的条件:notpturnAqturn

P・・・・Q……

pturn=true;pturn=true;

while(qturn);while(pturn);

临界区临界区

pturn=false;qturn=false;

破件解法（1）—“测试并设置”指令

booleanTS

(boolean*lock)whileTS(&lock);

(

临界区

TS=*lock;

lock=false;

*lock=true;

破件解法⑵一“交换”指令

voidSWAP(intkey=true;

*a,int*b)do

((

inttemp;WAP(&lock,key);

temp=*a;}while(key);

*a=*b;

临界区

*b=temp;

}lock:=false;

硬件解法⑶一“开关中断”指令

进入临界区前执行：

执行“关中断”指令

离开临界区后执行：

执行“开中断”指令

7.进程的同步机制——

信号量及P.V操作（解决进程同步）

同步机制：

信号量及P、V操作；管程；条

件临界域；路径表达式等（用于

集中式系统中）

同步机制应满足的基本要求

♦:♦描述能力

♦:♦可以实现

♦:♦效率IWJ

♦使用方便

解决互斥的锁机制

*实现互斥的一种软件方法是采用锁机制,

即提供一对上锁(Lock)和开锁(UnLock)

原语，以及一个锁变量W。

。进程进入临界区前，通过锁变量来判断

临界资源是否被占用。

信号量机制

❖信号量机制是一种卓有成效的进程同步工具，

被广泛应用于单处理机和多处理机系统，以及

计算机网络中。

♦:♦锁机制仅能表示“开”与“关”两种状态；开、

关锁原语必须作为原子操作来进行；关锁原语

中反复测试mutex状态，浪费了处理机的时间;

锁机制只能解决互斥，不能用于同步。信号量

同步机制能完满地解决上述问题。

信号量：semaphores

是一个数据结构

❖定义如下：

strucsemaphore

{

intvalue;

pointer_PCBqueue;

♦:♦信号量说明：

semaphores;

p操作

p(s)

s.value=s.value一一;

if(s.value<0)

(

该进程状态置为等待状态；

将该进程的PCB插入相应的等待队列末尾

s.queue;

P操作

♦意味着请求分配一个单位资源

平.

s》o?-V

V操作

V(s)

s.value=s.value++;

if(s.value<=0)〃意味着原有资源已用完,

等待队列非空

{

唤醒相应等待队列s.queue中等待的一个进程

改变其状态为就绪态

并将其插入就绪队列

V操作

♦意味着释放一个单位资源

SWO?

Yl

从信号量的等待队

列中取出等待量

P、V操作为原语操作

原语：是由若干多机器指令构成的完成某种

特定功能的一段程序，具有不可分割性。

即原语的执行必须是连续的，在执行过程

中不允许被中断。

实现：开关中断

信号量的使用：

必须置一次且只能置一次初值

初值不能为负数

只能执行P、V操作

用P、V操作解决进程间互斥问题

互斥例子

♦：♦三个进程共用两个I/O缓冲区。

♦:♦解：设用信号量S表示共享资源，S初

始值为2

■A班和B过衽・CQtt

假设用个进程使用缓冲区占两个时间片

•表示正在占用时间片的进程

同步例子

。有A、B两进程，A进程从卡片机读信息

入缓冲区，B进程负责加工读进缓冲区

的卡片

。解：设信号量S1：缓冲区中有否可供加

工的信息，初始值为0;信号量S2：缓

冲区是否为空，初始值为1。

同步例子(续)

榆入aHlA加工递钱B

在输入进程A中，可以把P(S2)调到

V(S1)后面，而把信号量S2的初始值设

为0。

用P-V操作描述前趋关系的例子

♦:♦信号量还可以描述程序或语句之间的前

趋关系O

用P-V操作描述前趋关系（续）

描述如下:

Vara,b,c,d,e,f,g：semaphore：=0,0,0,0,0,0,0；

begin

parbegin

beginSI；V(a)；V(b)；end；

beginP(a)；S2；V(c)；V(d)；end；

beginP(b)；S3；V(e)；end；

beginP(c)；S4；V(f)；end；

beginP(d)；S5；Vg()；end；

beginP(e)；P(f);P(g);S6；end；

parend

经典的生产者一消费者问题

生产者消费者

一次只可放一个产品

经典的生产者一消费者问题

同步问题：

P进程不能往“满”的缓冲区中放

产品，设置信号量为S1

Q进程不能从“空”的缓冲区中取

产品，设置信号量S2

P:

while(true){while(true){

生产一个产品；P(s2);

P(s1);从缓冲区取产品;

送产品到缓冲区;V(s1);

V(s2);消费产品；

)；)；

S1初值为1,S2初值为0

生产者-消费者问题

❖生产者一消费者(Producer-Consumer)问题是著

名的进程同步问题。它描述一组生产者向一组

消费者提供消息，它们共享一个有界缓冲池，

生产者向其中投放消息，消费者从中取得消息。

以下用信号量解决生产者一消费者问题。

♦:♦假设缓冲池中有n个缓冲区，每个缓冲区存放一

个消息，可利用互斥信号量mutex使诸进程对缓

冲泡实貌宣序齿问;刘用empty和full计数信号

量分别表示空缓冲及满缓冲的数量。又假定这

些生产者和消费者互相等效，只要缓冲池未满,

生产者可将消息送入缓冲池；只要缓冲池未空,

消费者可从缓冲池取走一个消息。

方文消息耳又消息、

(Buffer)

生产者-消费者问题(续)

♦:♦其中，mutex,empty,full的初始值分别

为为n,0；

•i产弟班隹消费者进银:

一生埼一件新产品।

P(CEply)|P(full)I

P(mulcx)|P(mutex)|

〔把产品放；把产品从缓

赴约冲池冲斑戢定n

V(mutex)V《mutex)|

---------1…V，<fu-一l.l一)，-」IV(empty)|

P操作的顺序可换吗?

P.V操作讨论

1)信号量的物理含义：

s〉o表示有s个资源可用

s=0表示无资源可用

s<0则|S|表示S等待队列中的进程个数

P(s)：表示申请一个资源

V(S)表示释放一个资源。信号量的初值应该大于等于0

2)P.V操作必须成对出现，有一个P操作就一定有一个V操作

当为互斥操作时，它们同处于同一进程

当为同步操作时，则不在同一进程中出现

如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至

关重要，一个同步P操作与一个互斥P操作在一起时同步P操作

在互斥P操作前

而两个V操作无关紧要

P.V操作的优缺点

优点：

简单，而且表达能力强（用PY操作

可解决任何同步互斥问题）

缺点：

“不够安全；P.V操作使用不当会出

现死锁；遇到复杂同步互斥问题时实

现复杂

8.信号量集一AND型信号量集

。AND型信号量集是指同时需要多种资源且

每种占用一个时的信号量操作

♦AND型信号量集的基本思想：在一个原语

中申请整段代码需要的多个临界资源，要

么全部分配给它，要么一个都不分配

AND型信号量集P原语为Swait

❖AND型信号量集V原语为Ssignal

Swait(S1ZS2ZSn)//P原语；

(

whil㊀(TRUE){

if(Si>=1&&S2>=1&&...&&sn>=1)

{//满足资源要求时的处理；

for(i=1;i<=n;++i)——S1;

//注：与P的处理不同，这里是在确

信可满足

口//资源要求时，才进行减1操作；

break;

)

else{//某些资源不够时的处理；

调用进程进入第一个小于1信号量的等待队列

S..qu㊀u㊀；

阻塞调用进程；

)

Ssignal(SlfS2<…,Sn)

(

for(i=1;i<=n;++i)

{

++Si；//释放占用的资源；

for(在S].qu㊀u㊀中等待的每一^进

程P)

//检查每种资源的等待队列的所有

进程；

(

从等待队列.qu㊀u㊀中取出进程P;

if（判断进程P是否通过Swait中的测试）

//注：与signal不同，这里要进行重新

判断;

{//通过检查（资源够用）时的处理；

进程P进入就绪队列；

}

㊀1s㊀

{//未通过检查（资源不够用）时的处理;

进程P进入某等待队列；

}

)

9.一般“信号量集”

一般信号量集是指同时需要多种资

源、每种占用的数目不同、且可分

配的资源还存在一个临界值时的信

号量处理

一般信号量集的基本思路就是在

AND型信号量集的基础上进行扩充,

在一次原语操作中完成所有的资源

申请。

♦:♦进程对信号量Sj的

测试值为tj（表示信号量的判断条件，要

求Sj>=tj；即当资源数量低于tj时，便

木予分配）

占用值为4(表示资源的申请量，即Sj二

Si-dp

对应的P、V原语格式为：

c^Swait(S.,d.;・・・；St

_LrJ_1n1,1.1nA

dn)；

G^Ssignal(S.d.;・・・；Sd);

_LrJL1n1^11

一般“信号量集”可以用于各种情况的

资源分配和释放，几种特殊情况：

❖Swait(S,d,d)表示每次申请d个资源,

当少工d个时，便不分配

。Swag,1,1)表示互斥信号量

❖Swait(S,1,0)可作为一个可控开关

(当S"时，允许多个进程进入临界

区；当s=o时，禁止任何进程进入临

界区)

10.经典问题

1）读者写者问题

有两组并发进程：

读者和写者,共享一组数据区

要求：

允许多个读者同时执行读操作

不允许读者、写者同时操作

不允许多个写者同时操作

第一类：读者优先

如果读者来：

1）无读者、写者，新读者可以读

2）有写者等，但有其它读者正在读，则

新读者也可以读

3）有写者写，新读者等

如果写者来：

1）无读者，新写者可以写

2）有读者，新写者等待

3）有其它写者，新写者等待

第一类读者写者问题的解法

读者：

while(true){写者：

P(mutex);while(true){

readcount++;

if(readcount==1)P(w);

P(w);

V(mutex);写

读V(w);

P(mutex);

readcount)；

if(readcount==0)

V(w);

V(mutex);

第一类读者写者问题的解法

（一般信号量集）

读者:写者:

swait(wmutex,1,1;swait(rcount,1,1;

rcount,R,0);wmutex,1,0);

读；写；

ssignal(wmutex,1);ssignal(rcount,1);

2）哲学家就餐问题

有五个哲学家围坐在一圆桌旁，桌

中央有一盘通心粉，每人面前有一只空

盘子，每两人之间放一只筷子

每个哲学家的行为是思考，感到饥

饿，然后吃通心粉

为了吃通心粉，每个哲学家必须拿

到两只筷子，并且每个人只能直接从自

己的左边或右边去取筷子

#defineN5

voidphilosopher(inti){

while(true){

思考；

P(fork[i]);P(fork[(i+1)%5])；

进食；

V(fork[i]);V(fork[(i+1)%5])；

}

}

为防止死锁发生可采取的措施：

*最多允许4个哲学家同时坐在桌子周围

♦仅当一个哲学家左右两边的筷子都可用时,

才允许他拿筷子2

♦:♦给所有哲学家编号，奇数号的哲学家必须

首先拿左边的筷子，偶数号的哲学家则反

之

为了避免死锁，把哲学家分为三种状态，

思考，饥饿，进食，并且一次拿到两只筷

子，否则不拿

Varchopstickarray[0,..,4]of

semaphore:=(1,1,1,1);

(

while(true){

思考；

Sswait(chopstick[(i+1)%5],chopstick[i])；

进食；

Ssignal(chopstick[(i+1)%5],chopstick[i]);

}

}

3）第二类读者写者问题：

写者优先

条件：

1）多个读者可以同时进行读

2）写者必须互斥（只允许一个写者写，

也不能读者写者同时进行）

3）写者优先于读者（一旦有写者，则后

续读者必须等待，唤醒时优先考虑写

者）

4.2管程机制

1.管程的提出

采用P-V同步机制来编写并发程序，对于共享变量

及信号量变量的操作将被分散于各个进程中

缺点：

1）易读性差，因为要了解对于一组共享变量及信号

量的操作是否正确，则必须通读整个系统或者并

发程序

2）不利于修改和维护，因为程序的局部性很差，所

以任一组变量或一段代码的修改都可能影响全局

3）正确性难以保证，因为操作系统或并发程序通常

很大，要保证这样一个复杂的系统没有逻辑错误

是很难的

2.管程概念

♦:♦概念：指关于共享资源的数据及在其上操

作的一组过程或共享数据结构及其规定的

所有操作。

♦:♦系统按资源管理的观点分解成若干模块，

用数据表示抽象系统资源，同时分析了共

享资源和专用资源在管理上的差别，按不

同的管理方式定义模块的类型和结构，使

同步操作相对集中，从而增加了模块的相

对独立性。

3.管程的组成

管程的四个组成部分：

名称

数据结构说明

❖对该数据结构进行操作的一组过程/函数

初始化语句

局部于管程的数据结构，仅被局部于管

程的过程访问。局部于管程的过程，也仅能

访问管程内的数据结构。

管程（相当于围墙）把共享变量和对它

进行操作的若干过程围起来。

管程的形式

TYPEmonitor_name=MONITOR;

共享变量说明一

define本管程内所定义、本管程外可调用的过程（函数）

名字表

use本管程外所定义、本管程内将调用的过程（函数）

名字表

PROCEDURE过程名（形参表）；

过程局部变量说明；

BEGIN

语句序列；

END;

FUNCTION函数名（形参表）：值类型;

函数局部变量说明；

BEGIN

语句序列；

END;

BEGIN

共享变量初始化语句序列;

END;

4.管程的三个主要的特性

♦:♦模块化:一个管程是一个基本程序单位，可以

单独编译

♦:♦抽象数据类型:管程是一种特殊的数据类型,

其中不仅有数据，而且有对数据进行操作的代

码

♦:♦信息掩蔽:管程是半透明的，管程中的外部

过程（函数）实现了某些功能，至于这些功能

是怎样实现的，在其外部则是不可见的

5.管程的要素

♦:♦管程中的共享变量在管程外部是不可

见的，外部只能通过调用管程中所说

明的外部过程（函数）来间接地访问

管程中的共享变量

♦:♦为了保证管程共享变量的数据完整性,

规定管程互斥进入

♦:♦管程通常是用来管理资源的，因而在

管程中应当设有进程等待队以及相应

的等待及唤醒操作

问题：多个进程出现在管程中

当一个进入管程的进程执行等待操作时，它

应当释放管程的互斥权；当一个进入管程的

进程执行唤醒操作时（如P唤醒Q）,管程

中便存在两个同时处于活动状态的进程

处理方法有三种：

♦：.P等待Q继续，直到Q退出或等待

。Q等待P继续，直到P等待或退出

*规定唤醒为管程中最后一个可执行的操作

因为管程是互斥进入的，所以当一个进程

试图进入一个巳被占用的管程时它应当在管程

的入口处等待，因而在管程的入口处应当有一

个进程等待队列，称作入口等待队列

如果进程P唤醒进程Q,则P等待Q继续,

如果进程Q在执行又唤醒进程R,则Q等待R

继续，.・・・・・，如此，在管程内部，由于执行唤

醒操作，可能会出现多个等待进程，因而还需

要有一个进程等待队列，这个等待队列被称为

紧急等待队列。它的优先级应当高于入口等待

队列的优先级

由于管程通常是用于管理资源的，因而在管程内

部，应当存在某种等待机制。当进入管程的进程因资

源被占用等原因不能继续运行时使其等待。为此在管

程内部可以说明和使用一种特殊类型的变量，称作条

件变量：

VARC:condition;

对于条件型变量，可以执行wait和signal操作：

wait(c)：如果紧急等待队列非空，则唤醒第一

个等待者；否则释放管程的互斥权，执行此操

作的进程的PCB入c链尾部

signal(c)：如果c链为空,则相当于空操作,执

行此操作的进程继续；否则唤醒第一个等待者,

执行此操作的进程的PCB入紧急等待队列的尾部

6.管程的实现

两个主要途径：

♦:♦直接构造（效率高）

♦:♦间接构造，即用某种已经实现的同步机制

去构造

例子：用P-V操作构造管程

7.管程和进程的异同点

(1)设置进程和管程的目的不同

⑵系统管理数据结构

进程：PCB

管程：等待队列

⑶管程被进程调用

⑷管程是操作系统的固有成分,

无创建和撤消

4.3进程通信

1.进程通信概述

♦P.v操作实现的是进程之间的低级通讯，

所以P.V为低级通讯原语。它只能传递简

单的信号，不能传递交换大量信息

。如果要在进程间传递大量信息则要用

Send/Receive原语（高级通讯原语）

2.实现进程通信的方式

♦:♦共享存储器方式：相互通信的进程通过共享

某些数据结构或存储区来进行通信，可分为

共享数据结构方式、共享存储区方式；

♦:♦消息通信方式：进程间的消息交换以消息或

报文为单位，程序员利用一组通信命令（原语）

来实现通信，可分为直接、间接通信方式；

♦:♦共享文件方式：利用共享文件来实现进程间

的通信。

3.管道通信

♦:♦在UNIX系统中，利用一个打开的共享

文件来连接两个相互通信的进程，该

共享文件称为管道(Pipe),因而该方

式又称为管道通信。

♦:♦为了协调双方通信，管道通信必须提

供三方面的协调能力：互斥、同步、

对方是否存在。

4.消息传递模式

♦：♦系统为进程提供了两个高级通讯原语

send和receive。要进行消息传递时执

行send，当接收者要接收消息时执行

receive

♦:♦消息缓冲：在内存中开设缓冲区，发

送进程将消息送入缓冲区，接收进程

接收传递来的缓冲区

*信箱通信

5.直接方式

共享文件模式：管道通信发送进程发消

息时要指定接收进程的名字，

反过来，接收时要指明发送进程的名字

Send(receiver,message)

Receiver(sender,message)

♦:♦对称形式：一对一

♦:♦非对称形式：多对一(顾客/服务员).

有缓冲(有界，无界)，无缓冲

直接通信方式

-进嘏P17操作系统卜通信通道

直接通信方式模型

6.消息缓冲（有界缓冲区）

在操作系统空间设置一组缓冲区，当发送进程需

要发送消息时，执行send系统调用，产生自愿性中断,

进入操作系统，操作系统为发送进程分配一个空缓冲

区，并将所发送的消息从发送进程copy到缓冲区中，

然后将该载有消息的缓冲区连接到接收进程的消息链

链尾，如此就完成了发送过程。发送进程返回到用户

态继续执行。

在以后某个时刻，当接收进程执行到receive接

收原语时，也产生自愿性中断进入操作系统，由操作

系统将载有消息的缓冲区从消息链中取出，并把消息

内容copy到接收进程空间，之后收回缓冲区，如此就

完成了消息的接收，接收进程返回到用户态继续进行。

直接通信方式实例-消息缓冲通信

♦:♦消息缓冲数据结构（下图）

sender消息发送者

size消息长度

text消息正文

next指向下一个消息缓冲区的指针

♦:♦此外，进程的PCB块中增加一些数据项以

支持消息缓冲区的通信机制实现；如：

mq,消息链首指针；mutex,消