操作系统期末课程设计-创新互联

进程调度算法模拟 一、设计目的

编程实现进程调度的算法，更好地掌握操作系统的原理及实现方法，从而有利于把握进程调度细节。

创新互联建站是一家专业提供连山企业网站建设,专注与网站设计制作、成都网站设计、H5开发、小程序制作等业务。10年已为连山众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。二、设计要求

(1)要求实现先来先服务,短作业优先,时间片轮转,高优先权调度算法四种算法并进行对比分析.

(2)要求界面简单,易懂,关键代码部分要注释.

(3)编程语言可以采用自己任意精通的语言

三、设计思想说明

先来先服务：程序的执行调度顺序按先进入队列的先获得执行，并且其他进程都不能中断正在执行的进程，要等进程完成后才能，让出CPU给其他进程。执行的时候可以随时在队列中插入进程。

短作业优先：进程的调度顺序按程序的服务时间来决定，进程的执行顺序。服务时间短的先被调用。调度时先从队列中选取服务时间最短的进程来执行。进程中途不能中断，即使此时队列中存在服务时间比其更短的进程，仍需要等待该进程执行完后才能被执行。

高优先权调度：选取进程中优先级最高的一个，以优先级的值大，优先级就大。调度时总是选取队列中进程优先级最高的来执行，不管是否有某个进程在执行，只要存在比正在执行进程优先级高的进程，则就会立刻中断正在执行的进程，让给跟高优先级的进程。

时间片轮转：本课程设计采用多级反馈队列调度算法，设立4个进程队列，分给队列1的时间片为3秒，队列2的时间片为6秒，队列3的时间片为12秒，队列4的时间片为24秒。队列1的优先级最高，队列4的优先级最低。高优先级的队列没执行完，即不为空，就永远不执行其下面的低优先级的队列里面的进程。当执行低优先级队列里面的进程时，突然间高优先级的队列插入了进程就立刻跳到高优先级的队列执行其里面的进程。每个队列的进程都是按先来先执行的顺序执行。进程初次执行肯定要进入队列1。如何从头到尾执行一遍队列1中的进程是，存在某些进程在队列1的时间片内还没执行完，就把进程移交到下一个队列中。每个队列都如此类推。直到最后一个队列4，如果在队列4还有进程在本时间片内还没没执行完，就把该程序放到队尾，从新等待时间片执行。

基本概念

程序：程序是指静态的指令集合，它不占用系统的运行资源，可以长久地保存在磁盘中。

进程：进程是指进程实体（由程序、数据和进程控制块构成）的运行过程，是系统进行资源分配和调度的一个独立单位。进程执行程序，但进程与程序之间不是一一对应的。通过多次运行，一个程序可以包含多个进程；通过调用关系，同一进程可以被多个程序包含（如一个DLL文件可以被多个程序运用）。

作业：作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。作业可以是完成了编译、链接之后的一个用户程序，也可以是各种命令构成的一个脚本。

作业调度：作业调度是在资源满足的条件下，将处于后备状态的作业调入内存，同时生成与作业相对应的进程，并为这些进程提供所需要的资源。作业调度适用于多道批处理系统中的批处理作业。根据作业控制块中的信息，检查系统是否满足作业的资源要求，只有在满足作业调度的资源需求的情况下，系统才能进行作业调度。

基本调度算法

1）先来先服务（First-Come First-Served，FCFS）调度算法

先来先服务调度算法遵循按照进入后备队列的顺序进行调度的原则。该算法是一种非抢占式的算法，是到目前为止最简单的调度算法，其编码实现非常容易。该算法仅考虑了作业到达的先后顺序，而没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求。

2）短作业优先（Shortest-Job-First，SJF）调度算法

短作业优先调度算法根据作业控制块中指出的执行时间，选取执行时间最短的作业优先调度。本实验中规定，该算法是非抢占式的，即不允许立即抢占正在执行中的长进程，而是等当前作业执行完毕再进行调度。

3）响应比高者优先（HRRF）调度算法

FCFS调度算法只片面地考虑了作业的进入时间，短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。响应比高者优先调度算法为这两种算法的折中。响应比为作业的响应时间与作业需要执行的时间之比。作业的响应时间为作业进入系统后的等待时间与作业要求处理器处理的时间之和。

4）优先权高者优先（Highest-Priority-First，HPF）调度算法

