【计算机课件】软件学院计算机操作系统讲解课件-进程管理

第二章进程管理

.2.1进程的基本概念

.2.2进程管理

・23进程间的同步与互斥

.2.4进程通讯

■2.5线建

2.1进程的基本概念

程序的顺序执行和并发执行

■顺序执行是单道批处理系统的执行方式，也

用于简单的单片机系统；；

■现在的操作系统多为并发执行，具有许多

新的特征。引入并发执行的目的是为了提高,

资源利用率。

程序的顺序执行

•例：程序段

read(disk,&a,4);/*从磁盘读a*/

read(tape,&b,4);/*从带读b*/

c=a+b;

////

printf(c=%f\n/c);

・顺序执行的特征

-顺序性

_封闭性

-可再现性

程序并行性表示

是一个有向无环图，图中每个结点表示一个语句、一段程序或一个进程

有向边切表示外仅在必执行完后才能开始执行

有回路的前趋图

前趋图

2.并行语言

类Pascal的并行语句。

COBEGIN

C•C•.C

，口2，•••，

COEND

COBEGIN/COEND相当于一个括号，表示其中的所

有语句Sl，S2f...Sn可并行执行。

并发执行及其特征

例：si:read(disk,&a,4);/*从磁盘读a*/

s2:read(tape,&b,4)；/*从带读b*/

s3:c=a+b;

si和s2可并发，s2和s3不可并发

书中p36eg

多道程序系统：资源共享；程序的并发运行

例：intN=0;/*全局变量*/

cobegin

progamA

progamB

while(l){(

while(l){

N++;

printf("N=%d\n”,N);

N=0;

)

)

)

)

coend

•并发执行的特征

一间断（异步）性："运行一暂停一运行”；

并发程序之间依赖相互、相互制约

（e.g.I-C-P程序）

-不可再现性（e.g.NPrint（N））

-失去封闭性

P37

进程(PROCESS)的概念

►一个具有一定独立功能的程序在一个数据集合，

上的一次动态执行过程。

►是系统进行资源分配和调度的一个独立单位

■进程的定义

是并发程序的一次执行过程，它由一个动作序列组

成，每个动作是在某数据集上执行一段程序，整个

活动的结果是提供一种系统或用户功能。

■进程的特征P38

•结构特征

•动态性：产生、执行、暂停、消亡。有一个生

存期

•独立性：是系统进行资源分配和调度的独立单

位，是能独立运行的基本单位

•并发性：程序在建立进程后并发运行

・异步性

■进程与程序的区别

•进程是动态的，程序是静态的

•进程是暂时的，程序的永久的

•进程与程序的组成不同

■进程与程序的联系

•通过多次执行，一个程序可对应多个进程;

通过调用关系，一个进程可包括多个程序。

2.2进程管理

进程的状态

■三种基本调度状态

・运行状态：进程分配到必要的资源，在CPU上

执行时的状态

•就绪状态：进程分配到必要的资源，还没获

得在CPU上执行的状态

・阻塞状态（等待状态）：进程的执行由于本

身不具备运行条件而受到阻塞，处于暂停状

态

进程的状态

•细分的进程调度状态（另一些系统）

・挂起：强迫进程释放分配到的资源，将进程

调出到外存

•活动：未被挂起的就绪和阻塞状态称为活动

一就绪和活动阻塞

•静止：被挂起的就绪和阻塞状态称为静止就

绪和静止阻塞

wakeup（唤醒）

wakeup（唤醒）图：具有挂起功能的进

程状态变化

进程的状态转换：

,，三状态进程模型

Dispatch

Timeout

S

+JJ

Um

①o

次o

o

进程控制块(PCB」processcontrolblock)

■进程的物理结构

•程序：描述进程要完成的功能

•数据集合：包含程序运行所需的数据和工作

区

•进程控制块(PCB)：包含进程的描述信息和

二控制信息，是进程动态特性的反映

程序和数据集合是进程的实体

二进程控制块是进程存在的唯一标志；

进程控制块是由OS维护的用来记录进程相关

信息的一块内存。

■进程控制块的内容

•进程标识符：

唯野翻（ProcessID）（内部标识符）|唯一，通常

-靠程名（外上标识符）：不唯一，由字母数字组成；

•居曹信息：指出进程的程序和数据在内存和外存中的物理

­洋:|扇巅嚼产器值（通用、程序计数器P&状态PS肌地

•状态信息「进程现行状态

•进程优先级：进程使用CPU的优先级别

•资源清单：已分配到的资源等

•同步与互斥机构

•进程通讯机制

•队列指针

•家族联素

•资源占用信息：虚拟地址空间的现状、打开文件列表

■PCB的组织方式

•顺序表：将所有PCB连续存放在内存。要经常扫

描整个表

•索引表：同一状态的PCB建立一个index表（由

index指向PCB）,多个状态对应多个不同的

index表

-各状态形成不同的索引表：就绪索引表、阻塞索引表

