„Verhungern (Informatik)“ – Versionsunterschied
| [ungesichtete Version] | [gesichtete Version] |
K AWB clean up patrol. You can patrol as well!, removed stub tag |
Erstellung des Artikels. |
||
| Zeile 1: | Zeile 1: | ||
In der [[Informatik]] ist Ressourcenmangel ein Problem beim Concurrent Computing, bei dem einem Prozess ständig die notwendigen Ressourcen für die Verarbeitung seiner Arbeit verweigert werden. Hunger kann durch Fehler in einem Planungs- oder gegenseitigen Ausschlussalgorithmus verursacht werden, kann aber auch durch Ressourcenlecks verursacht werden und kann absichtlich durch einen [[Denial-of-Service-Angriff]] wie eine [[Forkbomb|Fork-Bombe]] verursacht werden. |
|||
{{short description|Resource shortage in computers}} |
|||
{{other uses|Starvation (disambiguation)}} |
|||
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.<ref>{{Literatur |Autor=Andrew S. Tanenbaum |Titel=Modern operating systems |Verlag=Upper Saddle River, N.J. : Prentice Hall |Datum=2001 |ISBN=978-0-13-031358-4 |Online=http://archive.org/details/modernoperatings00tane |Abruf=2021-10-17}}</ref> |
|||
In [[computer science]], '''resource starvation''' is a problem encountered in [[concurrent computing]] where a [[computer process|process]] is perpetually denied necessary [[Resource (computer science)|resources]] to process its work.<ref>{{cite book |title=Modern Operating Systems |url=https://archive.org/details/modernoperatings00tane |url-access=registration |last=Tanenbaum |first=Andrew |author-link=Andrew Tanenbaum |year=2001 |publisher=Prentice Hall |isbn=0-13-092641-8 |pages=[https://archive.org/details/modernoperatings00tane/page/184 184–185] }}</ref> Starvation may be caused by errors in a scheduling or [[mutual exclusion]] algorithm, but can also be caused by [[resource leak]]s, and can be intentionally caused via a [[denial-of-service attack]] such as a [[fork bomb]]. |
|||
== Terminplanung == |
|||
When starvation is impossible in a [[concurrent algorithm]], the algorithm is called '''starvation-free''', '''lockout-freed'''<ref>{{cite book |title=The Art of Multiprocessor Programming |first1=Maurice |last1=Herlihy |author-link1=Maurice Herlihy |first2=Nir |last2=Shavit |author-link2=Nir Shavit |publisher=Elsevier |year=2012 |page=24 |isbn=9780123977953}}</ref> or said to have '''finite bypass'''.{{r|raynal}} This property is an instance of [[liveness]], and is one of the two requirements for any mutual exclusion algorithm; the other being [[Correctness (computer science)|correctness]]. The name "finite bypass" means that any process (concurrent part) of the algorithm is bypassed at most a finite number times before being allowed access to the [[shared resource]].<ref name="raynal">{{cite book |title=Concurrent Programming: Algorithms, Principles, and Foundations |first=Michel |last=Raynal |author-link=Michel Raynal |publisher=Springer Science & Business Media |year=2012 |isbn=3642320279 |pages=10–11}}</ref> |
|||
Verhungern wird normalerweise durch einen zu einfachen Planungsalgorithmus 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 [[Prozessor|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 verVerhungern. 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. <ref>{{Literatur |Autor=Maurice Herlihy |Titel=The art of multiprocessor programming |Auflage=Rev. 1st ed |Verlag=Morgan Kaufmann |Ort=Waltham, MA |Datum=2012 |ISBN=0-12-397795-9 |Online=https://www.worldcat.org/oclc/812350175 |Abruf=2021-10-17}}</ref> |
|||
Moderne Scheduling-Algorithmen enthalten normalerweise 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.<ref>{{Literatur |Autor=M. Raynal |Titel=Concurrent programming : algorithms, principles, and foundations |Verlag=Springer-Verlag |Ort=Heidelberg |Datum=2013 |ISBN=978-3-642-32027-9 |Online=https://www.worldcat.org/oclc/823641117 |Abruf=2021-10-17}}</ref> |
|||
==Scheduling== |
|||
Starvation is usually caused by an overly simplistic [[scheduling algorithm]]. For example, if a (poorly designed) multi-tasking system always switches between the first two tasks while a third never gets to run, then the third task is being starved of [[CPU time]]. The scheduling algorithm, which is part of the [[Kernel (computer science)|kernel]], is supposed to allocate resources equitably; that is, the algorithm should allocate resources so that no process perpetually lacks necessary resources. |
|||
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. |
|||
Many operating system schedulers employ the concept of process priority. A high priority process A will run before a low priority process B. If the high priority process (process A) blocks and never yields, the low priority process (B) will (in some systems) never be scheduled—it will experience starvation. If there is an even higher priority process X, which is dependent on a result from process B, then process X might never finish, even though it is the most important process in the system. This condition is called a [[priority inversion]]. Modern scheduling algorithms normally contain code to guarantee that all processes will receive a minimum amount of each important resource (most often CPU time) in order to prevent any process from being subjected to starvation. |
|||
== Einzelnachweise == |
|||
In computer networks, especially wireless networks, [[scheduling algorithm]]s may suffer from scheduling starvation. An example is [[maximum throughput scheduling]]. |
|||
Starvation is normally caused by [[deadlock]] in that it causes a process to freeze. Two or more processes become deadlocked when each of them is doing nothing while waiting for a resource occupied by another program in the same set. On the other hand, a process is in starvation when it is waiting for a resource that is continuously given to other processes. Starvation-freedom is a stronger guarantee than the absence of deadlock: a mutual exclusion algorithm that must choose to allow one of two processes into a [[critical section]] and picks one arbitrarily is deadlock-free, but not starvation-free.{{r|raynal}} |
|||
A possible solution to starvation is to use a scheduling algorithm with priority queue that also uses the [[Aging (scheduling)|aging]] technique. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.<ref>{{cite book |title=Operating System Concepts |last=Galvin |first=Peter|year=2010 |publisher=Wiley India Edition |isbn=978-81-265-2051-0|page=193}}</ref> |
|||
==See also== |
|||
* [[Dining philosophers problem]] |
|||
==References== |
|||
{{reflist}} |
|||
{{Processor scheduling}} |
|||
[[Category:Concurrency (computer science)]] |
|||
[[Category:Processor scheduling algorithms]] |
|||
[[Category:Problems in computer science]] |
|||
Version vom 17. Oktober 2021, 16:28 Uhr
In der Informatik ist Ressourcenmangel ein Problem beim Concurrent Computing, bei dem einem Prozess ständig die notwendigen Ressourcen für die Verarbeitung seiner Arbeit verweigert werden. Hunger kann durch Fehler in einem Planungs- oder gegenseitigen Ausschlussalgorithmus verursacht werden, kann aber auch durch Ressourcenlecks verursacht werden und kann absichtlich durch einen Denial-of-Service-Angriff wie eine Fork-Bombe verursacht werden.
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.[1]
Terminplanung
Verhungern wird normalerweise durch einen zu einfachen Planungsalgorithmus 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 verVerhungern. 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. [2]
Moderne Scheduling-Algorithmen enthalten normalerweise 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.[3]
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.
Einzelnachweise
- ↑ 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 (worldcat.org [abgerufen am 17. Oktober 2021]).
- ↑ M. Raynal: Concurrent programming : algorithms, principles, and foundations. Springer-Verlag, Heidelberg 2013, ISBN 978-3-642-32027-9 (worldcat.org [abgerufen am 17. Oktober 2021]).