第二講進程管理

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

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

3、圖DAG（Directed Acyclic Graph）結(jié)點：一個執(zhí)行單元（如一條語句、一個程序段或進程） （有向）邊：前驅(qū)關(guān)系“”，(Pi,Pj)|Pi必須在Pj開始執(zhí)行前執(zhí)行完若(Pi,Pj) ，可寫成PiPj其中，稱Pi是Pj的前驅(qū)，而Pj是Pi的后繼v沒有前驅(qū)的結(jié)點稱為初始結(jié)點（initial node）沒有后繼的結(jié)點稱為終止結(jié)點（final node）v結(jié)點上使用一個權(quán)值（weight）表示該結(jié)點所含的程序量或結(jié)點的執(zhí)行時間v前驅(qū)圖舉例：123865749程序的順序執(zhí)行程序的順序執(zhí)行v 一個較大的程序通常包含若干個程序段。程序必須按照某種先后順序逐個執(zhí)行。例如 其中，I代表用戶程序和

4、數(shù)據(jù)的輸入；C代表計算；P代表輸出結(jié)果v 在一個程序段中，多條語句也存在順序執(zhí)行的問題 S1：ax3 S2：by4 S3：cab S4：dacI1C1P1I2C2P2S1S2S3S4S1S2S3S4按照語句依賴關(guān)系按照語句依賴關(guān)系若按指令地址順序執(zhí)行若按指令地址順序執(zhí)行程序順序執(zhí)行時的特征程序順序執(zhí)行時的特征v順序性v封閉性v可再現(xiàn)性程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行I1C1P1I2C2P2I1C1P1I2C2P2I3C3P3I4C4P4程序并發(fā)執(zhí)行時的特征程序并發(fā)執(zhí)行時的特征v間斷性間斷性并發(fā)程序“執(zhí)行暫停執(zhí)行執(zhí)行”v失去封閉性失去封閉性由于資源共享，程序之間可能出現(xiàn)相互影響的現(xiàn)象v不可再現(xiàn)性不可

5、再現(xiàn)性原因同上。舉例：變量N的共享，設(shè)某時刻Nn，則若執(zhí)行順序為：lN:N1；print(N); N:=0; N的值依次為n1；n1；0lprint(N); N:=0; N:N1； N的值依次為n；0；1lprint(N); N:N1；N:=0; N的值依次為n；n1；0程序程序Arepeat N:=N+1;程序程序Brepeat print(N);N:=0;程序并發(fā)執(zhí)行的條件程序并發(fā)執(zhí)行的條件(Bernstein條件條件)v在上述3個特性中，必須防止“不可再現(xiàn)性”。v為使并發(fā)程序的執(zhí)行保持“可再現(xiàn)性”，引入并發(fā)執(zhí)行的條件。思路：分析程序或語句的輸入信息和輸出信息，考察它們之間的相關(guān)性符號和術(shù)

6、語定義：l讀集R(pi)，表示程序pi在執(zhí)行時需要參考的所有變量的集合l寫集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)容提要內(nèi)容提要v多道程序技術(shù)和程序并發(fā)執(zhí)行的條件v進程的定義進程的定義v進程的狀態(tài)v進程的描述v進程的控制進程進程v進程需要使用某種方法加以描述，原因進程運行的間斷性，要求在進程暫停運行時記錄該程序的現(xiàn)場，以便下次能正確的繼續(xù)運行資源的共享，要求能夠記錄進程對資源的共享情況為保證程序“正確”的

7、并發(fā)執(zhí)行，必須將進程看成某種對象，對其進行描述并加以控制v引入進程控制塊PCB進程的實體：程序段數(shù)據(jù)段PCB進程的定義進程的定義v湯子瀛，計算機操作系統(tǒng)，二版是“可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運行過程”是進程實體的運行過程vSilberschatz，Operating System Concepts，7th“A process is a program in execution”進程的進程的2大基本屬性大基本屬性v進程是可以獨立獨立運行的基本單位。v有2大基本屬性進程是一個可以擁有資源的獨立單位進程是一個可以獨立調(diào)度和分派的基本單位進程的進程的5大特征大特征 vs. 程序程序v動態(tài)性：最基

