Round Robin ir CPU plānošanas algoritms, kurā katram procesam cikliski tiek piešķirts fiksēts laika nips. Tā ir CPU plānošanas algoritma “Pirmais nāk pirmais pirmais piedāvājums” preventīvā versija.

gimp taisnstūra zīmējums

• Round Robin CPU algoritms parasti koncentrējas uz laika dalīšanas tehniku.
• Laika periodu, kurā procesam vai darbam ir atļauts darboties, izmantojot iepriekšēju metodi, sauc par laiku kvantu .
• Katram procesam vai darbam, kas atrodas gatavības rindā, tiek piešķirts CPU šim laika kvantam, ja procesa izpilde šajā laikā tiek pabeigta, process tiks pabeigts. beigas pretējā gadījumā process atgriezīsies uz gaidīšanas galds un gaidiet nākamo kārtu, lai pabeigtu izpildi.

Round Robin CPU plānošanas algoritma raksturojums

• Tas ir vienkāršs, viegli īstenojams un bez bada, jo visi procesi saņem taisnīgu daļu no CPU.
• Viena no visbiežāk izmantotajām metodēm CPU plānošana ir kodols.
• Tas ir preventīvs jo procesiem tiek piešķirts CPU tikai noteiktam laika posmam.
• Tā trūkums ir lielāka konteksta maiņa.

Round Robin CPU plānošanas algoritma priekšrocības

• Ir godīgi, jo katrs process saņem vienādu daļu no CPU.
• Jaunizveidotais process tiek pievienots gatavās rindas beigām.
• Apļveida plānotājs parasti izmanto laika dalīšanu, katram darbam piešķirot laika nišu vai kvantu.
• Veicot apļveida plānošanu, dažādiem darbiem tiek atvēlēts noteikts laika daudzums.
• Katrs process iegūst iespēju pārplānot pēc noteikta kvantu laika šajā plānošanā.

Round Robin CPU plānošanas algoritma trūkumi

• Ir lielāks gaidīšanas laiks un atbildes laiks.
• Ir zema caurlaidspēja.
• Ir konteksta slēdži.
• Šķiet, ka Ganta diagramma ir pārāk liela (ja kvantu laiks ir mazāks plānošanai. Piemēram, 1 ms lielai plānošanai.)
• Laikietilpīga plānošana maziem kvantiem.

Piemēri, kā parādīt darbību Round Robin Plānošanas algoritms

1. piemērs: Apsveriet šo tabulu par četru procesu ierašanās laiku un sērijveida laiku P1, P2, P3 un P4 un dots Laika kvants = 2

Round Robin CPU plānošanas algoritms darbosies, pamatojoties uz tālāk norādītajām darbībām.

brīdī = 0,

• Izpilde sākas ar procesu P1, kura sērijveida laiks ir 5.
• Šeit katrs process tiek izpildīts 2 milisekundes ( Laika kvantu periods ). P2 un P3 joprojām ir gaidīšanas rindā.

Laikā = 2,

• Procesi P1 un P3 nonāk gatavības rindā, un P2 sāk izpildīt TQ periodā

Laikā = 4,

• Process P4 ierodas gatavā rinda ,
• Pēc tam P3 izpilda TQ periodā.

Laikā = 6,

• Process P3 pabeidz tā izpildi
• Sāk izpildīt procesu P1 TQ periods, kā tas ir nākamais b.

Laikā = 8,

• Process P4 sāk izpildīt, tas netiks izpildīts Laiks Kvantu periods jo tā pārraidīšanas laiks = 1
• Tādējādi tas darbosies tikai 1 ms.

Laikā = 9,

• Process P4 pabeidz tā izpildi
• Sāk izpildīt procesu P2 TQ periodā, kā tas ir nākamais gatavā rinda

Laiks = 11,

• Process P2 pabeidz tā izpildi.
• Process P1 sāk izpildīt, tas tiks izpildīts tikai 1 ms

Laiks = 12,

• Process P1 pabeidz tā izpildi.
• Procesu kopējā izpilde būs tāda, kā parādīts zemāk:

Ganta diagramma būs šādi:

Ganta diagramma Round Robin plānošanas algoritmam

Kā aprēķināt zemāk norādītos laikus Round Robin, izmantojot programmu?

• Pabeigšanas laiks: Laiks, kurā process pabeidz tā izpildi.
• Apgriešanas laiks: Laiks Atšķirība starp pabeigšanas laiku un ierašanās laiku. Apgriešanas laiks = pabeigšanas laiks — ierašanās laiks
• Gaidīšanas laiks (W.T): Laiks Atšķirība starp apgriešanās laiku un sērijveida laiku.
  Gaidīšanas laiks = aprites laiks – sērijveida uzņemšanas laiks

Tagad aprēķināsim vidējo gaidīšanas laiks un apgriezties laiks:

