課件：進(jìn)程與并發(fā)程序設(shè)計

1、第3章 進(jìn)程機制與并發(fā)程序設(shè)計引言進(jìn)程的引入和定義進(jìn)程的狀態(tài)和進(jìn)程控制塊進(jìn)程控制線程的基本概念進(jìn)程調(diào)度進(jìn)程通信死鎖Linux中的進(jìn)程并發(fā)程序設(shè)計實例小結(jié)引言并發(fā)與并行概念同時進(jìn)行多個任務(wù)的需求舉例 解決需求采用的技術(shù)處理機分配問題進(jìn)程概念和基本狀態(tài)作業(yè)概念并發(fā)與并行首先聲明：此處的系統(tǒng)是計算機軟件系統(tǒng)或者是計算機控制環(huán)境中運行的軟件系統(tǒng)。定義1 設(shè)System代表系統(tǒng)，則系統(tǒng)表示為：System = (S,Int,R)其中， S ： 軟件集合； Int： 軟件系統(tǒng)與硬件環(huán)境的交互關(guān)系集合； R：軟件子系統(tǒng)之間的交互關(guān)系集合。定義2 如果考慮兩個程序,它們在同一時間度量下同時運行在不同的處理機上

2、，則稱這兩個程序是并行執(zhí)行的。定義3 設(shè)有兩個活動a1和a2，如果在某一指定的時間t，無論a1和a2是在同一處理機上還是在不同的處理機上執(zhí)行，只要a1和a2都處在各自的起點和終點之間的某一處，則稱a1和a2是并發(fā)執(zhí)行的。定義4 如果一個軟件系統(tǒng)的行為由許多活動構(gòu)成，假設(shè)其中至少有兩個活動是并發(fā)執(zhí)行的，則稱該軟件系統(tǒng)為并發(fā)系統(tǒng)。同時進(jìn)行多個任務(wù)的需求舉例編輯文檔運行程序網(wǎng)上瀏覽CD音樂欣賞解決需求采用的技術(shù)問題：單處理機如何同時執(zhí)行多個任務(wù)？PCB1PCB2PCB3程序1程序2程序3CPU分時：每個程序運行相等的時間片，輪流運行輪轉(zhuǎn)。手段：采用進(jìn)程概念，構(gòu)造進(jìn)程控制塊，記錄程序運行信息，建立進(jìn)程

3、運行機制。程序進(jìn)程控制塊PCB數(shù)據(jù)處理機分配 為進(jìn)程分配處理機，為進(jìn)程分配使用CPU的時間段（時間片）按照系統(tǒng)服務(wù)的目標(biāo)選擇優(yōu)先級最高的進(jìn)程運行 優(yōu)先級的計算依據(jù)程序的運行、等待、以及中斷現(xiàn)場的保護(hù)區(qū)問題。進(jìn)程概念和基本狀態(tài)程序進(jìn)程控制塊PCB數(shù)據(jù)進(jìn)程程序運行狀態(tài)運行狀態(tài)程序被中斷時鐘中斷其它中斷程序性中斷外部中斷基本狀態(tài)分析程序等待CPU的狀態(tài)就緒狀態(tài)程序等待I/O設(shè)備的狀態(tài)阻塞狀態(tài)作業(yè)概念作業(yè)：用戶提交的任務(wù)，包括作業(yè)步以及每一作業(yè)步要求的程序和數(shù)據(jù)。例如：用戶要運行程序：第一步：編輯文件vi第二步：編譯cc第三步：運行a.out第四步：得到結(jié)果這些就是作業(yè)步。作業(yè)與進(jìn)程的關(guān)系includ

4、e “stdio.h”main()printf(“C programn”)initshellvicca.outchild創(chuàng)建關(guān)系進(jìn)程的引入和定義順序程序的特點并發(fā)系統(tǒng)概述并發(fā)程序的特點進(jìn)程的引入進(jìn)程的定義順序程序及其特點程序執(zhí)行的順序性、環(huán)境的封閉性、結(jié)果的可再現(xiàn)性。圖3-1 順序處理操作的先后次序I1P1O1I2P2O2作業(yè)1作業(yè)2并發(fā)系統(tǒng)硬件環(huán)境概略展示的所有網(wǎng)絡(luò)中，節(jié)點計算機可以是任何類型。單處理機新體系結(jié)構(gòu)：數(shù)據(jù)流與函數(shù)語言機器單CPU，具有專用前端與后端處理機共享存儲器多處理機（對稱或?qū)Ｓ锰幚頇C）LAN本地互連網(wǎng)向量與陣列處理機多計算機多處理機LAN/WAN系統(tǒng)并發(fā)（子）系統(tǒng)與并發(fā)活