优先权高者优先调度算法与响应比高者优先调度算法十分相似，根据作业的优先权进行作业调度，每次总是选取优先权高的作业优先调度。作业的优先权通常用一个整数表示，也叫优先数。优先数的大小与优先权的关系由系统或者用户规定。优先权高者优先调度算法综合考虑了作业执行时间和等待时间的长短、作业的缓急度，作业对外部设备的使用情况等因素，根据系统设计目标和运行环境而给定各个作业的优先权，决定作业调度的先后顺序。

实验环境与测试数据

实验环境

硬件环境：计算机一台；

软件环境：Linux操作系统，C语言编程环境。

本实验所选用的调度算法均默认为非抢占式调度。

测试数据如下表所示。

作业Id	到达时间	执行时间	优先权
1	800	50	0
2	815	30	1
3	830	25	2
4	835	20	2
5	845	15	2
6	700	10	1

重要函数说明

void initial_jobs()

初始化所有作业信息

void reset_jinfo()

重置所有作业信息

int findminjob(job jobs[],int count)

找到执行时间最短的作业。输入参数：所有的作业信息及待查找的作业总数，输出为执行时间最短的作业id

int findrearlyjob(job jobs[],int count)

找到达到最早的作业 输入参数：所有的作业信息及待查找的作业总数，输出参数为最早达到的作业id

void readJobdata()

//读取作业的基本信息

void FCFS()

//先来先服务算法

void SFJschdulejob(job jobs[],int count)

//短作业优先算法 输入参数：所有的作业信息及待查找的作业总数

实验内容

运行程序代码

#include#include#include#include//大作业数量
#define MAXJOB 50
//作业的数据结构
typedef struct node
{
 int number;//作业号        
 int reach_time;//作业抵达时间
 int need_time;//作业的执行时间
 int privilege;//作业优先权
 float excellent; //响应比
 int start_time;//作业开始时间
 int wait_time;//等待时间
 int visited;//作业是否被访问过
 bool isreached;//作业是否抵达
}job;
job jobs[MAXJOB];//作业序列
int quantity;//作业数量
//初始化作业序列
void initial_jobs()
{
 int i;
 for(i=0;ijobs[i].reach_time&&jobs[i].visited==0)
  {
   rearlyjob=jobs[i].reach_time;
   rearlyloc=i;
  }
 }
 return rearlyloc;
}
//读取作业数据
void readJobdata()
{
 FILE *fp;
 char fname[20];
 int i;
 //输入测试文件文件名
 printf("please input job data file name\n");
 scanf("%s",fname);
 if((fp=fopen(fname,"r"))==NULL)
 {//读取文件失败
  printf("error, open file failed, please check filename:\n");
 }
 else
 {
  //依次读取作业信息
  while(!feof(fp))
  {
 if(fscanf(fp,"%d %d %d %d",&jobs[quantity].number,&jobs[quantity].reach_time,&jobs[quantity].need_time,&jobs[quantity].privilege)==4)
   quantity++;
  }
  //打印作业信息
  printf("output the origin job data\n");
  printf("---------------------------------------------------------------------\n");
  printf("\tjobID\treachtime\tneedtime\tprivilege\n");
  for(i=0;icurrent_time)
  {
   jobs[loc].start_time=jobs[loc].reach_time;
   current_time=jobs[loc].reach_time;
  }
  else
  {
   jobs[loc].start_time=current_time;
  }
  jobs[loc].wait_time=current_time-jobs[loc].reach_time; 
 printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n",loc+1,jobs[loc].reach_time,jobs[loc].start_time,jobs[loc].wait_time,
   jobs[loc].wait_time+jobs[loc].need_time);
  jobs[loc].visited=1;
  current_time+=jobs[loc].need_time;
  total_waitime+=jobs[loc].wait_time; 
  total_roundtime=total_roundtime+jobs[loc].wait_time+jobs[loc].need_time;
  //获取剩余作业中最近到达作业
  loc=findrearlyjob(jobs,quantity);
 } 
 printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
 printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}