Tagad

• Vidējais apgriešanās laiks = (12 + 10 + 4 + 5)/4 = 31/4 = 7,7
• Vidējais gaidīšanas laiks = (7 + 6 + 2 + 4)/4 = 19/4 = 4,7

2. piemērs: Apsveriet šādu tabulu par ierašanās laiku un sērijveida laiku trim procesiem P1, P2 un P3 un doto Laika kvants = 2

Līdzīgi, Ganta diagramma šim piemēram:

Ganta diagramma, piemēram, 2

Tagad aprēķināsim vidējo gaidīšanas laiks un apgriezties laiks:

Kopējais apgriešanas laiks = 59 ms
Tātad, Vidējais apgrozības laiks = 59/3 = 19,667 ms

Un kopējais gaidīšanas laiks = 36 ms
Tātad, Vidējais gaidīšanas laiks = 36/3 = 12,00 ms

Programma Round Robin plānošanai ar ierašanās laiku kā 0 visiem procesiem

Darbības, lai atrastu visu procesu gaidīšanas laikus

• Izveidojiet masīvu rem_bt[] lai sekotu līdzi atlikušajam procesu pārrāvuma laikam. Šis masīvs sākotnēji ir bt[] kopija (sērijveida masīvs).
• Izveidojiet citu masīvu wt[] lai saglabātu procesu gaidīšanas laikus. Inicializējiet šo masīvu kā 0.
• Inicializācijas laiks: t = 0
• Turpiniet šķērsot visus procesus, kamēr tie nav pabeigti. Veiciet tālāk norādītās darbības es procesu, ja tas vēl nav izdarīts.
  • Ja rem_bt[i]> kvants
    • t = t + kvants
    • rem_bt[i] -= summa;
  • Else // Pēdējais cikls šim procesam
    • t = t + rem_bt[i];
    • wt[i] = t – bt[i]
    • rem_bt[i] = 0; // Šis process ir beidzies

Kad mums ir gaidīšanas laiks, mēs varam aprēķināt procesa apgriezienu laiku tat[i] kā gaidīšanas un eksplozijas laiku summu, t.i., wt[i] + bt[i].
Zemāk ir aprakstīta iepriekš minēto darbību īstenošana.

C++

>

>

Java

tostring metode java

atšķirība starp lauvu un tīģeri

>

>

Python3

>

>

C#

> 
iemet java izņēmumu apstrādi
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > >// JavaScript program for implementation of RR scheduling> >// Function to find the waiting time for all> >// processes> >const findWaitingTime = (processes, n, bt, wt, quantum) =>{> >// Make a copy of burst times bt[] to store remaining> >// burst times.> >let rem_bt =>new> Array(n).fill(0);> >for> (let i = 0; i   rem_bt[i] = bt[i];  let t = 0; // Current time  // Keep traversing processes in round robin manner  // until all of them are not done.  while (1) {  let done = true;  // Traverse all processes one by one repeatedly  for (let i = 0; i   // If burst time of a process is greater than 0  // then only need to process further  if (rem_bt[i]>0) {darīts = nepatiess; // Ir gaidošs process if (rem_bt[i]> quantum) { // Palielināt t vērtību t.i. parāda // cik daudz laika process ir apstrādāts t += kvants;  // Samazināt pašreizējā procesa burst_time // par kvantu rem_bt[i] -= kvants;  } // Ja sērijas laiks ir mazāks vai vienāds ar // kvantu. Pēdējais cikls šim procesam else { // Palieliniet t vērtību, t.i., parāda // cik ilgu laiku process ir apstrādāts t = t + rem_bt[i];  // Gaidīšanas laiks ir pašreizējais laiks mīnus laiks // ko izmanto šis process wt[i] = t - bt[i];  // Kad process tiek pilnībā izpildīts, // padarīt tā atlikušo sērijveida laiku = 0 rem_bt[i] = 0;  } } } // Ja visi procesi ir veikti if (done == true) break;  } } // Apgriešanās laika aprēķināšanas funkcija const findTurnAroundTime = (procesi, n, bt, wt, tat) => { // aprites laika aprēķināšana, pievienojot // bt[i] + wt[i] for (lai i = 0 i tat[i] = bt[i] + wt[i] } // Funkcija vidējā laika aprēķināšanai const findavgTime = (procesi, n, bt, kvants) => { let wt = new Masīvs(n). fill(0), tat = new Array(n).fill(0) let total_wt = 0, total_tat = 0 // Funkcija visu procesu gaidīšanas laika noteikšanai findWaitingTime(proceses, n, bt, wt, quantum); // Funkcija, lai atrastu apgriezienu laiku visiem procesiem findTurnAroundTime(processes, n, bt, wt, tat // Parādīt procesus kopā ar visām detaļām document.write(`Procesi Burst laiks Gaidīšanas laiks `); Aprēķināt kopējo gaidīšanas laiku un kopējo apgriezienu // apgriešanās laiku (lai i = 0; i total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; document.write(`${i + 1} ${ bt[i]} ${wt[i]} ${tat[i]} `); = ${total_tat / n}`);  } // Draivera kods // process id's process = [1, 2, 3];  lai n = procesi.garums;  // Visu procesu sērijveida laiks let burst_time = [10, 5, 8];  // Laika kvants let quantum = 2;  findavgTime(proceses, n, burst_time, kvants);  // Šo kodu sniedz rakeshsahni>
 
 
 
 
    
 
>
 
    
 
