第二講進程管理

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

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

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

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

5、再現性原因同上。舉例：變量N的共享，設某時刻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個特性中，必須防止“不可再現性”。v為使并發(fā)程序的執(zhí)行保持“可再現性”，引入并發(fā)執(zhí)行的條件。思路：分析程序或語句的輸入信息和輸出信息，考察它們之間的相關性符號和術

6、語定義：l讀集R(pi)，表示程序pi在執(zhí)行時需要參考的所有變量的集合l寫集W(pi)，表示程序pi在執(zhí)行期間要改變的所有變量的集合1966， Bernstein：若兩個程序p1和p2滿足下列條件，則它們就能并發(fā)執(zhí)行，且具有可再現性R(p1) W(p2) R(p2) W(p1) W(p1) W(p2) 內容提要內容提要v多道程序技術和程序并發(fā)執(zhí)行的條件v進程的定義進程的定義v進程的狀態(tài)v進程的描述v進程的控制進程進程v進程需要使用某種方法加以描述，原因進程運行的間斷性，要求在進程暫停運行時記錄該程序的現場，以便下次能正確的繼續(xù)運行資源的共享，要求能夠記錄進程對資源的共享情況為保證程序“正確”的

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

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

9、義v進程的狀態(tài)進程的狀態(tài)v進程的描述v進程的控制進程的狀態(tài)進程的狀態(tài)v根據進程的動態(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)需要進程初始化，分配一些預

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

11、起的活動狀態(tài)：活動就緒，活動阻塞，還包括執(zhí)行態(tài)v在狀態(tài)轉換中，增加了從活動狀態(tài)與靜止狀態(tài)之間，以及靜止狀態(tài)內部之間的狀態(tài)轉換狀態(tài)轉換圖狀態(tài)轉換圖執(zhí)行執(zhí)行活動活動就緒就緒靜止靜止就緒就緒活動活動阻塞阻塞靜止靜止阻塞阻塞激活激活掛起掛起激活激活掛起掛起釋放釋放釋放釋放掛起掛起請求請求I/O新增新增6種狀態(tài)轉換種狀態(tài)轉換調度調度 中斷中斷另外一個視圖另外一個視圖對換引入的中期調度對換引入的中期調度v作業(yè)調度：長期調度v對換：引起中期調度多道數過高，引起內存不足v進程調度：短期調度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?內容提要內容提要v多道程序技術和程序并發(fā)執(zhí)行的條件v進程的定義v進程的狀態(tài)v進程的描述進程的描述v進程的控制進程控制塊進程控制塊PCBv進程控制塊是操作系統(tǒng)中的一種關鍵數據結構由操作系統(tǒng)進程管理模塊維護常駐內存v操作系統(tǒng)根據PCB來控制和管理并發(fā)執(zhí)行的進程vPCB是進程存在的唯一標志進程控制塊中的進程控制塊中的4大類信息大類信息v 進程標識符信息： 外

13、部標識 vs 內部標識v 處理機的狀態(tài)信息，即硬件上下文CPU registers: Architecture-specific PC: Address of the next instruction 通用寄存器 程序狀態(tài)字 用戶堆棧指針PointerProcess stateProcess numberProgram counterRegistersMemory limitsList of open files.v調度信息 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在內存中的位置：操作系統(tǒng)數據區(qū)，位于內核中v常用的2種組織方式：鏈接方式索引方式v根據組織在一起的進程控制塊的狀態(tài)以及對應進程的狀態(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調度引起的上下文切換調度引起的上下文切換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)在進程管理上：時空交錯內容提要內容提要v多道程序技術和程序并發(fā)執(zhí)行的條件v進程的定義v進程的描述v進程的狀態(tài)v進程的控制進程的控制進程控制進程控制v進程控制是操作系統(tǒng)進程管理功能的一部分，由操作系統(tǒng)內核實現v操作系統(tǒng)內核運行在內核態(tài)，用戶程序運行在用戶態(tài)內核態(tài)，系統(tǒng)態(tài)l具有較高的特權，能執(zhí)行一切指令，能訪問所有寄存器和存儲區(qū)用戶態(tài)，l具有較低特權，只能執(zhí)行規(guī)定的指令，訪問指定的寄存器和存儲區(qū)v用戶程序不能執(zhí)行OS特權指

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