Verhungern (Informatik)

Begriff und Bedeutung

Verhungern (englisch Starvation) bezeichnet in der Informatik den Zustand, dass ein Prozess oder Thread keine CPU-Zeit erhält, obwohl er ausführungsbereit ist. Aufgabe des Schedulers im Betriebssystemkern ist es, CPU-Zeit und andere wichtige Ressourcen möglichst gerecht zu verteilen. Eine vollkommen ideale Lösung gibt es jedoch im Allgemeinen nicht: Ein streng prioritätengesteuertes Scheduling ist gerade nicht fair, weil Prozesse mit niedriger Priorität immer wieder zurückgestellt werden können.

Bei gleichzeitigen Algorithmen heißt die Eigenschaft, dass Verhungern unmöglich ist, hungerfrei, aussperrungsfrei oder endlicher Bypass. Sie ist eine Form der Lebendigkeit. Für einen Algorithmus zum gegenseitigen Ausschluss sind zwei Voraussetzungen wichtig: Lebendigkeit und Richtigkeit. Endlicher Bypass bedeutet dabei, dass jeder Prozess nur höchstens endlich oft übergangen wird, bevor er Zugriff auf die gemeinsam genutzte Ressource erhält.

Ursachen, Folgen und Vermeidung

Eine Ursache kann ein zu einfacher oder schlecht entworfener Planungsalgorithmus sein. Wechselt ein Multitasking-System beispielsweise immer nur zwischen den ersten beiden Tasks, wird ein dritter Task niemals ausgeführt und erhält keine CPU-Zeit. Scheduler sollen deshalb Ressourcen so zuteilen, dass keinem Prozess die benötigten Ressourcen dauerhaft fehlen.

Besonders relevant sind Prozessprioritäten: Ein Prozess A mit hoher Priorität wird vor einem Prozess B mit niedriger Priorität ausgeführt. Blockiert A nicht und gibt nie nach, kann B in manchen Systemen nie geplant werden und verhungert. Wartet ein noch höher priorisierter Prozess X auf ein Ergebnis von B, kann auch X möglicherweise nie beendet werden. Dieser Zustand heißt Prioritätsumkehr.

Moderne Scheduler enthalten normalerweise Mechanismen, die jedem Prozess eine Mindestmenge wichtiger Ressourcen – meist CPU-Zeit – garantieren. Auch in Computernetzwerken, besonders drahtlosen, kann es zu Planungsmangel kommen; als Beispiel wird maximale Durchsatzplanung genannt.

Verhungern ist von Deadlock zu unterscheiden. Bei einem Deadlock sind zwei oder mehr Prozesse blockiert, weil jeder auf eine Ressource wartet, die von einem anderen beteiligten Programm gehalten wird. Beim Verhungern wartet ein Prozess dagegen auf eine Ressource, die fortlaufend an andere Prozesse vergeben wird. Hungerfreiheit ist daher stärker als bloße Deadlock-Freiheit: Ein gegenseitiger Ausschlussalgorithmus kann stets einen von zwei Prozessen in den kritischen Abschnitt lassen und dabei willkürlich auswählen; dann ist er deadlock-frei, aber nicht hungerfrei.

Eine mögliche Gegenmaßnahme ist eine Prioritätswarteschlange mit Alterungstechnik. Beim Altern wird die Priorität von Prozessen, die lange im System warten, schrittweise erhöht.