计算机操作系统实验报告

                                 实验二  进程调度算法

一、实验名称：进程调度算法

二、实验内容：编程实现如下算法：

1.先来先服务算法；

                    2.短进程优先算法；

                    3.时间片轮转调度算法。

三、问题分析与设计：

 1.先来先服务调度算法

先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。

  

 

 

2.短作业（进程）优先调度算法

短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。

 

3.时间片轮转算法

在时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

 

 

 

 

 

四、程序代码：

#include <cstdlib>

#include <iostream>

#include<iomanip>

using namespace std;

struct A{   //先来先服务算法从这里开始

    char name[10];   

    float arrivetime;   

    float servicetime;   

    float starttime;   

    float finishtime;   

    float zztime;   

    float dqzztime; 

    float avzztime;

    float avdqzztime;

    float lefttime;

    float stoptime;

    int timeprice;

};   //定义一个结构体，里面包含的有一个进程相关的信息

A a[100];  //先来先服务算法从这里开始

void input(A *p,int N)   

{

    int i;  

    cout<<endl;

    printf("    请您输入进程的            名字   到达时间   服务时间:  (例如: a 0 100)\n\n");   

    for(i=0;i<=N-1;i++)   

    {   

         printf("     请您输入进程%d的信息:\t",i+1);

         scanf("\t\t\t%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);  

        

    }   

  

}   

void Print(A *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N)   

{

    int k;     

     cout<<endl;

    printf("\n   具体进程调度信息:\n\n");   

    printf("\t进程名  到达时间  服务时间  开始时间  结束时间  周转时间  带权周转时间\n");   

  

     for(k=0;k<=N-1;k++)   

     {

          printf("\t%s\t%-.2f\t  %-.2f\t   %-.2f\t       %-.2f\t %-.2f\t  %-.2f\n",p[k].name,p[k].arrivetime,

              p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);

     }

     getchar();  

}

 

  

void sort(A *p,int N)  //到达时间排序 

{   

     for(int i=0;i<=N-1;i++)   

         for(int j=0;j<=i;j++)   

             if(p[i].arrivetime<p[j].arrivetime)   

             {   

                 A temp;   

                 temp=p[i];   

                 p[i]=p[j];   

                 p[j]=temp;   

             }   

}    

void deal(A *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,/*float &avzztime,float &avdqzztime,*/int N)   //运行阶段  

{

    int k;   

    for(k=0;k<=N-1;k++)   

     {   

         if(k==0)   

          {    

              p[k].starttime=p[k].arrivetime;   

              p[k].finishtime=p[k].arrivetime+p[k].servicetime;}   

  

         else  

          {   

              p[k].starttime=p[k-1].finishtime;   

             p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}   

     }   

  

     for(k=0;k<=N-1;k++)   

     { 

          p[k].zztime=p[k].finishtime-p[k].arrivetime;  

          p[k].dqzztime=p[k].zztime/p[k].servicetime; 

         } 

     

}      

void FCFS(A *p,int N)   

{    float sumzztime=0,  sumdqzztime=0,avzztime,avdqzztime;

     float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;

     sort(p,N);   

     deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);  

     Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);

     for(int k=0;k<=N-1;k++)

     {

          sumzztime=sumzztime+p[k].zztime;

        sumdqzztime=sumdqzztime+ p[k].dqzztime;

     }

    avzztime=sumzztime/N;

     printf("\n该算法的平均周转时间为:%-.2f\t",avzztime);

     avdqzztime= sumdqzztime/N; 

     printf("该算法的平均带权周转时间为:%-.2f\t\n\n",avdqzztime);

     getchar();      

}  //先来先服务算法到此结束

A a1[100];

void sort1(A *p,int N1)//到达时间排序

{

     for(int i=0;i<=N1-1;i++)

         for(int j=0;j<=i;j++)

             if(p[i].arrivetime<p[j].arrivetime)

             {

                 A temp;

                 temp=p[i];

                 p[i]=p[j];

                 p[j]=temp;

             }

}

