操作系統原理與實驗——實驗三優先級進程調度

實驗指南

運行環境：

Dev c++

算法思想：?

本實驗是模擬進程調度中的優先級算法，在先來先服務算法的基礎上，只需對就緒隊列到達時間進行一次排序。第一個到達的進程首先進入CPU，將其從就緒隊列中出隊后。若此后隊首的進程的到達時間大于上一個進程的完成時間，則該進程進入CPU，其開始時間即到達時間；否則如果上一個進程完成后，已經有多個進程到達，則需從已到達的進程中尋找到優先級最高的進程，并將其取出，進入CPU執行。直到所有進程執行完畢。

核心數據結構：

typedef struct data{

????? int hour;

????? int minute;

}time;

typedef struct node{

?????

????? int id;//進程編號

????? char name[20];//進程名

????? int good;//優先級

????? time arrive;//到達就緒隊列的時間

????? int zx;//執行時間

????? time start;//開始執行時間

????? time finish;//執行完成時間

????? int zz;//周轉時間=執行完成時間-到達就緒隊列時間

????? float zzxs;//帶權周轉時間=周轉時間/執行時間

????? struct node* next;

?????

}Node;

typedef struct Queue{

?????

????? Node* front = NULL;

????? Node* tail = NULL;

?????

}Queue;

程序主體框架：

#include <iostream>

#include <stdio.h>

#include <malloc.h>

#include <string.h>

using namespace std;

typedef struct data{

??? int hour;

??? int minute;

}time;

typedef struct node{

???

??? int id;//進程編號

??? char name[20];//進程名

??? int good;//優先級

??? time arrive;//到達就緒隊列的時間

??? int zx;//執行時間

??? time start;//開始執行時間

??? time finish;//執行完成時間

??? int zz;//周轉時間=執行完成時間-到達就緒隊列時間

??? float zzxs;//帶權周轉時間=周轉時間/執行時間

??? struct node* next;

???

}Node;

typedef struct Queue{

???

??? Node* front = NULL;

??? Node* tail = NULL;

???

}Queue;

Queue* init(){

???

??? Queue* p = (Queue*)malloc(sizeof(Queue));

??? p->front = NULL;

??? p->tail = NULL;

??? return p;

???

}

//函數名：timecompare()????????? 參數:tt 當前時間, p 進程到達時間

bool timecompare(time tt,time p){//tt<p(時間沒到) false??? tt >= p true

??? //函數功能：比較進程到達時間和當前時間，若小于則返回false，否則返回true

???

}

//函數名：timecompare2()????????? 參數:tt 當前時間, p 進程到達時間

bool timecompare2(time tt,time p){//tt<=p(時間沒到) false??? tt > p true

??? //函數功能：比較進程到達時間和當前時間，若小于等于則返回false，否則返回true

???

}

//函數名：Levelcompare()????????? 參數:p,q 進程

bool Levelcompare(Node* p,Node* q){

??? //函數功能：比較p,q的優先級，p的優先級高則返回true，低則返回false，否則比較到達時間，p先或同時到達則返回true，反之則false

???

}

//函數名：LevelSorted()????????? 參數:que 進程隊列指針

void LevelSorted(Queue* que){

//函數功能：對進程隊列按優先級排序

???

}

//函數名：ComputeTime()??? 參數:tt 當前時間的指針,q 當前進程的指針

time ComputeTime(time* tt,Node* q){

???

//函數功能：更新當前時間和進程的各項時間

??????????

}

//函數名：priority()??? 參數:que進程隊列指針,tt當前時間 n 進程數

Queue* priority(Queue *que,time tt,int n){

???

//函數功能：進行優先級進程調度，并同時更新當前時間。

???

}

//函數名：Print()??? 參數:que進程隊列指針, n 進程數

void Print(Queue* que,int n){

??? //函數功能：打印輸出進程優先進程調度結果

???

}

//函數名：ScanIn()??? 參數:wait進程隊列指針, n 進程數

time ScanIn(Queue* wait,int n){

???

??? //函數功能：輸入進程信息，返回最早的進程到達時間

??????????

}

int main(){

???

??? Queue* wait;

??? wait = init();

??? int flag,n;

??? time earlytime;

???

??? while(1){

?????? printf("請輸入操作:(1:開始進程;0:結束進程):");

?????? scanf("%d",&flag);

?????? if(flag == 0){

?????????? printf("\n操作結束!\n");

?????????? break;

?????? }

?????? else{

?????????? printf("請輸入進程數量:");

?????????? scanf("%d",&n);

?????????? earlytime = ScanIn(wait,n);

??????????

?????????? LevelSorted(wait);

?????????? wait = priority(wait,earlytime,n);

?????????? Print(wait,n);

?????????? wait = init();

??????????

?????? }

??? }

???

??? return 0;

}

