Detaillierte Einführung in die Prozessorplanung

Prozessorplanung

Tags (durch Leerzeichen getrennt): Prozessplanung Planungsalgorithmus Betriebssystem

---

Grundlegende Konzepte

Definition
: Betriebssystemverwaltung Begrenzte Ressourcen Wenn mehrere Prozesse (oder von mehreren Prozessen ausgegebene Anforderungen) diese Ressourcen nutzen möchten, müssen Prozesse (Anforderungen) nach bestimmten Prinzipien ausgewählt werden, um die Ressourcen zu belegen .

Der Zweck besteht darin, die Anzahl der Ressourcenbenutzer zu steuern und die Berechtigung von Ressourcenbenutzern auszuwählen, Ressourcen zu belegen oder Ressourcen zu belegen. Drei Ebenen der Prozessorplanung:

• Erweiterte Planung: Jobplanung, das Planungsobjekt ist der Job.

• Zwischenplanung: Speicherplanung (im Wesentlichen Es handelt sich um die Speicheraustauschfunktion)

• Scheduling auf niedriger Ebene: Prozessplanung, das Planungsobjekt ist ein Prozess oder Thread auf Kernelebene

Jobplanung Der Algorithmus ist auch auf die Prozessplanung anwendbar

Dienstzeit(T_s): Die Zeit, die das System benötigt, um Dienste für einen Job oder Prozess bereitzustellen
Durchlaufzeit(T_i): Das Zeitintervall von der Übermittlung eines Auftrags oder Prozesses an das System bis zum Abschluss des Auftrags oder Prozesses
Enthält normalerweise:

Die Zeit, die der Job auf die Planung in der externen Speichersicherungswarteschlange wartet.
Der Prozess befindet sich in der Zeit, die er damit verbringt, auf die Prozessplanung in der Bereitschaftswarteschlange zu warten.
Die Zeit, die der Prozess auf der CPU ausgeführt wird.
Die Zeit, die der Prozess auf den Abschluss des E/A-Vorgangs wartet.

Durchschnittliche Bearbeitungszeit:
[T = frac{sum_{i=1}^n T_i}{n} ]
Gewichtete Bearbeitungszeit: Das Verhältnis der Bearbeitungszeit eines Auftrags zur Zeit, die für die Bearbeitung benötigt wird
[W_i = frac{T_i}{T_s}]
Durchschnittliche gewichtete Bearbeitungszeit:
[W = frac{sum_{i=1}^n frac{T_i}{T_s} }{n}]

Terminplanung, Wechsel und Prozess

Das Prozessplanungs- und Umschaltprogramm ist das Kernelprogramm des Betriebssystems. Wenn das eine Planung anfordernde Ereignis auftritt, kann der Prozessplaner ausgeführt werden. Wenn ein neuer bereiter Prozess geplant wird, wird ein Wechsel zwischen Prozessen durchgeführt. Theoretisch sollten diese drei Dinge nacheinander ausgeführt werden, aber im tatsächlichen Design, wenn das Kernelprogramm des Betriebssystems ausgeführt wird und irgendwann Faktoren auftreten, die eine Prozessplanung verursachen, sind Planung und Wechsel möglicherweise nicht sofort möglich.

In modernen Betriebssystemen können Prozessplanung und -umschaltung in den folgenden Situationen nicht durchgeführt werden:

1. Beim Umgang mit Interrupts: Der Interrupt-Verarbeitungsprozess ist kompliziert Es ist schwierig, Prozesse in der Implementierung zu wechseln, und die Interrupt-Verarbeitung ist Teil der Systemarbeit. Sie gehört logischerweise nicht zu einem bestimmten Prozess und sollte nicht von Prozessorressourcen beraubt werden.

