[e-lang] GridLock

[Kevin Reid]

On Feb 2, 2007, at 4:17, Dr. Pierre Vignéras wrote:
> On Thursday 01 February 2007 23:23, Kevin Reid wrote:
>> On Feb 1, 2007, at 2:01, Dr. Pierre Vignéras wrote:
>>> I have some questions concerning GridLock (mentionned in Event-Loop
>>> Concurrency http://www.erights.org/elib/concurrency/event- 
>>> loop.html).
>>
>> ...
>>
>>> Are GridLocks E related? I mean do we found GridLocks in a  
>>> traditional
>>> thread-based concurrent OO Application?  (I guess yes, and so they
>>> are not E related).
>
>> A program with a gridlock bug has at least one buffer and a  
>> procedure for emptying it which fills some buffer (not necessarily  
>> the same one).
>
> So this means that is it not related to E.

The use of the word is (as far as I know); the occurrence of the  
problem is not.

>> Note that a buffer does not necessarily hold just bits: for example,
>> if a program starts threads which end up waiting for some condition
>> before proceeding, the collection of waiting threads constitutes a
>> buffer.
>
> I don't see where this is different to a deadlock. What are the basic
> conditions for a gridlock (what is actually locking)? In your  
> example, it seems that we have a sort of producer/consumer algorithm.

The difference (as I understand it) between gridlock and deadlock is  
that gridlock involves some resource of which multiple units exist  
(e.g.  space in some buffer or the heap), whereas deadlock results  
from unique objects being unavailable, and there may well be plenty  
of available resources.

> By the way, you use the term gridlock. Why Grid?

Gridlock is originally an English term referring to the equivalent  
situation on the streets of a city, which are often designed as a grid.

"A condition of total, interlocking traffic congestion on the streets  
or highways of a crowded city, in which no one can move because  
everyone is in someone else's way."
-- http://en.wiktionary.org/wiki/gridlock

>>> In the case of a gridlock, can we recover from it at runtime (For
>>> example, by increasing the buffer space and restarting something
>>> (request or thread, ...))?
>
> No reply? ;-)

Increasing space and retrying is equivalent to having had more space  
already.

>>> How to prevent gridlocks?
>>
>> By designing a program so that parts of it which empty buffers can
>> make progress without additional buffer space.
>
> Still not clear to me.

Gridlocks happen when the emptying of some buffer cannot proceed  
without the filling of some buffer, and these dependencies between  
buffers form a loop. If there are no such loops, then there will be  
no gridlock.

-- 
Kevin Reid                            <http://homepage.mac.com/kpreid/>