第一篇：常用進程調(diào)度算法的分析與評價
常用進程調(diào)度算法的分析與評價
（一）2009-10-31 22:48
進程調(diào)度是按照某種調(diào)度算法從就緒狀態(tài)的進程中選擇一個進程到處理機上運行。進程調(diào)度的兩種方式 ：
(1)非搶占調(diào)度方式
在這種調(diào)度方式中，OS一旦把處理機分配給某個就緒狀態(tài)的進程后，就讓該進程一直執(zhí)行下去，直至該進程完成或由于該進程等待某事件發(fā)生而被阻塞時，才把處理機分配給其他進程。
(2)搶占調(diào)度方式
在這種調(diào)度方式中，進程調(diào)度程序可根據(jù)某種原則停止正在執(zhí)行的進程，將已分配給當前進程的處理機收回，重新分配給另一個處于就緒狀態(tài)的進程。
搶占進程調(diào)度的原則：
（1）時間片原則：各進程按系統(tǒng)分配給的一個時間片運行，當該時間片用完或由于該進程等待某事件發(fā)生而被阻塞時，系統(tǒng)就停止該進程的執(zhí)行而重新進行調(diào)度。
（2）優(yōu)先級原則：每個進程均賦于一個調(diào)度優(yōu)先級，通常一些重要和緊急的進程賦于較高的優(yōu)先級。當一個新的緊迫進程到達時，或者一個優(yōu)先級高的進程從阻塞狀態(tài)變成就緒狀態(tài)的時，如果該進程的優(yōu)先級比當前進程的優(yōu)先級高，OS就停止當前進程的執(zhí)行，將處理機分配給該優(yōu)先級高的進程，使之執(zhí)行。
（3）短進程優(yōu)先原則：當新到達的作業(yè)對應(yīng)的進程比正在執(zhí)行的作業(yè)對應(yīng)進程的運行時間明顯短時，系統(tǒng)剝奪當前進程的執(zhí)行，而將處理機分配給新的短進程，使之優(yōu)先執(zhí)行。進程調(diào)度算法評價依據(jù)
進程調(diào)度性能的衡量方法可以分為定性和定量兩種，在定性衡量方面，首先是調(diào)度的安全性。比如，一次進程調(diào)度是否可能引起數(shù)據(jù)結(jié)構(gòu)的破壞等。這要求對調(diào)度時機的選擇和保存CPU現(xiàn)場十分小心。另外，系統(tǒng)開銷也是衡量進程調(diào)度的一個重要指標，由于調(diào)度程序的執(zhí)行涉及到多個進程的上下文切換，如果調(diào)度策略過于繁瑣和復(fù)雜，將會耗去較大的系統(tǒng)開銷。這在用戶進程調(diào)度系統(tǒng)調(diào)用較多的情況下，將會造成響應(yīng)時間大幅度增加。
進程調(diào)度的定量評價包括CPU的利用率評價、進程在就緒隊列中的等待時間與執(zhí)行時間之比等。實際上，由于進程進入就緒隊列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執(zhí)行效率，從而對進程調(diào)度進行解析是很困難的，一般情況下，大多利用模擬或測試系統(tǒng)響應(yīng)時間的方法來評價進程調(diào)度的性能。
常用進程調(diào)度算法的分析與評價
（二）2009-11-01 20:22
四種常用進程調(diào)度算法的分析與評價
3.1 先來先服務(wù)算法
3.1.1 算法思想
該算法思想是按照進入就緒隊列的先后次序來分配處理機。FCFS采用非剝奪調(diào)度方式，即
一旦某個進程占有處理機，就一直運行下去，直到該進程完成其工作或因等待某一事件而不能繼續(xù)執(zhí)行時才釋放處理機。
3.1.2 算法實現(xiàn)原理圖
該算法實現(xiàn)原理圖如圖1所示。
說明：Ready表示就緒隊列，Pi表示新進入隊列的進程，F(xiàn)inish表示進程運行完畢退出。
3.1.3 算法分析與評價
① 該算法原理簡單，易于實現(xiàn)。
② 各進程平等競爭。
③ 由于各進程執(zhí)行的時間不一樣，從而導(dǎo)致相對不公平現(xiàn)象的產(chǎn)生。
④ 該算法有利于長進程，不利于短進程。
⑤ 該算法很少用來作為主調(diào)度策略，常常用作輔助調(diào)度算法使用
3.2最高優(yōu)先權(quán)優(yōu)先調(diào)度算法
3.2.1 算法思想
該算法的基本思想是進程優(yōu)先權(quán)高者優(yōu)先調(diào)度，是一種最常用的進程調(diào)度算法。該算法的關(guān)鍵是如何確定優(yōu)先數(shù)。通常確定優(yōu)先數(shù)的方法有兩種，即靜態(tài)法和動態(tài)法。
靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，其運行特征是優(yōu)先數(shù)確定之后在整個進行運行期間不再改變。確定靜態(tài)優(yōu)先權(quán)的依據(jù)有進程的類型、進程所使用的資源、進程的估計運行時間等因素。進程所申請的資源越多，估計的運行時間越長，進程的優(yōu)先權(quán)越低。進程類型不同，優(yōu)先權(quán)也不同，如系統(tǒng)進程的優(yōu)先權(quán)高于用戶進程的優(yōu)先權(quán)。
動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進程時，其運行特征是根據(jù)系統(tǒng)資源的使用情況和進程的當前特點確定一個優(yōu)先權(quán)，在進程運行過程中再根據(jù)情況的變化調(diào)整優(yōu)先權(quán)。動態(tài)優(yōu)先權(quán)一般根據(jù)進程占有CPU時間的長短、進程等待CPU時間的長短等因素確定。占有處理機的時間越長，則優(yōu)先權(quán)越低；等待時間越長，則優(yōu)先權(quán)越高。
3.3.2 算法分析與評價
① 靜態(tài)優(yōu)先級調(diào)度算法實現(xiàn)較為簡單，但不能反映系統(tǒng)以及進程在運行過程中發(fā)生的各種變化。而動態(tài)優(yōu)先級法可以滿足這個方面的需要。
② 動態(tài)優(yōu)先級調(diào)度算法的性能一般介于時間片輪轉(zhuǎn)算法和先來先服務(wù)算法之間。
常用進程調(diào)度算法的分析與評價
（三）2009-11-01 20:23
3.3時間片輪轉(zhuǎn)調(diào)度算法
3.3.1 算法思想
該算法思想是使每個進程在就緒隊列中的等待時間與享受服務(wù)的時間成比例。即將CPU的處理時間分成固定大小的時間片，如果在執(zhí)行的一個進程把它分給它的時間片用完了，但任務(wù)還沒有完成，則它也只能停止下來，釋放它所占的CPU資源，然后排在相應(yīng)的就緒隊列的后面去。
3.3.2 算法實現(xiàn)原理圖
該算法實現(xiàn)原理圖如圖2所示
說明：Ready表示就緒隊列，Pi表示新進入隊列的進程，F(xiàn)inish表示進程運行完畢退出。Not Finish表示分配給某進程的時間片已用完但任務(wù)還沒有完成，從而插入到Ready隊列尾部。
3.3.3 算法分析與評價
① 時間片的長度選擇比較困難
時間片的長度選擇比較困難是因為時間片長度的選擇直接關(guān)系到系統(tǒng)開銷和進程的響應(yīng)時間。如果時間片長度過短→導(dǎo)致調(diào)度程序剝奪處理器的次數(shù)增加→進程的上下文切換的次數(shù)增加→系統(tǒng)的開銷也加重；如果時間片長度過長，長到能使就緒隊列中所需要執(zhí)行時間最長的進程執(zhí)行完
畢→輪轉(zhuǎn)法就變成了FCFS算法→FCFS短處不足就顯示出來了。
又因為CPU的整個執(zhí)行時間＝各進程執(zhí)行時間之和＋系統(tǒng)開銷（各進程切換所花費的CPU時間之和，假定存儲開銷忽略不計）。即。因此，時間片的長短通常需要由以下因素確定：↙系統(tǒng)的響應(yīng)時間。
↙就緒隊列中的進程數(shù)。
↙進程的切換時間。
↙ 計算機的處理能力，計算機的速度越高，時間片就可越短。
② 時間片長度選擇的動態(tài)性
以上僅僅作了靜態(tài)分析，通常情況下，就緒隊列里地進程個數(shù)是不斷變化的。因此，每一次的調(diào)度都需要計算新一輪的時間片長度，不能用固定的時間片長度來進行所有進程的輪轉(zhuǎn)執(zhí)行。③ 該算法的擴充——多級反饋輪轉(zhuǎn)法
在上面的算法中，未對就緒隊列中的進程加以條件分析（即進入就緒隊列的因素），由于進入就緒隊列的原因不一樣，要求占用處理機的緊急程度也不一樣。主要因素有：↙分給該進程的時間片用完，但進程還未完成。
↙ 分給其時間片未用完，而發(fā)生了I/O等請求后由阻塞態(tài)轉(zhuǎn)變成就緒態(tài)。
↙新的進程進入。
因此，根據(jù)緊急程度的不一樣，建立多個就緒隊列，同時賦予不同的的優(yōu)先級，優(yōu)先權(quán)高的就緒隊列優(yōu)先執(zhí)行，同一就緒隊列中，優(yōu)先級相同，按照先來先服務(wù)進行調(diào)度，運行一個給定的時間片，如果沒有執(zhí)行完成則轉(zhuǎn)入到相應(yīng)的就緒隊列中去（運行一次，優(yōu)先級降低一個等級，等待一個時間片，則優(yōu)先級升高一個等級）。其實現(xiàn)原理圖如圖3所示。
3.4 短進程優(yōu)先調(diào)度算法
3.4.1 算法思想
該算法的基本思想是從就緒隊列（內(nèi)存）中選擇一個估計運行時間最短的進程，將處理機分配給它。
3.4.2 算法分析與評價
① 該算法能有效降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。
② 對長進程不利，甚至導(dǎo)致長期得不到處理。
③ 該算法完全未考慮進程的緊迫程度。
④ 進程的長短通常由某種策略估計提供，不能做到真正的短進程優(yōu)先。
4結(jié)語
綜述所述，本文從算法思想、算法的實現(xiàn)原理、算法的優(yōu)缺點等幾個方面對先來先服務(wù)算法、時間片輪轉(zhuǎn)算法、最高優(yōu)先權(quán)優(yōu)先調(diào)度算法、短進程優(yōu)先調(diào)度算法等四種進程調(diào)度算法進行詳細地論述。（轉(zhuǎn)自《計算機與信息技術(shù)》）
第二篇：操作系統(tǒng)進程調(diào)度算法模擬實驗報告
進程調(diào)度算法模擬
專業(yè)：XXXXX 學號：XXXXX 姓名：XXX 實驗日期：20XX年XX月XX日
一、實驗?zāi)康?/p>
通過對進程調(diào)度算法的模擬加深對進程概念和進程調(diào)度算法的理解。
二、實驗要求
編寫程序?qū)崿F(xiàn)對5個進程的調(diào)度模擬，要求至少采用兩種不同的調(diào)度算法分別進行模擬調(diào)度。
三、實驗方法內(nèi)容
1.算法設(shè)計思路
將每個進程抽象成一個控制塊PCB，PCB用一個結(jié)構(gòu)體描述。
構(gòu)建一個進程調(diào)度類。將進程調(diào)度的各種算法分裝在一個類中。類中存在三個容器，一個保存正在或未進入就緒隊列的進程，一個保存就緒的進程，另一個保存已完成的進程。還有一個PCB實例。主要保存正在運行的進程。類中其他方法都是圍繞這三個容器可以這個運行中的PCB展開。
主要用到的技術(shù)是STL中的vector以維護和保存進程容器、就緒容器、完成容器。
當程序啟動時，用戶可以選擇不同的調(diào)度算法。然后用戶從控制臺輸入各個進程的信息，這些信息保存到進程容器中。進程信息輸入完畢后，就開始了進程調(diào)度，每調(diào)度一次判斷就緒隊列是否為空，若為空則系統(tǒng)時間加一個時間片。判斷進程容器中是否有新的進程可以加入就緒隊列。2.算法流程圖 主程序的框架：
開始void FCFS();//先來先服務(wù)void SJF();//最短進程優(yōu)先調(diào)度void RR();//簡單時間片輪轉(zhuǎn)void PD();//最高優(yōu)先數(shù)優(yōu)先void PCBInput();//輸入進程信息選擇調(diào)度算法輸入進程信息將輸入容器中以滿足進入條件的進程調(diào)入就緒隊列void ProcessQueueProcess();//查看當前時間下，有無進程加入。若有則把該進程調(diào)入就緒隊列按照選擇的算法開始選擇就緒隊列的進程開始執(zhí)行void ProcessSelect();//若當前就緒隊列不為空則根據(jù)選擇的調(diào)度算法開始調(diào)度,否則，系統(tǒng)時間加一個時間片.以等待新的進程到判斷就緒容器和輸入容器是否為空!processScheduler.m_WaitQueue.empty()||!processScheduler.m_ProcessQueue.empt()Y打印各進程信息進行統(tǒng)計計算周轉(zhuǎn)時間等結(jié)束void PCBDisplay();//打印當前狀況下。就緒隊列、完成隊列、運行中的進程信息void SchedulerStatistics();//調(diào)度統(tǒng)計，計算周轉(zhuǎn)時間等進程調(diào)度過程：
開始為空判斷就緒隊列是否為空if(m_WaitQueue.empty())非空讓系統(tǒng)等待一個時間片TimePast()根據(jù)設(shè)定的調(diào)度算法從就緒隊列中調(diào)入一個進程并執(zhí)行（此時進程從就緒隊列中刪除，賦值到表示運行中的成員變量中）void FCFS();//先來先服務(wù)void SJF();//最短進程優(yōu)先調(diào)度void RR();//簡單時間片輪轉(zhuǎn)void PD();//最高優(yōu)先數(shù)優(yōu)先進程運行一個時間片N是否達到該進程停止運行的條件Y選入的進程狀態(tài)是否為“完成”如進程已完成，或者分得的時間片個數(shù)已到ProcessRun()Yvector
m_WaitQueue;//進程就緒隊列進程未完成，將進程優(yōu)先數(shù)減一，并放回到就緒隊列中設(shè)置進程完成時間，將該進程放入完成隊列vector
m_FinishQueue;//完成隊列結(jié)束
3.算法中用到的數(shù)據(jù)結(jié)構(gòu)
struct fcfs{
//先來先服務(wù)算法從這里開始
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
};
//定義一個結(jié)構(gòu)體，里面包含的有一個進程相關(guān)的信息
4.主要的常量變量
vector
m_ProcessQueue;//進程輸入隊列
vector
m_WaitQueue;//進程就緒隊列 vector
m_FinishQueue;//完成隊列 vector
::iterator m_iter;//迭代器 PCB m_runProcess;//運行中的進程
int m_ProcessCount;//進程數(shù) float m_RunTime;//運行時間
int m_tagIsRun;//是否在運行標志。表示正在運行，表示沒有 float m_TimeSlice;//時間片大小
int m_TimeSliceCount;//指時間片輪轉(zhuǎn)中一次分到的時間片個數(shù) char m_SchedulerAlgorithm;//調(diào)度算法
5.主要模塊
void PCBInput();//輸入進程信息
void PCBSort();//對進程控制塊按照優(yōu)先級排序(采用冒泡排序)void ProcessSelect();//若當前就緒隊列不為空則根據(jù)選擇的調(diào)度算法開始調(diào)度。否則，系統(tǒng)時間void PCBDisplay();//打印當前狀況下。就緒隊列、完成隊列、運行中的進程信息
void ProcessRun();//進程運行一次。運行時間加個時間片。并判斷進程是否達到完成條件。若是則void ProcessQueueProcess();//查看當前時間下，有無進程加入。若有則把該進程調(diào)入就緒隊列 void ProcessDispatch();//進程分派，進程執(zhí)行完成后決定進程該進入哪個隊列(就緒、完成)void TimePast(){ m_RunTime +=m_TimeSlice;ProcessQueueProcess();}//當前系統(tǒng)時間加個時間void SchedulerStatistics();//調(diào)度統(tǒng)計，計算周轉(zhuǎn)時間等 void FCFS();//先來先服務(wù) void SJF();//最短進程優(yōu)先調(diào)度 void RR();//簡單時間片輪轉(zhuǎn) void PD();//最高優(yōu)先數(shù)優(yōu)先 加.以等待新的進程到來
ProcessStatus='f'.否則為'w';片，并檢查是否有新的進程加入
四、實驗代碼
#include
using namespace std;
struct fcfs{
//先來先服務(wù)算法從這里開始
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
};
//定義一個結(jié)構(gòu)體，里面包含的有一個進程相關(guān)的信息
fcfs a[100];
void input(fcfs *p,int N)
{
int i;
cout< printf(“ 請您輸入進程的名字 到達時間 服務(wù)時間:(例如: a 0 100)nn”); for(i=0;i<=N-1;i++) { printf(“ 請您輸入進程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime); } } void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) { int k; printf(“nn調(diào)用先來先服務(wù)算法以后進程運行的順序是: ”); printf(“%s”,p[0].name); for(k=1;k { printf(“-->%s”,p[k].name); } cout< printf(“n 具體進程調(diào)度信息:n”); printf(“t進程名 到達時間 服務(wù)時間 開始時間 結(jié)束時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間n”); for(k=0;k<=N-1;k++) { printf(“t%st%-.2ft %-.2ft %-.2ft %-.2ft %-.2ft %-.2fn”,p[k].name,p[k].arrivetime，p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } getchar(); //此處必須要有這個函數(shù)，否則就看不到顯示器上面的輸出，可以看到的結(jié)果只是一閃而過的一個框剪 } void sort(fcfs *p,int N)//排序 { for(int i=0;i<=N-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { fcfs temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //運行階段 { int k; for(k=0;k<=N-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} } for(k=0;k<=N-1;k++) { p[k].zztime=p[k].finishtime-p[k].arrivetime; p[k].dqzztime=p[k].zztime/p[k].servicetime; } } void FCFS(fcfs *p,int N) { float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); getchar(); } //先來先服務(wù)算法到此結(jié)束 struct sjf{//最短進程優(yōu)先調(diào)度算法從這里開始 char name[10];float arrivetime;//到達時間 float servicetime;//運行時間 float starttime; //開始時間 float finishtime; //完成時間 };sjf a1[100]; void input(sjf *p,int N1)//進程信息輸入 { int i;cout< printf(“ 請您輸入進程的名字 到達時間 服務(wù)時間:(例如: a 0 100)n”); for(i=0;i<=N1-1;i++){ printf(“ 請您輸入進程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} } void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)//最終結(jié)果輸出 { int k; printf(“nt調(diào)用最短進程優(yōu)先調(diào)度算法以后進程的調(diào)度順序為:”); printf(“%s”,p[0].name); for(k=1;k {printf(“-->%s”,p[k].name);} cout< printf(“n給個進程具體調(diào)度信息如下:n”); printf(“nt進程名t到達時間t運行時間t開始時間t完成時間n”); for(k=0;k<=N1-1;k++) { printf(“ t%st %-.2ftt %-.2ftt %-.2ftt %-.2ftn”,p[k].name,p[k].arrivetime，p[k].servicetime,p[k].starttime,p[k].finishtime); } getchar(); } void sort(sjf *p,int N1)//排序 { for(int i=0;i<=N1-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { sjf temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//運行階段 { int k; for(k=0;k<=N1-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+float(p[k].servicetime)/60;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+float(p[k].servicetime)/60;} } } void sjff(sjf *p,int N1){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0; sort(p,N1); for(int m=0;m {if(m==0) p[m].finishtime=p[m].arrivetime+float(p[m].servicetime)/60; else p[m].finishtime=p[m-1].finishtime+float(p[m].servicetime)/60; int i=0; for(int n=m+1;n<=N1-1;n++) { if(p[n].arrivetime<=p[m].finishtime) i++; } float min=p[m+1].servicetime; int next=m+1; for(int k=m+1;k { if(p[k+1].servicetime {min=p[k+1].servicetime; next=k+1;} } sjf temp; temp=p[m+1]; p[m+1]=p[next]; p[next]=temp; } deal(p,arrivetime,servicetime,starttime,finishtime,N1); Print(p,arrivetime,servicetime,starttime,finishtime,N1); getchar();}//最短進程優(yōu)先調(diào)度算法到這里結(jié)束 char menu()//用來輸出相關(guān)信息的函數(shù) { char cse1; while(1) { system(“cls”); fflush(stdin); cout< cout< cout<<“t”<<“|| <<<<<<<<<<<<歡<<<<<<<<<<< >>>>>>>>>>>>迎>>>>>>>>>>> ||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“t 進程調(diào)度算法模擬”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 1.先來先服務(wù)調(diào)度算法 ”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 2.最短進程優(yōu)先調(diào)度算法”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“|| <<<<<<<<<<<<<<<<<<<<<<<<<您>>>>>>>>>>>>>>>>>>>>>>>>> ||”< cout< cout< cout<<“tt 請輸入您的選擇（1/2）：”; cse1=getchar(); if(cse1<'1'||cse1>'2') cout<<“你的輸入有錯！”< else break; } return cse1;} int main(int argc, char *argv[]){ while(1) { switch(menu()) { case '1': int N; cout< cout< printf(“tt<<---！!@@@先來先服務(wù)調(diào)度算法@@@！!--->>n”); cout< printf(“輸入進程數(shù)目:”); scanf(“%d”,&N); input(a,N); FCFS(a,N); case '2': int N1; cout< cout< printf(“tt<<---！!@@@最短進程優(yōu)先調(diào)度算法@@@！!--->>n”); cout< printf(“輸入進程數(shù)目: ”); scanf(“%d”,&N1); input(a1,N1); sjf *b=a1; sjf *c=a1; sjff(b,N1); getchar(); } } system(“PAUSE”); return EXIT_SUCCESS;} 五、實驗結(jié)果 1.執(zhí)行結(jié)果 2.結(jié)果分析 先來先服務(wù)調(diào)度算法就是根據(jù)進程達到的時間為依據(jù)，哪一個進程先來那么該進程就會先執(zhí)行；最短進程優(yōu)先調(diào)度算法則是以每個進程執(zhí)行所需時間長短為依據(jù)，某一個進程執(zhí)行所需花的時間要短些那么該進程就先執(zhí)行。以上就是本次進程調(diào)度實驗的依據(jù)。 六、實驗總結(jié) 通過本次實驗了解到算法很重要，又更加明白算法本身可以節(jié)約時間，而且不同的函數(shù)之間在調(diào)用的時候要注意很多的問題。 操作系統(tǒng)課程設(shè)計 進 程 調(diào) 度 實 踐 報 告 姓名： 董宇超 班級：計算機一班 學號：0906010124 目錄： ? 實踐內(nèi)容 ? 實踐目的及意義 ? 功能設(shè)計及數(shù)據(jù)結(jié)構(gòu) ? 調(diào)試運行及測設(shè)分析 ? 存在的問題及改進設(shè)想 ? 實踐體會 ? 總結(jié) ? 參考文獻 正文： 1.實踐內(nèi)容： 2.3.在多道程序運行環(huán)境下，進程數(shù)目一般多于處理機數(shù)目，使得進程要通過競爭來使用處理機。這就要求系統(tǒng)能按某種算法，動態(tài)地把處理機分配給就緒隊列中的一個進程，使之運行，分配處理機的任務(wù)是由進程調(diào)度程序完成的。一個進程被創(chuàng)建后，系統(tǒng)為了便于對進程進行管理，將系統(tǒng)中的所有進程按其狀態(tài)，將其組織成不同的進程隊列。于是系統(tǒng)中有運行進程隊列、就緒隊列和各種事件的進程等待隊列。進程調(diào)度的功能就是從就緒隊列中挑選一個 進程到處理機上運行。進程調(diào)度的算法有多種，常用的有先來先服務(wù)算法、時間片輪轉(zhuǎn)算法。 采用先來先服務(wù)及時間片輪轉(zhuǎn)算法進行進程調(diào)度，編程模擬。實踐目的： ·要求設(shè)計并實現(xiàn)模擬進程調(diào)度的算法：時間片輪轉(zhuǎn)及先來先服務(wù)。·理解進程控制塊的結(jié)構(gòu)。·理解進程運行的并發(fā)性。·掌握進程調(diào)度算法。功能設(shè)計： 1)數(shù)據(jù)結(jié)構(gòu)： class PCB { string ProcessName;// 進程名字 int Time;// 進程需要時間 int LeftTime;// 進程運行一段時間后還需要的時間 } 2)功能函數(shù)： void Copy(Process proc1, Process proc2);// 把proc2賦值給proc1 void sort(Process pr[], int size);// 此排序后按需要的cpu 時間從小到大排列 void Fcfs(Process pr[], int num);// 先來先服務(wù)算法 void TimeTurn(Process process[], int num, int Timepice);// 時 間片輪轉(zhuǎn)算法 源代碼： #include }; void Copy(PCB proc1, PCB proc2);// 把proc2賦值給proc1 void sort(PCB pr[], int size);// 此排序后按需要的cpu時間從小到大排列 void Fcfs(PCB pr[], int num);// 先來先服務(wù)算法 void TimeTurn(PCB process[], int num, int Timepice);// 時間片輪轉(zhuǎn)算法 void main(){ int a;cout< process[Size];int num;int TimePice; cout<<“輸入進程個數(shù):”< } for(int i=0;i< num;i++)//輸入進程信息 { } for(int k=0;k cout< int LeftTime;// 進程運行一段時間后還需要的時間 } { } else if(a==2)//時間片輪轉(zhuǎn)調(diào)度 { } cout<<“進程名”<<“ 剩余時間”<<“ 狀態(tài)”< CPU時間 ”<<“ 狀態(tài)”< } void sort(PCB pr[], int size)// 以進程時間從低到高排序 {// 直接插入排序 } /* 先來先服務(wù)算法的實現(xiàn)*/ void Fcfs(PCB process[], int num){ // process[] 是輸入的進程，num是進程的數(shù)目 while(true){ if(num==0){ } if(process[0].LeftTime==0)//由于第一個進程總是在運行，所以每次都只判斷process[0].LeftTime { cout<<“ 所有進程都已經(jīng)執(zhí)行完畢!”< } PCB temp;temp = pr[i];int j=i; while(j>0 && temp.Time < pr[j-1].Time){ } pr[j] = temp;pr[j] = pr[j-1];j--;proc1.ProcessName =proc2.ProcessName;proc1.Time =proc2.Time; } } cout<<“ 進程”< } else if(process[0].LeftTime > 0){ cout< 運行”;cout< for(int s=1;s } cout<<“ ”< “< 等待”< /* 時間片輪轉(zhuǎn)調(diào)度算法實現(xiàn)*/ void TimeTurn(PCB process[], int num, int Timepice){ while(true){ if(num==0){ } if(process[0].LeftTime==0)//由于第一個進程總是在運行，所以每次都只判斷process[0].LeftTime { cout<<“ 進程”< } } num--;if(process[num-1].LeftTime ==0){ } else if(process[0].LeftTime > 0){ cout< } PCB temp;//中間變量 temp = process[0];for(int j=0;j 等待”< 就緒”< process[0].LeftTime=process[0].LeftTime-Timepice;if(process[0].LeftTime<=0)//當剩余時間小于零時，做零處理 process[0].LeftTime=0;cout<<“ ”< “< 運行”< for(int s=1;s cout<<” 進程“ << process[num-1].ProcessName <<” 已經(jīng)執(zhí)行完畢!"< } // while 4.調(diào)試運行： 運行開始后出現(xiàn)如下界面： 按提示選擇1/2； ? 先選1，進行FCFS調(diào)度： ? 若選2，進行時間片輪轉(zhuǎn)調(diào)度： 5.存在的問題： 由于初次做操作系統(tǒng)模擬實驗，所以程序設(shè)計中存在很多問題，例如定義好PCB后，各種指針的使用，使得程序甚是復(fù)雜，再加上隊列指針，而且指針錯誤在調(diào)試的時候不提示錯誤，只是編好的程序看似沒有錯誤，卻在執(zhí)行時出現(xiàn)異常而中斷，由于使用指針使得程序龐大檢查改正困難，無法發(fā)現(xiàn)隱藏的錯誤，只是程序無法進行下去。 最終本程序選擇數(shù)組保存PCB信息，存儲和調(diào)用都簡單化。 改進之處：學習指針，并且使用三個隊列，就緒隊列，運行隊列，完成隊列，使得進程調(diào)度模擬更加清晰。 還有一些簡單的以解決的問題，不一一列舉了。 6.實踐心得體會： 通過這次實踐學會了不少內(nèi)容，更深的理解了進程調(diào)度的幾種算法，而且學 會了系統(tǒng)的編寫程序，而不是只編寫幾個功能函數(shù)。在編程過程中，需要 查閱各種資料，并且學習前人的編寫方法，找出優(yōu)劣，然后形成自己的思想，最終完成程序的編寫。 通過模擬進程調(diào)度的兩種算法，懂得了各種算法在不同情況下的作用。選擇 一個好的調(diào)度算法可以是計算機在執(zhí)行龐大的作業(yè)時井井有條，并且使用時 間很短。 在模擬過程中出現(xiàn)過好多問題，有的解決了，有的還未解決，不管如何都是 一種收獲，編寫功能函數(shù)時總會出現(xiàn)參數(shù)調(diào)用錯誤的情況，通過分析解決了。在指針指向的問題上，覺得很復(fù)雜，最終沒有解決。 7.總結(jié)： 為期一周的操作系統(tǒng)實踐課結(jié)束了，編寫了包含有兩種調(diào)度算法的進程 調(diào)度模擬程序，兩種程序各有優(yōu)劣，F(xiàn)CFS調(diào)度算法是按照進程進入系統(tǒng)的時 間先后被CPU選擇創(chuàng)建的，這種算法易于實現(xiàn)，但效率不高，只顧及到進程 的等候時間，沒考慮要求服務(wù)的時間長短，相比SJF算法不利于較短的作業(yè)。本程序的另一種調(diào)度算法是RR算法，它在調(diào)度是是為每個進程分配時間片，當時間片用完時，進程便排到隊尾以便下次分配，這種調(diào)度策略可以防止那 些很少使用設(shè)備的進程長時間占用處理器，導(dǎo)致要使用設(shè)備的那些進程沒機 會啟動設(shè)備。 在編寫程序的同時，還學習了進程調(diào)度的其他算法，明白了它們各自的優(yōu)劣，懂得了計算機在調(diào)度進程時的取舍。 8.參考文獻： 1.操作系統(tǒng)教程（第4版）…………孫鐘秀 主編 高等教育出版社； 2.算法與數(shù)據(jù)結(jié)構(gòu)-C語言描述（第2版）……張乃孝 主編 高等教育出版社； 3.網(wǎng)絡(luò)資源； 天津大學仁愛學院 實驗類型：實驗名稱：實驗地點： 學生姓名：班 級： 操作系統(tǒng) 實驗報告 必 修 實驗日期：2014年4月18日進程調(diào)度 二實驗樓504 李帥帥 指導(dǎo)教師：張 磊 計科一班 計算機科學與技術(shù)系 天津大學仁愛學院——計算機科學與技術(shù)系——李帥帥 實驗報告內(nèi)容： 1）實驗?zāi)康?/p> 用c語言編寫和調(diào)試一個進程調(diào)度程序，以加深對進程的概念及進程調(diào)度算法的理解。 2）實驗器材和設(shè)備 硬 件： 二實驗樓504計算機 開發(fā)工具： Microsoft Visual C++ 6.0 3）實驗任務(wù) 本實驗?zāi)M單處理器系統(tǒng)的進程調(diào)度，加深對進程的概念及進程調(diào)度算法的理解。用c語言編寫和調(diào)試一個進程調(diào)度的算法程序，有一些簡單的界面，能夠運行，仿真操作系統(tǒng)中進程調(diào)度的原理和過程。通過對調(diào)度算法的模擬，進一步理解進程的基本概念，加深對進程運行狀態(tài)和進程調(diào)度 4）實驗原理 無論是在批處理系統(tǒng)還是分時系統(tǒng)中，用戶進程數(shù)一般都多于處理機數(shù)、這將導(dǎo)致它們互相爭奪處理機。另外，系統(tǒng)進程也同樣需要使用處理機。這就要求進程調(diào)度程序按一定的策略，動態(tài)地把處理機分配給處于就緒隊列中的某一個進程，以使之執(zhí)行。 基本狀態(tài)：1.等待態(tài)：等待某個事件的完成； 2.就緒態(tài)：等待系統(tǒng)分配處理器以便運行； 3.運行態(tài)：占有處理器正在運行。 運行態(tài)→等待態(tài) 往往是由于等待外設(shè)，等待主存等資源分配或等待人工干預(yù)而引起的。 等待態(tài)→就緒態(tài) 則是等待的條件已滿足，只需分配到處理器后就能運行。運行態(tài)→就緒態(tài) 不是由于自身原因，而是由外界原因使運行狀態(tài)的進程讓出處理器，這時候就變成就緒態(tài)。例如時間片用完，或有更高優(yōu)先級的進程來搶占處理器等。 就緒態(tài)→運行態(tài) 系統(tǒng)按某種策略選中就緒隊列中的一個進程占用處理器，此時就變成了運行態(tài) 5）實驗過程描述 a)打開Microsoft Visual C++ 6.0，創(chuàng)建工程。 b)根據(jù)要求用 c語言代碼實現(xiàn)應(yīng)用程序，并調(diào)試完成。c)運行程序，根據(jù)提示輸入相應(yīng)的字符。 d)輸入實驗測試內(nèi)容，并觀察執(zhí)行窗口顯示的過程。 天津大學仁愛學院——計算機科學與技術(shù)系——李帥帥 q=(struct pcb *)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0; q->priority=P_TIME-q->needtime; q->process=ready; q->next=NULL; if(i==0) { p=q; t->next=q; } else { q->next=t->next; t=q; q=p; } i++;} return p;} void display(pcb * p){ cout<<“name”<<“ ”<<“cputime”<<“needtime”<<“ ”<<“priority”<<“ ” <<“state”< cout< name; cout<<“ ”; cout< cputime; cout<<“ ”; cout< needtime; cout<<“ ”; cout< priority; cout<<“ ”; switch(p->process) { case ready:cout<<“ready”< case execute:cout<<“execute”< case block:cout<<“block”< case finish:cout<<“finish”< } 天津大學仁愛學院——計算機科學與技術(shù)系——李帥帥 void priority_cal(){ pcb * p;system(“cls”);p=get_process();int cpu=0;system(“cls”);while(!process_finish(p)){ cpu++; cout<<“cuptime:”< cpuexe(p); display(p); Sleep(1000);} printf(“All processes have finished,press any key to exit”);getch();} void display_menu(){ cout<<“nCHOOSE THE ALGORITHM:”< pcb *get_process_round(){ pcb *q;pcb *t;pcb *p;int i=0;t=(struct pcb *)malloc(sizeof(pcb));p=(struct pcb *)malloc(sizeof(pcb));cout<<“input name and time”< cin>>q->name; cin>>q->needtime; q->cputime=0; 天津大學仁愛學院——計算機科學與技術(shù)系——李帥帥 { } } return t;} void set_state(pcb *p){ while(p){ if(p->needtime==0) { p->process=finish;//如果所需執(zhí)行時間為0，則設(shè)置運行狀態(tài)為結(jié)束 } if(p->process==execute) { p->process=ready;//如果未執(zhí)行狀態(tài)則設(shè)置為就緒 } p->next;} }//設(shè)置隊列中進程執(zhí)行狀態(tài) void display_round(pcb *p){ cout<<“NAME”<<“ ”<<“CPUTIME”<<“ ”<<“NEEDTIME”<<“ ”<<“COUNT”<<“ ”<<“ROUND” <<“ ”<<“STATE”< cout< name; cout<<“ ”; cout< cputime; cout<<“ ”; cout< needtime; cout<<“ ”; cout< count; cout<<“ ”; cout< round; cout<<“ ”; switch(p->process) { case ready:cout<<“ready”< case execute:cout<<“execute”< case finish:cout<<“finish”< 天津大學仁愛學院——計算機科學與技術(shù)系——李帥帥 7）實驗結(jié)果截圖 電梯優(yōu)先調(diào)度算法 電梯調(diào)度算法(ms InterView) 移臂調(diào)度算法包括以下四種： 1）先來先服務(wù)算法：根據(jù)訪問者提出訪問請求的先后次序來決定執(zhí)行次序。 2）最短尋找時間優(yōu)先調(diào)度算法：從等待的訪問者中挑選尋找時間最短的那個請求執(zhí)行，而不管訪問者的先后次序。 3）電梯調(diào)度掃描算法：從移動臂當前位置沿移動方向選擇最近的那個柱面的訪問者來執(zhí)行，若該方向上無請求訪問時，就改變移動方向再選擇。 4）單向掃描調(diào)度算法：從0柱面開始往里單向掃描，掃到哪個執(zhí)行哪個。 */ // t1.cpp : 定義控制臺應(yīng)用程序的入口點。 // #include “stdafx.h” #include“math.h” #include“stdlib.h” #include“string.h” struct Head { int nPosition;bool bVisited;}; void Visit(struct Head *pHead){ printf(“visite cy:%dn”,pHead->nPosition);pHead->bVisited=true;} int ReadInputKeyboard(struct Head *pHead,int *pCurrentPosition,int nMaxNumber){ int i; printf(“please input Current position:”);scanf(“%d”,pCurrentPosition); printf(“please input will visit position:”);for(i=0;i scanf(“%d”,&pHead[i].nPosition);pHead[i].bVisited=false;if(pHead[i].nPosition<0)break;} return i;} int ReadInputFile(struct Head *pHead,int *pCurrentPosition,int nMaxNumber){ int i; char szFileName[256],*q,*p,szTemp[20];printf(“please input filename:”);scanf(“%s”,szFileName); FILE *pFile=fopen(szFileName,“r”);if(pFile==NULL){ printf(“open file %s error”,szFileName);return-1;} for(i=0;!feof(pFile)&&i p=szFileName;fgets(p,256,pFile); while(q=strchr(p,',')){ memset(szTemp,0,sizeof(szTemp)*sizeof(char));strncpy(szTemp,p,q-p);p=q+1;if(i==0) *pCurrentPosition=atoi(szTemp);else { pHead[i-1].nPosition=atoi(szTemp);pHead[i-1].bVisited=false;} i++;} memset(szTemp,0,sizeof(szTemp)*sizeof(char));pHead[i-1].nPosition=atoi(p);pHead[i-1].bVisited=false;//i++; } fclose(pFile);return i;} int FifoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ //先來先服務(wù) int nHaveVisited=0;int nMoveDistance=0;int i;while(nHaveVisited for(i=0;i if(pHead[i].bVisited)continue; Visit(&pHead[i]);nHaveVisited++; nMoveDistance+=abs(nCurrentPosition-pHead[i].nPosition);nCurrentPosition=pHead[i].nPosition;} } printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int SsfoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ // 最短尋找時間優(yōu)先 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i; while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } //訪問 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int DtVisit(int nCurrentPosition,bool bOut,struct Head *pHead,int nNumber){ //電梯調(diào)度算法 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i; while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(bOut&&pHead[i].nPosition if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } } if(nMinDistance==0xffff){ bOut=!bOut;continue;} //訪問 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int DxVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ //單向調(diào)度算法 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i;while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(pHead[i].nPosition>nCurrentPosition){ if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } } if(nMinDistance==0xffff){ nMoveDistance+=199-nCurrentPosition;nCurrentPosition=0;continue;} //訪問 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int main(int argc, char* argv[]){ //p114 struct Head mylist[20];//={98,false,183,false,37,false,122,false,14,false,124,false,65,false,67,false}; //int nCurrentPosition=53; //int nRealNumber=8; int nCurrentPosition=0; int nRealNumber=ReadInputFile(mylist,&nCurrentPosition,20);// FifoVisit(nCurrentPosition,mylist,nRealNumber); // SsfoVisit(nCurrentPosition,mylist,nRealNumber); //DtVisit(nCurrentPosition,false,mylist,nRealNumber); DxVisit(nCurrentPosition,mylist,nRealNumber); return 0;}第三篇：進程調(diào)度
第四篇：進程調(diào)度實驗報告
第五篇：電梯優(yōu)先調(diào)度算法
點擊咨詢 