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