计算机互联网02 进程管理

第二章程管/

第二章程管理

2.1程的基本概念

2.2程控制J

2.3程同步

2.4典程的同步

2.5管程机制

2.6程通信

2.7程

2.1程的基本概念

程序的序行及特征

米一、程序行有固定的序。

11"C1P1——"I2"C2——"P2

、特征:

,序性、封性、可再性

一运工一地

2.1.2前定

。有向无循

。表示方式：

米(1)p1——>p2

米(2)——>={(pl,p2)lpl必在p2始前完成}

2.1.3程序的并

。一多个程序的并行

:♦二、特征

米断性

米失去封性：主要由共享源引起

米不可再性：

米例，N的初n。有2个循程序A和B,

它共享一个量N,A、B并行。

程序A程序B

N:=N+1;Print(N);

N:=0

*

♦N:=N+1在print(N)和N:=0之前，N

分n+1,n+1,0.

♦:♦N:=N+1在print(N)和N:=0之后，N

分n,0,1.

♦：♦N:=N+1在print(N)和N:=0之,N分

n,n+1,0.

2.1.4程的特征和状

♦1.程的特征和定

米定：程序的一次行程.

分析：

要素：程序、数据、CPU、状空

似：食、材料、厨、状空

明：在引入了程体的概念后，我可以把OS中的程定

程是程体的运行程，是系行源分配和度的一个独立位”

:程与程序的异同？

程和程序是既有系又有区的两个概念：

(1)程序是指令的集合，静幄;程是程序在理机

上的一次行程，概念°

(2)程序是期存在的，程有生命周期，有建、活、

消亡。

(3)程序是指令的有序集合；而程由程序、数据和

程控制成°

(4)程与程序之不是——的，即同一程序同运行

于若干不同的数据集合上，它将属于若干个不同的程；

而一个程可以行多个程序°一

程的特征：

1.树特征

・程：由程序段、数据段及程控制三部分构成,

称“程映像"°

2.性

・由“建”而生，由“度”而行；由得不到源

而阻塞；由撤消而消亡°（而程序是静的）°

3.并性

■只有建立了程，才能并行°

4.独立性°

■独立运行，独立得源°

5.异步性：（断性）

第二章程管一理a

❖2.程的三基本状

米就状

米行状

米阻塞状

程的三基本状及其

♦:*3.挂起状（被出内存的状）

米引入原因

■端用求

■父程求

・荷需要

■操作系需要

米程状的

■活就静止就

■活阻塞静止阻塞

■静止就活就

■静止阻塞活阻塞

1^*___

—,,

=早

2.1.5程控制

程控制的作用

pid

米是程存在的唯一志

■程状

泰PCB(processcontrol

block)常内存先

♦:*2.程控制中的信息、

阻塞原因

米、理机状，程

度信息，程控制信息程序地址

同步机制

源清

接指

03.PCB的

米接

(p332-7)PCB14

PCB23

PCB30

PCB48

PCB5

PCB67

PCB79ZJ

PCB80

PCB91

等待列示例

