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

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

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

.2.2進(jìn)程管理

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

.2.4進(jìn)程通訊

■2.5線建

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

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

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

用于簡(jiǎn)單的單片機(jī)系統(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)性

程序并行性表示

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

有向邊切表示外僅在必執(zhí)行完后才能開始執(zhí)行

有回路的前趨圖

前趨圖

2.并行語言

類Pascal的并行語句。

COBEGIN

C?C?.C

，口2，???，

COEND

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

有語句Sl，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ā)

書中p36eg

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

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

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ù)集合，

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

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

■進(jìn)程的定義

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

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

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

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

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

?動(dòng)態(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)程是動(dòng)態(tài)的，程序是靜態(tài)的

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

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

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

?通過多次執(zhí)行，一個(gè)程序可對(duì)應(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)

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

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

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

調(diào)出到外存

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

一就緒和活動(dòng)阻塞

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

緒和靜止阻塞

wakeup（喚醒）

wakeup（喚醒）圖：具有掛起功能的進(jìn)

程狀態(tài)變化

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

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

Dispatch

Timeout

S

+JJ

Um

①o

次o

o

進(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)程動(dòng)態(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)識(shí)符：

唯野翻（ProcessID）（內(nèi)部標(biāo)識(shí)符）|唯一，通常

-靠程名（外上標(biāo)識(shí)符）：不唯一，由字母數(shù)字組成；

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

-洋:|扇巔嚼產(chǎn)器值（通用、程序計(jì)數(shù)器P&狀態(tài)PS肌地

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

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

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

?同步與互斥機(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)對(duì)應(yīng)多個(gè)不同的

index表

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

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

態(tài)對(duì)應(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)用請(qǐng)求

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

創(chuàng)建過程

進(jìn)程終止P45.46

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

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

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

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

?阻塞、喚醒過程

掛起與激活P?

?進(jìn)程掛起

?激活過程

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

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

-間接制約：進(jìn)行競(jìng)爭(zhēng)一一獨(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,i=l,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

iLkZjs示口售兀；

共享變量的修改沖突:

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

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

同類臨界區(qū):對(duì)同一臨界資源進(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)識(shí)

?缺點(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]=0;

if(turn==j){remaindersection

flag[i]=0;)

while(turn==j);

flag[i]=l;

)

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

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

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

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

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

■鎖操作方法

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

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

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

缺點(diǎn)：

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

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

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

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

信號(hào)量(semaphore)

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

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

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

typedefstruct{

intvalue;/*信號(hào)量的值*/

PCB*ptr_of_semque;

}semaphore;

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

ptr^of_semque：指向等待使用該信號(hào)量的進(jìn)程隊(duì)列的隊(duì)首

信號(hào)量初始化：

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

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

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

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

?P操作wait⑸

signal(s)

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

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

P(mutex);

criticalsection

V(mutex);

remaindersection:

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

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

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

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

重復(fù)或遺漏

信號(hào)量實(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ī)票;

)

解決共享變量的修改沖突

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

設(shè)置一個(gè)同步信號(hào)量proceedL其初值為0

semaphoreproceedl={0,NULL};

cobegin

進(jìn)程pl

P(&proceedl)；

進(jìn)儲(chǔ)p2-

V(&proceedl)；

coend

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

semaphoredrive_sem={O,NULL};

semaphoreconductor_sem={0,NULL};

cobegin

programdrive

(

while(l){

driving;/*正常行車*/

stopping;i

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

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

startacar;

)

programconductor

while(l){

selltickets;/*售票*/

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

openthedoor;

closethedoor;

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

}一

:}

coend

信號(hào)量應(yīng)用

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

互斥訪問臨界資源

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

P54

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

1.生產(chǎn)者^—消費(fèi)者^|可^§(theproducer-consumerproblem)

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

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

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

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

Producer1Consumer1

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

Producer2__Consumer2

xX)

ProducerMConsumerN

xX)

滿/空/共享緩沖區(qū)指針移動(dòng)方向

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

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

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

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

?每個(gè)進(jìn)程中各個(gè)P操作的次序是重要的：先檢查

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

（為什么？）

算法:#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)

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

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

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

一“讀一寫”互斥，

一-“寫一寫”互斥，.

--〃讀一讀〃允許

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

-wrmutex表示〃允許寫〃，初值是1。

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

-mrutex表示讀者對(duì)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

寫者長(zhǎng)期阻塞

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

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