Brechen einer Krawatte in Round Robin Scheduling

Question

Ich bin verwirrt mit einem Grundkonzept der Round Robin CPU-Prozess-Scheduling, wo der kurzfristige Scheduler fügt den Prozess in die Warteschlange bereit.

Wenn es im System 3 Prozesse P0, P1 und P2 gibt und ein Kontextwechsel für P1 bei 5 Sekunden und gleichzeitig P2 ANKOMMT (d. H. Bei 5 Sekunden) auftritt. In welchem ​​Fall wird der Prozess zuerst in die Bereitschaftswarteschlange eingefügt, P1 oder P2? Die durchschnittliche Gesamtwartezeit darf sich in beiden Fällen nicht unterscheiden, die individuelle Wartezeit eines Prozesses ist jedoch unterschiedlich.

Answer 1

Es ist nicht möglich, dass P1 und P2 gleichzeitig zur Bereit-Warteschlange hinzugefügt werden. Es muss eine Reihenfolge geben, in der sie hinzugefügt werden (entweder wird P1 vor P2 hinzugefügt, oder P2 wird vor P1 hinzugefügt), da Sie Zugriffe auf die Bereit-Warteschlange in synchronisieren müssen, wenn Sie der Bereit-Warteschlange einen Prozess hinzufügen möchten Um zu vermeiden, die Warteschlange zu korrumpieren. Auf einem einzelnen Kernsystem können Sie dies tun, indem Sie Interrupts deaktivieren, während Sie die Warteschlange ändern. In einem Multicore-System können Sie dies je nach Implementierung des Kernels über eine Kombination von Sperren und Interrupts durchführen.

Als Beispiel für einen einzelnen Kern, nehmen wir an, dass ein Timer-Interrupt ankommt, der dazu führt, dass P1 vorgezogen wird. Sie deaktivieren Interrupts, wenn der Timer-Interrupt empfangen wird. Während Sie P1 zur Warteschlange hinzufügen, ist es nicht möglich, dass P2 verfügbar wird, entweder weil einige E/A für P2 abgeschlossen sind oder der Benutzer P2 gestartet hat usw. Interrupts wurden deaktiviert, so dass Ihr Kernel gewonnen hat Es werden keine Ereignisse in Bezug auf P2 gestört, bis P1 der Warteschlange hinzugefügt und Interrupts aktiviert wurden. Dasselbe gilt für P2: Wenn Sie P2 zur Warteschlange hinzufügen und ein Timer-Interrupt eintrifft, der dazu führen sollte, dass P1 vorweggenommen wird, wird der Timer-Interrupt einfach ignoriert, bis P2 der Warteschlange hinzugefügt wurde.