一、目的和要求
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． 實驗須檢查，回答實驗相關問題。
注：帶**号的條目表示選做内容。
二、實驗内容
根據指定的實驗課題，完成設計、編碼和調試工作，完成實驗報告。
三、實驗環境
可以采用TC，也可以選用Windows下的利用各種控件較為友善的VB，VC等可視化環境。也可以自主選擇其他實驗環境。
四、實驗原理及核心算法參考程式段
單道FCFS算法：
1 #include<stdio.h>
2 #include<string.h>
3 void shuru();
4 void readfiles();
5 void ran();
6 typedef struct jcb
7 {
8 char name[10];
9 char status; //狀态：開始s，等待d，就緒j
10 int id;
11 int arrtime; //到達時間
12 int reqtime; //要求服務時間
13 int startime; //開始時間
14 int finitime; //完成時間
15
16 float TAtime,TAWtime; //周轉時間、帶權周轉時間
17 float prio; //優先級
18 float HRRF; //響應比
19
20 }jcb;
21
22
23
24 jcb jcbs[100]; //最多100個作業
25 int systime=0,bfsum,add,del;
26 int intarr,infin,intjob,sumjcb;
27 char T='A'; //T的預設值是A
28
29 void sort(int choose) //排序
30 {
31 int i,j;
32 jcb temp;
33 for(i=1;i<=sumjcb;i++)
34 {
35 for(j=i+1;j<=sumjcb;j++)
36 {
37 if(choose==1)
38 {
39 if(jcbs[i].arrtime>jcbs[j].arrtime)
40 {
41 strcpy(temp.name,jcbs[i].name);
42 temp.status=jcbs[i].status;
43 temp.arrtime=jcbs[i].arrtime;
44 temp.reqtime=jcbs[i].reqtime;
45 temp.startime=jcbs[i].startime;
46 temp.finitime=jcbs[i].finitime;
47 temp.TAtime=jcbs[i].TAtime;
48 temp.TAWtime=jcbs[i].TAWtime;
49 temp.prio=jcbs[i].prio;
50 temp.id=jcbs[i].id;
51 temp.HRRF=jcbs[i].HRRF;
52
53 strcpy(jcbs[i].name,jcbs[j].name);
54 jcbs[i].status=jcbs[j].status;
55 jcbs[i].arrtime=jcbs[j].arrtime;
56 jcbs[i].reqtime=jcbs[j].reqtime;
57 jcbs[i].startime=jcbs[j].startime;
58 jcbs[i].finitime=jcbs[j].finitime;
59 jcbs[i].TAtime=jcbs[j].TAtime;
60 jcbs[i].TAWtime=jcbs[j].TAWtime;
61 jcbs[i].prio=jcbs[j].prio;
62 jcbs[i].id=jcbs[j].id;
63 jcbs[i].HRRF=jcbs[j].HRRF;
64
65 strcpy(jcbs[j].name,temp.name);
66 jcbs[j].status=temp.status;
67 jcbs[j].arrtime=temp.arrtime;
68 jcbs[j].reqtime=temp.reqtime;
69 jcbs[j].startime=temp.startime;
70 jcbs[j].finitime=temp.finitime;
71 jcbs[j].TAtime=temp.TAtime;
72 jcbs[j].TAWtime=temp.TAWtime;
73 jcbs[j].prio=temp.prio;
74 jcbs[j].id=temp.id;
75 jcbs[j].HRRF=temp.HRRF;
76 }
77 }
78 else if(choose==2)
79 {
80 if(jcbs[i].reqtime>jcbs[j].reqtime)
81 {
82 strcpy(temp.name,jcbs[i].name);
83 temp.status=jcbs[i].status;
84 temp.arrtime=jcbs[i].arrtime;
85 temp.reqtime=jcbs[i].reqtime;
86 temp.startime=jcbs[i].startime;
87 temp.finitime=jcbs[i].finitime;
88 temp.TAtime=jcbs[i].TAtime;
89 temp.TAWtime=jcbs[i].TAWtime;
90 temp.prio=jcbs[i].prio;
91 temp.id=jcbs[i].id;
92 temp.HRRF=jcbs[i].HRRF;
93
94 strcpy(jcbs[i].name,jcbs[j].name);
95 jcbs[i].status=jcbs[j].status;
96 jcbs[i].arrtime=jcbs[j].arrtime;
97 jcbs[i].reqtime=jcbs[j].reqtime;
98 jcbs[i].startime=jcbs[j].startime;
99 jcbs[i].finitime=jcbs[j].finitime;
100 jcbs[i].TAtime=jcbs[j].TAtime;
101 jcbs[i].TAWtime=jcbs[j].TAWtime;
102 jcbs[i].prio=jcbs[j].prio;
103 jcbs[i].id=jcbs[j].id;
104 jcbs[i].HRRF=jcbs[j].HRRF;
105
106 strcpy(jcbs[j].name,temp.name);
107 jcbs[j].status=temp.status;
108 jcbs[j].arrtime=temp.arrtime;
109 jcbs[j].reqtime=temp.reqtime;
110 jcbs[j].startime=temp.startime;
111 jcbs[j].finitime=temp.finitime;
112 jcbs[j].TAtime=temp.TAtime;
113 jcbs[j].TAWtime=temp.TAWtime;
114 jcbs[j].prio=temp.prio;
115 jcbs[j].id=temp.id;
116 jcbs[j].HRRF=temp.HRRF;
117 }
118 }
119 else if(choose==3)
120 {
121 if(jcbs[i].HRRF<jcbs[j].HRRF)
122 {
123 strcpy(temp.name,jcbs[i].name);
124 temp.status=jcbs[i].status;
125 temp.arrtime=jcbs[i].arrtime;
126 temp.reqtime=jcbs[i].reqtime;
127 temp.startime=jcbs[i].startime;
128 temp.finitime=jcbs[i].finitime;
129 temp.TAtime=jcbs[i].TAtime;
130 temp.TAWtime=jcbs[i].TAWtime;
131 temp.prio=jcbs[i].prio;
132 temp.id=jcbs[i].id;
133 temp.HRRF=jcbs[i].HRRF;
134
135 strcpy(jcbs[i].name,jcbs[j].name);
136 jcbs[i].status=jcbs[j].status;
137 jcbs[i].arrtime=jcbs[j].arrtime;
138 jcbs[i].reqtime=jcbs[j].reqtime;
139 jcbs[i].startime=jcbs[j].startime;
140 jcbs[i].finitime=jcbs[j].finitime;
141 jcbs[i].TAtime=jcbs[j].TAtime;
142 jcbs[i].TAWtime=jcbs[j].TAWtime;
143 jcbs[i].prio=jcbs[j].prio;
144 jcbs[i].id=jcbs[j].id;
145 jcbs[i].HRRF=jcbs[j].HRRF;
146
147 strcpy(jcbs[j].name,temp.name);
148 jcbs[j].status=temp.status;
149 jcbs[j].arrtime=temp.arrtime;
150 jcbs[j].reqtime=temp.reqtime;
151 jcbs[j].startime=temp.startime;
152 jcbs[j].finitime=temp.finitime;
153 jcbs[j].TAtime=temp.TAtime;
154 jcbs[j].TAWtime=temp.TAWtime;
155 jcbs[j].prio=temp.prio;
156 jcbs[j].id=temp.id;
157 jcbs[j].HRRF=temp.HRRF;
158 }
159 }
160 else
161 printf("Error!\n");
162 }
163 }
164 }
165 void ins() //插入
166 {
167 int i;
168 while(T!='E'&&T!='e')
169 {
170 printf("'I'nsert or 'D'elete or 'E'xit?\n");
171 getchar();
172 scanf("%c",&T);
173 if(T=='I'||T=='i')
174 {
175 printf("你想插入多少個作業?\n");
176 scanf("%d",&add);
177 bfsum=sumjcb;
178 sumjcb=sumjcb+add;
179 for(i=bfsum+1;i<=sumjcb;i++)
180 {
181 printf("\n第%d個作業:\n",i);
182 getchar();
183 printf("輸入作業名:\n");
184 gets(jcbs[i].name);
185 printf("到達時間:\n");
186 scanf("%d",&jcbs[i].arrtime);
187 printf("要求服務時間:\n");
188 scanf("%d",&jcbs[i].reqtime);
189 }
190 }
191 else if(T=='D'||T=='d')
192 {
193 printf("你想删除第幾組?");
194 scanf("%d",&del);
195 for(i=del;i<=sumjcb-1;i++)
196 {
197 strcpy(jcbs[i].name,jcbs[i+1].name);
198 jcbs[i].arrtime=jcbs[i+1].arrtime;
199 jcbs[i].reqtime=jcbs[i+1].reqtime;
200 }
201 sumjcb--;
202 }
203 }
204 }
205
206
207 void printarr() //列印
208 {
209 int i;
210 printf("\t\tname\tartime\trqtime\n");
211 for(i=1;i<=sumjcb;i++)
212 {
213 printf("N %d\t",i);
214 printf("\t%s",jcbs[i].name);
215 printf("\t%d",jcbs[i].arrtime);
216 printf("\t%d\n",jcbs[i].reqtime);
217 }
218 printf("\t\t\t\t\t\t現在系統時間%d\n",systime);
219
220 }
221 void printz()
222 {
223 int i;
224 float sum1=0,sum2=0; //計算平均周轉時間、平均帶權周轉時間
225 printf("\t\tname\tartime\trqtime\tstime\tftime\tTAtime\t\tTAWtime\n");
226 for(i=1;i<=sumjcb;i++)
227 {
228 printf("N %d\t",i);
229 printf("\t%s",jcbs[i].name);
230 printf("\t%d",jcbs[i].arrtime);
231 printf("\t%d",jcbs[i].reqtime);
232 printf("\t%d",jcbs[i].startime);
233 printf("\t%d",jcbs[i].finitime);
234 printf("\t%f",jcbs[i].TAtime);
235 printf("\t%f\n",jcbs[i].TAWtime);
236 }
237 for(i=1;i<=sumjcb;i++)
238 {
239 sum1=sum1+jcbs[i].TAtime;
240 }
241 for(i=1;i<=sumjcb;i++)
242 {
243 sum2=sum2+jcbs[i].TAWtime;
244 }
245 printf("\n平均周轉時間=%f\n",sum1/sumjcb);
246 printf("\n平均帶權周轉時間=%f\n",sum2/sumjcb);
247 printf("\t\t\t\t\t\t現在系統時間%d\n",systime);
248 }
249 void sumofthey()
250 {
251 int i;
252 jcbs[1].startime=jcbs[1].arrtime;
253 jcbs[1].finitime=jcbs[1].arrtime+jcbs[1].reqtime;
254 jcbs[1].TAtime=(float)(jcbs[1].finitime-jcbs[1].arrtime);
255 jcbs[1].TAWtime=(float)(jcbs[1].TAtime/jcbs[1].reqtime);
256 jcbs[1].HRRF=(float)(jcbs[1].TAtime/jcbs[1].reqtime);
257 for(i=2;i<=sumjcb;i++)
258 {
259 jcbs[i].startime=jcbs[i-1].finitime;
260 jcbs[i].finitime=jcbs[i].startime+jcbs[i].reqtime;
261 jcbs[i].TAtime=(float)(jcbs[i].finitime-jcbs[i].arrtime);
262 jcbs[i].TAWtime=(float)(jcbs[i].TAtime/jcbs[i].reqtime);
263 jcbs[i].HRRF=(float)(jcbs[i].TAtime/jcbs[i].reqtime);
264 }
265 }
266 void startit()
267 {
268 int n;
269 printf("\n");
270 printf("\t\t\t**************************\n");
271 printf("\t\t\t**1.調用文本寫入資料******\n");
272 printf("\t\t\t**2.調用僞随機數産生資料**\n");
273 printf("\t\t\t**3.調用自己輸入模拟資料**\n");
274 printf("\t\t\t**************************\n");
275 scanf("%d",&n);
276 switch(n)
277 {
278 case 1:
279 readfiles();
280 sumofthey();
281 break;
282 case 2:
283 ran();
284 sumofthey();
285 break;
286 case 3:
287 shuru();
288 sumofthey();
289 break;
290 default:
291 {
292 printf("輸入有誤，請重新輸入");
293 break;
294 }
295 }
296 }
297 void ran()
298 {
299 int i;
300 srand((unsigned)time(0)); //參數seed是rand()的種子，用來初始化rand()的起始值。
301 sumjcb=rand()%23+5;
302 for(i=1;i<=sumjcb;i++)
303 {
304 itoa(i,jcbs[i].name, 2);
305
306 jcbs[i].arrtime=rand()%29+1;
307
308 jcbs[i].reqtime=rand()%7+1;
309 }
310 printf("\n \tid \t作業到達時間 \t作業運作所需要時間\n");
311 for(i=1; i<=sumjcb; i++)
312 {
313 printf("\n\t%s\t%12d\t%15d",jcbs[i].name,jcbs[i].arrtime,jcbs[i].reqtime);
314 }
315 printf("\n");
316 }
317
318 void readfiles()
319 {
320 char szTest[1000] = {0};int i=0,n;
321 FILE *fp=fopen("D:\\File1.txt","r");
322 //FILE *fout=fopen("D:\\File2.txt","w");
323 if(fp == NULL)
324 {
325 printf("ERROR!\n");
326 exit(0);
327 }
328 //fscanf(fp,"jcbsum=%d\n",%n);
329 while(!feof(fp))
330 {
331 fscanf(fp,"%d%d%d",&jcbs[i].id,&jcbs[i].arrtime,&jcbs[i].reqtime); //fscanf()函數将資料讀入
332 printf("\n%3d%12d%15d\n",jcbs[i].id,jcbs[i].arrtime,jcbs[i].reqtime); //輸出到螢幕
333 itoa(jcbs[i].id,jcbs[i].name,10);
334 i++;
335 /*memset(szTest, 0, sizeof(szTest));
336 fscanf(fp,"@id=%d|",&i);
337 fgets(fp,"name=%s|",jcbs[i].name);
338 fscanf(fp,"arrtime=%d|reqtime=%d\n",&jcbs[i].arrtime,&jcbs[i].reqtime);
339 */
340 //fscanf(fp,"%d",)
341 }
342 sumjcb=i;
343 fclose(fp);
344 }
345 void shuru()
346 {
347 int i;
348 printf("作業個數:\n");
349 scanf("%d",&sumjcb);
350 for(i=1;i<=sumjcb;i++)
351 {
352 printf("\n第%d個作業:\n",i);
353 getchar();
354 printf("輸入作業名:\n");
355 gets(jcbs[i].name);
356 printf("到達時間:\n");
357 scanf("%d",&jcbs[i].arrtime);
358 printf("要求服務時間:\n");
359 scanf("%d",&jcbs[i].reqtime);
360 }
361 sumofthey();
362 }
363 void choosesort()
364 {
365 int n;
366 printf("\t\t\t*****************************\n");
367 printf("\t\t\t*******1.FCFS算法排程********\n");
368 printf("\t\t\t*******2.SJF算法排程*********\n");
369 printf("\t\t\t*******3.HRRF算法排程********\n");
370 printf("\t\t\t*******4.調用系統清屏********\n");
371 printf("\t\t\t*******5.退出算法排程********\n");
372 printf("\t\t\t*****************************\n");
373 scanf("%d",&n);
374 switch(n)
375 {
376 case 1:
377 printf("運作先來先服務算法FCFS\n");
378 sort(1);
379 printf("\n經按到達時間排序後，未達到隊列是\n");
380 printz();
381 break;
382 case 2:
383 printf("運作最短作業優先算法FJS\n");
384 sort(2);
385 printf("\n經按到達時間排序後，未達到隊列是\n");
386 printz();
387 break;
388 case 3:
389 printf("運作最高響應比優先算法HRRF\n");
390 sort(3);
391 printf("\n經按到達時間排序後，未達到隊列是\n");
392 printz();
393 break;
394 case 4:
395 system("cls");
396 break;
397 case 5:
398 exit(0);
399 break;
400 }
401 }
402 void main()
403 {
404 startit();
405 choosesort();
406
407
408 }