一、目的和要求
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<string.h>
#define MAX 100
typedef struct
{
char name[10];//程序名
int arrtime;//到達系統時間
int reqtime;//運作時間
int TAtime;//周轉時間
int finitime;//完成時間
int waittime;//等待時間
double XYB;//響應比
double TAWtime;//帶權周轉時間
}pr;
pr a[MAX];
void input(int n)
{
/*int m,i;
printf("輸入作業個數:",m);
scanf("%d",&m);*/
int i;
for(i=0;i<n;i++)
{
printf("第%d個作業\n",i+1);
printf("輸入作業名:");
scanf("%s",&a[i].name);
printf("\n");
printf("到達時間:");
scanf("%d",&a[i].arrtime);
printf("\n");
printf("要求服務時間:");
scanf("%d",&a[i].reqtime);
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].arrtime>a[j+1].arrtime)
{
time1=a[j].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=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].TAtime=a[i].reqtime;
a[i].finitime=a[i].arrtime+a[i].TAtime;
}
else
{
if(a[i].arrtime>a[i-1].finitime)
{
a[i].TAtime=a[i].reqtime;
a[i].finitime=a[i].arrtime+a[i].TAtime;
}
else
{
a[i].TAtime=a[i].reqtime+a[i-1].finitime-a[i].arrtime;
a[i].finitime=a[i].arrtime+a[i].TAtime;
}
}
a[i].TAWtime=a[i].TAtime*1.0/a[i].reqtime;
}
}
//最短作業優先，假設在前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].arrtime>a[j+1].arrtime)
{
time1=a[j].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
a[0].finitime=a[0].arrtime+a[0].reqtime;
for(i=1;i<n;i++)
{
if(a[i].arrtime<a[0].finitime)
b++; //作業到達但第0個作業還在運作時
//用b統計需等待作業0運作的作業個數
}
for(i=1;i<b+1;i++)
{//已經到達的但要等待第0個作業運作完的作業按最短運作時間排序
for(j=1;j<b+1-1;j++)
{
if(a[j].reqtime>a[j+1].reqtime)
{
time1=a[j].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
if(a[1].arrtime>a[0].finitime) a[1].finitime=a[1].arrtime+a[1].reqtime;
else a[1].finitime=a[0].finitime+a[1].reqtime;
for(i=2;i<n;i++)
{
if(a[i].arrtime<a[1].finitime)
c++; //作業到達但第1個作業還在運作時
//用c統計需等待作業1運作的作業個數
}
for(i=2;i<c+2;i++)
{//已經到達的但要等待第1個作業運作完的作業按最短運作時間排序
for(j=2;j<c+2-1;j++)
{
if(a[j].reqtime>a[j+1].reqtime)
{
time1=a[j].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
if(a[2].arrtime>a[1].finitime) a[2].finitime=a[2].arrtime+a[2].reqtime;
else a[2].finitime=a[1].finitime+a[2].reqtime;
for(i=3;i<n;i++)
{
if(a[i].arrtime<a[2].finitime)
d++; //作業到達但第2個作業還在運作時
//用d統計需等待作業2運作的作業個數
}
for(i=3;i<d+3;i++)
{//已經到達的但要等待第2個作業運作完的作業按最短運作時間排序
for(j=3;j<d+3-1;j++)
{
if(a[j].reqtime>a[j+1].reqtime)
{
time1=a[j].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=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].arrtime>a[i-1].finitime)
{
a[i].finitime=a[i].arrtime+a[i].reqtime;
a[i].TAtime=a[i].reqtime;
}
else
{
a[i].finitime=a[i-1].finitime+a[i].reqtime;
a[i].TAtime=a[i].finitime-a[i].arrtime;
}
a[i].TAWtime=a[i].TAtime*1.0/a[i].reqtime;
}
}
//最高響應比優先,隻寫了按到達時間的順序前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].arrtime>a[j+1].arrtime)
{
time1=a[j].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
a[0].finitime=a[0].arrtime+a[0].reqtime;
for(i=1;i<n;i++)
{
a[i].waittime=a[0].finitime-a[i].arrtime;
a[i].XYB=1+(a[i].waittime/a[i].reqtime);
}
//運作完作業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].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
a[1].finitime=a[0].finitime+a[1].reqtime;
for(i=2;i<n;i++)
{
a[i].waittime=a[1].finitime-a[i].arrtime;
a[i].XYB=1+(a[i].waittime/a[i].reqtime);
}
//運作完作業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].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
a[2].finitime=a[1].finitime+a[2].reqtime;
for(i=3;i<n;i++)
{
a[i].waittime=a[2].finitime-a[i].arrtime;
a[i].XYB=1+(a[i].waittime/a[i].reqtime);
}
//運作完作業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].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=time2;
strcpy(temp,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,temp);
}
}
}
a[3].finitime=a[2].finitime+a[3].reqtime;
for(i=4;i<n;i++)
{
a[i].waittime=a[3].finitime-a[i].arrtime;
a[i].XYB=1+(a[i].waittime/a[i].reqtime);
}
//運作完作業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].arrtime;
a[j].arrtime=a[j+1].arrtime;
a[j+1].arrtime=time1;
time2=a[j].reqtime;
a[j].reqtime=a[j+1].reqtime;
a[j+1].reqtime=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].arrtime>a[i-1].finitime)
{
a[i].finitime=a[i].arrtime+a[i].reqtime;
a[i].TAtime=a[i].reqtime;
}
else
{
a[i].finitime=a[i-1].finitime+a[i].reqtime;
a[i].TAtime=a[i].finitime-a[i].arrtime;
}
a[i].TAWtime=a[i].TAtime*1.0/a[i].reqtime;
}
}
void output(int n)
{
int sum_Time=0;//作業總周轉時間
double sum_DQ=0;//作業總帶權周轉時間
int i;
printf("\tname arrtime reqtime TAtime finitime \tTAWtime\n");
for(i=0;i<n;i++)
{
printf("%8s%10d%10d%10d%10d\t%10lf\n",a[i].name,a[i].arrtime,a[i].reqtime,a[i].TAtime,a[i].finitime,a[i].TAWtime);
sum_Time+=a[i].TAtime;
sum_DQ+=a[i].TAWtime;
}
printf("平均作業周轉時間為:%.2lf\n",sum_Time*1.0/n);
printf("平均帶權作業周轉時間為:%.2lf\n",sum_DQ*1.0/n);
printf("\n");
}
int main()
{ /*int d,i,n;
printf("***************************\n");
printf("1、調用文本寫入資料\n");
printf("2、調用僞随機數得産生資料\n");
printf("3、調用自己輸入模拟資料\n");
printf("***************************\n");
scanf("%d",&d);
if(d==3)
*/
int n,i;
printf("輸入作業個數:",n);
scanf("%d",&n);
input(n);
output(n);
while(1)
{
printf("**************************\n ");
printf("1、FCFS算法排程\n");
printf(" 2、SJF算法排程\n");
printf(" 3、HRRF算法排程\n");
printf(" 4、退出算法排程\n");
printf("***************************\n ");
printf("請選擇菜單項: ");
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)
{
printf("謝謝使用\n");
exit(0);
}
}
}
程式截圖：