2. Der Prozess befindet sich im kritischen Abschnitt des Kernelprogramms des Betriebssystems: Nach dem Betreten des kritischen Abschnitts muss er ausschließlich auf freigegebene Daten zugreifen. Theoretisch muss er gesperrt werden, um andere zu verhindern Parallele Programme können nach dem Entsperren nicht eingegeben werden. Sie sollten vor der Ausführung nicht zu anderen Prozessen wechseln, um die Freigabe der freigegebenen Daten zu beschleunigen.

3. Bei anderen atomaren Vorgängen, die eine vollständige Abschirmung von Interrupts erfordern: wie Sperren, Entsperren, Unterbrechung des Standortschutzes, Wiederherstellung und anderen atomaren Vorgängen. In einem atomaren Prozess müssen sogar Interrupts maskiert werden und Prozessplanung und -umschaltung sollten nicht durchgeführt werden.

Wenn während des oben genannten Prozesses Bedingungen auftreten, die eine Planung verursachen, und die Planung und Umschaltung nicht sofort durchgeführt werden kann, sollte das Anforderungsplanungsflag des Systems gesetzt werden und die entsprechende Planung wird erst durchgeführt Der obige Vorgang ist mit dem Schalter abgeschlossen.

Die Situationen, in denen Prozessplanung und -umschaltung durchgeführt werden sollten, sind:

1. Wenn eine Planungsbedingung auftritt und der aktuelle Prozess nicht weiter ausgeführt werden kann, können Planung und Umschaltung durchgeführt werden sofort. Wenn das Betriebssystem in dieser Situation nur die Prozessplanung durchführt, handelt es sich um eine Planung ohne Deprivation.

2. Wenn die Interrupt- oder Trap-Verarbeitung abgeschlossen ist, können Prozessplanung und -umschaltung durchgeführt werden, bevor zum Benutzermodus-Programmausführungsort des unterbrochenen Prozesses zurückgekehrt wird und das Anforderungsplanungsflag gesetzt ist sofort durchgeführt. Wenn das Betriebssystem in diesem Fall einen Ausführungsplaner unterstützt, wird die Planung im Deprivationsmodus implementiert.

Die Prozessumschaltung erfolgt häufig unmittelbar nach Abschluss der Planung. Dazu müssen die Szeneninformationen des aktuellen Umschaltpunkts des ursprünglichen Prozesses gespeichert und die Szeneninformationen des geplanten Prozesses wiederhergestellt werden. Beim Wechseln des Kontexts schiebt der Betriebssystemkernel die Kontextinformationen des ursprünglichen Prozesses in den Kernel-Stack des aktuellen Prozesses, um sie zu speichern, und aktualisiert den Stapelzeiger. Nachdem der Kernel das Laden der lokalen Informationen des neuen Prozesses aus dem Kernel-Stack des neuen Prozesses, das Aktualisieren des aktuell ausgeführten Prozessraumzeigers, das Zurücksetzen des PC-Registers und andere damit verbundene Arbeiten abgeschlossen hat, beginnt er mit der Ausführung des neuen Prozesses.

Planungsmethode

• Nicht-präemptive Methode
  Sobald der Prozessor einem Prozess zugewiesen ist, läuft er weiter und wird nie aufgrund einer Taktunterbrechung unterbrochen oder Aus irgendeinem anderen Grund wird der Prozessor des aktuell ausgeführten Prozesses nicht anderen Prozessen zugewiesen, bis der Prozess aufgrund eines Ereignisses abgeschlossen oder blockiert ist Methode

  Das System ermöglicht es dem Scheduler, einen ausgeführten Prozess anzuhalten und den dem Prozess zugewiesenen Prozessor auf der Grundlage bestimmter Prinzipien einem anderen Prozess zuzuweisen
Bestimmte Grundsätze sollten beim „Vorwegnehmen“ befolgt werden:

• 
  
  

  Prioritätsprinzip

• Kurzprozess-Prioritätsprinzip

• Zeitscheibenprinzip

Typischer Planungsalgorithmus

Wer zuerst kommt, mahlt zuerst: Planungsalgorithmus ):

