Prioritätsumkehrung (Scheduling)
-
Hallo zusammen,
Im Tanenbaum (S. 170 - Sleep und Wakeup) las ich von der Problematik der Prioritätsumkehrung.
Dort heißt es:
Es gibt zwei Prozesse H und L (high prio, low prio). Die Schedulingregeln besagen, dass wenn H ready ist, dieser immer laufen kann.
Wenn sich L in seiner critical section befindet und H ready ist, wartet H (busy waiting).
Zitat Tannenbaum "... da L niemals zum Zug kommt, während H läuft, bekommt L niemals die Möglichkeit, seinen kritischen Bereich zu verlassen. Somit bleibt H für immer in der Warteschleife".
Dabei habe ich folgendes Verständnisproblem: H hat eine höhere Prio, ja. Aber selbst ein Prozess mit hoher Prio bekommt nur ein bestimmtes Zeitquantum vom Scheduler zugewiesen. Irgendwann ist das Quantum abgelaufen und der Scheduler kommt wieder zum Zug und wählt den nächsten Prozess. Muss nicht irgendwann mal wieder L zum Zuge kommen (welcher somit irgendwann seine CS verlässt)? Oder wird H immer wieder die Zeitscheibe zugewiesen, da er höhere Prio hat? Kann ich mir ehrlich gesagt gar nicht vorstellen. Dann würden Low-Prio-Prozesse ja niemals dran kommen (zumindest solange High-Prio-Prozesse existieren).
Oder denke ich gerade in die falsche Richtung?
Danke im Voraus.
Gruß
n2k
-
n2k schrieb:
Oder wird H immer wieder die Zeitscheibe zugewiesen, da er höhere Prio hat?
Ja, genau. So ist es wohl in diesem (vereinfachten) Modell.
In einem echten modenen BS wirds schon ein wenig anders sein, also daß tatsächlich jeder Prozess mal drankommt, um genau das Probem zu lösen.
Eigentlich erwarte ich, daß es schon ein Betriebssystemmittel "critical section" gibt, sodaß H wenn er auf die CritSect wartet, gar nicht drankommt.
-
Du hast das entscheidende doch zu Anfang gesagt:
Die Schedulingregeln besagen, dass wenn H ready ist, dieser immer laufen kann.
Wenn H nun busy-waited, anstatt anderen den Vorrang zu lassen, dann kommt L niemals dran, so dass H für immer wartet.
Oder wird H immer wieder die Zeitscheibe zugewiesen, da er höhere Prio hat?
Genau so ist es.
Kann ich mir ehrlich gesagt gar nicht vorstellen. Dann würden Low-Prio-Prozesse ja niemals dran kommen (zumindest solange High-Prio-Prozesse existieren).
Klar kommen die dran. Dann, wenn Prozesse mit H-Priorität nichts zu tun haben. Ein Programm kann schließlich auch nicht-busy warten.
-
Hallo,
danke euch für die schnellen Antworten.
Ich glaube jetzt habe ich es verstanden.
SeppJ schrieb:
Klar kommen die dran. Dann, wenn Prozesse mit H-Priorität nichts zu tun haben. Ein Programm kann schließlich auch nicht-busy warten.
Stimmt. Man muss hier klar zwischen BusyWait und sleep unterscheiden. Beim sleep wird die Zeitscheibe abgegeben und der Prozess schlafen gelegt. Solange dieser nicht wieder geweckt wird, wird er nicht vom Scheduler "beachtet".
Ich danke für die Denkanstöße
Gruß
n2k
-
Für Priority Inversion braucht man mindestens drei Prozesse, und das geht dann so:
(EDIT: OK, muss mich korrigieren. Auch mit zwei Prozessen mit "sleep waiting" kommt es zu Priority Inversion. Allerdings ergibt sich daraus normalerweise kein pathologisches Verhalten, und daher ist der Fall auch nicht sonderlich interessant.)H = high priority prozess der die CS locken will
M = medium priority prozess der nix locken muss aber viel zu berechnen hat
L = low priority prozess der die CS gelockt hatL kommt nun nie zum zug, weil M die ganze zeit läuft und ihm die ganze rechenzeit weglutscht.
L bekommt daher nie eine chance die CS freizugeben.
Und H, der eigentlich der wichtigste wäre, kommt nie weiter.Daher auch der Begriff "Priority Inversion", da ein Prozess mit niedrigerer Priorität (M) einem mit höherer Priority (H) die Rechenzeit klaut.
Siehe auch Wikipedia, da steht es auch korrekt beschrieben:
http://en.wikipedia.org/wiki/Priority_inversionIch hab' den Tanenbaum selbst nicht und nie drin gelesen, was man so hört soll der ja recht gut sein.
Priority Inversion mit nur zwei Prozessen ist aber einfach nur Quatsch. Wenn das da wirklich so drin steht, dann muss er was ganz schlimmes geraucht haben wie er das Kapitel geschrieben hat, oder einfach krass überbewertet sein.(EDIT: s.o.)
-
Scheint nicht so unüblich zu sein, das Problem mit 2 Prozessen und busy wait auch so zu nennen. Denke, der Tanenbaum hat recht.
Mir gefällt auch diese Auslegung: https://ls12-www.cs.tu-dortmund.de/daes/media/documents/teaching/courses/ss08/ies/downloads/es-marw-5.3-inversion.pdf
-
In dem von dir verlinkten Paper wird die Situation mit zwei Prozessen und "sleep waiting" als Priority Inversion bezeichnet.
Was auch noch Sinn macht, da ja wirklich für die Zeit wo H auf L warten muss, obwohl H Arbeit hätte, das Scheduling invers zur Priorität ist.
Das ist aber einfach so, und auch noch kein besonders interessantes Problem, weil relativ einfach zu lösen: L darf die Resource halt einfach nicht lange gelockt halten.Das interessante, weil oft unerwartete und auch nicht mehr trivial zu lösende Problem ist dann eben das mit >= 3 Prozessen.
(EDIT: Und in dem Paper wird dann ja auch sofort mit der 3-Prozess Variante weitergemacht, eben weil das die Interessante Variante von dem Phänomen ist. Das Beispiel MARS Pathfinder, wo auch drei Prozesse beteiligt waren, wird ja auch erwähnt.)Mit Busy Waiting dagegen ist das Scheduling analog zur Priorität, da ist nix invertiert, demzufolge kann man das auch nicht Priority Inversion nennen. Ist dann eher mit nem Deadlock zu vergleichen.
-
trotzdem googelt priority inversion mit busy wait recht gut.
-
Jo es googelt viel gut was keinen Sinn macht.
Erklär mir wo die "Inversion" bei nur zwei Prozessen mit Busy Wait ist, dann geb' ich mit geschlagen.
Mit > 2 Prozessen, wobei H sleep waitet und nur andere Prozesse busy waiten geht es natürlich. Unter bestimmten Voraussetzungen.
Wobei dann der interessantere Punkt der ist, dass busy waiting (ohne Backoff und ohne Fallback auf sleep Waiting nach ein paar tausend Spins) einfach plem ist. Und nicht dass reines Busy Waiting in ein paar komischen Konstellationen in zusammenhang mit blah und blub zu Priority Inversion führen kann. Darauf wertvolle Vorlesungszeit zu verschwenden halte ich für fragwürdig.
-
Es sind mir zu viele Treffer, um einfach mal anzunehmen, daß alle den Fehler vom Tanenbaum (oder einem früheren Fehlererfinder) abgeschrieben hätten.
-
Vielleicht wird es mangels eines eigenen Namens oft als Priority Inversion bezeichnet, das mag schon sein.
Davon wird es aber nicht richtiger.Es ist einfach nichts invertiert, also ist es auch keine Priority Inversion.
-
Hi zusammen,
interessante Diskussion
Im Buch "Operating System Concepts" von Abraham Silberschatz (auch ein gutes OS Buch) heißt es dazu:
"... assume, we have three processes, L, M, H, whose priorities follow the order L < M < H. Assume that process H requires resource R, which is currently being accessed by process L. Ordinarily, process H would wait for L to finish using resource R. However, now suppose that process M becomes runnable, thereby preempting process L. Indirectly, a process with a lower priority - process M - has affected how long process H must wait for L to relinquish resource R. This problem is known as priority inversion. It occurs only in systems with more than two priorities."
Gruß
n2k
