操作系统实验一：处理器调度算法的实现

佚名 6年前 (2019-04-10) 随笔 816人围观抢沙发百度已收录

实验报告

一、实验目的

（1）加深对处理机调度的作用和工作原理的理解。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

（2）进一步认识并发执行的实质。

二、实验要求：

本实验要求用高级语言，模拟在单处理器情况下，采用多个调度算法，对N个进程进行进程调度。语言自选。

并完成实验报告。

三、实验内容：

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。

当就绪状态进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。

进程及进程队列的表示。
处理器调度算法：FCFS，SJF，RR，HRRN，MLFQ等
跟踪进程状态的转化
输出：系统中进程的调度次序，计算CPU利用率，平均周转时间和平均带权周转时间

四、实验过程与结果

算法思想与设计
算法实现代码
运行结果

算法思想与设计

通过构造进程输入input()，进程运行结果输出output()，disp(),以及使整个程序正常运行的函数块等，通过主函数调用方法函数的想法来实现作业调度。在对程序控制块的访问和调用通过链表指针的形式，进行调用各种作业调度算法。在作业输入后，会显示输入的内容，并把每一个作业运行的状态都能在程序中体现出来。

(1)先来先服务调度算法（FCFS）

该算法采用非剥夺策略，算法按照进程提交或进程变为就绪状态的先后次序，分派 CPU。当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程唤醒后（如I/O 完成），并不立即恢复执行，通常等到当前进程出让CPU。这是最简单的调度算法，比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程。

(2)短进程优先调度算法（SPN）

该算法也采用非剥夺策略，对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。缺点是对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。

(3)时间片轮转算法（RR）

该算法采用剥夺策略。让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。时间片轮转调度算法的特点是简单易行、平均响应时间短，但不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当。