5、動業(yè)務(wù)過程處理系統(tǒng)并發(fā)應(yīng)用操作系統(tǒng)存儲管理（子）系統(tǒng)通信處理（子）系統(tǒng)硬件事件操作系統(tǒng)存儲管理（子）系統(tǒng)通信處理（子）系統(tǒng)業(yè)務(wù)處理系統(tǒng)其他應(yīng)用并發(fā)算法客戶需求并發(fā)（子）系統(tǒng) 并發(fā)活動文件管理（子）系統(tǒng)文件管理（子）系統(tǒng)并發(fā)程序及其特點并發(fā)意指“同時”。更準(zhǔn)確地說，在某一時間里如果兩個活動都處在各自的起點與終點之間，則認(rèn)為這兩個活動是并發(fā)的。 我們把在邏輯上的并行稱之為并發(fā)。 例子：變量X為共享變量，程序1和程序2都要對X進(jìn)行訪問，當(dāng)兩個程序執(zhí)行的速度變化時可得到不同的結(jié)果。程序2 X=X+1 R2=XR2=R2+1X=R2程序1 X=X+1 R1=XR1=R1+1X=R1 目標(biāo)程序段 x=x+

6、1程序2 R2=XR2=R2+1X=R2 程序1 R1=XR1=R1+1X=R1 執(zhí)行順序1：程序1程序2 結(jié)果為：X增加2。執(zhí)行順序2： R1=X; R2=X; R1=R1+1; R2=R2+1; X=R1; X=R2 結(jié)果為： X 增加1。 還可有許多其它組合解決問題的手段 總 線中央處理機單元 內(nèi)存儲器磁盤適配器輸入/輸出接口其他外設(shè)接口通信線路接口磁盤驅(qū)動器輸入/輸出設(shè)備各種外設(shè)通信線路引入進(jìn)程的目的，是為了使多個程序并發(fā)執(zhí)行，以改善資源利用率及提高系統(tǒng)的吞吐量，用進(jìn)程代表運行的程序。建立進(jìn)程的同步機制，對并發(fā)程序之間的相互牽連加以控制。P(mutex)V(mutex)P(mutex)

7、V(mutex)信號量初值mutex=1互斥進(jìn)程的定義進(jìn)程的參考定義有如下幾種：1、進(jìn)程是程序的一次執(zhí)行；2、進(jìn)程=PCB+程序+數(shù)據(jù)；3、進(jìn)程是一個可擁有資源的獨立實體，同時又是一個可以獨立調(diào)度的基本單位。PCB程序段私有數(shù)據(jù)塊進(jìn)程的定義進(jìn)程的狀態(tài)和進(jìn)程控制塊PCB程序段私有數(shù)據(jù)塊進(jìn)程的定義運行就緒阻塞進(jìn)程調(diào)度I/O完成時間片用完等待I/O完成進(jìn)程的狀態(tài)進(jìn)程名當(dāng)前狀態(tài)優(yōu)先數(shù)現(xiàn)場保留區(qū)指示處于同一狀態(tài)進(jìn)程的鏈指針資源清單進(jìn)程起始地址家族關(guān)系其他進(jìn)程控制塊進(jìn)程控制原語 進(jìn)程控制原語 創(chuàng)建原語 撤銷原語 阻塞原語 喚醒原語 控制原語與進(jìn)程狀態(tài)的轉(zhuǎn)換祖先進(jìn)程用戶進(jìn)程系統(tǒng)進(jìn)程用戶進(jìn)程用戶進(jìn)程進(jìn)程家族樹

