Verhungern (Informatik)
Als Verhungern (englisch Starvation) bezeichnet man in der Informatik den Fall, wenn ein Prozess oder Thread keine CPU-Zeit zugeteilt bekommt, obwohl er zur Ausführung bereit wäre. Der Scheduler im Betriebssystemkern sollte idealerweise dafür sorgen, dass dies nicht geschieht und die CPU-Zeit „fair“ zugeteilt wird. Es gibt im Allgemeinen keine ideale Lösung, um Verhungern zu vermeiden, weil ein ideales prioritätengesteuertes Scheduling gerade nicht fair ist.[1]
Wenn Verhungern in einem gleichzeitigen Algorithmus unmöglich ist, wird der Algorithmus als hungerfrei, aussperrungsfrei oder als endlicher Bypass bezeichnet. Diese Eigenschaft ist eine Instanz der Lebendigkeit und ist eine der beiden Voraussetzungen für jeden Algorithmus zum gegenseitigen Ausschluss; das andere ist die Richtigkeit. Der Name „endliche Umgehung“ bedeutet, dass jeder Prozess (gleichzeitiger Teil) des Algorithmus höchstens eine endliche Anzahl von Malen umgangen wird, bevor Zugriff auf die gemeinsam genutzte Ressource gewährt wird.[2]
Terminplanung
Verhungern wird normalerweise durch einen zu einfachen Planungsalgorithmus (englisch Scheduling-algorithm) verursacht. Wenn beispielsweise ein (schlecht konzipiertes) Multitasking-System immer zwischen den ersten beiden Tasks wechselt, während ein dritter nie ausgeführt wird, dann wird dem dritten Task CPU-Zeit gehungert. Der Scheduling-Algorithmus, der Teil des Kernels ist, soll Ressourcen gerecht zuteilen; das heißt, der Algorithmus sollte Ressourcen zuweisen, so dass keinem Prozess ständig die notwendigen Ressourcen fehlen. Viele Betriebssystem-Scheduler verwenden das Konzept der Prozesspriorität. Ein Prozess A mit hoher Priorität wird vor einem Prozess B mit niedriger Priorität ausgeführt. Wenn der Prozess mit hoher Priorität (Prozess A) blockiert und nie nachgibt, wird der Prozess mit niedriger Priorität (B) (in einigen Systemen) nie geplant – er wird verhungern. Wenn es einen Prozess X mit noch höherer Priorität gibt, der von einem Ergebnis von Prozess B abhängig ist, dann wird Prozess X möglicherweise nie beendet, obwohl es der wichtigste Prozess im System ist. Dieser Zustand wird als Prioritätsumkehr bezeichnet.[3]
Moderne Scheduling-Algorithmen enthalten normalerweise einen Code, der garantiert, dass alle Prozesse eine minimale Menge jeder wichtigen Ressource (meistens CPU-Zeit) erhalten, um zu verhindern, dass irgendein Prozess ausgehungert wird. In Computernetzwerken, insbesondere drahtlosen Netzwerken, können Planungsalgorithmen unter Planungsmangel leiden. Ein Beispiel ist die maximale Durchsatzplanung. Hunger wird normalerweise durch Deadlock verursacht, indem ein Prozess einfriert. Zwei oder mehr Prozesse werden blockiert, wenn jeder von ihnen nichts tut, während er auf eine Ressource wartet, die von einem anderen Programm in derselben Menge belegt wird. Auf der anderen Seite befindet sich ein Prozess im Hungerzustand, wenn er auf eine Ressource wartet, die anderen Prozessen kontinuierlich zur Verfügung gestellt wird.[4]
Hungerfreiheit ist eine stärkere Garantie als das Fehlen von Deadlocks: Ein Algorithmus zum gegenseitigen Ausschluss, der einen von zwei Prozessen in einen kritischen Abschnitt zulassen muss und einen willkürlich auswählt, ist Deadlock-frei, aber nicht hungerfrei. Eine mögliche Lösung für den Hunger besteht darin, einen Planungsalgorithmus mit Prioritätswarteschlange zu verwenden, der auch die Alterungstechnik verwendet. Altern ist eine Technik, bei der die Priorität von Prozessen, die lange Zeit im System warten, schrittweise erhöht wird.
Siehe auch
Einzelnachweise
- Baun, Christian.: Betriebssysteme Kompakt. Springer, Berlin / Heidelberg 2017, S. 166 (proquest.com).
- Andrew S. Tanenbaum: Modern operating systems. Upper Saddle River, N.J. : Prentice Hall, 2001, ISBN 978-0-13-031358-4 (archive.org [abgerufen am 17. Oktober 2021]).
- Maurice Herlihy: The art of multiprocessor programming. Rev. 1st ed Auflage. Morgan Kaufmann, Waltham, MA 2012, ISBN 0-12-397795-9.
- M. Raynal: Concurrent programming : algorithms, principles, and foundations. Springer-Verlag, Heidelberg 2013, ISBN 978-3-642-32027-9.