第2章進程和線程內容提要：

2.1進程概念

2.2進程的狀態和組成

2.3進程管理

2.4線程2.1進程概念

2.1.1多道程序設計1．順序程序活動的特點

順序性封閉性可再現性2．多道程序設計2.1.1多道程序設計

3．程序并發執行的特征①失去封閉性。②程序與計算不再一一對應。③并發程序在執行期間相互制約。2.1.2進程概念

1．引入：用程序這個靜態概念已經不能如實反映程序并發執行過程中的這些特征。2．進程概念進程最根本的屬性是動態性和并發性。進程定義為：程序在并發環境中的執行過程2.1.2進程概念進程和程序的區別：

（1）動態性（2）并發性（3）非對應性（4）異步性2.1.2進程概念

3．進程的基本特征

（1）動態性（2）并發性（3）調度性2.2進程的狀態和組成

2.2.1進程的狀態及其轉換

1．進程的基本狀態運行狀態（Running）就緒狀態（Ready）阻塞狀態（Blocked

新建狀態（New）終止狀態（Terminated）運行狀態就緒狀態阻塞狀態等待某事件發生（如等待I/O）所等待事件發生（如I/O完成）分到CPU時間片到2．進程狀態的轉換圖2-2進程的5種基本狀態及其轉換2.2.2進程描述1．進程映像進程映像由它的（用戶）地址空間內容、硬件寄存器內容和與該進程有關的核心數據結構組成。圖2-3進程映像模型2.2.2進程描述2．進程控制塊的組成進程控制塊（PCB）有時也稱進程描述塊（ProcessDescriptor），它是進程組成中最關鍵的部分，其中含有進程的描述信息和控制信息，是進程動態特性的集中反映，是系統對進程施行識別和控制的依據。進程控制塊的組成進程名特征信息進程狀態信息調度優先權通信信息現場保護區資源需求進程實體信息族系關系其他信息2.2.2進程描述3．進程控制塊的作用每個進程有惟一的進程控制塊2.2.3進程隊列1．線性方式圖2-4PCB線性隊列示意圖2.2.3進程隊列2．鏈接方式圖2-5PCB鏈接隊列示意圖圖2-6PCB索引結構示意圖2.2.3進程隊列3．索引方式2.3進程管理

2.3.1進程圖

進程圖（ProcessGraph）是描述進程族系關系的有向樹圖2-7進程創建的層次關系2.3.2進程創建

引發創建進程的事件通常是調度新的批作業，交互式用戶登錄，操作系統提供服務和現有進程派生新進程。創建新進程時要執行創建進程的系統調用（如UNIX/Linux系統中的fork），其主要操作過程有如下四步：（1）申請一個空閑的PCB

（2）為新進程分配資源（3）將新進程的PCB初始化（4）將新進程加到就緒隊列中下面這個C程序展示了UNIX系統中父進程創建子進程及各自分開活動的情況

#include<stdio.h>voidmain(int

argc,char*argv[]){

int

pid;

/*forkanotherprocess*/

pid=fork();if(pid<0){/*erroroccurred*/

fprintf(stderr,"ForkFailed");exit(-1);}

elseif(pid==0){/*childprocess*/

execlp("/bin/ls","ls",NULL);}else{/*parentprocess*//*parentwillwaitforthechildtocomplete*/

wait(NULL);

printf("ChildComplete");exit(0);}}

2.3.3進程終止（1）正常終止（2）異常終止（3）外部干擾2.3.3進程終止終止進程的主要操作過程如下：找到指定進程的PCB終止該進程的運行回收該進程所占用的全部資源終止其所有子孫進程，回收它們所占用的全部資源。將被終止進程的PCB從原來隊列中摘走2.3.4進程阻塞進程阻塞的過程如下：立即停止當前進程的執行現行進程的CPU現場保存現行狀態由“運行”改為“阻塞”轉到進程調度程序2.3.5進程喚醒喚醒原語執行過程如下：①把阻塞進程從相應的阻塞隊列中摘下。②將現行狀態改為就緒狀態，然后把該進程插入就緒隊列中。③如果被喚醒的進程比當前運行進程的優先級更高，則設置重新調度標志。2.4線程

2.4.1線程概念現代操作系統中，進程只作為資源擁有者，而調度和運行的屬性賦予新的實體——線程。線程（Thread）是進程中實施調度和分派的基本單位2.4.1線程概念

