Round Robin ist ein CPU-Planungsalgorithmus, bei dem jedem Prozess zyklisch ein fester Zeitschlitz zugewiesen wird. Es handelt sich um die präventive Version des CPU-Planungsalgorithmus „Wer zuerst kommt, mahlt zuerst“.
wie die Schule erfunden wurde
- Der Round-Robin-CPU-Algorithmus konzentriert sich im Allgemeinen auf die Time-Sharing-Technik.
- Der Zeitraum, für den ein Prozess oder Job präventiv ausgeführt werden darf, wird als Zeit bezeichnet Quantum .
- Jedem in der Bereitschaftswarteschlange vorhandenen Prozess oder Job wird die CPU für dieses Zeitquantum zugewiesen. Wenn die Ausführung des Prozesses in dieser Zeit abgeschlossen ist, wird der Prozess dies tun Ende andernfalls geht der Prozess zurück zum Wartetisch und warten Sie auf die nächste Runde, um die Ausführung abzuschließen.
Eigenschaften des Round-Robin-CPU-Planungsalgorithmus
- Es ist einfach, leicht zu implementieren und hungrig, da alle Prozesse einen angemessenen Anteil an CPU erhalten.
- Eine der am häufigsten verwendeten Techniken in CPU-Planung ist ein Kern.
- Es ist präventiv da Prozessen höchstens für einen festen Zeitraum CPU zugewiesen wird.
- Der Nachteil ist der höhere Aufwand für den Kontextwechsel.
Vorteile des Round-Robin-CPU-Planungsalgorithmus
- Es besteht Gerechtigkeit, da jeder Prozess den gleichen Anteil an der CPU erhält.
- Der neu erstellte Prozess wird am Ende der Bereitschaftswarteschlange hinzugefügt.
- Ein Round-Robin-Scheduler verwendet im Allgemeinen Time-Sharing und weist jedem Job ein Zeitfenster oder Quantum zu.
- Bei der Durchführung einer Round-Robin-Planung wird verschiedenen Jobs ein bestimmtes Zeitquantum zugewiesen.
- Jeder Prozess erhält in dieser Planung die Möglichkeit, nach einer bestimmten Quantenzeit neu zu planen.
Nachteile des Round-Robin-CPU-Planungsalgorithmus
- Es gibt längere Wartezeiten und Reaktionszeiten.
- Es liegt ein geringer Durchsatz vor.
- Es gibt Kontextwechsel.
- Das Gantt-Diagramm scheint zu groß zu sein (wenn die Quantenzeit für die Planung geringer ist. Beispiel: 1 ms für große Planung.)
- Zeitaufwändige Planung für kleine Mengen.
Beispiele zur Veranschaulichung der Funktionsweise Round Robin Planungsalgorithmus
Beispiel 1: Betrachten Sie die folgende Tabelle mit Ankunftszeiten und Burst-Zeiten für vier Prozesse P1, P2, P3 und P4 und gegeben Zeitquantum = 2
| Verfahren | Burst-Zeit | Ankunftszeit |
|---|---|---|
| P1 | 5 ms | 0 ms |
| P2 | 4 ms | 1 ms |
| P3 | 2 ms | 2 ms |
| P4 | 1 ms | 4 ms |
Der Round-Robin-CPU-Planungsalgorithmus basiert auf den unten aufgeführten Schritten:
Zum Zeitpunkt = 0,
- Die Ausführung beginnt mit Prozess P1, der die Burst-Zeit 5 hat.
- Hier wird jeder Prozess 2 Millisekunden lang ausgeführt ( Zeitquantenperiode ). P2 und P3 stehen noch in der Warteschlange.
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 0-2ms | P1 | 0ms | P2, P3 | P1 | 2ms | 5ms | 3 ms |
Zum Zeitpunkt = 2,
- Die Prozesse P1 und P3 gelangen in die Bereitschaftswarteschlange und P2 beginnt mit der Ausführung TQ Zeitraum
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 2-4ms | P1 | 0ms | P3, P1 | P2 | 0ms | 3 ms | 3 ms |
| P2 | 1ms | 2ms | 4 ms | 2ms |
Zum Zeitpunkt = 4,
- Der Prozess P4 gelangt in die bereit Warteschlange ,
- Dann führt P3 aus für TQ Zeitraum.
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 4-6ms | P1 | 0ms | P1, P4, P2 | P3 | 0ms | 3 ms | 3 ms |
| P2 | 1ms | 0ms | 2ms | 2ms | |||
| P3 | 2ms | 2ms | 2ms | 0ms |
Zum Zeitpunkt = 6,
- Prozess P3 schließt seine Ausführung ab
- Prozess P1 beginnt mit der Ausführung für TQ Zeitraum, da es als nächstes in der b.
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 6-8ms | P1 | 0ms | P4, P2 | P1 | 2ms | 3 ms | 1ms |
| P2 | 1ms | 0ms | 2ms | 2ms |
Zum Zeitpunkt = 8,
- Prozess P4 beginnt mit der Ausführung, wird aber nicht ausgeführt Zeit Quantenperiode da es eine Burst-Zeit = 1 hat
- Daher dauert die Ausführung nur 1 ms.
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 8-9ms | P1 | 0ms | P2, P1 | P4 | 0ms | 3 ms | 1ms |
| P2 | 1ms | 0ms | 2ms | 2ms | |||
| P4 | 4 ms | 1ms | 1ms | 0ms |
Zum Zeitpunkt = 9,
- Prozess P4 schließt seine Ausführung ab
- Prozess P2 beginnt mit der Ausführung für TQ Zeitraum als nächstes in der bereit Warteschlange
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 9–11 ms | P1 | 0ms | P1 | P2 | 0ms | 3 ms | 1ms |
| P2 | 1ms | 2ms | 2ms | 0ms |
Zum Zeitpunkt = 11,
- Prozess P2 schließt seine Ausführung ab.
- Prozess P1 beginnt mit der Ausführung, er wird nur 1 ms lang ausgeführt
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 11-12 ms | P1 | 0ms | P1 | 1ms | 1ms | 0ms |
Zum Zeitpunkt = 12,
- Prozess P1 schließt seine Ausführung ab.
- Die Gesamtausführung der Prozesse sieht wie folgt aus:
| Zeitinstanz | Verfahren | Ankunftszeit | Bereit-Warteschlange | Laufende Warteschlange | Ausführungszeit | Anfängliche Burst-Zeit | Verbleibender Burst Zeit |
|---|---|---|---|---|---|---|---|
| 0-2ms | P1 | 0ms | P2, P3 | P1 | 2ms | 5ms | 3 ms |
| 2-4ms | P1 | 0ms | P3, P1 | P2 | 0ms | 3 ms | 3 ms |
| P2 | 1ms | 2ms | 4 ms | 2ms | |||
| 4-6ms | P1 | 0ms | P1, P4, P2 | P3 | 0ms | 3 ms | 3 ms |
| P2 | 1ms | 0ms | 2ms | 2ms | |||
| P3 | 2ms | 2ms | 2ms | 0ms | |||
| 6-8ms | P1 | 0ms | P4, P2 | P1 | 2ms | 3 ms | 1ms |
| P2 | 1ms | 0ms | 2ms | 2ms | |||
| 8-9ms | P1 | 0ms | P2, P1 | P4 | 0ms | 3 ms | 1ms |
| P2 | 1ms | 0ms | 2ms | 2ms | |||
| P4 | 4 ms | 1ms | 1ms | 0ms | |||
| 9–11 ms | P1 | 0ms | P1 | P2 | 0ms | 3 ms | 1ms |
| P2 | 1ms | 2ms | 2ms | 0ms | |||
| 11-12 ms | P1 | 0ms | P1 | 1ms | 1ms | 0ms |
Gantt-Diagramm wird wie folgt aussehen:
Gantt-Diagramm für den Round-Robin-Planungsalgorithmus
Wie berechnet man die folgenden Zeiten in Round Robin mit einem Programm?
- Vervollständigungszeit: Zeitpunkt, zu dem der Prozess seine Ausführung abschließt.
- Seitenwechsel: Zeitdifferenz zwischen Fertigstellungszeit und Ankunftszeit. Bearbeitungszeit = Fertigstellungszeit – Ankunftszeit
- Wartezeit (W.T): Zeitunterschied zwischen Durchlaufzeit und Burst-Zeit.
Wartezeit = Durchlaufzeit – Burst-Zeit
Berechnen wir nun den Durchschnitt Wartezeit und Umdrehen Zeit:
| Prozesse | BEI | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| P1 | 0 | 5 | 12 | 12-0 = 12 | 12-5 = 7 |
| P2 | 1 | 4 | elf | 11-1 = 10 | 10-4 = 6 |
| P3 | 2 | 2 | 6 | 6-2 = 4 | 4-2 = 2 |
| P4 | 4 | 1 | 9 | 9-4 = 5 | 5-1 = 4 |
Jetzt,
- Durchschnittliche Bearbeitungszeit = (12 + 10 + 4 + 5)/4 = 31/4 = 7,7
- Durchschnittliche Wartezeit = (7 + 6 + 2 + 4)/4 = 19/4 = 4,7
Beispiel 2: Betrachten Sie die folgende Tabelle mit Ankunftszeiten und Burst-Zeiten für die drei Prozesse P1, P2 und P3 Zeitquantum = 2
| Verfahren | Burst-Zeit | Ankunftszeit |
|---|---|---|
| P1 | 10 ms | 0 ms |
| P2 | 5 ms | 0 ms |
| P3 | 8 ms | 0 ms |
Ähnlich, Gantt-Diagramm für dieses Beispiel:
Gantt-Diagramm zum Beispiel 2
Berechnen wir nun den Durchschnitt Wartezeit und Umdrehen Zeit:
| Prozesse | BEI | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| P1 | 0 | 10 | 23 | 23-0 = 23 | 23-10 = 13 |
| P2 | 0 | 5 | fünfzehn | 15-0 = 15 | 15-5 = 10 |
| P3 | 0 | 8 | einundzwanzig | 21-0 = 21 | 21-8 = 13 |
Gesamtdurchlaufzeit = 59 ms
Also, Durchschnittliche Bearbeitungszeit = 59/3 = 19,667 msUnd Gesamtwartezeit = 36 ms
Also, Durchschnittliche Wartezeit = 36/3 = 12,00 ms
Programm für Round-Robin-Scheduling mit Ankunftszeit als 0 für alle Prozesse
Schritte zum Ermitteln der Wartezeiten aller Prozesse
- Erstellen Sie ein Array rem_bt[] um die verbleibende Burst-Zeit von Prozessen im Auge zu behalten. Dieses Array ist zunächst eine Kopie von bt[] (Burst Times Array).
- Erstellen Sie ein weiteres Array Gewicht[] um Wartezeiten von Prozessen zu speichern. Initialisieren Sie dieses Array als 0.
- Zeit initialisieren: t = 0
- Durchlaufen Sie weiterhin alle Prozesse, solange sie noch nicht abgeschlossen sind. Gehen Sie wie folgt vor ich Vorgang, falls dieser noch nicht abgeschlossen ist.
- Wenn rem_bt[i]> Quantum
- t = t + Quantum
- rem_bt[i] -= Betrag;
- Else // Letzter Zyklus für diesen Prozess
- t = t + rem_bt[i];
- wt[i] = t – bt[i]
- rem_bt[i] = 0; // Dieser Prozess ist beendet
Sobald wir Wartezeiten haben, können wir die Durchlaufzeit tat[i] eines Prozesses als Summe der Warte- und Burst-Zeiten berechnen, d. h. wt[i] + bt[i].
Nachfolgend finden Sie die Umsetzung der oben genannten Schritte.
C++
// C++ program for implementation of RR scheduling> #include> using> namespace> std;> // Function to find the waiting time for all> // processes> void> findWaitingTime(>int> processes[],>int> n,> >int> bt[],>int> wt[],>int> quantum)> {> >// Make a copy of burst times bt[] to store remaining> >// burst times.> >int> rem_bt[n];> >for> (>int> i = 0 ; i rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round robin manner // until all of them are not done. while (1) { bool done = true; // Traverse all processes one by one repeatedly for (int i = 0 ; i { // If burst time of a process is greater than 0 // then only need to process further if (rem_bt[i]>0) { erledigt = falsch; // Es gibt einen ausstehenden Prozess if (rem_bt[i]> Quantum) { // Erhöhen Sie den Wert von t, d. h. zeigt // an, wie viel Zeit ein Prozess verarbeitet wurde t += Quantum; // Burst_time des aktuellen Prozesses // um Quantum verringern rem_bt[i] -= Quantum; } // Wenn die Burst-Zeit kleiner oder gleich // Quantum ist. Letzter Zyklus für diesen Prozess else { // Erhöhen Sie den Wert von t, d. h. zeigt // an, wie lange ein Prozess verarbeitet wurde t = t + rem_bt[i]; // Wartezeit ist aktuelle Zeit minus Zeit //, die von diesem Prozess verwendet wird wt[i] = t - bt[i]; // Sobald der Prozess vollständig ausgeführt wird // seine verbleibende Burst-Zeit auf 0 setzen rem_bt[i] = 0; } } } // Wenn alle Prozesse abgeschlossen sind if (done == true) break; } } // Funktion zur Berechnung der Bearbeitungszeit void findTurnAroundTime(int processing[], int n, int bt[], int wt[], int tat[]) { // Berechnung der Bearbeitungszeit durch Addition // bt[i] + wt[i] for (int i = 0; i tat[i] = bt[i] + wt[i]; } // Funktion zur Berechnung der durchschnittlichen Zeit void findavgTime(int processing[], int n, int bt[ ], int Quantum) { int wt[n], tat[n], total_wt = 0, total_tat = 0; // Funktion zum Ermitteln der Wartezeit aller Prozesse findWaitingTime(processes, n, bt, wt, Quantum); Funktion zum Ermitteln der Bearbeitungszeit für alle Prozesse findTurnAroundTime(processes, n, bt, wt, tat); // Prozesse zusammen mit allen Details anzeigen cout<< 'PN '<< ' BT ' << ' WT ' << ' TAT
'; // Calculate total waiting time and total turn // around time for (int i=0; i { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; cout << ' ' << i+1 << ' ' << bt[i] <<' ' << wt[i] <<' ' << tat[i] < } cout << 'Average waiting time = ' << (float)total_wt / (float)n; cout << '
Average turn around time = ' << (float)total_tat / (float)n; } // Driver code int main() { // process id's int processes[] = { 1, 2, 3}; int n = sizeof processes / sizeof processes[0]; // Burst time of all processes int burst_time[] = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); return 0; }> |
Javascript am nächsten
>
>
Java
// Java program for implementation of RR scheduling> public> class> GFG> {> >// Method to find the waiting time for all> >// processes> >static> void> findWaitingTime(>int> processes[],>int> n,> >int> bt[],>int> wt[],>int> quantum)> >{> >// Make a copy of burst times bt[] to store remaining> >// burst times.> >int> rem_bt[] =>new> int>[n];> >for> (>int> i =>0> ; i rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round robin manner // until all of them are not done. while(true) { boolean done = true; // Traverse all processes one by one repeatedly for (int i = 0 ; i { // If burst time of a process is greater than 0 // then only need to process further if (rem_bt[i]>0) { erledigt = falsch; // Es gibt einen ausstehenden Prozess if (rem_bt[i]> Quantum) { // Erhöhen Sie den Wert von t, d. h. zeigt // an, wie viel Zeit ein Prozess verarbeitet wurde t += Quantum; // Burst_time des aktuellen Prozesses // um Quantum verringern rem_bt[i] -= Quantum; } // Wenn die Burst-Zeit kleiner oder gleich // Quantum ist. Letzter Zyklus für diesen Prozess else { // Erhöhen Sie den Wert von t, d. h. zeigt // an, wie lange ein Prozess verarbeitet wurde t = t + rem_bt[i]; // Wartezeit ist aktuelle Zeit minus Zeit //, die von diesem Prozess verwendet wird wt[i] = t - bt[i]; // Sobald der Prozess vollständig ausgeführt wird // seine verbleibende Burst-Zeit auf 0 setzen rem_bt[i] = 0; } } } // Wenn alle Prozesse abgeschlossen sind if (done == true) break; } } // Methode zur Berechnung der Bearbeitungszeit static void findTurnAroundTime(int processing[], int n, int bt[], int wt[], int tat[]) { // Berechnung der Bearbeitungszeit durch Addition // bt[i ] + wt[i] for (int i = 0; i tat[i] = bt[i] + wt[i]; } // Methode zur Berechnung der durchschnittlichen Zeit static void findavgTime(int processing[], int n, int bt[], int Quantum) { int wt[] = new int[n], tat[] = new int total_wt = 0, total_tat = 0; // Funktion zum Ermitteln der Wartezeit aller Prozesse findWaitingTime( Prozesse, n, bt, wt, Quantum); // Funktion zum Ermitteln der Bearbeitungszeit für alle Prozesse findTurnAroundTime(processes, n, bt, wt, tat); // Prozesse zusammen mit allen Details anzeigen System.out.println( 'PN ' + ' B ' + ' WT ' + ' TAT'); // Gesamtwartezeit und Gesamtumdrehungszeit berechnen für (int i=0; i { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; System.out.println(' ' + (i+1) + ' ' + bt[i] +' ' + wt[i] +' ' + tat[i]); } System.out.println('Durchschnittliche Wartezeit = ' + (float)total_wt / (float)n); System.out.println('Durchschnittliche Bearbeitungszeit = ' + (float)total_tat / (float)n); } // Treibermethode public static void main(String[] args) { // Prozess-ID's int processing[] = { 1, 2, 3}; int n = Prozesse.Länge; // Burst-Zeit aller Prozesse int Burst_time[] = {10, 5, 8}; // Zeitquantum int Quantum = 2; findavgTime(processes, n, Burst_time, Quantum); } }> |
>
>
Python3
# Python3 program for implementation of> # RR scheduling> # Function to find the waiting time> # for all processes> def> findWaitingTime(processes, n, bt,> >wt, quantum):> >rem_bt>=> [>0>]>*> n> ># Copy the burst time into rt[]> >for> i>in> range>(n):> >rem_bt[i]>=> bt[i]> >t>=> 0> # Current time> ># Keep traversing processes in round> ># robin manner until all of them are> ># not done.> >while>(>1>):> >done>=> True> ># Traverse all processes one by> ># one repeatedly> >for> i>in> range>(n):> > ># If burst time of a process is greater> ># than 0 then only need to process further> >if> (rem_bt[i]>>0>) :> >done>=> False> # There is a pending process> > >if> (rem_bt[i]>Quantum) :> > ># Increase the value of t i.e. shows> ># how much time a process has been processed> >t>+>=> quantum> ># Decrease the burst_time of current> ># process by quantum> >rem_bt[i]>->=> quantum> > ># If burst time is smaller than or equal> ># to quantum. Last cycle for this process> >else>:> > ># Increase the value of t i.e. shows> ># how much time a process has been processed> >t>=> t>+> rem_bt[i]> ># Waiting time is current time minus> ># time used by this process> >wt[i]>=> t>-> bt[i]> ># As the process gets fully executed> ># make its remaining burst time = 0> >rem_bt[i]>=> 0> > ># If all processes are done> >if> (done>=>=> True>):> >break> > # Function to calculate turn around time> def> findTurnAroundTime(processes, n, bt, wt, tat):> > ># Calculating turnaround time> >for> i>in> range>(n):> >tat[i]>=> bt[i]>+> wt[i]> # Function to calculate average waiting> # and turn-around times.> def> findavgTime(processes, n, bt, quantum):> >wt>=> [>0>]>*> n> >tat>=> [>0>]>*> n> ># Function to find waiting time> ># of all processes> >findWaitingTime(processes, n, bt,> >wt, quantum)> ># Function to find turn around time> ># for all processes> >findTurnAroundTime(processes, n, bt,> >wt, tat)> ># Display processes along with all details> >print>(>'Processes Burst Time Waiting'>,> >'Time Turn-Around Time'>)> >total_wt>=> 0> >total_tat>=> 0> >for> i>in> range>(n):> >total_wt>=> total_wt>+> wt[i]> >total_tat>=> total_tat>+> tat[i]> >print>(>' '>, i>+> 1>,>' '>, bt[i],> >' '>, wt[i],>' '>, tat[i])> >print>(>'
Average waiting time = %.5f '>%>(total_wt>/>n) )> >print>(>'Average turn around time = %.5f '>%> (total_tat>/> n))> > # Driver code> if> __name__>=>=>'__main__'>:> > ># Process id's> >proc>=> [>1>,>2>,>3>]> >n>=> 3> ># Burst time of all processes> >burst_time>=> [>10>,>5>,>8>]> ># Time quantum> >quantum>=> 2>;> >findavgTime(proc, n, burst_time, quantum)> # This code is contributed by> # Shubham Singh(SHUBHAMSINGH10)> |
>
>
C#
String-zu-Int-Konverter
// C# program for implementation of RR> // scheduling> using> System;> public> class> GFG {> > >// Method to find the waiting time> >// for all processes> >static> void> findWaitingTime(>int> []processes,> >int> n,>int> []bt,>int> []wt,>int> quantum)> >{> > >// Make a copy of burst times bt[] to> >// store remaining burst times.> >int> []rem_bt =>new> int>[n];> > >for> (>int> i = 0 ; i rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round // robin manner until all of them are // not done. while(true) { bool done = true; // Traverse all processes one by // one repeatedly for (int i = 0 ; i { // If burst time of a process // is greater than 0 then only // need to process further if (rem_bt[i]>0) { // Es ist ein ausstehender Prozess abgeschlossen = false; if (rem_bt[i]> Quantum) { // Erhöhen Sie den Wert von t, d. h. // zeigt an, wie viel Zeit ein Prozess // verarbeitet wurde t += Quantum; // Burst_time // des aktuellen Prozesses um Quantum verringern rem_bt[i] -= Quantum; } // Wenn die Burst-Zeit kleiner als // oder gleich Quantum ist. Letzter Zyklus // für diesen Prozess else { // Erhöhen Sie den Wert von t, d. h. // zeigt an, wie viel Zeit ein Prozess // verarbeitet wurde t = t + rem_bt[i]; // Wartezeit ist aktuell // Zeit minus Zeit, die von // diesem Prozess verwendet wird wt[i] = t - bt[i]; // Wenn der Prozess vollständig // ausgeführt wird, wird die verbleibende // Burst-Zeit = 0 rem_bt[i] = 0; } } } // Wenn alle Prozesse abgeschlossen sind if (done == true) break; } } // Methode zur Berechnung der Bearbeitungszeit static void findTurnAroundTime(int []processes, int n, int []bt, int []wt, int []tat) { // Berechnung der Bearbeitungszeit durch Addition // bt[i ] + wt[i] for (int i = 0; i tat[i] = bt[i] + wt[i]; } // Methode zur Berechnung der durchschnittlichen Zeit static void findavgTime(int []processes, int n, int []bt, int Quantum) { int []wt = new int[n]; int []tat = new int[n]; // Funktion zum Ermitteln der Wartezeit von // all Prozesse findWaitingTime(Prozesse, n, bt, wt, Quantum); // Funktion zum Ermitteln der Bearbeitungszeit // für alle Prozesse findTurnAroundTime(Prozesse, n, bt, wt, tat); // Prozesse zusammen mit // allen Details anzeigen Console.WriteLine('Processes ' + ' Burst time ' + ' Waiting time ' + ' Turn around time'); // Gesamtwartezeit und Gesamtumdrehungszeit berechnen für (int i = 0; i { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; Console.WriteLine(' ' + (i+1) + ' ' + bt[i ] + ' ' + wt[i] +' ' + tat[i]); } Console.WriteLine('Durchschnittliche Wartezeit = ' + (float)total_wt / (float)n); Console.Write('Durchschnittliche Bearbeitungszeit = ' + (float)total_tat / (float)n); } // Treibermethode public static void Main() { // Prozess-ID's int []processes = { 1, 2, 3}; int n = Prozesse.Länge; // Burst-Zeit aller Prozesse int []burst_time = {10, 5, 8}; // Zeitquantum int Quantum = 2; findavgTime(processes, n, Burst_time, Quantum); } } // Dieser Code wurde von Nitin Mittal beigesteuert.> |
>
>
Javascript
Java-String ist leer
> >// 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) { erledigt = falsch; // Es gibt einen ausstehenden Prozess if (rem_bt[i]> Quantum) { // Erhöhen Sie den Wert von t, d. h. zeigt // an, wie viel Zeit ein Prozess verarbeitet wurde t += Quantum; // Burst_time des aktuellen Prozesses // um Quantum verringern rem_bt[i] -= Quantum; } // Wenn die Burst-Zeit kleiner oder gleich // Quantum ist. Letzter Zyklus für diesen Prozess else { // Erhöhen Sie den Wert von t, d. h. zeigt // an, wie lange ein Prozess verarbeitet wurde t = t + rem_bt[i]; // Wartezeit ist aktuelle Zeit minus Zeit //, die von diesem Prozess verwendet wird wt[i] = t - bt[i]; // Sobald der Prozess vollständig ausgeführt wird // seine verbleibende Burst-Zeit auf 0 setzen rem_bt[i] = 0; } } } // Wenn alle Prozesse abgeschlossen sind if (done == true) break; } } // Funktion zur Berechnung der Durchlaufzeit const findTurnAroundTime = (processes, n, bt, wt, tat) => { // Berechnung der Durchlaufzeit durch Addition // bt[i] + wt[i] for (let i = 0; i tat[i] = bt[i] + wt[i]; } // Funktion zur Berechnung der Durchschnittszeit const findavgTime = (processes, n, bt, Quantum) => { let wt = new Array(n). fill(0), tat = new Array(n).fill(0); let total_wt = 0, total_tat = 0; // Funktion zum Ermitteln der Wartezeit aller Prozesse findWaitingTime(processes, n, bt, wt, Quantum); // Funktion zum Ermitteln der Bearbeitungszeit für alle Prozesse findTurnAroundTime(processes, n, bt, wt, tat); // Prozesse zusammen mit allen Details anzeigen document.write(`Prozesse Burst Time Wartezeit `); Berechnen Sie die Gesamtwartezeit und die Gesamtdrehzeit // für (let 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]} `); } document.write(`Durchschnittliche Wartezeit = ${total_wt / n}`); = ${total_tat / n}`); } // Treibercode // Prozess-ID's processing = [1, 2, 3]; sei n = Prozesse.Länge; // Burst-Zeit aller Prozesse let Burst_time = [10, 5, 8]; // Zeitquantum letquantum = 2; findavgTime(processes, n, Burst_time, Quantum); // Dieser Code wurde von rakeshsahni>'> beigesteuert |
>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>
Programm für Round Robin Scheduling mit Ankunftszeit als Null, unterschiedlichen und gleichen Ankunftszeiten
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>> quant;> >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; // Variablen deklarieren int c = n, s[n][20]; float time = 0, mini = INT_MAX, b[n], a[n]; // Burst- und Ankunftszeit-Arrays initialisieren int index = -1; für (i = 0; i b[i] = p[i].BT; a[i] = p[i].AT; für (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) { index = i; mini = a[i]; Flag = wahr; } } // wenn bei =1 dann wird die Schleife beendet, daher Flag auf false setzen if (!flag) { time++; weitermachen; } // Berechnung der Startzeit j = 0; while (s[index][j] != -1) { j++; } if (s[index][j] == -1) { s[index][j] = time; p[index].ST[j] = Zeit; } if (b[index]<= quant) { time += b[index]; b[index] = 0; } else { time += quant; b[index] -= quant; } if (b[index]>0) { a[index] = Zeit + 0,1; } // Berechnung von Ankunft, Burst, Endzeiten if (b[index] == 0) { c--; p[index].FT = Zeit; p[index].WT = p[index].FT - p[index].AT - p[index].BT; tot_wt += p[index].WT; p[index].TAT = p[index].BT + p[index].WT; tot_tat += p[index].TAT; } } // Ende der While-Schleife // Ausgabe cout drucken<< '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 |
Alpha-Beta-Schnitt
>
>
C
#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){ index=i; mini=a[i]; flag=true; } } // wenn bei =1 dann wird die Schleife beendet, daher Flag auf false setzen if(!flag){ time++; weitermachen; } //Berechnung der Startzeit j=0; while(s[index][j]!=-1){ j++; } if(s[index][j]==-1){ s[index][j]=time; p[index].ST[j]=Zeit; } if(b[index]<=quant){ time+=b[index]; b[index]=0; } else{ time+=quant; b[index]-=quant; } if(b[index]>0){ a[index]=time+0.1; } // Berechnung der Ankunfts-, Burst- und Endzeiten if(b[index]==0){ c--; p[index].FT=time; p[index].WT=p[index].FT-p[index].AT-p[index].BT; tot_wt+=p[index].WT; p[index].TAT=p[index].BT+p[index].WT; tot_tat+=p[index].TAT; } } // Ende der While-Schleife // Ausgabe drucken printf('Prozessnummer '); printf('Ankunftszeit '); printf('Burst-Zeit '); printf(' Startzeit'); j=0; while(j!=10){ j+=1; printf(' '); } printf(' Endzeit'); printf(' Wartezeit '); printf(' Bearbeitungszeit
'); for(i=0;i printf('%d ',p[i].pos); printf('%d ',p[i].AT); printf ('%d ',p[i].BT); j=0; int v=0; while(s[i][j]!=-1){ printf('%d ' ,p[i].ST[j]); j++; v+=3; } while(v!=40){ printf(' '); ',p[i].FT); printf('%d ',p[i].WT); printf('%d
',p[i].TAT) ; //Berechnung der durchschnittlichen Wartezeit und Bearbeitungszeit double avg_wt=tot_wt/(float)n; //Durchschnittliche Wartezeit und Bearbeitungszeit drucken Zeit ist: %lf
',avg_wt); printf('Die durchschnittliche Bearbeitungszeit ist: %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>
Programm zur Round-Robin-Planung mit unterschiedlichen Ankunftszeiten für alle Prozesse
Eine detaillierte Implementierung des Preemptive Round Robin-Algorithmus mit unterschiedlichen Ankunftszeiten für alle Prozesse finden Sie unter: Programm für Round Robin Scheduling mit unterschiedlichen Ankunftszeiten .
Abschluss
Zusammenfassend lässt sich sagen, dass Round-Robin-CPU-Scheduling ein fairer und präventiver Algorithmus ist, der jedem Prozess eine feste Zeitmenge zuweist und so den gleichen CPU-Zugriff gewährleistet. Es ist einfach zu implementieren, kann jedoch zu einem höheren Aufwand für den Kontextwechsel führen. Dies fördert zwar die Gerechtigkeit und beugt Hungersnöten vor, kann jedoch je nach Zeitmenge zu längeren Wartezeiten und einem geringeren Durchsatz führen. Eine effektive Programmimplementierung ermöglicht die Berechnung wichtiger Kennzahlen wie Abschlusszeit, Bearbeitungszeit und Wartezeit und hilft so bei der Leistungsbewertung und -optimierung.