短作業優先調度演算法

Ⅰ 什麼是短作業優先的作業調度演算法

短作業優先（SJF, Shortest Job First）又稱為「短進程優先」SPN(Shortest Process Next)；這是對FCFS演算法的改進,其目標是減少平均周轉時間.
定義
對預計執行時間短的作業（進程）優先分派處理機.通常後來的短作業不搶先正在執行的作業.

Ⅱ 如何理解先來先服務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)經驗和體會 通過本次實驗， 通過本次實驗，深入理解了先來先服務和短進程優先進程調 度演算法的思想，培養了自己的動手能力，通過實踐加深了記憶。 度演算法的思想，培養了自己的動手能力，通過實踐加深了記憶。

Ⅲ 作業調度的演算法有哪些

作業調度的演算法有：演算法有先來先服務、最短作業優先演算法、最高響應比優先演算法、基於優先數調度演算法。

1、演算法有先來先服務

最簡單的調度演算法，按作業的先後順序進行調度，只考慮每個作業的等待時間而未考慮執行時間的長短。

2、最短作業優先演算法

最短作業優先演算法是對先來先服務演算法的改進，其目標是減少平均周轉時間。對預計執行時間短的作業優先分派處理機。通常後來的短作業不搶先正在執行的作業。 只考慮執行時間而未考慮等待時間的長短。

3、最高響應比優先演算法

最高響應比優先演算法是對先來先服務方式和最短作業優先演算法方式的一種綜合平衡。最高響應比優先法調度策略同時考慮每個作業的等待時間的長短和估計需要的執行時間長短，從中選出相應比最高的作業投入執行。

4、基於優先數調度演算法

優先數調度演算法常用於批處理系統中。在進程調度中，每次調度時，系統把處理機分配給就緒隊列中優先數最高的進程。它又分為兩種：非搶占式優先數演算法和搶占式優先數演算法。

(3)短作業優先調度演算法擴展閱讀：

作業調度是指按照時間周期(年、月、日、時、分、秒等)對作業進行分割，並根據業務需求、作業長度、存儲管理及依賴性關系對作業的執行方式加以調度。主要任務是從作業後備隊列中選擇作業進入主存運行。作業調度的功能主要有以下幾方面：

1、記錄各作業在系統中的狀態；

2、從後備隊列中挑選一部分作業投入運行；

3、從被選中的作業做好執行前的准備工作；

4、在作業執行結束時，做善後處理工作。

進行作業調度有很多作業調度演算法，這些作業調度演算法要實現的目標是：

1、調度對所有作業都是公平合理的；

2、應使設備有較高的利用率（提供系統利用率）；

3、每次運行盡可能多的作業（提高系統吞吐量）；

4、較快的相應時間。

Ⅳ 作業調度演算法的短作業優先法

短作業優先（SJF, Shortest Job First）又稱為「短進程優先」SPN(Shortest Process Next)；這是對FCFS演算法的改進，其目標是減少平均周轉時間。 (1) 優點：
比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間；
提高系統的吞吐量；
(2) 缺點：
對長作業非常不利，可能長時間得不到執行；
未能依據作業的緊迫程度來劃分執行的優先順序；
難以准確估計作業（進程）的執行時間，從而影響調度性能。 「最短剩餘時間優先」SRT(Shortest Remaining Time)（允許比當前進程剩餘時間更短的進程來搶占）
「最高響應比優先」HRRN(Highest Response Ratio Next)（響應比R = (等待時間 + 要求執行時間) / 要求執行時間，是FCFS和SJF的折衷）

Ⅳ 最短作業優先演算法

以下是最短作業優先演算法

最短作業優先調度演算法是對預計執行時間短的作業（進程）優先分派處理機，通常後來的短作業不搶先正在執行的作業。這種演算法稱為這種演算法會根據作業長短，也就是作業服務時間的多少來調度作業，服務時間短的會被優先調度執行。

通常情況下，對於簡單的時間觸發式調度器來說，待命任務列表的數據結構的設計要盡可能縮短最壞賣嫌情況下，程序在調度器關鍵部分的執行時間，以防止其他任務一直在待命列表中，無法及時執行。

因此，在這種調度器中，應盡可能避免搶占式任務，甚至應該關閉調度器之外的所有中斷。當然，待命任務列表的數據結構也應根據這個系統需要的最大任務數量做進一步的優化。

Ⅵ 常見的調度演算法總結

一、FCFS——先來先服務和短作業（進程）優先調度演算法

1. 先來先服務調度演算法。

先來先服務（FCFS）調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度， 也可用於進程調度。FCFS演算法比較有利於長作業（進程），而不利於短作業（進程）。由此可知，本演算法適合於CPU繁忙型作業， 而不利於I/O繁忙型的作業（進程）。

2. 短作業（進程）優先調度演算法。

短作業（進程）優先調度演算法（SJ/PF）是指對短作業或短進程優先調度的演算法，該演算法既可用於作業調度， 也可用於進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

二、FPF高優先權優先調度演算法

1. 優先權調度演算法的類型。

為了照顧緊迫性作業，使之進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。 此演算法常被用在批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度，還可以用於實時系統中。當其用於作業調度， 將後備隊列中若干個優先權最高的作業裝入內存。當其用於進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該演算法分成以下兩種：

1)非搶占式優先權演算法

2)搶占式優先權調度演算法（高性能計算機操作系統）

2. 優先權類型 。

對於最高優先權優先調度演算法，其核心在於：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。

