OS_進程調度：C++實現
- 2020 年 6 月 19 日
- 筆記
- C++, 進程調度, 作業系統實驗C++實現, 作業系統實驗
實驗二、進程調度模擬實驗
一、實驗目的：
本實驗模擬在單處理機環境下的處理機調度，幫助理解進程調度的概念，深入了解進程式控制制塊的功能，以及進程的創建、撤銷和進程各個狀態間的轉換過程。
二、實驗內容：
- 進程調度演算法：採用最高優先數優先的調度演算法、先來先服務演算法、SJF和多級回饋調度演算法。
- 每個進程有一個進程式控制制塊（PCB）表示。進程式控制制塊可以包含如下資訊：進程名、優先數、到達時間、需要運行時間、已用CPU時間、進程狀態等等。進程的優先數及需要的運行時間可以事先人為輸入（也可以由隨機數產生）。進程的到達時間為進程輸入的時間。 進程的運行時間以時間片為單位進行計算。
- 就緒進程獲得CPU後都只能運行一個時間片。用已佔用CPU時間加1來表示。如果運行一個時間片後，進程的已佔用CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片後進程的已佔用CPU時間還未達所需要的運行時間，也就是進程還需要繼續運行，此時應將進程的優先數減1（即降低一級），然後把它插入就緒隊列等待CPU。
- 每個進程的狀態可以是就緒W（Wait）、運行R（Run）、或完成F（Finish）三種狀態之一。
三、實驗要求：- 每進行一次調度程式都列印一次運行進程、就緒隊列、以及各個進程的PCB，以便進行檢查。
- 對同一組進程的各種調度演算法分別計算平均周轉時間和平均帶權周轉時間。
第一步
關於頭文件：
#include<stdio.h>
#include<cstdlib>
#include<iostream>
#define N 3
我們這裡默認最大允許三個進程，您也可以自己改成5，這邊建議用3就好，程式還有一些不為人知的秘密
命名空間這可以學習一下c++，與本演算法無太大關係所以在此不講述
using std::cout;
using std::cin;
using std::endl;
接下來我們開始我們最初的結構的定義：
進程pcb的定義
因為是進程調度，所以一定涉及到了進程pcb的調用，跟書一樣的定義，我們直接給出
typedef struct pcb{
char pname;//進程名
int n;//優先順序
int atime;//進程到達時間
int rtime;//運行時間
int utime;//已用時間
char status;//進程的狀態，w等待，r運行
pcb* next;
}pcb,*PCB;
PCB zpcb[N];//裝載著每個pcb的指針數組
int ctime;//當前運行時間用於先來先服務
int num;//處理機要處理的進程的個數
float time1,time2;//1為平均周轉：完成減去到達，2為帶權周轉：平均除以運行
PCB head=(PCB)malloc(sizeof(pcb));
zpcb是一個指針數組你也可以想像成進程隊列，這是根據演算法的各個形式進行增刪的，time1是平均周轉時間，用完成減去到達就可以，time2是平均帶權周轉時間，用time1除以進程運行時間即可，這裡可以看後面各個調度演算法的應用，很容易理解。
假設我們的調度演算法都實現了，首先我們需要定義我們的參數，創建pcb，裝載pcb數組，進程個數等等####
那麼我們首先定義一個方法，createProcess
在創建之前我們需要一個思考，我們的進程的初始狀態應該都置於wait，我們可以將所有的進程放置在我們之前的head隊列中，方便後續的使用。我們需要輸入我們的進程名等pcb結構中需要的值，最後用一個隊列進行裝載，這裡只給出一些提示，讀者自己創造。
int createProcess(){
cout<<"請輸入您需要運行的進程數目（max：3）";
cin>>num;
cout<<"輸入 "<<num<<"個的進程名、優先順序、到達時間、運行時間（空格隔開，進程直接回車隔開）\n注意：進程的到達時間必須遞增，首個的到達時間為0"<<endl;
PCB p = head;
for(int i=0;i<num;i++){
希望讀者可以自己去實現，最後我們需要告訴我們的調度演算法用戶一共創建了幾個進程，所以num應該作為返回值進行一個返回，這裡其實有一個bug，我的到達時間是我自己控制的，這是一種純粹的理想狀態。希望有人後來居上。
既然已經創建好了我們的進程，接下來是一種關於使用進程調度演算法了，我們可以設置一個while循環，讓用戶去選擇，while中可以搭配swtich語句這種簡單的留給讀者####
在這裡面你肯定會這樣想，我們是不會想調用一個演算法就退出，我們是想再調度幾個，用原來的輸入，所以我們如果已經動了我們的head，那麼這裡面的值都要一個歸零，就會很麻煩，這裡你會想起來我們的zpcb數組，它可以代替我們的head，這裡我們需要一個clean函數，讓使用時間歸零，讓狀態至為w，這個clean叫進程狀態初始化。在此給出程式碼
void clean(){//清除狀態，使用其他的調度演算法
cout<<"進程資訊初始化："<<endl;
PCB pc=head->next;
int i;
while(pc)
{
i++;
pc->utime=0;
pc->status='W';
pc=pc->next;
}
}
第一個調度演算法：PSA高優先數###
在每次傳參我們只需要傳入我們main中的num，其餘的為全局變數，
這裡直接給出定義
void PSA(int num){
//int n=num;
PCB pc=head->next;
int time,pr[N];//pr數組記錄了各個進程的優先順序
time1=0;
time2=0;
首先我們將n暫替我們的num，pc指針指向我們的首進程，pr數組用於記錄優先順序，time在前期可以充當一個臨時的變數，後期可以充當我們的系統時間，兩個平均**時間我們可以讓它們進行一個清零。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
第一步我們得讓我們的pr數組和我們的zpcb數組記錄下進程的優先順序，和clone整個進程，這就是我們上面說的作用，關於zpcb數組，一個參與調度的進程集合，ok話不多說我們給出程式碼：
for(time=0; time<N; time++)
if(pc)
{
zpcb[time]=pc;
pr[time]=pc->n;
pc=pc->next;
}
接下來我們找一找有沒有與我們進程同時到達的進程，又要使用我們的工具變數time，定義一個for，這裡我們的zpcb已經有了我們所有的進程，所以我們直接zpcb[0]->atime==zpcb[time]->atime，看看我們的for循環運行與否，如果我們的time大於了1，說明在此刻已經有進程同時到達了，這時候我們要去比較它們的優先順序決定誰位於對首，後面的運行中我們肯定是不止一次要進行一個比較優先順序的操作，我們為什麼不將這個封裝成函數呢，既然如此，干就完事了。
sort函數：比較優先順序，在同時為第一時間到達的進程中將優先順序高的放置與首，進程優先順序n越大就說明優先順序越高
void sort(int time)
{
int i=1;
while(zpcb[i]&&time>=zpcb[i]->atime)i++;
for(int j=0; j<i-1; j++)
for(int k=j+1; k<i; k++)if(zpcb[j]->n<zpcb[k]->n)
{
PCB c=zpcb[j];
zpcb[j]=zpcb[k];
zpcb[k]=c;
}
}
這裡直接給出程式碼，因為太簡單，就用了一個排序默認你們都可以看懂
接下來我們回到我們的psa調度演算法，這裡給出了之後我們的工具變數time可以做回本職工作了，將第一個的到達時間設置為time，也就是zpcb[0]—>atime;
接下來開始我們的調度，我們首先用一個大while，條件是num>0,
我們需要考慮幾種情況，第一種情況，//如果第二個進程還未到達，第一個進程就開始運行//優先順序減一，運行時間和總的時間加1，狀態置為run
第二種情況，第二個進程到達了
這裡是第一種情況
大致思想：首先我們讓第一個進程的utime++ 系統時間++ 在這個同時讓我們的優先順序-- 因為已經進行了一次對cpu的使用，狀態置為r 這時候我們找一找有沒有到達的進程，比較優先順序，輸出正在運行的進程，在這個同時我們也要將優先順序最高且到達的進程至於第一個，輸出一下我們的就緒隊列，也就是已經到達的進程，已經就緒的進程，看看有沒有完成的進程，如果有就狀態置為f計算兩個時間，將zpc中的第一個進程覆蓋掉因為已經調度完了，如果沒有完成，我們就讓它置為等待，進行新的判斷。
這裡我們還有一個問題就是我們的進程重新的進行了排序輸出了就緒隊列，我們同時也需要輸出當前所有進程的狀態，因為並不是所有的進程都是就緒了，因此這裡需要輸出，在後面我們進行了換位也好，調度完成了都是需要使用，這裡就需要一個show，展示當前所有進程的狀態，這裡直接給出
void show(bool n)
{
for(PCB p=head->next;p!=NULL;p=p->next)
{
if(n)
cout<<"進程名:"<<p->pname<<" 優先順序數："<<p->n<<"到達時間:"<<p->atime<<" 運行時間:"<<p->rtime<<" 已用運行時間："<<p->utime<<" 狀態:"<<p->status<<endl;
else cout<<"進程名:"<<p->pname<<" 到達時間:"<<p->atime<<" 運行時間:"<<p->rtime<<" 已用運行時間："<<p->utime<<" 狀態:"<<p->status<<endl;
}
cout<<"++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
}
因為大致思想描述可能需要程式碼參考，也在這附上我的程式碼
if(zpcb[1]&&time<zpcb[1]->atime||!zpcb[1])//如果第二個進程還未到達，第一個進程就開始運行
//優先順序減一，運行時間和總的時間加1，狀態置為run
{
zpcb[0]->utime++;
time++;
if(zpcb[0]->n!=0)zpcb[0]->n--;
zpcb[0]->status='R';
int i;
for(i=1; zpcb[i]; i++)if(time>=zpcb[i]->atime);
else break;//找看有沒有比第二個進程先到達的進程
for(int j=1; j<i-1; j++)//如果優先順序比第二個的高就換位
for(int k=j+1; k<i; k++)if(zpcb[j]->n<zpcb[k]->n)
{
PCB t=zpcb[j];
zpcb[j]=zpcb[k];
zpcb[k]=t;
}
printf("正在運行的進程：%c\t",zpcb[0]->pname);
printf("就緒隊列：");
for(int i=1; zpcb[i]; i++)
if(time>=zpcb[i]->atime) printf("%c ",zpcb[i]->pname);//輸出到達時間到了系統時間的進程，為就緒隊列
printf("\n");
show(true);
if(zpcb[0]->utime==zpcb[0]->rtime)//如果當前進程運行完了狀態為F，平均和帶權根據公式，將後一個覆蓋前一個
{//再去查看有與系統時間time相同的到達時間或者在之前到達，比較優先順序
zpcb[0]->status='F';
time1+=time-zpcb[0]->atime;
time2+=(double)(time-zpcb[0]->atime)/zpcb[0]->utime;
int i;
for( i=1; zpcb[i]; i++)zpcb[i-1]=zpcb[i];
zpcb[i-1]=NULL;
num--;
sort(time);
}
else//如果沒運行完就等待，根據優先順序再度確定下一個要運行的進程
{
zpcb[0]->status='W';
if( zpcb[1]!=NULL) sort(time);
}
}
希望讀者能夠自主的編碼，
第二個情況是第二個進程到達了，比較到達了之後的優先順序分為大於和小於第一個進程，後面與前面一樣
else//第二個進程到達了
{
if( zpcb[1]&& zpcb[0]->n>= zpcb[1]->n||! zpcb[1])//如果第二個進程也到達了，且優先順序小於第一個進程
{
zpcb[0]->utime++;
time++;
if( zpcb[0]->n!=0) zpcb[0]->n--;
zpcb[0]->status='R';
}
else//如果優先順序比第一個進程高，那麼第一個進程等待，將其換位置，運行
{
zpcb[0]->status='W';
sort(time);
zpcb[0]->utime++;
time++;
if( zpcb[0]->n!=0) zpcb[0]->n--;
zpcb[0]->status='R';
}
int i;
for(i=1; zpcb[i]; i++)if(time>= zpcb[i]->atime);
else break;
for(int j=1; j<i-1; j++)
for(int k=j+1; k<i; k++)if( zpcb[j]->n< zpcb[k]->n)
{
PCB t= zpcb[j];
zpcb[j]= zpcb[k];
zpcb[k]=t;
}//與上一個一樣，下一個進程到達了，比較優先順序
printf("正在運行的進程：%c\t", zpcb[0]->pname);
printf("就緒隊列：");//輸出就緒隊列，判斷是否完成
for(int i=1; zpcb[i]; i++)if(time>= zpcb[i]->atime)printf("%c ", zpcb[i]->pname);
printf("\n");
show(true);
if( zpcb[0]->utime== zpcb[0]->rtime)
{
zpcb[0]->status='F';
time1+=time- zpcb[0]->atime;
time2+=(double)(time- zpcb[0]->atime)/ zpcb[0]->utime;
int i;
for( i=1; zpcb[i]; i++) zpcb[i-1]= zpcb[i];
zpcb[i-1]=NULL;
num--;
sort(time);
}
else
{
zpcb[0]->status='W';
if( zpcb[1]!=NULL)sort(time);
}
}
}
最後大while結束，輸出最終的進程的資訊和兩個時間time1 time2 清楚狀態，輸出進程隊列的初始隊列，等待下一輪新的選擇。PSA到此結束
接下來是FCFS先來先服務
基本思想：在這已經沒有優先順序的概念了，定義好pc指針和time，（這裡我們沒有改變其他的，可以直接用head隊列，也就是pc。）記得初始化兩個時間，我們直接一個大while進行使用，讓系統時間和utime進行++就好，每進行一次輸出就緒隊列，發現有完成了也是覆蓋，最後輸出最終情況，清零，展示原始狀態，這裡比較的簡單我就不貼程式碼了，讀者自行編碼。
短進程優先
//短進程優先
//當做了幾個之後，其實是差不多的，這裡的優先順序是作業的使用時間
//即utime，剛開始第一個我們判斷是否存在且第二個是否到達
//然後分情況進行處理，跟前面的程式碼有重合，其實可以封裝一下算時間的等等，
//
基本思想：這裡跟前面一樣進行初始化，用zpcb數組，一個while，接下來想想會有幾種情況，第一種後面的進程還沒來，第二種後面的進程來了。
假如沒來，直接讓它完成，不用++直接+rtime。輸出各個隊列，覆蓋，狀態置為f，兩個time，num--
如果來了，比較誰的rtime小，置於第一個，接下來是一樣的操作，就不敘述了，這裡附上程式碼，留給讀者進行參考，很簡單希望自己編碼。
void SJF(int num){
int n = num;
PCB pc=head->next;
int time=0;
time1=time2=0;
for(time=0;time<N;time++)if(pc){
zpcb[time]=pc;
pc=pc->next;
}
time = zpcb[0]->atime;
while(num>0){
if(zpcb[1]&&time<zpcb[1]->atime||!zpcb[1]){
zpcb[0]->utime+=zpcb[0]->rtime;
time+=zpcb[0]->rtime;
zpcb[0]->status='R';
printf("正在運行的進程：%c\t",zpcb[0]->pname);
printf("就緒隊列：");
for(int i = 1;zpcb[i]&&time>zpcb[i]->atime;i++)
cout<<zpcb[i]->pname;
cout<<endl;
show(false);
if(zpcb[0]->utime==zpcb[0]->rtime){
zpcb[0]->status='F';
time1+=time-zpcb[0]->atime;
time2+=(float)(time-zpcb[0]->atime)/zpcb[0]->utime;
int i;
for(i = 1; zpcb[i];i++)zpcb[i-1]=zpcb[i];
zpcb[i-1]=NULL;
num--;
}
}
else{
int i;
for(i=1;zpcb[i];i++)if(time>=zpcb[i]->atime);
else break;
for(int j=0;j<i-1;j++)
for(int k = j+1;k<i;k++)if(zpcb[j]->rtime>zpcb[k]->rtime){
PCB t=zpcb[j];
zpcb[j]=zpcb[k];
zpcb[k]=t;
}
zpcb[0]->utime+=zpcb[0]->rtime;
time+=zpcb[0]->rtime;
zpcb[0]->status='R';
cout<<"正在運行的進程："<<'\t'<<zpcb[0]->pname;
printf("就緒隊列：");
for(i= 1;zpcb[i]&&time>zpcb[i]->atime;i++)
cout<<zpcb[i]->pname;
cout<<endl;
show(false);
if(zpcb[0]->utime==zpcb[0]->rtime){
zpcb[0]->status='F';
time1+=time-zpcb[0]->atime;
time2+=(float)(time-zpcb[0]->atime)/zpcb[0]->utime;
num--;
}
}
}
cout<<"最終的進程資訊："<<endl;
show(false);
clean();
cout<<"平均周轉時間："<<(float)(time1/n)<<" 平均帶權周轉時間："<<(float)(time2/n)<<endl<<endl;
show(false);
}
多級回饋MFQ 這個演算法我的程式碼有問題在此只敘述思想
關於初始化這裡可以給出：
void MFQ(int num){
int n=num;
PCB head1[N],head2[N],head3[N],pc=head->next; //三個優先順序隊列
int time=pc->atime;
time1=0;
time2=0;
for(int i=0; i<N; i++)head1[i]=head2[i]=head3[i]=NULL;//每個就緒清空
head1[0]=pc;//放入第一個
pc=pc->next;
接下來就是while分情況，後續沒到達，後續到達。
後續沒到達也需要分情況，首先就是看看優先順序最高到最低，從h0（head0）到h3中哪一個是有進程的，讓它進行一個使用，並輸出其他的兩個隊列的進程，如果三個都沒有，我們將pc指向的進程進行一個放入h1中，看看情況如何，最後展示當前進程的一個情況。。。看當前的進程隊列0-2中是否有已經完成進程，有就狀態置為f,覆蓋，num--，計算時間12，沒有就投放下一級隊列如果head3中就將其放到最後。
第二種情況中，我們需要判斷pc是不是結束標誌，如果不是加入head1後，繼續運行一個時間片，輸出情況，判斷是否執行完，如果沒有後續進程，將每個隊列中的進程由0-2的優先順序進行執行，判斷是否完成，丟入下級。
最後輸出情況
基本的思想我都已經實現，但是會有一些問題，希望寫出程式碼的同志評論區走一走，最後我們的程式碼就編完了，希望多級回饋能夠有一個更好的程式碼，我的程式碼就不附上了。。。
完結撒花！！！
