實驗三 程序排程模拟程式
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<string.h>
4 #define Max 100
5 typedef struct pcb
6 {
7 char name[Max]; //程序名
8 int priority; //優先級
9 int arrtime; //到達時間
10 int needtime; //需要運作時間
11 int usedtime; //已用時間
12 char state; //程序狀态
13 }PCB;
14 PCB pcb[Max];
15
16 int n=1;
17 int pTime; //時間片
18 char SelectMenu();
19 void Input();
20 void Sort();
21 void Print();
22 void Attemper();
23
24 char SelectMenu()
25 {
26 char select;
27 printf("\t 選擇菜單：");
28 printf("\n\t1.添加并排程程序");
29 printf("\n\t2.列印程序");
30 printf("\n\t3.退出");
31 printf("\n\n請輸入你的選擇(1--3):");
32 do{
33 select=getchar();
34 }while(select!='1'&&select!='2'&&select!='3');
35 return select;
36 }
37 void main()
38 {
39 int choice;
40 n=1;
41 choice=SelectMenu();
42 do{
43 if(choice=='1')
44 {
45 printf(" \n");
46 printf("請設定時間片的大小:");
47 scanf("%d",&pTime);
48 Input();
49 Print();
50 Attemper();
51 }
52 if(choice=='2')
53 {
54 Print();
55 }
56 if(choice=='3')
57 {
58 return;
59 }
60 choice=SelectMenu();
61 }while(1);
62 }
63 void Input()
64 {
65 int a;
66 printf("請輸入程序個數:");
67 scanf("%d",&a);
68 do{
69 printf("\n---請輸入第%d個程序程序---\n",n);
70 printf("\n程序名:");
71 scanf("%s",pcb[n].name);
72 printf("程序優先級:");
73 scanf("%d",&pcb[n].priority);
74 printf("程序需要的時間:");
75 scanf("%d",&pcb[n].needtime);
76 pcb[n].arrtime=n;
77 pcb[n].usedtime=0;
78 pcb[n].state='W';
79 n++;
80 }while(n<=a);
81 }
82 void Sort()
83 {
84 int i,j;
85 PCB temp;
86 for(i=0;i<n-1;i++) //按照到達時間排序
87 {
88 for(j=n-2;j>=i;j--)
89 {
90 if(pcb[j+1].arrtime<pcb[j].arrtime)
91 {
92 temp=pcb[j];
93 pcb[j]=pcb[j+1];
94 pcb[j+1]=temp;
95 }
96 }
97 }
98
99 for(i=0;i<n-1;i++) //按照優先級排序
100 {
101 for(j=n-2;j>=i;j--)
102 {
103 if(pcb[j+1].priority>pcb[j].priority)
104 {
105 temp=pcb[j];
106 pcb[j]=pcb[j+1];
107 pcb[j+1]=temp;
108 }
109 }
110 }
111 if(pcb[0].state!='F')
112 {
113 pcb[0].state='R';
114 }
115 }
116 void Print()
117 {
118 int i;
119 Sort();
120 printf("\n 程序名 優先級 到達時間 需要時間 已用時間 程序狀态 \n");
121 for(i=0;i<n;i++)
122 {
123 printf("%8s%8d %8d %10d %10d %10c\n",pcb[i].name,pcb[i].priority,pcb[i].arrtime,pcb[i].needtime,pcb[i].usedtime,pcb[i].state);
124 }
125 }
126 void Attemper()
127 {
128 do{
129 if((pcb[0].needtime-pcb[0].usedtime)>pTime) //判斷程序剩餘的運作時間是否大于時間片
130 {
131 pcb[0].usedtime+=pTime;
132 pcb[0].priority--;
133 pcb[0].state='W';
134 }
135 else //已完成的程序
136 {
137 pcb[0].usedtime=pcb[0].needtime;
138 pcb[0].priority=-1;
139 pcb[0].state='F';
140 }
141 Print();
142 }while(pcb[0].state!='F');
143 } 運作結果：