void deal(A *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//运行阶段

{ int k;

    for(k=0;k<=N1-1;k++)

     {

         if(k==0)

            {

    p[k].starttime=p[k].arrivetime;

p[k].finishtime=p[k].arrivetime+p[k].servicetime;}//float(p[k].servicetime)/60;}

         else

           {

    p[k].starttime=p[k-1].finishtime;

    p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}//float(p[k].servicetime)/60;}

     }

for(k=0;k<=N1-1;k++)   

     {   

          p[k].zztime=p[k].finishtime-p[k].arrivetime;   

          p[k].dqzztime=p[k].zztime/p[k].servicetime;   

        

     }   

  

}

void sjff(A *p,int N1)

{    float sumzztime=0,  sumdqzztime=0,avzztime,avdqzztime,zztime,dqzztime;

        float arrivetime=0,servicetime=0,starttime=0,finishtime=0;

        sort1(p,N1);

        for(int m=0;m<N1-1;m++)

        {if(m==0)

            p[m].finishtime=p[m].arrivetime+p[m].servicetime;//float(p[m].servicetime)/60;

         else

            p[m].finishtime=p[m-1].finishtime+p[m].servicetime;//float(p[m].servicetime)/60;

 

         int i=0;

         for(int n=m+1;n<=N1-1;n++)

          {

              if(p[n].arrivetime<=p[m].finishtime)

             i++;

          }

         float min=p[m+1].servicetime;

         int next=m+1;

         for(int k=m+1;k<m+i;k++)

         {

          if(p[k+1].servicetime<min)

            {min=p[k+1].servicetime;

            next=k+1;}

           

         }

            A temp;

            temp=p[m+1];

            p[m+1]=p[next];

            p[next]=temp;

        }

       

        deal(p,arrivetime,servicetime,starttime,finishtime,N1);

 Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N1);

    for(int k=0;k<=N1-1;k++)

     {

          sumzztime=sumzztime+p[k].zztime;

        sumdqzztime=sumdqzztime+ p[k].dqzztime;

     }

    avzztime=sumzztime/N1;

     printf("\n该算法的平均周转时间为:%-.2f\t",avzztime);

     avdqzztime= sumdqzztime/N1; 

     printf("该算法的平均带权周转时间为:%-.2f\t\n",avdqzztime);

         getchar();

}//最短进程优先调度算法到这里结束

A a2[100];

void ptt(A *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,float avzztime,float avdqzztime,float lefttime,int timeprice,int N2)

{  

    float w=0;int c=0;

    float stoptime=0;

    printf("\n  请输入时间片的值：");

    cin>>timeprice;

     sort(p,N2);

float d[20],h[20];

   for(int k=0;k<=N2-1;k++)    

     { d[k]=p[k].servicetime;

    if(k==0)   

          {    

              p[k].starttime=p[k].arrivetime;   

              p[k].finishtime=p[k].arrivetime+p[k].servicetime;}   

  

         else  

          {   

              p[k].starttime=p[k-1].finishtime;   

             p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} 

          

          h[k]=p[k].starttime;

  

    p[k].lefttime=p[k].servicetime-timeprice;

   

    if(p[k].lefttime>0)

    {c=c+1;

    p[k].stoptime=p[k].starttime+timeprice;

   p[k].finishtime=p[k].stoptime;

    }

    else p[k].stoptime=p[k].finishtime;   

   

    w=p[k].stoptime;

}

  

   printf("\n   第1轮进程调度信息:\n\n");   

    printf("\t进程名  到达时间  服务时间  开始时间   停止时间    剩余时间\n");   

  

     for(k=0;k<=N2-1;k++)   

     {

          printf("\t%s\t%-.2f\t  %-.2f\t   %-.2f\t\t   %-.2f\t      %-.2f\n",p[k].name,p[k].arrivetime,

              p[k].servicetime,p[k].starttime,p[k].stoptime,p[k].lefttime);

     }

     getchar();

 int i=2;

     while(c>0)

     {

          printf("\n   第 %d 轮具体进程调度信息(时间片为 %d ):\n\n",i,timeprice);

printf("\t进程名  服务时间  开始时间  停止时间  剩余时间\n");

     

          for(k=0;k<=N2-1;k++)

          {

              if(p[k].lefttime>0)

              {

              p[k].servicetime=p[k].lefttime;

              p[k].starttime=w;

              p[k].finishtime=p[k].starttime+p[k].servicetime;

              p[k].lefttime=p[k].servicetime-timeprice;

              

              if(p[k].lefttime>0)p[k].stoptime=p[k].starttime+timeprice;  

              

               if(p[k].lefttime<=0)

              {

                   c=c-1;

                   p[k].stoptime=p[k].finishtime;

            

              }

            w=p[k].stoptime;

              printf("\t%s\t%-.2f\t   %-.2f     %-.2f       %-.2f\n",p[k].name,

              p[k].servicetime,p[k].starttime,p[k].stoptime,p[k].lefttime);

             }

     

          }

          i=i+1;

     }

     

     if(c<=0)

          printf("\n 时间片轮转调度过程结束！\n");

for(k=0;k<=N2-1;k++)   

     {  p[k].servicetime=d[k];

       p[k].starttime=h[k];

          p[k].zztime=p[k].finishtime-p[k].arrivetime;  

          p[k].dqzztime=p[k].zztime/p[k].servicetime; 

         } 

getchar();

}

