Wir alle sind es gewöhnt, dass mehrere Programme gleichzeitig auf unserem Computern laufen. Doch tun sie das wirklich?
Nein. Denn der klassische Computer hat ein Problem: er hat weniger Gehirne als Aufgaben. Der klassische Computer hat nur eine Recheneinheit: den Prozessor, auch CPU genannt (Central Processing Unit).Die müssen sich alle Programme teilen.
Die Rechner, der so bei uns zu Hause stehen, sind seit den späten 80er jahren fähig, mehrere Programme quasi gleichzeitig laufen zu lassen, aber das war nicht immer so, die, die noch einen altehrwürdigen Commodore 64, ZX Spectrum, Atari XL/XE oder Schneider CPC zuhause stehen haben, haben es schon mal erlebt, aber sie kennen meist auch nur die halbe Wahrheit.
Nun geht es hier aber um Scheduling, also warum fasel ich hier von Multitasking rum? Nun. Die Sache ist recht einfach: Damit man Multitasking machen kann, braucht man ein entsprechendes Scheduling.
Unter Scheduling (zu deutsch: Terminplanung) versteht man die Planung einer möglichst optimalen Reihenfolge, in der die verschiedenen Programme abgearbeitet werden, die man auf einem Computer startet. Je optimaler das Scheduling funktioniert, desto schneller sieht der Benutzer des Computers ein Ergebnis, wenn er dem Computer eine Aufgabe stellt. So eine Aufgabe kann ein Rechenjob sein, er kann aber auch ein einfacher Mausklick sein. Wer wartet schon gerne lange darauf, dass etwas passiert, wenn man mit der Maus klickt? Niemand. Und auch in der stinknormalen Firma von nebenan muss der Chef immer darauf achten, dass er seine Aufträge rechtzeitig raus kriegt. Egal, ob er nur einen Arbeitsplatz hat oder mehrere, er muss die Ressourcen möglichst optimal verwalten. Und schon sind wir wieder beim Scheduling.
Fangen wir einmal an und überlegen uns, wie das früher war, um zu verstehen, wie es heute gemacht wird.
Ein Programm ist, und das wissen wir spätestens seit Alan Turing und Kurt Gödel, eine einzige Rechenaufgabe, oder, um es mathematisch zu sagen: eine Funktion.
Damals konnten Computer ihre Aufgaben nur hintereinander lösen (das lag weniger am Computer, sondern viel mehr am Betriebsystem, doch dazu komme ich noch). Da Computer damals sehr teuer waren, konnte man nicht jedem, der was ausrechnen wollte, einen eigenen Computer geben, und so reichten die Programmierer ihre Programme damals im Rechenzentrum ein und die Mitarbeiter im Rechenzentrum starteten die Programme hintereinander auf dem Großrechner. Damit das Rechenzentrum besser planen konnten, gaben die Programmierer zu ihren Programmen auch an, wie lange sie schätzten, dass ihr Programm in etwa rechnen würde. Diese Abschätzung des zeitaufwands war damals sehr wichtig, denn schliesslich musste man sich den Rechner teilen und von daher war die Terminplanung von absoluter Wichtigkeit und nicht zuletzt war auch die Reihenfolge entscheidend dafür, ob die Kunden mit der gebotenen Leistung zufrieden waren und das Rechenzentrum mit seiner Dienstleistung Gewinn machen konnte. Leute, die einen eigenen Betrieb haben, kennen dieses Problem nur zu gut. Im folgenden Absatz erkläre ich an einem einfachen Beipspiel eine Möglichkeit, wie man diesem Problem beikommen teilweise beikommen konnte.
Also, wir waren bei unserem Computer, und den Programmen. Der Einfachheit halber, versetzen wir uns zurück in die Schulzeit, genauer: die Grundschulzeit und unseren Computer reduzieren wir einfach einmal auf den Prozessor.
Wie wir also wissen, ist ein Programm nur eine mathematische Aufgabe. Bleiben wir deswegen einfach erst einmal bei der Matheaufgabe, die wir aus dem Schulunterricht kennen: Stellen wir uns vor, unser Schüler (=Prozessor) hätte die Aufgabe, an der Tafel Aufgaben (=Programme) zu lösen. Da unser Schüler noch in der Grundschule ist, sind die Aufgaben einfach. Die Aufgaben sollen aber von den anderen Schülern gestellt werden.
Am Anfang fällt 2 Schülern eine Aufgabe ein: Peter sagt: "Rechne 6*11+20", Kathrin meint: "Rechne 12*3". Als unser Schüler eine Minute gerechnet hat und mitten in der ersten Aufgabe steckt, fällt dem kleinen Nils auch noch eine Aufgabe ein: "Rechne 13+7+20".
Unser Schüler schreibt die dritte Aufgabe unter die anderen beiden und macht in der normalen Reihenfolge weiter. Die Reihenfolge, in der er die Aufgaben löst könnte man also als "First come, first served" bezeichnen, oder: "wer zuerst kommt, malt zuerst". Man redet in dem Zusammenhang auch von dem FIFO-Prinzip (First In, First Out).
Sagen wir, dass unser Schüler für die erste Aufgabe etwa 3 Minuten braucht, für die 2. Aufgabe etwa 2 Minuten und die letzte schafft er in etwa einer Minute. Peter bekommt also nach 3 Minuten das Ergebnis für seine Aufgabe, Kathrin bekommt ihr Ergebnis nach insgesamt 5 Minuten (3min Peter + ihre 2min). Auch Nils wartet 5 Minuten, auf das Ergebnis (nicht 6, denn er stellte sie, als Peter schon eine Minute gerechnet hatte, also nur 2 min Peter + 2 min Kathrin + 1 min von ihm).
Nun sind Peter, Kathrin und Nils aber etwas ungeduldig und fangen an zu maulen, weil sie so lange warten müssen, und es ergibt sich für unseren Schüler die Frage: "Wie schaffe ich es, dass jeder möglichst schnell ein Ergebnis für eine neue Aufgabe sieht?". Er ezählt sein Problem seinem Papa, seines Zeichens Informatiker, und der zeigt ihm einen Trick, der heisst: "Shortest job first", also "die kürzeste Aufgabe zuerst".
Insgesamt braucht unser Schüler natürlich immer 6 Minuten, das ändert sich auch nach dem Prinzip nicht, aber etwas anderes ändert sich und das ist für Computer damals sehr wichtig gewesen:
Als unser Schüler die erste Aufgabe löst, weiss er ja noch nichts von der dritten, also fängt er mit er Aufgabe von Kathrin an, die geht schneller als die von Peter und nach 2 Minuten hat Kathrin bereits ein Ergebnis. Als er eine Minute an Kathrins Aufgabe gerechnet hat, stellt Nils die dritte Aufgabe, die dauert nur eine Minute, also rehnet er die von Kathrin zuende und löst Nils Aufgabe ebenfalls noch vor der Aufgabe von Peter. Nils hat also nach 2 Minuten ein Ergebnis (1 min Rest von Kathrin + 1 min von ihm). Dann erst macht er die von Peter und Peter hat nach 6 Minuten seine Aufgabe gelöst.
Ohne es zu wissen, hat unser Musterschüler bisher gerechnet, wie es ein Computer anfangs auch tat, aber fassen wir diese beiden Arbeitsweisen doch einmal zusammen, und stellen sie gegenüber, damit es etwas übersichtlicher wird. In der folgenden Tabelle sehen wir also, wie lange jeder der Mitschüler auf die Lösung seiner Aufgabe gewartet hat. Die Reaktionszeit, also die Zeit, die zwischen dem Stellen der Aufgabe und der Erledigung vergeht, nennen wir Latenz.
Wie wir sehen, sorgt das Shortest Job First-Scheduling also dafür, dass die durchschnittliche Latenzzeit (die Antwortzeit) kleiner wird. Leute, die viel mit Lieferterminen zu tun haben und sich zur Maxime gemacht haben, alles immer schön der Reihe nach zu erledigen, sollten spätestens in diesem Moment aufhorchen, sofern sie es nicht schon vorher wussten. Hier kann man vielleicht noch etwas von der Informatik lernen.
Na, wenn das so einfach wäre, wäre das ja optimal, aber es gibt da nämlich noch ein paar kleine Probleme:
Zum ersten ist, vor allem bei Programmen, nicht unbedingt klar, wie lange eine neue Aufgabe wirklich dauern wird und somit ist nicht immer klar, wo sie einzuordnen ist. Zum Zweiten kann man noch in einer weitere Falle tappen: Wenn man nämlich eine sehr große Aufgabe zu erledigen hat und ständig neue, kleine Aufgaben eintrudeln, kann es sein, dass unser Kunde mit seinem Riesenauftrag nie an die Reihe kommt. Dieses Problem ist in der Informatik bekannt unter dem Begriff "Starvation" oder zu Deutsch: Verhungern. Was man also braucht, ist ein Mechanismus, der das verhindert. Dazu gibt es viele Lösungsvorschläge, z.B. kann man versuchen, dieses Problem durch Vergabe von Prioritäten zu lösen, durch Bestimmung des Alters einer Aufgabe oder einer Kombination von beidem.
Doch möchte ich es erst einmal bei diesem Beispiel belassen, denn schliesslich geht es in diesem Beitrag auch um Multitasking und dabei um den Versuch, mehrere Programme/Aufgaben scheinbar gleichzeitig zu lösen. Hier sieht die Scheduling-Strategie anders aus.
Multitasking nennt man den Versuch, mehere Programme scheinbar gleichzeitig auf einem Prozessorlaufen zu lassen.
Nun wissen wir aber, dass ein klassischer Prozessor immer eine Aufgabe gleichzeitig lösen kann, ein Problem, das man mit Hyperthreading zwar auf die diversen Funktionseinheiten innerhalb des Prozessors verschiebt, aber das spätestens dort wieder gilt. Also was tun? Denken wir noch einmal an unseren Schüler an der Tafel.
Wir erinnern uns: Am Anfang fiel 2 Schülern eine Aufgabe ein: Peter sagte: "Rechne 6*11+20", Kathrin meinte: "Rechne 12*3". Dieses mal soll unser Schüler Kopfrechnen! Aber damit es nicht so schwer wird, vergessen wir die Aufgabe von Nils und bleiben bei diesen beiden Aufgaben. Dafür meldet Kathrin sich erst, als er schon eine Minute an Peters Aufgabe rumrechnet. Kathrin ist sooo hübsch, aber kann so gemein sein!
Ein gewöhnlicher Schüler grübelt also nach und rechnet 6*1 = 6 und 10* 6 = 60 und danach 6+60 = 66 und zum Schluss 66+20 = 86, und löst so Aufgabe 1 von Peter. Nun macht er sich an Nummer 2: Also rechnet er: 3*3 = 9, 10*6 = 60, addiert die Ergebnisse und bekommt 9+60 = 69, Aufgabe 2 gelöst.
Unser Schüler ist aber nicht gewöhnlich, er will die anderen beeindrucken und so tun, als würde er beides gleichzeitig rechnen können. Aber wie schafft es nun unser kleiner Genius, beide Aufgaben so zu erledigen, dass es scheint, er würde es gleichzeitig tun? Nun, dazu braucht er ein gutes Gedächnis.
Er fängt an, bei Aufgabe 1 zu Rechnen, rechnet 6*3 = 6. Just in diesem Moment hört er Kathrin ihre Aufgabe rufen, also merkt er sich das Zwischenergebnis 6 von Peter und merkt sich auch, wo er gerade in der Rechnung war. Dann rechnet von Kathrins Aufgabe erst einmal 3*3, und merkt sich das Ergebnis 9 und merkt sich ebenfalls, wo er bei Kathrin stehen geblieben ist und kramt die Erinnerung von Peters Aufgabe raus, rechnet dann 10*6, merkt sich auch dieses Zwischenergebnis, und wo er stehen geblieben ist erinnert sich jetzt wieder an das, was er sich bei Kathrin gemerkt hat, rechnet 10*6, merkt sich die 60, holt sich Peters 6 und Peters 60, rechnet 60+6, merkt sich die 66, erinnert sich an Kathrins Aufgabe, rechnet 9+60 und sagt "Kathrins Aufgabe ergibt 69", vergisst alles, was er von Kathrin gemerkt hatte (die Aufgabe ist ja gelöst), erinnert sich an den Stand von Peters Aufgabe, rechnet 66+20 und sagt: "Peter, bei dir ist es die 86". Die anderen Schüler sind schwer beeindruckt und unser kleiner Haudegen hat freien Blick auf die süße Zahnlücke von Kathrin, weil ihr der Mund offen steht.
Ohne es zu wissen, hat unser Schüler genau das getan, was jeder moderne Computer beim Multitasking tut und zwar hat er ein Time sliced Round Robin Scheduling angewandt, wobei hier das wichtige nicht der Round Robin ist, sondern das Time-Slicing, aber dazu gleich mehr.
Das Round Robin Scheduling wird derzeit in fast jedem Betriebsystem erfolgreich eingesetzt. Es ist so einfach, wie effektiv: Mehrere Programme teilen sich einen Prozessor, indem sie sich ständig reihum abwechseln. "Time sliced" bedeutet hierbei, dass die Programme mitten in der Arbeit unterbrochen werden und später da fortgeführt werden, wo man sie unterprochen hat.
Stellen wir uns ein Karussell auf dem Jahrmarkt vor, und stellen wir uns vor, jeder Wagen auf dem Karussell wäre ein Programm, oder sagen wir besser: Ein Prozess. Das Programm, das gerade an dem Kassiererhäschen des Karussells vorbeizischt, ist immer das Programm, das gerade den Prozessor benutzen darf, sprich: es darf dem Kassierer nen Vogel zeigen. Sagen wir also, dass alle Leute in den Wagen still sitzen müssen und sich nur bewegen, wenn sie am Kassenhäschen vorbeifahren.
Aus Sicht des Prozessors (des Kassierers in seinem Häusch) sieht das so aus, als wenn jeder im Wagen sich bewegt, wie in einem Daumenkino, nur dass in jedem Wagen ein eigenes Daumenkino läuft. Der Kassierer sieht also mehrere Programme, die scheinbar gleichzeitig und unabhängig voneinander langsam laufen. Damit sich der Kassierer nun merken kann, wer ihm gerade den Stinkefinger zeigt, und wer ihn einen Kuss rüberwirft, muss er sich den Status jedes Wagens merken, sonst kommt er durcheinander. Nun, beim Prozessor laeuft das eigentlich andersrum, aber das Multitasking bespreche ich in einem anderen Teil genauer. Ich möchte eigentlich auf etwas anderes hinaus: Die Latenzzeiten für jedes eigene Programm.
Es ergibt sich nämlich ein grundlegendes Problem: Wie schnell mache ich mein Karussell?
Eins wollen wir einmal direkt festhalten: jeder Prozesswechsel braucht Zeit, um sich den Status des vorherigen Prozesses zu merken und den Status des nächsten Prozesses zu rekonstruieren, also sich daran zu erinnern, wo der Prozess das letzte mal stehen geblieben war, als er unterbrochen wurde.
Lässt der Kassierer das Karussell schnell drehen, so haben die Insassen kaum Zeit ihre Gesten zu machen, weil der Kassierer (=Prozessor) ständig damit beschäftig ist, diesen Prozesswechel zu machen, oder andersrum: jedes Programm hat nur wenig Zeit zu arbeiten wird also langsamer, dafür kommt es aber oft an die Reihe und die Latenzzeit wird kleiner. Verringern wir die Umdrehungsfrequenz, so kann jedes Programm zwar länger arbeiten, aber jedes Programm muss dementsprechend länger warten, bis es an die Reihe kommt. Damit verlängert sich die Reaktionszeit eines Programms, d.h.: Die Latenzzeit steigt, dafür kann das Programm in seinem Zeitabschnitt mehr tun, ist also schneller fertig mit seiner Aktion. Hier ist es wichtig die richtige Balance zu finden.
Nun, es ist natürlich ärgerlich, wenn die Programme langsam sind, weil häufig Prozesswechsel gemacht werden, genauso ärgerlich ist es, wenn ein Programm träge reagiert. Nun haben wir im Computer mehrere Programme, die unterschiedlich wichtig sind. Ein Programm, dass nur auf eine Eingabe wartet, muss nicht schnell arbeiten, aber es sollte schnell reagieren. Dafür sollte ein Programm, dass gerade heftig rechnet, besser schnell arbeiten und kann ruhig ein wenig träger auf Eingaben reagieren, weil es ja keine Eingaben erwartet. Andere Programme wiederum arbeiten im Hintergrund und sollten die anderen Programme möglichst wenig stören. Um dieses Problem zu lösen, kombiniert man das Round Robin Scheduling mit einem sogenanten Priority-Scheduling. Kurz gesagt: man setzt Prioritäten..
Eine Möglichkeit die Sache mit den Wichtigkeiten zu lösen, wäre doch die Folgende: Man gibt jedem Programm eine Priorität. Sagen wir einfach, es wäre eine Zahl zwischen 0 und 10.
Man arbeitet nun die Programme in der Reihenfolge ihrer Priorität ab. In regelmässigen Abständen unterbricht man das gerade laufende Programm und überdenkt die Sache mit den Prioritäten neu: Zum Beispiel kann man Programmen, die schon recht lange laufen, die Priorität erniedrigen. Und Programmen, die lange nicht rangekommen sind, kann man die Priorität erhöhen, damit sie nicht verhungern. Das klassische UNIX-Betriebsystem hat es so gemacht. Einmal pro Sekunde wurden dort die Prioritäten neu vergeben.
Nun kombiniert man das ganze mit einem Round Robin und das geht so: Programme mit gleicher Priorität steckt man gleichberechtig in einen Round Robin. So garantiert man, dass es mehrere Programme geben kann, die mit höchster Priorität, gleichberechtigt arbeiten.
Wie gewichtet man nun die Prioritäten sinnvoll? Nun, ein Programm, das auf ein Ereignis wartet, oder freiwillig angibt, dass es eine Zeit schlafen möchte, behält seine Priorität, bis es unterbrochen wird, weil es schon x Sekunden mit dieser Priorität gearbeitet hat. Einem Programm, das von aussen eine Eingabe bekommt, erhöht man automatisch seine Priorität (bei einem Schreibprogramm z.B. sorgt das dafür, dass ein Programm, an dem gearbeitet wird, auch schneller reagiert). Ein gutes Beispiel für diese Vorgehensweise ist Windows NT... aber einen hab ich noch:
Hierbei handelt es sich um eine Erweiterung des oben genannten Priority-Schedulings. Um die Reihenfolge und vor allem die Zeit, für die die Programme den Prozessor zugeteilt bekommen, je nach Priorität noch besser zuteilen zu können, teilt man jeder Prioritätsstufe einen eigenen Scheduling-Algortihmus zu. z.B: Die Programme mit höherer Priorität wechseln sich untereinander nach Round Robin-Manier ab, bei der den Programmen viel Zeit zum Rechnen gelassen wird, dafür wechseln sie sich also seltener ab. Die Programme niedriger Priorität laufen z.B. ebenfalls in einem Round Robin, bei dem allerdings den Programmen weniger Prozessor-Zeit gegeben wird. Diese wechseln sich dafür schneller untereinander ab und jedes hat so eine bessere Chance zu reagieren, wenn der User eine Eingabe macht, wodurch sie dann in die höhere Prioritätsklasse gehoben werden, wo sie wieder mehr Rechenzeit bekommen, um die vom Benutzer gewünschte Aufgabe zu erledigen. Natürlich gäbe es noch die Möglichkeit einer bestimmten Prioritätsstufe einen komplett anderen Scheduler zu geben, z.B. First Come - First Served, sofern das für die gegebene Aufgabe sinnvoll ist.