3.動態優先權

高響應比優先調度演算法為了彌補短作業優先演算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間

三、基於時間片的輪轉調度演算法

1.時間片輪轉法。

時間片輪轉法一般用於進程調度，每次調度，把CPU分配隊首進程，並令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鍾中斷請求，該進程被停止，並被送往就緒隊列末尾；依次循環。

2. 多級反饋隊列調度演算法

多級反饋隊列調度演算法多級反饋隊列調度演算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度演算法。 其實施過程如下：

1) 設置多個就緒隊列，並為各個隊列賦予不同的優先順序。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。

2) 當一個新進程進入內存後，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最後隊列）後，便按第n隊列時間片輪轉運行。

3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；

僅當第1到第（ i-1 ）隊列空時， 才會調度第i隊列中的進程運行，並執行相應的時間片輪轉。

4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，並把正在運行的進程放在第i隊列的隊尾。

Ⅶ 如果多個進程同時到達系統，則平均周轉時間最短的進程調度演算法是什麼

如果多個進程同時到達系統，則平均周轉時間最短的進程調度演算法是 短進程優先調度演算法 。
短進程優先調度演算法SJ（P）F，是指對短作業或短進程優先調度的演算法。它們可以分別信拿孫用於作業調度和進程調度。短作業優先（SJF）的調度演算法是從後備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程（SPF）調度演算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機再重新調度。
優點是SJ(P)F調度演算法能有效地降低作業（進程）的平均等待時間，提高系統吞吐量。
缺點是該演算法對長作業不利；完全未考慮作業的緊迫程度，因而不能保證緊迫性作業（進程）長期不被調度；由於作業（進程）的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該演算法不一定能真正做到短作業游戲那調度。
該程序定義了一個進程數據塊(struct spf)，該數據塊有進程名(name)、到達時間(arrivetime)、服務時間(servicetime)、開始執行時間(starttime)、完成時間(finishtime)、周轉時間(zztime)、平均周轉時間(averzztime)。用到的公式有：完成時間=到達時間+服務時間；周轉時間=完成時間-到達時間；(第一次執行的進程的完成時間=該進程的到達時間；下一個進程的開始執行時間=上一個進程的完成時間)。運行進程的順序需要對進程的到達時間和服務時間進行比較。如果某一進程是從0時刻到達的，那麼首先執行該進程；之後就比較進程的服務時間，誰的服務時間滑鏈短就先執行誰（如果服務時間相同則看它們的到達時間，敏兆到達時間短的先執行）；如果到達時間和服務時間相同，則按先來先服務演算法執行。

Ⅷ 如何證明按短作業優先演算法調度時其平均周轉時間最短

假設有n個作業，按照運行時間排序t1
<扮戚
t2
<...
<
tn
平均周轉時間
=
（總的運行時間
+
總的等待時間）/n
其中總的運行時間是定值，n為定值，因此要平均周轉時間最短既要滑閉求總信缺裂的等待時間最短。
按照最短作業優先，設第i個作業的等待時間為ai.則
a1
=
0
a2
=
t1
a3
=
t1
+
t2
....
an
=
t1
+
t2
+
...
+
t(i-1)
總的等待時間為a1
+
a2
+
a3
+
...
+
an
現在只需要證明這個是最小就可以了。任意取2個作業i
和
j。
且ti
<
tj。交換ti和tj的順序。
則新等待時間變成b0
b1
b2
....
b(i-1)
bi
b(i+1)
.....
b(j-1)
bj
b(j+1)
...
bn
其中b0
+
b1
+
...
+
b(i-1)
+
bi與原來的a相等。
b(i+1)
=
t1
+
t2
+
...
+
t(i-1)
+
tj
>
t1
+
t2
+
...
+
t(i-1)
+
ti
=
a(i+1)
依次類推之後bx
>
ax
其中i
<
x
<
j+1.之後b與a又相等。
所以任意交換後，等待時間變大。所以最小作業優先的等待時間最小。所以平均周轉時間最短。

Ⅸ 短作業優先調度演算法中處於就緒隊列中的短作業到底搶占當前正在執行的長作業的CPU

貌似一樓沒有回答樓主的問題，我來簡單回答一下：
你是指SJF演算法吧，這個應該是大家通常所蔽宏說的短作業調度演算法，那麼從我看的書來說，這個演算法是「非搶占式」的，也就是說：如果A進程到達時刻為0，服務時間為4，但B進程到達時間為1，服務時間為2，那麼SJF也會先讓A執行完，然後再去執行B。
-----------------------------------------------------------------------
我感覺你不必太糾結於這個問題，如果只是為了做題的話，姑且可以講SJF就認為是非搶占式，但如果你要實現SJF的話，那麼搶占式和非搶占式均可，看你的系統的需求而定，你也懂的宏歲冊，現在中國教材太不嚴謹，不必糾結於這些，如果你翻閱了大量的文獻（高級journal中的）還是沒有看到搶占式SJF演算法，那麼你可以證明它優於非搶占雀猜式SJF，然後發paper，搞計算機的就是這樣.........

Ⅹ 短作業優先調度演算法和優先順序為基礎的非搶占式調度演算法

短進程優先乎坦演算法是一種棚帆非剝奪式演算法，總是選取預計作業時間最短的作業優先運歲和桐行；最短剩餘時間優先演算法是非剝奪式的，但可以改造成剝奪式的調度演算法，稱搶占式最短作業優先演算法。