//短作业优先作业调度
//在current_time之前找最短，都在current_time之后找最近
void SFJschdulejob()
{
 int loc=0;
 int current_time=0;
 int total_waitime=0;
 int total_roundtime=0;
 int rearlyloc = findrearlyjob(jobs, quantity);//最早到达的作业序号
 loc = findminjob(jobs, jobs[rearlyloc].reach_time);
 //获取执行时间最短的作业
 //输出作业流
 printf("\n\nSJF算法作业流\n");
 printf("------------------------------------------------------------------------\n"); 
 printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
 current_time=jobs[loc].reach_time; 
 //每次循环找出最先到达的作业并打印相关信息
 for(int i=0;icurrent_time)
  {
   jobs[loc].start_time=jobs[loc].reach_time;
   current_time=jobs[loc].reach_time;
  }
  else
  {
   jobs[loc].start_time=current_time;
  }
  jobs[loc].wait_time=current_time-jobs[loc].reach_time; 
 printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n",loc+1,jobs[loc].reach_time,jobs[loc].start_time,jobs[loc].wait_time,
   jobs[loc].wait_time+jobs[loc].need_time);
  jobs[loc].visited=1;
  current_time+=jobs[loc].need_time;
  total_waitime+=jobs[loc].wait_time; 
  total_roundtime=total_roundtime+jobs[loc].wait_time+jobs[loc].need_time;
  //获取剩余作业中最短的作业
  loc=findminjob(jobs,current_time);
 }
 printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
 printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}
//高响应比调度算法
int max_excellent(job jobs[], int current_time)
{
 int maxjob= -1;
 int maxloc= -1;
 for (int i = 0; i< quantity; i++)
 {
  //current_time之前有最高响应比的作业，取
  if(jobs[i].reach_time<= current_time && jobs[i].visited==0)
  {
   if(jobs[i].excellent >maxjob)
   {
    maxjob=jobs[i].excellent;
    maxloc=i;
   }
  }
 }
 int min_reachtime = 1000000;
 //若current_time之前没有作业，
 //取current_time之后最先开始的(如果多个项目同时最先开始，取权值最高的)
 if (maxloc == -1)
 {
  for(int i=0;imaxjob)
     {
      maxjob=jobs[i].excellent;
      maxloc=i;
     }
    }
   }
  }
 }
 return maxloc;
}
void HRRFschdulejob() 
{
 int i; 
 int current_time=0;
 int loc;
 int total_waitime=0;
 int total_roundtime=0;
 float new_excellent=0;
 //获取最高响应比的作业
 int rearlyloc = findrearlyjob(jobs,quantity);
 loc = max_excellent(jobs, jobs[rearlyloc].reach_time);
 //输出作业流
 printf("\n\nHRRF算法作业流\n");
 printf("------------------------------------------------------------------------\n"); 
 printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
 current_time=jobs[loc].reach_time; 
 //每次循环找出最先到达的作业并打印相关信息
 for(i=0;icurrent_time)
  {
   jobs[loc].start_time=jobs[loc].reach_time;
   current_time=jobs[loc].reach_time;
  }
  else
  {
   jobs[loc].start_time=current_time;
  }
  jobs[loc].wait_time=current_time-jobs[loc].reach_time; 
 printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n",loc+1,jobs[loc].reach_time,jobs[loc].start_time,jobs[loc].wait_time,
   jobs[loc].wait_time+jobs[loc].need_time);
  jobs[loc].visited=1;
  current_time+=jobs[loc].need_time;
  total_waitime+=jobs[loc].wait_time; 
  total_roundtime=total_roundtime+jobs[loc].wait_time+jobs[loc].need_time;
  //获取剩余作业中最近到达作业
 
 for(int j = 0; j< quantity; j++)
  {
   if(current_time >jobs[j].reach_time && jobs[j].visited == 0)
   {
    jobs[j].wait_time = current_time - jobs[j].reach_time;
    new_excellent =( (float)jobs[j].wait_time + (float)jobs[j].need_time ) / (float)jobs[j].need_time ;
   jobs[j].excellent = new_excellent;
   }
   
  }
  loc = max_excellent(jobs, current_time);
 } 
 printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
 printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}
