Re: What is a livelock? (was: [patch] sys_sync livelock fix)

[David Schwartz <davids@webmaster.com>]

>I still don't get it :-(. When there is more work, this more work
>needs to be done. So, how could livelock be considered a bug? It's
>just overload. Or is this about the work, which must be done _after_
>the queue is empty?

	Livelock situations can differ. One common issue is when you tune your 
ability to handle load only at a certain point and the load level is such 
that you never reach that point.

	Consider:

int work_count;
while(1)
{
 work_count=0;
 while(work_is_still_to_be_done())
 {
  do_work();
  work_count++;
 }
 if(work_count>250)
  create_more_threads();
}

	In this case, you may be so busy doing work that you never look at how much 
work you did and realize it was too much, so the additional threads never get 
created, and so you remain overloaded forever.

	There are other livelock scenarios that don't involve load over what the 
system can actually take, just over what the system is currently tuned to 
take. Any scheme that considers tuning a low priority can get into this kind 
of problem.

	Here's another case:

lock(first_lock);
/* some stuff */
 lock(second_lock);
 while(there_is_work())
 {
  unlock(second_lock);
  do_work();
  lock(second_lock);
 }
 unlock(second_lock);
/* more stuff */
unlock(first_lock);

	In this case, so long as work keeps flowing in and keeps this thread 
saturated, the first lock may never be released. This is true even if there 
are other threads capable of doing this work without holding the first lock. 
Since this thread remains perpetually ready, it may remain perpetually 
scheduled. This is probably the most common type of livelock encountered in 
kernel code.

	DS