1．線程的組成每個線程有一個thread結構，即線程控制塊，用于保存自己私有的信息，主要由以下4個基本部分組成：圖2-8thread結構示意圖2.4.1線程概念

線程必須在某個進程內執行一個進程可以包含一個線程或多個線程圖2-9單線程和多線程的進程模型2.4.1線程概念

2．線程的狀態運行狀態：就緒狀態：阻塞狀態：終止狀態：2.4.1線程概念

3．線程的管理線程創建線程終止線程等待線程讓權2.4.1線程概念4．線程和進程的關系①一個進程可以有多個線程，但至少要有一個線程；而一個線程只能在一個進程的地址空間內活動。②資源分配給進程，同一進程的所有線程共享該進程的所有資源。③處理機分配給線程，即真正在處理機上運行的是線程。④線程在執行過程中需要協作同步。不同進程的線程間要利用消息通信的辦法實現同步。2.4.1線程概念5．引入線程的好處

①易于調度。

②提高并發性。

③開銷少。

④利于充分發揮多處理器的功能。2.4.2在用戶空間實現線程

把線程庫整個地放在用戶空間，核心對線程一無所知。圖2-10(a)在用戶空間實現線程2.4.2在用戶空間實現線程

1．在用戶空間實現線程的優點

①線程切換速度很快。

②調度算法可以是應用程序專用的。

③用戶級線程可以運行在任何操作系統上，包括不支持線程機制的操作系統。2.4.2在用戶空間實現線程2．用戶級線程的主要缺點①系統調用的阻塞問題。②在單純用戶級線程方式中，多線程應用程序不具有多處理器的優點。2.4.3在核心空間實現線程

核心知道線程存在，并對它們實施管理①在多處理器系統中，核心可以同時調度同一進程的多個線程；

②如果一個進程的某個線程阻塞了，核心可以調度同一個進程的另一個線程。優點是，核心線程本身也可以是多線程的。缺點，主要是控制轉移開銷大。圖2-10(b)在核心空間實現線程2.4.4組合方式

1．多對一模型圖2-11在核心級線程上有多個用戶級線程圖2-12多對一模型2.4.4組合方式

2．一對一模型圖2-13一對一多模型2.4.4組合方式

3．多對多模型圖2-14多對一多模型2.4.5線程池

2.5進程的同步和通信

①互斥

②同步

③通信2.5.1進程的同步與互斥

1．同步同步進程通過共享資源來協調活動，在執行時間的次序上有一定約束。雖然彼此不直接知道對方的名字，但知道對方的存在和作用。在協調動作的情況下，多個進程可以共同完成一項任務。2．互斥在邏輯上這兩個進程本來完全獨立，毫無關系，只是由于競爭同一個物理資源而相互制約。它們的運行不具有時間次序的特征競爭條件（RaceCondition），即兩個或多個進程同時訪問和操縱相同的數據時，最后的執行結果取決于進程運行的精確時序。2.5.2臨界資源和臨界區

1．臨界資源和臨界區一次僅允許一個進程使用。我們把這類共享資源稱為臨界資源（CriticalResource）。在每個進程中訪問臨界資源的那段程序叫做臨界區（CriticalSection），簡稱CS區。2.5.2臨界資源和臨界區

2．進程的一般結構圖2-15典型進程的一般結構2.5.2臨界資源和臨界區

3．臨界區進入準則①如果若干進程要求進入空閑的臨界區，一次僅允許一個進程進入。②任何時候，處于臨界區內的進程不可多于一個。③進入臨界區的進程要在有限時間內退出。④如果進程不能進入自己的臨界區，則應讓出CPU，避免進程出現“忙等”現象。2.5.2臨界資源和臨界區圖2-16互斥使用臨界區2.5.3互斥實現方式

1．利用硬件方法解決進程互斥問題（1）禁止中斷（2）專用機器指令2．原語是機器指令的延伸，往往是為完成某些特定的功能而編制的一段系統程序。原語操作也稱做“原子操作”（atomicaction），即一個操作中的所有動作要么全做，要么全不做。執行原語操作時，要屏蔽中斷，以保證其操作的不可分割性。2.5.3互斥實現方式

3．利用軟件方法解決進程互斥問題可為每類臨界區設置一把鎖，該鎖有打開和關閉兩種狀態。關鎖原語lock(W):while(W==1);W=1;

開鎖原語unlock(W):w=0;2.5.3互斥實現方式

進程A

……

lock(W);打印信息S;}CS區

unlock(W);……

進程B

……

lock(W);打印信息S;}CS區

unlock(W);……2.5.4信號量