8、置狀態(tài)為“阻塞”插入等待隊列停止程序運行釋放PCB釋放內(nèi)存釋放所有資源申請空白PCB填PCB置狀態(tài)為“就緒”插入就緒隊列置狀態(tài)為“就緒”插入就緒隊列不可中斷的系統(tǒng)程序。進(jìn)程控制原語以及進(jìn)程的狀態(tài)轉(zhuǎn)換運行就緒阻塞進(jìn)程調(diào)度I/O完成時間片用完等待I/O完成創(chuàng)建進(jìn)程撤銷進(jìn)程喚醒進(jìn)程阻塞進(jìn)程結(jié)束開始線程的基本概念引入線程的目的：則是為了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使操作系統(tǒng)具有更好的并發(fā)性。線程的定義：是進(jìn)程中的一個實體，是被系統(tǒng)獨立調(diào)度的基本單位。進(jìn)程線程1線程2線程3進(jìn)程1 分配處理機資源分配進(jìn)程調(diào)度進(jìn)程調(diào)度的職能 進(jìn)程調(diào)度亦可稱為處理機調(diào)度，它協(xié)調(diào)和控制各進(jìn)程對CPU的使用。 進(jìn)程調(diào)度算

9、法先來先服務(wù)FCFS 輪轉(zhuǎn)調(diào)度 分級輪轉(zhuǎn)法 優(yōu)先數(shù)法 進(jìn)程調(diào)度時的狀態(tài)圖FCFSP1P2 鏈頭Pn就緒隊列按進(jìn)程創(chuàng)建的時間先后排序程序2程序1程序nPCB集合就緒狀態(tài)創(chuàng)建時間就緒狀態(tài)創(chuàng)建時間就緒狀態(tài)創(chuàng)建時間中斷現(xiàn)場保護(hù)區(qū)中斷現(xiàn)場保護(hù)區(qū)中斷現(xiàn)場保護(hù)區(qū)輪轉(zhuǎn)調(diào)度最初的隊列形成可按照FCFS或者按照優(yōu)先級排隊為每個進(jìn)程分配一個時間片，輪流運行P1P2 鏈頭Pn程序2程序1程序n剛從CPU上退下來的進(jìn)程就緒狀態(tài)調(diào)度信息就緒狀態(tài)調(diào)度信息就緒狀態(tài)調(diào)度信息中斷現(xiàn)場保護(hù)區(qū)中斷現(xiàn)場保護(hù)區(qū)中斷現(xiàn)場保護(hù)區(qū)分級輪轉(zhuǎn)法輪轉(zhuǎn)鏈頭指針FCFS最高優(yōu)先級最低優(yōu)先級次高優(yōu)先級剛從CPU上退下來的進(jìn)程優(yōu)先數(shù)法P1P2 鏈頭Pn就緒

10、隊列按進(jìn)程的優(yōu)先級排序程序2程序1程序n中斷現(xiàn)場保護(hù)區(qū)就緒狀態(tài)優(yōu)先級就緒狀態(tài)優(yōu)先級就緒狀態(tài)優(yōu)先級中斷現(xiàn)場保護(hù)區(qū)中斷現(xiàn)場保護(hù)區(qū)進(jìn)程調(diào)度時的狀態(tài)圖3-6 調(diào)度時的進(jìn)程狀態(tài)變遷圖低優(yōu)先數(shù)就緒高優(yōu)先數(shù)就緒運行因等待I/O而阻塞請求I/O首先選擇超過時間片I/O完成其次選擇掛起進(jìn)程模型進(jìn)程通信臨界資源和臨界區(qū)同步與互斥兩個經(jīng)典的同步/互斥問題其他同步例子管程消息緩沖臨界資源和臨界區(qū)臨界資源critical resource臨界區(qū) critical section程序1Y=Y+1output程序2Y=Y+2output內(nèi)存共享區(qū)Ypcb1pcb2同步與互斥基本概念同步工具硬件指令信號量與P、V操作并發(fā)程序

