lkml.org 
[lkml]   [2002]   [Feb]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: What is a livelock? (was: [patch] sys_sync livelock fix)
Date
On Tuesday 12 February 2002 08:36 pm, Olaf Dietsche wrote:
> Andrew Morton <akpm@zip.com.au> writes:
> > The get_request fairness patch exposed a livelock
> > in the buffer layer. write_unlocked_buffers() will
> > not terminate while other tasks are generating write traffic.
>
> The subject says it: what is a livelock? How is it different
> from a deadlock?

A deadlock is when two or more processes sleep forever, each waiting for
something the other has to release. In a deadlock situation, the dead
processes are not using CPU time.

In a livelock, at least one of the processes is active, and the other process
can only continue if the active one stops. (Sometimes they're both active,
but can never finish what they're doing.)

The sync thing is a good example: sync tries to flush all dirty blocks to
disk and exits when there are no more dirty blocks. But if the system is a
busy server that's constantly generating dirty blocks as fast as they can be
written to disk and keeping the write buffer full, then sync never manages to
empty the buffer completely, and it can be flushing for hours before getting
a lucky break where it can declare victory and exit. A script that calls
"sync" in the middle can get completely blocked, and something else waiting
for that to finish...

Process priority is another common cause of livelocks. One mainframe at MIT
was decomissioned in the early 70's and they found a "run only when idle"
task that had been started around seven years earlier and still hadn't gotten
any time slices because the server had never been completely idle. (The
pathfinder mars probe kept rebooting for a similar reason: a vital system
task was getting starved while it held a semaphore that other stuff needed,
and not scheduling before timeouts caused a reboot. Look up the "priority
inversion" problem...)

This is why even the lowest priority tasks in modern operating systems still
occasionally are guaranteed timeslices and will even pre-empt pretty high
priority stuff if they've been starved long enough. Otherwise, they might
grab some vital resource other higher-priority programs need (sempahore, file
lock, etc) and block with it, and the rest of the system will never be
TOTALLY idle so they can keep important stuff waiting for a very long time.

> Thanks, Olaf.

Rob
-
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/

\
 
 \ /
  Last update: 2005-03-22 13:24    [W:0.172 / U:0.952 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site