For each car, strategy is

while (have not crossed) {
   if (full)
        take a step back
   else
        go ahead
}

So neither car can go through the crossroad here.

This case is called livelock.

This comment was marked helpful 0 times.

I think you want go ahead inside of the while block.

This comment was marked helpful 0 times.

Livelock is the same as deadlock, in the sense that nothing useful is getting done. However, in livelock, work is being done, but in deadlock, nothing is happening.

This comment was marked helpful 0 times.

@pd43 I think saying that "work is being done" is misleading: it's more accurate to say that in a deadlock, all agents are blocked on a resource (idling), whereas in a livelock, at least one agent is performing an action (usually intended to avoid deadlock).

This comment was marked helpful 0 times.

Livelock occurs less often because it requires both party to take the "back-off" actions simultaneously, which is unlikely due to mechanisms like pipelining and write-back buffering. But in those cases it may introduce inconsistency.

This comment was marked helpful 0 times.

Since there is always at least one agent performing an action, livelock is a lot harder to detect. It appears as though your system is doing useful work, however it continually undoes all the work previously performed.

Is livelock really that much less common? I feel like any situation that results in deadlock could easily be translated into a situation of livelock. Instead of sitting and waiting for a resource, each agent "reverses".

This comment was marked helpful 0 times.

Livelock can also occur with Test&Test;&Set; and exponential backoff when two processors 1 and 2 acquire locks on memory addresses A and B respectively; however, these processors need both locks to make any progress. As a result, both processors will attempt to acquire these locks in exponentially longer times but will fail to do so. Thus, both processors do work of acquiring both locks but neither will acquire them; thus, resulting in livelock.

This comment was marked helpful 0 times.