•链表：同一状态的进程的PCB成一链表，多个状

态对应多个不同的链表

-各状态的形成不同的链表：就绪链表、阻塞链表

进程控制

■进程控制的功能完成进程状态的转换。

原语(primitive)：由若干条指令构成的“原子

操什(atomicoperation)”过程，作为一个整体

而不可分割一一要么全都完成，要么全都不做。

许多系统调用就是原语。

进程创建P43-44

•进程图二

父、子进程­

•引起进程创建事件

用户登录、作业调度、提供服务、应用请求

•进程创建

创建过程

进程终止P45.46

•引起进程终止的事件

•进程的终止过程

进程阻塞与唤醒P46

•引起进程阻塞与唤醒的事件

•阻塞、唤醒过程

挂起与激活P©

•进程挂起

•激活过程

2.3进程间的同步与互斥

•进程间的制约关系

-间接制约：进行竞争一一独占分配到的部分或全部?

“互斥”

-直接制约：进行协作一一等待来自其他进程的信息,“同步”

临界资源(CriticalResource)

系统中一次仅允许一个进程使用的一类资源。

打印机，卡片输入机，磁带机、共享变量等。

斥

互多个进程不能同时使用同一个资源；

锁

死

:多个进程互不相让，都得不到足够的资源；

饿

饥

:一个进程一直得不到资源(其他进程可能轮流占用

资源)

例：民航售票系统，n个售票处

/*ProcessPi,i=l,2,・・・,n*/

/*按订票要求找到共享数据x[k]*/

/*x[k]存放某月某日某次航班的现有票数*/

R=x[k];/*现有票数*/

if(R>=l){

R--；

x[k]=R;

输出一张机票；：

}

else

iLkZjs示口售兀；

共享变量的修改冲突:

把变量x[k]作为临界资源处理

临界区：访问临界资源的那段代码（程序段）。

同类临界区:对同一临界资源进行操作的程序段。

临界区的访问过程

entrysection

criticalsection

exitsection

remaindersection

增加一段检查的代码

•临界区(criticalsection)：进程中访问

临界资源的一段代码。

•进入区(entrysection)：在进入临界区之

前，检查可否进入临界区的一段代码。

•退出区(exitsection)

•剩余区(remaindersection)：代码中的其

余部分。

-同步机制应遵循的准则

・空闲则入：其他进程均不处于临界区；

•忙则等待：已有进程处于其临界区；

­有限等待：等待进入临界区的进程不能"死等"；

・让权等待：不能进入临界区的进程，应释放CPU

（如转换到阻塞状态）

互斥算法

■进程互斥的软件方法

卜算法1:单标志

•有两个进程Pi,Pj,其中的Pi

while(turn!=i);

criticalsection

turn=j;

remaindersection

•设立一个公用整型变量turn：描述允许进入临

界区的进程标识

•缺点：强制轮流进入临界区，没有考虑

进程的实际需要。容易造成资源利用不

充分：在Pi出让临界区之后，Pj使用临

界区之前，Pi不可能再次使用临界区；

算法2：双标志

•设立一个标志数组flag口:描述进程是否要求进入

临界区或已在临界区，初值均为FALSE

•turn二j;描述可进入的进程（同时修改标志时）

•在进入区先修改、后检查、后修改者等待

intflag[2]={0,0};

/*进入临界区*/

intturn=O;

criticalsection

/*进程pi的结构*/

/*退出临界区]*/

while(l){

flag[i]=l;turn=j;

while(flag[j]){flag[i]=0;

if(turn==j){remaindersection

flag[i]=0;)

while(turn==j);

flag[i]=l;

)

■进程互斥的锁操作方法

•每一类临界资源设置一把锁lock。

•lock表示资源的两种状态：TRUE表示正被占用（锁

关状态）；FALSE表示空闲（锁开状态）

执行临界区程序

■锁操作方法

，用开、关中断实现锁操作

执行临界区程序

优点：简单、可靠

缺点：

・,木能实现所有的同类临界区互斥；

•临界区太长时，降低了中断响应速度;

•扩大了互斥范围；

•加锁时CPU不断测试，处于忙等待。

信号量(semaphore)

信号量表示临界资源的实体，是一个数据结构，其

值仅能由P、v操作来改变。

阻塞等待信号量数据结构：

typedefstruct{

intvalue;/*信号量的值*/

PCB*ptr_of_semque;

}semaphore;

PCB:进程控制块的数据类型

ptr^of_semque：指向等待使用该信号量的进程队列的队首

信号量初始化：

•Value:指定一个非负整数值，表示空闲资源总数

——若为非负值表示当前的空闲资源数，若为负

值其绝对值表示当前等待临界区的进程数

•L：链接等待的进程指针

►P操作wait⑸

signal(s)

v操作通常唤醒进程等待队列中的头一个进程

■利用信号量实现互斥

P(mutex);

criticalsection

V(mutex);

remaindersection:

•为临界资源设置一个互斥信号量mutex(MUTual

Exclusion),其初值为1；在每个进程中将临界区

代码置于P(mutex)和V(mutex)原语之间

•必须成对使用P和V原语，P、V原语不能次序错误、

重复或遗漏

信号量实现互斥模型：

semaphoremutex={l,NULL};

cobegin

programpi

(

while(l){

P(&mutex)；

criticalsectionforpi;/*进程pi临界区*/

V(&mutex)；

remaindersectionforpi;

)

)

coend

例：民航售票系统，n个售票处

semaphoremutex={l,NULL};

else{

cobegin

V(&mutex)；

programpi

显示“票已售完”；

)

P(&mutex)；)

