第二講進程管理

第二講進程管理中國科學技術(shù)大學計算機系陳香蘭xlanchen@Fall2013內(nèi)容提要多道程序技術(shù)和程序并發(fā)執(zhí)行的條件進程的定義進程的狀態(tài)進程的描述進程的控制內(nèi)容提要多道程序技術(shù)和程序并發(fā)執(zhí)行的條件進程的定義進程的狀態(tài)進程的描述進程的控制多道程序技術(shù)從單道多道內(nèi)存必須被多個“程序”共享CPU必須被多個“程序”復用操作系統(tǒng)必須具備4大基本功能：處理器管理內(nèi)存管理I/O管理文件管理容易混淆的幾個基本術(shù)語Program，程序；Tasks，任務(wù)

Jobs，作業(yè)；Processes，進程本課程中關(guān)于上述幾個術(shù)語的界定程序：靜態(tài)的代碼序列，通常以文件為存儲介質(zhì)。代碼可以是高級語言的、匯編語言的、指令序列等等。任務(wù)：泛指。作業(yè)：批處理系統(tǒng)中，等待裝入內(nèi)存執(zhí)行的用戶程序和數(shù)據(jù)。進程：已經(jīng)被裝載到內(nèi)存中運行的程序及其外延多道程序技術(shù)的難點與單道相比，在多道系統(tǒng)中，進程之間的運行隨著調(diào)度的發(fā)生而具有無序性，那么如何保證正確的并發(fā)。相關(guān)理論：程序并發(fā)執(zhí)行的條件理論模型：前驅(qū)圖基于前驅(qū)圖的程序順序執(zhí)行分析基于前驅(qū)圖的程序并發(fā)執(zhí)行分析PrecedenceGraph前驅(qū)圖目的：準確的描述語句、程序段、進程之間的執(zhí)行次序前驅(qū)圖是一個有向無環(huán)圖DAG（DirectedAcyclicGraph）結(jié)點：一個執(zhí)行單元（如一條語句、一個程序段或進程）（有向）邊：前驅(qū)關(guān)系“”，

＝{(Pi,Pj)|Pi必須在Pj開始執(zhí)行前執(zhí)行完}若(Pi,Pj)∈，可寫成PiPj

其中，稱Pi是Pj的前驅(qū)，而Pj是Pi的后繼沒有前驅(qū)的結(jié)點稱為初始結(jié)點（initialnode）

沒有后繼的結(jié)點稱為終止結(jié)點（finalnode）結(jié)點上使用一個權(quán)值（weight）表示該結(jié)點所含的程序量或結(jié)點的執(zhí)行時間前驅(qū)圖舉例：123865749程序的順序執(zhí)行一個較大的程序通常包含若干個程序段。程序必須按照某種先后順序逐個執(zhí)行。例如其中，I代表用戶程序和數(shù)據(jù)的輸入；C代表計算；P代表輸出結(jié)果在一個程序段中，多條語句也存在順序執(zhí)行的問題S1：a＝x＋3S2：b＝y(tǒng)＋4S3：c＝a＋bS4：d＝a＋cI1C1P1I2C2P2S1S2S3S4S1S2S3S4按照語句依賴關(guān)系若按指令地址順序執(zhí)行程序順序執(zhí)行時的特征順序性封閉性可再現(xiàn)性程序的并發(fā)執(zhí)行I1C1P1I2C2P2×I1C1P1I2C2P2I3C3P3I4C4P4程序并發(fā)執(zhí)行時的特征間斷性并發(fā)程序“執(zhí)行－－暫停執(zhí)行－－執(zhí)行”失去封閉性由于資源共享，程序之間可能出現(xiàn)相互影響的現(xiàn)象不可再現(xiàn)性原因同上。舉例：變量N的共享，設(shè)某時刻N＝n，則若執(zhí)行順序為：N:＝N＋1；print(N);N:=0;N的值依次為n＋1；n＋1；0print(N);N:=0;N:＝N＋1；N的值依次為n；0；1print(N);N:＝N＋1；N:=0; N的值依次為n；n＋1；0程序A

repeatN:=N+1;程序B

