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

From: David Schwartz (davids@webmaster.com)
Date: Mon Feb 18 2002 - 17:19:24 EST


>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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/



This archive was generated by hypermail 2b29 : Sat Feb 23 2002 - 21:00:16 EST