4.18 进程调度模拟算法

本文主要是介绍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();
}