【正文】 內(nèi)的一個(gè)可調(diào)度的實(shí)體 ” 。 第三章 進(jìn)程管理 1. 用戶作業(yè) 、 進(jìn)程和程序之間的聯(lián)系 所謂一個(gè)作業(yè) ， 就是用戶在一次算題過程或一個(gè)事務(wù)處理中要求計(jì)算機(jī)系統(tǒng)所做工作的總和 。 第三章 進(jìn)程管理 可變時(shí)間片輪轉(zhuǎn)法 ， (1) 系統(tǒng)的響應(yīng)時(shí)間固定 ， 每次計(jì)算就緒隊(duì)列中的進(jìn)程數(shù) ， 記為 Nmax， 則時(shí)間片為 q=T/Nmax。 如果 q取得足夠大 ， 以致所有進(jìn)程都能在分得的一個(gè)時(shí)間片內(nèi)執(zhí)行完畢 ， FCFS法 。 與作業(yè)調(diào)度算法的選擇類似 ， 進(jìn)程調(diào)度算法的選擇也要綜合各方面的因素 ， 從中選擇一種切合實(shí)際 、 行之有效的算法 。 (4) 一個(gè)具有更高優(yōu)先級的進(jìn)程要求使用處理機(jī) ， 即進(jìn)入就緒隊(duì)列 。 對于動(dòng)態(tài)優(yōu)先數(shù) ， 還須按一定算法定期地對它進(jìn)行計(jì)算 。 第三章 進(jìn)程管理 進(jìn)程調(diào)度 交通控制程序和進(jìn)程調(diào)度程序 1. 交通控制程序 交通控制程序 (Traffic Controller)是 1966 年起的名字 。 前者可能導(dǎo)致被撤消的進(jìn)程子孫與進(jìn)程家族隔離 ， 成為不可控的 。 由創(chuàng)建原語所創(chuàng)建的子進(jìn)程處于 “ 靜止就緒 ” ， 若希望該進(jìn)程盡快獲得處理機(jī) ， 應(yīng)在創(chuàng)建原語后緊跟一個(gè)激活原語 ，使之變成活躍就緒 ， 從而引起調(diào)度程序的重新調(diào)度 。掛起原語的具體作法是：以被掛起的進(jìn)程標(biāo)識名為索引， 到 PCB集合中查找該進(jìn)程的 PCB，得到該進(jìn)程的內(nèi)部標(biāo)識數(shù)，并檢查該進(jìn)程的狀態(tài)。 (3) 進(jìn)程層次清晰， 關(guān)系明確。 運(yùn)行就緒 阻塞I / O 完成調(diào)度時(shí)間片用完I/O 請求圖 進(jìn)程的基本調(diào)度狀態(tài)及其轉(zhuǎn)換 第三章 進(jìn)程管理 2. 細(xì)分的進(jìn)程調(diào)度狀態(tài) 圖 細(xì)分的進(jìn)程狀態(tài)轉(zhuǎn)換圖 低優(yōu)先級就緒中優(yōu)先級就緒高優(yōu)先級就緒運(yùn)行因頁面阻 塞因盤帶阻 塞因 I / O阻 塞運(yùn)行 5 0 0 m s 缺頁運(yùn)行100msI / O 完成運(yùn)行 50ms超過時(shí)限I / O 完成I / O 完成第三章 進(jìn)程管理 圖 具有掛起操作的進(jìn)程狀態(tài)轉(zhuǎn)換圖 活躍就緒活躍阻塞靜止阻塞時(shí)間片用完調(diào)度事件到達(dá)事件到達(dá)等待事件掛起激活掛起激活創(chuàng)建掛起活躍靜止運(yùn)行靜止就緒第三章 進(jìn)程管理 進(jìn) 程 的 控 制 進(jìn)程的控制機(jī)構(gòu) 1. 所謂 “ 原語 ” ， 是指由若干條機(jī)器指令構(gòu)成的并用以完成特定功能的一段程序 ， 這段程序在執(zhí)行期間是不可分割的 。 (4) 進(jìn)程的優(yōu)先級。 (4) 順序進(jìn)程 (有時(shí)稱為任務(wù) )是一個(gè)程序與其數(shù)據(jù)集一道順序通過處理機(jī)的執(zhí)行所發(fā)生的活動(dòng) (Alan )。 count∶ =count+1, count∶ =0。 count∶ =0 go to l2 end coend end 第三章 進(jìn)程管理 由于觀察者 和報(bào)告者 各自獨(dú)立 地并行工 作 ， count∶ =count+1 的操作 ， 既可以在報(bào)告者的 print count和count∶ =0 操作之前 ， 也可以在其后 ， 還可以在 print count和count∶ =0 之間 。 觀察者不斷觀察并對通過的卡車計(jì)數(shù) 。 第三章 進(jìn)程管理 2. 資源共享是現(xiàn)代操作系統(tǒng)另一基本特性 。 (3) 程序的執(zhí)行結(jié)果與其執(zhí)行速度無關(guān)。 除了人為的干預(yù)造成機(jī)器暫時(shí)停頓外 ， 前一動(dòng)作的結(jié)束就意味著后一動(dòng)作的開始 。 I3和 C2和 P1。 一方面 ， 資源共享是以程序并發(fā)執(zhí)行為條件的 ， 因?yàn)槿粝到y(tǒng)不允許程序并發(fā) ， 也就不存在資源共享問題；另一方面 ， 若系統(tǒng)不能對共享資源進(jìn)行有效的管理 ， 也就降低了程序并發(fā)執(zhí)行的效果 。 cobegin 第三章 進(jìn)程管理 observer begin L1； …… observe next car。 count∶ =0。 第三章 進(jìn)程管理 進(jìn)程概念的引入 (1) 行為的一個(gè)規(guī)則叫做程序 ， 程序在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動(dòng)稱為進(jìn)程 (Dijkstra)。 第三章 進(jìn)程管理 在通常的操作系統(tǒng)中 ， PCB (1) 進(jìn)程標(biāo)識名或標(biāo)識數(shù)。 第三章 進(jìn)程管理 進(jìn)程的調(diào)度狀態(tài) 1. 進(jìn)程的基本調(diào)度狀態(tài) (1) 運(yùn)行狀態(tài)。 屬于進(jìn)程控制方面的原語有進(jìn)程創(chuàng)建原語 、 進(jìn)程撤消原語 、 進(jìn)程掛起原語 、 進(jìn)程激活原語 、 進(jìn)程阻塞原語以及進(jìn)程喚醒原語等 。 這樣 ， 子進(jìn)程就建立起來了 。 一旦被激活的進(jìn)程處于 “ 活躍就緒 ” 時(shí) ， 便引起處理機(jī)的重新調(diào)度 。 然后把 “ 活躍阻塞 ” 賦予該進(jìn)程 ，并把它插入到該事件的等待隊(duì)列中 ， 再從活躍就緒隊(duì)列中按一定算法選取一進(jìn)程投入運(yùn)行 。 而且凡屬于該進(jìn)程的所有子孫也一律撤消 。 進(jìn)程調(diào)度稱為 “ 低級 ” 調(diào)度 ， 是相對作業(yè)調(diào)度而言的 。 (1) 現(xiàn)運(yùn)行進(jìn)程運(yùn)行結(jié)束或者因任務(wù)完成而正常結(jié)束 ， 或者因出現(xiàn)錯(cuò)誤而異常結(jié)束 。 第三章 進(jìn)程管理 3. 進(jìn)程調(diào)度算法的選擇 進(jìn)程調(diào)度的主要任務(wù)就是按照一定的調(diào)度算法從就緒隊(duì)列中選出一個(gè)進(jìn)程 ， 把 CPU分配給它 。 2. 動(dòng)態(tài)優(yōu)先級法 第三章 進(jìn)程管理 3. 時(shí)間片輪轉(zhuǎn)法 在時(shí)間片輪轉(zhuǎn)法中 ， 時(shí)間片是一個(gè)重要的參數(shù) 。 第三章 進(jìn)程管理 (1) (2) (3) (4) 計(jì)算機(jī)的處理能力 ， 計(jì)算機(jī)的速度越高 ， 時(shí)間片就可越短 。 第三章 進(jìn)程管理 (2) 時(shí)間片的長短取決于優(yōu)先級的高低 。 (3) 程序可以作為一種軟件資源長期保留 ， 而進(jìn)程是程序的一次執(zhí)行過程 ， 是暫時(shí)的 。 (2) 進(jìn)程的多線程都在進(jìn)程的地址空間活動(dòng) 。 (4) 至少有一個(gè)執(zhí)行進(jìn)程。也就是說 ， 進(jìn)程之間是在異步環(huán)境下運(yùn)行的 ， 每個(gè)進(jìn)程都以各自獨(dú)立的 、 不可預(yù)知的速度向運(yùn)行的終點(diǎn)推進(jìn) 。 R1∶ =R1+1。 count∶ =R1。鎖有兩種狀態(tài)： W=0 表示鎖已打開； W=1 表示鎖被關(guān)閉 。 即當(dāng) W不為 0 時(shí)轉(zhuǎn)移到上一條指令 TS繼續(xù)測試 ， 否則停止測試 ， 進(jìn)入臨界區(qū) 。 公用信號量通常用于實(shí)現(xiàn)進(jìn)程之間的互斥 ，初值為 1， 它所聯(lián)系的一組并發(fā)進(jìn)程均可對其實(shí)施 P、 V操作；私用信號量一般用于實(shí)現(xiàn)進(jìn)程間的同步 ， 初值為 0 或?yàn)槟硞€(gè)正整數(shù) n， 僅允許擁有它的進(jìn)程對其實(shí)施 P操作 。 {P} Procedure V(Var S:Semaphore)。 對此 ， 可寫出如下程序： begin count: integer。 count∶ =R1。 coend。 if Ri≥1 then begin Ri∶ =Ri1。 進(jìn)程 A負(fù)責(zé)從卡片輸入機(jī)讀入卡片送到緩沖區(qū) ， 進(jìn)程 B取走緩沖區(qū)中的卡片信息進(jìn)行加工處理 。n1］ of integer。 P(S)。 R∶ =(R+1) mod n。 讀者 —寫者問題可描述如下： begin S, Sr: semaphore。 read file F。 但在實(shí)際的系統(tǒng)中往往希望讓寫者優(yōu)先 。 V(S)。 end。 信箱大?。? boxsize。 第三章 進(jìn)程管理 send (bosname, msg) begin local X。 第三章 進(jìn)程管理 死鎖舉例 例 1 P、 V操作引起的死鎖 。 第三章 進(jìn)程管理 例 3 加鎖法引起的死鎖 。 P1： 釋放 S1, 請求 S3。 第三章 進(jìn)程管理 圖 例 5 哲學(xué)家吃通心面問題 (Dining Philosophers Problem)。 eating。 P(S 5)。 V(S 1)。 (2) 資源順序分配法。 現(xiàn)有五個(gè)進(jìn)程 A、 B、 C、 D和 E， 已獲得的資源的種類及數(shù)量用矩陣 R表示： 第三章 進(jìn)程管理 進(jìn)程 磁帶驅(qū)動(dòng)器 繪圖儀 打印機(jī) 穿孔機(jī) A 3 0 1 1 B 0 1 0 0 C 1 1 1 0 D 1 1 0 1 E 0 0 0 0 第三章 進(jìn)程管理 尚需資源的種類和數(shù)量用矩陣 Q表示： 進(jìn)程 磁帶驅(qū)動(dòng)器 繪圖儀 打印機(jī) 穿孔機(jī) A 1 1 0 0 B 0 1 1 2 C 3 1 0 0 D 0 0 1 0 E 2 1 1 0 第三章 進(jìn)程管理 (1) 如果某一進(jìn)程對某一種資源提出請求 ， 就假定預(yù)先分配給它 ， 然后修改矩陣 R、 Q以及向量 S (2) 在矩陣 Q中找出一行 ， 使該行向量小于等于 S。 第三章 進(jìn)程管理 在一般情況下 ， 系統(tǒng)由一個(gè)狀態(tài)過渡到另一個(gè)狀態(tài) ， 是由于不同進(jìn)程執(zhí)行了若干次操作的結(jié)果 ， 此時(shí)狀態(tài)的演變表示為： S W。 (6) 如果在狀態(tài) S以及它可能到達(dá)的所有狀態(tài)都是非死鎖狀態(tài)， 則 S稱為安全狀態(tài)。 若 e={Rj, Pi)， 則 e稱為一條資源分配邊 ， 由資源 Rj指向進(jìn)程 Pi， 它表示一個(gè)單位的資源 Rj分配給進(jìn)程 Pi。 第三章 進(jìn)程管理 2. 進(jìn)程 — (1) 從進(jìn)程 —資源圖中找到既非阻塞又非孤立的進(jìn)程結(jié)點(diǎn)Pi。 第三章 進(jìn)程管理 (3) 若資源 Rj有 Wj個(gè)單位 (部件 )， 并用 |(Rj, Pi)|表示資源 Rj分配給進(jìn)程 Pi的單位 (部件 )數(shù) ， 用 |(Pi, Rj)|表示進(jìn)程 Pi請求資源 Rj的單位 (部件 )數(shù) ， 則每一張合理的進(jìn)程 —資源圖必須滿足如下兩個(gè)條件： ① 對于資源 Rj所進(jìn)行的分配不能多于 Wj， 亦即對于所有的 j均應(yīng)滿足下式： jij WPiR ?? ,第三章 進(jìn)程管理 ② 對于一個(gè)具體的資源 Rj來說 ， 任何進(jìn)程對它的請求及分配數(shù)量之和 ， 不能大于 Rj的可用部件數(shù) Wj， 亦即對任何 i和 j均應(yīng)滿足下式： jjj WRPiPiR ?? ,),((4) 每一張合理的進(jìn)程 — 資源圖代表了一個(gè)系統(tǒng)狀態(tài)， 反之亦然。 (1) N被分為兩個(gè)互斥的子集：一個(gè)是進(jìn)程結(jié)點(diǎn)子集 ， π={P1, P2, …, Pn}。 (4) 一個(gè)進(jìn)程 Pi在狀態(tài) S是死鎖的 ， 是指對任何使 S→T 的 T，Pi在狀態(tài) T是阻塞的 。 第三章 進(jìn)程管理 1. 系統(tǒng)狀態(tài)圖 (1) 系統(tǒng)狀態(tài)圖是一組系統(tǒng)狀態(tài) σ={S 1, S 1, …)和一組進(jìn)程 π={P1, P2, …)構(gòu)成的一個(gè)數(shù)對 (σ, π)。 第三章 進(jìn)程管理 死鎖的避免 1. 例如 ， 設(shè)系統(tǒng)中有 10 臺(tái)磁帶機(jī) ， 由三個(gè)進(jìn)程 A、 B、 C共享 。 coend。 P(S 1)。 putdown r i+1 。 S1∶ =S2∶ =S3∶ =S4∶ =S5∶