8、本的特性動態(tài)性：最基本的特性具有一定的生命期由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行；因得不到資源而阻塞；由撤消而消亡。程序只是一組有序指令的集合，存放在某種介質(zhì)上，是靜態(tài)的v并發(fā)性：最重要的特征并發(fā)性：最重要的特征多道并發(fā)，不僅是進程也是OS的重要特征程序本身不能并發(fā)執(zhí)行，必須“變成”進程后才能并發(fā)v獨立性獨立性是獨立運行、調(diào)度、資源分配的基本單位；v異步性進程按各自獨立的、不可預(yù)知的速度向前推進進程之間是異步的對于“不可再現(xiàn)性”，需要采取某些措施來保證進程之間的協(xié)調(diào)運行v結(jié)構(gòu)特性具有結(jié)構(gòu)性，由程序段、數(shù)據(jù)段及進程控制塊三部分構(gòu)成，稱“進程映像”內(nèi)容提要內(nèi)容提要v多道程序技術(shù)和程序并發(fā)執(zhí)行的條件v進程的定

9、義v進程的狀態(tài)進程的狀態(tài)v進程的描述v進程的控制進程的狀態(tài)進程的狀態(tài)v根據(jù)進程的動態(tài)特性，進程在整個生命期中將會出于不同的狀態(tài)。v狀態(tài)模型最基本的“三狀態(tài)”模型引入“新”和“終止”態(tài)的“五狀態(tài)”模型引入“掛起”狀態(tài)的“七狀態(tài)”模型“三狀態(tài)三狀態(tài)”模型模型v三種最基本的狀態(tài)就緒狀態(tài) “萬事具備，只欠CPU” 就緒隊列執(zhí)行狀態(tài)阻塞（等待、睡眠）狀態(tài)l等待原因：1）發(fā)出I/O指令之后，等待I/O操作的完成2）等待某個事件發(fā)生3）等待分配到資源等等l阻塞（等待）隊列，通常按照原因，有多個“五狀態(tài)五狀態(tài)”模型模型v在三種基本狀態(tài)中，引入新狀態(tài)：進程剛創(chuàng)建，但還沒有進入就緒隊列l(wèi)需要進程初始化，分配一些預(yù)

10、設(shè)資源等等終止?fàn)顟B(tài)：進程已經(jīng)（正常/異常）結(jié)束，已經(jīng)從就緒隊列中移出，但尚未撤銷l需要將進程暫時留在系統(tǒng)中，以便其他進程去收集該進程的相關(guān)信息狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖Ready queuewait queues六種轉(zhuǎn)換關(guān)系六種轉(zhuǎn)換關(guān)系“七狀態(tài)七狀態(tài)”模型模型v進程因自身內(nèi)部的一些原因，無法繼續(xù)運行時，暫時進入“等待”狀態(tài)，當(dāng)?shù)却脑蛳?，就可以返回就緒狀態(tài)；v但有時候會因為進程外部的一些原因，使得進程暫時不能繼續(xù)運行。外部原因主要有終端用戶的需要父進程的需求操作系統(tǒng)的需要對換的需要負載調(diào)節(jié)的需要v引入“掛起”狀態(tài)v“掛起”狀態(tài)不是一種狀態(tài)，而是一類狀態(tài)掛起后處于靜止?fàn)顟B(tài)：靜止就緒，靜止阻塞非掛

11、起的活動狀態(tài)：活動就緒，活動阻塞，還包括執(zhí)行態(tài)v在狀態(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)換圖狀態(tài)轉(zhuǎn)換圖執(zhí)行執(zhí)行活動活動就緒就緒靜止靜止就緒就緒活動活動阻塞阻塞靜止靜止阻塞阻塞激活激活掛起掛起激活激活掛起掛起釋放釋放釋放釋放掛起掛起請求請求I/O新增新增6種狀態(tài)轉(zhuǎn)換種狀態(tài)轉(zhuǎn)換調(diào)度調(diào)度 中斷中斷另外一個視圖另外一個視圖對換引入的中期調(diào)度對換引入的中期調(diào)度v作業(yè)調(diào)度：長期調(diào)度v對換：引起中期調(diào)度多道數(shù)過高，引起內(nèi)存不足v進程調(diào)度：短期調(diào)度Mid-term schedulerv Select which process to swap in & out

12、 Swapping Remove processes from memory, & reintroduce processes into memory Reduce the degree of multiprogramming, WHY?內(nèi)容提要內(nèi)容提要v多道程序技術(shù)和程序并發(fā)執(zhí)行的條件v進程的定義v進程的狀態(tài)v進程的描述進程的描述v進程的控制進程控制塊進程控制塊PCBv進程控制塊是操作系統(tǒng)中的一種關(guān)鍵數(shù)據(jù)結(jié)構(gòu)由操作系統(tǒng)進程管理模塊維護常駐內(nèi)存v操作系統(tǒng)根據(jù)PCB來控制和管理并發(fā)執(zhí)行的進程vPCB是進程存在的唯一標(biāo)志進程控制塊中的進程控制塊中的4大類信息大類信息v 進程標(biāo)識符信息： 外