>
 
  Izvade  
 
PN BT WT TAT 1 10 13 23 2 5 10 15 3 8 13 21 Average waiting time = 12 Average turn around time = 19.6667>
 
    Programma Round Robin plānošanai ar ierašanās laiku kā nulle, atšķirīgi un vienādi ierašanās laiki    
 
C++
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 #include> #include> using> namespace> std;> struct> Process {> >int> AT, BT, ST[20], WT, FT, TAT, pos;> };> int> quant;> int> main() {> >int> n, i, j;> >// Taking Input> >cout <<>'Enter the no. of processes: '>;> >cin>> n;> >Process p[n];> >cout <<>'Enter the quantum: '> << endl;> >cin>> kvants;> >cout <<>'Enter the process numbers: '> << endl;> >for> (i = 0; i   cin>> p[i].pos;  cout<< 'Enter the Arrival time of processes: ' << endl;  for (i = 0; i   cin>> p[i].AT;  cout<< 'Enter the Burst time of processes: ' << endl;  for (i = 0; i   cin>> p[i].BT;  // Mainīgo deklarēšana int c = n, s[n][20];  peldēšanas laiks = 0, mini = INT_MAX, b[n], a[n];  // Burst un ierašanās laika masīvu inicializācija int index = -1;  ja (i = 0; i b[i] = p[i].BT; a[i] = p[i].AT; ja (j = 0; j)<20; j++) {  s[i][j] = -1;  }  }  int tot_wt, tot_tat;  tot_wt = 0;  tot_tat = 0;  bool flag = false;  while (c != 0) {  mini = INT_MAX;  flag = false;  for (i = 0; i   float p = time + 0.1;  if (a[i] <= p && mini>a[i] && b[i]> 0) { indekss = i;  mini = a[i];  karogs = patiess;  } } // ja pie =1, tad cilpa tiek izvadīta, tāpēc iestatiet karogu uz false if (!flag) { laiks++;  Turpināt;  } // sākuma laika aprēķināšana j = 0;  while (s[indekss][j] != -1) { j++;  } if (s[indekss][j] == -1) { s[indekss][j] = laiks;  p[indekss].ST[j] = laiks;  } ja (b[indekss]<= quant) {  time += b[index];  b[index] = 0;  } else {  time += quant;  b[index] -= quant;  }  if (b[index]>0) {a[indekss] = laiks + 0,1;  } // aprēķinot ierašanās, sērijveida, beigu laikus if (b[indekss] == 0) { c--;  p[indekss].FT = laiks;  p[indekss].WT = p[indekss].FT — p[indekss].AT — p[indekss].BT;  tot_wt += p[indekss].WT;  p[indekss].TAT = p[indekss].BT + p[indekss].WT;  tot_tat += p[indekss].TAT;  } } // while cilpas beigas // Drukāšanas izvades apjoms<< 'Process number ';  cout << 'Arrival time ';  cout << 'Burst time ';  cout << '	Start time';  j = 0;  while (j != 10) {  j += 1;  cout << ' ';  }  cout << '		Final time';  cout << '	Wait Time ';  cout << '	TurnAround Time' << endl;  for (i = 0; i   cout << p[i].pos << '		';  cout << p[i].AT << '		';  cout << p[i].BT << '	';  j = 0;  int v = 0;  while (s[i][j] != -1) {  cout << p[i].ST[j] << ' ';  j++;  v += 3;  }  while (v != 40) {  cout << ' ';  v += 1;  }  cout << p[i].FT << '		';  cout << p[i].WT << '		';  cout << p[i].TAT << endl;  }  // Calculating average wait time and turnaround time  double avg_wt, avg_tat;  avg_wt = tot_wt / static_cast(n);  avg_tat = tot_tat / static_cast(n);  // Drukāšanas vidējais gaidīšanas laiks un apgrozījuma laiks<< 'The average wait time is: ' << avg_wt << endl;  cout << 'The average TurnAround time is: ' << avg_tat << endl;  return 0; }>
 
 
 
 
    
 
>
 
    
 
