一、目的和要求
1. 實驗目的
（1）加深對作業排程算法的了解；
（2）進行程式設計的訓練。
2．實驗要求
用進階語言編寫一個或多個作業排程的模拟程式。
單道批處理系統的作業排程程式。作業一投入運作，它就占有計算機的一切資源直到作業完成為止，是以排程作業時不必考慮它所需要的資源是否得到滿足，它所運作的時間等因素。
作業排程算法：
1) 采用先來先服務（FCFS）排程算法，即按作業到達的先後次序進行排程。總是首先排程在系統中等待時間最長的作業。
2) 短作業優先 (SJF) 排程算法，優先排程要求運作時間最短的作業。
3) 響應比高者優先(HRRN)排程算法，為每個作業設定一個優先權(響應比)，排程之前先計算各作業的優先權，優先數高者優先排程。RP (響應比)＝ 作業周轉時間 / 作業運作時間=1+作業等待時間/作業運作時間
每個作業由一個作業控制塊JCB表示，JCB可以包含以下資訊：作業名、送出（到達）時間、所需的運作時間、所需的資源、作業狀态、鍊指針等等。
作業的狀态可以是等待W（Wait）、運作R（Run）和完成F（Finish）三種之一。每個作業的最初狀态都是等待W。
一、 模拟資料的生成
1． 允許使用者指定作業的個數（2-24），預設值為5。
2． 允許使用者選擇輸入每個作業的到達時間和所需運作時間。
3． （**）從檔案中讀入以上資料。
4． （**）也允許使用者選擇通過僞随機數指定每個作業的到達時間（0-30）和所需運作時間（1-8）。
二、 模拟程式的功能
1． 按照模拟資料的到達時間和所需運作時間，執行FCFS, SJF和HRRN排程算法，程式計算各作業的開始執行時間，各作業的完成時間，周轉時間和帶權周轉時間（周轉系數）。
2． 動态示範每排程一次，更新現在系統時刻，處于運作狀态和等待各作業的相應資訊（作業名、到達時間、所需的運作時間等）對于HRRN算法，能在每次排程時顯示各作業的響應比R情況。
3． （**）允許使用者在模拟過程中送出新作業。
4． （**）編寫并排程一個多道程式系統的作業排程模拟程式。 隻要求作業排程算法：采用基于先來先服務的排程算法。 對于多道程式系統，要假定系統中具有的各種資源及數量、排程作業時必須考慮到每個作業的資源要求。
三、 模拟資料結果分析
1． 對同一個模拟資料各算法的平均周轉時間，周轉系數比較。
2． （**）用曲線圖或柱形圖表示出以上資料，分析算法的優點和缺點。
四、 實驗準備
| 序号 | 準備内容 | 完成情況 |
| 1 | 什麼是作業？ | 作業相當于一個程式。 任務相當于整個程式中的一段段可以并發執行的代碼。 程序其實就是任務。從系統的角度看，作業則是一個比程式更廣的概念。它由程式、資料和作業說明書組成。系統通過作業說明書控制檔案形式的程式和資料，使之執行和操作。而且，在批處理系統中，作業是搶占記憶體的基本機關。也就是說，批處理系統以作業為機關把程式和資料調入記憶體以便執行。 |
| 2 | 一個作業具備什麼資訊？ | 作業由三部分組成，即程式、資料和作業說明書。一個作業可以包含多個程式和多個資料集，但必須至少包含一個程式。否則将不成為作業。 |
| 3 | 為了友善模拟排程過程，作業使用什麼方式的資料結構存放和表示？JCB | 由作業說明書在系統中生成一個稱為作業控制塊(job control block，JCB)的表格。該表格登記該作業所要求的資源情況、預計執行時間和執行優先級等。進而，作業系統通過該表了解到作業要求，并配置設定資源和控制作業中程式和資料的編譯、連結、裝入和執行等。 |
| 4 | 作業系統中，常用的作業排程算法有哪些？ | 先來先服務、輪轉法、多級回報隊列列算法、優先級法、短作業優先法、最高響應 |
| 5 | 如何程式設計實作作業排程算法？ | |
| 6 | 模拟程式的輸入如何設計更友善、結果輸出如何呈現更好？ | |
五、 其他要求
1． 完成報告書，内容完整，規格規範。
2． 實驗須檢查，回答實驗相關問題。
注：帶**号的條目表示選做内容。
二、實驗内容
根據指定的實驗課題，完成設計、編碼和調試工作，完成實驗報告。
三、實驗代碼：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define M 24
struct JCB{
char name[M]; //作業名
int arrivetime; //到達時間
float r; //響應比
int cputime; //需要CPU（運作）時間
int finishtime; //完成時的時間
int wt; //周轉時間
float awt; //權重周轉時間
}p[M];
//輸出函數
void Output(int a)
{
int i;
printf("\n作業名 到達系統時間 所需CPU時間 完成時間 周轉時間 權重周轉時間\n");
for(i=0;i<a;i++)
{
printf("%s\t ",p[i].name);
printf(" %d\t\t",p[i].arrivetime);
printf(" %d\t\t",p[i].cputime);
printf("%d\t",p[i].finishtime);
printf("%d\t",p[i].wt);
printf("%f\n",p[i].awt);
}
}
//輸入函數
int Input()
{
int i,a,b=0;
int init,k;
int j=1;
JCB f;
do{
printf("請輸入作業個數（2-20）：");
scanf("%d",&a);
if(a<2||a>20)
j=0;
else break;
}while(j=1);
for(i=0;i<a;i++)
{
printf("請輸入作業名:");
scanf("%s",p[i].name);
printf("請輸入到達時間:");
scanf("%d",&p[i].arrivetime);
printf("請輸入需要CPU（運作）時間:");
scanf("%d",&p[i].cputime);
printf("\n");
p[i].finishtime=0;
p[i].wt=0;
p[i].awt=0;
p[i].r=0;
}
//按到達系統時間先後排序
for(i=0;i<a;i++)
{
init=p[b].arrivetime;
f=p[b];
for(k=b;k<a;k++)
{
if(p[k].arrivetime<init)
{
f=p[k];
p[k]=p[b];
p[b]=f;
init=p[b].arrivetime;
}
}
b++;
}
Output(a);
return a;
}
//SJF算法選擇短作業
int Selecputimework(int t,int n){
int i,l=0;
int temp,m,k=0;
JCB a[M];
JCB b;
//尋找t到達系統還未完成的作業，用數組存儲
for(i=1;i<n;i++)
{
if(p[i].arrivetime<=t&&p[i].finishtime==0)
{
a[l]=p[i];
l++;
k=l;
}
}
//尋找未完成作業中最短的作業
temp=a[0].cputime;
b=a[0];
for(m=0;m<k;m++)
{
if(a[m].cputime<temp)
{
b=a[m];
a[m]=a[0];
a[0]=b;
temp=a[0].cputime;
}
}
return a[0].cputime;//傳回最短作業的所需CPU時間
}
//HRRE算法選擇響應比高的作業
int Choose(int t,int n)
{
int i,k,l=0;
int m=0;
float r,temp;
JCB a[M];
JCB b;
//尋找目前時間t到達系統還未完成的作業，用數組a[M]存儲
for(i=1;i<n;i++)
{
if(p[i].arrivetime<=t&&p[i].finishtime==0)
{
a[l]=p[i];
l++;
k=l;
}
}
//計算每個未完成作業的響應比
for(i=0;i<k;i++)
{
a[i].r=1+(float)(t-a[i].arrivetime)/(float)a[i].cputime;
}
//尋找未完成作業中響應比最高的作業
temp=a[0].r;
b=a[0];
for(m=0;m<k;m++)
{
if(a[m].r>temp)
{
b=a[m];
a[m]=a[0];
a[0]=b;
temp=a[0].r;
}
}
return a[0].cputime;//傳回最高響應比的作業的所需CPU時間
}
//先來先服務
void FCFS()
{
int i,j;
int now=0;//目前時間
j=Input();
int sumwt=0;//周轉時間的和
float sumawt=0;//帶權周轉時間的和
float avwt,avgwt;//avwt是平均周轉時間，avgwt是平均帶權周轉時間
for(i=0;i<j;i++)
{
if(i==0)
{
now=p[i].arrivetime;
p[i].finishtime=now+p[i].cputime;
p[i].wt=p[i].finishtime-p[i].arrivetime;
p[i].awt=p[i].wt/p[i].cputime;
}
else
{
if(p[i-1].finishtime>p[i].arrivetime)
{
now=p[i-1].finishtime;
p[i].finishtime=now+p[i].cputime;
}
else
{
now=p[i].arrivetime;
p[i].finishtime=now+p[i].cputime;
}
p[i].wt=p[i].finishtime-p[i].arrivetime;
p[i].awt=(float)p[i].wt/(float)p[i].cputime;
}
sumwt+=p[i].wt;
sumawt+=p[i].awt;
}
avgwt=(float)sumwt/j;
avwt=sumawt/j;
Output(j);
printf("平均周轉時間為：%f\n",avgwt);
printf("平均帶權周轉時間為：%f\n",avwt);
}
//最短路徑優先
void SJF()
{
int i=0,j=0,k=0;
j=Input();
int l,m,now;//目前時間
int a=0;
int sumwt=0;//周轉時間總和
float sumawt=0;//帶權周轉時間總和
double avwt,avgwt;//avwt是平均周轉時間，avgwt是平均帶權周轉時間
l=0;
int n=0;
for(i=0;i<j;i++)
{
if(i==0)
{
now=p[i].arrivetime;
p[i].finishtime=p[i].arrivetime+p[i].cputime;
now=p[i].finishtime;
}
else
{
a=Selecputimework(now,j);
//尋找最短作業的位置
for(m=0;m<j;m++)
if(p[m].cputime==a&&p[m].finishtime==0)
{
k=m;
break;
}
p[k].finishtime=now+p[k].cputime;//計算時間
now=p[k].finishtime;
}
}
for(i=0;i<j;i++)
{
p[i].wt=p[i].finishtime-p[i].arrivetime;
p[i].awt=(float)p[i].wt/(float)p[i].cputime;
sumwt+=p[i].wt;
sumawt+=p[i].awt;
}
avgwt=(float)sumwt/j;
avwt=sumawt/j;
Output(j);
printf("平均周轉時間為：%f\n",avgwt);
printf("平均帶權周轉時間為：%f\n",avwt);
}
//最高相應比
void HRRN()
{
int i=0,j=0,k=0;
int b=0,now=0,m;
float sumwt=0;//周轉時間總和
float sumawt=0;//帶權周轉時間總和
double avwt,avgwt;//avwt是平均周轉時間，avgwt是平均帶權周轉時間
j=Input();
for(i=0;i<j;i++)
{
if(i==0)
{
p[i].finishtime=p[i].arrivetime+p[i].cputime;
now=p[i].finishtime;
}
else
{
b=Choose(now,j);
//尋找最高響應比的作業的位置
for(m=0;m<j;m++)
if(p[m].cputime==b&&p[m].finishtime==0)
{
k=m;
break;
}
p[k].finishtime=now+p[k].cputime;//計算最高響應比的作業的完成時間
now=p[k].finishtime;
}
}
for(i=0;i<j;i++)
{
p[i].wt=p[i].finishtime-p[i].arrivetime;
p[i].awt=(float)p[i].wt/(float)p[i].cputime;
sumwt+=p[i].wt;
sumawt+=p[i].awt;
}
avgwt=(float)sumwt/j;
avwt=sumawt/j;
Output(j);
printf("平均周轉時間為：%f\n",avgwt);
printf("平均帶權周轉時間為：%f\n",avwt);
}
void Start()
{
int d;
int j=1;
do{ printf(" *******************************************");
printf("\n 1.FCFS先來先服務排程算法。 ");
printf("\n 2.SJF最短路徑優先排程算法。 ");
printf("\n 3.HRRN最高響應比優先排程算法。 ");
printf("\n 請選擇輸入你需要的排程算法的序号：");
printf("\n *******************************************");
scanf("%d",&d);
if(d<1||d>3)
j=0;
else break;
}while(j=1);
switch(d)
{
case 1:
FCFS();
break;
case 2:
SJF();
break;
case 3:
HRRN();
break;
}
}
int main()
{
int i=1;
char a;
do{
Start();
printf("\n你想要繼續嗎?(y or n):");
scanf(" %c",&a);
if(a=='n')
break;
}while(i=1);
printf("The end!\n");
return 0;
} 測試結果
