【計算機課件】軟件學院計算機操作系統(tǒng)講解課件-進程管理

第二章進程管理

.2.1進程的基本概念

.2.2進程管理

<2.3進程間的同步與互斥

.2.4進程通訊

?2.5線程

2.1進程的基本概念

程序的順序執(zhí)行和并發(fā)執(zhí)行

■順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式，也

用于簡單的單片機系統(tǒng)；

勵現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行，具有許多

新的特征。引入并發(fā)執(zhí)行的目的是為了提高

資源利用率。

程序的順序執(zhí)行

?例：程序段

read(disk,&a,4);/*從磁盤讀a*/

read(tape,&b,4);/*從帶讀b*/

c=a+b;

printf("c=%f\n〃,c);

?順序執(zhí)行的特征

-順序性

-封閉性

-可再現(xiàn)性

程序并行性表示

L前趨圖

是一個有向無環(huán)圖，圖中每個結(jié)點表示一個語句、一段程序或一個進程

有向邊V7?＞切表示嶗僅在0執(zhí)行完后才能開始執(zhí)行

2,并行語言

類Pascal的并行語句。

COBEGIN

S]；S2；???5

COEND

COBEGIN/COEND相當于一個括號，表示其中的所

有語句Si，S2f...Sn可并行執(zhí)行。

并發(fā)執(zhí)行及其特征

例：si:read(disk,&a,4);/*從磁盤讀a*/

s2:read(tape,&b,4);/*從帶讀b*/

s3:c=a+b;

si和s2可并發(fā)，s2和s3不可并發(fā)

書中p36e.g.

多道程序系統(tǒng)：資源共享;程序的并發(fā)運行

例：intN=O;/*全局變量*/

cobegin

progamA

progamB

while(l){(

while(l){

N++;

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

N=0;

}

)

)

)

coend

?并發(fā)執(zhí)行的特征

-間斷（異步）性："運行一暫停一運行”；

并發(fā)程序之間依賴相互、相互制約

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

-不可再現(xiàn)性（e.g.NPrint（N））

-失去封閉性

P37

進程(PROCESS)的概念

?一個具有一定獨立功能的程序在一個數(shù)據(jù)集合

上的一次動態(tài)執(zhí)行過程。

?是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位

■進程的定義

是并發(fā)程序的一次執(zhí)行過程，它由一個動作序列組

成，每個動作是在某數(shù)據(jù)集上執(zhí)行一段程序，整個

活動的結(jié)果是提供一種系統(tǒng)或用戶功能。

?進程的特征P38

■結(jié)構(gòu)特征

?意態(tài)性:產(chǎn)生、執(zhí)行、暫停、消亡。有一個生

存期

?獨立性：是系統(tǒng)進行資源分配和調(diào)度的獨立單

位，是能獨立運行的基本單位

?并發(fā)性：程序在建立進程后并發(fā)運行

?異步性

■進程與程序的區(qū)別

?進程是動態(tài)的，程序是靜態(tài)的

?進程是暫時的，程序的永久的

?進程與程序的組成不同

■進程與程序的聯(lián)系

?通過多次執(zhí)行，一個程序可對應(yīng)多個進程;

通過調(diào)用關(guān)系，一個進程可包括多個程序。

2.2進程管理

進程的狀態(tài)

-三種基本調(diào)度狀態(tài)

?運行狀態(tài)：進程分配到必要的資源，在CPU上

執(zhí)行時的狀態(tài)

?就緒狀態(tài)：進程分配到必要的資源，還沒獲

得在CPU上執(zhí)行的狀態(tài)

?阻塞狀態(tài)（等待狀態(tài)）：進程的執(zhí)行由于本

身不具備運行條件而受到阻塞，處于暫停狀

態(tài)

Running

等待事件

（系統(tǒng)服務(wù)請求，如請求I/O））

Blocked

夕事件發(fā)生

進程的狀態(tài)

■細分的進程調(diào)度狀態(tài)（另一些系統(tǒng)）

-掛起：強迫進程釋放分配到的資源，將進程

調(diào)出到外存

