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

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

Jobs，作業(yè)；Processes，進(jìn)程本課程中關(guān)于上述幾個術(shù)語的界定程序：靜態(tài)的代碼序列，通常以文件為存儲介質(zhì)。代碼可以是高級語言的、匯編語言的、指令序列等等。任務(wù)：泛指。作業(yè)：批處理系統(tǒng)中，等待裝入內(nèi)存執(zhí)行的用戶程序和數(shù)據(jù)。進(jìn)程：已經(jīng)被裝載到內(nèi)存中運(yùn)行的程序及其外延多道程序技術(shù)的難點與單道相比，在多道系統(tǒng)中，進(jìn)程之間的運(yùn)行隨著調(diào)度的發(fā)生而具有無序性，那么如何保證正確的并發(fā)。相關(guān)理論：程序并發(fā)執(zhí)行的條件理論模型：前驅(qū)圖基于前驅(qū)圖的程序順序執(zhí)行分析基于前驅(qū)圖的程序并發(fā)執(zhí)行分析PrecedenceGraph前驅(qū)圖目的：準(zhǔn)確的描述語句、程序段、進(jìn)程之間的執(zhí)行次序前驅(qū)圖是一個有向無環(huán)圖DAG（DirectedAcyclicGraph）結(jié)點：一個執(zhí)行單元（如一條語句、一個程序段或進(jìn)程）（有向）邊：前驅(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(yù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í)行的條件進(jìn)程的定義進(jìn)程的狀態(tài)進(jìn)程的描述進(jìn)程的控制進(jìn)程進(jìn)程需要使用某種方法加以描述，原因進(jìn)程運(yùn)行的間斷性，要求在進(jìn)程暫停運(yùn)行時記錄該程序的現(xiàn)場，以便下次能正確的繼續(xù)運(yùn)行資源的共享，要求能夠記錄進(jìn)程對資源的共享情況為保證程序“正確”的并發(fā)執(zhí)行，必須將進(jìn)程看成某種對象，對其進(jìn)行描述并加以控制引入進(jìn)程控制塊PCB進(jìn)程的實體：程序段＋數(shù)據(jù)段＋PCB進(jìn)程的定義湯子瀛，計算機(jī)操作系統(tǒng)，二版

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

是進(jìn)程實體的運(yùn)行過程Silberschatz，OperatingSystemConcepts，7th

“Aprocessisaprograminexecution”進(jìn)程的2大基本屬性進(jìn)程是可以獨立運(yùn)行的基本單位。有2大基本屬性進(jìn)程是一個可以擁有資源的獨立單位進(jìn)程是一個可以獨立調(diào)度和分派的基本單位進(jìn)程的5大特征vs.程序動態(tài)性：最基本的特性具有一定的生命期由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行；因得不到資源而阻塞；由撤消而消亡。程序只是一組有序指令的集合，存放在某種介質(zhì)上，是靜態(tài)的并發(fā)性：最重要的特征多道并發(fā)，不僅是進(jìn)程也是OS的重要特征程序本身不能并發(fā)執(zhí)行，必須“變成”進(jìn)程后才能并發(fā)獨立性是獨立運(yùn)行、調(diào)度、資源分配的基本單位；異步性進(jìn)程按各自獨立的、不可預(yù)知的速度向前推進(jìn)進(jìn)程之間是異步的對于“不可再現(xiàn)性”，需要采取某些措施來保證進(jìn)程之間的協(xié)調(diào)運(yùn)行結(jié)構(gòu)特性具有結(jié)構(gòu)性，由程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分構(gòu)成，稱“進(jìn)程映像”內(nèi)容提要多道程序技術(shù)和程序并發(fā)執(zhí)行的條件進(jìn)程的定義進(jìn)程的狀態(tài)進(jìn)程的描述進(jìn)程的控制進(jìn)程的狀態(tài)根據(jù)進(jìn)程的動態(tài)特性，進(jìn)程在整個生命期中將會出于不同的狀態(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)：進(jìn)程剛創(chuàng)建，但還沒有進(jìn)入就緒隊列需要進(jìn)程初始化，分配一些預(yù)設(shè)資源等等終止?fàn)顟B(tài)：進(jìn)程已經(jīng)（正常/異常）結(jié)束，已經(jīng)從就緒隊列中移出，但尚未撤銷需要將進(jìn)程暫時留在系統(tǒng)中，以便其他進(jìn)程去收集該進(jìn)程的相關(guān)信息狀態(tài)轉(zhuǎn)換圖Readyqueuewaitqueues六種轉(zhuǎn)換關(guān)系“七狀態(tài)”模型進(jìn)程因自身內(nèi)部的一些原因，無法繼續(xù)運(yùn)行時，暫時進(jìn)入“等待”狀態(tài)，當(dāng)?shù)却脑蛳螅涂梢苑祷鼐途w狀態(tài)；但有時候會因為進(jìn)程外部的一些原因，使得進(jìn)程暫時不能繼續(xù)運(yùn)行。外部原因主要有終端用戶的需要父進(jìn)程的需求操作系統(tǒng)的需要對換的需要負(fù)載調(diào)節(jié)的需要引入“掛起”狀態(tài)“掛起”狀態(tài)不是一種狀態(tài)，而是一類狀態(tài)掛起后處于靜止?fàn)顟B(tài)：靜止就緒，靜止阻塞非掛起的活動狀態(tài)：活動就緒，活動阻塞，還包括執(zhí)行態(tài)在狀態(tài)轉(zhuǎn)換中，增加了從活動狀態(tài)與靜止?fàn)顟B(tài)之間，以及靜止?fàn)顟B(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)存不足進(jìn)程調(diào)度：短期調(diào)度Mid-termschedulerSelectwhichprocesstoswapin&outSwapping

Removeprocessesfrommemory,&

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

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

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