操作系統(tǒng)教程補(bǔ)充作業(yè)管理實(shí)用教案

1、2.7.2 作業(yè)狀態(tài) 批處理作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行(ynxng)結(jié)束，一般要經(jīng)歷提交、收容、運(yùn)行(ynxng)、完成四個(gè)階段，而交互式作業(yè)要經(jīng)歷提交、運(yùn)行(ynxng)、完成三個(gè)階段。 1提交狀態(tài) 批處理作業(yè)從輸入設(shè)備進(jìn)入外存儲(chǔ)器的過(guò)程為其提交狀態(tài)。輸入方式可以是脫機(jī)或偽脫機(jī)輸入。處于提交狀態(tài)的作業(yè)，因它的信息尚未全部進(jìn)入系統(tǒng)，不受作業(yè)管理調(diào)度。而交互型作業(yè)經(jīng)用戶終端輸入后，直接進(jìn)入內(nèi)存儲(chǔ)器，準(zhǔn)備接受進(jìn)程調(diào)度。第1頁(yè)/共30頁(yè)第一頁(yè)，共31頁(yè)。 2收容狀態(tài) 當(dāng)批處理作業(yè)的全部信息進(jìn)入外存后，系統(tǒng)(xtng)將它們加入后備作業(yè)隊(duì)列，為每個(gè)作業(yè)建立一個(gè)作業(yè)控制表（JCT），記錄該作業(yè)的資源請(qǐng)求、運(yùn)行

2、狀態(tài)等信息。 3運(yùn)行狀態(tài) 作業(yè)被作業(yè)調(diào)度程序選中，并分配到它需要的資源時(shí)，調(diào)入內(nèi)存運(yùn)行，即作業(yè)進(jìn)入運(yùn)行狀態(tài)。作業(yè)管理程序?qū)雌渥鳂I(yè)步組織的順序依次為每個(gè)作業(yè)步建立一個(gè)主進(jìn)程，并為它分配必要的資源交給進(jìn)程調(diào)度模塊管理。每個(gè)主進(jìn)程又可以建立若干子進(jìn)程來(lái)實(shí)現(xiàn)主進(jìn)程承擔(dān)的工作。這些子進(jìn)程有的正占用CPU處于執(zhí)行狀態(tài)，有的阻塞等待某事件，有的處于就緒狀態(tài)。從宏觀上看，該作業(yè)處于運(yùn)行狀態(tài)。第2頁(yè)/共30頁(yè)第二頁(yè)，共31頁(yè)。 4完成狀態(tài) 當(dāng)作業(yè)運(yùn)行結(jié)束或非正常結(jié)束而停止運(yùn)行時(shí)，作業(yè)進(jìn)入完成狀態(tài)。作業(yè)調(diào)度(diod)程序收回與它有關(guān)的主進(jìn)程和子進(jìn)程占用的全部資源，撤消該作業(yè)的作業(yè)控制表JCT。 批處理作業(yè)狀態(tài)

3、轉(zhuǎn)換過(guò)程和交互式作業(yè)狀態(tài)轉(zhuǎn)換過(guò)程分別如圖2-57(a)、2-57(b)所示。第3頁(yè)/共30頁(yè)第三頁(yè)，共31頁(yè)。圖2-57 作業(yè)狀態(tài)轉(zhuǎn)換(zhunhun)(a) 批處理系統(tǒng)作業(yè)狀態(tài)轉(zhuǎn)換(zhunhun)；(b) 交互式作業(yè)狀態(tài)轉(zhuǎn)換(zhunhun)(b)(a)執(zhí)行阻塞就緒收容提交運(yùn)行完成執(zhí)行阻塞就緒提交運(yùn)行完成第4頁(yè)/共30頁(yè)第四頁(yè)，共31頁(yè)。2.7.3 作業(yè)調(diào)度 作業(yè)調(diào)度是對(duì)批處理作業(yè)從收容到運(yùn)行狀態(tài)的轉(zhuǎn)變，所以批處理作業(yè)需要作業(yè)調(diào)度。而分時(shí)與實(shí)時(shí)作業(yè)是交互型作業(yè)，用戶提交給系統(tǒng)后直接進(jìn)入(jnr)內(nèi)存運(yùn)行，所以不需要進(jìn)行作業(yè)調(diào)度。 1作業(yè)調(diào)度功能 實(shí)現(xiàn)作業(yè)從收容到運(yùn)行的狀態(tài)變換，具體工作是按