1．整型信號量P操作最初源于荷蘭語proberen，表示測試；V操作源于荷蘭語verhogen，表示增加。在有些書上將P操作稱做wait或者DOWN操作，將V操作稱做signal或者UP操作。P和V操作都是原語2.5.4信號量

2．結構型信號量結構型信號量一般是由兩個成員組成的數據結構。其中一個成員是整型變量，表示該信號量的值；另一個是指向PCB的指針。

typedef

struct{

intvalue;

structPCB*list;}semaphore;2.5.4信號量

信號量的值與相應資源的使用情況有關圖2-17信號量的一般結構及PCB隊列對信號量的操作有如下嚴格限制：1.信號量可以賦初值，且初值為非負數。2.信號量的值可以修改，但只能由P和V操作來訪問

2.5.4信號量

P操作的定義如下：

voidP(semaphoreS){

S.value--;

if(S.value<0){

把這個進程加到S.list隊列；

block()；

}}2.5.4信號量

V操作的定義如下：

voidV(semaphoreS){

S.value++；

if(S.value<=0){

從S.list隊列中移走進程Q；

wakeup(Q)；

}}在具體實現時應注意，P,V操作都應作為一個整體實施，不允許分割或相互穿插執行2.5.4信號量

3．二值信號量2.5.5信號量的一般應用

1．用信號量實現進程互斥

Pa:Pb:……

P(mutex)P(mutex)

分配打印機釋放打印機（讀寫分配表）（讀寫分配表）

V(mutex)V(mutex)……2.5.5信號量的一般應用

利用信號量實現互斥的一般模型是：進程P1進程P2…進程Pn………P(mutex);P(mutex);P(mutex);臨界區臨界區臨界區

V(mutex);V(mutex);V(mutex);………2.5.5信號量的一般應用

使用P,V操作實現互斥時應注意兩點：①在每個程序中用于實現互斥的P(mutex)和V(mutex)必須成對出現，即先做P，進入臨界區；后做V，退出臨界區。②互斥信號量mutex的初值一般為1。2.5.5信號量的一般應用

2．用信號量實現進程簡單同步圖2-18簡單供者和用者對緩沖區的使用關系2.5.5信號量的一般應用

供者和用者間要交換兩個消息：緩沖區空和緩沖區滿的狀態。設置兩個信號量：

S1表示緩沖區是否空（0表示不空，1表示空）。

S2表示緩沖區是否滿（0表示不滿，1表示滿）。規定S1和S2的初值分別為1和02.5.5信號量的一般應用

供者進程用者進程

L1:P(S1)L2:…

啟動讀卡機P(S2);…從緩沖區取出信息收到輸入結束中斷V(S1);V(S2);加工并且存盤

gotoL1;gotoL2;2.5.5信號量的一般應用

用P和V操作實現同步時應注意如下三點：①分析進程間的制約關系，確定信號量種類。②信號量的初值與相應資源的數量有關，也與P,V操作在程序代碼中出現的位置有關。③同一信號量的P,V操作要“成對”出現，但是，它們分別出現在不同的進程代碼中。2.6經典進程同步問題1．生產者-消費者問題如果一個進程能產生并釋放資源，則該進程稱做生產者；如果一個進程單純使用（消耗）資源，則該進程稱做消費者。問題可以表述如下：一組生產者進程和一組消費者進程（設每組有多個進程）通過緩沖區發生聯系。生產者進程將生產的產品（數據、消息等統稱為產品）送入緩沖區，消費者進程從中取出產品。假定緩沖區共有N個，不妨把它們設想成一個環形緩沖池。1．生產者-消費者問題圖2-19生產者-消費者問題環形緩沖池它們應滿足如下同步條件：①任一時刻所有生產者存放產品的單元數不能超過緩沖區的總容量（N）。②所有消費者取出產品的總量不能超過所有生產者當前生產產品的總量。1．生產者-消費者問題1.設緩沖區的編號為0～N-1，in和out分別是生產者進程和消費者進程使用的指針，指向下面可用的緩沖區，初值都是0。2.設置三個信號量：full：表示放有產品的緩沖區數，其初值為0。empty：表示可供使用的緩沖區數，其初值為N。mutex：互斥信號量，初值為1，表示各進程互斥進入臨界區，保證任何時候只有一個進程使用緩沖區。1．生產者-消費者問題生產者進程Producer：消費者進程Consumer：

