Starvation (computer science)

For other uses, see Starvation (disambiguation).

In computer science, resource starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to process its work.[1] Starvation may be caused by errors in a scheduling or mutual exclusion algorithm, but can also be caused by resource leaks, and can be intentionally caused via a denial-of-service attack such as a fork bomb.

When starvation is impossible in a concurrent algorithm, the algorithm is called starvation-free, lockout-freed[2] or said to have finite bypass.[3] This property is an instance of liveness, and is one of the two requirements for any mutual exclusion algorithm; the other being 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.[3]

  1. ^ Tanenbaum, Andrew (2001). Modern Operating Systems. Prentice Hall. pp. 184–185. ISBN 0-13-092641-8.
  2. ^ Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. p. 24. ISBN 9780123977953.
  3. ^ a b Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. pp. 10–11. ISBN 978-3642320279.