მრგვალი რობინის დანიშვნა


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Facebook Google microsoft
ალგორითმი ოპერაციული სისტემები

მრგვალი რობინის დანიშვნა ძალიან ჰგავს FCFS- ს. ერთადერთი განსხვავება RR– სა და FCFS– ს დაგეგმვას შორის არის, რომ RR არის პრემენტული დაგეგმვისა ვინაიდან FCFS წარმოადგენს არაპრემიერულ დაგეგმვას. ყველა პროცესი გამოყოფილია CPU მზა რიგში ერთჯერადი ნაჭრისთვის. აქ, ა მზა რიგი წრიული რიგის მსგავსია. ყოველ ჯერზე ნაჭერი 10-დან 100 მგ-მდეა. ამ ფაქტის გამო, მას დროის ფილის დაგეგმვა ეწოდება.

RR დანიშვნის პროცედურა შემდეგია:

  1. რიგის ბოლოს ემატება ახალი პროცესი.
  2. ის პროცესი შეირჩევა რიგის წინა მხრიდან.
  3. ტაიმერი წყდება ერთჯერადი ნაჭრის შემდეგ.
  4. ერთჯერადი ნაჭრის შემდეგ, პროცესი ან სრულდება ან გადადის რიგის ბოლოს

ასე რომ, შეიძლება შემდეგი ორი შემთხვევა იყოს:

  1. პირველ შემთხვევაში, პროცესის პროცესორის ადიდებული დრო ნაკლებია ერთ ჯერზე, შემდეგ პროცესი მთლიანად შესრულდება და გამოაქვეყნებს პროცესორს და შესრულდება შემდეგი პროცესი
  2. მეორე შემთხვევაში, შეფერხება ხდება ერთჯერადად. კონტექსტური გადართვის დახმარებით, შემდეგ პროცესორი გამოყოფილი იქნება შემდეგ პროცესზე და ეს პროცესი გადავა რიგის კუდში, შემდეგ შესრულდება შემდეგი პროცესი.

მაგალითი

მრგვალი რობინის დანიშვნა

დროის მონაკვეთის ზომა იყოს 4 მმ, P1 იღებს პროცესორს პირველი 4 მმ-ისთვის. ამის შემდეგ ხდება შეფერხება და P1 მზადდება მდგომ რიგში. P2 შესრულებულია 4 მმ-ით, შემდეგ ის მზა რიგის კუდში შედის. ამის შემდეგ P3 შესრულებულია 4ms- ით, ის დასრულებულია და უშვებს CPU– ს შეწყვეტის გარეშე. ისევ P1– ის მხრივ 4 მმ. ეს პროცესი გრძელდება.

განტის დიაგრამა შემდეგი პროცესისთვის ასეთი იქნება:

მრგვალი რობინის დანიშვნა

პროცესის მოლოდინი P1 = 0 + 8 + 1 = 9ms

ახლა, პროცესის მოლოდინი P2 = 4 + 8 = 12 მლნ

P3 = 8ms პროცესის მოლოდინი

ლოდინის საერთო დრო = 29 მლნ

ლოდინის საშუალო დრო = 29/3 = 9.67 წმ

RR დანიშვნის შესრულება დამოკიდებულია დროის ნაკვეთის ზომაზე. თუ დროის მონაკვეთი ძალიან დიდია, მაშინ RR ჰგავს FCFS- ს. თუ დროის მონაკვეთი ძალიან მცირეა, მაშინ RR ჰგავს პროცესის გაზიარებას, ანუ პროცესს დიდი დრო დასჭირდება დალოდებას.

RR დაგეგმვის უპირატესობები

  1. ის მხარს უჭერს დროის გაზიარებას.
  2. RR იყენებს კვანტს.
  3. მას შეუძლია მრავალი პროცესის მართვა.
  4. თუ პროცესის გასროლის დრო უფრო მცირეა ვიდრე კვანტი, მაშინ ეს პროცესი შესრულდება პირველ კვანტში.

RR დაგეგმვის უარყოფითი მხარეები

  1. პროცესის შესრულება ნელა ხდება, თუ ადიდებული დრო უფრო დიდია, ვიდრე კვანტი.
  2. თუ კვანტი დიდია, ის მუშაობს როგორც FCFS.
  3. დიდი პროცესი უნდა დაელოდოს მცირე პროცესის დასრულებას.

განხორციელება

C პროგრამა მრგვალი რობინის დანიშვნისთვის

#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

ჯავა პროგრამა მრგვალი რობინის დანიშვნისთვის

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

სირთულის ანალიზი

დროის სირთულე

O (S) სადაც S აღნიშნავს ყველა შეყვანის პროცესის ადიდებული დროის ჯამს.

სივრცის სირთულე

O (S) სადაც S აღნიშნავს ყველა შეყვანის პროცესის ადიდებული დროის ჯამს.

Reference