?活動：未被掛起的就緒和阻塞狀態(tài)稱為活動

就緒和活動阻塞

?靜止：被掛起的就緒和阻塞狀態(tài)稱為靜止就

緒和靜止阻塞

進程的狀態(tài)轉(zhuǎn)換：

一三狀態(tài)進程模型

Dispatch-/

New)Admit―?(Ready)(Running)—Release—i/Exit

_J-Timeout-J_

S

J

m

o

o

。

Blocked

進程控制塊(PCB,processcontrolblock)

■進程的物理結(jié)構(gòu)

?程序：描述進程要完成的功能

?數(shù)據(jù)集合：包含程序運行所需的數(shù)據(jù)和工作

區(qū)

?進程控制塊(PCB)：包含進程的描述信息和

控制信息，是進程動態(tài)特性的反映

程序和數(shù)據(jù)集合是進程的實體

進程控制塊是進程存在的唯一標志

進程控制塊是由OS維護的用來記錄進程相關(guān)

信息的一塊內(nèi)存。

■進程控制塊的內(nèi)容

?進程標識符：

^（processID）（內(nèi)部標識符）：唯一，通常

-進程名（外部標識符）：不唯一，由字母數(shù)字組成；

窟亶信息：指出進程的程序和數(shù)據(jù)在內(nèi)存和外存中的物理

器值（通用、程序計數(shù)器PC、狀態(tài)PSW,地

狀態(tài)信息：進程現(xiàn)行狀態(tài)

進程優(yōu)先級：進程使用CPU的優(yōu)先級別

資源清單：已分配到的資源等

同步與互斥機構(gòu)

進程通訊機制

隊列指針

家族聯(lián)系

資源占甫信息：虛擬地址空間的現(xiàn)狀、打開文件列表

■PCB的組織方式

?順序表：將所有PCB連續(xù)存放在內(nèi)存。要經(jīng)常掃

描整個表

?索引表：同一狀態(tài)的PCB建立一個index表（由

index指向PCB）,多個狀態(tài)對應(yīng)多個不同的

index表

-各狀態(tài)形成不同的索引表：就緒索引表、阻塞索引表

-鏈表：同一狀態(tài)的進程的PCB成一鏈表，多個狀

態(tài)對應(yīng)多個不同的鏈表

-各狀態(tài)的形成不同的鏈表：就緒鏈表、阻塞鏈表

進程控制

■進程控制的功能完成進程狀態(tài)的轉(zhuǎn)換。

原語(primitive)：由若干條指令構(gòu)成的“原子

操作(atomicoperation)”過程，作為一個整體

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

許多系統(tǒng)調(diào)用就是原語。

進程創(chuàng)建P43-44

?進程圖

父、子進程

?引起進程創(chuàng)建事件

用戶登錄、作業(yè)調(diào)度、提供服務(wù)、應(yīng)用請求

?進程創(chuàng)建

創(chuàng)建過程

進程終止Pi

?引起進程終止的事件

?進程的終止過程

進程阻塞與喚醒P46

?引起進程阻塞與喚醒的事件

?阻塞、喚醒過程

掛起與激活已

?進程掛起

?激活過程

2.3進程間的同步與互斥

?進程間的制約關(guān)系

-間接制約：進行競爭一一獨占分配到的部分或全部共享資源,

“互斥”

-直接制約：進行協(xié)作一一等待來自其他進程的信息，“同步”

臨界資源(CriticalResource)

系統(tǒng)中一次僅允許一個進程使用的一類資源。

打印機，卡片輸入機，磁帶機、共享變量等。

互斥：多個進程不能同時使用同一個資源；

死鎖：多個進程互不相讓，都得不到足夠的資源；

饑餓：一個進程一直得不到資源(其他進程可能輪流占用

資源)

例：民航售票系統(tǒng)，n個售票處

/*ProcessPi,1=1,2,...,n*/

/*按訂票要求找到共享數(shù)據(jù)x[k]*/

〃x[k]存放某月某日某次航班的現(xiàn)有票數(shù)*/

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=l){

R—;

x[k]=R;

輸出一張機票；

)

