實驗三程序排程模拟程式
專業：商軟一班 姓名：黃冠鋒 學号：201406114134
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). （**）在進行模拟排程過程可以建立（增加）程序，其到達時間為程序輸入的時間。
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 "conio.h"
3 #include <stdlib.h>
4 #define getpch(type) (type*)malloc(sizeof(type))
5 #define NULL 0
6
7 struct pcb{ /*定義程序控制塊pcb */
8 char name[10];
9 char state;
10 int super;
11 int ntime;
12 int rtime;
13 struct pcb* link;
14 }
15 *q=NULL,*p;
16 typedef struct pcb PCB;
17
18 void sort() /*建立對程序進行優先級排列函數*/
19 {
20 PCB *first,*second;
21 int i=0;
22 if((q==NULL)||((p->super)>(q->super))) /*優先數最大者插入隊首*/
23 {
24 p->link=q;
25 q=p;
26 }
27 else /*程序比較優先級，插入适當的位置中*/
28 {
29 first=q;
30 second=first->link;
31 while(second!=NULL)
32 {
33 if((p->super)>(second->super)) /*若插入程序比目前程序優先數大，插入到目前程序前面*/
34 {
35 p->link=second;
36 first->link=p;
37 second=NULL;
38 i=1;
39 }
40 else /*插入程序優先數最低，則插入到隊尾*/
41 {
42 first=first->link;
43 second=second->link;
44 }
45 }
46 if(i==0) first->link=p;
47 }
48 }
49
50 void input() /*建立程序控制塊函數*/
51 {
52 int i,num;
53 printf("\n 請輸入程序數：");
54 scanf("%d",&num);
55 for(i=0;i<num;i++)
56 {
57 printf("\n 請輸入程序号No.%d:\n",i);
58 p=getpch(PCB);
59 printf("\n 請輸入程序名：");
60 scanf("%s",p->name);
61 printf("\n 請輸入程序優先數：");
62 scanf("%d",&p->super);
63 printf("\n 請輸入程序運作時間：");
64 scanf("%d",&p->ntime);
65 printf("\n");
66 p->rtime=0;p->state='w';
67 p->link=NULL;
68 sort();
69 }
70 }
71
72 int len()
73 {
74 int l=0;PCB* pr=q;
75 while(pr!=NULL)
76 {
77 l++;
78 pr=pr->link;
79 }
80 return(l);
81 }
82
83 void show(PCB* pr) /*建立程序顯示函數，用于顯示目前程序*/
84 {
85 printf("\n qname \t state \t super \t ndtime \truntime \n");
86 printf("|%s\t",pr->name);
87 printf("|%c\t",pr->state);
88 printf("|%d\t",pr->super);
89 printf("|%d\t",pr->ntime);
90 printf("|%d\t",pr->rtime);
91 printf("\n");
92 }
93
94 void check() /*建立程序檢視函數*/
95 {
96 PCB* pr;
97 printf("\n 目前正在運作的程序是：%s",p->name); /*顯示目前運作程序*/
98 show(p);
99 pr=q;
100 printf("\n 目前就緒隊列狀态為：\n"); /*顯示就緒隊列狀态*/
101 while(pr!=NULL)
102 {
103 show(pr);
104 pr=pr->link;
105 }
106 }
107
108 void destroy() /*建立程序撤銷函數（程序運作結束，撤銷程序）*/
109 {
110 printf("\n 程序[%s]已完成.\n",p->name);
111 free(p);
112 }
113
114 void running() /*建立程序就緒函數（程序運作時間到，置就緒狀态）*/
115 {
116 (p->rtime)++;
117 if(p->rtime==p->ntime)
118 destroy();
119 else
120 {
121 (p->super)--;
122 p->state='w';
123 sort();
124 }
125 }
126
127 void main()
128 {
129 int length,h=0;
130 char ch;
131 input();
132 length=len();
133 while((length!=0)&&(q!=NULL))
134 {
135 ch=getchar();
136 h++;
137 printf("\n The execute number:%d \n",h);
138 p=q;
139 q=p->link;
140 p->link=NULL;
141 p->state='R';
142 check();
143 running();
144 printf("\n 按任一鍵繼續......");
145 ch=getchar();
146 }
147 printf("\n\n 程序已完成.\n");
148 ch=getchar();
149
150 } 實驗三
運作結果：
5. 實驗總結
通過這次實驗我覺得我還是在對C語言的使用尤其是在編寫代碼方面很欠缺，在老師和網上搜集資料後，經過多次修改程式，最終得以運作，解決了用動态優先級在方法實作程序排程模拟算法。在編寫和調試的過程中，我明白了有些問題是無法預料的，這就需要通過自己的不斷分析得出問題的解決方案。