Was ist der Algorithmus hinter sleep()?
Nun, es gibt etwas, was ich mich immer gefragt: wie ist sleep() implementiert ?
Wenn es ist alles über die Verwendung einer API vom OS, dann ist, wie die API gemacht ?
Macht alles einkochen, mit speziellen Maschinen-code auf der CPU ? Nicht, dass die CPU Sie benötigen eine spezielle co-Prozessoren oder anderen gizmo, ohne die Sie nicht haben kann sleep() ?
Die bekannteste Inkarnation von sleep() ist in C (um genauer zu sein, in den Bibliotheken, die mit C-Compilern wie dem GNU libc), obwohl fast jede Sprache hat heute seine Entsprechung, aber die Umsetzung des Schlafes in einigen Sprachen (denken Sie an die Bash), ist nicht das, was wir suchen, in dieser Frage...
EDIT: Nach der Lektüre einige der Antworten, sehe ich, dass der Prozess in einer wait-queue. Von dort aus kann ich denke, zwei alternativen, entweder
- ein timer ist so eingestellt, dass der kernel weckt den Prozess rechtzeitig, oder
- wenn der kernel erlaubt eine Zeitscheibe, es fragt die Uhr, um zu prüfen, ob es Zeit zu wecken, ein Prozess.
Antworten erwähnen nur die alternative 1. Daher Frage ich: wie funktioniert das timer-Verhalten ? Wenn es ein einfaches unterbrechen, damit der kernel wake den Prozess, wie kann das kernel-Fragen Sie den timer auf "wake me up in 140 Millisekunden, so kann ich den Prozess in den Status "wird ausgeführt" ?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Den "update" in Frage zu stellen, zeigt ein Missverständnis, wie die moderne OSs arbeiten.
Kernel ist nicht "erlaubt" eine Zeitscheibe. Der kernel ist das Ding, das gibt Zeit-slices in Benutzer-Prozesse. Der "timer" nicht wecken die Schlaf-up - Prozess festgelegt ist, stoppen Sie die Laufenden Prozess.
Im wesentlichen der kernel versucht, gerecht zu verteilen die CPU-Zeit durch stoppen der Prozesse auf die CPU zu lange. Für ein Vereinfachtes Bild, sagen wir mal, dass kein Prozess darf die CPU mehr als 2 Millisekunden. So, die kernel timer auf 2 Millisekunden, und lassen Sie den Vorgang laufen. Wenn der timer feuert einen interrupt, gibt der kernel die Kontrolle übernimmt. Es speichert den Laufenden Prozess' aktuellen Zustand (Register, instruction-pointer und so weiter), und das Steuerelement wird nicht zurückgegeben werden. Stattdessen wird ein anderer Prozess ausgewählt wird aus der Liste der Prozesse, die warten, gegeben zu werden, die CPU und der Prozess, der unterbrochen wurde, geht an der Rückseite der Warteschlange.
Den schlafenden Prozess ist einfach nicht in der Warteschlange der Dinge warten, die für die CPU. Stattdessen, es ist gespeichert in der sleeping-Warteschlange. Wenn der kernel bekommt timer-interrupt, sleep-queue überprüft, und die Prozesse, deren Zeit gekommen sind, übertragen zu bekommen "waiting for CPU" - Warteschlange.
Dies ist natürlich eine grobe Vereinfachung. Es dauert sehr ausgefeilte algorithmen um die Sicherheit zu gewährleisten, fairness, balance, Prioritäten zu setzen, zu verhindern, Hunger, tun es alle, schnell und mit minimalen Menge des verwendeten Speichers für kernel-Daten.
HZ=1000
stattHZ=100
zu bekommen 1ms jiffies. Siehe zum Beispiel serverfault.com/questions/377947/.... Multi-core-CPUs haben diese viel weniger wichtig, auch, da die Verriegelung benötigt für SMP macht die Unterstützung von pre-emption viel billiger. Und es gibt oft einen freien KernGibt es eine kernel-Daten-Struktur, die so genannte sleep-queue. Es ist eine Priorität. Wann immer ein Prozess Hinzugefügt wird, um die sleep-queue, dem Ablauf der Zeit, von der die meisten bald-zu-sein-erwacht-Prozess berechnet wird, und ein timer gesetzt ist. Zu dieser Zeit, die abgelaufen ist, job aus der Warteschlange und der Prozess-Ausführung.
(amüsantes trivia: in älteren unix-Implementierungen, gab es eine Warteschlange für Prozesse, die für die Gabel() gerufen worden waren, für die aber der child-Prozess wurde nicht erstellt. Es war natürlich genannt Gabel Warteschlange.)
HTH!
Vielleicht die wesentliche Aufgabe eines Betriebssystems ist das ausblenden der Komplexität, die ein echtes Stück hardware aus dem writer Anwendung. Daher, jede Beschreibung, wie das OS arbeitet, läuft Gefahr, sich wirklich kompliziert ist, ist wirklich schnell. Von daher bin ich nicht umzugehen mit all den "was wäre wenn" und ja, Abers", die ein echtes Betriebssystem zu beschäftigen. Ich werde einfach mal beschreiben, auf hohem konzeptionellen Niveau, was ein Prozess ist, was der scheduler macht, wie die timer-Warteschlange funktioniert. Hoffentlich ist dies hilfreich.
Was ist ein Prozess:
Denke, dass der eine Prozess--lassen Sie uns nur über Prozesse sprechen, und man threads später-als "die Sache des Betriebssystems Zeitpläne". Ein Prozess hat eine ID-denken ein integer--und Sie denken, die ganze Zahl als index in eine Tabelle, die alle den Kontext des Prozesses.
Kontext ist die hardware-Informationen-Register, memory management unit Inhalt, andere hardware-Staat -, dass, wenn in die Maschine geladen, ermöglicht, den Prozess zu "gehen". Es gibt auch andere Komponenten des Kontext--Listen von Dateien geöffnet, der Zustand der signal-Handler, und, am wichtigsten ist hier, Dinge, die der Prozess wartet.
Prozesse verbringen viel Zeit mit schlafen (ein.k.ein. Wartezeit)
Einen Prozess verbringt viel Zeit mit dem warten. Zum Beispiel, ein Prozess, der liest oder schreibt auf die Festplatte verbringen eine Menge Zeit mit dem warten auf die Daten zu kommen oder anerkannt werden, werden auf der Festplatte. OS Leute verwenden die Begriffe "warten" und "schlafen" (und "blockiert") etwas austauschbar--alle Bedeutung, die der Prozess erwartet, dass etwas passiert, bevor es weiter auf Ihre fröhliche Art und Weise. Es ist nur verwirrend, dass die OS-API sleep() passiert, zu verwenden zugrunde liegende Betriebssystem-Mechanismen für die schlafenden Prozesse.
Prozesse können warten, werden für andere Dinge: - Netzwerk-Pakete ankommen, Fenster Auswahl der Ereignisse, oder ein timer abläuft, zum Beispiel.
Prozesse und Scheduling
Prozesse, die darauf warten, sagte non-runnable. Sie gehen nicht auf die run-queue des Betriebssystems. Aber wenn das Ereignis Auftritt, das der Prozess wartet, es bewirkt, dass das Betriebssystem den Prozess aus dem non-runnable, um den Zustand runnable. Zur gleichen Zeit, das Betriebssystem legt den Vorgang auf der run-queue, die ist wirklich nicht eine Warteschlange-es ist mehr ein Haufen von alle die Prozesse, die, sollte das Betriebssystem entscheiden, dies zu tun, könnte laufen.
Planung:
das Betriebssystem entscheidet, in regelmäßigen Abständen, welche Prozesse ausgeführt werden sollen. Der Algorithmus, mit dem das Betriebssystem entscheidet, das zu tun, ist aufgerufen, etwas überraschend, der scheduling-Algorithmus. Scheduling-algorithmen reichen von tot-einfach ("jeder zum laufen bekommt, für 10 ms, und dann den nächsten Mann in der Warteschlange wird ausgeführt") zu weit komplizierter (unter Berücksichtigung der Prozess-Priorität, Häufigkeit der Ausführung, Laufzeit -, Fristen, inter-Prozess-Abhängigkeiten, verkettet, Schlösser und allerlei andere komplizierte Materie).
Die Timer-Warteschlange
Ein computer hat einen timer drin. Es gibt viele Möglichkeiten, wie dies umgesetzt werden kann, aber die klassische Art und Weise ist, genannt periodische timer -. Eine periodische timer-ticks, die in regelmäßigen Abständen-in den meisten Betriebssystemen heute, ich glaube, diese rate ist 100-mal pro Sekunde-100 Hz--alle 10 Millisekunden. Ich werde den Wert in dem, was folgt, als eine konkrete rate, aber wissen, dass die meisten Betriebssysteme Wert Ihr Salz kann so konfiguriert werden mit verschiedenen Zecken-und viele nicht nutzen diesen Mechanismus, und kann eine viel bessere timer Genauigkeit. Aber ich schweife ab.
Jeden tick die Ergebnisse in einem interrupt an das Betriebssystem.
Wenn das Betriebssystem behandelt diesen timer-interrupt, erhöht es die Idee der system-Zeit von weiteren 10 ms. Dann sieht es so aus, das timer-Warteschlange und entscheidet, welche Ereignisse auf die Warteschlange, die behandelt werden müssen.
Die timer-Warteschlange wirklich ist eine Warteschlange von "Dinge, die geregelt werden müssen", die wir Ereignisse nennen. Diese Warteschlange ist bestellt von der Zeit der Ablauf, frühestens Ereignisse zuerst angezeigt werden.
Einem "event" kann so etwas wie, "wake up-Prozess X", oder "go kick disk-I/O über es, da es möglicherweise steckengeblieben", oder "senden eines keepalive-Pakets auf, dass fibrechannel-link drüben". Was muss das Betriebssystem gemacht haben.
Wenn Sie eine Warteschlange bestellt auf diese Weise, es ist einfach zu verwalten das abarbeiten der Warteschlange. Das OS sieht einfach am Kopf der Warteschlange und verringert die "time-to-Ablauf" der Veranstaltung, die von 10 ms bei jedem tick. Wenn die Gültigkeitsdauer auf null geht, das OS aus der Warteschlange entfernt, die Veranstaltung, und tut, was gefordert ist.
Im Falle eines schlafenden Prozess, der es einfach macht den Prozess ausführbar wieder.
Einfach, nicht wahr?
gibt es mindestens zwei verschiedene Ebenen, um diese Frage zu beantworten. (und eine Menge anderer Dinge, die mit ihm verwechselt werden, werde ich nicht Anfassen)
Anwendungsebene, das ist, was die C-Bibliothek bietet. Es ist ein einfaches OS aufrufen, es sagt einfach das OS nicht zu geben die CPU-Zeit dieses Prozesses, bis die Zeit vergangen ist. Der OS hat eine Warteschlange hängenden, und einige Infos über das, was sind Sie warten für (in der Regel entweder die Zeit, oder einige Daten angezeigt werden, irgendwo).
kernel-Ebene. wenn das OS gar nichts zu tun haben, jetzt, führt er ein 'hlt' instruction. diese Anweisung tut nichts, aber es endet nie von selbst. Natürlich, ein hardware-interrupt wird bearbeitet, in der Regel. Einfach gesagt, der main-loop eines OS sieht wie folgt aus (von sehr, sehr weit entfernt):
den interrupt-Handler simpy hinzufügen Dinge auf der todo-Warteschlangen. Die Echtzeit-Uhr ist so programmiert, dass interrupts erzeugen, die entweder in regelmäßigen Abständen (zu einem festen Zinssatz) oder zu einem festen Zeitpunkt in der Zukunft, wenn der nächste Prozess will geweckt werden.
Einem multitasking-Betriebssystem verfügt über eine Komponente namens scheduler, diese Komponente ist verantwortlich für die CPU-Zeit, die threads, aufrufen von sleep erzählt die OS nicht zu geben die CPU-Zeit für diesen thread für einige Zeit.
sehen http://en.wikipedia.org/wiki/Process_states für komplette details.
Ich weiß nichts über Linux, aber ich kann Ihnen sagen, was passiert, auf Windows.
Sleep() bewirkt, dass der Prozess' time-slice-zu-Ende sofort Rückgabe der Kontrolle an das OS. Das Betriebssystem setzt dann einen timer ein kernel-Objekt signalisiert bekommt, nachdem die Zeit abgelaufen ist. Wird das OS dann nicht geben, dass der Prozess mehr Zeit, bis der kernel-Objekt signalisiert bekommt. Selbst dann, wenn andere Prozesse haben eine höhere oder gleiche Priorität, es kann noch ein wenig warten lassen, bevor der Prozess fortgesetzt werden.
Spezielle CPU-Maschinen-code wird von dem OS zu tun Prozess-switching. Diese Funktionen können aufgerufen werden, indem Sie user-mode-code, so dass auf Sie zugegriffen wird streng nach API-Aufrufe in die OS.
Im wesentlichen ja, es ist ein "Spezial-Ding" - und es ist wichtig, für viel mehr als nur schlafen().
Klassisch, auf x86, dies war ein Intel 8253 oder 8254 "Programmierbare Intervall-Timer". In den frühen PCs war dies ein separater chip auf dem motherboard, die programmiert werden konnten, die von der CPU zur Geltendmachung eines interrupt (über die "Programmable Interrupt Controller", eine weitere diskrete chip) nach einem voreingestellten Zeitintervall. Die Funktionalität ist noch vorhanden, obwohl es ist jetzt ein winziger Teil eines viel größeren Stück des motherboard-Schaltung.
Den OS heute noch Programme die GRUBE, um ihn zu aktivieren, regelmäßig (in den letzten Versionen von Linux, einmal jede Millisekunde standardmäßig), und dies ist, wie der Kernel ist in der Lage zu implementieren, pre-emptive multitasking.
glibc 2.21 Linux
Vorne, um die
nanosleep
system nennen.glibc ist die Standard-Implementierung für die C-stdlib, die auf den meisten Linux-desktop-Distributionen.
Wie es zu finden: der erste reflex ist:
Diese enthält:
und wir wissen, dass:
enthält den Linux-Besonderheiten.
Auf der Oberseite, dass die Datei, die wir sehen:
Also, wenn Sie Vertrauen in die Kommentare, wir sind im Grunde.
Unten:
die im Grunde sagt
__sleep
==sleep
. Die Funktion verwendetnanosleep
durch:Nach greppingg:
bekommen wir eine kleine Liste der interessanten Ereignisse, und ich denke
__nanosleep
definiert ist:auf der Linie:
ist die einige super DRY magic-format analysiert:
Dann aus dem build-Verzeichnis:
Führt uns zu:
/sysd-syscalls
wasmake-syscalls.sh
generiert und enthält:Sieht es aus wie ein Teil einer Makefile.
git grep sysd-syscalls
zeigt, dass es enthalten ist in:compile-syscall
sieht aus wie der Schlüssel Teil, so finden wir:Beachten Sie, dass
-x assembler-with-cpp
ist eingcc
option.Diese
#define
s Parameter wie:und verwenden Sie Sie dann an:
OK, das ist soweit ich werde gehen auf der makro-expansion Spiel für jetzt.
Ich denke, dann generiert dies den
posix/nanosleep.o
- Datei, die verknüpft werden müssen zusammen mit alles.Linux 4.2 x86_64 nanosleep syscall
Verwendet der scheduler: es ist nicht ein schlafen beschäftigt.
Suche ctags:
Führt uns zu
kernel/time/hrtimer.c
:hrtimer
steht für High-Resolution-Timer. Von dort aus werden die Haupt-Zeile sieht so aus:hrtimer_nanosleep
do_nanosleep
set_current_state(TASK_INTERRUPTIBLE);
was ist unterbrechbar schlafenfreezable_schedule();
fordertschedule()
und können andere Prozesse laufenhrtimer_start_expires
hrtimer_start_range_ns
arch/x86
timing NiveauEin paar Artikel darüber:
sleep(3)
umgesetzt wird obennanosleep(2)
von glibc. Das ist nicht der interessante Teil, IMO. Ich würde vielleicht verbringen Sie einen Satz auf, dass an der Spitze, dann vielleicht wieder an ein glibc-source Speicherort der Datei unten in der Antwort. BTW, Einzelschritt im debugger oder mitstrace
trace system calls für ein test-Programm, wäre ein einfacher Weg, um herauszufinden, dass glibc istsleep
verwendetnanosleep
. Es würde nicht sparen Sie sich die Mühe waten durch die Quelle, wenn Sie möchten, um zu sehen, die eigentliche übersetzung-layer source-code, though.