Was ist der Algorithmus hinter sleep()?

Jetzt gibt es etwas, das ich mich immer gefragt habe: Wie wird sleep() implementiert?

Wenn es darum geht, eine API aus dem Betriebssystem zu verwenden, wie wird die API dann erstellt?

Läuft alles darauf hinaus, speziellen Maschinencode auf der CPU zu verwenden? Benötigt diese CPU einen speziellen Co-Prozessor oder ein anderes Gizmo, ohne das Sie sleep() nicht haben können?

Die bekannteste Inkarnation von sleep() ist in C (genauer gesagt in den Bibliotheken, die mit C-Compilern geliefert werden, wie GNUs libc), obwohl fast jede Sprache heute ihre Entsprechung hat, aber die Implementierung von sleep in einigen Sprachen ( denke Bash) ist nicht das, was wir in dieser Frage betrachten …

BEARBEITEN: Nachdem ich einige der Antworten gelesen habe, sehe ich, dass der Prozess in eine Warteschlange gestellt wird. Von dort aus kann ich auch zwei Alternativen erraten

1. ein Timer wird gesetzt, damit der Kernel den Prozess zum richtigen Zeitpunkt weckt, oder
2. Wann immer dem Kernel eine Zeitscheibe erlaubt wird, fragt er die Uhr ab, um zu prüfen, ob es Zeit ist, einen Prozess aufzuwecken.

Die Antworten erwähnen nur Alternative 1. Daher frage ich: Wie verhält sich dieser Timer? Wenn es ein einfacher Interrupt ist, um den Kernel dazu zu bringen, den Prozess aufzuwecken, wie kann der Kernel den Timer bitten, “mich in 140 Millisekunden aufzuwecken, damit ich den Prozess in den laufenden Zustand versetzen kann”?

Die Frage “Update” zeigt einige Missverständnisse darüber, wie moderne Betriebssysteme funktionieren.

Dem Kernel wird keine Zeitscheibe “erlaubt”. Der Kernel ist das Ding, das Zeitscheiben an Benutzerprozesse ausgibt. Der “Timer” ist nicht so eingestellt, dass er den schlafenden Prozess aufweckt – er ist so eingestellt, dass er den aktuell laufenden Prozess stoppt.

Im Wesentlichen versucht der Kernel, die CPU-Zeit gerecht zu verteilen, indem er Prozesse stoppt, die zu lange auf der CPU sind. Nehmen wir für ein vereinfachtes Bild an, dass kein Prozess die CPU länger als 2 Millisekunden verwenden darf. Der Kernel würde also den Timer auf 2 Millisekunden setzen und den Prozess laufen lassen. Wenn der Timer einen Interrupt auslöst, übernimmt der Kernel die Kontrolle. Es speichert den aktuellen Zustand des laufenden Prozesses (Register, Befehlszeiger usw.), und die Steuerung wird nicht an ihn zurückgegeben. Stattdessen wird ein anderer Prozess aus der Liste der Prozesse ausgewählt, die darauf warten, CPU zu erhalten, und der unterbrochene Prozess wird an das Ende der Warteschlange gestellt.

Der Schlafvorgang ist einfach nicht in der Warteschlange der Dinge, die auf die CPU warten. Stattdessen wird es in der Schlafwarteschlange gespeichert. Immer wenn der Kernel einen Timer-Interrupt erhält, wird die Schlafwarteschlange überprüft, und die Prozesse, deren Zeit abgelaufen ist, werden in die Warteschleife “Warten auf CPU” übertragen.

Das ist natürlich eine grobe Vereinfachung. Es sind sehr ausgefeilte Algorithmen erforderlich, um Sicherheit, Fairness, Ausgewogenheit, Priorisierung und Vermeidung von Hunger zu gewährleisten, alles schnell und mit minimalem Speicherbedarf für Kernel-Daten.

Es gibt eine Kernel-Datenstruktur namens Sleep Queue. Es ist eine Prioritätswarteschlange. Immer wenn ein Prozess zur Schlafwarteschlange hinzugefügt wird, wird die Ablaufzeit des Prozesses, der am ehesten geweckt wird, berechnet und ein Timer gesetzt. Zu diesem Zeitpunkt wird der abgelaufene Job aus der Warteschlange genommen und der Prozess nimmt die Ausführung wieder auf.

(Lustige Kleinigkeit: In älteren Unix-Implementierungen gab es eine Warteschlange für Prozesse, für die fork() aufgerufen wurde, für die jedoch kein untergeordneter Prozess erstellt wurde. Sie hieß natürlich the Gabelschlange.)

HTH!