????

測試數據

/*

1001 p1 1 9:40 20
1004 p4 4 10:10 10
1005 p5 3 10:05 30
1002 p2 3 9:55 15
1003 p3 2 9:45 25

*/

/*

5001 p1 1 14:40 20
5002 p4 2 10:10 10
5003 p5 3 10:05 30
5004 p2 4 9:55 15
5005 p3 5 9:45 25
5006 p6 6 10:40 20
5007 p8 7 11:10 10?
5008 p9 8 12:05 30
5009 p10 9 13:55 15
5010 p7 10 7:15 15

*/

關鍵代碼

#include <iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
using namespace std;typedef struct data{int hour;int minute;
}time;typedef struct node{int id;//進程編號 char name[20];//進程名 int good;//優先級 time arrive;//到達就緒隊列的時間 int zx;//執行時間 time start;//開始執行時間 time finish;//執行完成時間 int zz;//周轉時間=執行完成時間-到達就緒隊列時間 float zzxs;//帶權周轉時間=周轉時間/執行時間 struct node* next;}Node;typedef struct Queue{Node* front = NULL;Node* tail = NULL;}Queue;
void Print(Queue* que,int n);
Queue* init(){Queue* p = (Queue*)malloc(sizeof(Queue));p->front = NULL;p->tail = NULL;return p;} 
//函數名：timecompare()          參數:tt 當前時間, p 進程到達時間
bool timecompare(time tt,time p){//tt<p(時間沒到) false    tt >= p true //函數功能：比較進程到達時間和當前時間，若小于則返回false，否則返回true if((tt.hour<p.hour)||((tt.hour==p.hour)&&(tt.minute<p.minute)))return false;elsereturn true;
}
//函數名：timecompare2()          參數:tt 當前時間, p 進程到達時間
bool timecompare2(time tt,time p){//tt<=p(時間沒到) false    tt > p true //函數功能：比較進程到達時間和當前時間，若小于等于則返回false，否則返回trueif((tt.hour<p.hour)||((tt.hour==p.hour)&&(tt.minute<p.minute||tt.minute==p.minute)))return false;elsereturn true;
}
//函數名：Levelcompare()          參數:p,q 進程
bool Levelcompare(Node* p,Node* q){//函數功能：比較p,q的優先級，p的優先級高則返回true，低則返回false，否則比較到達時間，p先或同時到達則返回true，反之則falseif(p->good>q->good)return true;else if(p->good<q->good)return false;else{if((p->arrive.hour<q->arrive.hour)||(p->arrive.hour==q->arrive.hour&&p->arrive.minute<=q->arrive.minute))return true;elsereturn false;}}
//函數名：LevelSorted()          參數:que 進程隊列指針
void LevelSorted(Queue* que){//函數功能：對進程隊列按優先級排序	Node *bl,*head=NULL,*pre=NULL,*q=NULL,*p,*c;bl=que->front;while(bl!=NULL){Node *p=(Node *)malloc(sizeof(Node));*p=*bl;//重點：指針的應用 p->next=NULL;if(head==NULL){head=p;q=p;}else{q=head;pre=NULL;while(q!=NULL){if(Levelcompare(p,head)){p->next=head;head=p;q=head;break;}else if(!Levelcompare(p,q)&&q->next==NULL){q->next=p;break;}else if(Levelcompare(p,q)){p->next=q;pre->next=p;break;}pre=q;q=q->next;}}bl=bl->next;}que->front=head;que->tail=pre;}//函數名：ComputeTime()    參數:tt 當前時間的指針,q 當前進程的指針
time ComputeTime(time* tt,Node* q){//函數功能：更新當前時間和進程的各項時間q->start.hour=tt->hour;q->start.minute=tt->minute;q->finish.minute=(q->start.minute+q->zx)%60;q->finish.hour=q->start.hour+(q->start.minute+q->zx)/60;q->zz=q->finish.hour*60+q->finish.minute-q->arrive.hour*60-q->arrive.minute;q->zzxs=q->zz*1.0/q->zx;tt->hour=q->finish.hour;tt->minute=q->finish.minute;}
//函數名：priority()    參數:que進程隊列指針,tt當前時間 n 進程數
Queue* priority(Queue *que,time tt,int n){//函數功能：進行優先級進程調度，并同時更新當前時間。
int count=n;Node *pre=NULL,*p=NULL,*head=NULL,*q=NULL,*Head;Head=que->front;p=Head;while(1){if((p->arrive.hour==tt.hour)&&(p->arrive.minute==tt.minute)){break;}pre=p;p=p->next;}	Node *N=(Node *)malloc(sizeof(Node));*N=*p;N->next=NULL;head=N;q=head;if(p==Head){Head=Head->next;free(p);count--;}else{pre->next=p->next;free(p);count--;}ComputeTime(&tt,N);while(count){p=Head;pre=NULL;while(p!=NULL){if(timecompare2(tt,p->arrive)==true)//提前到達 {Node *N=(Node *)malloc(sizeof(Node));*N=*p;N->next=NULL;q->next=N;q=q->next;if(p==Head){Head=Head->next;free(p);count--;}else{pre->next=p->next;free(p);count--;}ComputeTime(&tt,N);break;}pre=p;p=p->next;}if(p==NULL)//按到達時間先后 {Node *l,*r;l=Head;r=Head;while(r!=NULL){if(timecompare2(l->arrive,r->arrive)){l=r;}r=r->next;}//找到最小到達時間 tt.hour=l->arrive.hour;tt.minute=l->arrive.minute;Node *N=(Node *)malloc(sizeof(Node));*N=*l;N->next=NULL;q->next=N;q=q->next;pre=Head;if(l==Head){Head=Head->next;free(l);count--;}else{while(pre->next!=l){pre=pre->next;}pre->next=l->next;free(l);count--;}ComputeTime(&tt,N);}}que->front=head;return que;
}
//函數名：Print()    參數:que進程隊列指針, n 進程數
void Print(Queue* que,int n){//函數功能：打印輸出進程優先進程調度結果float pz=0,px=0;Node *p;p=que->front;printf("模擬進程優先進程調度過程輸出結果\n  id號    名字\t優先級\t到達時間  執行時間（分鐘）\t開始時間\t完成時間  周轉時間（分鐘）  帶權周轉系數\n"); while(p!=NULL){printf("%6d %6s %6d %6d:%02d %10d %17d:%02d %12d:%02d %10d(分鐘) %12.2f\n",p->id,p->name,p->good,p->arrive.hour,p->arrive.minute,p->zx,p->start.hour,p->start.minute,p->finish.hour,p->finish.minute,p->zz,p->zzxs);pz=pz+p->zz;px=px+p->zzxs;p=p->next;} printf("系統平均周轉時間為：\t\t\t\t\t\t\t\t\t%.2f\n",pz/n);printf("系統平均帶權周轉系數為:        \t\t\t\t\t\t\t\t\t\t%.2f\n",px/n);
}
//函數名：ScanIn()    參數:wait進程隊列指針, n 進程數
time ScanIn(Queue* wait,int n){//函數功能：輸入進程信息，返回最早的進程到達時間int count; count=n;time N;Node *q;q=wait->tail;printf("請輸入進程的參數:\nid號 名字 優先級 到達時間 執行時間（分鐘）：\n");while(count--){Node *p=(Node *)malloc(sizeof(Node));p->next=NULL;scanf("%d %s %d %d:%d %d",&p->id,&p->name,&p->good,&p->arrive.hour,&p->arrive.minute,&p->zx);if(wait->front==NULL&&wait->tail==NULL){wait->front=p;q=p;N.hour=p->arrive.hour;N.minute=p->arrive.minute;}else{q->next=p;q=p;wait->tail=p;if((p->arrive.hour<N.hour)||((p->arrive.hour==N.hour)&&(p->arrive.minute<N.minute))){N.hour=p->arrive.hour;N.minute=p->arrive.minute;}}}return N;
}int main(){Queue* wait;wait = init();int flag,n;time earlytime;while(1){printf("請輸入操作:(1:開始進程;0:結束進程):");scanf("%d",&flag);if(flag == 0){printf("\n操作結束!\n");break; } else{printf("請輸入進程數量:");scanf("%d",&n);earlytime = ScanIn(wait,n);//函數功能：輸入進程信息，返回最早的進程到達時間LevelSorted(wait);//函數功能：對進程隊列按優先級排序wait = priority(wait,earlytime,n);//函數功能：進行優先級進程調度，并同時更新當前時間。Print(wait,n);//函數功能：打印輸出進程優先進程調度結果wait = init();}}return 0;}