第二章程管/

第二章程管理

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