【正文】 第 2 章 進(jìn) 程 管 理 第二章 進(jìn)程管理 進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程的同步與互斥 經(jīng)典的進(jìn)程同步問題 管程機(jī)制 進(jìn)程通信 線程 第 2 章 進(jìn) 程 管 理 第 一 節(jié) 進(jìn)程的基本概念 第 2 章 進(jìn) 程 管 理 一、程序的順序執(zhí)行 程序是一個(gè)在時(shí)間上有嚴(yán)格次序的指令序列。僅當(dāng)前一操作 (程序段 )執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。 第 2 章 進(jìn) 程 管 理 圖 21 程序的順序執(zhí)行 ( a ) 程序的 順序執(zhí)行 ( b ) 三條語 句的順序執(zhí) 行I 1 C 1 P 1 I 2 C 2 P 2 S 1 S 2 S 3第 2 章 進(jìn) 程 管 理 在單道系統(tǒng)中，程序執(zhí)行具有以下特征 (P5)： (1) 順序性 (2) 封閉性 (3) 可再現(xiàn)性 其中最大特征就是程序的順序執(zhí)行。 第 2 章 進(jìn) 程 管 理 二、前趨圖 前趨圖 (Precedence Graph)是一個(gè) 有向無循環(huán) 圖，記為 DAG(Directed Acyclic Graph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的 每個(gè)結(jié)點(diǎn) 可用于描述一個(gè)程序段或進(jìn)程、一條語句；結(jié)點(diǎn)間的 有向邊 則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序 (Partial Order)或前趨關(guān)系 (Precedence Relation)“→ ”。 第 2 章 進(jìn) 程 管 理 →={(P i, Pj)|Pi must plete before Pj may start}, 如果 (Pi, Pj)∈ →, 可寫成 Pi→P j，稱 Pi是Pj的直接前趨，而稱 Pj是 Pi的直接后繼。在前趨圖中，把沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn) (Initial Node)，把沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn) (Final Node)。 第 2 章 進(jìn) 程 管 理 每個(gè)結(jié)點(diǎn)還具有一個(gè) 重量 (Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的 執(zhí)行時(shí)間 。 P1P3P8P9P4P2P5P6P7S1S2S3( a ) 具有九 個(gè)結(jié)點(diǎn)的前 趨圖 ( b ) 具有循 環(huán)的前趨圖圖 22 前趨圖 第 2 章 進(jìn) 程 管 理 對(duì)于圖 22(a)所示的前趨圖， 存在下述前趨關(guān)系： P1→P 2, P1→P 3, P1→P 4, P2→P 5, P3→P 5, P4→P 6, P4→P 7, P5→P 8, P6→P 8, P7→P 9, P8→P 9 或表示為： P={P1, P2, P3, P4, P5, P6, P7, P8, P9} →={ (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9)} 第 2 章 進(jìn) 程 管 理 三、程序的并發(fā)執(zhí)行 什么是程序的并發(fā)執(zhí)行 (回顧 ) 程序的并發(fā)執(zhí)行可進(jìn)一步分為：①不同程序間的并發(fā)執(zhí)行；②同一程序中不同程序段的并發(fā)執(zhí)行。 第 2 章 進(jìn) 程 管 理 并發(fā)程序的前趨圖： P1P2P3P4I1I2I3I4C1C2C3C4第 2 章 進(jìn) 程 管 理 在該例中存在下述前趨關(guān)系： Ii→C i， Ii→I i+1, Ci→P i, Ci→C i+1， Pi→P i+1 而 Ii+1和 Ci及 Pi1是重迭的 ， 亦即在 Pi1和 Ci以及 Ii+1之間 ， 可以并發(fā)執(zhí)行 。 第 2 章 進(jìn) 程 管 理 對(duì)于具有下述四條語句的程序段 ， 前趨圖： S1: a∶ =x+2 S2: b∶ =y+4 S3: c∶ =a+b S4: d∶ =c+b S1S2S3S4第 2 章 進(jìn) 程 管 理 程序并發(fā)執(zhí)行帶來的影響： 程序運(yùn)行的間斷性； 程序的執(zhí)行失去了封閉性和以此為基礎(chǔ)的可再現(xiàn)性； 程序之間由于資源共享與競(jìng)爭(zhēng)，形成了相互制約。 第 2 章 進(jìn) 程 管 理 例如 ， 有兩個(gè)循環(huán)程序 A和 B， 它們共享一個(gè)變量 N。 程序 A每執(zhí)行一次時(shí) ， 都要做 N∶ =N+1操作；程序 B每執(zhí)行一次時(shí) ， 都要執(zhí)行 Print(N)操作 ， 然后再將 N置成 “ 0”。 程序 A和 B以不同的速度運(yùn)行 。 (1) N∶ =N+1在 Print(N)和 N∶ =0之前 ， 此時(shí)得到的 N值分別為 n+1, n+1, 0。 (2) N∶ =N+1在 Print(N)和 N∶ =0之后 ， 此時(shí)得到的 N值分別為 n, 0, 1。 (3) N∶ =N+1在 Print(N)和 N∶ =0之間 ， 此時(shí)得到的 N值分別為 n, n+1, 0。 第 2 章 進(jìn) 程 管 理 為了合理管理系統(tǒng)資源、協(xié)調(diào)各程序段在執(zhí)行時(shí)對(duì)資源的競(jìng)爭(zhēng)，需要一個(gè)記錄和描述程序執(zhí)行過程的基本單位，于是引進(jìn)了“進(jìn)程”這一概念。 第 2 章 進(jìn) 程 管 理 四、進(jìn)程的定義 較典型的進(jìn)程定義有： (1) 進(jìn)程是程序的一次執(zhí)行 。 (2) 進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng) 。 (3) 進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程 ， 它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位 。 第 2 章 進(jìn) 程 管 理 四、進(jìn)程的定義 進(jìn)程實(shí)體：程序段、相關(guān)數(shù)據(jù)、 PCB(進(jìn)程控制塊 )管理進(jìn)程的數(shù)據(jù)結(jié)構(gòu) 進(jìn)程的特征 (p1922)： (1) 結(jié)構(gòu)特征 (2) 動(dòng)態(tài)性 (3) 并發(fā)性 (4) 獨(dú)立性 (5)異步性 第 2 章 進(jìn) 程 管 理 在引入了進(jìn)程實(shí)體的概念后 ， 我們可以把傳統(tǒng) OS中的進(jìn)程定義為： “ 進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程 ， 是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位 ” 第 2 章 進(jìn) 程 管 理 五、進(jìn)程的三種基本狀態(tài) (p2324) 就緒狀態(tài) 就緒隊(duì)列 執(zhí)行狀態(tài) 阻塞狀態(tài) (等待狀態(tài) )等待隊(duì)列 第 2 章 進(jìn) 程 管 理 進(jìn)程基本狀態(tài)轉(zhuǎn)換圖 就緒 執(zhí)行 阻塞 進(jìn)程調(diào)度 時(shí)間片用完 等待某個(gè)事件發(fā)生而阻塞 因等待的事件已發(fā)生而被喚醒 創(chuàng)建 撤消 第 2 章 進(jìn) 程 管 理 圖 27 進(jìn)程的五種基本狀態(tài)及轉(zhuǎn)換 p3133 創(chuàng)建 就緒阻塞 執(zhí)行 終止許可I / O 請(qǐng)求釋放I/O完成時(shí)間片完進(jìn)程調(diào)度第 2 章 進(jìn) 程 管 理 六、掛起狀態(tài) 在一般 OS中，進(jìn)程只有以上三種基本狀態(tài)。而在一些有特殊要求的 OS中，由于控制的需要，引入“掛起”狀態(tài)。 “掛起”狀態(tài)有 靜止就緒 和 靜止阻塞 兩種?！皰炱稹本鸵馕吨鴷和?duì)該進(jìn)程分配 CPU資源。 第 2 章 進(jìn) 程 管 理 六、掛起狀態(tài) 引起“掛起”的原因 (P2627)： (1) 終端用戶的請(qǐng)求。 (2) 父進(jìn)程請(qǐng)求。 (3) 負(fù)荷調(diào)節(jié)的需要。 (4) 操作系統(tǒng)的需要。 第 2 章 進(jìn) 程 管 理 圖 26 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 活動(dòng)就緒靜止就緒執(zhí)行掛起激活釋放掛起活動(dòng)阻塞靜止阻塞掛起激活釋放請(qǐng)求I/O調(diào)度 第 2 章 進(jìn) 程 管 理 圖 28 具有創(chuàng)建、終止和掛起狀態(tài)的進(jìn)程狀態(tài)圖 創(chuàng)建 終止執(zhí)行活動(dòng)就緒活動(dòng)阻塞靜止阻塞靜止就緒許可許可請(qǐng)求I/O釋放激活掛起釋放掛起激活掛起釋放第 2 章 進(jìn) 程 管 理 七、進(jìn)程控制塊 (PCB) 進(jìn)程控制塊：包含了進(jìn)程的描述信息、控制信息、資源信息的 數(shù)據(jù)結(jié)構(gòu) 。它隨進(jìn)程的創(chuàng)建而產(chǎn)生、在進(jìn)程執(zhí)行的過程中記錄進(jìn)程各信息的變化。當(dāng)一個(gè)進(jìn)程完成其功能后，系統(tǒng)則回收 PCB，進(jìn)程也隨之消失。 第 2 章 進(jìn) 程 管 理 進(jìn)程控制塊的作用： 標(biāo)識(shí)進(jìn)程的存在、動(dòng)態(tài)地記錄進(jìn)程運(yùn)行過程中的所有控制信息，如進(jìn)程狀態(tài)、中斷現(xiàn)場(chǎng)、進(jìn)程的優(yōu)先級(jí)等，以便 OS感知進(jìn)程的存在，根據(jù)系統(tǒng)資源的情況和設(shè)計(jì)原則 (算法 )對(duì)進(jìn)程 (通過 PCB)進(jìn)行控制和管理。 第 2 章 進(jìn) 程 管 理 3. 進(jìn)程控制塊中的信息 1) 進(jìn)程標(biāo)識(shí)符 進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程 。 一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符： (1) 內(nèi)部標(biāo)識(shí)符 。 在所有的操作系統(tǒng)中 ， 都為每一個(gè)進(jìn)程賦予一個(gè)惟一的 數(shù)字標(biāo)識(shí)符 ， 它通常是一個(gè)進(jìn)程的序號(hào) 。 設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便系統(tǒng)使用 。 (2) 外部標(biāo)識(shí)符 。 它由創(chuàng)建者提供 ， 通常是由 字母 、數(shù)字 組成 ， 往往是由用戶 (進(jìn)程 )在訪問該進(jìn)程時(shí)使用 。為了描述進(jìn)程的 家族關(guān)系 ， 還應(yīng)設(shè)置父進(jìn)程標(biāo)識(shí)及子進(jìn)程標(biāo)識(shí) 。 此外 ， 還可設(shè)置用戶標(biāo)識(shí) ， 以指示擁有該進(jìn)程的用戶 。 第 2 章 進(jìn) 程 管 理 2) 處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的 。 ① 通用寄存器 ， 又稱為用戶可視寄存器 ，它們是用戶程序可以訪問的 ， 用于暫存信息 ， 在大多數(shù)處理機(jī)中 ， 有 8~32 個(gè)通用寄存器 ， 在 RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過 100 個(gè)； ② 指令計(jì)數(shù)器 ， 其中存放了要訪問的下一條指令的地址； ③ 程序狀態(tài)字 PSW， 其中含有狀態(tài)信息 ， 如條件碼 、 執(zhí)行方式 、 中斷屏蔽標(biāo)志等； ④ 用戶棧指針 ， 指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧 ， 用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址 。 棧指針指向該棧的棧頂 。 第 2 章 進(jìn) 程 管 理 3) 進(jìn)程調(diào)度信息 在 PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信息 ， 包括： ① 進(jìn)程狀態(tài) ， 指明進(jìn)程的當(dāng)前狀態(tài) ， 作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)； ② 進(jìn)程優(yōu)先級(jí) ， 用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù) ， 優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)； ③ 進(jìn)程調(diào)度所需的其它信息 ， 它們與所采用的進(jìn)程調(diào)度算法有關(guān) ， 比如 ，進(jìn)程已等待 CPU的時(shí)間總和 、 進(jìn)程已執(zhí)行的時(shí)間總和等； ④ 事件 ， 是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件 ， 即阻塞原因 。 第 2 章 進(jìn) 程 管 理 4) 進(jìn)程控制信息 進(jìn)程控制信息包括： ① 程序和數(shù)據(jù)的地址 ， 是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地 (首 )址 ，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí) ， 能從 PCB中找到其程序和數(shù)據(jù)； ② 進(jìn)程同步和通信機(jī)制 ， 指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制 ， 如消息隊(duì)列指針 、信號(hào)量等 ， 它們可能全部或部分地放在 PCB中； ③ 資源清單 ， 是一張列出了除 CPU以外的 、 進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單； ④ 鏈接指針 ， 它給出了本進(jìn)程 (PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的 PCB的首地址 。 第 2 章 進(jìn) 程 管 理 在系統(tǒng)中存在的各種進(jìn)程隊(duì)列，就是由進(jìn)程的 PCB組成的。 PCB組成隊(duì)列的方式： 鏈接方式 索引方式 第 2 章 進(jìn) 程 管 理 1) 鏈接方式 圖 27 PCB鏈接隊(duì)列示意圖 P C B 1 4P C B 2P C B 3P C B 4P C B 5P C B 6P C B 7P C B 8P C B 93087901執(zhí) 行 指 針就 緒 隊(duì) 列 指 針阻 塞 隊(duì) 列 指 針空 閑 隊(duì)