【正文】 作業(yè)進入系統(tǒng)的時間和估計運行時間如下表所示 137 作業(yè) 進入系統(tǒng)時間 估計運行時間 /分鐘 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)度算法，試將下面表格填寫完整。 138 作業(yè) 進入系統(tǒng)時間 估計運行時間 /分鐘 開始時間 結(jié)束時間 周轉(zhuǎn)時間 /分鐘 1 8:00 40 8： 00 2 8:20 30 3 8:30 12 4 9:00 18 5 9:10 5 作業(yè)平均周轉(zhuǎn)時間 T= 在一個兩道作業(yè)的批處理系統(tǒng)中，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。 （ 1）列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間 （ 2）計算平均周轉(zhuǎn)時間 139 作業(yè)名 到達(dá)時間 估計運行時間 優(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 進入時間 10： 00 完成時間 11： 30 B2 進入時間 10： 30 完成時間 11： 10 C3 進入時間 11： 30 完成時間 12： 30 D4 進入時間 11： 10 完成時間 13： 00 （ 2）周轉(zhuǎn)時間 A1 1： 30 B2 00： 40 C3 1： 00 D4 1； 50 平均周轉(zhuǎn)時間 1小時 15分鐘 140 A1 B2 C3 C4 10:00 10:30 11:10 12:30 12:30 13:00 141 進程通訊 臨界區(qū)和臨界資源 進程互斥 信號燈和 P、 V操作 進程同步 經(jīng)典的同步 / 互斥問題 結(jié)構(gòu)化的同步 /互斥機構(gòu) —管程 142 ? 什么叫臨界區(qū) (critical section) ？ 在并發(fā)進程中，對共享變量操作的那段程序叫臨界區(qū) 。 或把不允許多個并發(fā)進程交叉執(zhí)行的一段程序稱為臨界區(qū)。 例一 假設(shè)一個飛機定票系統(tǒng)有兩個終端 ，分別運行進程 T1和 T2， 由于 T1和 T2是兩個可同時運行的并發(fā)進程 。 系統(tǒng)會出現(xiàn)何種情況 . 臨界區(qū)和臨界資源 143 其中 Cobegin和 Coend表示在它們之間的程序是并發(fā)執(zhí)行的，交叉調(diào)用。 變量 X 表示系統(tǒng)中剩余的票數(shù)。 main( ) { int x。 char w=?0?。 Cobegin T1(x)。 T2(x)； Coend } 144 void T1( x ) {lock(w)。 read ( x )。 if ( x = 1 ) then x = x 1。 出票； write ( x )； unlock(w)。 } 臨界區(qū) 145 void T2 ( x ) {lock(w)。 read ( x )。 if ( x = 1 ) then x = x 1。 出票； write ( x )； unlock(w)。 } 臨界區(qū) 146 這兩個進程按各自的速率執(zhí)行，兩種情況（交叉執(zhí)行）。 第一種情況：正常 時間 T0 T1 T2 T3 T4 T5 X T1 T2 1 read(x) 1 x=x1 0 read(x) 0 write(x) 0 0 write(x) 147 第二種情況： 時間 T0 T1 T2 T3 T4 T5 X T1 T2 1 read(x) 1 read(x) 1 x=x1 0 x=x1 write(x) 0 0 write(x) 結(jié)果：兩個不同售票點售出了兩張相同的票．出現(xiàn)了與時間有關(guān)的錯誤 148 ? 什么叫互斥 ？ 一組并發(fā)進程中的一個或多個程序段 ， 因共享某一公有資源而導(dǎo)致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行 。 即不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū) ,稱為互斥 。 例如：進程 p1，p2共享使用打印機 ?什么叫臨界資源？ （ critical resource） 一次僅允許一個進程使用的資源稱為臨界資源 。 ?什么叫臨界區(qū)？ （ critical section） 包含對臨界資源的訪問操作，不允許多個并發(fā)進程交叉執(zhí)行的那段程序 149 臨界區(qū)的管理 計算機專家 Dijkstra 1965年提出臨界區(qū)設(shè)計原則，即一組并發(fā)進程互斥執(zhí)行時必須滿足： ① 每次至多有一個進程處于臨界區(qū) 。 ② 當(dāng)若干進程同時要求進入它們的臨界區(qū)時 ， 應(yīng)在有限時間內(nèi)使一進程進入臨界區(qū) ， 它們不應(yīng)相互堵塞而致使彼此不能進入臨界區(qū) 。 ③ 進程僅在臨界區(qū)內(nèi)逗留有限的時間 。 150 進程互斥的實現(xiàn) 、開鎖操作 當(dāng)一個進程使用某個臨界資源之前必須完成下列操作： ① 考察鎖位的值； ② 若原來的值是為 “ 0”，將鎖位置為 “ 1”,即 上鎖； ③ 若原來值是為 “ 1”，說明該資源已被別人占用，則轉(zhuǎn)到第 ① 步。 ④ 當(dāng)進程使用完資源后，將鎖位置為“ 0 ” ，稱為開鎖操作。 151 152 2. 用上鎖原語和開鎖原語實現(xiàn)互斥 ? 假設(shè)有兩個進程共享打 印機，兩個進程中使用 打印機的程序段為臨界 區(qū)。 ? 為保證打印的正確，設(shè) 置打印機的鎖位 print， 其初值為“ 0”，表示 打印機可打印。 153 154 信號量和 P、 V操作 1. 信號量 (semaphore)的概念 信號量是一個被保護的變量 ， 只有 P操作 、V操作和一種稱為信號量初始化操作才能訪問和改變它的值 。 155 ? 信號燈的定義： ? 信號燈是一個確定的二元數(shù)組（ s,q）， q ：是一個初始狀態(tài)為空的隊列。 S：一個有非負(fù)初值的整型變量 ， 代表資源的實體 。 在實際應(yīng)用中應(yīng)準(zhǔn)確地說明 s的意義和初值 ， 每個信號燈都有一個隊列 ， 其初始狀態(tài)為空 。 156 2 . P、 V操作 信號燈的值僅能由 P、 V操作來改變 。 對信號燈的 P操作記為： P(S)， P操作是一個原子操作 。 對信號燈的 V操作記為： V(S), V操作是一個原子操作 。 在實際操作系統(tǒng)中 ， 一般情況下是由機器硬件提供 P、V操作的指令 ， 當(dāng)然是原子操作 ， 若機器不提供 P、 V操作的指令 ， 則操作系統(tǒng)提供 P、 V操作原語 。 157 （ 1） s值減 1； （ 2） 若相減結(jié)果大于等于 0，則進程繼續(xù)執(zhí)行； （ 3） 若結(jié)果小于 0， 則該進程阻塞 。 注：阻塞該進程包括：保存進程 CPU現(xiàn)場；置 “ 等待 ”狀態(tài)；入等待隊列；轉(zhuǎn)進程調(diào)度； P操作 158 （ 1） s值加 1； （ 2）若相加結(jié)果大于 0，進程繼續(xù)執(zhí)行； （ 3）否則，喚醒一個等待該信號燈的進程，然后本進程繼續(xù)執(zhí)行。 V操作 159 3. 用信號燈實現(xiàn)進程互斥 ? 用兩個進程共享打印機的例子 。 ? 設(shè)信號燈 print表示打印機 ， 初值為 1， 表示打印機可用 (也可理解為有 1臺打印機 )。 160 161 用 P、 V操作解決進程間互斥問題 P(mutex) V(mutex) P1 P2 P3 互斥區(qū) P(mutex) P(mutex) V(mutex) V(mutex) 比喻：每個人都有一把進門的鑰匙，但只能容納一個人 162 進程同步（ synchronism） 先看一個例子 163 到站停車 開 車 開 車 門 關(guān) 車 門 售 票 正常行車 。 。 。 售票員 司機 。 。 164 同步的概念 同步：所謂同步就是并發(fā)進程在一些關(guān)鍵點上可能需要相互等待與互通消息 ， 這樣的相互制約關(guān)系稱為進程同步 。 在操作系統(tǒng)中 ， 同步有各種各樣 ， 但歸納起來有兩類 ? 諸進程合作完成某工作的邏輯順序 ； ? 對系統(tǒng)資源的共享 。 如兩個進程共享一個緩沖區(qū) 。 165 3 . 用信號燈實現(xiàn)進程的同步 （ 一 ） 合作進程的執(zhí)行次序 用進程流程圖 (前趨圖 ） 來描述諸進程合作完成某一任務(wù)的次序 ， 其規(guī)則如下： 166 ? 用信號燈及 P、 V操作來描述左圖 ? 說明進程的同步關(guān)系 ? 進程 P P2可并行執(zhí)行 ， P3的執(zhí)行必須等待 P P2都完成后才能開始執(zhí)行 。 ? 設(shè)置信號燈 ， 說明含義 、 初值 。 ? s13 = 0 表示進程 P1尚未執(zhí)行完成； ? s23 = 0 表示進程 P2尚未執(zhí)行完成； 167 168 設(shè)有一個緩沖區(qū) buffer， 大小為一個字節(jié) ， CP進程不斷產(chǎn)生字符 ， 送buffer， IOP進程從 buffer中取出字符打印 。 要保證打印結(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， 否則也必須等待 。 (二 ） 共享緩沖區(qū)的合作進程的同步 169 解決這個問題的步驟： (1)分析問題 ， 弄清楚同步關(guān)系 ， 如上分析； (2)設(shè)置信號燈 ， 說明含義 、 初值； (3)寫出程序描述 。 170 171 經(jīng)典的同步 / 互斥問題 一．生產(chǎn)者－消費者問題 把前面的例子擴充 ， 假定緩沖區(qū) buffer是一個有界緩沖區(qū) ， 可存放 n個數(shù)據(jù) ， 同時假定有 K個 CP進程不斷地產(chǎn)生數(shù)據(jù) ，并送 buffer；有 m個 IOP進程從緩沖區(qū)中取數(shù)據(jù)打印 。 172 ? 對于生產(chǎn)者進程： 產(chǎn)生一個數(shù)據(jù) ， 當(dāng)要送入緩沖區(qū)時 ， 要檢查緩沖區(qū)是否已滿 ， 若未滿 ， 則可將數(shù)據(jù)送入緩沖區(qū) ， 并通知消費者進程；否則 ， 等待； ? 對于消費者進程： 當(dāng)它去取數(shù)據(jù)時 ， 要看緩沖區(qū)中是否有數(shù)據(jù)可取 ， 若有則取走一個數(shù)據(jù) ， 并通知生產(chǎn)者進程 ， 否則 ， 等待 。 ? 這種相互等待 ， 并互通信息就是典型的進程同步 。 ? 同時 ， 緩沖區(qū)是個臨界資源 ， 因此 ， 諸進程對緩沖區(qū)的操作程序是一個共享臨界區(qū) ， 因此 ，還有個互斥的問題 。 173 生產(chǎn)者－消費者問題 程序 174 175 分析下面的生產(chǎn)者－消費者問題 176 二．讀者和寫者問題 ? 有十個讀者和兩個編輯同時處理一篇文章 ， 對于讀操作是可以同時進行的 ， 若有讀者正在讀這篇文章 ， 編輯就不能工作 ， 若編輯正在處理這篇文章 ， 讀者就不能作讀操作 ， 編輯與編輯的工作也是互斥的 ， 試用信號燈及 P、 V操作寫出讀者與編輯之間協(xié)同工作的程序描述 。 177 178 解： mutex:用于讀者與編輯、編輯與編輯的互斥信號燈，初值為 1； mutex1:用于對 couter操作的互斥的信號燈，初值為 1。 179 結(jié)構(gòu)化的同步 /互斥機構(gòu) —管程 （ Monitor） 雖然信號量是一種既方便又有效的進程同步機制，但每個要訪問臨界資源的進程都必須自備