進程調度演算法程序

❶ 進程調度演算法

調度算指:根據系統資源配策略所規定資源配算
、先先服務短作業(進程)優先調度算
1.
先先服務調度算先先服務(FCFS)調度算種簡單調度算該算既用於作業調度
用於進程調度FCFS算比較利於作業(進程)利於短作業(進程)由知本算適合於CPU繁忙型作業
利於I/O繁忙型作業(進程)
2.
短作業(進程)優先調度算短作業(進程)優先調度算(SJ/PF)指短作業或短進程優先調度算該算既用於作業調度
用於進程調度其作業利;能保證緊迫性作業(進程)及處理;作業短估算
二、高優先權優先調度算
1.
優先權調度算類型照顧緊迫性作業使進入系統便獲優先處理引入高優先權優先(FPF)調度算
算用批處理系統作作業調度算作種操作系統進程調度用於實系統其用於作業調度
備隊列若干優先權高作業裝入內存其用於進程調度處理機配給緒隊列優先權高進程
進步該算兩種:
1)非搶占式優先權算
2)搶占式優先權調度算(高性能計算機操作系統)
2.
優先權類型
於高優先權優先調度算其核於:使用靜態優先權態優先權
及何確定進程優先權
3.
高響應比優先調度算
彌補短作業優先算足我引入態優先權使作業優先等級隨著等待間增加速率a提高
該優先權變化規律描述:優先權=(等待間+要求服務間)/要求服務間;即
=(響應間)/要求服務間
三、基於間片輪轉調度算
1.
間片輪轉間片輪轉般用於進程調度每調度CPU配隊首進程並令其執行間片
執行間片用完由記器發鍾斷請求該進程停止並送往緒隊列末尾;依循環
2.
級反饋隊列調度算
級反饋隊列調度算級反饋隊列調度算必事先知道各種進程所需要執行間目前公認種較進程調度算
其實施程:
1)
設置緒隊列並各隊列賦予同優先順序優先權越高隊列
每進程所規定執行間片越
2)
新進程進入內存首先放入第隊列末尾按FCFS原則排隊等候調度
能間片完便撤離;未完轉入第二隊列末尾同等待調度……
作業(進程)第隊列依第n隊列(隊列)便按第n隊列間片輪轉運行
3)
僅第隊列空閑調度程序才調度第二隊列進程運行;僅第1第(i-1)隊列空
才調度第i隊列進程運行並執行相應間片輪轉
4)
處理機處理第i隊列某進程新進程進入優先權較高隊列
則新隊列搶占運行處理機並運行進程放第i隊列隊尾

❷ （操作系統）編寫進程調度演算法程序

#include<iostream>
#include<string>
#include<iomanip>
#include<windows.h>
using namespace std;
typedef struct Process
{ string id;
int arrive_time;
int sever_time;
int finish_time;
int turnover_time;
Process * next;
}Process,* Linkp; class FCFS_schele
{ public: FCFS_schele()
{
Creat_queue();
}
~FCFS_schele();
void Creat_queue();
void Insert_queue();
void orderInsert_queue();
void Out_queue();
void Printall();
void Sort_queue();
Process Gethead();
private:
Linkp head,tail;
int num;
Process Creat_process();
};///////////////////////////////////////////////////////方法的具體實現void FCFS_schele::Creat_queue()
{ head=new Process;
head->next=0;
tail=head;
num=0;
}
ostream& operator <<(ostream& out,Process& a) //對插入流運算符<<進行重載
{ out<<"process id:"<<a.id <<" arrivetime:"<<a.arrive_time
<<" severtime:"<<a.sever_time<<endl;
return(out);
}Process FCFS_schele::Creat_process()
{ Process a;

cout<<"please input process id"<<num+1<<":";
cin>>a.id ;
cout<<"please input process arrivetime:";
cin>>a.arrive_time ;
cout<<"please input process severtime:";
cin>>a.sever_time ;
a.finish_time=0;
a.turnover_time=0;
a.next =0;
return(a);
} void FCFS_schele::Insert_queue ()
{ Linkp p;
p=new Process;
*p=Creat_process();
if(num==0)
{p->finish_time=p->arrive_time+p->sever_time;<br> p->turnover_time=p->finish_time-p->arrive_time ;<br> }
else
{p->finish_time=tail->finish_time + p->sever_time ;<br> p->turnover_time=p->finish_time - p->arrive_time ;<br> }
tail->next=p;
tail=p;
num++;
}
void FCFS_schele::Out_queue() //進程調度出隊
{ Linkp p;
p=head->next;
if(!p) cout<<"empty!\n";
else
{ head->next=p->next;
if(p->next==NULL) tail=head;
cout<<"process id:"<<p->id<<" arrivetime:"<<p->arrive_time
<<" severtime:"<<p->sever_time<<" finishtime:"<<p->finish_time
<<" turnovertime:"<<p->turnover_time <<endl;
delete p;
num--;
}
}
Process FCFS_schele::Gethead()throw(int)