coend

R=x[k];/*现有票数*/

if(R>=l){

x[k]=R;

V(&mutex)；

输出一张机票;

)

解决共享变量的修改冲突

■利用信号量实现同步

设置一个同步信号量proceedL其初值为0

semaphoreproceedl={0,NULL};

cobegin

进程pl

P(&proceedl)；

进储p2-

V(&proceedl)；

coend

例：一辆公共汽车上，司机和售票员进程的同步

semaphoredrive_sem={O,NULL};

semaphoreconductor_sem={0,NULL};

cobegin

programdrive

(

while(l){

driving;/*正常行车*/

stopping;i

V(&conductor_sem)；/*唤醒开门*/

P(&drive_sem)；/*等待关门*/

startacar;

)

programconductor

while(l){

selltickets;/*售票*/

P(&conductor_sem)；/*等待停车*/

openthedoor;

closethedoor;

V(&drive_sem)；/*唤醒司机开车*/

}一

:}

coend

信号量应用

•实现进程互斥:

互斥访问临界资源

•实现前趋关系；

P54

经典应用示例

1.生产者^—消费者^|可^§(theproducer-consumerproblem)

问题描述：若干进程通过有限的共享缓冲区交换数据。

其中，〃生产者〃进程不断写入，而〃消费者〃进程不断

读出；共享缓冲区共有N个；任何时刻只能有一个进程

可对共享缓冲区进行操作。

Producer1Consumer1

生产指针消费指针

Producer2__Consumer2

xX)

ProducerMConsumerN

xX)

满/空/共享缓冲区指针移动方向

•采用信号量机制：

-full是〃满〃数目，初值为0,empty是〃空〃数

目，初值为N。full+empty=N

-mutex用于访问缓冲区时的互斥，初值是1

•每个进程中各个P操作的次序是重要的：先检查

;资源数目，再检查是否互斥一一否则可能死锁

（为什么？）

算法:#defineN100

#defineMAXLEN80

typedefstruct{

intnum;

chararray[MAXLEN];

}Message;

semaphoremutex={l,NULL};

semaphoreempty={N,NULL};

semaphorefull={O,NULL};

Messagebuffers[N];

intp_index=0,cJndex=0;

cobegin

programproduceri

(

Messagep_puf;

while(l){

produceamessageinp_buf;

P(&empty)；

P(&mutex)；

memcpy((char*)&buffers[p_index],

(char*)&p_buf,sizeof(Message));

p_index=(p_index+l)%N;

V(&mutex)；

V(&full)；}

)

programconsumer]

(

Messagec_buf;

while(l){

P(afull)；

P(&mutex)；

memcpy((char*)&c_buf,

(char*)&buffers[c_index],sizeof(Message));

c_index=(c_index+l)%N;

V(&mutex)；

V(&empty)；

consumethemessageinc_buf;}

}一：

coend

2.读者一写者问题(thereaders-writersproblem)

•问题描述：对共享资源的读写操作，任

一时刻“写者”最多只允许一个，而

“读者”则允许多个

一“读一写”互斥，

一-“写一写”互斥，.

--〃读一读〃允许

•采用信号量机制：

-wrmutex表示〃允许写〃，初值是1。

-公共变量Readcount表示“正在读”的进程数，初值是0；

-mrutex表示读者对Readcount的互斥操作，初值是1。

semaphorerwmutex={l,NULL},rmutex={1,NULL};

算法:intreadcount=0;

cobegin

programreaderi

{

P(&rmutex)；

readcount++;

if(readcount==l)

P(&rwmutex)；

V(&rmutex)；

readdata;

P(&rmutex)；

readcount-;

if(readcount==0)

V(&rwmutex)；

V(&rmutex)；

)

programwriterj

P(&rwmutex)；

writeorupdatedata;

V(&rwmutex)；

}

coend

写者长期阻塞

写者优先算法:

semaphorerwmutex={1,NULL},rsem={10,NULL};

programwriterj

cobegin

programreaderi

inti;

P(&rwmutex)；

P(&rwmutex)；

for(i=l;i<=10;i++)

P(arsem)；

P(arsem)；

V(&rwmutex)；

writeorupdatedata;

readdata;

for(i=l;i<=10;i++)

V(&rsem)；