【正文】 179 結(jié)構(gòu)化的同步 /互斥機(jī)構(gòu) —管程 （ Monitor） 雖然信號量是一種既方便又有效的進(jìn)程同步機(jī)制，但每個(gè)要訪問臨界資源的進(jìn)程都必須自備同步操。 173 生產(chǎn)者－消費(fèi)者問題 程序 174 175 分析下面的生產(chǎn)者－消費(fèi)者問題 176 二．讀者和寫者問題 ? 有十個(gè)讀者和兩個(gè)編輯同時(shí)處理一篇文章 ， 對于讀操作是可以同時(shí)進(jìn)行的 ， 若有讀者正在讀這篇文章 ， 編輯就不能工作 ， 若編輯正在處理這篇文章 ， 讀者就不能作讀操作 ， 編輯與編輯的工作也是互斥的 ， 試用信號燈及 P、 V操作寫出讀者與編輯之間協(xié)同工作的程序描述 。 ? 這種相互等待 ， 并互通信息就是典型的進(jìn)程同步 。 170 171 經(jīng)典的同步 / 互斥問題 一．生產(chǎn)者－消費(fèi)者問題 把前面的例子擴(kuò)充 ， 假定緩沖區(qū) buffer是一個(gè)有界緩沖區(qū) ， 可存放 n個(gè)數(shù)據(jù) ， 同時(shí)假定有 K個(gè) CP進(jìn)程不斷地產(chǎn)生數(shù)據(jù) ，并送 buffer；有 m個(gè) IOP進(jìn)程從緩沖區(qū)中取數(shù)據(jù)打印 。 要保證打印結(jié)果的正確 ， CP、 IOP必須遵循以下同步規(guī)則： (1)當(dāng) CP把結(jié)果送入 buffer后 ， IOP才能從 buffer中取 ， 否則 IOP必須等待； (2)當(dāng) IOP從 buffer中取走數(shù)據(jù)后 ， CP才能將新產(chǎn)生數(shù)據(jù)送 buffer， 否則也必須等待 。 ? 設(shè)置信號燈 ， 說明含義 、 初值 。 如兩個(gè)進(jìn)程共享一個(gè)緩沖區(qū) 。 164 同步的概念 同步：所謂同步就是并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要相互等待與互通消息 ， 這樣的相互制約關(guān)系稱為進(jìn)程同步 。 售票員 司機(jī) 。 。 ? 設(shè)信號燈 print表示打印機(jī) ， 初值為 1， 表示打印機(jī)可用 (也可理解為有 1臺打印機(jī) )。 注：阻塞該進(jìn)程包括：保存進(jìn)程 CPU現(xiàn)場；置 “ 等待 ”狀態(tài)；入等待隊(duì)列；轉(zhuǎn)進(jìn)程調(diào)度； P操作 158 （ 1） s值加 1； （ 2）若相加結(jié)果大于 0，進(jìn)程繼續(xù)執(zhí)行； （ 3）否則，喚醒一個(gè)等待該信號燈的進(jìn)程，然后本進(jìn)程繼續(xù)執(zhí)行。 在實(shí)際操作系統(tǒng)中 ， 一般情況下是由機(jī)器硬件提供 P、V操作的指令 ， 當(dāng)然是原子操作 ， 若機(jī)器不提供 P、 V操作的指令 ， 則操作系統(tǒng)提供 P、 V操作原語 。 對信號燈的 P操作記為： P(S)， P操作是一個(gè)原子操作 。 在實(shí)際應(yīng)用中應(yīng)準(zhǔn)確地說明 s的意義和初值 ， 每個(gè)信號燈都有一個(gè)隊(duì)列 ， 其初始狀態(tài)為空 。 155 ? 信號燈的定義： ? 信號燈是一個(gè)確定的二元數(shù)組（ s,q）， q ：是一個(gè)初始狀態(tài)為空的隊(duì)列。 ? 為保證打印的正確，設(shè) 置打印機(jī)的鎖位 print， 其初值為“ 0”，表示 打印機(jī)可打印。 ④ 當(dāng)進(jìn)程使用完資源后，將鎖位置為“ 0 ” ，稱為開鎖操作。 ③ 進(jìn)程僅在臨界區(qū)內(nèi)逗留有限的時(shí)間 。 ?什么叫臨界區(qū)？ （ critical section） 包含對臨界資源的訪問操作，不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的那段程序 149 臨界區(qū)的管理 計(jì)算機(jī)專家 Dijkstra 1965年提出臨界區(qū)設(shè)計(jì)原則，即一組并發(fā)進(jìn)程互斥執(zhí)行時(shí)必須滿足： ① 每次至多有一個(gè)進(jìn)程處于臨界區(qū) 。 即不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū) ,稱為互斥 。 } 臨界區(qū) 146 這兩個(gè)進(jìn)程按各自的速率執(zhí)行，兩種情況（交叉執(zhí)行）。 if ( x = 1 ) then x = x 1。 } 臨界區(qū) 145 void T2 ( x ) {lock(w)。 if ( x = 1 ) then x = x 1。 T2(x)； Coend } 144 void T1( x ) {lock(w)。 char w=?0?。 變量 X 表示系統(tǒng)中剩余的票數(shù)。 例一 假設(shè)一個(gè)飛機(jī)定票系統(tǒng)有兩個(gè)終端 ，分別運(yùn)行進(jìn)程 T1和 T2， 由于 T1和 T2是兩個(gè)可同時(shí)運(yùn)行的并發(fā)進(jìn)程 。 （ 1）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間 （ 2）計(jì)算平均周轉(zhuǎn)時(shí)間 139 作業(yè)名 到達(dá)時(shí)間 估計(jì)運(yùn)行時(shí)間 優(yōu)先數(shù) A1 B2 C3 D4 10： 00 10： 30 10： 40 10： 50 50分 40分 60分 30分 6 4 5 8 （ 1） A1 進(jìn)入時(shí)間 10： 00 完成時(shí)間 11： 30 B2 進(jìn)入時(shí)間 10： 30 完成時(shí)間 11： 10 C3 進(jìn)入時(shí)間 11： 30 完成時(shí)間 12： 30 D4 進(jìn)入時(shí)間 11： 10 完成時(shí)間 13： 00 （ 2）周轉(zhuǎn)時(shí)間 A1 1： 30 B2 00： 40 C3 1： 00 D4 1； 50 平均周轉(zhuǎn)時(shí)間 1小時(shí) 15分鐘 140 A1 B2 C3 C4 10:00 10:30 11:10 12:30 12:30 13:00 141 進(jìn)程通訊 臨界區(qū)和臨界資源 進(jìn)程互斥 信號燈和 P、 V操作 進(jìn)程同步 經(jīng)典的同步 / 互斥問題 結(jié)構(gòu)化的同步 /互斥機(jī)構(gòu) —管程 142 ? 什么叫臨界區(qū) (critical section) ？ 在并發(fā)進(jìn)程中，對共享變量操作的那段程序叫臨界區(qū) 。 假定在單道批處理環(huán)境下有 5個(gè)作業(yè)，各作業(yè)進(jìn)入系統(tǒng)的時(shí)間和估計(jì)運(yùn)行時(shí)間如下表所示 137 作業(yè) 進(jìn)入系統(tǒng)時(shí)間 估計(jì)運(yùn)行時(shí)間 /分鐘 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18 5 9:10 5 如果應(yīng)用先來先服務(wù)的作業(yè)調(diào)度算法，試將下面表格填寫完整。 136 ? 靜態(tài)： ? 進(jìn)程的優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)確定后就不再變化 。 133 完成 A1 B1 C1 D1 CPU 調(diào)度 I/O I/O完成 阻塞 時(shí)間片到 完成 A2 B2 C2 D2 CPU 調(diào)度 I/O I/O完成 阻塞 級 2（ FIFO） 時(shí)間片到 調(diào)度 完成 An Bn Cn Dn CPU I/O I/O完成 阻塞 時(shí)間片到 級 n（ FIFO） 級 1（ FIFO） 134 ? 首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列 ? 每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級高的 為第一級隊(duì)列，時(shí)間片最小，隨著隊(duì)列級別的降低，時(shí)間片加大 ? 各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法 ? 一個(gè)新進(jìn)程就緒后進(jìn)入第一級隊(duì)列 ? 進(jìn)程由于等待而放棄 CPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列 ? 當(dāng)有一個(gè)優(yōu)先級更高的進(jìn)程就緒時(shí)，可以搶占CPU，被搶占進(jìn)程回到本級就緒隊(duì)列末尾 ? 當(dāng)?shù)谝患夑?duì)列空時(shí)，就去調(diào)度第二級隊(duì)列，如此類推 ? 當(dāng)時(shí)間片到后，進(jìn)程放棄 CPU，回到下一級隊(duì)列 135 ４ .優(yōu)先級調(diào)度算法 ? 優(yōu)先數(shù)調(diào)度算法是目前操作系統(tǒng)廣泛采用的一種進(jìn)程調(diào)度算法 ， 這種算法按照某種原則由系統(tǒng)（ 或用戶 、 或系統(tǒng)與用戶結(jié)合 ） 賦予每個(gè)進(jìn)程一個(gè)優(yōu)先數(shù) ， 在處理機(jī)空閑時(shí) ， 進(jìn)程調(diào)度程序就從就緒進(jìn)程中選擇一個(gè)優(yōu)先數(shù)最大 （ 或者最小 ） 的進(jìn)程占用 CPU。 這種方法得到的時(shí)間片是隨就緒隊(duì)列中的進(jìn)程數(shù)變化的 。 131 時(shí)間片 S ＝ R / Nmax R——響應(yīng)時(shí)間 Nmax——最大進(jìn)程數(shù) 每當(dāng)一輪調(diào)度開始時(shí) ， 系統(tǒng)便根據(jù)就緒隊(duì)列中已有進(jìn)程數(shù)目計(jì)算一次值 。 2. 輪轉(zhuǎn)調(diào)度算法（ RR） 129 I/O I/O完成 完成 A B C D CPU 調(diào)度 阻塞 到達(dá) 時(shí)間片到 輪轉(zhuǎn)調(diào)度算法 130 時(shí)間片輪轉(zhuǎn)策略特別適合于分時(shí)系統(tǒng)中使用 ， 當(dāng)多個(gè)進(jìn)程駐留在主存中時(shí) ， 在進(jìn)程間轉(zhuǎn)換 ， 處理機(jī)的開銷一般是不大的 。 128 其進(jìn)程就緒隊(duì)列往往按到達(dá)時(shí)間來排序 ， 按照先來先服務(wù)原則調(diào)度 ， 一個(gè)進(jìn)程占用處理機(jī)僅使用一個(gè)時(shí)間片 。 127 在當(dāng)今系統(tǒng)中 ， 先進(jìn)先出算法很少作為調(diào)度模式 ， 而是常常嵌套在其它的調(diào)度模式中 。 這種調(diào)度從形式上講是公平的 ， 但它使短作業(yè)要等待長作業(yè)的完成 ， 重要的作業(yè)要等待不重要作業(yè)的完成 。 進(jìn)程調(diào)度的核心問題就是 ， 采用什么算法把處理機(jī)分配給進(jìn)程 。 進(jìn)程調(diào)度 124 進(jìn)程調(diào)度程序： 負(fù)責(zé)進(jìn)程調(diào)度功能的內(nèi)核程序 。 在作業(yè)完成后要撤銷該作業(yè)的全部進(jìn)程 。 121 作業(yè) 進(jìn)入 執(zhí)行 開始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)刻 帶權(quán)周轉(zhuǎn)時(shí)刻 1 1 2 2 3 3 2 4 4 平均周轉(zhuǎn)時(shí)間 T＝ 平均帶權(quán)周轉(zhuǎn)時(shí)間 W＝ 122 響應(yīng)比 R R2 = 1 + (10 – ) / R3 = 1+ ( 10 － ) / = R4 = 1 + (10 － ) / R2 = 1 + ( － ) / = R4 = 1 + ( － ) / 123 進(jìn)程調(diào)度的功能：從就緒隊(duì)列中挑選一個(gè)進(jìn)程到處理機(jī)上運(yùn)行 。 由于 R與要求運(yùn)行時(shí)間成反比 ， 故對短作業(yè)是有利的 ， 另一方面 ， 因 R與等待時(shí)間成正比 ， 故長作業(yè)隨著其等待時(shí)間的增長 ， 也可獲得較高的響應(yīng)比 。 作業(yè)調(diào)度算法 115 作業(yè) 進(jìn)入 執(zhí)行 開始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2 3 4 ① 周轉(zhuǎn)時(shí)間 T1 ＝ － ＝ 帶權(quán)周轉(zhuǎn)時(shí)間 W1 ＝ 2 / 2 ＝ 1 ② 周轉(zhuǎn)時(shí)間 T2 ＝ － ＝ 帶權(quán)周轉(zhuǎn)時(shí)間 W2 ＝ / ＝ 先來先服務(wù)算法分析結(jié)果 116 ③ 周轉(zhuǎn)時(shí)間 T3 ＝ － ＝ 帶權(quán)周轉(zhuǎn)時(shí)間 W3 ＝ / ＝ ④ 周轉(zhuǎn)時(shí)間 T4＝ － ＝ 帶權(quán)周轉(zhuǎn)時(shí)間 W4＝ / ＝ 周轉(zhuǎn)時(shí)間 Ti ＝ Tei － Tsi 帶權(quán)周轉(zhuǎn)時(shí)間 Wi ＝ Ti / Tri 平均周轉(zhuǎn)時(shí)間 T＝ 1/n ∑ Ti 117 該算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè) 。 Wi = Ti / Tri 平均帶權(quán)周轉(zhuǎn)時(shí)間為： n W = 1/n ∑ Wi i=1 114 （ 1） 先來先服務(wù) （ FCFS） 調(diào)度算法 將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列 ， 并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理 ， 是一種最普遍和最簡單的方法 。 Ti = Tei — Tsi 周轉(zhuǎn)時(shí)間 = 完成 — 提交 112 作業(yè)平均周轉(zhuǎn)時(shí)間為 （ 有 n 個(gè)作業(yè) ， n = 1 )