11、共享資源問題的解決基本概念同步進(jìn)程之間的一種通信方式，有時序上的制約關(guān)系，或者說是進(jìn)程之間為了協(xié)同工作而存在的一種等待關(guān)系?；コ膺M(jìn)程之間對臨界資源的一種競爭關(guān)系，排他性地對資源的訪問方式。同步工具同步機制：用于控制進(jìn)程之間的同步與互斥。硬件指令：test-and-set（lock）功能表示如下：test-and-set(lock)begina:=lock;If lock=0 then lock :=1;reutrn(a)end其中：lock是內(nèi)存單元。舉例應(yīng)用舉例程序1初始化lock=0程序的其它部分代碼開鎖lock=0test-and-set（lock）訪問臨界資源代碼程序的其它部分lock

12、=1lock=0程序2初始化lock=0程序的其它部分代碼開鎖lock=0test-and-set（lock）訪問臨界資源代碼程序的其它部分lock=1lock=0信號量信號量：僅能由P、V操作修改的整型變量。整型值 S隊列指針 NextP操作P操作：申請資源操作(1)S:=S-1；(2)如果S0，則表示有資源，該進(jìn)程繼續(xù)執(zhí)行；如果S0，則該進(jìn)程繼續(xù)執(zhí)行；如果S0，則釋放S信號量隊列的排頭等待者并清除其阻塞狀態(tài)，即從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)，執(zhí)行V(S)者繼續(xù)執(zhí)行。 兩個經(jīng)典的同步/互斥問題生產(chǎn)者與消費者讀者與寫者生產(chǎn)者與消費者問題模型的抽象化與進(jìn)程分析(p99)生產(chǎn)者進(jìn)程臨界資源消費者進(jìn)程信號

13、量的設(shè)置Mutex=1 臨界資源Empty=n空緩沖區(qū)的個數(shù)Full=0滿緩沖區(qū)的個數(shù)生產(chǎn)者/消費者算法描述1var mutex，empty，full：psemaphore； i,j，goods：integer；buffer：array 0n-1 of item；procedure producer； 生產(chǎn)者進(jìn)程 begin while true do begin produce next product； P(empty)； P(mutex)； buffer(i):=product； i:=(i+1) mod(n)； V(mutex)； V(full)； endend；滿空ij圖3-8 環(huán)形

14、緩沖區(qū)procedure consumer； 消費者進(jìn)程 begin while true do begin P(full)； P(mutex)； goods：= buffer(j)； j:=(j+1) mod(n)； V(mutex)； V(empty)； consume product； end end；生產(chǎn)者/消費者算法描述2begin seminitial (mutex.v，1；empty.v，n；full.v，0)； i：=j：=0； cobegin producer； consumer； coendend讀者與寫者問題模型的抽象化與進(jìn)程分析(p100)文件寫者進(jìn)程讀者進(jìn)程讀者進(jìn)程.

