fcfs演算法程序

A. 1) FCFS先進先服務的進程調度演算法 2) SPF短作業優先的進程調度演算法 3) 響應比高優先的進程調度演算法

FCFS和preemptive SJF不是SPF注意,Average Turnround Time平均周轉時間的計算如下: 將所有進程的等待時間和執行時間都加起來除以進程數,如P1,P2,P3 CPU burst time 5,9,6 Arrive time到達時間為3,0,1 即P2先到達等待時間為0 然後P3到達,然後P1到達, 那麼P3,P1能不能搶占哪?看誰的CPU burst time最少,SJF最短job先執行First, P1 CPU burst time是5所以P1優先順序最大, 然後是P3優先順序第二大,因為CPU burst time是6, 所以當P2因Arrive time為0而先執行,當執行1單位時間後,P3到達 Arrive Time 為1嘛,所以P3搶佔P2開始執行執行到第3單位時間時P1到達,P1 CPU burst time是5而P3是6,所以P1將P3搶占 P1從開始到P1任務完成,執行了5單位時間, 然後P2和P3誰優先,P3 CPU burst time是6 而P2 CPU burst time是9 所以P3接著從剛才的終端點繼續執行，剛才已經執行（3-1）=2單位時間，（6-2）=4 即P3又執行4單位時間，接著P2執行（9-1）=8 單位時間：所以平均周轉時間 Average Turnaround Time為等待時間加執行時間：P1：5（因優先順序最大又沒等）P2：等待時間（2+5+4）=11執行時間=9 所以P2周轉時間11+9=20 P3：等待時間=5（被P1搶佔了嘛）執行時間=6 所以P3周轉時間 Turnaround Time：5+6=11 這樣平均周轉時間等於（5+20+11）/3=36/3=12 單位時間 有問題email：[email protected]

B. 畫出採用先來先服務演算法（FCFS）、短作業優先演算法（SJF）和高響應比優先演算法（HRN）的作業調度程序流程圖

先來先服務演算法，就是來了就排隊，然後逐個處理.....流程太簡單了，不知道怎麼畫，所以就隨手畫了一個

C. 使用fcfs，sjf和rr調度演算法，並判斷哪個演算法的平均等待時

先來先服務FCFS和短作業優先 和短作業優先SJF進程調度演算法 先來先服務 和短作業優先 進程調度演算法 1、實驗目的 通過這次實驗，加深對進程概念的理解，進一步掌握進程狀態的 轉變、進程調度的策略及對系統性能的評價方法。 2、需求分析 (1) 輸入的形式和輸入值的范圍 輸入值：進程個數Num 依次輸入Num個進程的到達時間 依次輸入Num個進程的服務時間 范圍：0<Num<=100 范圍： 范圍： 輸入要使用的演算法（1-FCFS，2-SJF） 范圍：1或者2 輸出的形式（ 表示變數） (2) 輸

D. 如何理解先來先服務fcfs和短作業優先sjf進程調度演算法