else

顯示“票已售完”；

共享變量的修改沖突:

把變量x[k]作為臨界資源處理

臨界區(qū)：訪問臨界資源的那段代碼（程序段）。

同類臨界區(qū):對同一臨界資源進行操作的程序段。

臨界區(qū)的訪問過程

entrysection

criticalsection

exitsection

remaindersection

增加一段檢查的代碼

?臨界區(qū)(criticalsection)：進程中訪問

臨界資源的一段代碼。

?進入?yún)^(qū)(entrysection)：在進入臨界區(qū)之

前，檢查可否進入臨界區(qū)的一段代碼。

?退出區(qū)(exitsection)

?乘馀區(qū)(remaindersection)：代碼中的其

條部分。

■同步機制應(yīng)遵循的準則

?空閑則入：其他進程均不處于臨界區(qū)；

-忙則等待：已有進程處于其臨界區(qū)；

-有限等待：等待進入臨界區(qū)的進程不能"死等"；

?讓權(quán)等待：不能進入臨界區(qū)的進程，應(yīng)釋放CPU

（如轉(zhuǎn)換到阻塞狀態(tài)）

互斥算法

■進程互斥的軟件方法

卜算法1:單標志

-有兩個進程Pi,Pj,其中的Pi

while(turn!=i);

criticalsection

turn=j;

remaindersection

?設(shè)立一個公用整型變量turn：描述允許進入臨

界區(qū)的進程標識

?缺點：強制輪流進入臨界區(qū)，沒有考慮

進程的實際需要。容易造成資源利用不

充分：在Pi出讓臨界區(qū)之后，Pj使用臨

界區(qū)之前，Pi不可能再次使用臨界區(qū)；

＞算法2：雙標志

?設(shè)立一個標志數(shù)組flag□:描述進程是否要求進入

臨界區(qū)或已在臨界區(qū)，初值均為FALSE

?turn二j;描述可進入的進程（同時修改標志時）

?在進入?yún)^(qū)先修改、后檢查、后修改者等待

intflag[2]={0,0};

/*進入臨界區(qū)*/

intturn=O;

criticalsection

/*進程pi的結(jié)構(gòu)*/

/*退出臨界區(qū)]*/

while(l){

flag[i]=l;turn=j;

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

if(turn==j){remaindersection

flag[i]=O;}

while(turn==j);

flag[i]=l;

)

?進程互斥的鎖操作方法

?每一類臨界資源設(shè)置一把鎖lock。

?lock表示資源的兩種狀態(tài)：TRUE表示正被占用（鎖

關(guān)狀態(tài)）；FALSE表示空閑（鎖開狀態(tài)）

■鎖操作方法

，用開、關(guān)中斷實現(xiàn)鎖操作

執(zhí)行臨界區(qū)程序

優(yōu)點：簡單、可靠

缺點：

?不能實現(xiàn)所有的同類臨界區(qū)互斥；

?臨界區(qū)太長時，降低了中斷響應(yīng)速度;

?擴大了互斥范圍；

?加鎖時CPU不斷測試，處于忙等待。

信號量(semaphore)

信號量表示臨界資源的實體，是一個數(shù)據(jù)結(jié)構(gòu)，其

值僅能由P、V操作來改變。,

阻塞等待信號量數(shù)據(jù)結(jié)構(gòu)：

typedefstruct{

intvalue;/*信號量的值*/

PCB*ptr_of_semque;

}semaphore;

PCB:進程控制塊的數(shù)據(jù)類型

ptr_of_semque：指向等待使用該信號量的進程隊列的隊首

信號量初始化：

?Value:指定一個非負整數(shù)值，表示空閑資源總數(shù)

——若為非負值表示當前的空閑資源數(shù)，若為負

值其絕對值表示當前等待臨界區(qū)的進程數(shù)

?L：鏈接等待的進程指針

?P操作wait⑸

?V操作signal(s)

V操作通常喚醒進程等待隊列中的頭一個進程

p51

?利用信號量實現(xiàn)互斥

P(mutex);二

criticalsection

V(mutex);

remaindersection

