Կլոր Ռոբինի ժամանակացույցը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon facebook Google Microsoft
Ալգորիթմ Օպերացիոն համակարգեր

Round Robin- ի ժամանակացույցը շատ նման է FCFS- ին: RR- ի և FCFS- ի պլանավորման միակ տարբերությունն այն է, որ RR- ը կանխարգելիչ է ներով մինչդեռ FCFS- ը ոչ կանխարգելիչ ժամանակացույց է: Յուրաքանչյուր գործընթաց հատկացված է CPU պատրաստ հերթում ՝ մեկ անգամվա կտորով: Այստեղ, ա պատրաստ հերթ նման է շրջանաձեւ հերթին: Ամեն անգամ հատվածը 10-ից 100 ms է: Այս փաստի պատճառով այն կոչվում է ժամանակի հատվածների ժամանակացույց:

RR պլանավորման կարգը հետևյալն է.

  1. Հերթի ավարտին ավելացվում է նոր գործընթաց:
  2. The պրոցես ընտրվում է հերթի դիմացից կատարման համար:
  3. Timամաչափը կարգավորված է ընդհատել միանվագ կտորից հետո:
  4. Մեկ անգամ կտորից հետո գործընթացը կամ ավարտվում է, կամ տեղափոխվում է հերթի վերջ

Այսպիսով, կարող է լինել երկու դեպք, ինչպես հետևյալը.

  1. Առաջին դեպքում, պրոցեսորի պրոցեսորի ժամանակի պայթյունի ժամանակը մեկ անգամից պակաս է, ապա գործընթացն ամբողջությամբ կկատարվի և կթողարկի պրոցեսոր, և կկատարվի հաջորդ գործընթացը:
  2. Երկրորդ դեպքում ընդհատումը տեղի է ունենում մեկ ժամանակի կտրվածքով: Համատեքստի անջատիչի միջոցով պրոցեսորը հետո կհատկացվի հաջորդ գործընթացին, և այս գործընթացը կտեղափոխվի հերթի պոչ: Այնուհետև կկատարվի հաջորդ գործընթացը:

Օրինակ

Կլոր Ռոբինի ժամանակացույցը

Թող ժամանակի հատվածի չափը լինի 4ms, P1- ը տանում է պրոցեսոր առաջին 4ms- ի համար: Դրանից հետո տեղի է ունենում ընդհատում, և P1- ը դրվում է պատրաստ հերթի պոչի մեջ: P2- ը կատարվում է 4ms- ի համար, ապա այն դրվում է պատրաստ հերթի պոչում: Դրանից հետո P3- ը կատարվում է 4ms- ի համար, այնուհետև այն ավարտվում է և առանց ընդհատումների թողարկում է պրոցեսորը: Կրկին P1- ի հերթը գալիս է 4ms- ի: Այս գործընթացը շարունակվում է:

Հետևյալ գործընթացի Գանտի աղյուսակը այսպիսին կլինի.

Կլոր Ռոբինի ժամանակացույցը

P1 = 0 + 8 + 1 = 9ms գործընթացի սպասման ժամանակ

Այժմ, սպասման ժամանակ P2 = 4 + 8 = 12ms գործընթացի համար

P3 = 8ms գործընթացի սպասման ժամանակը

Ընդհանուր սպասման ժամանակ = 29 մմ

Սպասման միջին ժամանակը = 29/3 = 9.67 մմ

