برنامه ریزی دور رابین


سطح دشواری متوسط
اغلب در آمازون فیس بوک گوگل مایکروسافت
الگوریتم سیستم های عامل

زمانبندی Round Robin بسیار شبیه FCFS است. تنها تفاوت بین زمانبندی RR و FCFS این است که RR پیشگیرانه است زمان بندی در حالی که FCFS یک برنامه ریزی غیرقابل پیش بینی است. هر فرایند به اختصاص داده شده است پردازنده در صف آماده برای یک قطعه واحد. در اینجا ، صف آماده شبیه صف دایره ای است. هر بار برش بین 10 تا 100 میلی ثانیه است. به همین دلیل ، به آن زمانبندی برش زمان گفته می شود.

روش برنامه ریزی RR به شرح زیر است:

  1. روند جدیدی به انتهای صف اضافه می شود.
  2. La روند برای اجرا از جلوی صف انتخاب می شود.
  3. تایمر قرار است پس از برش یکبار مصرف قطع شود.
  4. پس از یک بار برش ، فرآیند یا تکمیل می شود یا به انتهای صف منتقل می شود

بنابراین ممکن است دو مورد به شرح زیر وجود داشته باشد:

  1. در حالت اول ، زمان ترکیدن پردازنده پردازش کمتر از یک برش زمان است ، سپس فرایند به طور کامل اجرا می شود و CPU را آزاد می کند و روند بعدی اجرا می شود
  2. در حالت دوم ، وقفه در یک برش زمانی واحد رخ می دهد. با کمک سوئیچ زمینه ، پردازنده به فرآیند بعدی تخصیص داده می شود و این فرآیند به دم صف منتقل می شود سپس فرآیند بعدی اجرا می شود.

مثال

برنامه ریزی دور رابین

اجازه دهید اندازه قطعه زمان 4 میلی ثانیه باشد ، P1 برای 4 میلی ثانیه پردازنده می گیرد. پس از آن ، وقفه ایجاد می شود و P1 در دم صف آماده قرار می گیرد. P2 برای 4ms اجرا می شود و سپس در دم صف آماده قرار می گیرد. پس از آن P3 برای 4ms اجرا شد ، سپس آن را تکمیل می کند و CPU را بدون وقفه آزاد می کند. باز هم نوبت P1 به 4ms می رسد. این روند ادامه دارد.

نمودار گانت برای روند زیر به شرح زیر خواهد بود:

برنامه ریزی دور رابین

زمان انتظار برای فرآیند 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 برای برنامه ریزی 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

برنامه جاوا برای برنامه ریزی 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

تحلیل پیچیدگی

پیچیدگی زمان

O (S) جایی که S مجموع زمان ترکیدگی تمام فرایندهای ورودی را نشان می دهد.

پیچیدگی فضا

O (S) جایی که S مجموع زمان ترکیدگی تمام فرایندهای ورودی را نشان می دهد.

ارجاع