int max_privilege(job jobs[], int current_time)
{
 int maxjob= -1;
 int minloc= -1;
 for (int i = 0; i< quantity; i++)
 {
  //current_time之前有最高权值，取
  if(jobs[i].reach_time<= current_time && jobs[i].visited==0)
  {
   if(jobs[i].privilege >maxjob)
   {
    maxjob=jobs[i].privilege;
    minloc=i;
   }
  }
 }
 int min_reachtime = 100000;
 //current_time之前没有作业，
 //取current_time之后最先开始的(如果多个项目同时最先开始，取权值最高的)
 if (minloc == -1)
 {
  for(int i=0;imaxjob)
     {
      maxjob=jobs[i].privilege;
      minloc=i;
     }
    }
   }
  }
 }
 return minloc;
}
//优先权高者优先调度算法
void HPF()
{
 int loc=0;
 int current_time=0;
 int total_waitime=0;
 int total_roundtime=0;
 int rearlyloc = findrearlyjob(jobs, quantity);
 loc = max_privilege(jobs, jobs[rearlyloc].reach_time);
 //获取优先权最高的作业
 //输出作业流
 printf("\n\nHPF算法作业流\n");
 printf("------------------------------------------------------------------------\n"); 
 printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
 current_time=jobs[loc].reach_time; 
 //每次循环找出最先到达的作业并打印相关信息
 for(int i=0;icurrent_time)
  {
   jobs[loc].start_time=jobs[loc].reach_time;
   current_time=jobs[loc].reach_time;
  }
  else
  {
   jobs[loc].start_time=current_time;
  }
  jobs[loc].wait_time=current_time-jobs[loc].reach_time; 
 printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n",loc+1,jobs[loc].reach_time,jobs[loc].start_time,jobs[loc].wait_time,
   jobs[loc].wait_time+jobs[loc].need_time);
  jobs[loc].visited=1;
  current_time+=jobs[loc].need_time;
  total_waitime+=jobs[loc].wait_time; 
  total_roundtime=total_roundtime+jobs[loc].wait_time+jobs[loc].need_time;
  //获取剩余作业中最短的作业
  loc=max_privilege(jobs,current_time);
 }
 printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
 printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}
 
int main() 
{   
 initial_jobs(); 
 readJobdata();
 HRRFschdulejob();
 reset_jinfo();
 HPF();
 reset_jinfo();
 FCFS();
 reset_jinfo();
 SFJschdulejob();
 system("pause");
 return 0;
}

时间片轮转调度算法模拟C语言

#include#include#define MAX 10   //大进程数
int Time;   //时间片
int process_amount;  //进程数量
int current_number = 0;   //当前执行的“号码牌”
int index = 0;       //就绪队列要发的“号码牌”，初始值为0
struct PCB
{
 char name[10];   //进程名字
 int arrival_time;   //到达时间
 int service_time;   //服务时间
 int completion_time;   //完成时刻
 int sign_completion;  //标志是否完成调用，0表示没完成，1表示完成
 int remaining_time;  //剩余服务时间
 int number;          //进程在就绪队列里的“号码牌”
}process[MAX];
void input()     //初始化进程的信息
{
 int i;
 printf("请输入时间片：\n");
 scanf("%d",&Time);
 printf("请输入进程名称、到达时间、服务时间：\n");
 for(i = 0; i< process_amount; i ++)      
 { 
  printf("%d号进程:\n",i+1);
  scanf("%s%d%d",process[i].name,&process[i].arrival_time,&process[i].service_time);
  printf("\n");
  process[i].remaining_time = process[i].service_time;
  process[i].sign_completion = 0;
  process[i].number = 0;       //“号码牌”初始为0
 }
}
void BubbleSort()    //冒泡排序算法对进程抵达时间先后排序
{
 int i,j,n = process_amount;
 for(i = 0; i< n - 1; i++)         
 for(j = 0; j< n - 1 - i; j++) 
 {
  if(process[j].arrival_time >process[j+1].arrival_time)
  {
   process[n] = process[j+1];
   process[j+1] = process[j];
   process[j] = process[n];
 
  }
 }
}
void RunProcess()     //时间片轮转调用过程
{
 int time = process[0].arrival_time;      //给当前时间赋初值 
 int sum = 0;     //记录完成的进程数 
 int i,j;
 while(sum< process_amount)
 {  
 for(i = 0;  i< process_amount; i++)
  if(current_number == process[i].number && process[i].sign_completion == 0)
  {
    if(process[i].remaining_time<= Time)    //剩余服务时间少于等于一个时间片 
    {
    time = time + process[i].remaining_time;
    process[i].sign_completion = 1;
    process[i].completion_time = time;
    process[i].remaining_time = 0;
   printf("%s ",process[i].name);          
   sum++;
   current_number++;
   for(j = i + 1; j< process_amount; j++)     //检测后面有没有新进程到达
    if(process[j].arrival_time<= time && process[j].number == 0)
    {
     index++;
     process[j].number = index;
    }
    }
    else if(process[i].remaining_time >Time)//剩余服务时间大于一个时间片 
    {
     time = time + Time;
    process[i].remaining_time -= Time;
    printf("%s ",process[i].name);
    current_number++;
    for(j = i + 1; j< process_amount; j++)    //检测后面有没有新进程到达
    if(process[j].arrival_time<= time && process[j].number == 0)
    {
     index++;
     process[j].number = index;
    }
    index++;
    process[i].number = index;
   } 
  }
 if(index< current_number && sum< process_amount)   // 还有没执行的进程，且没进入就绪队列 
 {
 for(i = 0; i<= process_amount; i++)
  if(process[i].sign_completion == 0) 
  {
   time = process[i].arrival_time;
   index++;
   process[i].number = index;
   break;
  }
 }
}
}
void output()   //打印信息
{
 int i;
 printf("程序名 到达时间 服务时间 完成时间 周转时间  带权周转时间\n");
 for(i = 0; i< process_amount; i++)
 {
  float weight_time = (float)(process[i].completion_time - process[i].arrival_time)/process[i].service_time;
  printf("  %s\t  %d\t   %d\t    %d\t     %d\t\t%.2f\n",process[i].name,process[i].arrival_time,process[i].service_time,
   process[i].completion_time,process[i].completion_time-process[i].arrival_time,weight_time);
 }
}
int main()
{
 int f;
 printf("模拟时间片轮转法实现进程调度\n");
 printf("请输入总进程数：\n");
 scanf("%d",&process_amount);
 input();
 BubbleSort();
 printf("进程运行顺序：\n");
 RunProcess();
 printf("\n");
 output();
 printf("\n");
 system("pause");
 return 0;
}