15、信號量的設(shè)置R-mutex=1 臨界資源1Rw-mutex=1 臨界資源2臨界資源：讀者計數(shù)器r-counter文件寫者進(jìn)程實例讀者與寫者算法描述var mutex，wrt：psemaphore；readcount：integer；begin seminit(mutex.v，1；wrt.v，1)； readcount：= 0； cobegin procedure reader； begin P(mutex)； readcount:=readcount+1； if readcount =1 then P(wrt)； V(mutex)； reading is performing； P(mutex

16、)； readcount:=readcount-1； if readcount =0 then V(wrt)； V(mutex)； end procedure writer； begin P(wrt)； writing is performing； V(wrt)； end coendend；哲學(xué)家就餐第 i 個哲學(xué)家活動描述信號量初值：FORKSi=1，其中i=0、1、2、3、4BEGIN思考饑餓P(FORKSi mod(5)P(FORKS(i+1)mod(5)）吃面條V(FORKSi mod(5)V(FORKS(i+1)mod(5)）END沒有考慮死鎖問題五個哲學(xué)家就餐信號量：c0c4,初值

17、均為1；整型變量I=0,1,2,3,4；Philosopher(I)Begin if I mod 2 = 0 thenbeginP(cI);P(cI+1mod 5);吃V(cI);V(cI+1mod 5);endelsebeginP(cI+1mod 5); P(cI);吃V(cI+1mod 5); V(cI);endEnd實例沒有考慮饑餓問題睡覺的理發(fā)師算法描述信號量：customers=0;barbers=0;mutex=1整型變量：waiting=0;理發(fā)師：Begin While(true)then Begin P(customers); P(mutex); Waiting=waitin

18、g-1; V(barbers); V(mutex); Cut hair(); End End 顧客：Begin P(mutex); If （waitingCHIRS) then Begin Waiting=waiting+1; V(customers); V(mutex); P(barbers); Get_haircut(); End Else Begin V(mutex); EndEnd管程把分散的各同類臨界區(qū)集中起來。并為每個可共享資源設(shè)立一個專門的機構(gòu)來統(tǒng)一管理各進(jìn)程對該資源的訪問，這個專門機構(gòu)稱為管程。Hansen在并發(fā)PASCAL語言中首先引入了管程，將它作為語言中的一個并發(fā)數(shù)據(jù)結(jié)構(gòu)

19、類型。主控程序M. Entry1M. Entry1Monitor MEntry1Entry2P(mutext)V(mutext)管程的組成管程主要由兩部分組成(p102)l 局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀態(tài)；l 局部于該管程的若干過程，每個過程完成關(guān)于上述數(shù)據(jù)的某種規(guī)定操作。條件變量每個獨立的條件變量是和進(jìn)程需要等待的某種原因(或說條件)相聯(lián)系的，當(dāng)定義一個條件變量時，系統(tǒng)就建立一個相應(yīng)的等待隊列。關(guān)于條件變量有兩種操作：wait(x)和signal(x)，其中x為條件變量。wait把調(diào)用者進(jìn)程掛在與x相應(yīng)的等待隊列上，signal喚醒相應(yīng)等待隊列上的一個進(jìn)程。管程描述pr

20、oducer: begin repeatproduce an item ;ringbuffer.put(item); until false;end consumer: begin repeatringbuffer.get(item);consume the item; until falseendmonitor ringbuffer；var rbuffer：array 0. n-1 of item； k ，nextempty，nextfull：integer； empty，full：condition；procedure entry put (var product：item)； begin

21、 if k=n then wait(empty)； rbuffernextempty:=product； k:=k+1； nextempty:=（nextempty+1) mod（n）； signal(full)； end；procedure entry get(var goods：item)； begin if k =0 then wait(full)； goods：=rbuffernextfull； k:=k-1； nextfull:=(nextfull+1) mod（n）； signal(empty)； end；begin k := 0； nextempty：=0；nextfull：=0

22、；end；消息緩沖:mq消息隊列mutex互斥指針sm同步指針PCB(B)Sender:ASize:5Text:HelloNptr:receive(b):發(fā)送者：A 長度：5 正文：Hellob 0:send(B,a):發(fā)送者：A 長度：5 正文：Helloa發(fā)送接收圖3-9 發(fā)送與接收消息過程。進(jìn)程A進(jìn)程B消息系統(tǒng)Receive 和 sendProcedure send(receiver,a)Begingetbuf(a,size,i);i.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0;getid(PCB,receiver,j

23、);P(j.mutext);insert(j.mq,i);V(j.mutext);V(j.sm);EndProcedure receive(b)BeginP(j.sm);P(j.mutext);remove(j.mq,i);V(j.mutext);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;putbuf(i);End死鎖死鎖原因和必要條件死鎖例子 產(chǎn)生死鎖的原因和必要條件 預(yù)防死鎖 資源獨占(靜態(tài)分配）資源順序分配 資源受控動態(tài)分配 （避免死鎖）發(fā)現(xiàn)死鎖 （死鎖檢測）解除死鎖 死鎖舉例死鎖例子 進(jìn)程P1 進(jìn)程P2 ： ： 申請文件F申請磁帶

24、機Tr1 ：申請磁帶機T r2: 申請文件F 釋放磁帶機T 釋放文件F釋放文件F釋放磁帶機T產(chǎn)生死鎖的原因和必要條件原因：系統(tǒng)資源不足；進(jìn)程推進(jìn)順序不合適；必要條件互斥條件不剝奪條件請求和保持條件環(huán)路等待條件進(jìn)程資源圖 P1 P2F申請不同類型的資源T簡單的死鎖例子FTP2P1請求已分配請求配分已銀行家算法10 (0)P 8Q 8R 7P 4Q 7R 64 (6)P 0Q 7R 60 (10)PQ 7R 68 (2)PQ 0R 50 (10)PQR 58 (2)PQR 03 (7)PQR10 (0)有顧客P、Q、和R，總共需要貸款23個貨幣單位，銀行家有10個貨幣單位。死鎖檢測檢測算法如下:

25、（進(jìn)程資源圖的化簡）(1) 把未阻塞(Ci=0)的進(jìn)程Pi記錄在L表中(其全部資源請求已得到滿足的進(jìn)程)；(2) 從L表中選擇一進(jìn)程，根據(jù)資源分配表S釋放分配給該進(jìn)程的所有資源；(3) 由進(jìn)程等待表W依次檢查和修改需要該進(jìn)程釋放資源的每一個進(jìn)程的等待計數(shù)器Cj；(4) 若Cj=0，則表示該進(jìn)程所請求的資源已得到滿足，不再阻塞，將Pj記入L表中；(5)再從L表中選取另一進(jìn)程，重復(fù)上述操作；(6) 若所有的進(jìn)程都記入L表中，則系統(tǒng)初始狀態(tài)為非死鎖狀態(tài)，否則為死鎖狀態(tài)。表示進(jìn)程資源圖的數(shù)據(jù)結(jié)構(gòu)表示請求邊：請求矩陣表示分配遍：分配矩陣行下標(biāo)表示進(jìn)程Pi列下標(biāo)表示資源Rj通過化簡進(jìn)程資源圖斷定是否存在死

26、鎖。p1r1p2r2r3請求矩陣Request 資源進(jìn)程R 1R2RjRmP1 b11b21b1jbm1P2b12b22b2jbm2Pib1jb2jbijbmjPm bm1bm2 bmjbmn 資源 R1R2RjRnP1a11a12a1ja1nP2a21a22a2ja2nPiai1ai2aijainPman1an2 amjamn進(jìn)程分配矩陣Allocation死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)1、可用資源向量Available：表示m類資源中，每一類的可用數(shù)目。2、請求矩陣Request：是n m 矩陣，表示進(jìn)程當(dāng)前對各類資源的請求數(shù)目。3、分配矩陣Allocation：是 n m矩陣，用以表示進(jìn)程某一時刻

27、的資源分配情況。4、工作向量Work：表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行的各類資源數(shù)目。5、進(jìn)程向量L：記錄當(dāng)前已不占有資源的諸進(jìn)程。算法描述算法描述Work:=Available;L:= Li | Allocationi=0 Requesti=0 ;For all LiL dobeginfor all Requesti WorkbeginWork = Work +Allocationi Li Lendenddeadlock:=(L=P1,P2,Pn 解除死鎖撤銷死鎖中的進(jìn)程，釋放出資源。撤銷進(jìn)程的代價進(jìn)程優(yōu)先級進(jìn)程運行代價（已運行的%）進(jìn)程類型等等交通死鎖死鎖圖示無死鎖例子有死鎖Linux中的進(jìn)程

28、Linux啟動過程Linux進(jìn)程控制塊PCB簡介 進(jìn)程的創(chuàng)建 相關(guān)系統(tǒng)調(diào)用信號量與P、V操作等待隊列進(jìn)程調(diào)度管道Linux內(nèi)核體系結(jié)構(gòu)Linux啟動過程引導(dǎo)扇區(qū)未分區(qū)分過區(qū)getty程序CPU執(zhí)行軌跡0#idleLinux進(jìn)程抽象Linux進(jìn)程控制塊PCB簡介task 數(shù)組:進(jìn)程控制塊指針的集合（512個）task_struct結(jié)構(gòu)進(jìn)程標(biāo)識進(jìn)程狀態(tài)調(diào)度信息進(jìn)程鏈時間片進(jìn)程通信信息內(nèi)存資源信息文件資源信息進(jìn)程上下文stoppedreadyrunningsuspendedzombie創(chuàng)建信號調(diào)度IO 結(jié)束IO 請求結(jié)束進(jìn)程狀態(tài)值說明TASK_RUNNING0就緒TASK_INTERRUPTIBLE

29、1淺度睡眠TASK_UNINTERRUPTIBLE2深度睡眠TASK_ZOMBIE4僵死TASK_STOPPED8暫停Linux進(jìn)程狀態(tài)表Linux進(jìn)程狀態(tài)轉(zhuǎn)換Linux進(jìn)程家譜Linux進(jìn)程的生命周期進(jìn)程的創(chuàng)建PCB1PCB2程序fork()采用Copy on write寫時再復(fù)制 0#1#gettyloginshellshellgetty父進(jìn)程fork()返回pid子進(jìn)程fork()返回0tss線程clone()返回0struct pt_regsstruct reg64 eax;struct reg64 esp;當(dāng)從fork()返回時，eax寄存器存放返回值。通用寄存器組的定義子進(jìn)程系統(tǒng)空

30、間堆棧示意圖系統(tǒng)調(diào)用返回時父子進(jìn)程系統(tǒng)堆棧對照進(jìn)程與線程本質(zhì)區(qū)別進(jìn)程地址空間獨立線程共享地址空間線程堆棧執(zhí)行上下文TSS進(jìn)程代碼數(shù)據(jù)堆棧文件IO虛存進(jìn)程線程進(jìn)程調(diào)度調(diào)度策略SCHED_OTHER普通進(jìn)程SCHED_FIFO執(zhí)行時間不長的實時進(jìn)程（更高優(yōu)先級可搶占CPU)SCHED_RR輪轉(zhuǎn)的實時進(jìn)程（相同優(yōu)先級進(jìn)程之間用時間片調(diào)度）weight權(quán)值priority靜態(tài)優(yōu)先級(時間片大小)缺省值為DEF_PRIORITY=20個時標(biāo)（每個時標(biāo)10ms）counter動態(tài)優(yōu)先級，當(dāng)前的時間配額（初值為DEF_PRIORITY)rt_priority相對優(yōu)先級（0-99）#define DEF_PR

31、IORITY(20*HZ / 100) / 其中：HZ=100幾個計算式子：普通進(jìn)程的權(quán)值：counter = counter / 2 + priority weight=counter+prinority 當(dāng)前進(jìn)程的權(quán)值：weight=counter+priority+1實時進(jìn)程的權(quán)值：weight = 1000+rt_priority Weight是linux系統(tǒng)在進(jìn)程調(diào)度過程中選擇進(jìn)程的唯一標(biāo)準(zhǔn) Linux內(nèi)核的任務(wù)控制流相關(guān)系統(tǒng)調(diào)用以下簡要列出了和進(jìn)程及進(jìn)程間通信相關(guān)的系統(tǒng)調(diào)用。在標(biāo)志列中，各字母的意義為：m：手冊頁可查；+：POSIX 兼容；-：Linux 特有；c：libc 包含該

32、系統(tǒng)調(diào)用；!：該系統(tǒng)調(diào)用和其他系統(tǒng)調(diào)用類似， 應(yīng)改用其他 POSIX 兼容系統(tǒng)調(diào)用。系統(tǒng)調(diào)用:廣義指令，操作系統(tǒng)提供給用戶使用的程序界面。系統(tǒng)調(diào)用表系統(tǒng)調(diào)用說明標(biāo)志alarm在指定時間之后發(fā)送SIGALRM 信號m+cclone創(chuàng)建子進(jìn)程m-execl, execlp, execle, .執(zhí)行映象m+!cexit終止進(jìn)程m+cfork創(chuàng)建子進(jìn)程m+cgeteuid獲取有效用戶標(biāo)識符m+cgetpid獲取當(dāng)前進(jìn)程的進(jìn)程標(biāo)識符m+cipc進(jìn)程間通信-ckill向進(jìn)程發(fā)送信號m+c續(xù)表一msgctl消息隊列控制m!cmsgget獲取消息隊列標(biāo)識符m!cmsgrcv接收消息m!cmsgsnd發(fā)送消息m

33、!cnice修改進(jìn)程優(yōu)先級mcpause進(jìn)程進(jìn)入休眠，等待信號m+cpipe創(chuàng)建管道m(xù)+c續(xù)表二semctl信號量控制m!csemget獲取某信號量數(shù)組的標(biāo)識符m!csemop在信號量數(shù)組成員上的操作m!csetitimer設(shè)置間隔定時器mcshmat附加共享內(nèi)存m!cshmctl共享內(nèi)存控制m!cshmdt移去共享內(nèi)存m!cshmget獲取/建立共享內(nèi)存m!csignal設(shè)置信號處理器mc續(xù)表三system執(zhí)行 shell 命令m!ctime獲取自 1970.1.1 以來的秒數(shù)m+ctimes獲取進(jìn)程的 CPU 時間m+cvfork見 forkm!cwait等待進(jìn)程終止m+cwait3, w

34、ait4等待指定進(jìn)程終止 （BSD）mcwaitpid等待指定進(jìn)程終止m+cvm86進(jìn)入虛擬 8086 模式m-cLinux信號量定義Linux 信號量數(shù)據(jù)結(jié)構(gòu)中包含的信息count（計數(shù)）該域用來跟蹤希望訪問該資源的進(jìn)程個數(shù)。正值表示資源是可用的，而負(fù)值或零表示有進(jìn)程正在等待該資源。該計數(shù)的初始值為 1，表明同一時刻有且只能有一個進(jìn)程可訪問該資源。進(jìn)程要訪問該資源時，對該計數(shù)減 1，結(jié)束對該資源的訪問時，對該計數(shù)加 1。sleepers（等待喚醒計數(shù)）等待該資源的進(jìn)程個數(shù)，也是當(dāng)該資源空閑時等待喚醒的進(jìn)程個數(shù)。Wait(等待隊列)某個進(jìn)程等待該資源時被添加到該等待隊列中。lock（鎖）用來實

35、現(xiàn)對 waking 域的互斥訪問的 Buzz 鎖（自旋鎖spin lock ）。Linux互斥操作進(jìn)程標(biāo)識調(diào)度信息時間片進(jìn)程通信信息進(jìn)程狀態(tài)進(jìn)程鏈內(nèi)存資源信息文件資源信息進(jìn)程上下文Linux進(jìn)程控制塊邏輯結(jié)構(gòu)task_struct結(jié)構(gòu)等待隊列Linux 中的等待隊列wait_queuewait_queuetask_structtask_structwait_queuetask_structtasktask.task.nextnextnexttask_structwait_queue_head_t Linux虛存管理數(shù)據(jù)結(jié)構(gòu)進(jìn)程控制塊與文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)關(guān)系管道 管道示意圖進(jìn)程 1file 結(jié)構(gòu)（

