實驗三進程調度模擬程序 - z1230－IT工程師數位筆記本

文章出處

實驗二、作業調度模擬程序實驗

專業 13物聯網姓名張欣怡學號 201306104135

1. 目的和要求

實驗目的

用高級語言完成一個進程調度程序，以加深對進程的概念及進程調度算法的理解。

實驗要求

設計一個有 N（N不小于5）個進程并發執行的進程調度模擬程序。

進程調度算法：“時間片輪轉法”調度算法對N個進程進行調度。

2. 實驗內容

完成兩個算法(簡單時間片輪轉法、多級反饋隊列調度算法)的設計、編碼和調試工作，完成實驗報告。

1) 每個進程有一個進程控制塊（PCB）表示。進程控制塊包含如下信息：進程名、優先級、到達時間、需要運行時間、已用CPU時間、進程狀態等等。

2) 每個進程的狀態可以是就緒 r（ready）、運行R（Running）、或完成F（Finished）三種狀態之一。

3) 就緒進程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。

4) 如果運行一個時間片后，進程的已占用 CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進程還需要繼續運行，應把它插入就緒隊列等待下一次調度。

5) 每進行一次調度,程序都打印一次運行進程、就緒隊列中各個進程的 PCB，以便進行檢查。　　

6) 重復以上過程，直到所要進程都完成為止。

3. 實驗原理及核心算法

“輪轉法”有簡單輪轉法、多級反饋隊列調度算法。

(1). 簡單輪轉法的基本思想是：

所有就緒進程按 FCFS排成一個隊列，總是把處理機分配給隊首的進程，各進程占用CPU的時間片長度相同。如果運行進程用完它的時間片后還未完成，就把它送回到就緒隊列的末尾，把處理機重新分配給隊首的進程。直至所有的進程運行完畢。

(2). 多級反饋隊列調度算法的基本思想是：

將就緒隊列分為N級（N＝3～5），每個就緒隊列優先數不同并且分配給不同的時間片：隊列級別越高，優先數越低，時間片越長；級別越小，優先數越高，時間片越短。

系統從第一級調度，當第一級為空時，系統轉向第二級隊列，.....當處于運行態的進程用完一個時間片，若未完成則放棄CPU，進入下一級隊列。

當進程第一次就緒時，進入第一級隊列。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/*進程控制塊數據結構*/
typedef struct node 
{
  char name[10];/*進程名*/
 int prio;     /*進程優先級*/ 
 int round;    /*進程分配的時間片*/ 
 int cputime;  /*進程消耗的CUP時間*/
 int needtime; /*進程需要的CUP時間*/
 int count;    /*進程運行時間*/
 char state;   /*進程的狀態：'R':運行,'W'：等待,'F'：結束*/
 struct node *next;/*指向下一個進程的指針*/     
}PCB;

PCB *finish,*ready,*tail,*run;/*指向三個隊列的隊首的指針，tail為就緒隊列的隊尾指針*/

int N;/*定義進程的數目*/

/*
函數功能： 將進程就緒隊列中第一個放進就緒隊列 
函數原型： void firstin(void)
函數參數： void 
函數返回值：void
*/
void firstin(void)
{
    if(ready!=NULL)
    {
     run=ready;
     ready=ready->next;
     run->state='R';
     run->next=NULL;
   }
   else
   {
     run=NULL;
     
   }
   
}
 

/*
函數功能：輸出單個進程信息的函數 
函數原型：void prt2(char a,PCB *p)
函數參數：char a :a=='p'為優先級，=='r'為時間片輪轉 
          PCB *p 為指向待輸出的進程控制塊的指針     
函數返回值：void
*/
void prt2(char a,PCB *p)
{
  printf("%-10s,%-10d,%-10d,%-10d,%-10d,%-5c\n",p->name,p->cputime,p->needtime,p->count,p->round,p->state);
}



/*
函數功能：輸出所有進程信息的函數 
函數原型：void prt(char algo)
函數參數：char a :a=='p'為優先級，=='r'為時間片輪轉 
函數返回值：void
*/
void prt(char algo)
{
  PCB *p;
  if(run!=NULL)
  {
  prt2(algo,run);
  }
  
  p=ready;
  while(p!=NULL)
  {
   prt2(algo,p);
   p=p->next;
  }
  
  p=finish;
  while(p!=NULL)
  {
  prt2(algo,p);
  p=p->next;
  }
  getchar();
}


/*
函數功能：時間片輪轉算法調度將進程插入到就緒隊列算法 
函數原型：void insert2(PCB *q)
函數參數：PCB *q 待插入的隊列進程控制塊  
函數返回值：void
*/
 void insert2(PCB *q)
 {
 tail->next=q;
 tail=q;
 q->next=NULL;
 }


/*
函數功能：采用時間片輪轉法進程調度法時，進程初始化函數 
函數原型：void rcreate_task(char algo)
函數參數：char algo:  R
函數返回值：void
*/
void rcreate_task(char algo)
{
  PCB *p;
 int i,time;
 char na[10];
 ready=NULL;
 finish=NULL;
 run=NULL;
 for(i=0;i<N;i++)
 {
  p=(PCB*)malloc(sizeof(PCB));
  printf("\nEnter the name of process\n");
  scanf("%s",na);
   printf("Enter the time of process\n");
  scanf("%d",&time);
  strcpy(p->name,na);
  p->cputime=0;
  p->needtime=time;
  p->count=0;
  p->state='W';
  p->round=2;
  if(ready!=NULL)
  {
  insert2(p);
  }
  else
  {
    p->next=ready;
    ready=p;
    tail=p;
  }
 printf("Output the waiting processes information\n");
 prt(algo);
  }
 run=ready;
 ready=ready->next;
 run->state='R';
     
}


/*
函數功能：采用時間片輪轉法進程調度法時，進程調度函數 
函數原型：void roundrun(char algo)
函數參數：char algo:  R
函數返回值：void
*/
void roundrun(char algo)
{
  while(run!=NULL)
  {
  run->cputime=run->cputime+1;
  run->needtime=run->needtime-1;
  run->count=run->count+1;
  if(run->needtime==0)
  {
    run->next=finish;
   finish=run;
   run->state='F';
   run=NULL;
   if(ready!=NULL)
   {
      firstin();
    }         
   }
   else
   {
     if(run->count==run->round)
     {
     run->count=0; 
     if(ready!=NULL)
   {        
      run->state='W';
      insert2(run);
      firstin();
   }
    }
   }
   prt(algo);
  }  
}



/*main 函數*/

void main()
{
  char algo='r';
  printf("Please enter the number of processes N:\n");
  scanf("%d",&N);
  rcreate_task(algo);
  roundrun(algo);
}