structwait_queue{

structtask_struct*task;

structwait_queue*next;

Ml

03.PCB的

米索引（p342-8）PCB1

PCB2

PCB3

PCB4

PCB5

PCB6

PCB7

阻塞表指

2.2程控制

程控制的任

系中所有程人人建、存在到消亡的全程施有效的管理和控

制。具有建新程、运行程行控制、撤程的能力°程控制由

os系的内核完成，内核通原操作来°

理机的两状

核心又称管或系，使OS管理程序行机器所的状。具有

高特，能行一切指令，所有寄存器和存区°

用又称目，是用程序行机器所的状。具有低特的行

状，只能行定的指令，指定的寄存器和存E°

内核：基于硬件的第一次件充，并常内存

内核的功能支撑功能（中断理、管理、原操作）

源管理（程管理、存器管理、管理）

原：由若干指令构成，用于完成一定功能的一段程序。原在行期

不可分割，所以原操作具有原子性°（中断下完成）

常用的程摔制原：

建

撤

阻塞：行一阻塞

醒：阻塞一就

挂起：活一静止

激活：静止一活

、---------------■■

一里士*

2.2.1程的建

、程：

程的家族系：（P342-9）

子程可承父的源，撤消父程，父的

撤消会撤消全部子程°

、引起建程的事件：

1.用登：端用建立一程

2.作度：被度的作建立程

3.提供服：如要打印建立打印程

4.用求：由用程序建立多个程

程管一瞿t

♦:♦三'程的建：（creat原）

米1,申空白PCB（一个系的PCB是有限的）

米2.新程分配源（不同于一般的分配，PCB-

LIST在一个特殊区域）

米3.初始彳匕PCB

米4.将新程插入就列。

procedureCreate(n,S0,k0,M(),R()

begin

/*求分配PCB空

I:=Getinternalname(n);

/*初始化PCB

Id(i):=n;

Priority(i):=kG;

Cpustate(i):=S0;

Mainstore(i):=M();

Resourse(i):=R0;

Status⑴：='readys,;

Parent(i):=CALLER;

/*插入就列

Insert(RL,i);

end

2.2.2程的止

一、引起程止的事件

*1.正常束:女口Halt'logoff

米2.异常束:女口Protecterrorovertime等

米3.外界干：

■a.系kill程；

■b.父程止；

■c.父程求。

二程的止程

米(1)程状；

米(2)行一一＞中止，且置度志真

米(3)有无子需止。

米(4)源其父程或系。

米(5)MPCB列中移出PCB.

procedureDestroy(n)

begin

Sched:=false;/*Sched度志

i:=searchinternalname(n);

Kill(i);

ifsched=truethenSCHEDULER;

End

Procedurekill(i);

Begin

Ifstatus(i)=?running'then

Begin

Stop(i);

Sched:=true;

End

REMOVE(Queue(i),i);

Forallpeprogeny(i)dokill(p);

Forallreresoures(i)doRELEASE(r);

RELEASE(PCB(i));

End

w

2.2.3程的阻塞与醒

♦:♦一、引起程阻塞和醒的事件

米1.求系服而得不到足，如向系求

打印服°

米2.后某操作而需同步：如操作和求

操作的程需同步运行（即非异步操

作）。

米3.新数据尚未到达：如程A写，程B

,A未写，完B不能°

米4.无新工作可做°

*W萱/

程阻塞程：

是程自身的一主行

a.block原

b.停止行，修改PCB入阻塞列（一个

或多个），并度。

第二章程管一理々

——---«__~---

procedureblock(n)

begin

i:=searchinternalname(n);

Stop(i);

Status(i):=Jblockeda,;

Insert(BL,i);

SCHEDULER

End

。三、醒程：

米其它相程完成°

"a.wakeup原

米b.修改PCB,人就歹U

米可，有block原，在其它程中就有

wakeup原°

程管.类

procedurewakeup(n)

begin

i:=searchinternalname(n);

Ifstatus(i)=?blockeda'then

Status⑴：='readya,;

Insert(AL,i);

SCHEDULER

end

2,2.4程的挂起与激活

-、程的挂起程

米由程自己或其父程suspend原完成,籽

程PCB移到指定区域，注意状的改，有可

能要重新度°

章一程萱）

proceduresuspend(n)

begin

i:=searchinternalname(n);

Casestatus(i)of

4blockeda?:status⑴：='blockeds，;

'readya':status⑴：=’readys’;

'running':beginstop(i);

status⑴：='readys’;

SCHEDULERend;

endcase

end

;♦二、程的激活程°

米active原(如在外存，入内存，改状，根据情

况看是否度，如先或非先)°

procedureactive(n)

begin

i:=searchinternalname(n);

Ifstatus⑴='readys,then

Beginstatus(i):=’readya,;

SCHEDULERend

Elsestatus(i):=’blockeda'

End

2.3程同步

同步一

效的并程在行次序上的，以达到有

再源共享和相互合作，使程序行有可

1生

Q

231程同步的基本概念

L两形式的制系

米源共享系：（程接制）

•需互斥地界源°

米相互合作系：（程直接制）

2..界源：（一次允一个程的源）

米引起不可再性是因界源没有互斥

==

3.介区

*定：程界源的那段代°

。可把一个界源的循程描述如下

repeat*

entrysection入区：有无程入

criticalsection;♦界区：

退出国：将志位

exitsection

remaindersection;*

untilfalse;

4.同步机制遵循的准

。空

♦:♦忙等待

。有限等待：保有限等待，不会生死等

Q)

等待：不能入界区的行程放弃

CPU行°

2.3.2信号量机制

1整型信号量

米是一个整型量，通2个原子操作wait(s)和

signal(s)来0

Wait(s):whiles<=0dono-op

s:=s-1;

Signal(s):s:=s+1;

信号量的用

。利用信号量互斥

例：两个并程共享一个赛区用信量机制保互斥

分析：

A

B

解：信号量S,初1；

「篝二阜i二一邕一里

A程B程

P(S)P(S)

使用I/O使用I/O

V(S)V(S)

varmutex:semaphore:=l

begin

parbegin

processl:begin

repeat

wait(mutex);

criticalsetion

signal(mutex);

remaindersection

untilfalse;

end

w

process!:begin

repeat

wait(mutex);

criticalsetion

signal(mutex);

remaindersection

untilfalse;

end

parend

芋^第二章一程.管一三

♦:♦利用信号量前系

例1：P1程P2程

n1=1n2=3

n3=n1+n2

分析：存在同步系：P2Tpi

解：置公共信号量S,初0°

P1程P2程

P(S)a2

alV(S)

注：al表示Pl程的句，a2表示P2程的句

例2.利用信号量来描述下面前系

2-10削例

*

Vara,b,c,d,eXg-semaphore:=0,0,0,0,0,0,0;

Begin

parbegin

beginSI;signal(a);signal(b);end;

beginwait(a);S2;signal(c);signal(d);end;

beginwait(b);S3;signal(e);end;

beginwait(c);S4;signal(f);end;

beginwait(d);Sl;signal(g);end;

beginwait(e);wait(f);wait(g);S6;end;

parend

end

程一管事

小

LPV操作有共享量信号量存在，所以其程序是一个

界区°PV操作是原子操作，行不可中断。信号量只

能通PV操作改其°

2.互斥的模式PV是成出在同一程中；

同步的模式PV是成出在不同程中；

用信号量描述前系有多少前系置多少个信

号量，初0；有多少前做多少P操作，有多少后

点做多少V操作，无前不做P操作°

典型分析

。教材P69第28:采集程和算程共享一冲区，采

集程野数据送入冲区，算程M轴酿出据算

O

提示:每一源置一个信号量

。桌上有一空，允存放一只水果，爸爸可向内放革

果或桔子，儿子等吃桔子，女儿等吃基果°

分析:本是生者-消者的一形,生者放入冲

区的品有两，消者也有两，每消者只消其中固定

的~,品

i.解：

process2:begin*

Varempty,full:semaphore=1,0；♦

begin*repeat*

parbegin*wait(full);*

process1:begin*criticalsection*

repeat*signal(empty);*

wait(empty);♦remaindersection*

criticalsection*until

signal(full);*false;*

remainderend*

section*untilfalse;parend

end

2.解：son:beginrepeat*

Vars,so,sa:semaphore=1,0,0;*wait(so);*

begin*l\k中取出

parbegin*桔子；

father:begin*signal(s);

repeat*

吃桔子；♦

wait(s);*

untilfalse;*

将水果放

入中；end

if放入的是桔子daughter:begin*repeat*

thensignal(so);wait(sa);*

elsesignal(sa);*

取出莘果；

untilfalse;*

signal(s);

end

w

2型信号量

❖引入：

在整型信号量机制中的wait操作，只要是信号量

S<0,就会不断地。因此，机制并未遵循“等

待'’的准，而是使程于“忙等”的状°

♦:♦解决方案：

typesemaphore=record

value:integer;

L:listofprocess;

end

L:程表，用于接所有等待源程°

*

procedurewait(S)

varS:semaphore

begin

S.value:=S.value-1;

ifS.value<0themblock(S,L)

end

proceduresignal(S)

varSrsemaphone

begin

S.value:=S.vaule+1

ifS.value<=0thenwakeup(S.L)

end

用wait(S)和signal(S)同步与互斥°

c-<

二早管二A

明：

l.S.value>0,表示系中可用源的数目。

2.当S.value<0,S.value的表示阻塞程的数目°

3.如果S.value的初1,表示只允一个程界源

,此的信号量化互斥信号量°

Aye----*■程萱w

3AND型信号量

♦:♦引入：

processA:processB:

wait(Dmutex);wait(Emutex);

wait(Emutex);wait(Dmutex);

若2程交替行，死

3AND型信号量

。特点：要全分配，要一个也不分配

♦:♦当不用它，有可能生系死。

♦:♦死：在无外力作用下的一僵持状

3AND型信号量

Swait(sl,s2,...,sn)

ifsl>land...andsn>1then

fori:=ltondosi:=si-l;endfor

else

placetheprocessinthewaitingqueuewiththefirstsifoundwith

si<l,andsettheprogramcountofthisprocesstothebeginningof

swaitoperation

endif

Ssignal(sl,s2,...,sn)

fori:=ltondosi:=si+l;

removealltheprocesswaitinginthequeueassociatedwithsiintothe

readyqueue

endfor

第二章程管/

4信号量集

。提高效率而AND信号的充

♦:♦允一次申多源多个°

Swait(SptpdpSn,tn,dn)<

ifand...andSn>tnthen*

fori=1tondo*

0=Srdi；*

endfor*

else*

PlacetheexecutingprocessinthewaitingqueueofthefirstSjwithSj<'

andsetitsprogramcountertothebeginningoftheSwaitOperation.♦

endif*

signal(SpdpSn,4)♦

fori・=1tondo*

Sj=oSi+4；*

RemovealltheprocesswaitinginthequeueassociatedwithSjintotheready

queue*

endfor;J.

♦:♦三特例：

(1)Swait(S,d,d):允每次申d个源。

当源数少于d,不予分配°

(2)Swait(s,1>1):S>1,型信号量°

S=1,互斥型信号量。

(3)Swait(s,l,O),可控，当，允入，Svl

，不能入。

2.4典程同步

❖2.4.1生者一一消者

<*2.4.2哲学家餐

<*2.4.3者——写者

2.4」生者一消者

描述

生者一消者(Producer-Consumer)是著名

的程同步。它描述一生者向一消者提供消

息，它共享一个包含n个冲的有界池，生

者向其中投放消息，消者队中取得消息°

»在操作系中，生者程可以是算程、送程；而消者程

可以是打印程、接收程等°

»解决好生者--消者就解决好了一并程的同步O■

放消息取消息

1

n个冲区

(Buffer)

定数据构

Varn:integer;

Typeitem=...;〃品型

varbuffer:array[04v*?n-l]ofitem;//冲池

in,out:0,1,・・・,n-1;

counter://品数

当冲池，生者等待，空，消者等待

程描述如下是否存在?

producer:consumer:

repeatrepeat

•••whilecounter=0dono-op;

produceaniteminnextp;nextc:=buffer[out];

•••out:=(out+l)modn;

whilecounter=ndono-op;counter:=counter-l;

buffer[in]:=nextp;consumertheitemin

in:=(in+l)modn;nextc;

counter:=counter+l;untilfalse;

untilfalse;

i

registerl:=counter;registerl:=counter;

registerl:=registerl+l;registerl:=register2-l;

counter:=registerl;counter:=register2;

counter白勺初5

registerl:=counter;(registerl:=5)

registerl:=registerl+l;(registerl:=6)

register!:=counter;(register!:=5)

register!:=register2-l;(register!:=4)

counter:=registerl;(counter:=6)

counter:=register2;(counter:=4)

♦:♦利用型信号量解决生者一消者

定互斥信号量mutex,使程互斥地冲

池，empty、fullr表示空、冲区数量。初分

1,n,。。

1产房此才支清费渚遗窃

描述如下

Varmutex,empty,full:semaphore:=l,n,0;

buffer:array[0,1v•?n-l]ofitem;

in,out:integer:=0,0;

begin

parbegin

producer:beginconsumer:begin

repeatrepeat

•••wait(full);

Produceaniteminnextp;wait(mutex);

•••nextc:=buffer(out);

wait(empty);out:=(out+l)modn;

wait(mutex);signal(mutex);

buffer(in):=nextp;signal(empty);

in:=(in+l)modn;Consumertheitemin

signal(mutex);nextc;

signal(full);Untilfalse;

untilfalse;end

endparend

end

producer:beginconsumer:begin

repeatrepeat

•••wait(mutex);

Produceaniteminnextp;wait(full);

•••nextc:=buffer(out);

wait(mutex);out:=(out+l)modn;

wait(empty);signal(empty);

buffer(in):=nextp;signal(mutex);

in:=(in+l)modn;Consumertheitemin

signal(full);nextc;

signal(mutex);Untilfalse;

untilfalse;end

endparend

end

*

于用信号量机制解决生者消者：

♦:*p操作的序是否可交？

♦:*v操作的序是否可交？

♦:♦什情况下互斥信号量mutex可以省略，什

?*

P操作的序至重要，序不当可能致死，而两个V操

作无要；当yWW—，mutex可省略°

。利用AND信号量解决生者消者

varmutex,empty,full:semaphore:=l,n,0;

buffer:array[O,...,n-l]ofitem;

inout:integer:=0,0;

begin

parbegin

producer:begin

repeat

•••

produceaniteminnextp;

•••

swait(empty9mutex);

buffer(in):=nextp;

塞上一翼一搴

in:=(in+l)modn;

ssingal(mutex9full);

Untilfalse;

End

Consumer:begin

repeat

swait(full9mutex);

nextc:=buffer(out);

out:=(out+l)modn;

ssignal(mutex9empty);

consumertheiteminnextc;

untilfalse;

end

parend

end

5个哲学家用5只筷子吃面条，筷子交替放

01.利用型信号量解决哲学家餐

信号量如何置？

>1个信号量表示筷子，初5?

>5个信号量表示5只筷子，初均,

1?

分析：了筷子的互斥使用，可以用一个信号量表示

一只筷子，由五个信号量构成信号量数。其描述如下

Varchopstick:array[0,…，4]of

semaphore={1,1,1,1,1};

第i个哲学家的活描述

Varchopstick:array[0,4]ofsemaphore={14444}；

Repeat

wait(chopstick[i]);可能死！是一个

wait(chopstick[(i+l)mod5]);

的描述！

•••

eat

signal(chopstick[i]);

signal(chopstick[(i+l)mod5]);

think;描述有?

Untilfalse

可采取以下几解决方法：♦

(1)至多只允有四位哲学家同去拿左的筷子，最能

保至少有一位哲学家能餐，并在用能放出他用

的两只筷子，AA而使更多的哲学家能餐°

(2)定奇数号哲学家先拿他左的筷子，然后再去拿右

的筷子；而偶数号哲学家相反。按此定，任何一个哲

学家拿到一支筷子以后，就已阻止了他座的一个哲学

家吃的企，除非某个哲学家一只吃下去，否不会有

人会死。

(3)当哲学家的左、右两只筷子均可用，才允他拿起

筷子餐。足

方案一：只允4个哲学家同餐

解：置一个信号量Sm来限制同餐的哲学家数目

,使他不能超4,故Sm的初置4°，第i个

哲学家的活可描述：

repeat*wait(Sm);

wait(chopstick[i]);♦

wait(chopstick[(i+1)mod5]);♦

eat;*

signal(chopstick[i]);♦

signal(chopstick[(i+1)mod5]);♦

signal(Sm);*

think;*

untilfalse;

方案二：奇数号哲学家先拿左的筷子，偶数号哲学家相反

第i个哲学家的活可描述：

repeat*ifimod2==0then

beginwait(chopstick[i]);wait(chopstick[(i+1)mod5]);♦

eat;*

signal(chopstick[i]);signal(chopstick[(i+1)mod5

])；

end*

elsebeginwait(chopstick[(i+1)mod5]);

wait(chopstick[i]);♦

eat;*

signal(chopstick[(i+1)mod5]);

signal(chopstick[i]);

end♦

think;*

方案三：当左、右两只筷子均可用，才拿起筷子餐

。利用AND信号量解决哲学家餐，可得最的解

*

Varchopstick:array[0,4]ofsemaphore:=(l,l,1,1,1)；

processi

Repeat

think;

Sswait(chopstick[(i+l)mod5],chopstick[i]);

eat

Ssignal(chopstick[(i+l)mod5],chopstick[i]);

Untilfalse

思考：如何用型信号量机制来方案三？

♦:♦利用整型信号量机制解决的参考描

*

efineN5/*哲学家数目*/

#defineLEFT(i-l)%N/*i的左号*/

#defineRIGHT(i+l)%N/*i的右号*/

#defineTHINKING0

#defineHUNGRY1

#defineEATING2

typedefintsemaphore;/*信号量是一个特殊的整形量

*/

intstate[N];/*每个人状的数*/

semaphoremutex=1;/*数state的互斥量*/

semaphores[N]={0,0,0,0,0};/*每个哲学家一个信

量*/

main()

{cobegin

philopher(O);/*哲学家的活*/

philopher(1);

philopher(2);

philopher(3);

philopher(4);

coend

voidphilopher(inti)/*i:哲学家号，人人0至(JN-

1*/

{while(1)/*无限循*/

{think();/*正在思考*/

take_forks(inti);/*需要两支筷子，或者阻塞*/

eat();/*餐*/

put_forks(i);/*把两支筷子放回桌上*/

voidtake_forks(inti)

{P(mutex);/*入界区，数state*/

state[i]=HUNGRY;/*下哲学家的事*/

test(i);/*得到两支筷子*/

V(mutex);/*离界区*/

P(s[i])；/*如果得不到筷子就阻塞*/

,

voidput_forks(inti)

{P(mutex);/*入界区*/

state[i]=THINKING;/*哲学家餐束，思考*/

test(LEFT);/*看左居是否能餐*/

test(RIGHT);/*看右居是否能餐*/

V(mutex);/*离界区*/

voidtest(inti)

{if(state[i]==HUNGRY&&statefLEFT]!=EATING

&&state[RIGHT][=EATING)

{state[i]=EATING;V(s[i]);}}

w

2.4.3者写者

描述：

米程可共享同一象。

米写程不可共享同一象

。分析：

整型量readcount--表示者数；

信号量：rmutex--互斥readcount;

wmutex--写互斥；

利用型信号量机制描述如下:

varrmutex,wmutex:semaphore:=1,1；

readcount:integer:=0;ifreadcounf=0

beginthensignal(wmutex);

parbegin

signal(rmutex);

reader:begin

repeatuntilfalse;end

wait(rmutex);writer:begin

ifreadcount=0

repeat

thenwait(wmutex);

readcount:=readcount+l;wait(wmutex)

signal(rmutex);performwriteoperation;

♦♦♦

performreadoperationsignal(wmutex)

untilfalse;

wait(rmutex);end

readcount:=readcount-l;parend

end

思考

修改算法，使得者写者算法耳者先。即当写程

到达，后的程必等待°

提示：增加信号量S（初1）,用于在写程到达

后封后者。

“写者先”描述如下：wait(rmutex);

varrmutex,wmutex,s:semaphore:=1,1J；readcount:=readcount-l;

readcount:integer:=0;

ifreadcount=0

begin

parbeginthensignal(wmutex);

reader:beginsignal(rmutex);

repeatuntilfalse;end

wait(s);wait(rmutex);

writer:begin

ifreadcount=0

thenwait(wmutex);repeat

readcount:=readc