實驗三 程序排程模拟程式
1. 目的和要求
1.1. 實驗目的
用進階語言完成一個程序排程程式，以加深對程序的概念及程序排程算法的了解。
1.2. 實驗要求
1.2.1例題：設計一個有 N個程序并發執行的程序排程模拟程式。
程序排程算法：采用最高優先級優先的排程算法（即把處理機配置設定給優先級最高的程序）和先來先服務（若優先級相同）算法。
(1). 每個程序有一個程序控制塊（PCB）表示。程序控制塊包含如下資訊：程序名、優先級、到達時間、需要運作時間、已用CPU時間、程序狀态等等。
(2). 程序的優先級及需要的運作時間可以事先人為地指定，程序的運作時間以時間片為機關進行計算。
(3). 每個程序的狀态可以是就緒 r（ready）、運作R（Running）、或完成F（Finished）三種狀态之一。
(4). 就緒程序獲得 CPU後都隻能運作一個時間片。用已占用CPU時間加1來表示。
(5). 如果運作一個時間片後，程序的已占用 CPU時間已達到所需要的運作時間，則撤消該程序，如果運作一個時間片後程序的已占用CPU時間還未達所需要的運作時間，也就是程序還需要繼續運作，此時應将程序的優先數減1（即降低一級），然後把它插入就緒隊列等待排程。
(6). 每進行一次排程程式都列印一次運作程序、就緒隊列中各個程序的 PCB，以便進行檢查。
(7). 重複以上過程，直到所要程序都完成為止。
思考：作業排程與程序排程的不同？
1.2.2實驗題A：編寫并調試一個模拟的程序排程程式，采用“最高優先數優先”排程算法對N（N不小于5）個程序進行排程。
“最高優先級優先”排程算法的基本思想是把CPU配置設定給就緒隊列中優先數最高的程序。
(1). 靜态優先數是在建立程序時确定的，并在整個程序運作期間不再改變。
(2). 動态優先數是指程序的優先數在建立程序時可以給定一個初始值，并且可以按一定規則修改優先數。例如：在程序獲得一次CPU後就将其優先數減少1，并且程序等待的時間超過某一時限（2個時間片時間）時增加其優先數等。
(3). （**）程序的優先數及需要的運作時間可以事先人為地指定，（也可以由随機數産生）。
(4). （**）在進行模拟排程過程可以建立（增加）程序，其到達時間為程序輸入的時間。
0．
1.2.3實驗題B：編寫并調試一個模拟的程序排程程式，采用“基于時間片輪轉法”排程算法對N（N不小于5）個程序進行排程。 “輪轉法”有簡單輪轉法、多級回報隊列排程算法。
(1). 簡單輪轉法的基本思想是：所有就緒程序按 FCFS排成一個隊列，總是把處理機配置設定給隊首的程序，各程序占用CPU的時間片長度相同。如果運作程序用完它的時間片後還未完成，就把它送回到就緒隊列的末尾，把處理機重新配置設定給隊首的程序。直至所有的程序運作完畢。（此排程算法是否有優先級？）
(2). 多級回報隊列排程算法的基本思想是：
将就緒隊列分為N級（N＝3～5），每個就緒隊列優先數不同并且配置設定給不同的時間片：隊列級别越高，優先數越低，時間片越長；級别越小，優先數越高，時間片越短。
系統從第一級排程，當第一級為空時，系統轉向第二級隊列，.....當處于運作态的程序用完一個時間片，若未完成則放棄CPU，進入下一級隊列。
當程序第一次就緒時，進入第一級隊列。
(3). （**）考慮程序的阻塞狀态B（Blocked）增加阻塞隊列。程序的是否阻塞和阻塞的時間由産生的“随機數”确定（阻塞的頻率和時間長度要較為合理）。注意程序隻有處于運作狀态才可能轉換成阻塞狀态，程序隻有處于就緒狀态才可以轉換成運作狀态。
2. 實驗内容
根據指定的實驗課題：A（1），A（2），B（1）和B（2）
完成設計、編碼和調試工作，完成實驗報告。
注：帶**号的條目表示選做内容。
3. 實驗環境
可以選用Turbo C作為開發環境。也可以選用Windows下的VB，CB等可視化環境，利用各種控件較為友善。自主選擇實驗環境。
4. 實驗原理及核心算法參考程式段
1 #include "stdio.h"
2 #include <stdlib.h>
3 #include <conio.h>
4 #define N 3
5 int k=1;
6 struct pcb{
7 int id;
8 char status;
9 int needtime;
10 int runtime;
11 float TAtime,TAWtime;
12 int prio;
13 }job[24];
14 int n;
15 void sort0()
16 {
17 int i,j;
18 struct pcb temp;
19 for(i=2;i<n;i++)
20 for(j=i+1;j<=n;j++)
21 if(job[i].prio>job[j].prio) //根據到達優先級排序
22 {
23 temp=job[i];
24 job[i]=job[j];
25 job[j]=temp;
26 }
27 }
28
29 void input()
30 {
31
32 printf("程序個數:");
33 scanf("%d",&n);
34 for(int i=1;i<=n;i++)
35 {
36 printf("\n第%d個程序:",i);
37 printf("\n輸入id:");
38 scanf("%d",&job[i].id);
39 printf("輸入程序運作時間:");
40 scanf("%d",&job[i].needtime);
41 job[i].prio=N;
42 job[i].status='W';
43 job[i].runtime=0;
44 sort0();
45 }
46 }
47 void disp()
48 {
49 printf("|%d\t",job[k].id);
50 printf("|%c\t",job[k].status);
51 printf("|%d\t",job[k].prio);
52 printf("|%d\t",job[k].needtime);
53 printf("|%d\t",job[k].runtime);
54 printf("\n");
55 }
56 void printbyprio(int prio)
57 {
58 printf("\n ****目前第%d級隊列(優先數為%d)的就緒程序有:\n",(N+1)-prio,prio); /*顯示就緒隊列狀态*/
59 printf("\n id \tstatus\t prio \tneeddtime\t runtime \n");
60 while(job[k+1].id!=NULL)
61 {
62 if(job[k+1].prio==prio) disp();
63 k++;
64 }
65 }
66 void check() /* 顯示所有程序狀态函數 */
67 {
68
69 int i=1;
70 job[k].status='R';
71 printf("\n /\\/\\/\\/\\目前正在運作的程序的id是:%d",job[k].id); /*顯示目前運作程序*/
72 printf("\n id \tstatus\t prio \tneedtime\t runtime \n");
73 disp();
74
75 printf("\n 目前就緒隊列狀态為:\n"); /*顯示就緒隊列狀态*/
76 for(i=N;i>=1;i--)
77 printbyprio(i);
78 }
79
80 void destroy() /*程序撤消函數(程序運作結束,撤消程序)*/
81 {
82 int i=k;
83 printf("\n 程序 [%s] 已完成.\n",job[k].id);
84 while(job[i+1].id!=NULL)
85 {
86 job[i]=job[i+1];
87 k++;
88 }
89 job[i-1]=job[i];
90 }
91 void running()
92 {
93 int slice,i;
94 slice=1;
95 for(i=1;i<((N+1)-job[k].prio);i++)
96 slice=slice*2;
97 for(i=1;i<=slice;i++)
98 {
99 job[k].runtime++;
100 if (job[k].runtime==job[k].needtime)
101 break;
102 }
103 if (job[k].runtime==job[k].needtime)
104 {
105 destroy();
106 n--;
107 }
108 else
109 {
110 if(job[k].prio>1) (job[k].prio)--;
111 job[k].status='r';
112 sort0(); /*調用sort函數*/
113 }
114
115 }
116 main()
117 {
118 int temp=0;
119 char ch;
120 input();
121 while(1)
122 {
123 ch=getchar();
124 temp++;
125 printf("\n The execute number:%d \n",temp);
126 check();
127 running();
128 printf("\n 按任一鍵繼續......");
129 ch=getchar();
130 }
131 printf("\n\n 程序已經完成.\n");
132 ch=getchar();
133 ch=getchar();
134 } 運作結果：
繼續執行，程式崩了··········