算法实现代码

 #include<stdio.h>
   #include <stdlib.h>
   #include <conio.h>
   #define getpch(type) (type*)malloc(sizeof(type))    //为进程创建一个空间
    
   struct worktime{
       float Tb;             //作业运行时刻
       float Tc;             //作业完成时刻
       float Ti;             //周转时间
      float Wi;            //带权周转时间
  };
   
  struct jcb {              
      char name[10];        //作业名
      float arrivetime;        //作业到达时间
      float runtime;        //作业所需的运行时间
      char resource;        //所需资源
      float Rp;             //后备作业响应比
     char state;           //作业状态
      int worked_time;      //已运行时间   
      struct worktime wt;
      int need_time;       //需要运行的时间
      int flag;             //进程结束标志
      struct jcb* link;     //链指针
  }*ready=NULL,*p;
   
  typedef struct jcb JCB;//重命名结构体
  float T=0;
  int N;
  JCB *front,*rear;       
   
  void sort()     
  {
      JCB *first, *second;
      int insert=0;  //插入数
      if((ready==NULL)||((p->arrivetime)<(ready->arrivetime)))  
      {
          p->link=ready;
          ready=p;
          T=p->arrivetime;
          p->Rp=1;
      }
      else
      {
          first=ready;
          second=first->link;
          while(second!=NULL)
          {
              if((p->arrivetime)<(second->arrivetime))
              {
                  p->link=second;
                 first->link=p;
                  second=NULL;
                  insert=1;
              }
              else
              {
                  first=first->link;
                  second=second->link;
              }
         }
          if (insert==0) first->link=p;
      }
  }
   
  void SJFget()
  {
      JCB *front,*mintime,*rear;
      int ipmove=0;
      mintime=ready;
      rear=mintime->link;
      while(rear!=NULL)
     {
          if ((rear!=NULL)&&(T>=rear->arrivetime)&&(mintime->runtime)>(rear->runtime))
          {
              front=mintime;
              mintime=rear;
             rear=rear->link;
              ipmove=1;
         }
         else
             rear=rear->link;
      }
      if (ipmove==1)
      {
        front->link=mintime->link;
          mintime->link=ready;
      }
      ready=mintime;
  }
   
  void HRNget()
  {
      JCB *front,*mintime,*rear;
      int ipmove=0;
      mintime=ready;
      rear=mintime->link;
      while(rear!=NULL)
          if ((rear!=NULL)&&(T>=rear->arrivetime)&&(mintime->Rp)<(rear->Rp))
         {
             front=mintime;
             mintime=rear;
            rear=rear->link;
             ipmove=1;
         }
         else
            rear=rear->link;
     if (ipmove==1){
         front->link=mintime->link;
        mintime->link=ready;
     }
     ready=mintime;
 }
  
 void creatJCB() //为每个作业创建一个JCB并初始化形成一个循环链队列
 {   
     JCB *p,*l;
     int i=0;
     l = (JCB *)malloc(sizeof(JCB));
     printf("\n 请输入作业的个数:");
     scanf("%d",&N);
     printf("\n 作业号No.%d:\n",i);
     printf("\n请输入作业的名字:");
     scanf("%s",l->name);
     printf("\n请输入作业需要运行的时间:");
     scanf("%d",&l->need_time);
    l->state = 'r';          //作业初始状态为就绪(即准备状态)
     l->worked_time = 0;
     l->link=NULL;
     l->flag=0;
     front=l;
     for(i =1;i<N;i++)
     {
         p = (JCB *)malloc(sizeof(JCB));
         printf("\n 作业号No.%d:\n",i);
         printf("\n请输入作业的名字:");
         scanf("%s",p->name);
         printf("\n请输入作业的时间:");
         scanf("%d",&p->need_time);
         p->state='r';
         p->worked_time=0;
         p->flag=0;
         l->link=p;
         l=l->link;
     }
     rear=l;rear->link=front;
 }  
  
 void output()//进程输出函数
 {  
     int j;
     printf("name runtime needtime state\n");
     for(j=1;j<=N;j++)
     {   printf(" %-4s\t%-4d\t%-4d\t%-c\n",front->name,front->worked_time,front->need_time,front->state);
         front=front->link;
     }
    printf("\n");
 }
  
 int judge(JCB *p) //判断所有进程运行结束
 {
    int flag=1,i;
     for(i=0;i<N;i++)
     {
         if(p->state!='e')
        {
             flag = 0;
             break;}
         p=p->link;
     }
    return flag;
 }
  
 //作业输入 
 void input()
 {
     int i,num;
     printf("\n 请输入作业的个数:");
     scanf("%d",&num);
     for(i=0;i<num;i++)
     {
         printf(" 作业号No.%d:\n",i);
        p=getpch(JCB);
         printf(" 输入作业名:");
         scanf("%s",p->name);
         printf(" 输入作业到达时刻:");
         scanf("%f",&p->arrivetime);
         printf(" 输入作业运行时间:");
         scanf("%f",&p->runtime);
         printf("\n");
         p->state='w';
         p->link=NULL;
         sort();
     }
 }
  
 int space()
 {
     int l=0; JCB* jr=ready;
     while(jr!=NULL)
     {
         l++;
         jr=jr->link;
     }
     return(l);
 }
  
 void disp(JCB* jr,int select)
 {
     if (select==3) printf("\n 作业  到达时间  服务时间  响应比  运行时刻  完成时刻  周转时间  带权周转时间 \n");
     else printf("\n 作业 到达时间 服务时间 运行时刻 完成时刻 周转时间 带权周转时间 \n");
     printf(" %s\t",jr->name);
     printf("%.2f\t  ",jr->arrivetime);
     printf("%.2f\t",jr->runtime);
     if (select==3&&p==jr) printf("   |%.2f    ",jr->Rp);
     if (p==jr){
         printf(" %.2f\t",jr->wt.Tb);
         printf(" %.2f  ",jr->wt.Tc);
         printf("   %.2f\t",jr->wt.Ti);
         printf("   %.2f",jr->wt.Wi);
     }
     //printf("\n");
 }
  
 int destroy()
 {
     free(p);
     return(1);
 }
  
 void check(int select)
 {
     JCB* jr;
     printf(" 是 :%s",p->name);//当前执行的作业是
     disp(p,select);
     jr=ready;
     destroy(); }
  
 void running(JCB* jr)
  {
     if (T>=jr->arrivetime) jr->wt.Tb=T;
     else jr->wt.Tb=jr->arrivetime;
     jr->wt.Tc=jr->wt.Tb+jr->runtime;
     jr->wt.Ti=jr->wt.Tc-jr->arrivetime;
     jr->wt.Wi=jr->wt.Ti/jr->runtime;
     T=jr->wt.Tc;
 }
  
 int main()
 {
     int select=0,len,h=0;
     float sumTi=0,sumWi=0;
     printf("请选择作业调度算法的方式:\n");
     printf("\t1.FCFS 2.SJF 3.HRN \n");
     printf("请输入作业调度算法序号(1-3):");
     scanf("%d",&select);
 
     input();   //调用输入函数
     len=space();
    
      
     while((len!=0)&&(ready!=NULL))
     {
         h++;
         printf(" 第%d个执行作业 ",h);
         p=ready;
         ready=p->link;
         p->link=NULL;
         p->state='R';
         running(p);
         sumTi+=p->wt.Ti;
         sumWi+=p->wt.Wi;
         check(select); //与所选择的算法比较，调用void check(int select)
         if (select==2&&h<len-1) SJFget();
         if (select==3&&h<len-1) HRNget();
         getchar();
         getchar();
     }
     printf(" 作业已经完成.\n");
     printf("\t 此组作业的平均周转时间：%.2f\n",sumTi/h);
    printf("\t 此组作业的带权平均周转时间：%.2f\n",sumWi/h);
     getchar();
 }