常用的作业调度算法(操作系统)

梦里梦外; 2022-12-23 09:40 348阅读 0赞

  1. 先来先服务
    先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。FCFS算法简单易行，是一种非抢占式策略。
    2.短进程优先调度
    最短进程优先算法是一种非剥夺式算法，总是选取预计作业时间最短的作业优先运行；最短剩余时间优先算法是非剥夺式的，但可以改造成剥夺式的调度算法，称抢占式最短作业优先算法。
    至于二者的平均周转时间，比如有四个进程P1，P2，P3，P4，分别在0,1,2,3时刻到达，所需时间分别为7,5,3,8；那么其平均周转时间为（（15-0）+（9-1）+（5-2）+（23-15））/4=8.5；
    公式：
    完成时间 = 开始时间 + 需要运行时间
    周转时间 = 完成时间 - 到达时间
    带权周转时间 = 周转时间 / 需要运行时间
    3.时间片轮转算法
    时间片轮转法（Round-Robin，RR）主要用于分时系统中的进程调度。为了实现轮转调度，系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，进程调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。时间片是一个小的时间单位，通常为10~100ms数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，把它放入就绪队列的末尾；然后，把CPU分给就绪队列的队首进程，同样也让它运行一个时间片，如此往复。
    以下为上面三个算法的代码：(先来先服务和最短进程调度都为进程随机获得)

    include

    include

    include

    include

    //进程控制块(PCB)
    struct PCB
    {
    char name;
    int arrivetime;
    int servetime;
    int finishtime;
    float roundtime;
    float daiquantime;
    int sc; //sign completion标志是否完成
    int st1; //剩余服务时间
    };
    struct PCB a[50];
    struct PCB b[50];
    char jczt[] = { “运行”, “就绪” };//表示没有字符串的大小限制
    //打印统计信息
    void tjxx(int n)
    {
    float averoundtime = 0.0f;
    float avedaiquantime = 0.0f;
    printf(“按任意键查看统计信息”);
    getchar(); getchar();
    printf(“\n\n进程名称\t到达时间\t服务时间\t完成时间\t周转时间\t带权周转时间”);
    for (int j = 0; j < n; j++)
    {
    printf(“\n %c\t\t%4d\t\t%4d\t\t%d\t\t%4.f\t\t %.2f\n”, a[j].name, a[j].arrivetime, a[j].servetime, a[j].finishtime, a[j].roundtime, a[j].daiquantime);
    averoundtime += a[j].roundtime;
    avedaiquantime += a[j].daiquantime;
    }
    printf(“\n平均周转时间:%.2f”, averoundtime / n);
    printf(“\n\n平均带权周转时间:%.2f\n”, avedaiquantime / n);
    }

    //先来先服务
    void fcfs(int n)
    {
    int time = 0; //定义当前时刻
    int processnum = 0; //定义当前进程指向
    struct PCB t; //定义一个空的结构体节点
    int processztsy = 0; //定义进程状态索引
    while (1)
    { printf(“当前时刻：%2d\n”, time);

    1. //排序
    2. for (int i = 1; i < n; i++)
    3. {  for (int j = 0; j < n - i; j++)
    4.     {  if (a[j].arrivetime > a[j+1].arrivetime)//先到先运行
    5.         {  t = a[j];
    6.           a[j] = a[j+1];
    7.           a[j+1] = t;
    8.         }
    9.         if (a[j].arrivetime == a[j + 1].arrivetime)//进程同时到
    10.         {  if (a[j].servetime > a[j + 1].servetime)//比较服务时间,将运行时间短的放在优先级高的位置
    11.             {  t = a[j];
    12.               a[j] = a[j + 1];
    13.               a[j + 1] = t;
    14.             }
    15.         }
    16.     }
    17. }
    18. for (int k = 0; k< n; k++)
    19. {  if (time == a[k].arrivetime && a[k].arrivetime != 0)
    20.     {  if (k >= 1 && time >= a[k - 1].finishtime || k == 0)
    21.         processztsy = 0;
    22.       else
    23.         processztsy = 1;
    24.       printf("\t\t进程 %c 到达\t进程状态\n", a[k].name);
    25.       printf("\n\t\t\t\t %s\n\n", jczt[processztsy]);
    26.       if (processnum >= 1)
    27.         { 
    28.             a[k].finishtime = a[k-1].finishtime + a[k].servetime;
    29.             a[k].roundtime =(float)(a[k].finishtime - a[k].arrivetime);
    30.             a[k].daiquantime = a[k].roundtime / a[k].servetime;
    31.         }
    32.         if (processnum == 0)
    33.         { 
    34.             a[k].finishtime = a[k].arrivetime + a[k].servetime;
    35.             a[k].roundtime =(float)(a[k].finishtime-a[k].arrivetime);
    36.             a[k].daiquantime = a[k].roundtime / a[k].servetime;
    37.             printf("\t\t\t进程 %c 开始\n\n", a[processnum].name);
    38.             processnum++;
    39.         }
    40.     }
    41.     if (time == a[k].finishtime && a[k].finishtime != 0)
    42.        printf("\t\t\t进程 %c 完成\n\n", a[k].name);
    43.     if ((k >= 1 && time >= a[k].arrivetime && time == a[k - 1].finishtime && a[k].arrivetime != 0))
    44.        printf("\t\t\t进程 %c 开始\n\n", a[k].name);
    45. }
    46. if (time > a[n-1].finishtime && a[n-1].finishtime != 0)
    47. { 
    48.     printf("\t\t\t所有进程已进程已加载完毕！\n\n");
    49.     break;
    50. }
    51. time++;
    52. Sleep(1000);

    }
    tjxx(n);
    }

    //短进程有先算法
    void spf(int n)
    {
    struct PCB t;
    int time = 0;//定义当前时刻
    int jcnum = 0;
    int jcztsy = 0;
    bool ztgb = false;
    //排序
    for (int i = 1; i < n; i++)
    { for (int j = 0; j < n-i; j++)

    1. {  if (a[j].arrivetime > a[j+1].arrivetime)//先到达的优先级高
    2.     {     t=a[j];
    3.         a[j] = a[j+1];
    4.         a[j+1] = t;
    5.     }
    6. }

    }
    while (1)
    { printf(“当前时刻：%d\n”, time);

    1. //遍历数组，注意同时达到的进程，所以采用for循环遍历

    for (int k = 0; k< n; k++)

    1. {         //是否有进程的到达时间等于当前时刻
    2.     if (time == a[k].arrivetime && a[k].arrivetime != 0)
    3.     {     //判断到达进程因该处于什么状态
    4.         if (k >= 1 && time >= a[k - 1].finishtime || k == 0)
    5.            jcztsy = 0;
    6.         else
    7.            jcztsy = 1;
    8.         printf("\t\t进程 %c 到达\t进程状态\n\n\n\n", a[k].name);
    9.     }
    10. }
    11. if (jcnum == 0)
    12. {         //遍历数组
    13.     for (int i = jcnum; i < n; i++)
    14.     {     //把当前到达的进程筛选出来
    15.         if (time >= a[i].arrivetime)
    16.         {     //从挑选出来的进程中选取服务时间最短的一个
    17.             if (a[i].servetime < a[jcnum].servetime)
    18.             {      t = a[jcnum];
    19.                 a[jcnum] = a[i];
    20.                 a[i] = t;
    21.             }
    22.             ztgb = true;
    23.         }
    24.     }
    25.     if (ztgb == true)
    26.     {     printf("\t\t\t进程 %c 开始\n\n\n\n", a[jcnum].name);
    27.         a[jcnum].finishtime = a[jcnum].arrivetime + a[jcnum].servetime;
    28.         a[jcnum].roundtime =(float)(a[jcnum].finishtime - a[jcnum].arrivetime);
    29.         a[jcnum].daiquantime = a[jcnum].roundtime / a[jcnum].servetime;
    30.         ztgb = false;
    31.         jcnum++;
    32.     }
    33. }
    34. if (time == a[jcnum - 1].finishtime && a[jcnum - 1].finishtime != 0)
    35. {     printf("\t\t\t进程 %c 完成\n\n\n\n", a[jcnum - 1].name);
    36.     //遍历数组
    37.     for (int i = jcnum; i < n; i++)
    38.     {     //把当前到达的进程筛选出来
    39.         if (time >= a[i].arrivetime)
    40.         {     //从挑选出来的进程中选取服务时间最短的一个
    41.             if (a[i].servetime < a[jcnum].servetime)
    42.             {     t = a[jcnum];
    43.                 a[jcnum] = a[i];
    44.                 a[i] = t;
    45.             }
    46.             ztgb = true;
    47.         }
    48.     }
    49.     if (ztgb == true || jcnum == n-1)
    50.     { 
    51.         printf("\t\t\t进程 %c 开始\n\n\n\n", a[jcnum].name);
    52.         a[jcnum].finishtime = a[jcnum - 1].finishtime + a[jcnum].servetime;
    53.         a[jcnum].roundtime =(float)(a[jcnum].finishtime - a[jcnum].arrivetime);
    54.         a[jcnum].daiquantime = a[jcnum].roundtime / a[jcnum].servetime;
    55.         ztgb = false;
    56.         jcnum++;
    57.     }
    58. }
    59. if (time > a[n - 1].finishtime && a[n - 1].finishtime != 0)
    60. { 
    61.     printf("\t\t\t所有进程已加载完毕！ \n\n\n\n");
    62.     break;
    63. }
    64. time++;
    65. Sleep(1000);

    }
    tjxx(n);
    }

    //时间片轮转算法
    void rr(int n)
    { struct PCB t;

    1.      int i,j,T;
    2.      printf("\n请输入时间片：\n");
    3.      scanf("%d",&T);
    4.      for(i=0;i<n;i++)      //收集进程信息
    5.      { 
    6.                a[i].sc=0;
    7.                printf("\n%d:\n请依次输入进程的信息\n请输入进程名:",i+1);
    8.                scanf("%s",&a[i].name);
    9.                printf("请输入到达时间:");
    10.                scanf("%d",&a[i].arrivetime);
    11.                printf("请输入服务时间:");
    12.                scanf("%d",&a[i].servetime);
    13.                a[i].st1=a[i].servetime;
    14.      }
    15.       for(i=0;i<n;i++)
    16.          for(j=i+1;j<n;j++)   //按照各进程到达时间升序，对进程排序 注意：稳定的排序
    17.          { 
    18.                if(a[j].arrivetime<a[i].arrivetime)
    19.                { 
    20.                        t=a[j];
    21.                        a[j]=a[i];
    22.                        a[i]=t;
    23.                }
    24.          }
    25.      for(i=0;i<n;i++)
    26.         printf("***排序后的***%12c%15d%11d%11d：\n",a[i].name,a[i].arrivetime,a[i].servetime,a[i].st1);
    27.      int time1=a[0].arrivetime;      //当前时间的初值
    28.      int flag=1;
    29.      int sum=0;                                              //记录完成的进程数
    30.      int z=1;   //记录第几次调度进程
    31.      printf("\n第几次调度进程 运行的进程名 开始运行时间 运行时间 剩余服务时间 结束时间\n");
    32.      while(sum<n)
    33.      { 
    34.       flag=0;           //标志就绪队列中是否还有进程
    35.       for(i=0;i<n;i++)    //时间片轮转法执行各进程
    36.       {  if(a[i].sc==1)continue;  //已完成的进程
    37.         else
    38.         {   if(a[i].st1<=T && time1>=a[i].arrivetime)//未完成的进程但是还需服务的时间少于等于一个时间片
    39.              {  flag=1;
    40.                time1=time1+a[i].st1;
    41.                a[i].sc=1;
    42.                a[i].finishtime=time1;
    43.                printf("%8d%12c%15d%11d%11d%11d\n",z++,a[i].name,time1-a[i].st1,a[i].st1,0,time1);
    44.                a[i].st1=0;
    45.               }
    46.            else if( a[i].st1>T && time1>=a[i].arrivetime)//未完成的进程但其还需服务时间至少大于一个时间片
    47.               {  flag=1;
    48.                 time1=time1+T;
    49.                 a[i].st1-=T;
    50.                 printf("%8d%12c%15d%11d%11d%11d\n",z++,a[i].name,time1-T,T,a[i].st1,time1);
    51.                }
    52.            if( a[i].sc==1)sum++;     //一个进程执行完就+1
    53.         }
    54.      }
    55.      if(flag==0 && sum<n)   // 还有没执行的进程，且没进入就就绪队列
    56.         for(i=0;i<n;i++)
    57.           if( a[i].sc==0) {   time1=a[ i].arrivetime;   break;}
    58. }
    59.   for(i=0;i<n;i++)
    60.   {  a[i].roundtime=(float)(a[i].finishtime - a[i].arrivetime);
    61.     a[i].daiquantime=a[i].roundtime / a[i].servetime;
    62.   }
    63. Sleep(1000);
    64. tjxx(n);

    }

    //信息输入
    int info()
    { int n = 0;
    srand(time(NULL)); //初始化随机函数
    printf(“请输入需要的进程数：”);
    scanf(“%d”, &n);
    printf(“\n”);
    for (int i = 0; i < n; i++)
    { printf(“进程 %d\t名称:”, i+1);

    1. scanf("%s", &a[i].name);
    2. a[i].arrivetime = (rand() % 5 + 1);//随机获取进程运行到达时间
    3. a[i].servetime = (rand() % 5 + 1);//随机获取进程运行服务时间

    }
    system(“cls”);
    return n;
    }

    int info1()
    { int n;
    printf(“请输入需要的进程数：”);
    scanf(“%d”, &n);
    printf(“\n”);
    return n;
    }

    int main()
    { 

    1. int b=1,k,m;
    2. while(b)
    3. { 
    4.     system("cls");
    5.     printf("*************************************************\n");
    6.     printf("** **\n");
    7.     printf("** 进程调度算法 **\n");
    8.     printf("** 程序清单 **\n");
    9.     printf("** **\n");
    10.     printf("** 1.先来先服务算法 **\n");
    11.     printf("** 2.短进程优先算法 **\n");
    12.     printf("** 3.时间片轮转算法 **\n");
    13.     printf("** 0.退出程序 **\n");
    14.     printf("** **\n");
    15.     printf("*************************************************\n");
    16.     printf("请选择：");
    17.     scanf("%d",&k);
    18.     switch(k)
    19.     { 
    20.         case 1:fcfs(info());break;
    21.         case 2:spf(info());break;
    22.         case 3:rr(info1()); break;
    23.         case 0:b=0;break;
    24.         default:printf("\n*****请输入正确的选择*****\n");
    25.     }
    26.     if(b!=0)
    27.         printf("\n");
    28.         system("pause");
    29. }
    30. printf("\n**********谢谢您使用**********\n");

    }

发表评论

表情：
评论列表 （有 0 条评论，348人围观）

还没有评论，来说两句吧...

相关阅读

    相关 作业调度算法

    作业调度算法 > 作业调度算法： 先来先服务（FCFS）调度算法，即按作业到达的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。 短作业优先 (S

    红太狼红太狼/ 0 赞/ 457 阅读

    相关 操作系统作业 - 进程调度

    第三章习题 一、问答题 1. 高级调度与低级调度的主要任务是什么? 为什么要引入中级调度? 高级调度主要任务是：根据某种算法，把外存上处于后备队列中的那些作业调入内存，也

    心已赠人心已赠人/ 0 赞/ 445 阅读

    相关 作业调度算法

    作业（程序+数据+作业说明书）比程序概念更为广泛，在批处理系统中，以作业为单位从外存调入内存 > FCFS先来先服务算法 既可以用于进程调度又可以用于作业调度。从后备作业队

    逃离我推掉我的手逃离我推掉我的手/ 0 赞/ 473 阅读