13、部標(biāo)識 vs 內(nèi)部標(biāo)識v 處理機的狀態(tài)信息，即硬件上下文CPU registers: Architecture-specific PC: Address of the next instruction 通用寄存器 程序狀態(tài)字 用戶堆棧指針PointerProcess stateProcess numberProgram counterRegistersMemory limitsList of open files.v調(diào)度信息 Process state，Priority, queue pointers, v進程控制信息Memory-management information lBase &a

14、mp; limit, page/segment tables, Accounting information lTime used/limits, account numbers, process NO, I/O status informationlAllocated devices, open files, 同步和通信信息進程控制塊的組織方式進程控制塊的組織方式v在內(nèi)存中的位置：操作系統(tǒng)數(shù)據(jù)區(qū)，位于內(nèi)核中v常用的2種組織方式：鏈接方式索引方式v根據(jù)組織在一起的進程控制塊的狀態(tài)以及對應(yīng)進程的狀態(tài)的不同就緒隊列阻塞隊列空閑隊列等執(zhí)行指針執(zhí)行指針就緒隊列指針就緒隊列指針阻塞隊列指針阻塞隊列指針空

15、閑隊列指針空閑隊列指針執(zhí)行指針執(zhí)行指針就緒隊列指針就緒隊列指針阻塞隊列指針阻塞隊列指針鏈接方式鏈接方式索引方式索引方式進程在不同隊列中的遷移進程在不同隊列中的遷移v Dispatch Select a process to executev While running, events: Issue an I/O request Create a new sub-process & wait for its termination Interrupt occurredv Process migrates between queues調(diào)度引起的上下文切換調(diào)度引起的上下文切換vSaving

16、the state of the old process, &loading the saved state for the new oneContext (上下文) of a process is represented in its PCBContext-switch timelOverhead (系統(tǒng)開銷)lNo usefullTime or speed architecture-specific (11000ms), & Depends on other components (E.X.: memory management)Occurs only in kernel

17、mode進程切換引起的時空感覺上的混亂進程切換引起的時空感覺上的混亂v用戶在宏觀上：并發(fā)；間斷vCPU在微觀上：串行；連續(xù)；空間變化v程序在功能上：完整，連續(xù)；空間不變v操作系統(tǒng)在進程管理上：時空交錯內(nèi)容提要內(nèi)容提要v多道程序技術(shù)和程序并發(fā)執(zhí)行的條件v進程的定義v進程的描述v進程的狀態(tài)v進程的控制進程的控制進程控制進程控制v進程控制是操作系統(tǒng)進程管理功能的一部分，由操作系統(tǒng)內(nèi)核實現(xiàn)v操作系統(tǒng)內(nèi)核運行在內(nèi)核態(tài)，用戶程序運行在用戶態(tài)內(nèi)核態(tài)，系統(tǒng)態(tài)l具有較高的特權(quán)，能執(zhí)行一切指令，能訪問所有寄存器和存儲區(qū)用戶態(tài)，l具有較低特權(quán)，只能執(zhí)行規(guī)定的指令，訪問指定的寄存器和存儲區(qū)v用戶程序不能執(zhí)行OS特權(quán)指

18、令，不能直接訪問OS區(qū)域進程控制原語進程控制原語v進程的創(chuàng)建和進程的終止v進程的阻塞和喚醒v進程的掛起與激活v進程關(guān)系圖：用于描述進程家族關(guān)系的有向樹結(jié)點：進程若進程1創(chuàng)建了進程2，則1是2的父進程，2是1的子進程l使用從1到2的有向邊表示進程的“父子關(guān)系”l父進程的父進程：祖父進程l樹的根結(jié)點為進程家族的祖先進程樹示意圖進程樹示意圖P1P2P3P4P5P6P7P8P9P10P11P12UNIX中的經(jīng)典進程樹中的經(jīng)典進程樹父子之間的關(guān)系父子之間的關(guān)系v 資源共享關(guān)系 Parent and children share all resources Children share subset of parents resources Parent and child share no resourcesv 并發(fā)執(zhí)行關(guān)系 Parent and children execute concurrently Parent waits until children terminatev 地址空間關(guān)系 Child duplicate of parent. Child has a program loaded into it.v UNIX examples Fork system call creates new proc