Resource starvation

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (February 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task.

Starvation is similar in effect to deadlock. Two or more programs become deadlocked together, when each of them wait for a resource occupied by another program in the same set. On the other hand, one or more programs are in starvation, when each of them is waiting for resources that are occupied by programs, that may or may not be in the same set that are starving. Moreover, in a deadlock, no program in the set changes its state. There may be a similar situation called livelock, where the processes changes their states continually, but cannot progress. Livelock is a special-case of starvation. In that sense, deadlock can also be said a special-case of starvation. Usually the problems in which programs are perpetually denied of resources are referred as deadlock problems when none of them are changing their states and each of them is waiting for resources only occupied by programs in the same set. All other such problems are referred as starvation.

Starvation is illustrated by Edsger Dijkstra's dining philosophers problem.

The fault lies in the scheduling algorithm. The scheduling algorithm, which is part of the kernel, is supposed to allocate resources equitably; that is, the algorithm should allocate resources so that no process perpetually lacks necessary resources.

Many operating system schedulers have 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) never blocks, 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 avoid any process from being subjected to starvation.

In computer networks, especially wireless networks, scheduling algorithms may suffer from scheduling starvation. An example is maximum throughput scheduling.