4、照一定算法從后備隊(duì)列中選出作業(yè)，為其分配內(nèi)存等必要資源，創(chuàng)建進(jìn)程，掛到就緒隊(duì)列上，使該作業(yè)進(jìn)入(jnr)運(yùn)行狀態(tài)。第5頁(yè)/共30頁(yè)第五頁(yè)，共31頁(yè)。 2算法評(píng)價(jià)(pngji)與衡量標(biāo)準(zhǔn) 1) 確定調(diào)度算法的準(zhǔn)則 (1) 批處理系統(tǒng)側(cè)重于系統(tǒng)的吞吐量，所以選擇調(diào)度算法時(shí)應(yīng)該與此目標(biāo)一致； (2) CPU繁忙的作業(yè)與I/O繁忙的作業(yè)搭配進(jìn)行，以保持系統(tǒng)資源的均衡性； (3) 算法要盡可能易于實(shí)現(xiàn)。第6頁(yè)/共30頁(yè)第六頁(yè)，共31頁(yè)。 2) 作業(yè)調(diào)度性能(xngnng)的衡量 (1) 周轉(zhuǎn)時(shí)間Ti：作業(yè)從提交到完成所經(jīng)歷的時(shí)間，是等待時(shí)間與運(yùn)行時(shí)間之和。 (2) 帶權(quán)周轉(zhuǎn)時(shí)間Wi：作業(yè)周轉(zhuǎn)時(shí)間Ti與作

5、業(yè)運(yùn)行時(shí)間Tsi之比。Wi=Ti/Tsi第7頁(yè)/共30頁(yè)第七頁(yè)，共31頁(yè)。 (3) 平均周轉(zhuǎn)時(shí)間T：是n個(gè)作業(yè)運(yùn)行時(shí)間的平均衡量尺度，是整個(gè)系統(tǒng)(xtng)的一個(gè)指標(biāo)和用戶追求的目標(biāo)，個(gè)別用戶不一定滿意，可以用它來(lái)衡量不同調(diào)度算法對(duì)同一作業(yè)流的調(diào)度性能。 nTTnii/ )(1 作業(yè)平均周轉(zhuǎn)時(shí)間短，意味著這些作業(yè)從提交到結(jié)束（完成）在系統(tǒng)中滯留(zhli)時(shí)間短，資源利用率高，多數(shù)用戶比較滿意，總的是比較合理。 第8頁(yè)/共30頁(yè)第八頁(yè)，共31頁(yè)。 (4) 平均帶權(quán)周轉(zhuǎn)時(shí)間：是作業(yè)被延誤的平均衡量尺度，是系統(tǒng)及用戶關(guān)注的另一個(gè)調(diào)度性能指標(biāo)，可以(ky)用它來(lái)比較某一調(diào)度算法對(duì)不同作業(yè)流的調(diào)度性能

6、。nWWnii/ )(1W越大說(shuō)明(shumng)延遲越大，W1說(shuō)明(shumng)延遲影響越小。第9頁(yè)/共30頁(yè)第九頁(yè)，共31頁(yè)。 3單道批處理系統(tǒng)的調(diào)度算法 1) 先來(lái)先服務(wù)（FCFS）調(diào)度算法 先來(lái)先服務(wù)（FCFS）調(diào)度算法按照作業(yè)(zuy)提交的先后次序進(jìn)行調(diào)度，即優(yōu)先調(diào)度在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)(zuy)，而不管它要求運(yùn)行時(shí)間的長(zhǎng)短，如表2-1所示。表2-1 FCFS的作業(yè)(zuy)調(diào)度第10頁(yè)/共30頁(yè)第十頁(yè)，共31頁(yè)。 2) 最短作業(yè)優(yōu)先（SJF）調(diào)度算法 最短作業(yè)優(yōu)先（SJF）調(diào)度算法選擇要求(yoqi)運(yùn)行時(shí)間最短的作業(yè)優(yōu)先調(diào)度。對(duì)表2-1中的四個(gè)作業(yè)采用本算法，將得到14