实验步骤

1）先来先服务（First-Come First-Served，FCFS）调度算法，2）短作业优先（Shortest-Job-First，SJF）调度算法，3）响应比高者优先（HRRF）调度算法，4）优先权高者优先（Highest-Priority-First，HPF）调度算法

代码如下

使用vim tiaodu.c 编辑器并且编写代码,保存退出，再使用cat tiaodu.c查看

使用vim a.txt创建一个测试数据，保存后使用cat b.txt查看

使用命令gcc tiaodu.c –o tiaodu.c 编译代码，./tiaodu运行程序，接着输入测试数据的文件名

时间片轮转调度算法

使用vim rr3.c 编辑器并且编写代码,保存退出

使用cat rr3.c查看

执行结果：

1）先来先服务（First-Come First-Served，FCFS）调度算法，2）短作业优先（Shortest-Job-First，SJF）调度算法，3）响应比高者优先（HRRF）调度算法，4）优先权高者优先（Highest-Priority-First，HPF）调度算法

结果如下

时间片轮转调度算法结果

编辑切换为居中

添加图片注释，不超过 140 字（可选）

实验总结

由四种算法的测试数据来看，算法思想不同，所需的等待时间和周转时间也不同。

算法与等待时间、执行时间、优先级的关系

作业调度算法	等待时间	执行时间	优先权
FCFS	√
SJF		√
HRRF	√	√
HPF			√

从上表得出FCFS算法仅考虑作业的等待时间，等待时间长的优先考虑；SJF算法主要考虑作业的执行时间，执行时间短的优先考虑；HRRF算法同时考虑了作业的等待时间和执行时间，是FCFS和SJF算法的折中；HPF算法仅考虑作业的优先权，优先权高者先执行。

我们实验结果中可以发现对测试数据而言，并非HRRF算法的平均等待时间和平均周转时间最短。对于这组作业，SJF算法的平均等待时间和平均周转时间比 HRRF算法和HPF算法的短，说明最适合这个作业的调度算法是SJF。

由此可以得出判断算法的好坏要根据具体的作业，如果对于a作业A算法的平均等待时间和周转时间是最短的，那说明A算法是最适合a作业的调度算法。

心得

FCFS算法比较有利于长作业，而不利于短作业，有利于CPU繁忙型作业，而不利于I/O繁忙型作业。并且 用于批处理系统，不适于分时系统。

SJF算法易于实现，照顾了短进程，缩短了短进程的等待时间，体现了短进程优先原则，改善了平均周转时间和平均带权周转时间，有利于提高系统的吞吐量。但是对长进程不利，甚至会导致长进程长时间无法得到关注而使得系统整体性能下降，完全未考虑进程的急迫程度，因而不能保证紧迫性进程会被及时处理，进程的运行时间很难精确估计，进程在运行前不一定能真正做到短进程被优先调度。

HRRF算法既照顾了短作业又照顾了长作业，同时也照顾了先到达进程。但是调度之前需要计算各个进程的响应比，增加了系统开销，导致对实时进程无法做出及时反映。

HPF算法调度灵活，能适应多种调度需求。但是进程优先级的划分和确定每个进程优先级比较困难，同时抢占式调度增加了系统开销。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：操作系统期末课程设计-创新互联
分享链接：http://cdkjz.cn/article/ccgshp.html