Vielleicht besteht die Hauptaufgabe eines Betriebssystems darin, die Komplexität einer echten Hardware vor dem Anwendungsautor zu verbergen. Daher läuft jede Beschreibung der Funktionsweise des Betriebssystems Gefahr, sehr schnell sehr kompliziert zu werden. Dementsprechend werde ich mich nicht mit all den “was wäre wenn” und “ja, aber” befassen, mit denen ein echtes Betriebssystem fertig werden muss. Ich werde nur auf einer hohen konzeptionellen Ebene beschreiben, was ein Prozess ist, was der Scheduler tut, wie die Timer-Warteschlange funktioniert. Hoffentlich ist dies hilfreich.

Was ist ein Prozess:

Stellen Sie sich einen Prozess vor – sprechen wir einfach über Prozesse und kommen später zu Threads – als „das Ding, das das Betriebssystem plant“. Ein Prozess hat eine ID – stellen Sie sich eine Ganzzahl vor – und Sie können sich diese Ganzzahl als Index in eine Tabelle vorstellen, die den gesamten Kontext dieses Prozesses enthält.

Kontext sind die Hardware-Informationen – Register, Inhalte der Speicherverwaltungseinheit, andere Hardware-Zustände – die, wenn sie in die Maschine geladen werden, es dem Prozess ermöglichen, “zu laufen”. Es gibt noch andere Kontextkomponenten – Listen offener Dateien, Status von Signalhandlern und, was hier am wichtigsten ist, Dinge, auf die der Prozess wartet.

Prozesse verbringen viel Zeit mit Schlafen (auch bekannt als Warten)

Ein Prozess verbringt viel Zeit mit Warten. Beispielsweise verbringt ein Prozess, der auf die Festplatte liest oder schreibt, viel Zeit damit, darauf zu warten, dass die Daten ankommen oder bestätigt werden, dass sie auf der Festplatte sind. OS-Leute verwenden die Begriffe “warten” und “schlafen” (und “blockiert”) etwas austauschbar – alles bedeutet, dass der Prozess darauf wartet, dass etwas passiert, bevor er seinen fröhlichen Weg fortsetzen kann. Es ist nur verwirrend, dass die Betriebssystem-API sleep() zufällig zugrunde liegende Betriebssystemmechanismen für schlafende Prozesse verwendet.

Prozesse können auf andere Dinge warten: beispielsweise auf das Eintreffen von Netzwerkpaketen, Fensterauswahlereignisse oder das Ablaufen eines Timers.

Prozesse und Terminplanung

Prozesse, die warten, werden gesagt nicht lauffähig. Sie gehen nicht in die Ausführungswarteschlange des Betriebssystems. Aber wenn das Ereignis eintritt, auf das der Prozess wartet, veranlasst es das Betriebssystem, den Prozess vom nicht lauffähigen in den lauffähigen Zustand zu versetzen. Gleichzeitig stellt das Betriebssystem den Prozess in die Ausführungswarteschlange, die eigentlich keine Warteschlange ist – es ist eher ein Stapel aller Prozesse, die, falls das Betriebssystem dies beschließt, könnte Lauf.

Planung:

das Betriebssystem entscheidet in regelmäßigen Abständen, welche Prozesse laufen sollen. Der Algorithmus, nach dem sich das Betriebssystem dafür entscheidet, wird wenig überraschend Scheduling-Algorithmus genannt. Planungsalgorithmen reichen von absolut einfach (“jeder darf 10 ms lang laufen, und dann darf der nächste in der Warteschlange laufen”) bis weitaus komplizierter (unter Berücksichtigung von Prozesspriorität, Ausführungshäufigkeit, Laufzeitfristen, Abhängigkeiten zwischen Prozessen, verkettete Sperren und alle möglichen anderen komplizierten Themen).

Die Timer-Warteschlange
Ein Computer hat einen Timer in sich. Es gibt viele Möglichkeiten, dies zu implementieren, aber die klassische Methode heißt a periodischer Timer. Ein periodischer Timer tickt in regelmäßigen Abständen – in den meisten Betriebssystemen von heute beträgt diese Rate meiner Meinung nach 100 Mal pro Sekunde – 100 Hz – alle 10 Millisekunden. Ich werde diesen Wert im Folgenden als konkrete Rate verwenden, aber wissen Sie, dass die meisten Betriebssysteme, die ihr Salz wert sind, mit unterschiedlichen Ticks konfiguriert werden können – und viele verwenden diesen Mechanismus nicht und können eine viel bessere Timer-Präzision bieten. Aber ich schweife ab.

Jeder Tick führt zu einem Interrupt für das Betriebssystem.

Wenn das Betriebssystem diesen Timer-Interrupt verarbeitet, erhöht es seine Vorstellung von der Systemzeit um weitere 10 ms. Dann sieht es sich die Timer-Warteschlange an und entscheidet, welche Ereignisse in dieser Warteschlange behandelt werden müssen.

Die Timer-Warteschlange wirklich ist eine Warteschlange von “Dingen, die behandelt werden müssen”, die wir Ereignisse nennen werden. Diese Warteschlange ist nach Ablaufzeit geordnet, die frühesten Ereignisse zuerst.

