一、目的和要求
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 | |
| 4 | 作業系統中，常用的作業排程算法有哪些？ | |
| 5 | 如何程式設計實作作業排程算法？ | |
| 6 | 模拟程式的輸入如何設計更友善、結果輸出如何呈現更好？ |
五、 其他要求
1． 完成報告書，内容完整，規格規範。
2． 實驗須檢查，回答實驗相關問題。
注：帶**号的條目表示選做内容。
二、實驗内容
根據指定的實驗課題，完成設計、編碼和調試工作，完成實驗報告。
三、實驗環境
可以采用TC，也可以選用Windows下的利用各種控件較為友善的VB，VC等可視化環境。也可以自主選擇其他實驗環境。
四、實驗原理及核心算法參考程式段
單道FCFS算法：
源代碼：
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<time.h>
4 struct jcb{
5 int id;
6 char status;
7
8 int arrtime;
9 int reqtime;
10 int startime;
11 int finitime;
12
13 float TAtime,TAWtime;
14 float prio;
15 } jobarr[24],jobfin[24],job[24];
16 int systime=0;
17
18
19 //主菜單
20 void menu()
21 {
22 printf("\t\t\t***************************************\n");
23 printf("\t\t\t| 作業排程 |\n");
24 printf("\t\t\t|-------------------------------------|\n");
25 printf("\t\t\t| 1.調用文本寫入資料 |\n");
26 printf("\t\t\t|-------------------------------------|\n");
27 printf("\t\t\t| 2.調用僞随機數的産生資料 |\n");
28 printf("\t\t\t|-------------------------------------|\n");
29 printf("\t\t\t| 3.自主輸入模拟資料 |\n");
30 printf("\t\t\t|**************************************\n");
31 }
32
33
34 //排程算法菜單
35 void menu0()
36 {
37 printf("\n");
38 printf("\n***************************************\n");
39 printf(" 1.FCFS算法排程\n");
40 printf(" 2.SJF算法排程\n");
41 printf(" 3.HRRF算法排程\n");
42 printf(" 4.調用系統清屏\n");
43 printf(" 0.退出算法排程\n");
44 printf("***************************************\n");
45 }
46
47
48 //短作業優先排序
49 void sort(int n)
50 {
51 int i,j;
52 struct jcb temp;
53 for(i=2;i<n;i++)
54 for(j=i+1;j<=n;j++)
55 if(jobarr[i].reqtime>jobarr[j].reqtime) //根據最短的要求服務時間排序
56 {
57 temp=jobarr[i];
58 jobarr[i]=jobarr[j];
59 jobarr[j]=temp;
60 }
61 }
62
63
64 //先到先服務排序
65 void sort0(int n)
66 {
67 int i,j;
68 struct jcb temp;
69 for(i=2;i<n;i++)
70 for(j=i+1;j<=n;j++)
71 if(job[i].arrtime>job[j].arrtime) //根據到達時間排序
72 {
73 temp=job[i];
74 job[i]=job[j];
75 job[j]=temp;
76 }
77 }
78
79
80 //自主輸入模拟資料
81 void shoushu()
82 {
83 int n;
84 printf("作業個數:");
85 scanf("%d",&n);
86 for(int i=1;i<=n;i++)
87 {
88 printf("\n第%d個作業:",i);
89 printf("\n請輸入作業名:");
90 scanf("%d",&job[i].id);
91 printf("到達時間:");
92 scanf("%d",&job[i].arrtime);
93 printf("要求服務時間:");
94 scanf("%d",&job[i].reqtime);
95 jobarr[i]=job[i];
96 }
97 }
98
99
100 //文本寫入資料
101 int ReadFile()
102 {
103 int m=0;
104 int i=1;
105 FILE *fp; //定義檔案指針
106 fp=fopen("作業排程.txt","r"); //打開檔案
107 if(fp==NULL)
108 {
109 printf("File open error !\n");
110 exit(0);
111 }
112 printf("\n 作業名 作業到達時間 作業運作所需要時間\n");
113 while(!feof(fp))
114 {
115 fscanf(fp,"%d%d%d",&job[i].id,&job[i].arrtime,&job[i].reqtime); //fscanf()函數将資料讀入
116 printf("\n%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime); //輸出到螢幕
117 i++;
118 };
119
120 if(fclose(fp)) //關閉檔案
121 {
122 printf("Can not close the file !\n");
123 exit(0);
124 }
125 m=i-1;
126 return m;
127
128 }
129
130
131 //僞随機數的産生資料
132 int Pseudo_random_number()
133 {
134 int i,n;
135 srand((unsigned)time(0)); //參數seed是rand()的種子，用來初始化rand()的起始值。
136 //輸入作業數
137 n=rand()%23+5;
138 for(i=1; i<=n; i++)
139 {
140 job[i].id=i;
141 //作業到達時間
142 job[i].arrtime=rand()%29+1;
143 //作業運作時間
144 job[i].reqtime=rand()%7+1;
145 }
146 printf("\n 作業名 作業到達時間 作業運作所需要時間\n");
147 for(i=1; i<=n; i++)
148 {
149 printf("\n%3d%12d%15d",job[i].id,job[i].arrtime,job[i].reqtime);
150 }
151 return n;
152
153 }
154
155
156 //先來先服務算法FCFS
157 void FCFS()
158 {
159 int i=1,j=1;
160 float sumTA=0,sumTAW=0;
161 printf("-----------先來先服務算法FCFS-------------\n");
162 printf("\n 作業名 作業到達時間 作業運作所需要時間\n");
163 while(job[j].id!=NULL)
164 {
165 printf("\n%3d%12d%15d",job[j].id,job[j].arrtime,job[j].reqtime); //輸出到螢幕
166 j++;
167 }
168 sort0(j-1);
169 printf("\n\n作業名 作業到達時間 作業完成時間 運作時間 作業周轉時間 帶權作業周轉時間\n");
170 while(job[i].id!=NULL)
171 {
172 if(i==1) //第一個作業先到達，先被排程
173 {
174 job[i].startime=job[i].arrtime;
175 }
176 else //其他作業被排程
177 {
178 if(job[i-1].finitime>=job[i].arrtime) //如果上一個作業的完成時間大于下一個到達時間，則下一個開始時間為上一個作業的完成時間
179 job[i].startime=job[i-1].finitime;
180 else
181 job[i].startime=job[i].arrtime; //否則下一個開始時間即它的到達時間
182 }
183 job[i].finitime=job[i].startime+job[i].reqtime; //計算完成時間
184 job[i].TAtime=job[i].finitime-job[i].arrtime; //計算周轉時間
185 job[i].TAWtime=job[i].TAtime/job[i].reqtime; //計算帶權周轉時間
186 sumTA+=job[i].TAtime;
187 sumTAW+=job[i].TAWtime;
188 printf("\n%3d%12d%13d%14d%12.0lf%14.2lf",job[i].id,job[i].arrtime,job[i].finitime,job[i].reqtime,job[i].TAtime,job[i].TAWtime);
189 i++;
190 }
191 printf("\n平均作業周轉時間= %.2lf",sumTA/(i-1));
192 printf("\n平均帶權作業周轉時間= %.2lf",sumTAW/(i-1));
193 }
194
195
196 //最短作業優先算法SJF
197 void SJF()
198 {
199 int i=1,j=1;
200 float sumTA=0,sumTAW=0;
201 printf("-----------最短作業優先算法SJF-------------\n");
202 printf("\n作業名 作業到達時間 作業運作所需要時間\n");
203 while(job[j].id!=NULL)
204 {
205 printf("\n%3d%12d%15d",job[j].id,job[j].arrtime,job[j].reqtime); //輸出到螢幕
206 jobarr[j]=job[j];
207 j++;
208 }
209 sort(j-1);
210 printf("\n\n作業名 作業到達時間 作業完成時間 運作時間 作業周轉時間 帶權作業周轉時間\n");
211 while(jobarr[i].id!=NULL)
212 {
213 if(i==1)
214 {
215 jobarr[i].startime=jobarr[i].arrtime;
216 }
217 else
218 {
219 if(jobarr[i-1].finitime>=jobarr[i].arrtime)
220 jobarr[i].startime=jobarr[i-1].finitime;
221 else
222 jobarr[i].startime=jobarr[i].arrtime;
223 }
224 jobarr[i].finitime=jobarr[i].startime+jobarr[i].reqtime;
225 jobarr[i].TAtime=jobarr[i].finitime-jobarr[i].arrtime;
226 jobarr[i].TAWtime=jobarr[i].TAtime/jobarr[i].reqtime;
227 sumTA+=jobarr[i].TAtime;
228 sumTAW+=jobarr[i].TAWtime;
229 printf("\n%3d%12d%13d%14d%12.0lf%14.2lf",jobarr[i].id,jobarr[i].arrtime,jobarr[i].finitime,jobarr[i].reqtime,jobarr[i].TAtime,jobarr[i].TAWtime);
230 i++;
231 }
232 printf("\n平均作業周轉時間= %.2lf",sumTA/(i-1));
233 printf("\n平均帶權作業周轉時間= %.2lf",sumTAW/(i-1));
234 }
235
236
237 //最高響應比排序
238 void sort1(int n,int k)
239 {
240 int i,j;
241 struct jcb temp;
242 for(i=k;i<n;i++)
243 for(j=i+1;j<=n;j++)
244 if(jobfin[i].prio<jobfin[j].prio)
245 {
246 temp=jobfin[i];
247 jobfin[i]=jobfin[j];
248 jobfin[j]=temp;
249 }
250 }
251
252
253 //響應比最高者優先HRRF算法
254 void HRRF()
255 {
256 int i=1,j=1,k=1;
257 float sumTA=0,sumTAW=0;
258 printf("-----------響應比最高者優先HRRF算法-------------\n");
259 printf("\n作業名 作業到達時間 作業運作所需要時間\n");
260 while(job[j].id!=NULL)
261 {
262 printf("%3d%12d%15d\n",job[j].id,job[j].arrtime,job[j].reqtime); //輸出到螢幕
263 jobfin[j]=job[j];
264 j++;
265 }
266 while(jobfin[k].id!=NULL)
267 {
268 i=k;
269 if(k==1)
270 {
271 jobfin[i].startime=jobfin[i].arrtime;
272 jobfin[i].finitime=jobfin[i].startime+jobfin[i].reqtime;
273 jobfin[i].TAtime=jobfin[i].finitime-jobfin[i].arrtime;
274 jobfin[i].TAWtime=jobfin[i].TAtime/jobfin[i].reqtime;
275 }
276 else
277 {
278 printf("\n作業名 最高響應比\n");
279 while(jobfin[i].id!=NULL)
280 {
281 if(jobfin[k-1].finitime>=job[i].arrtime)
282 {
283 jobfin[i].startime=jobfin[k-1].finitime;
284 jobfin[i].prio=(jobfin[i].startime-jobfin[i].arrtime)/(jobfin[i].reqtime/1.0)+1;
285 }
286 else
287 {
288 jobfin[i].startime=0;
289 jobfin[i].prio=0;
290 }
291 i++;
292 }
293 sort1(j-1,k);
294 for(i=k;i<j;i++)
295 printf("%3d%10.2lf\n",jobfin[i].id,jobfin[i].prio);
296 jobfin[k].finitime=jobfin[k-1].finitime+jobfin[k].reqtime;
297 jobfin[k].TAtime=jobfin[k].finitime-jobfin[k].arrtime;
298 jobfin[k].TAWtime=jobfin[k].TAtime/jobfin[k].reqtime;
299 }
300 k++;
301 }
302 printf("\n\n作業名 作業到達時間 作業完成時間 運作時間 作業周轉時間 帶權作業周轉時間\n");
303 for(i=1;i<j;i++)
304 {
305 printf("\n%3d%12d%13d%14d%12.0lf%14.2lf",jobfin[i].id,jobfin[i].arrtime,jobfin[i].finitime,jobfin[i].reqtime,jobfin[i].TAtime,jobfin[i].TAWtime);
306 sumTA+=jobfin[i].TAtime;
307 sumTAW+=jobfin[i].TAWtime;
308 }
309 printf("\n平均作業周轉時間= %.2lf",sumTA/(i-1));
310 printf("\n平均帶權作業周轉時間= %.2lf",sumTAW/(i-1));
311 }
312
313
314 void main0()
315 {
316 int tmp;
317 while(1)
318 {
319 menu0();
320 printf("\n請選擇菜單項:");
321 scanf("%d",&tmp);
322 switch (tmp)
323 {
324 case 1:
325 FCFS();
326 break;
327 case 2:
328 SJF();
329 break;
330 case 3:
331 HRRF();
332 break;
333 case 4:
334 system("cls");
335 break;
336 case 0:
337 return;
338 }
339 }
340 }
341
342
343 main()
344 {
345 int tmp;
346 while(1)
347 {
348 menu();
349 printf("\n請選擇菜單項:");
350 scanf("%d",&tmp);
351 switch (tmp)
352 {
353 case 1:
354 ReadFile();
355 break;
356 case 2:
357 Pseudo_random_number();
358 break;
359 case 3:
360 shoushu();
361 break;
362 }
363 main0();
364 printf("\n");
365 }
366 } 實驗結果：
FCFS：
SJF:
HRRF:
實驗總結：
剛開始做這個實驗時我覺得很難，有點不知所措，但是通過老師的一些講解和提供的思路，自己也上網百度了一些不懂的東西，最後成功完成了這個作業排程的一些基本要求，是以我覺得，付出多少，必然有所收獲。
學号：201406114214
姓名：馮梓凡