{ Linkp p;
p=head->next;
if(p) return(*p);
else throw 1; //當隊空無法返回Process類型返回值時拋出異常錯誤整形值1

}
void FCFS_schele::Printall()
//列印進程隊列所有進程信息
{ Linkp p;
float sum_wghtime=0;
p=head->next;
cout<<" Process Information\n";
cout<<"process id arrivetime severtime finishtime turnovertime weightime\n";
while(p)
{ cout<<p->id<<setw(14)<<p->arrive_time
<<setw(14)<<p->sever_time<<setw(14)<<p->finish_time<<setw(14)<<p->turnover_time
<<setw(14)<<float(p->turnover_time)/float(p->sever_time )<<endl;
sum_wghtime=sum_wghtime+(float)p->turnover_time/p->sever_time;
p=p->next;
}
cout<<"平均帶權周轉時間為:"<<sum_wghtime/num<<endl;
}
void FCFS_schele::Sort_queue ()
//採用選擇法將隊列中的進程按servertime長短進行換值不換址的排序{ Linkp location,search,record,track;
Process temp;
track=head->next;
location=track->next ;
while(location && location->next )
{ record=search=location;

while(search)
{ if(search->sever_time <record->sever_time ) record=search;
search=search->next ;
} if(record!=location)
{
temp=*record;
record->arrive_time =location->arrive_time ;
record->id =location->id ;
record->sever_time =location->sever_time ;

location->id =temp.id;
location->sever_time =temp.sever_time ;
location->arrive_time =temp.arrive_time ;
location->finish_time =track->finish_time + location->sever_time ;
location->turnover_time =location->finish_time - location->arrive_time ;
}
track=location;
location=location->next ;
}
if(tail==location)
{tail->finish_time = track->finish_time +tail->sever_time ;<br> tail->turnover_time =tail->finish_time -tail->arrive_time ;<br> }}
FCFS_schele::~FCFS_schele ()
{ Linkp p;
while(p=head)
{
head=head->next ;
delete p;
}
cout<<"the storage of memory has been distory!\n";
} void FCFS_schele::orderInsert_queue () //進程插入排序
{ Linkp p,pr;
p=new Process;
*p=Creat_process(); if(num==0)
{
head->next=p;
tail=p;
p->finish_time =p->arrive_time + p->sever_time ;
p->turnover_time =p->finish_time - p->arrive_time ;
}
else
{
pr=head->next ;
while(pr->next && p->sever_time >= pr->next->sever_time )
pr=pr->next;
if(pr->next==0)
{
p->finish_time = tail->finish_time + p->sever_time ;
p->turnover_time =p->finish_time - p->arrive_time ;
tail->next=p;
tail=p;
}
else
{
p->next =pr->next ;
pr->next=p;
while(p)
{
p->finish_time =pr->finish_time + p->sever_time ;
p->turnover_time = p->finish_time - p->arrive_time ;
pr=p;
p=p->next ;
}
}

}
num++;
} void main()
{
// DWORD start=GetTickCount();

FCFS_schele os;
os.orderInsert_queue ();
os.orderInsert_queue ();
os.orderInsert_queue ();
os.orderInsert_queue ();
os.orderInsert_queue ();
// os.orderInsert_queue ();
// os.orderInsert_queue ();
os.Printall ();
// os.Sort_queue ();
os.Sort_queue ();
os.Printall ();
os.Out_queue ();
os.Out_queue ();
os.Out_queue ();
os.Out_queue ();
/* try{
cout<<os.Gethead () ;
}
catch(int i)
{ if(i==1) cout<<"empty!\n";
}*/
//
// DWORD end=GetTickCount();
// cout<<"spend time:"<<(end-start)<<endl;
/*

os.Out_queue ();
*/
}

❸ 進程調度的演算法

演算法總是把處理機分配給最先進入就緒隊列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。
例如，有三個進程P1、P2和P3先後進入就緒隊列，它們的執行期分別是21、6和3個單位時間，
執行情況如下圖：
對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。
可見，FIFO演算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度演算法。 最短CPU運行期優先調度演算法(SCBF--Shortest CPU Burst First)
該演算法從就緒隊列中選出下一個「CPU執行期最短」的進程，為之分配處理機。
例如，在就緒隊列中有四個進程P1、P2、P3和P4，它們的下一個執行期分別是16、12、4和3個單位時間，執行情況如下圖：
P1、P2、P3和P4的周轉時間分別為35、19、7、3，平均周轉時間為16。
該演算法雖可獲得較好的調度性能，但難以准確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。 前幾種演算法主要用於批處理系統中，不能作為分時系統中的主調度演算法，在分時系統中，都採用時間片輪轉法。
簡單輪轉法：系統將所有就緒進程按FIFO規則排隊，按一定的時間間隔把處理機分配給隊列中的進程。這樣，就緒隊列中所有進程均可獲得一個時間片的處理機而運行。
多級隊列方法：將系統中所有進程分成若干類，每類為一級。 多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權。

❹ 進程調度演算法