Ein “Ereignis” kann so etwas sein wie “Prozess X aufwecken” oder “Disk-I/O dort drüben kicken, weil es möglicherweise hängen geblieben ist” oder “ein Keepalive-Paket auf dieser Fibrechannel-Verbindung dort drüben senden”. Was auch immer das Betriebssystem getan haben muss.

Wenn Sie eine Warteschlange auf diese Weise bestellt haben, ist es einfach, das Entfernen aus der Warteschlange zu verwalten. Das Betriebssystem schaut einfach auf den Kopf der Warteschlange und verringert die “Zeit bis zum Ablauf” des Ereignisses um 10 ms bei jedem Tick. Wenn die Ablaufzeit auf Null geht, holt das Betriebssystem dieses Ereignis aus der Warteschlange und tut, was immer gefordert wird.

Im Fall eines schlafenden Prozesses macht es den Prozess einfach wieder lauffähig.

Einfach, oder?

Es gibt mindestens zwei verschiedene Ebenen, um diese Frage zu beantworten. (und viele andere Dinge, die damit verwechselt werden, werde ich nicht anfassen)

1. auf Anwendungsebene, das macht die C-Bibliothek. Es ist ein einfacher Betriebssystemaufruf, der dem Betriebssystem einfach mitteilt, diesem Prozess keine CPU-Zeit zu geben, bis die Zeit abgelaufen ist. Das Betriebssystem verfügt über eine Warteschlange mit ausgesetzten Anwendungen und einigen Informationen darüber, worauf sie warten (normalerweise entweder Zeit oder einige Daten, die irgendwo erscheinen).

2. Kernel-Ebene. Wenn das Betriebssystem gerade nichts zu tun hat, führt es eine ‘hlt’-Anweisung aus. diese Anweisung tut nichts, aber sie wird nie von selbst beendet. Natürlich wird ein Hardware-Interrupt normal bedient. Einfach ausgedrückt sieht die Hauptschleife eines Betriebssystems so aus (von sehr sehr weit weg):

   allow_interrupts ();
   while (true) {
     hlt;
     check_todo_queues ();
   }
   

   Die Interrupt-Handler fügen einfach Dinge zu den Todo-Warteschlangen hinzu. Die Echtzeituhr ist so programmiert, dass sie Interrupts entweder periodisch (mit einer festen Rate) oder zu einem festen Zeitpunkt in der Zukunft erzeugt, wenn der nächste Prozess geweckt werden möchte.

Ein Multitasking-Betriebssystem verfügt über eine Komponente namens Scheduler. Diese Komponente ist dafür verantwortlich, Threads CPU-Zeit zu geben. Der Aufruf von sleep weist das Betriebssystem an, diesem Thread für einige Zeit keine CPU-Zeit zu geben.

sehen http://en.wikipedia.org/wiki/Process_states für vollständige Details.

Ich weiß nichts über Linux, aber ich kann Ihnen sagen, was unter Windows passiert.

Sleep() bewirkt, dass die Zeitscheibe des Prozesses sofort endet, um die Kontrolle an das Betriebssystem zurückzugeben. Das Betriebssystem richtet dann ein Timer-Kernel-Objekt ein, das nach Ablauf der Zeit signalisiert wird. Das Betriebssystem gibt diesem Prozess dann keine Zeit mehr, bis das Kernel-Objekt signalisiert wird. Selbst dann, wenn andere Prozesse eine höhere oder gleiche Priorität haben, kann es noch eine Weile warten, bevor der Prozess fortgesetzt wird.

Spezieller CPU-Maschinencode wird vom Betriebssystem verwendet, um die Prozessumschaltung durchzuführen. Auf diese Funktionen kann nicht über Code im Benutzermodus zugegriffen werden, daher erfolgt der Zugriff ausschließlich über API-Aufrufe in das Betriebssystem.

Im Grunde ja, es gibt ein “besonderes Gizmo” – und es ist für viel mehr als nur Schlaf wichtig ().

Klassischerweise war dies auf x86 ein Intel 8253 oder 8254 „Programmable Interval Timer“. Bei den frühen PCs war dies ein separater Chip auf der Hauptplatine, der von der CPU programmiert werden konnte, um nach einem voreingestellten Zeitintervall einen Interrupt (über den “Programmable Interrupt Controller”, einen weiteren diskreten Chip) zu aktivieren. Die Funktionalität existiert immer noch, obwohl sie jetzt ein winziger Teil eines viel größeren Teils der Motherboard-Schaltung ist.

Das Betriebssystem programmiert das PIT heute immer noch so, dass es regelmäßig geweckt wird (in neueren Linux-Versionen standardmäßig einmal jede Millisekunde), und so kann der Kernel präemptives Multitasking implementieren.