4.18 进程调度模拟算法

一、实验目的

进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法。

二、实验内容和要求

设计进程控制块PCB的结构，通常应包括：进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。
编写两种调度算法程序：

1) 优先数调度算法程序；

2) 循环轮转调度算法程序。

将程序源代码和运行截图写入实验报告并提交。

三、实验步骤

实验准备

(1) 查阅相关资料；

(2) 初步编写程序；

(3) 准备测试数据；

(4) 设计数据结构

上机调试

主要流程和源代码

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <windows.h>  // 进程控制块数据结构 typedef struct node {   char name[20];     /*进程的名字*/   int prio;          /* 进程的优先级*/   int round;         /* 分配 CPU 的时间片*/   int cputime;       /* CPU 执行时间*/   int needtime;      /* 进程执行所需要的时间*/   char state;        /* 进程的状态， W——就绪态， R——执行态， F——完成态*/   int count;         /* 记录执行的次数*/   struct node *next; /* 链表指针*/ } PCB; PCB *ready = NULL, *run = NULL, *finish = NULL, *tail = NULL; /*定义三个队列，就绪队列头，执行队列头和完成队列头，就绪队列尾*/ int N; void firstin(void);              //调度就绪队列的第一个进程投入运行 void print1(char a);             //打印表头行信息 void print2(char chose, PCB *p); //打印每一行的状态信息 void insert_prio(PCB *q);        //在优先数算法中，将尚未完成的PCB按优先顺序插入到就绪队列中 void prior_init(char chose);     //在进程优先级法初始化将进程按优先级插入到就绪队列中 void priority(char chose);       //进程优先级算法总函数 void insert_rr(PCB *q);          //在轮转法中，将执行了一个时间单位片（为2），但尚未完成的进程的PCB，插入到就绪队列的队尾 void roundrun_init(char chose);  //循环轮转法初始化将就绪队列保存为FIFO队列 void roundrun(char chose);       //循环轮转法总算法  void main() //主函数 {   char chose = ' ';   while ((chose != 'q') && (chose != 'Q'))   {     fflush(stdin);     printf(选择进程优先级算法请输入P,选择循环轮转算法请输入R,退出请输入Q\n);     printf(请输入你的选择：);     scanf(%c, &chose);     if ((chose != 'q') && (chose != 'Q'))     {       system(cls);       if ((chose == 'P') || (chose == 'p'))       {         prior_init(chose);         priority(chose);         system(cls);       }       else if ((chose == 'r') || (chose == 'R'))       {         roundrun_init(chose);         roundrun(chose);         system(cls);       }     }   }   printf(谢谢使用！\n); }  void firstin(void) //调度就绪队列的第一个进程投入运行 {   if (ready != NULL)   {     run = ready;     ready = ready->next;     run->state = 'R';     run->next = NULL;   }   else   {     run = NULL;   } }  void print1(char a) // 打印表头行信息 {   if (toupper(a) == 'P')   {     printf(name cputime needtime priority state \n);   }   else   {     printf(name cputime needtime count round state \n);   } }  void print2(char chose, PCB *p) //打印每一行的状态信息 {   if (toupper(chose) == 'P')   {     printf(%s\t%d\t%d\t%d\t%c\n, p->name, p->cputime, p->needtime, p->prio, p->state);   }   else   {     printf(%s\t%d\t%d\t%d\t%d\t%c\n, p->name, p->cputime, p->needtime, p->count, p->round, p->state);   } }  void print(char chose) //打印每执行一次算法后所有的进程的状态信息 {   PCB *p;   print1(chose);   if (run != NULL)   {     print2(chose, run);   }   p = ready;   while (p != NULL)   {     print2(chose, p);     p = p->next;   }   p = finish;   while (p != NULL)   {     print2(chose, p);     p = p->next;   } }  void insert_prio(PCB *q) /*在优先数算法中,将尚未完成的PCB按优先数顺序插入到就绪队列中;*/ {   PCB *p, *s, *r; /* p,r用来控制就绪队列滚动，S指向插入的队列*/   s = q;   p = ready;   r - p;   if (s->prio > ready->prio) //要插入的进程的优先级大于ready 的优先级{   {     s->next = ready;     ready = s;   }   else //要插入的进程的优先级不大于ready 的优先级   {     while (p)     {       if (p->prio >= s->prio)       {         r = p;         p = p->next;       }       else         break;     } // 找到要插入的位置     s->next = p;     r->next = s;   } }  void prior_init(char chose) /*进程优先级法初始化将进程按优先级插入到就绪队列里*/ {   PCB *p;   int i, time;   char na[10];   ready = NULL;   finish = NULL;   run = NULL;   printf(输入进程的个数N:\n);   scanf(%d, &N);   for (i = 0; i < N; i++)   {     p = (PCB *)malloc(sizeof(PCB));     printf(输入第%d个进程名\n, i + 1);     scanf(%s, na);     printf(完成进程需要的时间片数\n);     scanf(%d, &time);     strcpy(p->name, na);     p->cputime = 0;     p->needtime = time;     p->state = 'W';     p->prio = 50 - time; // 设置进程优先值初值     if (ready == NULL)     {       ready = p;       ready->next = NULL;     }     else     {       insert_prio(p);     }     printf(当前就绪队列的进程的信息\n);     print(chose);   }   printf(%d个进程已按优先级从高到低进到就绪队列中\n, N);   printf(按回车键开始模拟优先级算法....\n);   fflush(stdin);   getchar();   firstin(); }  void priority(char chose) //进程优先级算法总函数 {   int i = 1;   while (run != NULL)   {     run->cputime += 1;     run->needtime -= 1;     run->prio -= 1;     if (run->needtime == 0)     {       run->next = finish;       finish = run;       run->state = 'F';       run->prio = 0;       run = NULL;       firstin();     }     else     {       if ((ready != NULL) && (run->prio < ready->prio))       {         run->state = 'W';         insert_prio(run);         run = NULL;         firstin();       }     }     print(chose);   }   getchar(); }  void insert_rr(PCB *q) //在轮转法中，将执行了一个时间片单位（为2),//但尚未完成的进程的PCB，插到就绪队列的队尾; {   tail->next = q;   tail = q;   q->next = NULL; }  void roundrun_init(char chose) /*循环轮转法初始化将就绪队列保存为FIFO队列*/ {   PCB *p;   int i, time;   char na[10];   ready = NULL;   finish = NULL;   run = NULL;   printf(\t\t循环轮转算法模拟全过程\n\n);   printf(输入进程的个数N:\n);   scanf(%d, &N);   for (i = 0; i < N; i++)   {     p = (PCB *)malloc(sizeof(PCB));     printf(输入第%d个进程名\n, i + 1);     scanf(%s, na);     printf(完成进程需要的时间片数\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)     {       insert_rr(p);     }     else     {       p->next = ready;       ready = p;       tail = p;     }     printf(当前就绪队列的进程的信息\n);     print(chose);   }   printf(%d 个进程已按FIFO进到就绪队列中\n, N);   printf(按回车键开始模循环轮转算法......\n);   fflush(stdin);   getchar();   run = ready;   ready = ready->next;   run->state = 'R'; }  void roundrun(char chose) //循环轮转法总算法 {   int i = 1;   while (run != NULL)   {     run->cputime += 1;     run->needtime -= 1;     run->count += 1;     if (run->needtime == 0)     {       run->next = finish;       finish = run;       run->state = 'F';       run->prio = 0;       run = NULL;       if (ready != NULL)       {         firstin();       }     }     else     {       if (run->count = run->round)       {         run->count = 0;         if (ready != NULL)         {           run->state = 'W';           insert_rr(run);           firstin();         }       }     }     print(chose);   }   getchar(); }