36、files_struct） 進(jìn)程 2file 結(jié)構(gòu)inode數(shù)據(jù)頁管道寫操作集管道讀操作集 f_mode f_pos f_flags f_count f_owner f_inode f_version f_op f_mode f_pos f_flags f_count f_owner f_inode f_version f_op 信號檢測與處理流程圖進(jìn)程控制并發(fā)程序設(shè)計實例fildes1Father1.c進(jìn)程1Child1.c進(jìn)程2fildes0進(jìn)程的建立fork()的使用main() int i; i=fork(); if(i) printf(“parent”); else printf(“

37、child”); main() int i; i=fork(); if(i) printf(“parent”); else printf(“child”); fork()PCB1PCB2pipe系統(tǒng)調(diào)用說明int pipe(fildes)int fildes2Pipe建立一個I/O機制稱為管道，并且返回兩個文件描述符：files0管道讀指針files1 管道寫指針管道（FIFO緩沖區(qū)）大小為6kfiles0專門讀取由files1 寫入管道的數(shù)據(jù)。當(dāng)pipe執(zhí)行失敗時，返回-1。dup系統(tǒng)調(diào)用說明int dup(files)int fildesfildes 是文件描述符，由creat,open,dup,fcntl,或者pipe系統(tǒng)調(diào)用提供。dup返回一個新的文件描述符，與原始描述符具有如下共同點：相同的打開文件（或管道文件）相同文件指針（即：兩個文件描述符共享一個文件指針）相同的訪問權(quán)限（讀、寫、或讀/寫）返回的文件描述符是空閑描述符中序號最小的那個。執(zhí)行成功則返回非負(fù)整數(shù)，即文件描述符。執(zhí)行失敗則返回-1。execl系統(tǒng)調(diào)用說明int execl(path,arg