Linux Scheduling Grundlagenfragen



  • Hallo,
    ich habe mal ein paar Fragen zu Linux und schreibe erst mal wie ich die Sachen bisher verstanden habe.

    Interrupt:
    Der Prozessor wird unterbrochen um Recourcen unfreiwillig abzugeben.

    Locking:
    Der Prozessor gibt Recourcen freiwillig ab, dabei kommt entweder ein Scheduler zum Einsatz (bspw. beim arbeiten mit Semaphoren), oder es wird "aktiv" gewartet, bspw. Spinlocks, fuer rel. kurze Wartezeiten.

    Signal:
    Linux setzt die ersten 32 im POSIX Standard definierten Singale im Kernel um, die weiteren sind fuer einen etwaigen RT Betrieb vorgesehen. Singale sind vordefinierte Werte die etwas "signalisieren". Signale koennen auch zu System Calls fuehren.

    System Call:
    Aufrufe an das System von Meldungen, Anfragen oder Aktionen.

    0. Ist das so richtig?

    1. Wie ist das nun, wenn etwa ein Scheduler damit beschaeftigt ist mit seinen Time Slices zwischen den
    einzelnen Prozessen auszuwaehlen und ploetzlich kommt ein Interrupt - wird dieser sofort behandelt?
    Was ist mit dem kritischen Abschnitt des jew. Prozesses - ich habe auch irgendwo mal gelesen, dass
    der Prozess der der Interruptroutine entspricht irgendwo gequeued wird, aber was ist mit dem
    unmittelbaren eintreffen des Interrupts? Ich habe auch mal was von IRQs - also interruptrequests gelesen,
    wird da zuerst angefragt ob unmittelbar ein Interrupt gesendet werden darf oder ob der Interrupt selber
    noch etwas warten muss?

    2. Ich habe immer noch nicht ganz den Unterschied zwischen Signal und System Call verstanden? Wozu gibt
    es eig Signale? deren Verhalten liesse sich doch auch per System Call realisieren? Wo liegt genau der
    Unterschied und die unterschiedliche Verwendung beider?

    3. Sind Signals und System Calls eigentlich Prozesse bzw. Kernel Threads oder was eigenes? Wie sieht das
    bei - etwa obigem Szenario aus, wenn dem Scheduler ploetzlich ein Signal oder ein System Call in die
    quere kommt? Werden diese vom Scheduler behandelt?

    4. Um das komplette Ausmass meiner momentanen Verwirrung darzustellen, nun die letzte Frage: kann es eig
    zu Race Conditions zwischen Interrupts, Signals, System Calls und dem was auf dem Scheduler direkt
    behandelt wird kommen?

    5. Ach ja, was ist dann jetzt eine "Service Routine" (Prozess/Kernel Thread oder ???)? Wird diese vom Scheduler
    behandelt?

    Danke im voraus 🙂



  • Hallo Fabeltier,
    ich versuche es mal nach besten Wissen und Gewissen. Vielleicht kann der Ein oder Andere hier noch was ergÀnzen.

    1. Ein Interrupt hat in einem Computer wie wir ihn kennen, egal welche Architektur immer höchste PrioritĂ€t. Also alleine schon die Hardware, ohne Betriebssystem kĂŒmmert sich sofort um einen Interrupt wenn er ankommt. Ausgenommen sind Interrupts welche vom Interrupt-Controller maskiert sind. Die werden schon von der Hardware ignoriert. Bei den meisten Betriebssystem, so auch bei Linux hat auch eine Interrupt die höchste PrioritĂ€t. Das heist der Linux-Kernel lĂ€sst alles stehen und liegen und eilt um den Interrupt zu bedienen. Naja eingentlich bedeutet stehen und liegen lassen schon einiges an Arbeit. Es muss der gerade bediente Prozess schlafen gelegt werden. Dessen Registerinhalte und Anfangsadressen werden gesichert. Das dauert auch schon einige ”Sekunden! In diesem Fall braucht das Betriebssystem erst gar nicht zu den Scheduler zu bedienen bzw. befragen, es ist klar: jetzt muss die Interrupt-Service-Routine ausgefĂŒhrt werden! Danach kann man den Scheduler aufrufen um zu sehen, welcher Prozess als nĂ€chstes bedient wird.

    Wenn der gerade laufende Prozess sich in einem kritischen Abschnitt befindet, wird er trotzdem schlafen gelegt. Da mehrere Interrupts zur gleichen Zeit eintreffen können, wird der Interrupt mit der höchsten PrioritÀt zu erst bedient, die Anderen werden zunÀchst gequeued, bis sie bedient werden können.
    IRQs sind wie Du schon richtig geschrieben hast Interrupt-Requests. Das sind die Hardware-Signale, die von den Interrupt-Auslösenden GerÀten kommen. Wenn da einer kommt, schaut die Hardware erst mal nach wo dieser herkommt.

    2. Ein Signal ist gewissermaßen ein Software-Interrupt. Wenn eines Deiner Programme/Prozesse einen Fehltritt tut. Also eine Division durch 0 oder einen illegalen Speicherzugriff, bekommt es automatisch ein Signal vom Betriebssystem, "achtung du tust was fehlerhaftes" oder tue sonst was. Wenn ein Programm ein solches Signal empfĂ€ngt wird die der dafĂŒr zustĂ€ndige Signalhandler ausgefĂŒhrt. So eine Art Interrupt-Service-Routine fĂŒr Prozesse. Falls keiner eingerichtet ist, wird die default-Aktion fĂŒr dieses Signal ausgefĂŒhrt. I.d.R. bedeutet das daß der Prozess beendet wird. Bei Signal "kill" wird das sowiso gemacht. Du kannst dafĂŒr zwar auch einen Handler implemtieren der z.B. alle Dateien und Sockets schliesst aber danach wird der Prozess auf jeden Fall beendet!
    Du kannst auch selber ein Signal erzeugen, mit dem Systemcall "kill".

    Ein Systemcall ist etwas ganz anderes. Hier wird ganz einfach eine Kernelroutine aufgerufen. Der Kernel (egal ob Win32, Linux oder BSD, naja Microkernel sind etwas anders) ist ein riesiger Kneul von Routinen, die darauf warten aufgerufen zu werden. Also wenn Du in eine Datei schreibst, greifst Du implizit auf die Hardware zu (schreibst auf die Platte). Dazu muss aber der Kernel aufgerufen werden. DafĂŒr wird ĂŒber die diversen Bibliotheken ein Systemcall ausgefĂŒhrt, das Programm springt dann in einen Kerneltrap. Was dann passiert, liegt nicht mehr im ermessen des Programms, sondern der Kernel arbeitet dann die angeforderte Funktion aus und gibt nach Abschluss bzw. Abbruch (falls Fehler) die Kontrolle an den Prozess zurĂŒck.

    3. Weder Signale nach System-Calls sind Prozesse. Ein Signal ist ein Signal, besser kann man es nicht ausdrĂŒcken. Es ist einfach eine Nachricht die an einen Prozess geschickt wird. Dieser fĂŒhrt, falls ein Signal-Handler eingerichtet ist diesen aus. Wenn ein Interrupt ankommt wĂ€hrend der Signalhandler ausgefĂŒhrt wird, muss der Signalhandler unterbrochen werden.
    Der System-Call ist auch kein Prozess, sondern eine Kernel-Routine die ausgefĂŒhrt wird. Wenn hier ein Interrupt ankommt, hat auch dieser das nachsehen, zuerst wird die ISR (Interrupt Service Routine) ausgefĂŒhrt, dann wird nachgeschaut welcher Prozess dann an der Reihe ist. Falls es der Prozess ist, der gerade eben, vor der ISR den Systemcall ausgefĂŒhrt hat, dann wird der Systemcall weitergefĂŒhrt.

    4. Die ISR hat die höchste PrioritÀt, wie schon oben geschrieben. Eigentlich kann es hier zu keinem Race-Condition kommen. Ein System-Call und ein Signal gehört zu einem Prozess. Zwichen Prozessen kann es zu Race-Conditions kommen daher auch möglicherweise zwischen System-Call und Signal zwei versch. Prozesse.

    5. Wie oben erwĂ€hnt, eine Interrupt-Service-Routine(ISR), wird ausgefĂŒhrt, wenn der Interrupt ankommt. Sie ist Teil eines Treiber-Moduls, von einem GerĂ€t das Interrupts werfen kann.

    Ich kann Dir das Buch "Betriebssysteme" von Andrew Tanenbaum empfehlen. Das ist das Standartwerk und beantwortet alle Fragen. Nimm Dir Zeit dafĂŒr!

    Gruss Christian



  • Danke, das war sehr aufschlussreich. Den Tanenbaum kenn ich natuerlich und muss zustimmen, das es imo sehr viel Information enthaelt, aber ausserdem auch noch sehr verstaendlich geschrieben ist, fuer dieses doch sehr umfangreiche Themengebiet (nicht zu verachten den dezent platzierten Humor von Herrn Tanenbaum - Genial!!!).

    Folgendes war mir unklar:

    Naja eingentlich bedeutet stehen und liegen lassen schon einiges an Arbeit. Es muss der gerade bediente Prozess schlafen gelegt werden.

    Es laeuft also alles ueber den Scheduler! Mir war das etwas unklar ob Interrupts den Scheduler nicht einfach umgehen koennen (v.a. Hardware-Interrupts, etc) und somit auch was mit dem jew. bearbeiteten Prozess dann eigentlich gemacht wird. Gibt es nicht auch Formen von "Hardware-Schedulern"?

    Ein Signal ist gewissermaßen ein Software-Interrupt.

    Danke, wie ein Signal abgearbeitet wird, wusste ich zwar, aber was es eig ist, war mir unklar! Unter Software-Interrupt kann ich mir nun jedoch was vorstellen.

    Das der Kernel selber ein Prozess ist und somit alles was "im Kernel" vorgeht als Thread ablaeuft, da sich der Adressraum dieser Threads den des Kernel-Prozesses aufteilt, ist mir bekannt. Nur jedesmal, wenn ich wieder den daemlichen Scheduler ins Spiel bringe, kommt die Vorstellungskraft zum erliegen. Ich kann mir sehr wohl eine Race Condition zwischen versch Kernel Threads vorstellen (wuerde der Scheduler nicht richtig funktionieren). Nur was sind diese Service Routinen, bzw System Calls (das geht ja irgendwie in dieselbe Richtung) eigentlich?

    So wie ich es mir bisher vorstelle, handelt es sich dabei um "passive Elemente" im Kernel, die also keinen Anspruch auf Abarbeitung stellen, sondern bspw von Prozessen, Interrupts o.ae. - gestartet werden. Nur was passiert dann? Sie rufen dann - ploetzlich aktiv - wiederum andere System Calls auf oder starten Kernel Threads. Ich stelle mir das momentan so vor, dass solange sie "aktiv" sind, sie ebenfalls vom Scheduler als "Kernel Thread" behandelt werden. Stimmt das?

    Hier liegen meine Probleme, es geht mir darum ein riesen Wirr Warr in meinem Kopf etwas zu ordnen. Aber ich glaube ich bekomme langsam eine Vorstellung davon. Vieles was Du gesagt hattest war mir daher bspw. schon bekannt, nun bin ich mir hier etwas sicherer, das ich es anscheinend richtig verstanden habe.

    Nimm Dir Zeit dafĂŒr!

    Genau das ist wohl auch mein Problem.. nur einmal durchlesen und kurz mal durchblicken erzeugt Chaos, an manchen Stellen - definitiv! 😉

    PS: Ich kenne bspw von Qt her das Konzept von Signals und Slots, ist sowas vergleichbar mit System Calls und Service Routinen? Man kann ja von einem "definierten" Signal aus schliesslich auch einen System Call implementieren, sobald man es abfaengt?



  • Also was den Scheduler angeht ist auch meine Vorstellungskraft auf eine hohe Probe gestellt. Es heist "der Kernel ist eine Sammlung von Betriebssystem-Service-Routinen die darauf warten aufgerufen zu werden". Das stimmt bis auf den Scheduler. Dieser arbeitet aus sich heraus, es ist die wichtigste Routine im ganzen Betriebssytem. Es gibt sogenannte MicroKernel-Betriebssysteme. Bei deren Kernel kommt es nicht so sehr darauf an, daß er sehr klein ist (man kann auch einen monolytischen Kernel sehr klein halten) sondern darauf daß in deren Kernel nur das wichtigste drin steckt. Ein solcher Microkernel besteht im Idealfall nur aus einem Scheduler/Dispatcher und einer Speicherverteiler. So ein Kernel macht nichts anderes als anderen Prozessen Speicherplatz und Prozessorzeit zuzuweisen. Alles andere machen verschiedene Serverprozesse. Also Netzwerk-Verkehr, Filesystem. Ein normaler User-Prozess in einem solchen System ruft dann, wenn er z.B eine Datei öffnet den Filesystem-Server auf. Dieser ist berechtigt auf die Platte zuzugreifen.
    Aber der Scheduler ist der Regiseur. Wenn wir im extremfall einen Prozess haben, der eine höhre PrioritÀt hat, als alle anderen Prozesse, bekommt dieser Prozess dauernd die Prozessor vom Scheduler, ausser wenn er blockiert ist. Wenn dieser Prozess in eine Datei schreibt, dann bekommt, dann erkennt das der Scheduler, denn die Dateioperation ist Teil seines Prozessablaufs. Dann bekommt der Fileserver den Prozessor zugeteilt, bis die Schreib-Operation fertig ist. Wenn der Prozess dann weiter aktiv ist bekommt er wieder den Prozessor.

    Und so ist dann auch bei monolytischen Betriebssystemen. Der Scheduler ist das Herz des Kernels. Er vergibt den Prozessor immer fĂŒr gewisse Zeitscheiben an die verschiedenen rechenfĂ€higen (nicht blockierten) Prozesse. Wenn einer dieser Prozesse einen Dateizugriff macht, ruft er halt wiederrum den Kernel. Nun fĂŒhrt der Kernel diese FunktionalitĂ€t fĂŒr den Prozess aus. Es ist halt der gleiche Kernel, der auch den Scheduler beherbergt. Hat den Vorteil daß man keine Daten zwischen verschiedenen Server-Prozessen austauschen muss. Eine solche Betriebssystem-Routine (System-Call) die im Kernel ruht und darauf wartet ausgefĂŒhrt zu werden ist dann wirklich ein Thread. Der Begriff Kernel-Thread ist aber schon belegt fĂŒr normale Threads in einem User-Prozess, die aber vom Kernel geschedult werden, also nicht verwechseln mit einem Systemcall.

    Wenn dem Prozess, der den System-Call aufgerufen hat, der Prozessor enzogen wird (also ein anderer Prozess an der Reihe ist) dann bleibt auch der Systemcall erst mal stecken und pausiert (ausser er steckt in einem kritischen Code-Abschnitt der nicht unterbrochen werden darf).

    Um es zusammenzufassen, der Scheduler ist das zentrale Herz eines jeden Betriebssystems!

    So ich genug geschwafelt. Ich hoffe daß mich jemand korrigiert, falls ich falsch liege.

    Gruss Christian


Log in to reply