while(TRUE){ while(TRUE){

P(empty); P(full);

P(mutex); P(mutex);

產品送往buffer(in); 從buffer(out)中取出產品；

in=(in+1)modN;out=(out+1)modN;/*以N為模*//*以N為模*/

V(mutex); V(mutex);

V(full); V(empty);} }2.6經典進程同步問題

2．讀者-寫者問題讀者-寫者問題也是一個著名的進程互斥訪問有限資源的同步問題。例如，一個航班預訂系統有一個大型數據庫，很多競爭進程要對它進行讀、寫。允許多個進程同時讀該數據庫，但是在任何時候如果有一個進程寫（即修改）數據庫，那么就不允許其他進程訪問它——既不允許寫，也不允許讀。2．讀者-寫者問題

設置兩個信號量：讀互斥信號量rmutex和寫互斥信號量wmutex。另外設立一個讀計數器readcount，它是一個整型變量，初值為0。rmutex：用于讀者互斥地訪問readcount，初值為1。wmutex：用于保證一個寫者與其他讀者/寫者互斥地訪問共享資源，初值為1。2．讀者-寫者問題讀者Readers:

while(TRUE){

P(rmutex);

readcount=readcount+1;

if(readcount==1)

P(wmutex);

V(rmutex);

執行讀操作

P(rmutex);

readcount=readcount-1;

if(readcount==0)

V(wmutex);

V(rmutex);

使用讀取的數據

}寫者Writers：

while(TRUE){

P(wmutex);

執行寫操作

V(wmutex);}

這個算法隱含讀者的優先級高于寫者。2.6經典進程同步問題

3．哲學家進餐問題圖2-20哲學家進餐問題3．哲學家進餐問題===========================================#defineN5#defineLEFT(i-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2

typedef

struct{/*定義結構型信號量*/

intvalue;

structPCB*list;}semaphore;

int

state[N];semaphoremutex=1;/*互斥進入臨界區*/semaphores[N]; /*每位哲學家一個信號量*/3．哲學家進餐問題voidphilosopher(inti){

while(TRUE){think(); /*哲學家在思考問題*/

take_chopstick(i);/*拿到兩根筷子或者等待*/eat(); /*進餐*/

put_chopstick(i);/*把筷子放回原處*/}}voidtake_chopstick(inti){

P(mutex);

state[i]=HUNGRY;

test(i);/*試圖拿兩根筷子*/

V(mutex);

P(s[i]);}3．哲學家進餐問題voidput_chopstick(inti){

P(mutex);

state[i]=THINKING;

test(LEFT); /*查看左鄰，現在能否進餐*/

test(RIGHT); /*查看右鄰，現在能否進餐*/

V(mutex);}voidtest(inti){

if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){

state[i]=EATING;V(s[i]);}}===============================================2.6經典進程同步問題圖2-21打瞌睡的理發師4．打瞌睡的理發師問題4．打瞌睡的理發師問題理發師和每位顧客都分別是一個進程。===============================#defineCHAIRS5typedef

struct{

intvalue;

structPCB*list;}semaphore;semaphorecustomers=0;semaphorebarbers=0;semaphoremutex=1;intwaiting=0;

voidbarber(void){

while(TRUE){

P(customers);/*如果沒有顧客，則理發師打瞌睡*/

P(mutex);/*互斥進入臨界區*/waiting--;

V(barbers);/*一個理發師準備理發*/

V(mutex);/*退出臨界區*/

cut_hair();/*理發（在臨界區之外）*/}}4．打瞌睡的理發師問題

4．打瞌睡的理發師問題

voidcustomer(void){

P(mutex); /*互斥進入臨界區*/

if(waiting﹤CHAIRS){waiting++;

V(customers); /*若有必要，喚醒理發師*/

V(mutex);/*退出臨界區*/

P(barbers); /*如果理發師正忙著，則顧客打瞌睡*/

get_haircut();}else

V(mutex); /*店里人滿了，不等了*/}2.7管程管程概念的定義是：一個管程定義一個數據結構和能為并發進程在其上執行的一組操作，這組操作能使進程同步和改變管程中的數據。一個管程由管程名稱、局部于管程的共享數據的說明、對數據進行操作的一組過程和對該共享數據賦初值的語句四部分組成。2.7管程圖2-22管程的結構2.7管程管程具有以下三個特性：①管程內部的局部數據變量只能被管程內定義的過程所訪問，不能被管程外面聲明的過程直接訪問。②進程要想進入管程，必須調用管程內的某個過程。③一次只能有一個進程在管程內執行，而其