7、32的調(diào)度順序，運(yùn)行情況如表2-2所示。表2-2 SJF的作業(yè)(zuy)調(diào)度第11頁(yè)/共30頁(yè)第十一頁(yè)，共31頁(yè)。 比較上述兩種調(diào)度算法可以看出，最短作業(yè)優(yōu)先的算法其調(diào)度性能要好一點(diǎn)。但是對(duì)于長(zhǎng)作業(yè)可能會(huì)產(chǎn)生這種情況，如果不斷有短作業(yè)進(jìn)來(lái)(jn li)，則該長(zhǎng)作業(yè)一直得不到運(yùn)行機(jī)會(huì)，這是最短作業(yè)優(yōu)先調(diào)度算法的缺點(diǎn)。第12頁(yè)/共30頁(yè)第十二頁(yè)，共31頁(yè)。 3) 響應(yīng)(xingyng)比高者優(yōu)先(HRN) 調(diào)度算法 為了克服上述缺點(diǎn)，可以采用一種稱為響應(yīng)(xingyng)比高者優(yōu)先的調(diào)度算法。響應(yīng)(xingyng)比Rp：)(1)(估計(jì)值運(yùn)行時(shí)間作業(yè)等待時(shí)間估計(jì)值運(yùn)行時(shí)間作業(yè)響應(yīng)時(shí)間Rp 所謂響應(yīng)

8、比高者優(yōu)先調(diào)度算法，就是在每調(diào)度一個(gè)作業(yè)投入運(yùn)行(ynxng)時(shí)，計(jì)算后備作業(yè)表中每個(gè)作業(yè)的響應(yīng)比，挑選響應(yīng)比最高者。從上述公式可以看出，一個(gè)作業(yè)的響應(yīng)比隨等待時(shí)間的增加而提高，因此在系統(tǒng)中的作業(yè)只要它等待足夠長(zhǎng)的時(shí)間，總有可能成為響應(yīng)比最高者而獲得運(yùn)行(ynxng)機(jī)會(huì)。第13頁(yè)/共30頁(yè)第十三頁(yè)，共31頁(yè)。 對(duì)于前面例子中同樣的一批作業(yè)，采用高響應(yīng)比優(yōu)先(yuxin)調(diào)度，可以得到1342的調(diào)度順序，運(yùn)行過(guò)程如表2-3所示，其中(a)、(b)、(c)、(d)分別為開(kāi)始調(diào)度每道作業(yè)時(shí)刻的情況，(e)為該批作業(yè)全部完成后的統(tǒng)計(jì)。表2-3(a) HRN的作業(yè)(zuy)調(diào)度時(shí)刻第14頁(yè)/共30頁(yè)第

9、十四頁(yè)，共31頁(yè)。表2-3(b) HRN的作業(yè)(zuy)調(diào)度時(shí)刻第15頁(yè)/共30頁(yè)第十五頁(yè)，共31頁(yè)。表2-3(c) HRN的作業(yè)(zuy)調(diào)度時(shí)刻第16頁(yè)/共30頁(yè)第十六頁(yè)，共31頁(yè)。表2-3(d) HRN的作業(yè)(zuy)調(diào)度時(shí)刻第17頁(yè)/共30頁(yè)第十七頁(yè)，共31頁(yè)。表2-3(e) HRN的作業(yè)(zuy)調(diào)度時(shí)刻第18頁(yè)/共30頁(yè)第十八頁(yè)，共31頁(yè)。 雖然這種算法的調(diào)度性能不如最短作業(yè)優(yōu)先調(diào)度算法好，但是它既照顧了作業(yè)到來(lái)的先后順序，又考慮了要求(yoqi)系統(tǒng)服務(wù)時(shí)間的長(zhǎng)短，所以它是先來(lái)先服務(wù)算法FCFS和短作業(yè)優(yōu)先算法SJF的較好折衷。該算法的缺點(diǎn)是較為復(fù)雜，每次調(diào)度時(shí)需對(duì)已經(jīng)到達(dá)的作業(yè)

10、進(jìn)行響應(yīng)比的計(jì)算。第19頁(yè)/共30頁(yè)第十九頁(yè)，共31頁(yè)。輪轉(zhuǎn)(lnzhun)法 （ ）算法是一種剝奪式的進(jìn)程調(diào)度算法，它依據(jù)公平服務(wù)的原則，將時(shí)間劃分成一個(gè)個(gè)的時(shí)間片（記為S），并以為單位，輪轉(zhuǎn)地為各個(gè)就緒進(jìn)程一次分配(fnpi)一個(gè)時(shí)間片。 以三個(gè)進(jìn)程為例，考察(koch)算法的執(zhí)行情況及其調(diào)度性能。設(shè) ，則有：04811151721252930第20頁(yè)/共30頁(yè)第二十頁(yè)，共31頁(yè)。 進(jìn)程首先執(zhí)行一個(gè)時(shí)間片并被剝奪，其周期(zhuq)所剩余的 放到以后執(zhí)行；執(zhí)行一個(gè)時(shí)間片后也被剝奪；的時(shí)值為 ，不足一個(gè)時(shí)間片。第二輪開(kāi)始，又由先執(zhí)行一個(gè)時(shí)間片后被剝奪； 這次只執(zhí)行 。至此，和的周期(zhuq

11、)已先后完成，故隨后連續(xù)個(gè)時(shí)間片都分給了，直至完成，在最后一個(gè)時(shí)間片里，只執(zhí)行了 。容易算出，該例的平均等待時(shí)間和平均周轉(zhuǎn)時(shí)間分別為：)(33.193/ )111730()(43/ )840(msTmsW第21頁(yè)/共30頁(yè)第二十一頁(yè)，共31頁(yè)。最高優(yōu)先級(jí)法 優(yōu)先級(jí)通常是用一個(gè)整型數(shù)來(lái)表示，稱為優(yōu)先數(shù)。對(duì)于不同(b tn)的系統(tǒng)，既可以用較大的數(shù)也可以用較小的數(shù)來(lái)表示較高的優(yōu)先級(jí)，這并無(wú)統(tǒng)一的規(guī)定。例如，中的優(yōu)先數(shù)的取值范圍為，且規(guī)定優(yōu)先數(shù)愈小其表示的優(yōu)先級(jí)愈高。 優(yōu)先級(jí)的設(shè)置分為靜態(tài)和動(dòng)態(tài)兩種方式： （）靜態(tài)設(shè)置方式 （）動(dòng)態(tài)設(shè)置方式第22頁(yè)/共30頁(yè)第二十二頁(yè)，共31頁(yè)。 設(shè)有五個(gè)就緒進(jìn)程，

12、它們(t men)各自的本次周期的長(zhǎng)度、初始優(yōu)先數(shù)及進(jìn)入就緒隊(duì)列的相對(duì)時(shí)刻如下所示：第23頁(yè)/共30頁(yè)第二十三頁(yè)，共31頁(yè)。在非剝奪的靜態(tài)設(shè)置方式下，執(zhí)行(zhxng)情況如下：0436526062在進(jìn)程執(zhí)行(zhxng)完時(shí)，已進(jìn)入就緒隊(duì)列，因其優(yōu)先級(jí)較高，故先于和之前執(zhí)行(zhxng)?？伤愕眠@些進(jìn)程的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間以 及平均帶權(quán)周轉(zhuǎn)時(shí)間分別為：)(575. 8)(96.39)(2 .27msTmsTmsW第24頁(yè)/共30頁(yè)第二十四頁(yè)，共31頁(yè)。第25頁(yè)/共30頁(yè)第二十五頁(yè)，共31頁(yè)。第26頁(yè)/共30頁(yè)第二十六頁(yè)，共31頁(yè)。第27頁(yè)/共30頁(yè)第二十七頁(yè)，共31頁(yè)。第28頁(yè)/共30頁(yè)第二十八頁(yè)，共31頁(yè)。時(shí)鐘頁(yè)面置換(zhhun)算法（Clock）當(dāng)發(fā)生缺頁(yè)中斷時(shí)，檢查表針指向的頁(yè)面。根據(jù)R位采取動(dòng)作(dngzu)：R0：淘汰頁(yè)面R1：清楚R位并向前移動(dòng)表針第29頁(yè)/共30頁(yè)第二十九頁(yè)，共31頁(yè)。感謝您的觀看(gunkn)！第30頁(yè)/共30頁(yè)第三十頁(yè)，共31頁(yè)。NoImage內(nèi)容(nirng)總結(jié)1。輸入方式可以是脫機(jī)或偽脫