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

第二章進(jìn)程管理

.2.1進(jìn)程的基本概念

.2.2進(jìn)程管理

<2.3進(jìn)程間的同步與互斥

.2.4進(jìn)程通訊

?2.5線程

2.1進(jìn)程的基本概念

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

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

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

勵(lì)現(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前趨圖

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

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

2,并行語言

類Pascal的并行語句。

COBEGIN

S]；S2；???5

COEND

COBEGIN/COEND相當(dāng)于一個(gè)括號，表示其中的所

有語句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ā)運(yùn)行

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

cobegin

progamA

progamB

while(l){(

while(l){

N++;

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

N=0;

}

)

)

)

coend

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

-間斷（異步）性："運(yùn)行一暫停一運(yùn)行”；

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

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

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

-失去封閉性

P37

進(jìn)程(PROCESS)的概念

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

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

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

■進(jìn)程的定義

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

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

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

?進(jìn)程的特征P38

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

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

存期

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

位，是能獨(dú)立運(yùn)行的基本單位

?并發(fā)性：程序在建立進(jìn)程后并發(fā)運(yùn)行

?異步性

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

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

?進(jìn)程是暫時(shí)的，程序的永久的

?進(jìn)程與程序的組成不同

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

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

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

2.2進(jìn)程管理

進(jìn)程的狀態(tài)

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

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

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

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

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

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

身不具備運(yùn)行條件而受到阻塞，處于暫停狀

態(tài)

Running

等待事件

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

Blocked

夕事件發(fā)生

進(jìn)程的狀態(tài)

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

-掛起：強(qiáng)迫進(jìn)程釋放分配到的資源，將進(jìn)程

調(diào)出到外存

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

就緒和活動阻塞

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

緒和靜止阻塞

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

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

Dispatch-/

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

_J-Timeout-J_

S

J

m

o

o

。

Blocked

進(jìn)程控制塊(PCB,processcontrolblock)

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

?程序：描述進(jìn)程要完成的功能

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

區(qū)

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

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

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

進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志

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

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

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

?進(jìn)程標(biāo)識符：

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

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

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

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

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

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

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

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

進(jìn)程通訊機(jī)制

隊(duì)列指針

家族聯(lián)系

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

■PCB的組織方式

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

描整個(gè)表

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

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

index表

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

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

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

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

進(jìn)程控制

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

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

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

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

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

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

?進(jìn)程圖

父、子進(jìn)程

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

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

?進(jìn)程創(chuàng)建

創(chuàng)建過程

進(jìn)程終止Pi

?引起進(jìn)程終止的事件

?進(jìn)程的終止過程

進(jìn)程阻塞與喚醒P46

?引起進(jìn)程阻塞與喚醒的事件

?阻塞、喚醒過程

掛起與激活已

?進(jìn)程掛起

?激活過程

2.3進(jìn)程間的同步與互斥

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

-間接制約：進(jìn)行競爭一一獨(dú)占分配到的部分或全部共享資源,

“互斥”

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

臨界資源(CriticalResource)

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

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

互斥：多個(gè)進(jìn)程不能同時(shí)使用同一個(gè)資源；

死鎖：多個(gè)進(jìn)程互不相讓，都得不到足夠的資源；

饑餓：一個(gè)進(jìn)程一直得不到資源(其他進(jìn)程可能輪流占用

資源)

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

/*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;

輸出一張機(jī)票；

)

else

顯示“票已售完”；

共享變量的修改沖突:

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

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

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

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

entrysection

criticalsection

exitsection

remaindersection

增加一段檢查的代碼

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

臨界資源的一段代碼。

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

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

?退出區(qū)(exitsection)

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

條部分。

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

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

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

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

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

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

互斥算法

■進(jìn)程互斥的軟件方法

卜算法1:單標(biāo)志

-有兩個(gè)進(jìn)程Pi,Pj,其中的Pi

while(turn!=i);

criticalsection

turn=j;

remaindersection

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

界區(qū)的進(jìn)程標(biāo)識

?缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮

進(jìn)程的實(shí)際需要。容易造成資源利用不

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

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

＞算法2：雙標(biāo)志

?設(shè)立一個(gè)標(biāo)志數(shù)組flag□:描述進(jìn)程是否要求進(jìn)入

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

?turn二j;描述可進(jìn)入的進(jìn)程（同時(shí)修改標(biāo)志時(shí)）

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

intflag[2]={0,0};

/*進(jìn)入臨界區(qū)*/

intturn=O;

criticalsection

/*進(jìn)程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;

)

?進(jìn)程互斥的鎖操作方法

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

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

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

■鎖操作方法

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

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

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

缺點(diǎn)：

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

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

?擴(kuò)大了互斥范圍；

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

信號量(semaphore)

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

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

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

typedefstruct{

intvalue;/*信號量的值*/

PCB*ptr_of_semque;

}semaphore;

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

ptr_of_semque：指向等待使用該信號量的進(jìn)程隊(duì)列的隊(duì)首

信號量初始化：

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

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

值其絕對值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù)

?L：鏈接等待的進(jìn)程指針

?P操作wait⑸

?V操作signal(s)

V操作通常喚醒進(jìn)程等待隊(duì)列中的頭一個(gè)進(jìn)程

p51

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

P(mutex);二

criticalsection

V(mutex);

remaindersection

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

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

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

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

重復(fù)或遺漏

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

semaphoremutex={l,NULL};

cobegin

programpi

(

while(l){

P(&mutex)；

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

V(&mutex)；

remaindersectionforpi;

)

)

coend

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

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)；

輸出一張機(jī)票;

}

解決共享變量的修改沖突

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

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

semaphoreproceed1:{0,NULL};

cobegin

進(jìn)程pl

P(&proceedl)；

V(&proceedl)；

coend

例：一輛公共汽車上，司機(jī)和售票員進(jìn)程的同步

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)；/*喚醒司機(jī)開車*/

)

)

coend

信號量應(yīng)用

?實(shí)現(xiàn)進(jìn)程互斥

互斥訪問臨界資源

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

P54

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

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

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

讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程

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

Producer1Consumer1

生產(chǎn)指針消費(fèi)指針

Producer2Consumer2

ProducerM>￡2X)ConsumerN

□x)

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

?采用信號量機(jī)制:

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

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

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

?每個(gè)進(jìn)程中各個(gè)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)

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

一時(shí)刻“寫者”最多只允許一個(gè)，而

“讀者”則允許多個(gè)

—“讀一寫”互斥，

—“寫一寫，，互斥，

-"讀一讀〃允許

?采用信號量機(jī)制：

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

-公共變量Readcount表示“正在讀”的進(jìn)程數(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)；