![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
http://en.wikipedia.org/wiki/Resource_starvation
Starvation is when a process can never because it is waiting for a resource that never becomes available to it.
A special case of starvation is livelock (see below). A special case of livelock is deadlock:
http://en.wikipedia.org/wiki/Deadlock: "A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.
....
This situation may be likened to two people who are drawing diagrams, with only one pencil and one ruler between them. If one person takes the pencil and the other takes the ruler, a deadlock occurs when the person with the pencil needs the ruler and the person with the ruler needs the pencil to finish his work with the ruler. Both requests can't be satisfied, so a deadlock occurs. "
in a deadlock, strictly defined, neither process can change its state. in a __livelock__, any process in the livelocked set can change its state, but they can't "progress". "A real-world example of livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they both repeatedly move the same way at the same time."
See http://en.wikipedia.org/wiki/Deadlock for the Coffman conditions and a discussion on their prevention:
Necessary conditions
There are four necessary conditions for a deadlock to occur, known as the Coffman conditions from their first description in a 1971 article by E. G. Coffman.
1. Mutual exclusion condition: a resource that cannot be used by more than one process at a time 2. Hold and wait condition: processes already holding resources may request new resources 3. No preemption condition: No resource can be forcibly removed from a process holding it, resources can be released only by the explicit action of the process 4. Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds
http://en.wikipedia.org/wiki/Priority_inversion
" In (priority-based) scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. This causes the execution of the high priority task to be blocked until the low priority task has released the resource, effectively "inverting" the relative priorities of the two tasks. If some other medium priority task, one that does not depend on the shared resource, attempts to run in the interim, it will take precedence over both the low priority task and the high priority task.
... The trouble experienced by the Mars lander "Mars Pathfinder"[1][2] is a classic example of problems caused by priority inversion in realtime systems. "
Solns:
Just what it sounds like.
Contrast to fixed-priority scheduling.
"Deadline interchange" is a problem that may occur which is analogous to "priority inversion".
http://en.wikipedia.org/wiki/Busy_waiting
"a process repeatedly checks to see if a condition is true, such as waiting for keyboard input or waiting for a lock to become available.... it is considered an anti-pattern and should be avoided, as the CPU time spent waiting could have been reassigned to another task."
better alternatives: blocking or sleeping
when spinning is appropriate: when the time you will probably need to wait is so short that it would take longer to tell the OS to set up a delay or to block than it would have been just to spin
When locking is implemented by each process just spinning when it wants some resource.
Note that, b/c its locking, there are the usual threats of starvation.
In addition, you gotta watch out for race conditions when acquiring the lock. If you have atomic test-and-set, you can use that