>
 
 
C
    
 
     
  
 
    
 
     
     
    
ko tas nozīmē xd
 
 
 
 
 
 #include> #include> #include> struct> P{> int> AT,BT,ST[20],WT,FT,TAT,pos;> };> int> quant;> int> main(){> int> n,i,j;> // Taking Input> printf>(>'Enter the no. of processes :'>);> scanf>(>'%d'>,&n);> struct> P p[n];> > printf>(>'Enter the quantum 
'>);> scanf>(>'%d'>,&quant);> printf>(>'Enter the process numbers 
'>);> for>(i=0;i scanf('%d',&(p[i].pos));   printf('Enter the Arrival time of processes 
'); for(i=0;i scanf('%d',&(p[i].AT));   printf('Enter the Burst time of processes 
'); for(i=0;i scanf('%d',&(p[i].BT));   // Declaring variables int c=n,s[n][20]; float time=0,mini=INT_MAX,b[n],a[n]; // Initializing burst and arrival time arrays int index=-1; for(i=0;i  b[i]=p[i].BT;  a[i]=p[i].AT;  for(j=0;j<20;j++){  s[i][j]=-1;  } } int tot_wt,tot_tat; tot_wt=0; tot_tat=0; bool flag=false; while(c!=0){ mini=INT_MAX; flag=false; for(i=0;i  float p=time+0.1;  if(a[i]a[i] && b[i]>0){ indekss=i;  mini=a[i];  karogs=true;    } } // ja pie =1, tad cilpa tiek izvadīta, tāpēc iestatiet karogu uz false if(!flag){ time++;  Turpināt; } //aprēķinot sākuma laiku j=0; while(s[indekss][j]!=-1){ j++; } if(s[indekss][j]==-1){ s[indekss][j]=laiks; p[indekss].ST[j]=laiks; } if(b[indekss]<=quant){ time+=b[index]; b[index]=0; } else{ time+=quant; b[index]-=quant; } if(b[index]>0){a[indekss]=laiks+0,1; } // ierašanās, sērijveida, beigu laiku aprēķināšana if(b[index]==0){ c--; p[indekss].FT=laiks; p[indekss].WT=p[indekss].FT-p[indekss].AT-p[indekss].BT; tot_wt+=p[indekss].WT; p[indekss].TAT=p[indekss].BT+p[indekss].WT; tot_tat+=p[indekss].TAT; } } // while cikla beigas // Drukāšanas izvade printf('Procesa numurs '); printf('Irašanās laiks '); printf('Sērija laiks '); printf('	Sākuma laiks'); j=0; while(j!=10){ j+=1; printf(''); } printf('		Pēdējais laiks'); printf('	Gaidīšanas laiks '); printf('	TurnAround Time 
'); for(i=0;i printf('%d 		',p[i].pos); printf('%d 		',p[i].AT); printf ('%d 	',p[i].BT j=0 while(s[i][j]!=-1){ printf('%d '); ,p[i].ST[j] j++ } while(v!=40){ printf('%d 		; ',p[i].FT); printf('%d 		',p[i].WT); } //Vidējā gaidīšanas laika un aprites laika aprēķināšana double avg_wt,avg_tat=tot_wt/(float)n //Drukāšanas vidējais gaidīšanas laiks laiks ir: %lf
',avg_wt('Vidējais aprites laiks ir: %lf
',avg_tat }>'>);
 
 
 
 
    
 
> 
    
 Enter the number of processes : 4 Enter the time quanta : 2 Enter the process numbers : 1 2 3 4 Enter the arrival time of the processes : 0 1 2 3 Enter the burst time of the processes : 5 4 2 1 Program No. Arrival Time Burst Time Wait Time TurnAround Time 1 0 5 7 12 2 1 4 6 10 3 2 2 2 4 4 3 1 5 6 Average wait time : 5 Average Turn Around Time : 8>
 
    Programma apļa plānošanai ar dažādiem ierašanās laikiem visiem procesiem    
 
Lai iegūtu detalizētu Preemptive Round Robin algoritma ieviešanu ar dažādiem ierašanās laikiem visiem procesiem, lūdzu, skatiet: Programma Round Robin plānošanai ar dažādiem ierašanās laikiem .
 
Secinājums
 
Visbeidzot, Round Robin CPU plānošana ir godīgs un preventīvs algoritms, kas katram procesam piešķir fiksētu laika kvantu, nodrošinot vienādu CPU piekļuvi. To ir vienkārši ieviest, taču tas var novest pie lielākas konteksta maiņas pieskaitāmās izmaksas. Lai gan tas veicina godīgumu un novērš badu, tas var izraisīt ilgāku gaidīšanas laiku un samazināt caurlaidspēju atkarībā no laika kvantitatīvām. Efektīva programmas ieviešana ļauj aprēķināt galvenos rādītājus, piemēram, pabeigšanas laiku, izpildes laiku un gaidīšanas laiku, palīdzot veiktspējas novērtēšanā un optimizācijā.