實驗3 處理機管理
一、實驗目的
在多道程序或多任務系統中，系統中同時處于就緒態的進程有若干個，即能運行的進程數遠遠大于處理機個數。為了使系統中的各個進程能有條不紊的運行，必須按照某種調度策略，選擇一個進程占用處理機。
本次實驗要求設計并實現一個模擬單處理機調度的算法，以加深對處理機調度基本概念和基本算法的理解。
二、實驗內容
1、設計一個按時間片輪轉法實現處理機調度的程序(難度系數0.95)
?????? （1）假設系統中有N個進程，每個進程由一個進程控制塊（PCB）來標識，進程控制塊結構如下圖所示。
| 進程名 |
| 到達時間 |
| 估計運行時間 |
| 進程狀態 |
| …… |
| 鏈接指針 |
圖1 進程控制塊PCB結構圖
?
???????進程名：即進程標識。
?????? 到達時間：進程創建時的系統時間或由用戶制定。
估計運行時間：可由設計者指定一個時間值。
?????? 進程狀態：這里假定進程有兩種狀態：就緒狀態和完成狀態。就緒狀態用“R”表示，完成狀態用“C”表示。假定進程創建后就處于就緒狀態，運行結束時，就被置成完成狀態。
鏈接指針：按照進程到達系統的時間將處于就緒狀態的進程連接成一個就緒隊列。指針指出下一個到達的進程控制塊首地址。最后一個進程的鏈指針為NULL。
???????（2）按照進程到達的先后順序排成一個循環隊列。
?????? （3）執行處理機調度時，首先選擇隊首的第一個進程運行。
?????? （4）由于本實驗是模擬實驗，所以對被選中進程并不實際啟動運行，而只是執行：
????????????????? 估計運行時間減1,用這個操作來模擬進程的一次運行。
?????? （5）進程運行一次后，以后的調度則將當前指針依次下移一個位置，指向下一個進程。同時還應判斷該進程的剩余運行時間是否為0，若不為0，則等待下一輪的運行；若該進程的剩余運行為0，則將該進程的狀態置為完成狀態，并退出循環隊列。
?????? （6）若就緒隊列不空，則重復上述的步驟（4）和（5）直到所有進程都運行完為止。
?????? （7）在所設計的調度程序中，應包含顯示或打印語句，以便顯示或打印每次選中進程的名稱及運行一次后隊列的變化情況。
?????? （8）計算每個進程的周轉時間、帶權周轉時間以及進程平均周轉時間。
2、設計一個按優先級調度的算法實現處理機調度(難度系數1.0)
（1） 系統有N個進程，每個進程用一個進程控制塊來代表，進程控制塊的結構如下圖所示。
| 進程名 |
| 到達時間 |
| 估計運行時間 |
| 進程優先級 |
| 進程狀態 |
| …… |
| 鏈接指針 |
圖2 進程控制塊PCB結構
進程的優先級、要求運行時間和估計運行時間由用戶程序任意設定。調度時，總是選擇優先級最高的進程運行。
（2）為了調度方便，設計一個指針指向就緒隊列中的第一個進程。另外再設一個當前運行進程指針，指向當前正運行的進程。
（3）處理機每個時間片調度1次，總是選擇已經到達隊列的優先級最高的進程運行。為了采用動態優先級調度，進程每運行一次，其優先級就減1。由于本實驗是模擬實驗，所以對選中進程并不實際啟動運行，而只是執行：
優先級減1和估計運行時間減1，用這兩個操作來模擬進程的一次運行。
（4）進程運行一次后，若剩余時間不為0，且其優先級低于就緒隊列的其他進程優先級，則選擇一個高優先級進程搶占CPU；若剩余時間為0，把它的狀態改為完成狀態“C”，并撤出就緒隊列。
（5）若就緒隊列不空，則重復上述的步驟（3）和（4），直到所有進程成為完成狀態。
（6）在所設計的調度程序中，應包含顯示或打印語句，以便顯示或打印每次選中進程的名稱及運行一次后隊列的變化情況。
?????? （7）計算每個進程的周轉時間、帶權周轉時間以及進程平均周轉時間。
三、實驗結果和分析
（1）程序中使用的數據結構說明；
【1】實驗內容1使用的數據結構說明：
如上圖所示，進程控制塊使用結構體進行構建，包含以下幾個屬性：進程名字、進程狀態、就緒隊列中的累計排隊序號、進程到達時間、進程服務時間、進程完成時間、進程剩余時間。其中，進程名字使用字符串變量，其他屬性均使用整形變量。
如上圖所示，在執行RR算法之前，首先利用字符串存放當前的就緒隊列，利用數組list存放在就緒隊列中的進程的編號，利用數組waitnumber存放進程在就緒隊列中的累計排隊序號。然后，通過對數組waitnumber進行從小到大的排序，同時對應給數組list進行排序。最后，在數組list中得到按照等待順序遞增的進程序列，并將進程名字按序寫入ready中。
【2】實驗內容2使用的數據結構說明：
如上圖所示，進程控制塊使用結構體進行構建，包含以下幾個屬性：進程名字、進程狀態、進程到達時間、進程服務時間、進程完成時間、進程剩余時間、進程優先級、進程上一次變為就緒態的時間。其中，進程名字使用字符串變量，其他屬性均使用整形變量。此外，進程上一次變為就緒態的時間初始化為進程到達時間，如果進程后續有被CPU調用，則更新為被CPU調用后的時間。
如上圖所示，在執行PSA算法之前，首先利用數組存放當前的就緒隊列所對應的進程編號，并調用sortlist()函數進行當前時間的就緒隊列計算。
（2）程序流程圖和帶有注釋的源程序；
【1】實驗內容1的流程圖：如（4）處的總結1所示，并主要包含以下四個內容：
1）整體的程序流程圖；
2）進程初始化的流程圖；
3）按照到達時間排序進程的流程圖；
4）時間片輪轉算法的流程圖。
【2】實驗內容2的流程圖：如（4）處的總結2所示，并主要包含以下四個內容：
1）整體的程序流程圖；
2）進程初始化的流程圖；
3）就緒隊列進行排序的流程圖；
4）優先級調度算法的流程圖。
【3】實驗內容1 & 實驗內容2的帶有注釋的源程序：
| 實驗內容1：exp3-1.cpp |
| #include <iostream> #include <stdio.h> #include <iomanip> #include <string.h> #include <stdlib.h> using namespace std; //pcb的結構體設置 typedef struct{ ? ? string name; ? ? ? ?//進程名字 ? ? int flag; ? ? ? ? ? //是否完成，狀態檢測（1是完成，0是未完成） ? ? int number; ? ? ? ? //就緒隊列中的順序 ? ? int arrivetime; ? ? //到達時間 ? ? int runtime; ? ? ? ?//服務時間 ? ? int completetime; ? //完成時間 ? ? int remaintime; ? ? //剩余時間 }PCB; //進程指標 （全局） PCB p[100]; ? ? ? ? ? ? //可輸入的進程數量 int timelen=1; ? ? ? ? ?//時間片長度 int total; ? ? ? ? ? ? ?//進程總數（由main中的用戶輸入） //就緒隊列指標 （全局） int current=0; ? ? ? ? ?//當前應該執行的進程編號 int head=0; ? ? ? ? ? ? //就緒隊列中的隊首 //進程初始化 void initialize(){ ? ? for(int i=0;i<total;i++){ ? ? ? ? cout<<"請輸入第"<<i+1<<"個進程的名字、到達時間、服務時間："; ? ? ? ? cin>>p[i].name>>p[i].arrivetime>>p[i].runtime; ? ? ? ? ? ? ? ? //其他屬性的初始化 ? ? ? ? p[i].remaintime=p[i].runtime; ? //初始剩余時間 = 服務時間 ? ? ? ? p[i].flag=0; ? ? ? ? ? ? ? ? ? ?//完成狀態 = 未完成 ? ? ? ? p[i].number=0; ? ? ? ? ? ? ? ? ?//就緒隊列中的順序 = 0 ? ? } } //按照到達時間排序進程（冒泡排序） void sortarrive(){ ? ? for(int i=0;i<total-1;i++){ ? ? ? ? for(int j=0;j<total-i-1;j++){ ? ? ? ? ? ? //到達時間從小到大排序 ? ? ? ? ? ? if(p[j].arrivetime>p[j+1].arrivetime){ ? ? ? ? ? ? ? ? //如果前一個的時間大于后一個，則交換兩個進程的順序 ? ? ? ? ? ? ? ? PCB t=p[j+1]; ? ? ? ? ? ? ? ? p[j+1]=p[j]; ? ? ? ? ? ? ? ? p[j]=t; ? ? ? ? ? ? } ? ? ? ? } ? ? } } //時間片輪轉 void timeprocess(){ ? ? int time=p[0].arrivetime; ? ? ? ? ? //系統開始的時間是最早就緒進程的到達時間 ? ? int complete=0; ? ? ? ? ? ? ? ? ? ? //已經完成的進程個數 ? ? int n=0; ? ? ? ? ? ? ? ? ? ? ? ? ? ?//記錄while循環次數的變量 ? ? ? ? //所有進程執行的過程 ? ? while(complete<total){ ? ? ? ? for(int i=0;i<total;i++){ ? ? ? ? ? ? //當前這個進程和cur相同，且狀態為未完成 ? ? ? ? ? ? if(p[i].number==current && p[i].flag==0){ ? ? ? ? ? ? ? ? //print current cycle ? ? ? ? ? ? ? ? cout<<endl<<"當前的時鐘周期是：T"<<current<<endl; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //process ready list ? ? ? ? ? ? ? ? string ready=""; ? ? ? ? ? ? ? ? int list[100]; ? ? ? ? ? ? ? ? int waitnumber[100]; ? ? ? ? ? ? ? ? int cnt=0; ? ? ? ? ? ? ? ? for(int k=0;k<total;k++){ ? ? ? ? ? ? ? ? ? ? //大于當前current的，都是在就緒隊列里面的進程 ? ? ? ? ? ? ? ? ? ? if(p[k].number>current && p[k].flag==0){ ? ? ? ? ? ? ? ? ? ? ? ? list[cnt]=k; ? ? ? ? ? ? ? ? ? ? ? ? waitnumber[cnt]=p[k].number; ? ? ? ? ? ? ? ? ? ? ? ? cnt++; ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? cout<<"就緒隊列里面一共有："<<cnt<<"個進程，"; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //按照waitnumber排序 （冒泡排序） ? ? ? ? ? ? ? ? for (int k = 0; k < cnt - 1; k++) { ? ? ? ? ? ? ? ? ? ? for (int kk = 0; kk < cnt - 1 - k; kk++) { ? ? ? ? ? ? ? ? ? ? ? ? if (waitnumber[kk] > waitnumber[kk + 1]) { ? ? ? ? ? ? ? ? ? ? ? ? ? ? int tempfig = waitnumber[kk + 1]; ? ? ? ? ? ? ? ? ? ? ? ? ? ? waitnumber[kk + 1] = waitnumber[kk]; ? ? ? ? ? ? ? ? ? ? ? ? ? ? waitnumber[kk] = tempfig; ? ? ? ? ? ? ? ? ? ? ? ? ? ? int templist = list[kk + 1]; ? ? ? ? ? ? ? ? ? ? ? ? ? ? list[kk + 1] = list[kk]; ? ? ? ? ? ? ? ? ? ? ? ? ? ? list[kk] = templist; ? ? ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? }//不知道為啥死循環了。。調好了 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //按照waitnumber的大小進行push ? ? ? ? ? ? ? ? for(int k=0;k<cnt;k++){ ? ? ? ? ? ? ? ? ? ? int id=list[k]; ? ? ? ? ? ? ? ? ? ? ready+=p[id].name; ? ? ? ? ? ? ? ? ? ? ready+=" "; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? //print ready ? ? ? ? ? ? ? ? if(ready==""){ ? ? ? ? ? ? ? ? ? ? cout<<"就緒隊列為空"<<endl; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? else{ ? ? ? ? ? ? ? ? ? ? cout<<"當前的就緒隊列為："<<ready<<endl; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //時間片工作 ? ? ? ? ? ? ? ? cout<<"判斷時間片ing，當前應該執行進程"<<p[i].name<<endl; ? ? ? ? ? ? ? ? //current進程能在當前時間片運行完 ? ? ? ? ? ? ? ? if(p[i].remaintime<=timelen){ ? ? ? ? ? ? ? ? ? ? time+=p[i].remaintime; ? ? ?//系統時間，增加該進程的剩余時間 ? ? ? ? ? ? ? ? ? ? p[i].flag=1; ? ? ? ? ? ? ? ?//狀態變為完成 ? ? ? ? ? ? ? ? ? ? p[i].completetime=time; ? ? //此進程的完成時間為當前系統時間 ? ? ? ? ? ? ? ? ? ? p[i].remaintime=0; ? ? ? ? ?//剩余時間，設置為0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? complete++; ? ? //系統中完成的進程數+=1 ? ? ? ? ? ? ? ? ? ? current++; ? ? ?//cur+=1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //檢查是否有新的到達進程 ? ? ? ? ? ? ? ? ? ? for(int j=i+1;j<total;j++){ ? ? ? ? ? ? ? ? ? ? ? ? //有新的到達進程 ? ? ? ? ? ? ? ? ? ? ? ? if(p[j].arrivetime<=time && p[j].number==0){ ? ? ? ? ? ? ? ? ? ? ? ? ? ? head++; ? ? ? ? ? ? //就緒隊列個數+=1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? p[j].number=head; ? //這個進程的就緒編號為head ? ? ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? //current進程不能在當前時間片運行完 ? ? ? ? ? ? ? ? else{ ? ? ? ? ? ? ? ? ? ? time+=timelen; ? ? ? ? ? ? ? ? ? ? p[i].remaintime-=timelen; ? ? ? ? ? ? ? ? ? ? current++; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //檢查是否有新的到達進程 ? ? ? ? ? ? ? ? ? ? for(int j=i+1;j<total;j++){ ? ? ? ? ? ? ? ? ? ? ? ? if(p[j].arrivetime<=time && p[j].number==0){ ? ? ? ? ? ? ? ? ? ? ? ? ? ? head++; ? ? ? ? ? ? ? ? ? ? ? ? ? ? p[j].number=head; ? ? ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //重新給這個進程加入就緒隊列 ? ? ? ? ? ? ? ? ? ? head++; ? ? ? ? ? ? //剛剛執行的這個進程繼續進入就緒隊列 ? ? ? ? ? ? ? ? ? ? p[i].number=head; ? //更改就緒編號 ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? n++; ? ?//檢測while循環的次數 ? ? } ? ? cout<<"執行完畢，總共花費時鐘周期：T"<<current<<endl; } void show(){ ? ? double x=0; ? ? //總周轉時間 ? ? ? ? 周轉時間 = 完成時間 - 到達時間 ? ? double y=0; ? ? //總帶權周轉時間 ? 帶權周轉時間 = 周轉時間 / 服務時間 ? ? ? ? //輸出每個進程的基本信息 ? ? for(int i=0;i<total;i++){ ? ? ? ? double px=(double)p[i].completetime-p[i].arrivetime; ? ?//當前進程的周轉時間 ? ? ? ? double py=px/(double)p[i].runtime; ? ? ? ? ? ? ? ? ? ? ?//當前進程的帶權周轉時間 ? ? ? ? cout<<"進程名字："<<p[i].name; ? ? ? ? cout<<"\t"<<"周轉時間："<<px; ? ? ? ? cout<<"\t"<<"帶權周轉時間："<<py; ? ? ? ? cout<<"\t"<<"到達時間："<<p[i].arrivetime; ? ? ? ? cout<<"\t"<<"服務時間："<<p[i].runtime; ? ? ? ? cout<<"\t"<<"完成時間："<<p[i].completetime; ? ? ? ? cout<<endl; ? ? ? ? x+=px; ? ? ? ? y+=py; ? ? } ? ? double ret1=x/total; ? ?//平均周轉時間 ? ? double ret2=y/total; ? ?//平均帶權周轉時間 ? ? cout<<"平均周轉時間："<<ret1<<endl; ? ? cout<<"平均帶權周轉時間："<<ret2<<endl; } /* //RR 測試用例1： 5 p1 0 3 p2 2 6 p3 4 4 p4 6 5 p5 8 2 //優先級 測試用例2： 4 p1 0 2 2 p2 0 2 3 p3 0 4 1 p4 0 3 4 進程執行的順序應該是：p4 p2 p4 p1 p2 p4 p3 p1 p3 p3 p3 7.5 2.8125 */ int main(){ ? ? cout<<"請輸入進程總數："; ? ? cin>>total; ? ? ? ? //用戶輸入進程的總數 ? ? initialize(); ? ? ? //初始化 ? ? sortarrive(); ? ? ? //到達時間處理 ? ? timeprocess(); ? ? ?//時間片處理 ? ? cout<<endl; ? ? show(); ? ? ? ? ? ? //輸出最終的結果 ? ? return 0; } |
| 實驗內容2：exp3-2.cpp |
| #include <iostream> #include <stdio.h> #include <iomanip> #include <string.h> #include <stdlib.h> #include <vector> using namespace std; //pcb的結構體設置 typedef struct{ ? ? string name; ? ? ? ?//進程名字 ? ? int flag; ? ? ? ? ? //是否完成，狀態檢測（1是完成，0是未完成） ? ? int arrivetime; ? ? //到達時間 ? ? int runtime; ? ? ? ?//服務時間 ? ? int completetime; ? //完成時間 ? ? int remaintime; ? ? //剩余時間 ? ? int prior; ? ? ? ? ?//優先級 ? ? int lasttime; ? ? ? //上一次運行的時間 }PCB; //進程指標 （全局） PCB p[100]; ? ? ? ? ? ? //可輸入的進程數量 int timelen=1; ? ? ? ? ?//時間片長度 int total; ? ? ? ? ? ? ?//進程總數（由main中的用戶輸入） //進程初始化 void initialize(){ ? ? for(int i=0;i<total;i++){ ? ? ? ? cout<<"請輸入第"<<i+1<<"個進程的名字、到達時間、服務時間、優先級："; ? ? ? ? cin>>p[i].name>>p[i].arrivetime>>p[i].runtime>>p[i].prior; ? ? ? ? ? ? ? ? //其他屬性的初始化 ? ? ? ? p[i].remaintime=p[i].runtime; ? //初始剩余時間 = 服務時間 ? ? ? ? p[i].flag=0; ? ? ? ? ? ? ? ? ? ?//完成狀態 = 未完成 ? ? ? ? p[i].lasttime=p[i].arrivetime; ?//上一次運行的時間 ? ? } } //初始化就緒隊列 void sortlist(vector<int> &wait,int cycle){ ? ? //遍歷已經到來且未完成的進程 ? ? for(int i=0;i<total;i++){ ? ? ? ? if(p[i].arrivetime<=cycle && p[i].flag==0){ ? ? ? ? ? ? wait.push_back(i); ? ? ? ? } ? ? } ? ? ? ? int n=wait.size(); ? ? //按照prior劃分（選擇排序） ? ? for(int i=0;i<n-1;i++){ ? ? ? ? int id=i; ? //max to process ? ? ? ? for(int j=i+1;j<n;j++){ ? ? ? ? ? ? int curprocess=wait[j]; ? ? //遍歷到的后面的進程序號 ? ? ? ? ? ? int maxprocess=wait[id]; ? ?//當前優先級最大的進程序號 ? ? ? ? ? ? if(p[maxprocess].prior<p[curprocess].prior){ ? ? ? ? ? ? ? ? //如果后面進程的prior更大，則更新優先級最大的進程序號 ? ? ? ? ? ? ? ? id=j; ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? if(id!=i){ ? ? ? ? ? ? //如果有更新，則交換兩個pcb的順序 ? ? ? ? ? ? int t=wait[id]; ? ? ? ? ? ? wait[id]=wait[i]; ? ? ? ? ? ? wait[i]=t; ? ? ? ? } ? ? } ? ? ? ? //相同prior按照lasttime劃分 ? ? int i=0; ? ?//從隊首開始分析 ? ? while(i<n-1){ ? ? ? ? int pos=i; ?//記錄離當前最遠，且和當前進程優先級相同的進程 ? ? ? ? int nowid=wait[i]; ? ? ? ? for(int j=1+i;j<n;j++){ ? ? ? ? ? ? int processid=wait[j]; ? ? ? ? ? ? if(p[processid].prior==p[nowid].prior){ ? ? ? ? ? ? ? ? pos=j; ?//后面的進程和現在的進程優先級相同，更新最遠記錄 ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? if(pos!=i){ ? ? ? ? ? ? //sort between wait[i] and wait[pos] according to lasttime（選擇排序） ? ? ? ? ? ? for(int a=i;a<pos;a++){ ? ? ? ? ? ? ? ? int aid=a; ? ? ? ? ? ? ? ? for(int b=a+1;b<=pos;b++){ ? ? ? ? ? ? ? ? ? ? int cur=wait[b]; ? ? ? ? ? ? ? ? ? ? int min=wait[aid]; ? ? ? ? ? ? ? ? ? ? if(p[min].lasttime>p[cur].lasttime){ ? ? ? ? ? ? ? ? ? ? ? ? //如果后面的lasttime更小 ? ? ? ? ? ? ? ? ? ? ? ? aid=b; ? ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? if(aid!=a){ ? ? ? ? ? ? ? ? ? ? //如果有更新，則交換兩個pcb的順序 ? ? ? ? ? ? ? ? ? ? int tt=wait[aid]; ? ? ? ? ? ? ? ? ? ? wait[aid]=wait[a]; ? ? ? ? ? ? ? ? ? ? wait[a]=tt; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? i=pos+1; ? ?//移動到下一個還沒有判斷過優先級是否相等的pcb塊 ? ? } } void psa(){ ? ? //系統開始時間 （初始化） ? ? int starttime=p[0].arrivetime; ? ? for(int i=1;i<total;i++){ ? ? ? ? if(starttime>p[i].arrivetime){ ? ? ? ? ? ? starttime=p[i].arrivetime; ?//更新進程最早到達的時間 ? ? ? ? } ? ? } ? ? ? ? int cycle=0; ? ? ? ?//執行的周期數 ? ? int complete=0; ? ? //完成的進程數 ? ? ? ? //執行所有進程 ? ? while(complete<total){ ? ? ? ? //wait list ? ? ? ? vector<int> wait; ? ? ? ? sortlist(wait,cycle); ? ? ? ? cout<<endl<<"在執行該時間片前，T"<<cycle<<"的就緒隊列為："; ? ? ? ? for(int i=0;i<wait.size();i++){ ? ? ? ? ? ? int proid=wait[i]; ? ? ? ? ? ? cout<<p[proid].name<<" "; ? ? ? ? } ? ? ? ? cout<<endl; ? ? ? ? ? ? ? ? //執行wait[0]（位于就緒隊列隊首的時間片） ? ? ? ? int curpro=wait[0]; ? ? ? ? cout<<"判斷時間片ing，當前應該執行進程："<<p[curpro].name<<endl; ? ? ? ? ? ? ? ? //判斷當前時間片內，curpro是否能執行完畢 ? ? ? ? if(p[curpro].remaintime<=timelen){ ? ? ? ? ? ? ? //can ? ? ? ? ? ? p[curpro].flag=1; ? ? ? ? ? ? ? ? ? ? ? ? ? //修改進程狀態，且flag==1之后，就不需要管prior了 ? ? ? ? ? ? p[curpro].completetime=starttime+cycle+1; ? //修改完成時間 ? ? ? ? ? ? p[curpro].remaintime=0; ? ? ? ? ? ? ? ? ? ? //修改剩余時間 ? ? ? ? ? ? complete++; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //完成的進程數 += 1 ? ? ? ? ? ? cout<<"在這個時間片內，已經執行完進程："<<p[curpro].name<<endl; ? ? ? ? } ? ? ? ? else{ ? ? ? ? ? ? ? //cannot ? ? ? ? ? ? p[curpro].remaintime-=timelen; ?//修改剩余時間 ? ? ? ? ? ? p[curpro].prior--; ? ? ? ? ? ? ?//修改優先級 ? ? ? ? ? ? p[curpro].lasttime=cycle+1; ? ? //修改上次使用時間 ? ? ? ? } ? ? ? ? ? ? ? ? cycle++; ? ?//時間周期 += 1 ? ? ? ? //complete++; ? //temporary break while to debug ? ? } ? ? cout<<endl<<"執行完畢，總共花費時鐘周期：T"<<cycle<<endl; } void show(){ ? ? double x=0; ? ? //總周轉時間 ? ? ? ? 周轉時間 = 完成時間 - 到達時間 ? ? double y=0; ? ? //總帶權周轉時間 ? 帶權周轉時間 = 周轉時間 / 服務時間 ? ? ? ? //輸出每個進程的基本信息 ? ? for(int i=0;i<total;i++){ ? ? ? ? double px=(double)p[i].completetime-p[i].arrivetime; ? ?//當前進程的周轉時間 ? ? ? ? double py=px/(double)p[i].runtime; ? ? ? ? ? ? ? ? ? ? ?//當前進程的帶權周轉時間 ? ? ? ? cout<<"進程名字："<<p[i].name; ? ? ? ? cout<<"\t"<<"周轉時間："<<px; ? ? ? ? cout<<"\t"<<"帶權周轉時間："<<py; ? ? ? ? cout<<endl; ? ? ? ? cout<<"\t"<<"到達時間："<<p[i].arrivetime; ? ? ? ? cout<<"\t"<<"服務時間："<<p[i].runtime; ? ? ? ? cout<<"\t"<<"完成時間："<<p[i].completetime; ? ? ? ? cout<<endl; ? ? ? ? x+=px; ? ? ? ? y+=py; ? ? } ? ? double ret1=x/total; ? ?//平均周轉時間 ? ? double ret2=y/total; ? ?//平均帶權周轉時間 ? ? cout<<"平均周轉時間："<<ret1<<endl; ? ? cout<<"平均帶權周轉時間："<<ret2<<endl; } /* //優先級 測試用例2： 4 p1 0 2 2 p2 0 2 3 p3 0 4 1 p4 0 3 4 進程執行的順序應該是：p4 p2 p4 p1 p2 p4 p3 p1 p3 p3 p3 ? ? ? ? ? ? ? ? ? ? ? 0 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 7.5 2.8125 */ int main(){ ? ? cout<<"請輸入進程總數："; ? ? cin>>total; ? ? ? ? //用戶輸入進程的總數 ? ? initialize(); ? ? ? //初始化 ? ? psa(); ? ? ? ? ? ? ?//psa process ? ? cout<<endl; ? ? show(); ? ? ? ? ? ? //輸出最終的結果 ? ? return 0; } |
?
（3）執行程序名，并打印程序運行時的初值和運行結果，其中包括：
??? ①各進程控制塊的初始狀態；
【實驗內容1】
在本實驗內容中，測試用例的內容如下表所示。
| 進程總數 | 5 | |
| 進程名字 | 進程到達時間 | 進程服務時間 |
| P1 | 0 | 3 |
| P2 | 2 | 6 |
| P3 | 4 | 4 |
| P4 | 6 | 5 |
| P5 | 8 | 2 |
?如下圖所示，在初始化函數initialize()中，在初始化各個進程的各個屬性之后，將打印各個進程的基本信息（完成時間除外）。
測試用例的結果如下圖所示。
由上圖可知，進程初始化成功，各個進程控制塊的初始狀態符合預期。
【實驗內容2】
在本實驗內容中，測試用例的內容如下表所示。
| 進程總數 | 4 | ||
| 進程名字 | 進程到達時間 | 進程服務時間 | 進程優先級 |
| P1 | 0 | 2 | 2 |
| P2 | 0 | 2 | 3 |
| P3 | 0 | 4 | 1 |
| P4 | 0 | 3 | 4 |
如下圖所示，在初始化函數initialize()中，在初始化各個進程的各個屬性之后，將打印各個進程的基本信息（完成時間除外）。
測試用例的結果如下圖所示。
由上圖可知，進程初始化成功，各個進程控制塊的初始狀態符合預期。
??? ②選中運行進程的名字、運行后各進程控制塊狀態以及每次調度時，就緒隊列的進程排列順序；
【實驗內容1】
在RR算法執行過程中，程序會輸出當前的時間、就緒隊列的結果、當前時間片選中運行進程的名字、當前時間片運行后執行完畢的進程，并在算法執行完畢后輸出系統總花費的時間。程序輸出的結果如下圖所示。
在PSA算法執行完畢后，程序會輸出各個進程的周轉時間和帶權周轉時間，并同時輸出到達時間、服務時間、完成時間，以便核對計算是否正確。在輸出完所有進程的信息后，程序會輸出系統的平均周轉時間和平均帶權周轉時間。程序輸出的結果如下圖所示。
核驗實驗3的ppt中關于RR算法的測試案例后，發現實驗結果和理論計算結果一致。
【實驗內容2】
在PSA算法執行過程中，程序會輸出就緒隊列的結果、當前時間片選中運行進程的名字、當前時間片運行后執行完畢的進程，并在算法執行完畢后輸出系統總花費的時間。程序輸出的結果如下圖所示。
在PSA算法執行完畢后，程序會輸出各個進程的周轉時間和帶權周轉時間，并同時輸出到達時間、服務時間、完成時間，以便核對計算是否正確。在輸出完所有進程的信息后，程序會輸出系統的平均周轉時間和平均帶權周轉時間。
核驗實驗3的ppt中關于PSA算法的測試案例后，發現實驗結果和理論計算結果一致。
（4）總結本次實驗的心得與體會。
【流程圖】
1：實驗內容1的流程圖：
1）整體的程序流程圖（main函數）
2）進程初始化的流程圖（initialize函數）
3）按照到達時間排序進程的流程圖（sortarrive函數）
4）時間片輪轉算法的流程圖
5）運行結果輸出的流程圖（show函數）
2：實驗內容2的流程圖：
注：運行結果輸出的流程圖（show函數）與實驗內容1相同，此處不再贅述。
1）整體的程序流程圖
2）進程初始化的流程圖
3）就緒隊列進行排序的流程圖
4）優先級調度算法的流程圖
【實驗總結】
3：時間片原則：各進程按時間片運行，當一個時間片用完后，便停止該進程的執行而重新調度，適用于分時系統。
4：優先權原則：通常對一些重要的和緊急的進程賦予較高的優先權。當這種進程進入就緒隊列時，如果其優先權比正在執行的進程優先權高，便停止正在執行的進程，將處理機分配給優先權高的進程。
5：進程調度方式分為兩種——【搶占方式】和【非搶占方式】。搶占方式：把處理機分配給某進程后便讓它一直運行下去，直到進程完成或發生某事件而阻塞時，才把處理機分配給另一個進程。非搶占方式：當一個進程正在運行時，系統可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進程。因此，時間片輪轉法（RR）和優先級調度算法（PSA）均是搶占方式，因為這兩種算法都并沒有一個進程完整地運行。
6：各種調度算法的優點和缺點如下圖所示。
FCFS：先來先服務算法。
SJF：最短作業優先算法。
HRRF：最高響應比優先算法。
RR：時間片輪轉算法。
7：在本實驗中，主要使用了RR和PSA。RR的特點是：公平性高，每個進程都有機會執行；可能導致較高的上下文切換開銷，實時性較差。PSA的特點是：能夠更好地滿足緊急任務的需要，對于重要或緊急的任務更加有效；可能導致低優先級進程長時間等待，甚至發生饑餓現象。
8：饑餓現象：在操作系統中是指某一個或多個進程由于種種原因長時間得不到所需的資源，從而無法繼續執行的情況。
四、實驗指導
?????? 在Linux環境下， 用C語言編寫，程序中的數據結構定義和程序主框架如下，供參考。
??
?????? typedef?? struct? pcb????????? //進程控制塊定義
?????? {? ? int? pid； ??????????//進程ID
char? pname[N];????????? //進程名
????????????? int? runtime;??????????????? //運行時間
????????????? int? arrivetime;??????????? //到達時間
????????????? char state;??????????????????? //進程狀態
????????????? int? priority;??????????????? //進程優先級
int?? finishtime;???????????? //進程結束時間
????????????? struct? pcb? *next;????? //鏈接指針
??????? ……
}? PCB;
PCB? *head_input;???????????? //就緒隊列頭指針
PCB? *head_run;??????????????? //運行進程指針
unsigned long current;????? //記錄系統當前時間的變量
……
void? inputprocess( );? //建立進程，輸入進程數目N，輸入各個進程信息，并建立鏈表;
void? printreadylist( );? //輸出就緒隊列
int?? readyprocess( )； //檢查就緒隊列并運行進程
int?? runprocess( );? //運行進程的函數；
……
void main()?????????? //主函數
{? ? //fp=open（"result.txt”, “w”）;
??? current=0；
?????? inputprocess( );
????? readyprocess( );
??? ……
?????? getch( );
?????? //fclose(fp);
}
void? inputprocess( )? //建立進程，輸入進程數目N，輸入各個進程信息，并建立鏈表;
{ // 輸入需要運行的進程數量n
??…..
? // 輸入進程信息：進程名，運行時間，到達時間，優先級等信息
??…...
}
int ?readyprocess( )????? //檢查就緒隊列并運行進程
{ // 就緒隊列為空時，結束運行
??…..
?// 根據調度算法選擇一個進程；
runprocess();
//如果是時間片調度算法，則將時間減1
//如果是FCFS調度算法，則該進程運行結束，將當前時間+運行時間
//如果是優先級調度算法，運行時間-1，優先級-1
// 修改進程的狀態
?……
?// 輸出進程運行信息
}
五、測試用例
1. 時間片調度算法
2、 優先級調度算法
進程?????? 優先級????????? 運行時間?????? 到達時間?? ?結束時間
P1????? 12? ????????? 2???????? 0??????????? 8
P2????? 13????????? ? 2???????? 0??????????? 5
P3????? 11??????????? 4???????? 0??????????? 11
P4????? 14????????? ? 3???? ??? 0??????????? 6
程序執行過程：
每個時間片調度一次，執行完成的進程優先級減1，重新調度
0?? ??1? ???2???? 3? ???4? ???5?? ??6?? ??7?? ??8?? ??9?? ??10???? time
P4-——p2——p4——p1——P2——p4——p3——p1——p3——p3——p3
13? ??12? ??12? ??11? 11end ??11end 10 ???10end ?9? ??8? ???7end