void tt(A *p,int N2)

{   float sumzztime=0,  sumdqzztime=0,avzztime=0,avdqzztime=0;int timeprice=0;

     float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0,lefttime=0;

ptt(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,avzztime,avdqzztime,lefttime,timeprice,N2);

printf("\n  综合信息为：\n");

Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N2);

for(int k=0;k<=N2-1;k++)

     {

          sumzztime=sumzztime+p[k].zztime;

        sumdqzztime=sumdqzztime+ p[k].dqzztime;

     }

    avzztime=sumzztime/N2;

     printf("\n该算法的平均周转时间为:%-.2f\t",avzztime);

     avdqzztime= sumdqzztime/N2; 

     printf("该算法的平均带权周转时间为:%-.2f\t\n",avdqzztime);

     getchar();

}

int main(int argc, char *argv[])

{ int N;

char cse1;

            cout<<"\t"<<"\t\t  1.先来先服务调度算法  "<<"\t\t"<<endl;

             cout<<endl;

             cout<<"\t"<<"\t\t  2.最短进程优先调度算法"<<"\t\t"<<endl;

              cout<<endl;

              cout<<"\t"<<"\t\t  3.时间片轮转调度算法"<<"\t\t"<<endl;

            cout<<endl;

             printf("输入进程数目:");   

            scanf("%d",&N);   

            input(a,N);

            

  while(1)

    {

        cout<<"\t\t\t    请输入您的选择（1/2/3）：";

       cse1=getchar();

            switch(cse1)

            {

                case '1':

                           //int N;   

                           cout<<endl;

                           cout<<endl;

                           printf("\t\t<<---!!!@@@先来先服务调度算法@@@!!!--->>\n");   

                           cout<<endl;

                           //printf("输入进程数目:");   

                           //scanf("%d",&N);   

                           //input(a,N);   

                           FCFS(a,N);

                             break;

               

               

                case '2':     

                           //int N1;

                           cout<<endl;

                           cout<<endl;

                           printf("\t\t<<---!!!@@@最短进程优先调度算法@@@!!!--->>\n");

                           cout<<endl;

                           //printf("输入进程数目: ");

                           //scanf("%d",&N1);

                           //input(a1,N1);

                           sjff(a,N);

                            break;

                 case '3': 

                             //int N2;

                           cout<<endl;

                           cout<<endl;

                           printf("\t\t<<---!!!@@@时间片轮转调度算法@@@!!!--->>\n");

                           cout<<endl;

                           //printf("输入进程数目: ");

                          // scanf("%d",&N2);

                            //input(a2,N2);

                             tt(a,N);

                            break;

            }

    }

    system("PAUSE");

    return EXIT_SUCCESS;

}

五、运行结果:

六、实验心得：

通过做本实验，对进程或作业先来先服务、短进程优先、按时间片轮转调度算法以及进程调度的概念和算法，有了更深入的认识！初步理解了操作系统对于作业处理的基本思想！了解到算法很重要，又更加明白算法本身可以节约时间，而且不同的函数之间在调用的时候要注意很多的问题。在动手操作过程中，体会到了成功的喜悦和遇到问题自己解决的能力，对于我来说是一次提高，让自己多多的在实践中可以加深对理论的理解，也让我明白了以后应该如何更好，更高效的学习。

                                               09信息管理与信息系统（2）班

                                                何美西 12

                                                樊丽彬 15

                                                孔娜   18