?為臨界資源設(shè)置一個互斥信號量mutex(MUTual

Exclusion),其初值為1；在每個進程中將臨界區(qū)

代碼置于P(mutex)和V(mutex)原語之間

」必須成對使用P和V原語，P、V原語不能次序錯誤、

重復(fù)或遺漏

信號量實現(xiàn)互斥模型：

semaphoremutex={l,NULL};

cobegin

programpi

(

while(l){

P(&mutex)；

criticalsectionforpi;/*進程pi臨界區(qū)*/

V(&mutex)；

remaindersectionforpi;

)

)

coend

例：民航售票系統(tǒng)，n個售票處

semaphoremutex={l,NULL};

else{

cobegin

V(&mutex)；

programpi

顯示“票已售完”；

)

P(&mutex)；)

coend

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=l){

x[k]=R;

V(&mutex)；

輸出一張機票;

}

解決共享變量的修改沖突

■利用信號量實現(xiàn)同步

設(shè)置一個同步信號量proceedl,其初值為0

semaphoreproceed1:{0,NULL};

cobegin

進程pl

P(&proceedl)；

V(&proceedl)；

coend

例：一輛公共汽車上，司機和售票員進程的同步

semaphoredrive_sem={O,NULL};

semaphoreconductor_sem={0,NULL};

cobegin

programdrive

(

while(l){

driving;/*正常行車*/

stopping;

V(&conductor_sem)；/*喚醒開門*/

P(&drive_sem)；/*等待關(guān)門*/

startacar;

)

programconductor

while(l){

selltickets;/*售票*/

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

openthedoor;

closethedoor;

V(&drive_sem)；/*喚醒司機開車*/

)

)

coend

信號量應(yīng)用

?實現(xiàn)進程互斥

互斥訪問臨界資源

?實現(xiàn)前趨關(guān)系

P54

經(jīng)典應(yīng)用示例

問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。

其中，〃生產(chǎn)者”進程不斷寫入，而〃消費者〃進程不斷

讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程

可對共享緩沖區(qū)進行操作。

Producer1Consumer1

生產(chǎn)指針消費指針

Producer2Consumer2

ProducerM>￡2X)ConsumerN

□x)

滿空,“共享緩沖區(qū)指針移動方向

?采用信號量機制:

-full是"滿”數(shù)目，初值為0,empty是〃空“數(shù)

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

-mutex用于訪問緩沖區(qū)時的互斥，初值是1

?每個進程中各個P操作的次序是重要的：先檢查

資源數(shù)目，再檢查是否互斥一一否則可能死鎖

（為什么？）

EaMessaEra

3nqld.gnpo」d

I)S9WM

3ndldQMessal/M

}

一」8npo」dEB」go』d

uMoqoJ

oHXQpEJoHxapu「d

.Un

」

qN】s)=nq

aliagessalAI

KTInNoT-n-M①」oqdeEas

」oqdeEas

KTlnNz}HAldEaJa

KTInNduxwnEajoqdeulas

fagessal/\l{

qNlx4IAI>e」」e

xl—l」Blp

1=

fEnu

}itn」ls-M)apodAl

eEJep#

08NT1X41Al.

N3E生

00T.p#

P(&empty)；

P(&mutex)；

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

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

p_index=(p_index+l)%N;

V(&mutex)；

V(&full)；}

)

programconsumerj

(

Messagec_buf;

while(l){

P(&full)；

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)

?問題描述：對共享資源的讀寫操作，任

一時刻“寫者”最多只允許一個，而

“讀者”則允許多個

—“讀一寫”互斥，

—“寫一寫，，互斥，

-"讀一讀〃允許

?采用信號量機制：

-rwmutex表示"允許寫"，初值是1。

-公共變量Readcount表示“正在讀”的進程數(shù)，初值是0；

rmutex表示讀者對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

寫者長期阻塞

寫者優(yōu)先算法：

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

programwriterj

cobegin

programreaderi(

inti;

(P(&rwmutex)；

P(&rwmutex)；

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

P(&rsem)；

P(&rsem)；

V(&rwmutex)；