ist der FCFS-Planungsalgorithmus, der sowohl für die Jobplanung als auch für die Prozessplanung verwendet werden kann. Das System folgt bei der Planung der Reihenfolge der Jobankunft (Priorität gegenüber der längsten Wartezeit im Job).
Nachteile: Die Dringlichkeit des Jobs wird nicht berücksichtigt und kann nur nacheinander ausgeführt werden

Prioritätsplanungsalgorithmus für kurze Jobs (Prozesse) (kurze Jobs zuerst):

Es ist für Kurzjobs eingerichtet, da es sich bei den meisten Betriebssystemen um Kurzjobs handelt, wählt das System den Job mit der kürzesten Laufzeit aus und überträgt ihn in den Speicher.

1. SJF (nicht präemptiv): Der Algorithmus berechnet die Priorität basierend auf der Länge des Jobs (je kürzer der Job, desto höher seine Priorität).

2. SPF (preemptible): Dasselbe wie oben, aber wenn es einen Job mit einer höheren Priorität gibt, kann er Ressourcen vorbelegen und sie zuerst ausführen.

Nachteile:

• Die Laufzeit des Jobs muss im Voraus vorhergesagt werden

• Es ist nicht gut für der Jobprozess

• Mensch-Computer-Interaktion kann nicht erreicht werden

• Berücksichtigt nicht die Dringlichkeit des Jobs

Prioritätsplanungsalgorithmus:

Der PSA-Algorithmus basiert auf der auftragsbasierten Dringlichkeit. Die entsprechende Priorität wird dem Auftrag von außen zugewiesen und entsprechend der Auftragspriorität geplant.

Planungsalgorithmus mit der höchsten Antwortpriorität (höchstes Anforderungsverhältnis als nächstes):

Der HRRN-Algorithmus berücksichtigt sowohl die Wartezeit des Jobs als auch die Joblaufzeit. Er führt eine dynamische Priorität für ein keine Jobs:

Priorität = (Wartezeit + erforderliche Servicezeit) / erforderliche Servicezeit

kann abgekürzt werden als:

R = Reaktionszeit / erforderliche Servicezeit

Eigenschaften:

1. Bei gleicher Auftragswartezeit gilt: Je kürzer die erforderliche Servicezeit, desto höher die Priorität . Ähnlich wie beim SJF-Algorithmus ist es für kurze Jobs von Vorteil

2. Wenn der Job die gleiche Servicezeit erfordert, ist die Priorität umso höher, je länger der Job ist zum FCFS-Algorithmus, der für lange Jobs von Vorteil ist

3. Da die Wartezeit lang genug ist, können Sie auch eine höhere Priorität erhalten wird nicht ewig warten.

Time-Slice-Rotation-Scheduling-Algorithmus (RR)

Prinzip: Das System weist alle Anfragen basierend auf der FCFS-Richtlinie zu. Der Bereitschaftsprozess wird arrangiert in einer Bereitschaftswarteschlange und ist so eingestellt, dass er in regelmäßigen Abständen sequentielle Interrupts generiert, den Prozessplaner im System aktiviert, die sequentielle Planung abschließt und die CPU dem neuen Warteschlangenleiterprozess (oder neu angekommenen dringenden Prozess) zuweist.

Prozessumschaltung

1. Wenn eine Zeitscheibe nicht aufgebraucht ist und der laufende Prozess abgeschlossen ist, wird der Scheduler sofort aktiviert und aus der Ausführungswarteschlange gelöscht

2. Wenn eine Zeitscheibe abläuft, wird der Timing-Interrupt-Handler aktiviert. Wenn die Ausführung des Prozesses noch nicht abgeschlossen ist, sendet der Scheduler bis zum Ende der Bereitschaftswarteschlange, plant die Ausführung des Kopfprozesses der Bereitschaftswarteschlange und startet eine neue Zeitscheibe

