一、 實驗目的
(1)加深對作業排程算法的了解;
(2)進行程式設計的訓練。
二、 實驗内容和要求
用進階語言編寫一個或多個作業排程的模拟程式。
單道批處理系統的作業排程程式。作業一投入運作,它就占有計算機的一切資源直到作業完成為止,是以排程作業時不必考慮它所需要的資源是否得到滿足,它所運作的時間等因素。
作業排程算法:
1) 采用先來先服務(FCFS)排程算法,即按作業到達的先後次序進行排程。總是首先排程在系統中等待時間最長的作業。
2) 短作業優先 (SJF) 排程算法,優先排程要求運作時間最短的作業。
3) 響應比高者優先(HRRN)排程算法,為每個作業設定一個優先權(響應比),排程之前先計算各作業的優先權,優先數高者優先排程。RP (響應比)= 作業周轉時間 / 作業運作時間=1+作業等待時間/作業運作時間
每個作業由一個作業控制塊JCB表示,JCB可以包含以下資訊:作業名、送出(到達)時間、所需的運作時間、所需的資源、作業狀态、鍊指針等等。
作業的狀态可以是等待W(Wait)、運作R(Run)和完成F(Finish)三種之一。每個作業的最初狀态都是等待W。
2.1 模拟資料的生成
1. 允許使用者指定作業的個數(2-24),預設值為5。
2. 允許使用者選擇輸入每個作業的到達時間和所需運作時間。
3. (**)從檔案中讀入以上資料。
4. (**)也允許使用者選擇通過僞随機數指定每個作業的到達時間(0-30)和所需運作時間(1-8)。
2.2 模拟程式的功能
1. 按照模拟資料的到達時間和所需運作時間,執行FCFS, SJF和HRRN排程算法,程式計算各作業的開始執行時間,各作業的完成時間,周轉時間和帶權周轉時間(周轉系數)。
2. 動态示範每排程一次,更新現在系統時刻,處于運作狀态和等待各作業的相應資訊(作業名、到達時間、所需的運作時間等)對于HRRN算法,能在每次排程時顯示各作業的響應比R情況。
3. (**)允許使用者在模拟過程中送出新作業。
4. (**)編寫并排程一個多道程式系統的作業排程模拟程式。 隻要求作業排程算法:采用基于先來先服務的排程算法。 對于多道程式系統,要假定系統中具有的各種資源及數量、排程作業時必須考慮到每個作業的資源要求。
2.3 模拟資料結果分析
1. 對同一個模拟資料各算法的平均周轉時間,周轉系數比較。
2. (**)用曲線圖或柱形圖表示出以上資料,分析算法的優點和缺點。
2.4 其他要求
1. 完成報告書,内容完整,規格規範。
2. 實驗須檢查,回答實驗相關問題。
注:帶**号的條目表示選做内容。
三、 實驗方法、步驟及結果測試
1.流程圖
2.源程式
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100
typedef struct
{
char name[4];//程序名
int starttime;//到達系統時間
int needtime;//運作時間
int runtime;//周轉時間
int endtime;//完成時間
int waittime;//等待時間
double XYB;//響應比
double DQZZ_Time;//帶權周轉時間
}pr;
pr a[MAX];
void input(int n)
{
int i;
for(i=0;i<n;i++)
{
printf("name:");
scanf("%s",&a[i].name);
printf("\n");
printf("starttime:");
scanf("%d",&a[i].starttime);
printf("\n");
printf("needtime:");
scanf("%d",&a[i].needtime);
printf("\n");
}
}
void FCFS(int n)//先來先服務
{
int i,j,time1,time2;
char temp[4];
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
if(a[j].starttime>a[j+1].starttime)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
for(i=0;i<n;i++)
{
//第一個程序
if(i==0)
{
a[i].runtime=a[i].needtime;
a[i].endtime=a[i].starttime+a[i].runtime;
}
else
{
if(a[i].starttime>a[i-1].endtime)
{
a[i].runtime=a[i].needtime;
a[i].endtime=a[i].starttime+a[i].runtime;
}
else
{
a[i].runtime=a[i].needtime+a[i-1].endtime-a[i].starttime;
a[i].endtime=a[i].starttime+a[i].runtime;
}
}
a[i].DQZZ_Time=a[i].runtime*1.0/a[i].needtime;
}
}
//最短作業優先,假設在前3個作業運作完之前所有作業均已到達
void SJF(int n)
{
int i,j,time1,time2;
int b=0,c=0,d=0;
char temp[4];
//先按到達時間排序
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
if(a[j].starttime>a[j+1].starttime)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
a[0].endtime=a[0].starttime+a[0].needtime;
for(i=1;i<n;i++)
{
if(a[i].starttime<a[0].endtime)
b++; //作業到達但第0個作業還在運作時
//用b統計需等待作業0運作的作業個數
}
for(i=1;i<b+1;i++)
{//已經到達的但要等待第0個作業運作完的作業按最短運作時間排序
for(j=1;j<b+1-1;j++)
{
if(a[j].needtime>a[j+1].needtime)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
if(a[1].starttime>a[0].endtime) a[1].endtime=a[1].starttime+a[1].needtime;
else a[1].endtime=a[0].endtime+a[1].needtime;
for(i=2;i<n;i++)
{
if(a[i].starttime<a[1].endtime)
c++; //作業到達但第1個作業還在運作時
//用c統計需等待作業1運作的作業個數
}
for(i=2;i<c+2;i++)
{//已經到達的但要等待第1個作業運作完的作業按最短運作時間排序
for(j=2;j<c+2-1;j++)
{
if(a[j].needtime>a[j+1].needtime)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
if(a[2].starttime>a[1].endtime) a[2].endtime=a[2].starttime+a[2].needtime;
else a[2].endtime=a[1].endtime+a[2].needtime;
for(i=3;i<n;i++)
{
if(a[i].starttime<a[2].endtime)
d++; //作業到達但第2個作業還在運作時
//用d統計需等待作業2運作的作業個數
}
for(i=3;i<d+3;i++)
{//已經到達的但要等待第2個作業運作完的作業按最短運作時間排序
for(j=3;j<d+3-1;j++)
{
if(a[j].needtime>a[j+1].needtime)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
for(i=0;i<n;i++)
{
if(a[i].starttime>a[i-1].endtime)
{
a[i].endtime=a[i].starttime+a[i].needtime;
a[i].runtime=a[i].needtime;
}
else
{
a[i].endtime=a[i-1].endtime+a[i].needtime;
a[i].runtime=a[i].endtime-a[i].starttime;
}
a[i].DQZZ_Time=a[i].runtime*1.0/a[i].needtime;
}
}
//最高響應比優先,隻寫了按到達時間的順序前4個作業有效
void HRRF(int n)
{
int i,j,time1,time2;
char temp[4];
//先按到達時間排序
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
if(a[j].starttime>a[j+1].starttime)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
a[0].endtime=a[0].starttime+a[0].needtime;
for(i=1;i<n;i++)
{
a[i].waittime=a[0].endtime-a[i].starttime;
a[i].XYB=1+(a[i].waittime/a[i].needtime);
}
//運作完作業0後,剩下的作業按響應比高到低排序
for(i=1;i<n-1;i++)
{
for(j=1;j<n-i-1;j++)
{
if(a[j].XYB<a[j+1].XYB)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
a[1].endtime=a[0].endtime+a[1].needtime;
for(i=2;i<n;i++)
{
a[i].waittime=a[1].endtime-a[i].starttime;
a[i].XYB=1+(a[i].waittime/a[i].needtime);
}
//運作完作業1後,剩下的作業按響應比高到低排序
for(i=2;i<n-1;i++)
{
for(j=2;j<n-i-1;j++)
{
if(a[j].XYB<a[j+1].XYB)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
a[2].endtime=a[1].endtime+a[2].needtime;
for(i=3;i<n;i++)
{
a[i].waittime=a[2].endtime-a[i].starttime;
a[i].XYB=1+(a[i].waittime/a[i].needtime);
}
//運作完作業2後,剩下的作業按響應比高到低排序
for(i=3;i<n-1;i++)
{
for(j=3;j<n-i-1;j++)
{
if(a[j].XYB<a[j+1].XYB)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
a[3].endtime=a[2].endtime+a[3].needtime;
for(i=4;i<n;i++)
{
a[i].waittime=a[3].endtime-a[i].starttime;
a[i].XYB=1+(a[i].waittime/a[i].needtime);
}
//運作完作業3後,剩下的作業按響應比高到低排序
for(i=4;i<n-1;i++)
{
for(j=4;j<n-i-1;j++)
{
if(a[j].XYB<a[j+1].XYB)
{
time1=a[j].starttime;
a[j].starttime=a[j+1].starttime;
a[j+1].starttime=time1;
time2=a[j].needtime;
a[j].needtime=a[j+1].needtime;
a[j+1].needtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
for(i=0;i<n;i++)
{
if(a[i].starttime>a[i-1].endtime)
{
a[i].endtime=a[i].starttime+a[i].needtime;
a[i].runtime=a[i].needtime;
}
else
{
a[i].endtime=a[i-1].endtime+a[i].needtime;
a[i].runtime=a[i].endtime-a[i].starttime;
}
a[i].DQZZ_Time=a[i].runtime*1.0/a[i].needtime;
}
}
void output(int n)
{
int sum_Time=0;//作業總周轉時間
double sum_DQ=0;//作業總帶權周轉時間
int i;
printf("\tname starttime needtime runtime endtime \tDQZZ_Time\n");
for(i=0;i<n;i++)
{
printf("%8s%10d%10d%10d%10d\t%10lf\n",a[i].name,a[i].starttime,a[i].needtime,a[i].runtime,a[i].endtime,a[i].DQZZ_Time);
sum_Time+=a[i].runtime;
sum_DQ+=a[i].DQZZ_Time;
}
printf("平均作業周轉時間為:%.2lf\n",sum_Time*1.0/n);
printf("平均帶權作業周轉時間為:%.2lf\n",sum_DQ*1.0/n);
printf("\n");
}
int main()
{
int n,i;
printf("請輸入程序數n:");
scanf("%d",&n);
input(n);
output(n);
while(1)
{
printf("1.先來先服務FCFS\n2.最短作業優先SJF\n3.最高響應比優先\n4.退出\n");
scanf("%d",&i);
if(i==1)
{
printf("\t\t\t\t1.先來先服務FCFS\n");
FCFS(n);
output(n);
}
if(i==2)
{
printf("\t\t\t\t2.最短作業優先SJF\n");
SJF(n);
output(n);
}
if(i==3)
{
printf("\t\t\t\t3.最高響應比優先\n");
HRRF(n);
output(n);
}
if(i==4)
{
exit(0);
}
}
}
3.運作結果及分析
四、 實驗總結
知道如何實作算法就是不知如何使程式實作,去網上查找了一些資料,經過很久才搞定。
轉載于:https://www.cnblogs.com/wengshen/p/4974537.html