sjf演算法例題
『壹』 以下五個作業，fcfs sjf hrrn三種調度演算法平均周轉時間，高響應比怎麼算
作業調度演算法 .
先來先服務（FCFS, First Come First Serve）是最簡單的調度演算法，按先後順序進行調度。
定義：
按照作業提交或進程變為就緒狀態的先後次序，分派CPU；
當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。
在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或進程出讓CPU。
適用場景：
比較有利於長作業，而不利於短作業。因為長作業會長時間占據處理機。
有利於CPU繁忙的作業，而不利於I/O繁忙的作業。
演算法實現原理圖：
2. 輪轉法(Round Robin)
輪轉法是讓每個進程在就緒隊列中的等待時間與享受服務的時間成正比例。
定義：
將系統中所有的就緒進程按照FCFS原則，排成一個隊列。
每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。
在一個時間片結束時，發生時鍾中斷。
調度程序據此暫停當前進程的執行，將其送到就緒隊列的末尾，並通過上下文切換執行當前的隊首進程。
進程可以未使用完一個時間片，就出讓CPU（如阻塞）。
時間片長度的確定：
時間片長度變化的影響
過長－>退化為FCFS演算法，進程在一個時間片內都執行完，響應時間長。
過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，響應時間長。
對響應時間的要求：T(響應時間)=N(進程數目)*q(時間片)
就緒進程的數目：數目越多，時間片越小
系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使響應時間，平均周轉時間和平均帶權周轉時間延長。
演算法實現原理圖：
3. 多級反饋隊列演算法(Round Robin with Multiple Feedback)
多級反饋隊列演算法是輪轉演算法和優先順序演算法的綜合和發展。
定義：
設置多個就緒隊列，分別賦予不同的優先順序，如逐級降低，隊列1的優先順序最高。每個隊列執行時間片的長度也不同，規定優先順序越低則時間片越長，如逐級加倍。
新進程進入內存後，先投入隊列1的末尾，按FCFS演算法調度；若按隊列1一個時間片未能執行完，則降低投入到隊列2的末尾，同樣按FCFS演算法調度；如此下去，降低到最後的隊列，則按「時間片輪轉」演算法調度直到完成。
僅當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程執行。如果進程執行時有新進程進入較高優先順序的隊列，則搶先執行新進程，並把被搶先的進程投入原隊列的末尾。
優點：
為提高系統吞吐量和縮短平均周轉時間而照顧短進程。
為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程。
不必估計進程的執行時間，動態調節
幾點說明：
I/O型進程：讓其進入最高優先順序隊列，以及時響應I/O交互。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞隊列。
計算型進程：每次都執行完時間片，進入更低級隊列。最終採用最大時間片來執行，減少調度次數。
I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的隊列，以免每次都回到最高優先順序隊列後再逐次下降。
為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先順序；時間片用完時，降低優先順序。
演算法實現原理圖：
4. 優先順序法（Priority Scheling）
優先順序演算法是多級隊列演算法的改進，平衡各進程對響應時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。
靜態優先順序：
作業調度中的靜態優先順序大多按以下原則確定：
由用戶自己根據作業的緊急程度輸入一個適當的優先順序。
由系統或操作員根據作業類型指定優先順序。
系統根據作業要求資源情況確定優先順序。
進程的靜態優先順序的確定原則：
按進程的類型給予不同的優先順序。
將作業的情態優先順序作為它所屬進程的優先順序。
動態優先順序：
進程的動態優先順序一般根據以下原則確定：
根據進程佔用有CPU時間的長短來決定。
根據就緒進程等待CPU的時間長短來決定。
5．短作業優先法（SJF, Shortest Job First）
短作業優先又稱為「短進程優先」SPN(Shortest Process Next)；這是對FCFS演算法的改進，其目標是減少平均周轉時間。
定義：
對預計執行時間短的作業（進程）優先分派處理機。通常後來的短作業不搶先正在執行的作業。
SJF的特點：
(1) 優點：
比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間；
提高系統的吞吐量；
(2) 缺點：
對長作業非常不利，可能長時間得不到執行；
未能依據作業的緊迫程度來劃分執行的優先順序；
難以准確估計作業（進程）的執行時間，從而影響調度性能。
SJF的變型：
「最短剩餘時間優先」SRT(Shortest Remaining Time)（允許比當前進程剩餘時間更短的進程來搶占）
「最高響應比優先」HRRN(Highest Response Ratio Next)（響應比R = (等待時間 + 要求執行時間) / 要求執行時間，是FCFS和SJF的折衷）
6. 最高響應比優先法(HRN，Highest Response_ratio Next)
最高響應比優先法是對FCFS方式和SJF方式的一種綜合平衡。FCFS方式只考慮每個作業的等待時間而未考慮執行時間的長短，而SJF方式只考慮執行時間而未考慮等待時間的長短。因此，這兩種調度演算法在某些極端情況下會帶來某些不便。HRN調度策略同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。
響應比R定義如下： R =(W+T)/T = 1+W/T
其中T為該作業估計需要的執行時間，W為作業在後備狀態隊列中的等待時間。每當要進行作業調度時，系統計算每個作業的響應比，選擇其中R最大者投入執行。這樣，即使是長作業，隨著它等待時間的增加，W / T也就隨著增加，也就有機會獲得調度執行。這種演算法是介於FCFS和SJF之間的一種折中演算法。由於長作業也有機會投入運行，在同一時間內處理的作業數顯然要少於SJF法，從而採用HRN方式時其吞吐量將小於採用SJF 法時的吞吐量。另外，由於每次調度前要計算響應比，系統開銷也要相應增加。
『貳』 進程調度演算法1——FCFS、SJF、HNNR
進程的調度方式有兩種： 非剝奪調度方式（非搶占式）和剝奪調度方式（搶占方式）。
非搶占式：只允許進程主動放棄處理機。如進程運行結束、異常結束或主動請求I/O阻塞。在運行的過程中即使有更緊迫的任務到達，當前進程依然會繼續使用處理機，直到該進程終止或主動要求進入阻塞態。
搶占式：當一個進程正在處理機上執行時，如果有一個更重要更緊迫的進程需要處理機，則立即暫停正在執行的進程，將處理機分配給更重要更緊迫的那個進程。
下面介紹適用於早期操作系統幾種進程調度的演算法
先來先服務（FCFS）：按照到達的先後順序調度，事實上就是等待時間越久的越優先得到服務。
下面表示按照先來先服務演算法的執行順序
計算進程的幾個衡量指標：
短作業優先演算法是非搶占式的演算法，但是也有搶占式的版本—— 最短剩餘時間優先演算法（STRN,Shortest Remaining Time Next） 。
用於進程的調度演算法稱為短進程優先調度演算法（SPF,Shortest Process First）。
短作業/進程優先調度演算法：每次調度時選擇當前已到達且運行時間最短的作業/進程.。
因為進程1最先達到，此時沒有其他線程，所以進程1先被服務。當進程1運行完後，進程2和3已經到達，此時進程3需要的運行時間比進程2少，所以進程3先被服務…
計算進程的幾個衡量指標：
最短剩餘時間優先演算法：每當有進程 加入就緒隊列改變時就需要調度 ，如果新到達的進程的所需的運行時間比當前運行的進程剩餘時間更短，則由新進程搶占處理機，當前運行進程重新回到就緒隊列。此外，當一個 進程完成時也需要調度 。
通過比較上面三組的平均周轉時間、平均帶權周轉時間和平均等待時間可以看出，短作業優先演算法可以減少進程的等待時間，對短作業有利。
高響應比優先演算法： 非搶占式的調度演算法 ，只有當前運行的進程主動放棄CPU時（正常/異常完成、或主動阻塞），才需要進行調度，調度時計算所有就緒進程的相應比，選響應比最高的進程上處理機。
響應比 = （等待時間 + 運行時間）/ 運行時間
上面的三種調度演算法一般適用於 早期的批處理系統 ，沒有考慮響應時間也不區分任務的緊急程度。因此對用戶來說交互性差。
如發現錯誤，請指正！！！
『叄』 SJF調度演算法
SJF調度演算法：最短作業優先演算法SJF（Shortest Job First )，SJF演算法以進入系統的作業所要求的CPU時間為標准，總選取估計計算時間最短的作業投入運行。
SJF 調度演算法優缺點：演算法易於實現。但效率不高，主要弱點是忽視了作業等待時間;會出現飢餓現象。SJF 調度演算法可證明為最佳的，這是因為對於給定的一組進程， SJF 演算法的平均等待時間最小。雖然 SJF 演算法最佳，但是它不能在短期CPU 調度層次上加以實現。因為沒有辦法知道下一個 CPU 區間的長度。
SJF演算法Gantt圖:
進程 區間時間
PI 6
P2 8
P3 7
P4 3
進程 P1 的等待時間是 3 ms，進程P2的等待時間為 16 ms，進程P3的等待時間為 9ms，進程P4的等待時間為 0ms。因此，平均等待時間為(3 + 16 + 9 +0) / 4 = 7 ms。
『肆』 FSFS ，SJF ，HRN演算法實例
1、設在單道批處理系統中有四道作業，它們提交的時刻及運行時間如下：
作業號 提交時刻（h） 運行時間（h）
1 8.0 1.0
2 8.5 0.5
3 9.0 0.2
4 9.1 0.1
請分別給出在演算法FCFS、SJF和HRN中這組作業的調度順序、平周轉時間和平均帶權周轉時間。
【解答】
FCFS演算法調度順序：1，2，3，4，作業運行情況如下表
作業號 開始時間 完成時間 周轉時間 帶權周轉時間
1 8.0 9.0 1.0 1.0
2 9.0 9.5 1.0 2.0
3 9.5 9.7 0.7 3.5
4 9.7 9.8 0.7 7.0
平均周轉時間T=(1.0+1.0+0.7+0.7)/4=0.85
平均帶權周轉時間W=(1.0+2.0+3.5+7.0)/4=3.375
SJF演算法調度順序：1，3，4，2，作業運行情況如下表
作業號 開始時間 完成時間 周轉時間 帶權周轉時間
1 8.0 9.0 1.0 1.0
2 9.3 9.8 1.3 2.6
3 9.0 9.2 0.2 1.0
4 9.2 9.3 0.2 2.0
平均周轉時間T=(1.0+1.3+0.2+0.2)/4=0.675
平均帶權周轉時間W=(1.0+2.6+1.0+2.0)/4=1.65
HRN演算法調度順序：1，2，4，3，作業運行情況如下表
作業號 開始時間 完成時間 周轉時間 帶權周轉時間
1 8.0 9.0 1.0 1.0
2 9.0 9.5 1.0 2.0
3 9.6 9.8 0.8 4.0
4 9.5 9.6 0.5 5.0
平均周轉時間T=(1.0+1.0+0.8+0.5)/4=0.825
平均帶權周轉時間W=(1.0+2.0+4.0+5.0)/4=3.0
『伍』 操作系統作業調度演算法求平均帶權周轉時間，急！！！！！！！！！！！
周轉時間：從作業提交算起，直到執行完畢這段時間
帶權周轉時間：作業的周轉時間T與系統為其提供服務的服務時間之比
平均XX時間即算這些時間的數學期望值
響應比優先權：（等待時間+要求服務時間）/要求服務時間=響應時間/要求服務時間
FCFS:
A[0-120]B[120-170]C[170-180]D[180-200]
平均周轉時間（120+170-50+180-60+200-110）/4
SJF分為搶占式和非搶占式
非搶占式：A[0-120]C[120-130]D[130-150]B[150-200]
平均周轉時間(120+130-60+150-110+200-50)/4
帶權平均周轉時間（120/120+70/10+40/20+150/50）/4
搶占式(注意看A執行50min後仍剩餘70min，則與其它作業相比，時間還是過長)：
A[0-50]B[50-60]C[60-70]B[70-110]D[110-130]A[130-200]
平均周轉時間（200+110-50+70-60+130-110）/4
HRRF：要考慮響應比，響應比高者優先。
A先到，服務A，用時120，此時，B,C,D都已經到達，求出其響應比分別為（70+50）/50，（60+10）/10，（10+20）/20，則執行C，用時10min；之後剩下B,D，
響應比分別為（80+50）/50，（20+20）/20，則執行B，用時50，最後是D，用時20min
A[0-120]C[120-130]B[130-180]D[180-200]
平均周轉時間：（120+130-60+180-50+200-110）/4
其它幾個運算都一樣，我就不再多寫了。
『陸』 處理機調度在主存中的作業均分cpu時間
系統採用SJF 被更短作業搶占。(1)分別給出6個作業的執行時間序列、即開始執行時間、作業完成
(1) J2 到達時搶佔J1 ; J3 到達時搶佔J2 。
(2）但J4 到達時，因不滿足SJF ，故J4 不能被運行，J3 繼續執行5 分鍾。
(3）由於是4 道的作業系統，故後面作業不能進入主存而在後備隊列等待，直到有作業結束。
(4）根據進程調度可搶占原則，J3 第一個做完。而這時J5 、J6 均己進入後備隊列，而J5 可進入主存。
(5）因J5 最短，故它第二個完成。這時J6 方可進入主存。因J6 最短，故它第三個完成。
(6）然後是：J4 、J2和J1
(7) T =( 155 + 95 + 20 + 55 + 15 + 20 ) / 6 = 60
有一個具有兩道作業的批處理系統，作業調度採用短作業優先的調度演算法，進程調度採用以優先數為基礎的搶占式調度演算法，在下表所示的作業序列，作業優先數即為進程優
(1)(2)計算平均周轉時間。
每個作業運行將經過兩個階段：作業調度(SJF演算法) 和進程調度(優先數搶占式) 。另外，批處理最多容納2道作業，更多的作業將在後備隊列等待。
(2) 10:20，作業B 到達且優先權高於作業A ，故作業B 投入運行而作業A 在就緒隊列等待。
(3) 10:30，作業C 到達，因內存中已有兩道作業，故作業C 進入作業後備隊列等待。
(4) 10:50，作業B 運行結束，作業D 到達，按SJF 短作業優先演算法，或迅作業D 被裝入內存進入就緒隊列。而由於作業A 的優先順序高於作業D ，故作業A 投入運行。
(5) 11:10，作業A 運行結束，作業C 被調入內存，且作業C 的優先順序高於作業D ，故作業C 投入運行。
(6) 12:00，作業C 運行結束，作業D 投入運行。 (7) 12:20，作業，作業D 90。平均作業周轉時間為70分鍾。
某多道程序設計系統供用戶使用的主存為100K ，磁帶機2台，列印機1台。採用可變分
在
主存中的各作業平分CPU 時間。現求：(1)作業被調度的先後次序?(2)全部作業運行結束的時間?(3)作業平均周轉時間為多少?(4)最大作業周轉時間為多少? 答：(1)作業調度選擇的作業次序為：作業1、作業3、作業4、作業2和作業5。 (2)全部作業塵兆運行結束的時間9:30。
(3)周轉時間：作業1為30分鍾、作業2為55分鍾、作業3為40分鍾、作業4
為40分鍾和作業5為55分鍾。 (4)平均作業周轉時間=44分鍾。 (5) )最大作業周轉時間為55分鍾。
分析：本題綜合測試了作業調度、進程調度、及對外設的競爭、主存的競爭。 8 : 00 作業1 到達，佔有資源並調入主存運行。 8 : 20 作業2 和3 同時到達，但作業2 因分不到列印機，只能在後備隊列等待。作業3 資源滿足，可進主存運行，並與作業1 平分CPU 時間。
8 : 30 作業1 在8 : 30 結派團租束，釋放磁帶與列印機。但作業2 仍不能執行，因不能移動而沒有30KB 的空閑區，繼續等待。作業4 在8 : 30 到達，並進入主存執行，與作業3 分享CPU
8 : 35 作業5 到達，因分不到磁帶/列印機，只能在後備隊列等待。 9 : 00 作業3 運行結束，釋放磁帶機。此時作業2 的主存及列印機均可滿足，投入運行。作業5 到達時間晚，只能等待。
9 : 10 作業4 運行結束，作業5 因分不到列印機，只能在後備隊列繼續等待。 9：15 作業2 運行結束，作業5 投入運行。 9 : 30 作業全部執行結束。
某多道程序設計系統採用可變分區內存管理，供用戶使用的主存為200K ，磁帶機5台。採用靜態方式分配外圍設備，且不能移動在主存中的作業，忽略用戶作業I/O時間。現
執行的次序及作業平均周轉時間?
(1) FIFO演算法選中作業執行的次序為：A 、B 、D 、C 和E 。作業平均周轉時間為63分鍾。詳細說明：
1．先來先服務演算法。說明：
(1) 8 : 30 作業A 到達並投入運行。注意它所佔用的資源。 (2) 8 : 50 作業B 到達，資源滿足進主存就緒隊列等CPU 。
(3) 9 : 00 作業C 到達，主存和磁帶機均不夠，進後備作業隊列等待。
(4) 9 : 05 作業D 到達，磁帶機不夠，進後備作業隊列等待。後備作業隊列有C 、D 。 (5) 9 : 10 作業A 運行結束，歸還資源磁帶，但注意主存不能移動（即不能緊縮）。作業B 投入運行。作業C 仍因主存不夠而等在後備隊列。這時作業E 也到達了。也由於主存不夠進入後備作業隊列。此時作業D 因資源滿足（主存磁帶均滿足），進主存就緒隊列等待。後備作業隊列還有C 、E 。
(6) 9 : 35 作業B 運行結束，作業D 投入運行。這時作業C 因資源滿足而調入主存進就緒隊列等CPU 。而作業E 因磁帶機不夠繼續在後備作業隊列等待。
(7) 9 : 55 作業D 運行結束，作業C 投入運行。這時作業E 因資源滿足而調入主存進就緒隊列等CPU 。
(8) 10 : 30 作業C 運行結束，作業E 投入運行。 (9) 10 : 40 作業E 運行結束。
(2) SJF演算法選中作業執行的次序為：A 、B 、D 、E 和C 。作業平均周轉時間為58分鍾。說明：
( 1 ) 8 : 30 作業A 到達並投入運行。注意它所佔用的資源。 ( 2 ) 8 : 50 作業B 到達，資源滿足進主存就緒隊列等CPU 。
( 3 ) 9 : 00 作業C 到達，主存和磁帶機均不夠，進後備作業隊列等待。
( 4 ) 9 : 05 作業D 到達，磁帶機不夠，進後備作業隊列等待。後備作業隊列有C 、D 。 ( 5 ) 9 : 10 作業A 運行結束，歸還資源磁帶，但注意主存不能移動（即不能緊縮）。作業B 投入運行。作業C 仍因主存不夠而等在後備隊列。這時作業E 也到達了，雖然該作業最短，也由於主存不夠進入後備作業隊列．此時作業D 因資源滿足（主存磁帶均滿足），進主存就緒隊列等待。後備作業隊列還有C 、E 。
( 6 ) 9:35 作業B 運行結束，作業D 投入運行。這時作業C 和E 資源均滿足，但按SJF 應把作業E 調入主存進就緒隊列等CPU 。而作業C 因磁帶機不夠繼續在後備作業隊列等待。 ( 7 ) 9:55 作業D 運行結束，作業C 調入主存進就緒隊列等CPU 。 ( 8 ) 10:05 作業E 運行結束，作業C 投入運行。 ( 9 ) 10:40 作業C 運行結束。
『柒』 利用短作業優先演算法(SJF)，計算進程的周轉時間和帶權周轉時間。非常著急！！
周轉時間=進程結束的時間 - 進程到達的時間；
帶權周轉時間=周轉時間 / 執行時間；
如：A作業2：30到達，3：30結束，需要執行40分鍾。
周轉時間=3：30-2：30=60分鍾
帶權周轉時間=60分鍾/40分鍾=1.5