[計(jì)算機(jī)硬件及網(wǎng)絡(luò)]第三章b調(diào)度算法(已修改)
2024-12-20 02:17 本頁面
【正文】 調(diào)度算法 進(jìn)程調(diào)度算法類型 ? 算法類型 簡單的調(diào)度算法 先來先服務(wù)算法 短作業(yè)（進(jìn)程）優(yōu)先 最高響應(yīng)比優(yōu)先 優(yōu)先權(quán)法 搶占式優(yōu)先權(quán) 非搶占式優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán) 多級(jí)反饋隊(duì)列算法 時(shí)間片輪轉(zhuǎn)法 FirstComeFirstServed （ FCFS）（作業(yè)／進(jìn)程）調(diào)度算法 FCFS是一種最簡單的調(diào)度算法，可用于作業(yè)或進(jìn)程調(diào)度。此算法的原則是 按照作業(yè)到達(dá)后備作業(yè)隊(duì)列 （或進(jìn)程進(jìn)入就緒隊(duì)列） 的先后次序來選擇作業(yè) （或進(jìn)程）。 FCFS算法屬于 非搶占方式 ，一旦一個(gè)進(jìn)程占有處理機(jī)，它就一直運(yùn)行下去，直到該進(jìn)程完成或者因等待某事件而不能繼續(xù)運(yùn)行時(shí)才釋放處理機(jī)。 FCFS算法易于實(shí)現(xiàn)，表面上很公平。 CPU 就緒隊(duì)列 1 2 3 后備隊(duì)列 內(nèi)存 例題 : 在單道環(huán)境下，某批處理有四道作業(yè)，已知他們的進(jìn)入系統(tǒng)的時(shí)刻、估計(jì)運(yùn)算時(shí)間如下： 作業(yè) 進(jìn)入時(shí)刻 (h) 運(yùn)行時(shí)間 (h) 1 2 3 4 用 FCFS算法計(jì)算作業(yè)的運(yùn)行情況、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間 平均周轉(zhuǎn)時(shí)間 T＝ 平均帶權(quán)周轉(zhuǎn)時(shí)間 T’＝ 作業(yè) 進(jìn)入時(shí)刻 運(yùn)行時(shí)間 開始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 1 2 3 4 帶權(quán)周轉(zhuǎn) 用 FCFS算法 :計(jì)算作業(yè)的運(yùn)行情況、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間 完成時(shí)間 = 開始時(shí)間 +運(yùn)行時(shí)間 周轉(zhuǎn)時(shí)間 = 完成時(shí)間 — 進(jìn)入時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間= 周轉(zhuǎn)時(shí)間 / 運(yùn)行時(shí)間 （ h） （ h） FCFS算法調(diào)度例 2 作業(yè)名 進(jìn)入時(shí)間 運(yùn)行時(shí)間（分） 需內(nèi)存量 KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用戶空間 100KB，并規(guī)定作業(yè)相應(yīng)程序裝入內(nèi)存連續(xù)區(qū)域，并不能被移動(dòng)，作業(yè)與進(jìn)程均采用FCFS算法 名 裝 入 內(nèi) 存 時(shí) 間 開 始 時(shí) 間 結(jié) 束 時(shí) 間 周 轉(zhuǎn) 時(shí) 間 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 A 8 : 0 6 8 : 0 6 8 : 4 8 4 2 4 2 /4 2 B 8 : 1 8 8 : 4 8 9 : 1 8 6 0 6 0 /3 0 D 8 : 3 6 9 : 1 8 9 : 4 2 6 6 6 6 /2 4 C 9 : 1 8 9 : 4 2 1 0 : 0 6 9 6 9 6 /2 4 E 9 : 1 8 1 0 : 0 6 1 0 : 1 8 9 6 9 6 /1 2有用戶空間 100KB，并規(guī)定作業(yè)相應(yīng)程序裝入內(nèi)存連續(xù)區(qū)域，并不能被移動(dòng)，作業(yè)與進(jìn)程均采用 FCFS算法 作業(yè)名 進(jìn)入時(shí)間 運(yùn)行時(shí)間（分） 需內(nèi)存量 KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 100K 15K 60K 10K 15K FCFS總結(jié)： FCFS根據(jù)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)間來分配中央處理機(jī) ，一旦一個(gè)進(jìn)程獲得了中央處理機(jī) ， 就一直運(yùn)行到結(jié)束 ， 先來先服務(wù)是非剝奪調(diào)度 。 這種調(diào)度從形式上講是公平的 ， 但它使 短作業(yè)要等待長作業(yè)的完成 ， 重要的作業(yè)要等待不重要作業(yè)的完成 。 從這個(gè)意義上講又是不公平的 。 先進(jìn)先出調(diào)度使響應(yīng)時(shí)間的變化較小 ， 因此它比其它大多數(shù)調(diào)度都可預(yù)測 。 由于這種調(diào)度方法不 能保證良好的響應(yīng)時(shí)間 ， 在處理交互式用戶時(shí)很少用這種方法 。 在當(dāng)今系統(tǒng)中 ， 先進(jìn)先出很少作為調(diào)度模式 ， 而是 常常嵌套在其它的調(diào)度模式中 。 例如 ， 許多調(diào)度模式根據(jù)優(yōu)先級(jí)將處理機(jī)分配給進(jìn)程 ， 但具有相同優(yōu)先級(jí)的進(jìn)程卻按先進(jìn)先出進(jìn)行分配 。 ／進(jìn)程優(yōu)先 (SJF/Shortest Process Next)調(diào)度算法 這種調(diào)度算法主要用于 作業(yè)調(diào)度 ，它從作業(yè)后備隊(duì)列中挑選所需運(yùn)行時(shí)間（估計(jì)值）最短的作業(yè)進(jìn)入主存運(yùn)行。這一算法有利于短作業(yè)，對(duì)長作業(yè)不利。采用 SJF有利于系統(tǒng)減少平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 作業(yè) 進(jìn)入時(shí)刻 (h) 運(yùn)行時(shí)間 (h) 1 2 3 4 例題： 用 SJF 算法計(jì)算作業(yè)的運(yùn)行情況、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間 該算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè) 作業(yè) 進(jìn)入時(shí)刻 運(yùn)行時(shí)間 開始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn) 1 2 3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1