Dəyirmi Robin Planlaşdırma

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook google microsoft
Alqoritm Əməliyyat SistemləriBaxılıb 98

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Dəyirmi Robin cədvəli FCFS-ə çox oxşayır. RR və FCFS planlaşdırma arasındakı yeganə fərq, RR'nin önləyici olmasıdır planlaşdırma FCFS isə qabaqcıl olmayan bir planlaşdırmadır. Hər müddət ayrılır CPU birdəfəlik dilim üçün hazır növbədə. Budur, a hazır növbə dairəvi növbəyə bənzəyir. Hər dəfə dilim 10 ilə 100 ms arasındadır. Bu həqiqətə görə vaxt diliminin planlaşdırılması adlanır.

RR Planlaşdırma proseduru aşağıdakı kimidir:

  1. Növbənin sonuna yeni bir proses əlavə olunur.
  2. The proses növbənin ön hissəsindən icra üçün seçilir.
  3. Taymer birdəfəlik dilimdən sonra kəsiləcək.
  4. Birdəfəlik dilimdən sonra proses ya tamamlanır, ya da növbənin sonuna keçir

Beləliklə, aşağıdakı iki hal ola bilər:

  1. Birinci halda, proses prosessorunun partlama müddəti bir zaman dilimindən azdır, sonra proses tamamilə icra ediləcək və prosessoru buraxacaq və növbəti proses icra ediləcək
  2. İkinci halda, kəsilmə tək bir zaman dilimində baş verir. Kontekst keçidinin köməyi ilə CPU daha sonra növbəti əməliyyata ayrılacaq və bu proses növbənin quyruğuna köçürüləcək Sonra növbəti proses yerinə yetirilir.

misal

Dəyirmi Robin PlanlaşdırmaPin

Vaxt diliminin ölçüsü 4ms olsun, P1 ilk 4ms üçün CPU alır. Bundan sonra bir fasilə meydana gəlir və P1 hazır növbənin quyruğuna qoyulur. P2 4 saniyə icra edilir, sonra hazır növbənin quyruğuna qoyulur. Bundan sonra P3 4 saniyə icra edilir, sonra tamamlanır və CPU-nu fasiləsiz buraxır. Yenidən P1-in növbəsi 4 saniyədir. Bu proses davam edir.

Aşağıdakı proses üçün Gantt diaqramı belə olacaq:

Dəyirmi Robin Planlaşdırma

Proses P1 = 0 + 8 + 1 = 9ms üçün gözləmə müddəti

İndi P2 prosesi üçün gözləmə müddəti = 4 + 8 = 12ms

Proses P3 = 8ms üçün gözləmə müddəti

Ümumi gözləmə müddəti = 29ms

Orta gözləmə müddəti = 29/3 = 9.67 ms

RR planlaşdırmasının performansı zaman diliminin ölçüsündən asılıdır. Zaman dilimi çox böyükdürsə, RR də FCFS kimidir. Zaman dilimi çox azdırsa, RR yalnız proses paylaşımı kimidir, yəni bir müddət gözləmək çox vaxt alacaq.

RR Planlaşdırmanın üstünlükləri

  1. Zaman paylaşımı dəstəkləyir.
  2. RR kvant istifadə edir.
  3. Bir çox prosesi idarə edə bilər.
  4. Prosesin partlama müddəti kvantdan kiçikdirsə, proses birinci kvantda yerinə yetirilir.

RR Planlaşdırmanın dezavantajları

  1. Burst vaxtı kvantdan böyükdürsə, prosesin icrası daha yavaş olur.
  2. Kvant böyükdürsə, FCFS kimi işləyir.
  3. Böyük proses kiçik prosesin bitməsini gözləməlidir.

Həyata keçirilməsi

Dəyirmi Robin Planlaması üçün C proqramı

#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

Dəyirmi Robin Planlaşdırma üçün Java proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (S) burada S bütün giriş proseslərinin partlama vaxtının cəmini göstərir.

Kosmik Mürəkkəblik

O (S) burada S bütün giriş proseslərinin partlama vaxtının cəmini göstərir.

arayış

Crack Sistemi Dizayn Müsahibələri
Translate »