FCFS調度演算法屬於不可剝奪演算法。從表面上看，它對所有作業都是公平的，但若一個長作業先到達系統，就會使後面許多短作業等待很長時間，因此它不能作為分時系統和實時系統的主要調度策略。但它常被結合在其他調度策略中使用。例如，在使用優先順序作為調度策略的系統中，往往對多個具有相同優先順序的進程按FCFS原則處理。

FCFS調度演算法的特點是演算法簡單，但效率低； 對長作業比較有利，但對短作業不利（相對SJF和高響應比）；

FCFS調度演算法有利於CPU繁忙型作業，而不利於I/O繁忙型作業。

​ 短作業優先調度演算法是一個非搶占策略，他的原則是下一次選擇預計處理時間最短的進程，因此短進程將會越過長作業，跳至隊列頭。該演算法即可用於作業調度，也可用於進程調度。 但是他對長作業不利，不能保證緊迫性作業（進程）被及時處理，作業的長短只是被估算出來的。

缺點：

該演算法對長作業不利，SJF調度演算法中長作業的周轉時間會增加。更嚴重的是，如果有一長作業進入系統的後備隊列，由於調度程序總是優先調度那些 (即使是後進來的）短作業，將導致長作業長期不被調度（「飢餓」現象，注意區分「死鎖」。後者是系統環形等待，前者是調度策略問題）。

該演算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業會被及時處理。

由於作業的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該演算法不一定能真正做到短作業優先調度。

SJF調度演算法的平均等待時間、平均周轉時間最少。

高響應比優先調度演算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。

該演算法中的響應比是指作業等待時間與運行比值，響應比公式定義如下：

響應比 =（等待時間+要求服務時間）/ 要求服務時間,即RR=（w+s）/s=1+w/s，因此 響應比一定是大於等於1的。

短作業與先後次序的兼顧，且不會使長作業長期得不到服務。

響應比計算系統開銷，增加系統開銷。

高響應比優先調度演算法適合批處理系統，主要用於作業調度。

為了實現 RR 調度，我們將就緒隊列視為進程的 FIFO 隊列。新進程添加到就緒隊列的尾部。CPU 調度程序從就緒隊列中選擇第一個進程，將定時器設置在一個時間片後中斷，最後分派這個進程。

接下來，有兩種情況可能發生。進程可能只需少於時間片的 CPU 執行。對於這種情況，進程本身會自動釋放 CPU。調度程序接著處理就緒隊列的下一個進程。否則，如果當前運行進程的 CPU 執行大於一個時間片，那麼定時器會中斷，進而中斷操作系統。然後，進行上下文切換，再將進程加到就緒隊列的尾部，接著 CPU 調度程序會選擇就緒隊列內的下一個進程。

採用 RR 策略的平均等待時間通常較長。

在 RR 調度演算法中，沒有進程被連續分配超過一個時間片的 CPU（除非它是唯一可運行的進程）。如果進程的 CPU 執行超過一個時間片，那麼該進程會被搶占，並被放回到就緒隊列。因此， RR調度演算法是搶占的。

演算法描述

1、進程在進入待調度的隊列等待時，首先進入優先順序最高的Q1等待。

2、首先調度優先順序高的隊列中的進程。若高優先順序中隊列中已沒有調度的進程，則調度次優先順序隊列中的進程。例如：Q1,Q2,Q3三個隊列，當且僅當在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。

3、對於同一個隊列中的各個進程，按照FCFS分配時間片調度。比如Q1隊列的時間片為N，那麼Q1中的作業在經歷了N個時間片後若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。

4、在最後一個隊列QN中的各個進程，按照時間片輪轉分配時間片調度。

5、在低優先順序的隊列中的進程在運行時，又有新到達的作業，此時須立即把正在運行的進程放回當前隊列的隊尾，然後把處理機分給高優先順序進程。換而言之，任何時刻，只有當第1~i-1隊列全部為空時，才會去執行第i隊列的進程（搶占式）。特別說明，當再度運行到當前隊列的該進程時，僅分配上次還未完成的時間片，不再分配該隊列對應的完整時間片。

❺ 求進程調度演算法

第一部分： 實時調度演算法介紹

對於什麼是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的響應時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決於程序的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯。

實時系統根據其對於實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對於事件的響應時間的截止期限是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限到來之前得到處理，但違反截止期限並不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。

一個計算機系統為了提供對於實時性的支持，它的操作系統必須對於CPU和其他資源進行有效的調度和管理。在多任務實時系統中，資源的調度和管理更加復雜。本文下面將先從分類的角度對各種實時任務調度演算法進行討論，然後研究普通的 Linux操作系統的進程調度以及各種實時Linux系統為了支持實時特性對普通Linux系統所做的改進。最後分析了將Linux操作系統應用於實時領域中時所出現的一些問題，並總結了各種實時Linux是如何解決這些問題的。

1. 實時CPU調度演算法分類

各種實時操作系統的實時調度演算法可以分為如下三種類別[Wang99][Gopalan01]：基於優先順序的調度演算法（Priority-driven scheling-PD）、基於CPU使用比例的共享式的調度演算法（Share-driven scheling-SD）、以及基於時間的進程調度演算法（Time-driven scheling-TD），下面對這三種調度演算法逐一進行介紹。

1.1. 基於優先順序的調度演算法

基於優先順序的調度演算法給每個進程分配一個優先順序，在每次進程調度時，調度器總是調度那個具有最高優先順序的任務來執行。根據不同的優先順序分配方法，基於優先順序的調度演算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態優先順序調度演算法：

這種調度演算法給那些系統中得到運行的所有進程都靜態地分配一個優先順序。靜態優先順序的分配可以根據應用的屬性來進行，比如任務的周期，用戶優先順序，或者其它的預先確定的策略。RM（Rate-Monotonic）調度演算法是一種典型的靜態優先順序調度演算法，它根據任務的執行周期的長短來決定調度優先順序，那些具有小的執行周期的任務具有較高的優先順序。

動態優先順序調度演算法：

這種調度演算法根據任務的資源需求來動態地分配任務的優先順序，其目的就是在資源分配和調度時有更大的靈活性。非實時系統中就有很多這種調度演算法，比如短作業優先的調度演算法。在實時調度演算法中， EDF演算法是使用最多的一種動態優先順序調度演算法，該演算法給就緒隊列中的各個任務根據它們的截止期限（Deadline）來分配優先順序，具有最近的截止期限的任務具有最高的優先順序。

1.2. 基於比例共享調度演算法

雖然基於優先順序的調度演算法簡單而有效，但這種調度演算法提供的是一種硬實時的調度，在很多情況下並不適合使用這種調度演算法：比如象實時多媒體會議系統這樣的軟實時應用。對於這種軟實時應用，使用一種比例共享式的資源調度演算法（SD演算法）更為適合。

比例共享調度演算法指基於CPU使用比例的共享式的調度演算法，其基本思想就是按照一定的權重（比例）對一組需要調度的任務進行調度，讓它們的執行時間與它們的權重完全成正比。

我們可以通過兩種方法來實現比例共享調度演算法[Nieh01]：第一種方法是調節各個就緒進程出現在調度隊列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。

比例共享調度演算法可以分為以下幾個類別：輪轉法、公平共享、公平隊列、彩票調度法（Lottery）等。

比例共享調度演算法的一個問題就是它沒有定義任何優先順序的概念；所有的任務都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的任務的執行都會按比例地變慢。所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法。

1.3. 基於時間的進程調度演算法

對於那些具有穩定、已知輸入的簡單系統，可以使用時間驅動（Time-driven:TD）的調度演算法，它能夠為數據處理提供很好的預測性。這種調度演算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有的處理情況下，對於各個任務的開始、切換、以及結束時間等就事先做出明確的安排和設計。這種調度演算法適合於那些很小的嵌入式系統、自控系統、感測器等應用環境。

這種調度演算法的優點是任務的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有任務需要被執行而CPU卻保持空閑的情況。

2. 通用Linux系統中的CPU調度

通用Linux系統支持實時和非實時兩種進程，實時進程相對於普通進程具有絕對的優先順序。對應地，實時進程採用SCHED_FIFO或者SCHED_RR調度策略，普通的進程採用SCHED_OTHER調度策略。

在調度演算法的實現上，Linux中的每個任務有四個與調度相關的參數，它們是rt_priority、policy、priority（nice）、counter。調度程序根據這四個參數進行進程調度。

在SCHED_OTHER 調度策略中，調度器總是選擇那個priority+counter值最大的進程來調度執行。從邏輯上分析，SCHED_OTHER調度策略存在著調度周期（epoch），在每一個調度周期中，一個進程的priority和counter值的大小影響了當前時刻應該調度哪一個進程來執行，其中 priority是一個固定不變的值，在進程創建時就已經確定，它代表了該進程的優先順序，也代表這該進程在每一個調度周期中能夠得到的時間片的多少； counter是一個動態變化的值，它反映了一個進程在當前的調度周期中還剩下的時間片。在每一個調度周期的開始，priority的值被賦給 counter，然後每次該進程被調度執行時，counter值都減少。當counter值為零時，該進程用完自己在本調度周期中的時間片，不再參與本調度周期的進程調度。當所有進程的時間片都用完時，一個調度周期結束，然後周而復始。另外可以看出Linux系統中的調度周期不是靜態的，它是一個動態變化的量，比如處於可運行狀態的進程的多少和它們priority值都可以影響一個epoch的長短。值得注意的一點是，在2.4以上的內核中， priority被nice所取代，但二者作用類似。

可見SCHED_OTHER調度策略本質上是一種比例共享的調度策略，它的這種設計方法能夠保證進程調度時的公平性--一個低優先順序的進程在每一個epoch中也會得到自己應得的那些CPU執行時間，另外它也提供了不同進程的優先順序區分，具有高priority值的進程能夠獲得更多的執行時間。

對於實時進程來說，它們使用的是基於實時優先順序rt_priority的優先順序調度策略，但根據不同的調度策略，同一實時優先順序的進程之間的調度方法有所不同：

SCHED_FIFO：不同的進程根據靜態優先順序進行排隊，然後在同一優先順序的隊列中，誰先准備好運行就先調度誰，並且正在運行的進程不會被終止直到以下情況發生：1.被有更高優先順序的進程所強佔CPU；2.自己因為資源請求而阻塞；3.自己主動放棄CPU（調用sched_yield）；

SCHED_RR：這種調度策略跟上面的SCHED_FIFO一模一樣，除了它給每個進程分配一個時間片，時間片到了正在執行的進程就放棄執行；時間片的長度可以通過sched_rr_get_interval調用得到；

由於Linux系統本身是一個面向桌面的系統，所以將它應用於實時應用中時存在如下的一些問題：

Linux系統中的調度單位為10ms，所以它不能夠提供精確的定時；

當一個進程調用系統調用進入內核態運行時，它是不可被搶占的；

Linux內核實現中使用了大量的封中斷操作會造成中斷的丟失；

由於使用虛擬內存技術，當發生頁出錯時，需要從硬碟中讀取交換數據，但硬碟讀寫由於存儲位置的隨機性會導致隨機的讀寫時間，這在某些情況下會影響一些實時任務的截止期限；

雖然Linux進程調度也支持實時優先順序，但缺乏有效的實時任務的調度機制和調度演算法；它的網路子系統的協議處理和其它設備的中斷處理都沒有與它對應的進程的調度關聯起來，並且它們自身也沒有明確的調度機制；

3. 各種實時Linux系統

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大學（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，為了在Linux系統中提供對於硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為RT-Linux的實時子系統），而將普通Linux系統作為一個該操作系統中的一個低優先順序的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。RT-Linux的框架如圖 1所示：

圖 1 RT-Linux結構

RT -Linux的關鍵技術是通過軟體來模擬硬體的中斷控制器。當Linux系統要封鎖CPU的中斷時時，RT-Linux中的實時子系統會截取到這個請求，把它記錄下來，而實際上並不真正封鎖硬體中斷，這樣就避免了由於封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬體中斷到來時， RT-Linux截取該中斷，並判斷是否有實時子系統中的中斷常式來處理還是傳遞給普通的Linux內核進行處理。另外，普通Linux系統中的最小定時精度由系統中的實時時鍾的頻率決定，一般Linux系統將該時鍾設置為每秒來100個時鍾中斷，所以Linux系統中一般的定時精度為 10ms，即時鍾周期是10ms，而RT-Linux通過將系統的實時時鍾設置為單次觸發狀態，可以提供十幾個微秒級的調度粒度。

RT-Linux實時子系統中的任務調度可以採用RM、EDF等優先順序驅動的演算法，也可以採用其他調度演算法。

RT -Linux對於那些在重負荷下工作的專有系統來說，確實是一個不錯的選擇，但他僅僅提供了對於CPU資源的調度；並且實時系統和普通Linux系統關系不是十分密切，這樣的話，開發人員不能充分利用Linux系統中已經實現的功能，如協議棧等。所以RT-Linux適合與工業控制等實時任務功能簡單，並且有硬實時要求的環境中，但如果要應用與多媒體處理中還需要做大量的工作。

義大利的RTAI( Real-Time Application Interface )源於RT-Linux，它在設計思想上和RT-Linux完全相同。它當初設計目的是為了解決RT-Linux難於在不同Linux版本之間難於移植的問題，為此，RTAI在 Linux 上定義了一個實時硬體抽象層，實時任務通過這個抽象層提供的介面和Linux系統進行交互，這樣在給Linux內核中增加實時支持時可以盡可能少地修改 Linux的內核源代碼。

3.2. Kurt-Linux

Kurt -Linux由Kansas大學開發，它可以提供微秒級的實時精度[KurtWeb] [Srinivasan]。不同於RT-Linux單獨實現一個實時內核的做法，Kurt -Linux是在通用Linux系統的基礎上實現的，它也是第一個可以使用普通Linux系統調用的基於Linux的實時系統。

Kurt-Linux將系統分為三種狀態：正常態、實時態和混合態，在正常態時它採用普通的Linux的調度策略，在實時態只運行實時任務，在混合態實時和非實時任務都可以執行；實時態可以用於對於實時性要求比較嚴格的情況。

為了提高Linux系統的實時特性，必須提高系統所支持的時鍾精度。但如果僅僅簡單地提高時鍾頻率，會引起調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾， Kurt-Linux採用UTIME所使用的提高Linux系統中的時鍾精度的方法[UTIMEWeb]：它將時鍾晶元設置為單次觸發狀態（One shot mode），即每次給時鍾晶元設置一個超時時間，然後到該超時事件發生時在時鍾中斷處理程序中再次根據需要給時鍾晶元設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鍾中斷在我們需要的一個比較精確的時間發生，但並非一定需要系統時鍾頻率達到此精度。它利用CPU的時鍾計數器TSC (Time Stamp Counter)來提供精度可達CPU主頻的時間精度。

對於實時任務的調度，Kurt-Linux採用基於時間（TD）的靜態的實時CPU調度演算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度演算法對於那些循環執行的任務能夠取得較好的調度效果。

Kurt -Linux相對於RT-Linux的一個優點就是可以使用Linux系統自身的系統調用，它本來被設計用於提供對硬實時的支持，但由於它在實現上只是簡單的將Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基於Kurt-Linux的應用有：ARTS（ATM Reference Traffic System）、多媒體播放軟體等。另外Kurt-Linux所採用的這種方法需要頻繁地對時鍾晶元進行編程設置。

3.3. RED-Linux

RED -Linux是加州大學Irvine分校開發的實時Linux系統[REDWeb][ Wang99]，它將對實時調度的支持和Linux很好地實現在同一個操作系統內核中。它同時支持三種類型的調度演算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

為了提高系統的調度粒度，RED-Linux從RT-Linux那兒借鑒了軟體模擬中斷管理器的機制，並且提高了時鍾中斷頻率。當有硬體中斷到來時，RED-Linux的中斷模擬程序僅僅是簡單地將到來的中斷放到一個隊列中進行排隊，並不執行真正的中斷處理程序。

另外為了解決Linux進程在內核態不能被搶占的問題， RED-Linux在Linux內核的很多函數中插入了搶占點原語，使得進程在內核態時，也可以在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED-Linux的設計目標就是提供一個可以支持各種調度演算法的通用的調度框架，該系統給每個任務增加了如下幾項屬性，並將它們作為進程調度的依據：

Priority：作業的優先順序；

Start-Time：作業的開始時間；

Finish-Time：作業的結束時間；

Budget：作業在運行期間所要使用的資源的多少；

通過調整這些屬性的取值及調度程序按照什麼樣的優先順序來使用這些屬性值，幾乎可以實現所有的調度演算法。這樣的話，可以將三種不同的調度演算法無縫、統一地結合到了一起。

❻ 進程調度演算法模擬程序設計

public class PrivilegeProcess {
public static void main(String[] args) {
MyQueue myqueue = new MyQueue();//聲明隊列
PCB[] pcb = {new PCB(001,8,1),new PCB(002,7,9),new PCB(003,3,8),new PCB(004,1,7),new PCB(005,7,4)};
PCB para = new PCB();
for(int i=0;i<pcb.length;i++){//初始化後首先執行一次排序，這里使用的是選擇排序，優先順序高的先入隊
for(int j=i;j<pcb.length;j++){
if(pcb[i].privilege < pcb[j].privilege){
para = pcb[i];
pcb[i] = pcb[j];
pcb[j] = para;
}
}
}
System.out.println("初次入隊後各進程的順序：");
for(int i=0;i<pcb.length;i++){
System.out.println("初次入隊後 # processname : " + pcb[i].name + " totaltime : " + pcb[i].totaltime + " privilege :" + pcb[i].privilege);
}
System.out.println();
myqueue.start(pcb);
}
}

class MyQueue {
int index = 0;
PCB[] pc = new PCB[5];
PCB[] pc1 = new PCB[4];
PCB temp = new PCB();

public void enQueue(PCB process){//入隊演算法
if(index==5){
System.out.println("out of bounds !");
return;
}
pc[index] = process;
index++;
}

public PCB deQueue(){//出隊演算法
if(index==0)
return null;
for(int i=0;i<pc1.length;i++){
pc1[i] = pc[i+1];
}
index--;
temp = pc[0];
for(int i=0;i<pc1.length;i++){
pc[i] = pc1[i];
}
return temp;
}

public void start(PCB[] pc){//顯示進程表演算法
while(pc[0].isNotFinish==true||pc[1].isNotFinish==true||pc[2].isNotFinish==true||pc[3].isNotFinish==true||pc[4].isNotFinish==true){
//*注意：||運算符，所有表達式都為false結果才為false,否則為true
for(int i=0;i<pc.length;i++){
pc[i].run(this);
}
System.out.println();
for(int i=0;i<pc.length;i++){//所有進程每執行完一次時間片長度的運行就重新按優先順序排列一次
for(int j=i;j<pc.length;j++){
if(pc[i].privilege < pc[j].privilege){
temp = pc[i];
pc[i] = pc[j];
pc[j] = temp;
}
}
}
}
}
}

class PCB {//聲明進程類
int name,totaltime,runtime,privilege;
boolean isNotFinish;

public PCB(){

}

public PCB(int name, int totaltime, int privilege){
this.name = name;//進程名
this.totaltime = totaltime;//總時間
this.privilege = privilege;//優先順序別
this.runtime = 2;//時間片，這里設值為2
this.isNotFinish = true;//是否執行完畢
System.out.println("初始值： processname : " + name + " totaltime : " + totaltime + " privilege :" + privilege );
System.out.println();
}

public void run (MyQueue mq){//進程的基於時間片的執行演算法
if(totaltime>1){
totaltime-=runtime;//在總時間大於1的時候，總時間=總時間-時間片
privilege--;
System.out.println(" processname : " + name + " remaintime : " + totaltime + " privilege :" + privilege );
}else if(totaltime==1){
totaltime--;//在總時間為1時，執行時間為1
privilege--;
System.out.println(" processname : " + name + " remaintime : " + totaltime + " privilege :" + privilege );
}else{
isNotFinish = false;//總時間為0，將isNotFinish標記置為false
}
if(isNotFinish==true){
mq.deQueue();
mq.enQueue(this);
}
}
}

❼ 求進程調度先來先服務演算法，短進程優先演算法完整c語言代碼

/*（一）進程調度

進程調度演算法有FIFO，優先數調度演算法，時間片輪轉調度演算法，分級調度演算法，

輸入：進程流文件，其中存儲的是一系列要執行的進程，
每個作業包括三個數據項：
進程名 所需時間 優先數(0級最高)
輸出:
進程執行流 等待時間 平均等待時間

本程序包括:FIFO，優先數調度演算法，時間片輪轉調度演算法

進程流文件process_stream.txt
測試數據：
p0 16 2
p1 5 1
p2 4 3
p3 8 0
p4 9 4
p5 7 6

VC++調試通過
*/
#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <stdlib.h>

const int Quatum=2;//定義時間片的長度為2秒
const int MAXPCB=100;//定義最大進程數

//定義進程結構體
typedef struct node
{
char name[20];//進程名
int time; //進程運行時間
int privilege;//進程優先順序（靜態）
int finished;//進程完成標志，0-未完成，1-已完成
int wait_time;//進程等待時間
}pcb;

pcb pcbs[MAXPCB];
int quantiry;//進程流文件中的進程總數

void initial()
{
int i;
for (i=0;i<MAXPCB;i++)
{
strcpy(pcbs[i].name,"");
pcbs[i].time=0;
pcbs[i].privilege=0;
pcbs[i].finished=0;
pcbs[i].wait_time=0;
}
quantiry=0;
}

int readData()
{
FILE *fp;
char fname[20];
int i;
cout<<"請輸入進程流文件名:"<<endl;
cin>>fname;
if ((fp=fopen(fname,"r"))==NULL)
{
cout<<"錯誤,文件打不開，請檢查文件名"<<endl;
}
else
{
while (!feof(fp))
{
fscanf(fp,"%s %d %d %d",pcbs[quantiry].name,
&pcbs[quantiry].time,&pcbs[quantiry].privilege);
quantiry++;
}
//輸出所讀入得數據
cout<<"輸出所讀入的數據"<<endl;
cout<<"進程流文件中的進程總數="<<quantiry<<endl;
cout<<"進程名 所需時間 優先數"<<endl;

for (i=0;i<quantiry;i++)
{
cout<<" "<<pcbs[i].name<<" "<<pcbs[i].time<<" "<<pcbs[i].privilege<<endl;
}

return 1;
}

return 0;
}

//重置數據，以供另一個演算法使用
void init()
{
int i;
for (i=0;i<MAXPCB;i++)
{
pcbs[i].finished=0;
pcbs[i].wait_time=0;
}
}

void FIFO()
{
int i,j;

int total;
//輸出FIFO演算法執行流
cout<<endl<<"---------------------------------------------------------------"<<endl;
cout<<"FIFO演算法執行流:"<<endl;
cout<<"進程名 等待時間"<<endl;

for (i=0;i<quantiry;i++)
{
cout<<" "<<pcbs[i].name<<" "<<pcbs[i].wait_time<<endl;
for (j=i+1;j<quantiry;j++)
{
pcbs[j].wait_time+=pcbs[i].time;
}
}

total=0;
for (i=0;i<quantiry;i++)
{
total+=pcbs[i].wait_time;
}
cout<<"總等待時間:"<<total<<" "<<"平均等待時間:"<<total/quantiry<<endl;
}

//優先度調度演算法
void privilege()
{
int i,j,p;
int passed_time=0;
int total;

int queue[MAXPCB];
int current_privielege=1000;

for (i=0;i<quantiry;i++)
{
current_privielege=1000;
for (j=0;j<quantiry;j++)
{
if ((pcbs[j].finished==0)&&(pcbs[j].privilege<current_privielege))
{
p=j;
current_privielege=pcbs[j].privilege;
}
}
queue[i]=p;
pcbs[p].finished=1;
pcbs[p].wait_time+=passed_time;
passed_time+=pcbs[p].time;

}
//輸出優先數調度執行流
cout<<endl<<"-----------------------------------------"<<endl;
cout<<"優先數調度執行流:"<<endl;
cout<<"進程名 等待時間"<<endl;

for (i=0;i<quantiry;i++)
{
cout<<" "<<pcbs[queue[i]].name<<" "<<pcbs[queue[i]].wait_time<<"--"<<queue[i]<<endl;
}

total=0;
for (i=0;i<quantiry;i++)
{
total+=pcbs[i].wait_time;
}

cout<<"總等待時間:"<<total<<" 平均等待時間:"<<total/quantiry<<endl;
}

//時間片輪轉調度演算法
void timer()
{
int i,j,sum,flag=1;
int passed_time=0;
int max_time=0;
int round=0;

int queue[1000];
int total=0;

while(flag==1)
{
flag=0;
for (i=0;i<quantiry;i++)
{
if (pcbs[i].finished==0)
{
flag=1;
queue[total]=i;
total++;
if (pcbs[i].time<=Quatum*(round+1))
pcbs[i].finished=1;
}
}
round++;
}

cout<<endl<<"---------------------------------------------------------------"<<endl;
cout<<"時間片輪轉調度執行流:";
for(i=0;i<total;i++)
{
cout<<pcbs[queue[i]].name<<" ";
}
cout<<endl;
cout<<"進程名 結束時間 運行時間 等待時間"<<endl;

sum=0;

for (i=0;i<quantiry;i++)
{
for(j=total-1;j>=0;j--)//從輪轉調度執行流序列由後往前比較，找到同名進程即可計算其完成時間
{
if (strcmp(pcbs[queue[j]].name,pcbs[i].name)==0)
{
cout<<" "<<pcbs[i].name<<" "<<(j+1)*Quatum<<" ";
cout<<pcbs[i].time<<" "<<(j+1)*Quatum-pcbs[i].time<<endl;
sum+=(j+1)*Quatum-pcbs[i].time;
break;
}
}
}

cout<<"總等待時間:"<<sum<<" "<<"平均等待時間:"<<sum/quantiry<<endl;
}

//顯示版權信息函數
void version()
{
cout<<endl<<endl;

cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;
cout<<" ┃ 進程調度模擬系統 ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ version 2011 ┃"<<endl;
cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;
cout<<endl<<endl;
}
//主函數

int main()
{
int flag;
version();
initial();
flag=readData();
if(flag==1){
FIFO();
init();
privilege();
init();
timer();
}
cout<<endl;
system("pause");
return 0;
}

❽ 求進程調度演算法

進程調度源程序如下：

jingchendiao.cpp

#include "stdio.h"

#include <stdlib.h>

#include <conio.h>

#define getpch(type) (type*)malloc(sizeof(type))

#define NULL 0

struct pcb { /* 定義進程式控制制塊PCB */

char name[10];

char state;

int super;

int ntime;

int rtime;

struct pcb* link;

}*ready=NULL,*p;

typedef struct pcb PCB;

sort() /* 建立對進程進行優先順序排列函數*/

{

PCB *first, *second;

int insert=0;

if((ready==NULL)||((p->super)>(ready->super))) /*優先順序最大者,插入隊首*/

{

p->link=ready;

ready=p;

}

else /* 進程比較優先順序,插入適當的位置中*/

{

first=ready;

second=first->link;

while(second!=NULL)

{

if((p->super)>(second->super)) /*若插入進程比當前進程優先數大,*/

{ /*插入到當前進程前面*/

p->link=second;

first->link=p;

second=NULL;

insert=1;

}

else /* 插入進程優先數最低,則插入到隊尾*/

{

first=first->link;

second=second->link;

}

}

if(insert==0) first->link=p;

}

}

input() /* 建立進程式控制制塊函數*/

{

int i,num;

clrscr(); /*清屏*/

printf("\n 請輸入進程號?");

scanf("%d",&num);

for(i=0;i<num;i++)

{

printf("\n 進程號No.%d:\n",i);

p=getpch(PCB);

printf("\n 輸入進程名:");

scanf("%s",p->name);

printf("\n 輸入進程優先數:");

scanf("%d",&p->super);

printf("\n 輸入進程運行時間:");

scanf("%d",&p->ntime);

printf("\n");

p->rtime=0;p->state='w';

p->link=NULL;

sort(); /* 調用sort函數*/

}

}

int space()

{

int l=0; PCB* pr=ready;

while(pr!=NULL)

{

l++;

pr=pr->link;

}

return(l);

}

disp(PCB * pr) /*建立進程顯示函數,用於顯示當前進程*/

{

printf("\n qname \t state \t super \t ndtime \t runtime \n");

printf("|%s\t",pr->name);

printf("|%c\t",pr->state);

printf("|%d\t",pr->super);

printf("|%d\t",pr->ntime);

printf("|%d\t",pr->rtime);

printf("\n");

}
check() /* 建立進程查看函數 */

{

PCB* pr;

printf("\n **** 當前正在運行的進程是:%s",p->name); /*顯示當前運行進程*/

disp(p);

pr=ready;

printf("\n ****當前就緒隊列狀態為:\n"); /*顯示就緒隊列狀態*/

while(pr!=NULL)

{

disp(pr);

pr=pr->link;

}

}

destroy() /*建立進程撤消函數(進程運行結束,撤消進程)*/

{

printf("\n 進程 [%s] 已完成.\n",p->name);

free(p);

}

running() /* 建立進程就緒函數(進程運行時間到,置就緒狀態*/

{

(p->rtime)++;

if(p->rtime==p->ntime)

destroy(); /* 調用destroy函數*/

else

{

(p->super)--;

p->state='w';

sort(); /*調用sort函數*/

}

}

main() /*主函數*/

{

int len,h=0;

char ch;

input();

len=space();

while((len!=0)&&(ready!=NULL))

{

ch=getchar();

h++;

printf("\n The execute number:%d \n",h);

p=ready;

ready=p->link;

p->link=NULL;

p->state='R';

check();

running();

printf("\n 按任一鍵繼續......");

ch=getchar();

}

printf("\n\n 進程已經完成.\n");

ch=getchar();

}