先來先服務FCFS和短作業優先 和短作業優先SJF進程調度演算法 先來先服務 和短作業優先 進程調度演算法 1、實驗目的 通過這次實驗，加深對進程概念的理解，進一步掌握進程狀態的 轉變、進程調度的策略及對系統性能的評價方法。 2、需求分析 (1) 輸入的形式和輸入值的范圍 輸入值：進程個數Num 依次輸入Num個進程的到達時間 依次輸入Num個進程的服務時間 范圍：0<Num<=100 范圍： 范圍： 輸入要使用的演算法（1-FCFS，2-SJF） 范圍：1或者2 輸出的形式（ 表示變數） (2) 輸出的形式（X表示變數） 時刻X：進程X開始運行。 其完成時間：X 周轉時間：X 帶權周轉時 間：X …（省略（Num-1）個） 平均周轉時間：X 平均帶權周轉時間：X (3) 程序所能達到的功能 輸入進程個數Num，每個進程到達時間ArrivalTime[i]，服務時間 ServiceTime[i]。採用先來先服務FCFS或者短作業優先SJF進程調度算 法進行調度，計算每個進程的完成時間、周轉時間和帶權周轉時間， 並且統計Num個進程的平均周轉時間和平均帶權周轉時間。 3、概要設計 說明本程序中用到的所有抽象數據類型的定義、 主程序的流程以 及各程序模塊之間的層次(調用)關系。 4、詳細設計 5、調試分析 (1)調試過程中遇到的問題以及解決方法， (1)調試過程中遇到的問題以及解決方法，設計與實現的回顧討 調試過程中遇到的問題以及解決方法 論和分析 1 ○ 開始的時候沒有判斷進程是否到達， 導致短進程優先演算法運 開始的時候沒有判斷進程是否到達， 行結果錯誤，後來加上了判斷語句後就解決了改問題。 行結果錯誤，後來加上了判斷語句後就解決了改問題。 2 ○ 基本完成的設計所要實現的功能， 總的來說， FCFS編寫容易， 基本完成的設計所要實現的功能， 總的來說， FCFS編寫容易， 編寫容易 SJF 需要先找到已經到達的進程， 需要先找到已經到達的進程， 再從已經到達的進程里找到進程服務時 間最短的進程，再進行計算。 間最短的進程，再進行計算。 (2)算 (2)演算法的改進設想 改進： 改進：即使用戶輸入的進程到達時間沒有先後順序也能准確 的計算出結果。（就是再加個循環，判斷各個進程的到達時間先後， 的計算出結果。（就是再加個循環，判斷各個進程的到達時間先後， 。（就是再加個循環 組成一個有序的序列） 組成一個有序的序列） (3)經驗和體會 (3)經驗和體會 通過本次實驗， 通過本次實驗，深入理解了先來先服務和短進程優先進程調 度演算法的思想，培養了自己的動手能力，通過實踐加深了記憶。 度演算法的思想，培養了自己的動手能力，通過實踐加深了記憶。

E. 簡述FCFS分裂演算法

調度演算法：
FCFS演算法
按照作業提交或進程變為就緒狀態的先後次序，分派CPU； 當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。 在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或進程出讓CPU。最簡單的演算法。

2. FCFS的特點

比較有利於長作業，而不利於短作業。 有利於CPU繁忙的作業，而不利於I/O繁忙的作業。

F. 以下五個作業，fcfs sjf hrrn三種調度演算法平均周轉時間，高響應比怎麼算

作業調度演算法 .

1. 先來先服務（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 法時的吞吐量。另外，由於每次調度前要計算響應比，系統開銷也要相應增加。

G. 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

H. 先來先服務(FCFS)調度演算法 工作原理 優缺點

進程按到來的時間先後順序依次被CPU處理。
優點：就是俗話說的「先來後到」。
缺點：如果先來的進程需要很長的處理時間，而後來的進程卻很重要的。需要搶佔CUP的時候，此調度演算法就適用了。

I. 作業調度演算法一道題的解析——FCFS演算法

10.1時，①裝入主存，主存：15k，85k空閑，計算：①，等待隊列：空
10.3時，②裝入主存，主存：15k，60k，25k空閑，計算：①，等待隊列：②
10.4時，①完成計算，主存：15k空閑，60k，25k空閑，計算：②，等待隊列：空
10.5時，③要裝入主存，但由於內存不足，等待
10.6時，④裝入主存，主存：10k，5k空閑，60k，25k空閑，計算：②，等待隊列：④
10.7時，⑤裝入主存，主存：10k，5k空閑，60k，20k，5k空閑，計算：②，等待隊列：④，⑤
10.9時，②完成計算，主存：10k，65k空閑，20k，5k空閑，計算：④，等待隊列：⑤
10.9時，③由於存在超過50k的空間，裝入主存，主存：10k，50k，15k空閑，20k，5k空閑
計算：④，等待：⑤，③（此時按照先來先服務調度，⑤為先來的作業）
10.13時，④完成計算，主存：10k空閑，50k，15k空閑，20k，5k空閑，計算：⑤，等待隊列：③
10.15時，⑤完成計算，主存：15k空閑，60k，25k空閑，計算：②，等待隊列：空
10.19時，③完成計算，主存：100k空閑，計算：空，等待隊列：空
因此，順序為①②④⑤③