Process Starvation

Also called LiveLock ( http://en.wikipedia.org/wiki/Deadlock#Livelock ). When a process is not blocked but doesn't make any progress nonetheless because it repeatedly tries - but is always outcompeted by another process.

---

A situation or construct used in synchronization or locking schemes based on polling, especially LockFreeSynchronization when without hardware support like CompareAndExchange? or TestAndSet?. The idea can be demonstrated with this code fragment...

 function increment( const int * cell, const int sz )
 {
   int ref = *cell + sz;
   *cell = ref;
   while ( *cell != ref )
   {
     ref = *cell + sz;
     *cell = ref;
   }
 }

This code can be used to securely perform serial increments in a multi-threaded environment, so that you don't lose the result of one increment being overwritten by another. Unfortunately, under the right circumstances that might take a very, very long time. One thread might take ages to complete before it happens to not get interrupted between the new assignment and the loop test.

Ugh!!! Even assuming each line is atomic gives the following race condition. (Luckily it won't compile).

a is initially 0. Thread 1 calls increment(&a, 1). Thread 2 calls increment(&a,2). Thread 1 sets ref to 1. Thread 2 sets ref to 2. Thread 1 sets a to 1, checks that a = ref, and exits. Thread 2 sets a to 2, checks that a = ref, and exits.

Also any such code written in a high level language (CeeLanguage, JavaLanguage, CeePlusPlus) is generally broken as well. (See compiler reorderings, single-core single pipe-line hardware reorderings, and cache coherency problem.) The above code only works on a hypothetical machine with a very strict memory model which is basically non-existent. You would need memory barriers inserted in the correct places to make that work in CeeLanguage + Posix, for example.