Resource starvation
Encyclopedia
In computer science
, starvation is a multitasking
-related problem, where a process is perpetually denied necessary resource
s. Without those resources, the program can never finish its task.
Starvation is usually caused by an overly simplistic 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. For example, if a (not very well 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.
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 prevent 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
.
Starvation is similar to 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 simply keeps getting given to other processes.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, starvation is a multitasking
Computer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...
-related problem, where a process is perpetually denied necessary resource
Resource (computer science)
A resource, or system resource, is any physical or virtual component of limited availability within a computer system. Every device connected to a computer system is a resource. Every internal system component is a resource...
s. Without those resources, the program can never finish its task.
Starvation is usually caused by an overly simplistic 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. For example, if a (not very well 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.
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
Priority inversion
In computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....
. 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.
In computer networks, especially wireless networks, scheduling algorithms may suffer from scheduling starvation. An example is maximum throughput scheduling
Maximum throughput scheduling
Maximum throughput scheduling is a procedure for scheduling data packets in a packet-switched best-effort communications network, typically a wireless network, in view to maximize the total throughput of the network, or the system spectral efficiency in a wireless network...
.
Starvation is similar to deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
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 simply keeps getting given to other processes.