repeatprint(N);N:=0;程序并發(fā)執(zhí)行的條件(Bernstein條件)在上述3個特性中，必須防止“不可再現(xiàn)性”。為使并發(fā)程序的執(zhí)行保持“可再現(xiàn)性”，引入并發(fā)執(zhí)行的條件。思路：分析程序或語句的輸入信息和輸出信息，考察它們之間的相關(guān)性符號和術(shù)語定義：讀集R(pi)，表示程序pi在執(zhí)行時需要參考的所有變量的集合寫集W(pi)，表示程序pi在執(zhí)行期間要改變的所有變量的集合1966，Bernstein：若兩個程序p1和p2滿足下列條件，則它們就能并發(fā)執(zhí)行，且具有可再現(xiàn)性R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)＝{}內(nèi)容提要多道程序技術(shù)和程序并發(fā)執(zhí)行的條件進程的定義進程的狀態(tài)進程的描述進程的控制進程進程需要使用某種方法加以描述，原因進程運行的間斷性，要求在進程暫停運行時記錄該程序的現(xiàn)場，以便下次能正確的繼續(xù)運行資源的共享，要求能夠記錄進程對資源的共享情況為保證程序“正確”的并發(fā)執(zhí)行，必須將進程看成某種對象，對其進行描述并加以控制引入進程控制塊PCB進程的實體：程序段＋數(shù)據(jù)段＋PCB進程的定義湯子瀛，計算機操作系統(tǒng)，二版

是“可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運行過程”

是進程實體的運行過程Silberschatz，OperatingSystemConcepts，7th

“Aprocessisaprograminexecution”進程的2大基本屬性進程是可以獨立運行的基本單位。有2大基本屬性進程是一個可以擁有資源的獨立單位進程是一個可以獨立調(diào)度和分派的基本單位進程的5大特征vs.程序動態(tài)性：最基本的特性具有一定的生命期由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行；因得不到資源而阻塞；由撤消而消亡。程序只是一組有序指令的集合，存放在某種介質(zhì)上，是靜態(tài)的并發(fā)性：最重要的特征多道并發(fā)，不僅是進程也是OS的重要特征程序本身不能并發(fā)執(zhí)行，必須“變成”進程后才能并發(fā)獨立性是獨立運行、調(diào)度、資源分配的基本單位；異步性進程按各自獨立的、不可預(yù)知的速度向前推進進程之間是異步的對于“不可再現(xiàn)性”，需要采取某些措施來保證進程之間的協(xié)調(diào)運行結(jié)構(gòu)特性具有結(jié)構(gòu)性，由程序段、數(shù)據(jù)段及進程控制塊三部分構(gòu)成，稱“進程映像”內(nèi)容提要多道程序技術(shù)和程序并發(fā)執(zhí)行的條件進程的定義進程的狀態(tài)進程的描述進程的控制進程的狀態(tài)根據(jù)進程的動態(tài)特性，進程在整個生命期中將會出于不同的狀態(tài)。狀態(tài)模型最基本的“三狀態(tài)”模型引入“新”和“終止”態(tài)的“五狀態(tài)”模型引入“掛起”狀態(tài)的“七狀態(tài)”模型“三狀態(tài)”模型三種最基本的狀態(tài)就緒狀態(tài)“萬事具備，只欠CPU”就緒隊列執(zhí)行狀態(tài)阻塞（等待、睡眠）狀態(tài)等待原因：

1）發(fā)出I/O指令之后，等待I/O操作的完成

2）等待某個事件發(fā)生

3）等待分配到資源

等等阻塞（等待）隊列，通常按照原因，有多個“五狀態(tài)”模型在三種基本狀態(tài)中，引入新狀態(tài)：進程剛創(chuàng)建，但還沒有進入就緒隊列需要進程初始化，分配一些預(yù)設(shè)資源等等終止狀態(tài)：進程已經(jīng)（正常/異常）結(jié)束，已經(jīng)從就緒隊列中移出，但尚未撤銷需要將進程暫時留在系統(tǒng)中，以便其他進程去收集該進程的相關(guān)信息狀態(tài)轉(zhuǎn)換圖Readyqueuewaitqueues六種轉(zhuǎn)換關(guān)系“七狀態(tài)”模型進程因自身內(nèi)部的一些原因，無法繼續(xù)運行時，暫時進入“等待”狀態(tài)，當?shù)却脑蛳?，就可以返回就緒狀態(tài)；但有時候會因為進程外部的一些原因，使得進程暫時不能繼續(xù)運行。外部原因主要有終端用戶的需要父進程的需求操作系統(tǒng)的需要對換的需要負載調(diào)節(jié)的需要引入“掛起”狀態(tài)“掛起”狀態(tài)不是一種狀態(tài)，而是一類狀態(tài)掛起后處于靜止狀態(tài)：靜止就緒，靜止阻塞非掛起的活動狀態(tài)：活動就緒，活動阻塞，還包括執(zhí)行態(tài)在狀態(tài)轉(zhuǎn)換中，增加了從活動狀態(tài)與靜止狀態(tài)之間，以及靜止狀態(tài)內(nèi)部之間的狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換圖執(zhí)行活動就緒靜止就緒活動阻塞靜止阻塞激活掛起激活掛起釋放釋放掛起請求I/O新增6種狀態(tài)轉(zhuǎn)換調(diào)度中斷另外一個視圖對換引入的中期調(diào)度作業(yè)調(diào)度：長期調(diào)度對換：引起中期調(diào)度多道數(shù)過高，引起內(nèi)存不足進程調(diào)度：短期調(diào)度Mid-termschedulerSelectwhichprocesstoswapin&outSwapping