Hinweis: Die Zeitscheibe Wenn die Zeitscheibe zu lang gewählt wurde, wird der RR-Algorithmus zum FCFS-Algorithmus degenerieren, der die Anforderungen kurzer Jobs nicht erfüllen kann Die Zeitscheibe sollte etwas größer als die sequenzielle Zeit sein, die für eine typische Interaktion benötigt wird, da die meisten Prozesse innerhalb einer Zeitscheibe abgeschlossen werden.

Mehrstufiger Feedback-Warteschlangen-Planungsalgorithmus. :

1. Einstellungen Mehrere Bereitschaftswarteschlangen und jeder Warteschlange unterschiedliche Prioritäten zuweisen Je höher die Priorität, desto kleiner ist die Zeitscheibe. Die Warteschlange mit der höchsten Priorität wird zuerst eingeplant

2. Der FCFS-Planungsalgorithmus wird zwischen Warteschlangen verwendet. Erst wenn alle Prozesse in der Warteschlange mit hoher Priorität abgeschlossen sind, wird die nächste Warteschlange geplant

3. Die Prozesse in der Warteschlange werden gemäß dem Rotationsalgorithmus geplant. Neue Prozesse gelangen nach dem Speicher zuerst in die Warteschlange mit der höchsten Priorität

4. Wenn eine Warteschlange mit niedriger Priorität ausgeführt wird Wenn ein neuer Prozess eintrifft, wird die CPU nach der Ausführung dieser Zeitscheibe sofort den neu eintreffenden Jobs zugewiesen (präventiv).

Prozessplanungsalgorithmus im Echtzeitsystem

Echtzeitsystem bedeutet, dass das System zeitnah auf Anfragen von externen Ereignissen reagieren und diese Anfragen zeitnah verarbeiten kann Aufgrund dieser Eigenschaft werden Echtzeitsysteme häufig in der Industrie (üblich bei der Steuerung von Waffen), in Multimedia- und anderen Systemen eingesetzt.
In Echtzeitsystemen gibt es im Allgemeinen eine Frist. erfordern, dass sie vor der Startfrist ausgeführt werden und vor der Endfrist enden müssen. Dasselbe wie oben, aber nicht streng.
Es gibt zwei Arten von Algorithmen, die es zu beachten gilt: Früheste Frist Der erste Algorithmus (Earliest Deadline First) und der Least Laxity First-Algorithmus (Least Laxity First) können präventive Methoden und nicht-präventive Planung verwenden, letztere wird jedoch häufig für präemptive Planung verwendet.
In m periodischen Real- Zeitplanung, die Verarbeitungszeit jeder Echtzeitaufgabe(C_i), Zykluszeit (P_i), im Fall eines Einzelprozessors muss die Bedingung erfüllt sein: $sum_{ i=1}^mfrac{C_i}{P_i} (kleiner als 1; bei Multiprozessor muss die Bedingung erfüllt sein)sum_{i=1}^mfrac{C_i}{P_i } $ ist kleiner als N, N ist die Anzahl der Prozessoren.

Earliest Deadline First Algorithmus (EDF)

Dieser Algorithmus bestimmt die Priorität von Aufgaben anhand ihrer Fristen in einem Echtzeitsystem . 🎜>

Least Slack First Algorithmus (LLF)

1. Bei dieser Methode werden Aufgaben entsprechend ihrer Dringlichkeit (Slack) priorisiert, und je dringender die Aufgabe, desto höher die Priorität.

Der Slack-Grad der Aufgabe = die Zeit, in der sie abgeschlossen sein muss – ihre eigene Laufzeit – die aktuelle Zeit

2. Die Aufgaben des Systems werden entsprechend in einer Bereitschaftswarteschlange angeordnet Der Slack-Grad und die Aufgaben mit geringem Slack werden in die Warteschlange gestellt. Das heißt, der Scheduler führt sie zuerst aus.

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Prozessorplanung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!