❶ 最佳調度問題：假設有n個任務由k個並行工作的機器來完成。完成任務i需要的時間為Ti。試設計一個演算法找出完
Node{
int Path[n]; //節點對應的解空間樹的路徑，即到該節點為止的策略記錄
int T[k]; //在本策略下的每台機器的運行時間
int Time; //本策略的總執行時間，為每台機器運行時間的最大值
int length; //本節點的深度,即當前處理的作業
}
Proc BestDispatch(int n,int k,int t[])
Node Boot,X,P,result; //Boot為根節點，result保存最優解
int f; //記錄當前最優解的執行時間
f=n*max(t[]); //初始化f
Boot.T[n]={0};
Boot.Time=0;
Boot.Path[n]={0};
Boot.length=0; //初始化根節點
AddHeap(Boot); //根節點加入堆中，堆中元素按照Time值由小到大排序
While !Heap.empty() do
P=DeleteMinHeap(); //P為當前優先順序最高的點
for i=1 to k do //擴展P的k個子節點
X=Newnode(P.Path[],P.T[],P.length+1);
X.Path[X.length]=i;
X.T[i]=X.T[i]+t[X.length];
X.Time=max(X.T[]);
if X.length==n then //X為葉節點
if X.Time<f then //X的執行時間小於已知最優解
f=X.Time; //將X設為最優解
result=X;
end{if}
else //X為中間節點
if X.Time<f then
AddHeap(X);
end{if}//X的當前執行時間小於已知最優解則加入堆中，否則剪去
end{if}
end{for}
end{while}
end{ BestDispatch }
❷ 調度演算法詳細資料大全
作業系統管理了系統的有限資源，當有多個進程（或多個進程發出的請求）要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（請求）來佔用資源。這就是調度。目的是控制資源使用者的數量,選取資源使用者許可佔用資源或佔用資源。
基本介紹
調度演算法,評價因素,吞吐量,CPU利用率,周轉時間,確定進程調度原則,調度演算法分類,先來先服務(FCFS),輪轉法(Round Robin),多級反饋佇列演算法,
linux進程調度演算法,
調度演算法
在作業系統中調度是指一種資源分配，因而調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。對於不同的的系統和系統目標，通常採用不同的調度演算法，例如，在批處理系統中，為了照顧為數眾多的段作業，應採用短作業優先的調度演算法；又如在分時系統中，為了保證系統具有合理的回響時間，應當採用輪轉法進行調度。目前存在的多種調度演算法中，有的演算法適用於作業調度，有的演算法適用於進程調度；但也有些調度演算法既可以用於作業調度，也可以用於進程調度。 通常將作業或進程歸入各種就緒或阻塞佇列。 調度演算法要求：高資源利用率、高吞吐量、用戶滿意等原則。 進程調度所採用的演算法是與整個系統的設計目標相一致的： 1.批處理系統：增加系統吞吐量和提高系統資源的利用率; 2.分時系統：保證每個分時用戶能容忍的回響時間。 3.實時系統：保證對隨機發生的外部事件做出實時回響。
評價因素
吞吐量
單位時間內CPU完成作業的數量。
CPU利用率
從0%～100%。
周轉時間
評價批處理系統的性能指標。 Ti = 作業完成時刻 － 作業提交時刻
確定進程調度原則
在系統角度來說，公平性：每個進程（不論優先權）都有機會被運行；較大的吞吐量。 用戶角度：及時性：回響速度要快；較短的周轉時間：不應當讓用戶等待時間過長。
調度演算法分類
先來先服務(FCFS)
先來先服務（FCFS, First Come First Serve）是最簡單的調度演算法，按先後順序進行調度。 1. FCFS演算法 按照作業提交或進程變為就緒狀態的先後次序，分派CPU； 當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。 在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或梁兆進程出讓CPU。最簡單的演算法。 2. FCFS的特點 比較有利於長作業，而不利於短作業。 有利於CPU繁忙的作業，而不利於I/O繁忙的作業。
輪轉法(Round Robin)
輪轉法(Round Robin)是讓每個進程在就緒佇列中的等待時間與享受服務的時間成正比例。 1. 輪轉法 將系統中所有的就緒進程按照FCFS原則，排成一個佇列。 每次調度時將CPU分派給隊碧渣戚首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。 在一個時間片結束時，發生時鍾中斷。 調度程式據此暫停當前進程的執行，將其送到就緒佇列的末尾，並通過上下文切換執行當前的隊首進程。? 進程可以未使用完一個時間片，就出讓CPU（如阻塞）。 2. 時間片長度的確定 時間片長度變化的影響2 過長－>退化為FCFS演算法，進程在一個時間片內都執行完，回響時間長。2 過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，回響時間長。 對回響時間的要求：T(回響悔陵時間)=N(進程數目)*q(時間片) 就緒進程的數目：數目越多，時間片越小 系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使回響時間，平均周轉時間和平均帶權周轉時間延長。
多級反饋佇列演算法
多級反饋佇列演算法時間片輪轉演算法和優先權演算法的綜合和發展。優點：2 為提高系統吞吐量和縮短平均周轉時間而照顧短進程。2 為獲得較好的I/O設備利用率和縮短回響時間而照顧I/O型進程。2 不必估計進程的執行時間，動態調節。 1. 多級反饋佇列演算法2 設定多個就緒佇列，分別賦予不同的優先權，如逐級降低，佇列1的優先權最高。每個佇列執行時間片的長度也不同，規定優先權越低則時間片越長，如逐級加倍。2 新進程進入記憶體後，先投入佇列1的末尾，按FCFS演算法調度；若按佇列1一個時間片未能執行完，則降低投入到佇列2的末尾，同樣按FCFS演算法調度；如此下去，降低到最後的佇列，則按「時間片輪轉」演算法調度直到完成。2 僅當較高優先權的佇列為空，才調度較低優先權的佇列中的進程執行。如果進程執行時有新進程進入較高優先權的佇列，則搶先執行新進程，並把被搶先的進程投入原佇列的末尾。 2. 幾點說明 I/O型進程：讓其進入最高優先權佇列，以及時回響I/O互動。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞佇列。 計算型進程：每次都執行完時間片，進入更低級佇列。最終採用最大時間片來執行，減少調度次數。 I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的佇列，以免每次都回到最高優先權佇列後再逐次下降。2為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先權；時間片用完時，降低優先權。 3.shortest job next 系統計算程式調用的時間，時間最短的先執行。
linux進程調度演算法
linux核心的三種調度方法： 1. SCHED_OTHER 分時調度策略， 2. SCHED_FIFO實時調度策略，先到先服務 3. SCHED_RR實時調度策略，時間片輪轉 實時進程將得到優先調用，實時進程根據實時優先權決定調度權值，分時進程則通過nice和counter值決 定權值，nice越小，counter越大，被調度的機率越大，也就是曾經使用了cpu最少的進程將會得到優先調 度。 SHCED_RR和SCHED_FIFO的不同： 當採用SHCED_RR策略的進程的時間片用完，系統將重新分配時間片，並置於就緒佇列尾。放在佇列 尾保證了所有具有相同優先權的RR任務的調度公平。 SCHED_FIFO一旦佔用cpu則一直運行。一直運行直到有更高優先權任務到達或自己放棄。 如果有相同優先權的實時進程（根據優先權計算的調度權值是一樣的）已經准備好，FIFO時必須等待該 進程主動放棄後才可以運行這個優先權相同的任務。而RR可以讓每個任務都執行一段時間。 SHCED_RR和SCHED_FIFO的相同點： SHCED_RR和SHCED_FIFO都只用於實時任務。 創建時優先權大於0(1-99)。 按照可搶占優先權調度演算法進行。 就緒態的實時任務立即搶占非實時任務。 所有任務都採用linux分時調度策略時。 1. 創建任務指定採用分時調度策略，並指定優先權nice值(-20~19)。 2. 將根據每個任務的nice值確定在cpu上的執行時間(counter)。 3. 如果沒有等待資源，則將該任務加入到就緒佇列中。 4. 調度程式遍歷就緒佇列中的任務，通過對每個任務動態優先權的計算(counter+20-nice)結果，選擇 計算結果最大的一個去運行，當這 個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在 就緒佇列末尾(時間片用完)或等待佇列(因等待資源而放棄cpu)中。 5. 此時調度程式重復上面計算過程，轉到第4步。 6. 當調度程式發現所有就緒任務計算所得的權值都為不大於0時，重復第2步。 所有任務都採用FIFO時: 1. 創建進程時指定採用FIFO，並設定實時優先權rt_priority(1-99)。 2. 如果沒有等待資源，則將該任務加入到就緒佇列中。 3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用 cpu，該FIFO任務將一直佔有cpu直到有優先權更高的任務就緒(即使優先權相同也不行)或者主動放棄(等 待資源)。 4. 調度程式發現有優先權更高的任務到達(高優先權任務可能被中斷或定時器任務喚醒，再或被當前運行 的任務喚醒，等等)，則調度程式立即在當前任務 堆疊中保存當前cpu暫存器的所有數據，重新從高優先權 任務的堆疊中載入暫存器數據到cpu，此時高優先權的任務開始運行。重復第3步。 5. 如果當前任務因等待資源而主動放棄cpu使用權，則該任務將從就緒佇列中刪除，加入等待佇列，此時 重復第3步。 所有任務都採用RR調度策略時 1. 創建任務時指定調度參數為RR，並設定任務的實時優先權和nice值(nice值將會轉換為該任務的時間片 的長度)。 2. 如果沒有等待資源，則將該任務加入到就緒佇列中。 3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用 cpu。 4. 如果就緒佇列中的RR任務時間片為0，則會根據nice值設定該任務的時間片，同時將該任務放入就緒隊 列的末尾。重復步驟3。 5. 當前任務由於等待資源而主動退出cpu，則其加入等待佇列中。重復步驟3。 系統中既有分時調度，又有時間片輪轉調度和先進先出調度 1. RR調度和FIFO調度的進程屬於實時進程，以分時調度的進程是非實時進程。 2. 當實時進程准備就緒後，如果當前cpu正在運行非實時進程，則實時進程立即搶占非實時進程。 3. RR進程和FIFO進程都採用實時優先權做為調度的權值標准，RR是FIFO的一個延伸。FIFO時，如果兩 個進程的優先權一樣，則這兩個優先 級一樣的進程具體執行哪一個是由其在佇列中的未知決定的，這樣導 致一些不公正性(優先權是一樣的，為什麼要讓你一直運行?),如果將兩個優先權一樣的任務 的調度策略都 設為RR,則保證了這兩個任務可以循環執行，保證了公平。
❸ 常見的調度演算法總結
一、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隊列的隊尾。
❹ 操作系統的調度演算法
1)10:00Job1到達並投入運行。此時內存中有作業:Job1
2)10:05 Job2到達並進入內存。此時，Job1運行時間剩餘是25min， Job2運行剩餘時間是20min，根據SRTF，Job2開始運行。
3)10:25 Job2運行結束。Job3、Job4在後備隊列中，據SJF，Job3進入內存，據SRTF，Job3開始運行。內存：Job1、Job3
4)10:30 Job3運行結束。Job4在後備隊列中，Job4進入內存，據SRTF，Job4開始運行。內存：Job1、Job4
5)10:40 Job4運行結束。Job1重新繼續運行。
6)11:05 Job1運行結束。
❺ 怎麼用C語言實現多級反饋隊列調度演算法
調度演算法的實施過程如下所述：（1）應設置多個就緒隊列，並為各個隊列賦予不同的優先順序。（2）當一個新進程進入內存後，首先將它放入第一隊列的末尾，按FCFS的原則排隊等待調度。當輪到該進程執行時，如他能在該時間片內完成，便可准備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片後仍未完成，再依次將它放入第三隊列……，如此下去，當一個長作業進程從第一隊列依次降到第N隊列後，在第N隊列中便採取時間片輪轉的方式運行