RR պլանավորման կատարումը կախված է ժամանակի հատվածի չափից: Եթե ​​ժամանակի հատվածը չափազանց մեծ է, ապա RR- ը նման է FCFS- ին: Եթե ​​ժամանակի հատվածը շատ փոքր է, ապա RR- ը նման է գործընթացի բաշխմանը, այսինքն `գործընթացին սպասելը շատ ժամանակ կպահանջի:

RR պլանավորման առավելությունները

  1. Այն աջակցում է ժամանակի բաշխմանը:
  2. RR- ն օգտագործում է քվանտ:
  3. Այն կարող է կարգավորել բազմաթիվ գործընթացներ:
  4. Եթե ​​գործընթացի պայթյունի ժամանակը փոքր է քվանտից, ապա գործընթացը կատարվում է առաջին քվանտում:

RR պլանավորման թերությունները

  1. Գործընթացների կատարումն ավելի դանդաղ է, եթե պայթյունի ժամանակը մեծ է, քան քվանտը:
  2. Եթե ​​քվանտը մեծ է, այն աշխատում է որպես FCFS:
  3. Մեծ գործընթացը պետք է սպասի փոքր գործընթացի ավարտին:

Իրականացման

C ծրագիր Round Robin- ի ժամանակացույցի համար

#include<stdio.h>
#include<conio.h>
int main()
{
    int n,i,qt,count=0,temp,sq=0,bt[10],wt[10],tat[10],rem_bt[10];
    //n signifies number of process
    //i is for using loops
    //qt denotes Quantum Time
    //count denotes when one process is completed
    //temp and sq are temproray variables
    //bt[10] denotes burst time
    //wt[10] denotes waiting time
    //tat[10] denotes turnaround time
    //rem_bt[10] denotes remaining burst time
    float awt=0,atat=0;
    //awt represents average waiting time
    //atat represents average turnaround time
    printf("Enter number of process (upto 10) = ");
    scanf("%d",&n);
    printf("Enter burst time of process\n");
    for (i=0;i<n;i++)
    {
        printf("P%d = ",i+1);
        scanf("%d",&bt[i]);
        rem_bt[i]=bt[i];
    }
    printf("Enter quantum time ");
    scanf("%d",&qt);
    while(1)
    {
        for (i=0,count=0;i<n;i++)
        {
            temp=qt;
            if(rem_bt[i]==0)
            {
                count++;
                continue;
            }
            if(rem_bt[i]>qt)//changing the value of remaining burst time
                rem_bt[i]=rem_bt[i]-qt;
            else
                if(rem_bt[i]>=0)//if process is exhausted then setting remaining burst time tozero
                {
                    temp=rem_bt[i];
                    rem_bt[i]=0;
                }
                sq=sq+temp; //calculating turnaround time
                tat[i]=sq;
        }
        if(n==count)//breaking the loop when all process are exhausted
            break;
    }
    printf("\nProcess\tBurst Time\tTurnaround Time\tWaiting Time\n");
    for(i=0;i<n;i++)
    {
        wt[i]=tat[i]-bt[i];
        awt=awt+wt[i];
        atat=atat+tat[i];
        printf("\n%d\t%d\t\t%d\t\t%d",i+1,bt[i],tat[i],wt[i]);
    }
    awt=awt/n;
    atat=atat/n;
    printf("\nAverage waiting Time = %f\n",awt);
    printf("Average turnaround time = %f",atat);
    return 0;
}
Enter number of process (upto 10) = 3
Enter burst time of process
P1 = 21
P2 = 5
P3 = 4
Enter quantum time 4
Process	Burst Time	Turnaround Time	Waiting Time

1	20		29		9
2	5		17		12
3	4		12		8
Average waiting Time = 9.666667
Average turnaround time = 19.333334

Java ծրագիր Round Robin պլանավորման համար

import java.util.Scanner;

class main
{
  public static void main(String args[])
  {
    int n,i,qt,count=0,temp,sq=0,bt[],wt[],tat[],rem_bt[];
    float awt=0,atat=0;

    bt = new int[10];
    wt = new int[10];
    tat = new int[10];
    rem_bt = new int[10];

    Scanner s=new Scanner(System.in);

    System.out.print("Enter number of process (upto 10) = ");
    n = s.nextInt();

    System.out.print("Enter burst time of process\n");
    for (i=0;i<n;i++)
    {
      System.out.print("P"+i+" = ");
      bt[i] = s.nextInt();
      rem_bt[i] = bt[i];
    }
    System.out.print("Enter quantum time = ");
    qt = s.nextInt();

    while(true)
    {
      for (i=0,count=0;i<n;i++)
      {
        temp = qt;

        if(rem_bt[i] == 0)
        {
          count++;
          continue;
        }

        if(rem_bt[i]>qt)
          rem_bt[i]= rem_bt[i] - qt;
        else
          if(rem_bt[i]>=0)
          {
            temp = rem_bt[i];
            rem_bt[i] = 0;
          }
          sq = sq + temp;
          tat[i] = sq;
      }
      if(n == count)
      break;
    }
    System.out.print("\nProcess\tBurst Time\tTurnaround Time\tWaiting Time\n");
    for(i=0;i<n;i++)
        {
            wt[i]=tat[i]-bt[i];
            awt=awt+wt[i];
            atat=atat+tat[i];
            System.out.print("\n  "+(i+1)+"\t  "+bt[i]+"\t\t   "+tat[i]+"\t\t   "+wt[i]);
        }
        awt=awt/n;
        atat=atat/n;
        System.out.println("\nAverage waiting Time = "+awt);
        System.out.println("Average turnaround time = "+atat);
  }
}
Enter number of process (upto 10) = 3 
Enter burst time of process 
P1 = 29 
P2 = 51 
P3 = 42 
Enter quantum time 6
Process	Burst Time	Turnaround Time	Waiting Time

  1	  29		   77		   48
  2	  51		   122		   71
  3	  42		   113		   71
Average waiting Time = 63.333332
Average turnaround time = 104.0

Բարդության վերլուծություն

Timeամանակի բարդություն

O (S) որտեղ S- ը նշանակում է մուտքային բոլոր գործընթացների պոռթկման ժամանակի հանրագումարը:

Տիեզերական բարդություն

O (S) որտեղ S- ը նշանակում է մուտքային բոլոր գործընթացների պոռթկման ժամանակի հանրագումարը:

Մանրամասն