實驗三 程序排程模拟程式
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. 實驗原理及核心算法參考程式段
動态優先數（優先數隻減不加）：
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define N 3
int count;
sort2();
struct pcb { /* 定義程序控制塊PCB */
char name[10]; //程序名
char status; //程序狀态
int prio; //優先數
int ntime; //需要運作的時間
int rtime; //已用時間
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB; //程序控制塊
struct pcb2 { /* 定義程序控制塊PCB2 */
char name[10];
char status;
int prio;
int atime;
int ntime;
int runtime;
int restime;
}pcb[24];
input2() /* 建立程序控制塊函數*/
{
int i,num;
printf("\n 請輸入程序數:");
scanf("%d",&num);
count=num;
for(i=0;i<num;i++)
{
printf("\n 程序号No.%d:\n",i);
printf("\n 請輸入程序名:");
scanf("%s",pcb[i].name);
printf("\n 請輸入程序到達時間:");
scanf("%d",&pcb[i].atime);
printf("\n 請輸入程序運作時間:");
scanf("%d",&pcb[i].ntime);
printf("\n");
pcb[i].runtime=0;
pcb[i].status='r';
pcb[i].restime=pcb[i].ntime;
}
sort2();
printf("\n\n--------------FCFS排序之後-----------------\n");
printf("程序名 到達時間 需要運作時間\n");
for(i=0;i<num;i++)
{
printf("%s %d %d \n",pcb[i].name,pcb[i].atime,pcb[i].ntime);
}
}
sort2()
{
int i,j;
struct pcb2 t;
for(i=0;i<count-1;i++) //按程序到達時間的先後排序
{ //如果兩個程序同時到達，按在螢幕先輸入的先運作
for(j=i+1;j<count;j++)
{
if(pcb[j].atime< pcb[i].atime)
{
t=pcb[j];
pcb[j]=pcb[i];
pcb[i]=t;
}
}
}
}
sort() /* 程序進行優先級排列函數*/
{
PCB *first, *second;
int insert=0;
if((ready==NULL)||((p->prio)>(ready->prio))) /*優先級最大者,插入隊首*/
{
p->link=ready;
ready=p;
}
else /* 程序比較優先級,插入适當的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
if((p->prio)>(second->prio)) /*若插入程序比目前程序優先數大,*/
{ /*插入到目前程序前面*/
p->link=second;
first->link=p;
second=NULL;
insert=1;
}
else /* 插入程序優先數最低,則插入到隊尾*/
{
first=first->link;
second=second->link;
}
}
if(insert==0) first->link=p;
}
}
input() /* 建立程序控制塊函數*/
{
int i,num;
/*clrscr(); */ /*清屏*/
printf("\n 請輸入程序數:");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n 程序号No.%d:\n",i);
p=getpch(PCB); /*宏(type*)malloc(sizeof(type)) */
printf("\n 請輸入程序名:");
scanf("%s",p->name);
/*printf("\n 輸入程序優先數:");
scanf("%d",&p->prio); */
p->prio=N;
printf("\n 請輸入程序運作時間:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->status='r';
p->link=NULL;
sort(); /* 調用sort函數*/
}
}
int space()
{
int l=0; PCB* pr=ready;
while(pr!=NULL)
{
l++;
pr=pr->link;
}
return(l);
}
disp(PCB * pr) /*單個程序顯示函數*/
{
printf("|%s\t",pr->name);
printf("|%c\t",pr->status);
printf("|%d\t",pr->prio);
printf("|%d\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("\n");
}
void printbyprio(int prio)
{
PCB* pr;
pr=ready;
printf("\n ****目前第%d級隊列(優先數為%d)的就緒程序有:\n",(N+1)-prio,prio); /*顯示就緒隊列狀态*/
printf("\n qname \tstatus\t prio \tndtime\t runtime \n");
while(pr!=NULL)
{
if (pr->prio==prio) disp(pr);
pr=pr->link;
}
}
check() /* 顯示所有程序狀态函數 */
{
PCB* pr;
int i;
printf("\n /\\/\\/\\/\\目前正在運作的程序是:%s",p->name); /*顯示目前運作程序*/
printf("\n qname \tstatus\t prio \tndtime\t runtime \n");
disp(p);
printf("\n 目前就緒隊列狀态為:\n"); /*顯示就緒隊列狀态*/
for(i=N;i>=1;i--)
printbyprio(i);
/*
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
*/
}
destroy() /*程序撤消函數(程序運作結束,撤消程序)*/
{
printf("\n 程序 [%s] 已完成.\n",p->name);
free(p);
}
running() /* 運作函數。判斷是否完成，完成則撤銷，否則置就緒狀态并插入就緒隊列*/
{
int slice,i;
slice=1;
for(i=1;i<((N+1)-p->prio);i++)
slice=slice*2;
for(i=1;i<=slice;i++)
{
(p->rtime)++;
if (p->rtime==p->ntime)
break;
}
if(p->rtime==p->ntime)
destroy(); /* 調用destroy函數*/
else
{
if(p->prio>1) (p->prio)--;
p->status='r';
sort(); /*調用sort函數*/
}
}
void cteatpdisp()
/*顯示(運作過程中)增加新程序後,所有就緒隊列中的程序*/
{
int i;
printf("\n 當增加新程序後,所有就緒隊列中的程序(此時無運作程序):\n"); /*顯示就緒隊列狀态*/
for(i=N;i>=1;i--)
printbyprio(i);
}
void creatp()
{
char temp;
printf("\nCreat one more process?type Y (yes)");
scanf("%c",&temp);
if (temp=='y'||temp=='Y')
{
input();
cteatpdisp();
}
}
PRIO()//最高優先數優先排程算法
{
int len,h=0;
char ch;
input();
len=space();
while((len!=0)&&(ready!=NULL))
{
ch=getchar();
/*getchar();*/
h++;
printf("\n The execute number:%d \n",h);
p=ready;
ready=p->link;
p->link=NULL;
p->status='R';
check();
running();
creatp();
printf("\n 按任一鍵繼續......");
ch=getchar();
}
printf("\n\n 程序已經完成.\n");
ch=getchar();
ch=getchar();
}
QueueSort()
{
int i;
struct pcb2 t;
t=pcb[0];
for(i=1;i<count;i++)
pcb[i-1]=pcb[i];
pcb[0].restime--;
pcb[count-1]=t;
}
QueueSort1()
{
int i;
for(i=1;i<count;i++)
pcb[i-1]=pcb[i];
count--;
}
RR()//時間片輪轉法排程算法
{
int timeflag=0;
int timepiece=2;
int T;
printf("\n請輸入時間片：");
scanf("%d",&T);
int k;
char ch;
input2();
sort2();
while(count>=0)
{
if(timeflag==T)
{
timeflag=0;
if(pcb[0].restime==0)
{
printf("程序%s已完成\n",pcb[0].name);
if(count!=0){
QueueSort1();
printf("目前正在運作程序是:%s\n",pcb[0].name);
}
if(count>=1)
for(k=1;k<count;k++)
printf("程序%s正在等待\n",pcb[k].name);
if(count==0){
pcb[0].restime--;
count--;
}
}
else{
QueueSort();
if(count!=0){
//QueueSort1();
printf("目前正在運作程序是:%s\n",pcb[0].name);
}
if(count>=1)
for(k=1;k<count;k++)
printf("程序%s正在等待\n",pcb[k].name);
}
}
else{
if(pcb[0].restime==0)
{
printf("程序%s已完成\n",pcb[0].name);
if(count!=0){
QueueSort1();
printf("程序%s正在運作\n",pcb[0].name);
}
if(count>=1)
for(k=1;k<count;k++)
printf("程序%s正在等待\n",pcb[k].name);
}
else{
pcb[0].restime--;
if(count!=0)
printf("程序%s正在運作\n",pcb[0].name);
if(count>=1)
for(k=1;k<count;k++)
printf("程序%s正在等待\n",pcb[k].name);
}
}
timeflag++;
printf("\n 按任一鍵繼續......");
ch=getchar();
ch=getchar();
}
printf("\n\n 全部程序已經完成.\n");
}
main() /*主函數*/
{
int select;
printf("-------------------請選擇程序排程算法----------------------\n");
printf("0:退出\n1:采用最高優先數優先排程算法\n2:采用基于時間片輪轉法排程算法\n");
printf("請選擇：");
scanf("%d",&select);
if(select==1)
{
PRIO();
}
else if(select==2)
{
RR();
}
else if(select==0)
{
exit(0);
}
} 