Removeprocessesfrommemory,&

reintroduceprocessesintomemoryReducethedegreeofmultiprogramming,WHY?內(nèi)容提要多道程序技術(shù)和程序并發(fā)執(zhí)行的條件進程的定義進程的狀態(tài)進程的描述進程的控制進程控制塊PCB進程控制塊是操作系統(tǒng)中的一種關(guān)鍵數(shù)據(jù)結(jié)構(gòu)由操作系統(tǒng)進程管理模塊維護常駐內(nèi)存操作系統(tǒng)根據(jù)PCB來控制和管理并發(fā)執(zhí)行的進程PCB是進程存在的唯一標志進程控制塊中的4大類信息進程標識符信息：外部標識vs內(nèi)部標識處理機的狀態(tài)信息，即硬件上下文

CPUregisters:Architecture-specificPC:Addressofthenextinstruction通用寄存器程序狀態(tài)字用戶堆棧指針PointerProcessstateProcessnumberProgramcounterRegistersMemorylimitsListofopenfiles...調(diào)度信息Processstate，Priority,queuepointers,…進程控制信息Memory-managementinformationBase&limit,page/segmenttables,…AccountinginformationTimeused/limits,accountnumbers,processNO,…I/OstatusinformationAllocateddevices,openfiles,…同步和通信信息進程控制塊的組織方式在內(nèi)存中的位置：操作系統(tǒng)數(shù)據(jù)區(qū)，位于內(nèi)核中常用的2種組織方式：鏈接方式索引方式根據(jù)組織在一起的進程控制塊的狀態(tài)以及對應(yīng)進程的狀態(tài)的不同就緒隊列阻塞隊列空閑隊列等執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB918……PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……執(zhí)行指針就緒隊列指針阻塞隊列指針鏈接方式索引方式進程在不同隊列中的遷移DispatchSelectaprocesstoexecuteWhilerunning,events:IssueanI/OrequestCreateanewsub-process&waitforitsterminationInterruptoccurredProcessmigratesbetweenqueues調(diào)度引起的上下文切換Savingthestateoftheoldprocess,&

loadingthesavedstateforthenewoneContext(上下文)ofaprocessisrepresentedinitsPCBContext-switchtimeOverhead(系統(tǒng)開銷)NousefulTimeorspeedarchitecture-specific(1~1000ms),&Dependsonothercomponents(E.X.:memorymanagement)Occursonlyinkernelmode進程切換引起的時空感覺上的混亂用戶在宏觀上：并發(fā)；間斷CPU在微觀上：串行；連續(xù)；空間變化程序在功能上：完整，連續(xù)；空間不變操作系統(tǒng)在進程管理上：時空交錯內(nèi)容提要多道程序技術(shù)和程序并發(fā)執(zhí)行的條件進程的定義進程的描述進程的狀態(tài)進程的控制進程控制進程控制是操作系統(tǒng)進程管理功能的一部分，由操作系統(tǒng)內(nèi)核實現(xiàn)操作系統(tǒng)內(nèi)核運行在內(nèi)核態(tài)，用戶程序運行在用戶態(tài)內(nèi)核態(tài)，系統(tǒng)態(tài)具有較高的特權(quán)，能執(zhí)行一切指令，能訪問所有寄存器和存儲區(qū)用戶態(tài)，具有較低特權(quán)，只能執(zhí)行規(guī)定的指令，訪問指定的寄存器和存儲區(qū)用戶程序不能執(zhí)行OS特權(quán)指令，不能直接訪問OS區(qū)域進程控制原語進程的創(chuàng)建和進程的終止進程的阻塞和喚醒進程的掛起與激活進程關(guān)系圖：用于描述進程家族關(guān)系的有向樹結(jié)點：進程若進程1創(chuàng)建了進程2，則1是2的父進程，2是1的子進程使用從1到2的有向邊表示進程的“父子關(guān)系”父進程的父進程：祖父進程樹的根結(jié)點為進程家族的祖先進程樹示意圖P1P2P3P4P5P6P7P8P9P10P11P12UNIX中的經(jīng)典進程樹父子之間的關(guān)系資源共享關(guān)系ParentandchildrenshareallresourcesChildrensharesubsetofparent’sresourcesParentandchildsharenoresources并發(fā)執(zhí)行關(guān)系ParentandchildrenexecuteconcurrentlyParentwaitsuntilchildrenterminate地址空間關(guān)系Childduplicateofparent.Childhasaprogramloadedintoit.UNIXexamplesForksystemcallcreatesnewprocessExecvesystemcallusedafteraforktoreplaceth