《《處理器管理》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《處理器管理》PPT課件.ppt（92頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第2章處理器管理 主講 周文強課程 操作系統(tǒng) 本章內(nèi)容 2 4進程同步機制2 5進程通信2 6處理機調(diào)度 2 4進程同步機制 操作系統(tǒng)中引入進程后 雖然改善了資源的利用率 提高了系統(tǒng)的吞吐量 但是 由于進程的異步性 也會給系統(tǒng)造成混亂 因此 必須有效地協(xié)調(diào)各個并發(fā)進程間的關(guān)系 從而使它們能正確的執(zhí)行 本節(jié)主要介紹進程的同步與互斥的實現(xiàn)機制 2 4 1進程的并發(fā)性 在并發(fā)運行的系統(tǒng)中 若干個作業(yè)可以同時運行 而每個作業(yè)又需要有多個進程協(xié)作完成 在這些同時存在的進程間具有并發(fā)性 稱之為 并發(fā)進程 進程間的關(guān)系可以分為 1 資源共享關(guān)系2 相互合作關(guān)系 1 資源共享關(guān)系 系統(tǒng)中的某些進程需要訪問共同的資源 即當(dāng)一個進程訪問共享資源時 訪問該共享資源的其他進程必須等待 當(dāng)這個進程使用完后 其他進程才能使用 這時要求進程應(yīng)互斥地訪問共享資源 2 相互合作關(guān)系 系統(tǒng)中的某些進程之間存在相互合作的關(guān)系 即一個進程執(zhí)行完后 另一個進程才能開始 否則 另一個進程不能開始 這時就要保證相互合作的進程在執(zhí)行次序上要同步 1 臨界資源 通常一次僅允許一個進程使用的資源稱為臨界資源 同時 也將一個進程訪問的這種臨界資源的那段程序代碼稱為臨界區(qū) 操作系統(tǒng)中的進程就緒隊列就是一種在一個時刻只能允許一個進程訪問的臨界資源 所以 進程的互斥就是兩個進程不能同時進入訪問同一臨界資源的臨界區(qū) 2 臨界區(qū) criticalsection 臨界區(qū)是進程執(zhí)行程序中的對臨界資源訪問的那一段程序 這段程序的進入執(zhí)行 需要有一定的原則來協(xié)調(diào) 例如 1 有若干進程都欲進入臨界區(qū) 它們不能互相阻塞 使得誰也進不了臨界區(qū) 應(yīng)當(dāng)在有限時間內(nèi)讓一個進程進入臨界區(qū) 2 每次至多有一個進程進入臨界區(qū) 并且在臨界區(qū)中只能停留有限的時間 3 進程同步 多個相關(guān)進程在執(zhí)行次序上的協(xié)調(diào) 這些進程相互合作 在一些關(guān)鍵點上需要相互等待或相互通信 通過臨界區(qū)可以協(xié)調(diào)進程間相互合作的關(guān)系 這就是進程同步 4 進程互斥 當(dāng)一個進程進入臨界區(qū)使用臨界資源時 另一個進程必須等待 當(dāng)占用臨界資源的進程退出臨界區(qū)后 另一個進程才被允許使用臨界資源 通過臨界區(qū)協(xié)調(diào)進程間資源共享的關(guān)系 就是進程互斥 2 4 3進程同步機制應(yīng)遵循的原則 1 空閑讓進 當(dāng)無進程處于臨界區(qū)時 允許一個進程進入 2 忙則等待 當(dāng)有進程在臨界區(qū)中 其他欲進入臨界區(qū)的進程必須等待 3 有限等待 對要求進入臨界區(qū)的進程 應(yīng)在有限時間內(nèi)讓其進入 避免 死等 4 讓權(quán)等待 臨界區(qū)讓出 必須立即釋放處理器 讓等待進程進入 避免 忙等 12 鎖操作 1 測試鎖位的值 lock unlock2 若原來的值是為 0 將鎖位置為 1 占用該資源 3 若原來值是為 1 該資源已被別人占用 則轉(zhuǎn)到1 開鎖操作 進程使用完資源后 將鎖位置為 0 稱為開鎖操作 2 4 4進程同步機制 鎖 13 PAA lock key S unlock key S GotoA可能導(dǎo)致不公平現(xiàn)象 PBB lock key S unlock key S GotoB 鎖操作的缺點 14 1 循環(huán)測定鎖定位 將損耗較多的CPU時間 2 影響系統(tǒng)可靠性和執(zhí)行效率 并可能導(dǎo)致不公平現(xiàn)象 2 4 5進程同步機制 信號量 信號量是一種特殊變量 他用來表示系統(tǒng)中資源的使用情況 而整型信號量就是一個整型變量 當(dāng)值大于0時 表示系統(tǒng)中對應(yīng)可用資源的數(shù)目 當(dāng)值小于0時 其絕對值表示因該類資源而被等待的進程數(shù)目 當(dāng)值等于0時 表示系統(tǒng)中對應(yīng)資源已經(jīng)用完 并且沒有因該類資源而被等待的進程 P V原語 信號量的初值只能由P V原語操做P passerenV verhoogP操作 申請資源操作sem減1若sem減1后仍大于1或等于零 則P返回 進程繼續(xù) 若sem減1后小于零 則該進程阻塞轉(zhuǎn)等待隊列中 V操作 釋放資源操作 sem加1若sem加1后結(jié)果大于1 則V停止操作 該進程返回調(diào)用處 繼續(xù)執(zhí)行 若sem加1后小于或等于零 則該進程轉(zhuǎn)就緒隊列 同時進程調(diào)試選取一個等待隊列中的進程轉(zhuǎn)運行 P V操作必須用原語實現(xiàn) 18 用信號量實現(xiàn)兩并發(fā)進程PA PB互斥的描述如下 設(shè)sem為互斥信號量 其取值范圍為 1 0 1 其中sem 1表示進程PA和PB都未進入S的臨界區(qū) sem 0表示進程PA或PB已進入S的臨界區(qū) sem 1進程PA和PB中 一個進程已進入臨界區(qū) 另一進程等待進入 描述 PA PB P sem P sem V sem V sem 2 4 6用P V原語實現(xiàn)進程互斥 sem 1 進程A想使用臨界區(qū) 進程A執(zhí)行P操作 sem 0 進程B執(zhí)行P操作 進程B想使用臨界區(qū) sem 1 進程B被阻塞 進程A使用臨界區(qū)完 進程A執(zhí)行V操作 sem 0 進程B轉(zhuǎn)入阻塞隊列中 20 PAA P sem V sem GotoA會導(dǎo)致不公平現(xiàn)象嗎 PBB P sem V sem GotoB 放水果問題 有一個水果盤 只能放入1個水果 父親每次放1個蘋果供兒子吃 或者放1個橘子供女兒吃 給出父親 兒子 女兒的算法描述 放水果問題 需要三個信號量s1 s2 s3分別代表需要盤子是否為空 是否可以有蘋果 是否橘子 父親進程 A P s1 if放蘋果thenV s2 elseV s3 gotoA s1 1 s2 0 s2 0 放水果問題 兒子進程 B P s2 取走蘋果V s1 gotoB 女兒進程C P s3 取走蘋果V s1 gotoC 用P V原語操作實現(xiàn)進程同步的方法 為各并發(fā)進程設(shè)置私用信號量為私用信號量賦初值利用P V原語和私用信號量規(guī)定各進程的執(zhí)行順序 2 4 7用P V原語操作實現(xiàn)同步 PA Pp buffer deposit data remove data 例進程PA和PB共享緩沖隊列發(fā)送和接收數(shù)據(jù) 26 在PA至少送一塊數(shù)據(jù)入一個緩沖區(qū)之前 PB不可能從緩沖區(qū)中取出數(shù)據(jù) 假定數(shù)據(jù)塊長等于緩沖區(qū)長度 PA往緩沖隊列發(fā)送數(shù)據(jù)時 至少有一個緩沖區(qū)是空的 由PA發(fā)送的數(shù)據(jù)塊在緩沖隊列中按先進先出方式排列 解 設(shè)bufempty為進程PA的私用信號量 buffull為進程PB的私用信號量 令bufempty的初始值為n n為緩沖隊列的緩沖區(qū)個數(shù) buffull的初值為0 PA deposit data beginlocalxP bufempty 按FIFO選空緩沖區(qū)buf x buf x databuf x 置滿標(biāo)記V buffull end PB remove data beginlocalxP buffull 按FIFO選裝滿數(shù)據(jù)緩沖區(qū)buf x data buf x buf x 置空標(biāo)記V bufempty end 2 4 8利用信號量實現(xiàn)進程同步與互斥 生產(chǎn)者 消費問題消費者 系統(tǒng)中使用某一類資源的進程稱為該資源的消費者 生產(chǎn)者 釋放同類資源的進程稱為該資源的生產(chǎn)者 它們之間滿足 消費者想接收數(shù)據(jù)時 有界緩沖區(qū)中至少有一個單元是滿的 生產(chǎn)者想發(fā)送數(shù)據(jù)時 有界緩沖區(qū)中至少有一個單元是空的 生產(chǎn)者 消費者問題是同步關(guān)系 當(dāng)有進程在寫數(shù)據(jù)時 如生產(chǎn)者進程 則同時不允許對該緩沖區(qū)進行讀操作 如消費者進程 故有界緩沖區(qū)是臨界資源 進程必須互斥訪問 生產(chǎn)者 消費者問題同時也具有互斥關(guān)系 設(shè)信號量mutex 用于訪問緩沖區(qū)時的互斥 初值是1avail 生產(chǎn)者進程的私用信號量 表示有界緩沖區(qū)中的空單元數(shù) 初值為n full 為消費者進程的私用信號量 表示緩沖區(qū)中非空單元數(shù) 初值為0 avail full n consumer data beginP full P mutex 取緩沖區(qū)某單元數(shù)據(jù)V avail V mutex end producer data beginP avail P mutex 送數(shù)據(jù)入緩沖區(qū)某單元V full V mutex end 每個進程中各個P操作的次序是重要的 先檢查資源數(shù)目 再檢查是否互斥 否則可能死鎖 分析 P操作的順序 很重要 P操作的順序不當(dāng)會產(chǎn)生死鎖 例 假定執(zhí)行順序如下 分析 當(dāng)full 0 mutex 1時 執(zhí)行順序 Consumer P mutex Consumer P full C阻塞 等待Producer發(fā)出的full信號Producer P avail Producer P mutex P阻塞 等待Consumer發(fā)出的avail信號思考 還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎 發(fā)生死鎖 2 4 9利用信號量實現(xiàn)進程同步的方法 1 使用PV操作的規(guī)則 1 分清哪些是互斥問題 哪些是同步問題 2 對于互斥問題要設(shè)置互斥信號量 不管有互斥關(guān)系的進程有幾個或幾類 互斥信號量的個數(shù)只與臨界資源的種類有關(guān) 3 對于同步問題要設(shè)置同步信號量 通常同步信號量的個數(shù)與參與同步的進程種類有關(guān) 4 在每個進程中由于實現(xiàn)互斥的PV操作必須成對出現(xiàn) 用于實現(xiàn)同步的PV操作也必須成對出現(xiàn) 必須先執(zhí)行對同步信號量的P操作 再執(zhí)行對互斥信號量的P操作 2 同步互斥問題的解題步驟 1 確定進程 包括進程的數(shù)量 進程的工作內(nèi)容 可以用流程圖描述 2 確定同步互斥關(guān)系 根據(jù)使用的是臨界資源 還是處理的前后關(guān)系 來確定互斥與同步 然后確定信號的個數(shù) 含義 以及對信號量的PV操作 3 用C語言描述同步或互斥算法 2 5進程通信 進程通信是指進程間的信息交換 進程通信所交換的信息量少則一個數(shù)值或狀態(tài) 多則成千上萬個字節(jié) 根據(jù)通信的機制不同將進程通信分為低級通信和高級通信 低級通信 進程的同步和互斥 進程的同步和互斥稱為低級通信 缺點 1 效率低 一次發(fā)送的信息量比較少 2 信號量機制主要依靠進程來控制 用戶使用不方便 高級通信 高級通信是指用戶直接利用操作系統(tǒng)提供的一組通信命令 高效地傳送大量數(shù)據(jù)的一種通信方式 高級通信機制分為3大類 1 共享存儲器系統(tǒng)2 消息傳遞系統(tǒng)3 管道通信系統(tǒng) 2 5 1共享存儲器系統(tǒng) 在共享存儲器系統(tǒng)中 相互通信的進程共享某些數(shù)據(jù)結(jié)構(gòu)或存儲區(qū) 進程之間能夠通過它們進程通信 共享存儲器系統(tǒng)分為2種方式 1 共享數(shù)據(jù)結(jié)構(gòu)方式2 共享存儲區(qū)方式 1 共享數(shù)據(jù)結(jié)構(gòu)方式 在這種通信方式下 相互通信的進程共用某些數(shù)據(jù)結(jié)構(gòu) 并通過這些數(shù)據(jù)結(jié)構(gòu)交換信息 這種方式與信號量機制相比 并沒有發(fā)生太大的變化 比較低效 復(fù)雜 只適合于傳送少量的數(shù)據(jù) 2 共享存儲區(qū)方式 這種通信方式是在存儲器中劃出一塊共享存儲區(qū) 相互通信的進程可以通過對共享存儲區(qū)中的數(shù)據(jù)進行讀或?qū)憗韺崿F(xiàn)通信 這種方式效率高 可以傳送較多的數(shù)據(jù) 2 5 2消息傳遞系統(tǒng) 在消息傳遞信息中 進程間的數(shù)據(jù)交換是以消息為單位進行的 用戶直接利用系統(tǒng)中提供的一組通信命令 原語 進程通信 消息傳遞系統(tǒng)成為最常用的高級通信方式 優(yōu)點 1 工作效率提高2 簡化了程序編制的復(fù)雜性 方便用戶的使用 1 直接通信方式 發(fā)送進程使用發(fā)送原語直接將消息發(fā)送給接收進程 并將它掛在接收進程的消息緩沖隊列上 接收接收進程使用接收原語從消息緩沖隊列中讀取消息 通常系統(tǒng)提供兩條通信原語 發(fā)送原語 Send Receiver message 接收原語 Receive Sender message 例如原語Send P2 M 表示將消息M發(fā)送給接收進程P2 而原語Receive P1 M 則是表示接收由進程P1發(fā)送來的消息M 2 間接通信方式 發(fā)送進程與接收進程通過中間實體 信箱來完成通信 既可以實現(xiàn)實時通信 有可以實現(xiàn)非實時通信 接收進程使用接收原語從信箱中取出消息 1 信箱通信的操作 系統(tǒng)為信箱通信提供了若干條操作原語 包括創(chuàng)建信箱原語 撤銷信箱原語 發(fā)送原語 接收原語等 1 信箱的創(chuàng)建與撤銷 進程可以利用信箱創(chuàng)建原語來建立一個新信箱 創(chuàng)建進程應(yīng)給出信箱的名字 信箱屬性等 當(dāng)信箱所屬進程不再需要該信箱時 可用信箱撤銷原語來撤銷信箱 2 消息的發(fā)送與接收 相互通信的進程利用系統(tǒng)提供的下述通信原語來實現(xiàn)消息的發(fā)送與接收 Send mailbox message 將一個消息發(fā)送到指定信箱Receive mailbox message 從指定信箱中接收一個消息 2 消息的分類 消息可以由操作系統(tǒng)創(chuàng)建 也可以由用戶創(chuàng)建 創(chuàng)建者是信箱的擁有者 信箱可以分為3類 1 私用信箱 用戶進程可以為自己建立一個新信箱 并作為進程的一部分信箱的擁有者有權(quán)從信箱中讀取信息 其他用戶只能將自己的消息發(fā)送到該信箱中 當(dāng)擁有該信箱的進程終止時 信箱也隨之消失 2 公用信箱 它由操作系統(tǒng)創(chuàng)建 并提供給系統(tǒng)中所有核準(zhǔn)的用戶進程使用 核準(zhǔn)的進程既可以把消息發(fā)送到該信箱 有可以從信箱中取出發(fā)送給本人的消息 通常 公用信箱在系統(tǒng)運行期間始終存在 3 共享信箱 它實際上是某種進程創(chuàng)建的私有信箱 在創(chuàng)建時或創(chuàng)建后 又指明它是可以共享的 同時指出共享進程 用戶 的名字 此時就成為共享信箱 信箱的擁有者和共享者 都有權(quán)從信箱中取走發(fā)送給本人的消息 3 通信進程間的關(guān)系 當(dāng)利用信箱通信時 發(fā)送進程與接收進程存在下列關(guān)系 1 一對一關(guān)系 在一個發(fā)送進程和一個接收進程之間建立一條專用的通信通道 使它們之間的通信不受其他進程的影響 2 多對一關(guān)系 允許提供服務(wù)的一個接收進程與多個用戶發(fā)送進程之間進行通信 也稱為客戶 服務(wù)器方式 3 一對多關(guān)系 允許一個發(fā)送進程與多個接收進程進行通信 使發(fā)送進程可以用廣播形式 向一組或全部接收者發(fā)送消息 4 多對多關(guān)系 允許建立一個公用信箱 讓多個進程既可以把消息發(fā)送到該信箱 又可以從信箱中取出發(fā)送給本人的消息 2 5 3管道通信系統(tǒng) 管道是指連接讀進程和寫進程的 用于實現(xiàn)它們之間通信的共享文件 向管道提供輸入的發(fā)送進程 寫進程 以字符流的形式間大量數(shù)據(jù)送入管道 而接收管道輸出的接收進程 讀進程 可以從管道中接收數(shù)據(jù) 由于發(fā)送進程和接收進程是利用管道進行通信的 故稱為管道通信方式 2 6處理機調(diào)度 一個作業(yè)從提交開始直到完成 往往要經(jīng)歷三級調(diào)度 即作業(yè)調(diào)度 高級調(diào)度 進程調(diào)度 低級調(diào)度 和中級調(diào)度 1 作業(yè)調(diào)度是從后備作業(yè)隊列中選擇出若干個作業(yè) 為它們分配必要的資源 將它們調(diào)入主存 為它們建立進程 使之成為就緒進程 2 進程調(diào)度是從主存就緒隊列上選擇哪個進程獲得處理器資源 讓進程運行 56 功能 按照一定調(diào)度算法從就緒隊列中選擇一個新的進程投入運行 入口信息 可省 進程調(diào)度 2 6 1進程調(diào)度算法的選取原則 選擇調(diào)度算法的原則有面向用戶的 也有面向系統(tǒng)的 1 面向用戶的原則 1 周轉(zhuǎn)時間短 2 相應(yīng)時間快 3 截止時間有保證 4 優(yōu)先權(quán)原則 計算公式 周轉(zhuǎn)時間 完成時間 到達(dá)時間平均周轉(zhuǎn)時間 每個進程的周轉(zhuǎn)時間之和 進程個數(shù)帶權(quán)周轉(zhuǎn)時間 進程的周轉(zhuǎn)時間 系統(tǒng)為進程提供的實際服務(wù)時間平均帶權(quán)周轉(zhuǎn)時間 所有進程的帶權(quán)周轉(zhuǎn)世間之和 進程個數(shù) 2 面向系統(tǒng)的原則 1 系統(tǒng)吞吐量高 2 處理器利用率高 3 各類資源的平衡利用 2 6 2常用的進程調(diào)度算法 算法選擇的合理性 將決定進程調(diào)度的優(yōu)劣 它要解決兩個問題 第一選擇哪個進程執(zhí)行進程調(diào)度 第二個選中某個進程 如何給它分配處理器 該進程能占用處理器多久 第一個問題是選擇進程調(diào)度算法 第二個問題是選擇進程的調(diào)度方式 1 先來先服務(wù)調(diào)度算法 FCFS按照進程進入就緒隊列的先后順序選擇可以占用處理器的進程 這是一種不可搶占方式的調(diào)度算法 優(yōu)點 實現(xiàn)簡單 缺點 后來的進程等待CPU的時間較長 2 短執(zhí)行進程優(yōu)先算法 SPF就是從就緒隊列中選擇一個CPU執(zhí)行時間預(yù)期最短的進程 將處理器分配給它 優(yōu)點 較公平缺點 實現(xiàn)難度較大 因為要準(zhǔn)確預(yù)定下一個進程的CPU執(zhí)行周期是很困難的 3 最短剩余時間優(yōu)先調(diào)度算法 SRT是將CPU分配給需要最少時間來完成的進程 SRT充分照顧了剩余運行時間短的進程 4 時間片輪轉(zhuǎn)法 RR讓每個進程在就緒隊列中的等待時間與享受服務(wù)的時間成比例 在RR中 需要將CPU的處理時間分成固定大小的時間片 如果一個進程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時間片 但又未完成要求的任務(wù) 則它自行釋放自己所占有的CPU而排到就緒隊列的末尾 等待下一次調(diào)度 同時 進程調(diào)度程序又去調(diào)度當(dāng)前就緒隊列中的第一個進程 5 優(yōu)先權(quán)調(diào)度算法 HPF的核心是確定進程的優(yōu)先級 確定優(yōu)先級的方法可分為靜態(tài)法和動態(tài)法 靜態(tài)法根據(jù)進程的靜態(tài)特性 在進程開始執(zhí)行之前就確定它們的優(yōu)先級 一旦開始執(zhí)行之后就不能改變 動態(tài)法把進程的靜態(tài)特性和動態(tài)特性結(jié)合起來確定進程的優(yōu)先級 隨著進程的執(zhí)行過程 其優(yōu)先級不斷變化 基于靜態(tài)優(yōu)先級的調(diào)度算法 優(yōu)點 實現(xiàn)簡單 系統(tǒng)開銷小缺點 靜態(tài)優(yōu)先級一旦確定之后 直到執(zhí)行結(jié)束為止始終保持不變 從而系統(tǒng)效率較低 調(diào)度性能不高 現(xiàn)在的操作系統(tǒng)中 大多采用動態(tài)優(yōu)先級的調(diào)度策略 基于動態(tài)優(yōu)先級的調(diào)度算法 1 根據(jù)進程占有CPU時間的長短來決定 一個進程占有處理機的時間愈長 則在被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低 反之 其獲得調(diào)度的可能性就會越大 2 根據(jù)就緒進程等待CPU的時間長短來決定 一個就緒進程在就緒隊列中等待的時間越長 則它獲得調(diào)度選中的優(yōu)先級就越高 2 6 3作業(yè)調(diào)度 作業(yè)是指用戶在一次計算過程或者事務(wù)處理過程中 要求計算機系統(tǒng)所作工作的集合 作業(yè)調(diào)度是從后備作業(yè)隊列中選擇若干個作業(yè) 為它們分配必要的資源 將它們調(diào)入主存 為它們建立進程 使它們成為就緒進程的過程 這涉及到作業(yè)所處的狀態(tài) 作業(yè)調(diào)度以及調(diào)度算法 1 作業(yè)調(diào)度采用的數(shù)據(jù)結(jié)構(gòu) 為了管理和調(diào)度作業(yè) 系統(tǒng)為每個作業(yè)設(shè)置一個作業(yè)控制塊 JCB JCB是在作業(yè)進入系統(tǒng)時由SPOOLING系統(tǒng)為其建立的 其內(nèi)容由作業(yè)控制卡 說明書 中得到的 JCB是作業(yè)存在系統(tǒng)的標(biāo)志 作業(yè)進入系統(tǒng)時 則為之建立JCB 當(dāng)作業(yè)退出時 則其JCB也被撤銷 作業(yè)名 資源要求 資源使用情況 類型級別 優(yōu)先級 狀態(tài) 要求的運行時間 使用語言最遲完成時間 要求的主存量要求外設(shè)類型 臺數(shù)要求的文件量和輸出量 進入系統(tǒng)時間開始運行時間已運行時間主存地址外設(shè)臺號 控制方式作業(yè)類型 優(yōu)先數(shù) 作業(yè)控制表JCB SPOOLING系統(tǒng) SPOOLING又稱為外圍設(shè)備同時聯(lián)機操作 在SPOOLING系統(tǒng)中 多臺外圍設(shè)備通過通道或DMA器件和主機與外存連接起來 在硬盤中開辟一塊輸入 輸出井 并將多個用戶作業(yè)隨機的存儲提取 各用戶間互不干擾 系統(tǒng)中的輸入程序包含兩個獨立的過程 一個過程負(fù)責(zé)從外部設(shè)備把信息讀入緩沖區(qū) 另一個是寫過程 負(fù)責(zé)把緩沖區(qū)的信息送到外存輸入井中 2 作業(yè)調(diào)度與進程調(diào)度的關(guān)系 作業(yè)調(diào)度與進程調(diào)度的關(guān)系 3 常用的作業(yè)調(diào)度算法 作業(yè)調(diào)度程序要完成以下工作 1 按照某種調(diào)度算法從后備作業(yè)隊列中挑選作業(yè) 2 為選中的作業(yè)分配主存和外設(shè)資源 3 為選中的作業(yè)建立相應(yīng)的進程 4 構(gòu)造和填寫作業(yè)運行時所需的有關(guān)表格 5 作業(yè)結(jié)束時完成該作業(yè)的善后處理工作 如收回資源 輸出必要的信息 撤消該作業(yè)的全部進程 PCB 和作業(yè)控制塊JCB 調(diào)度原則 公平 合理 使用戶滿意提高系統(tǒng)資源利用率 如提高系統(tǒng)吞吐量作業(yè)調(diào)度算法的評價因素作業(yè)吞吐量 運行盡可能多的作業(yè) 充分利用資源 CPU忙 I O設(shè)備忙 對各作業(yè)公平 合理 使用戶滿意 執(zhí)行時間長短 等待時間等 1 選擇作業(yè)調(diào)度算法應(yīng)考慮的因素 2 常用的作業(yè)調(diào)度算法 FCFS按作業(yè)到達(dá)系統(tǒng)的先后次序進行調(diào)度 該算法優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè) 而不考慮作業(yè)運行時間的長短 1 先來先服務(wù)調(diào)度算法 先來先服務(wù)調(diào)度算法 由此 此作業(yè)流的平均周轉(zhuǎn)時間為T 2 0 1 5 1 2 1 5 4 1 55h 此作業(yè)流的平均周轉(zhuǎn)時間為W 1 0 3 0 6 0 3 75 4 3 4375h 注 通過以上分析 顯然 這種算法容易實現(xiàn) 但效率很低 2 短作業(yè)優(yōu)先調(diào)度算法 SJF總是從作業(yè)的后備隊列中挑選運行時間最短的作業(yè) 作為下 個調(diào)度運行的對象 短作業(yè)優(yōu)先調(diào)度算法 由此 此作業(yè)流的平均周轉(zhuǎn)時間為T 2 0 2 1 0 7 1 0 4 1 45h 此作業(yè)流的平均周轉(zhuǎn)時間為W 1 0 4 2 3 5 2 5 4 2 8h 注 通過以上分析 雖然這種算法易于實現(xiàn) 且效率也比較高 但未考慮長作業(yè)的利益 先來先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法 FCFS和SPF存在的問題 先來先服務(wù)調(diào)度算法只考慮了作業(yè)的等待時間 而忽略了作業(yè)的運行時間 對短作業(yè)不利 短作業(yè)優(yōu)先調(diào)度算法只考慮了作業(yè)運行時間的長短 而忽略了作業(yè)的等待時間 對運行時間長的作業(yè)不利 因為如果始終有短作業(yè)進入系統(tǒng) 則較長作業(yè)會長時間得不到調(diào)度 3 響應(yīng)比高者優(yōu)先調(diào)度算法 HRRN是在每次調(diào)度作業(yè)運行時 先計算后備作業(yè)隊列中每個作業(yè)的響應(yīng)比 然后挑選響應(yīng)比最高者投入運行 HRRN既考慮了作業(yè)的等待時間又考慮了作業(yè)的運行時間的調(diào)度算法 響應(yīng)比高者優(yōu)先調(diào)度算法 R 作業(yè)的響應(yīng)時間 作業(yè)的運行時間作業(yè)的響應(yīng)時間 作業(yè)的等待時間 作業(yè)的運行時間作業(yè)的響應(yīng)比為 R 1 作業(yè)的等待時間 作業(yè)的運行時間 一個作業(yè)的響應(yīng)比隨著等待時間的增加而提高 在相同等待時間的情況下 短作業(yè)優(yōu)先 而對于相同運行時間的作業(yè) 等待時間長的作業(yè)優(yōu)先運行 響應(yīng)比高者優(yōu)先調(diào)度算法 由于作業(yè)1的開始時間是5 00 而其余作業(yè)均未到達(dá) 故先運行作業(yè)1 當(dāng)作業(yè)1運行完畢 計算后備隊列中作業(yè)2 3 4的響應(yīng)比 按照以上的定義和計算公式 計算如下 作業(yè)2 R 60 30 30 3作業(yè)3 R 30 12 12 3 5作業(yè)4 R 24 24 24 2 可見 作業(yè)3的響應(yīng)比最高 選擇作業(yè)3運行 故表2 3中作業(yè)3的開始時間為作業(yè)1的完成時間 即7 00 當(dāng)作業(yè)3運行完畢 計算后備隊列中作業(yè)2 4的響應(yīng)比 計算如下 作業(yè)2 R 72 30 30 3 4作業(yè)4 R 36 24 24 2 5顯然 這次應(yīng)該選擇作業(yè)2 故表2 3中作業(yè)2的開始時間為作業(yè)3的完成時間 即7 12 最后運行作業(yè)4 故作業(yè)運行的次序為 1 3 2 4 由此 此作業(yè)流的平均周轉(zhuǎn)時間為T 2 0 1 7 0 7 1 5 4 1 475h 此作業(yè)流的平均周轉(zhuǎn)時間為W 1 0 3 4 3 5 3 75 4 2 9125注 通過以上分析 這種算法既考慮了作業(yè)的等待時間 也考慮了作業(yè)的運行時間 是一種比較理想的調(diào)度算法 但這種算法復(fù)雜 而且需要動態(tài)計算某一作業(yè)完成時刻后備隊列中每個作業(yè)的響應(yīng)比 增加了系統(tǒng)的開銷 4 優(yōu)先權(quán)調(diào)度算法 根據(jù)作業(yè)的優(yōu)先數(shù)調(diào)度作業(yè)進入系統(tǒng)運行 為每個作業(yè)確定一個優(yōu)先數(shù) 資源能滿足且優(yōu)先數(shù)高的作業(yè)優(yōu)先被選中 當(dāng)幾個作業(yè)有相同的優(yōu)先數(shù)時 對這些具有相同優(yōu)先數(shù)的作業(yè)再按照先來先服務(wù)原則進行調(diào)度 實例解析 例 系統(tǒng)中有四個作業(yè)同時到達(dá) 它們的運行時間和優(yōu)先數(shù)如表2 9所示 若使用優(yōu)先權(quán)調(diào)度算法時 作業(yè)的平均周轉(zhuǎn)時間為多少 分析 優(yōu)先權(quán)調(diào)度算法中規(guī)定作業(yè)的優(yōu)先數(shù)越高 則該作業(yè)在運行的次序中越靠前 所以本例四個作業(yè)的運行次序為1 3 4 2 實例解析 解 由表2 9作業(yè)的優(yōu)先數(shù)得作業(yè)運行次序為1 3 4 2 故該批作業(yè)的平均周轉(zhuǎn)時間為 T 3 3 7 3 7 2 3 7 2 5 4 42 4 10 5 5 均衡調(diào)度算法 這種調(diào)度算法根據(jù)作業(yè)對資源的要求進行分類 作業(yè)調(diào)度從各類作業(yè)中挑選 盡可能地使使用不同資源的作業(yè)同時執(zhí)行 這樣不僅可以使系統(tǒng)中的不同類型的資源都在被使用 而且可以減少作業(yè)等待使用相同資源的時間 從而加快作業(yè)的執(zhí)行 有的系統(tǒng)還對每一類中的各作業(yè)確定優(yōu)先數(shù) 作業(yè)調(diào)度時在每類作業(yè)中再按優(yōu)先數(shù)高者優(yōu)先的調(diào)度原則選擇作業(yè) 這樣 既能使各類作業(yè)都得到照顧 又能照顧同類作業(yè)中的緊迫作業(yè)