[svn commit] r365 - trunk/doc

[jimb at red-bean.com]

Author: jimb
Date: Sat Sep  4 00:22:42 2004
New Revision: 365

Modified:
   trunk/doc/locks
Log:
Refine lock discussion.


Modified: trunk/doc/locks
==============================================================================
--- trunk/doc/locks	(original)
+++ trunk/doc/locks	Sat Sep  4 00:22:42 2004
@@ -1,18 +1,29 @@
 * Global ordering of mutexes in the garbage collector
 
 For a program to deadlock with mutexes, there must be a cycle in the
-directed graph of threads formed by drawing edges from thread A to
-thread B whenever A is waiting for a mutex locked by B.
+directed graph whose nodes are threads and which has an edge from
+thread A to thread B whenever A is waiting for a mutex locked by B.
+In other words, there must be some A waiting for some B, who is
+waiting for some C, ... who is waiting for A.  If this were not the
+case, then every chain of waiting threads ends with a thread that's
+not waiting for anyone else.  Since that thread's runnable, it's not a
+mutex deadlock.
 
 The standard way to prevent deadlocks is to declare a partial ordering
-amongst all the mutexes threads might lock.  By definition, partial
-orderings are acyclic; there is no cycle of mutexes such that X < Y <
-Z < ... < X.  Then, we write the code so that threads will never try
-to lock a new mutex Y while holding a mutex X unless X < Y in this
-partial ordering.  If we do that correctly, it becomes impossible for
-a deadlock cycle to form: in such a cycle, each edge in the cycle
-corresponds to a mutex, and the mutexes would form a cycle, too.  But
-if we have respected the rule above, that can't happen.
+among all the mutexes threads might contend for.  By definition,
+partial orderings are acyclic, so there is no cycle of mutexes such
+that X < Y < Z < ... < X.  Then, we write the code so that threads
+will never try to lock a new mutex Y while holding a mutex X unless X
+< Y in this partial ordering.
+
+If we actually do that correctly, it becomes impossible for a deadlock
+cycle to form.  Each thread in such a cycle is holding some mutex X
+while waiting to acquire some other mutex Y.  This wouldn't be
+permitted unless X < Y.  But then walking the deadlock cycle would
+yield a cycle of mutexes X < Y < Z < ... < X.  Which we know can't
+happen, since < is a partial order.
+
+
 
 So, here is our global ordering for mutexes in Minor.
 
@@ -39,6 +50,23 @@
 incoherent_mutex < allocation_mutex
 
 
+One catch to all this is that the proof of freedom from deadlock only
+reassures you if the entire program respects the partial ordering ---
+the user's code as well as Minor.  So it's not sufficient for the
+Minor library to be well-behaved by itself.  In general, we would need
+to include the mutex partial ordering as part of Minor's public
+interface, explain how and when each Minor entry point uses the
+mutexes, and so on.  But that's really hairy.
+
+Fortunately, we can finesse things.  If Minor always releases all its
+mutexes before control leaves Minor code (in addition to respecting
+the rules described above), then the program will never try to acquire
+any non-Minor mutexes while holding any Minor mutexes.  Minor mutexes
+cannot participate in a deadlock cycle.  But note that this means more
+than just releasing your mutexes before you return: invoking a
+callback function provided by the user counts as "control leaving
+Minor code", as does making any system call that could block.
+
 
 ;;; Local Variables:
 ;;; dabbrev-friend-buffer-function: jimb-c-mode-p