[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

non critical-section uses of mutexes



While rereading the discussion archive, it occured to me that my
mailbox example had a nasty bug which is due to the fact that the
mutexes are not used to implement a critical section (of the form:
lock, critical-section, unlock).  I reproduce the code below.

    ; an implementation of a mailbox object of depth one

    (define (make-empty-mailbox)
      (let ((put-mutex (make-mutex)) ; allow put! operation
            (get-mutex (make-mutex (current-thread))) ; prevent get! operation
            (cell #f))

        (define (put! obj)
          (mutex-lock! put-mutex) ; prevent put! operation
          (set! cell obj)
          (mutex-unlock! get-mutex)) ; allow get! operation

        (define (get!)
          (mutex-lock! get-mutex) ; wait until object in mailbox
          (let ((result cell))
            (set! cell #f) ; prevent space leaks
            (mutex-unlock! put-mutex) ; allow put! operation
            result))

        (lambda (msg)
          (case msg
            ((put!) put!)
            ((get!) get!)
            (else (error "unknown message"))))))

When a thread T1 "put!"s an object in the mailbox, T1 becomes the
owner of the "put-mutex" (due to the call (mutex-lock! put-mutex)).
T1 will remain the owner until some thread T2 "get!"s the object from
the mailbox (the call (mutex-unlock! put-mutex) will break the link
from the mutex to T1).

But if after the "put!" T1 decides to terminate and another thread T3
performs a "put!" (before the "get!" by T2) then the put-mutex will be
abandoned when T3 does the "put!", which will raise an "abandoned
mutex" exception.

The problem is that the notion of "mutex ownership" is only meaningful
if the owner of a mutex is the one responsible for unlocking the mutex
(this is the case when implementing critical sections, but not in the
mailbox example).  Also, in the context of a real-time multithreading
system with priority inheritance, you don't want priority inheritance
to occur for mutexes not used in critical sections (because the
"priority boost" of the lower priority thread will in no way help the
higher priority thread to lock the mutex faster).

So I am considering adding a new mutex state that indicates that the
mutex is locked but has no owner, and the primitive
"mutex-lock-anonymously!"  which is like "mutex-lock!" but puts the
mutex in this new state.  The code above would work properly if both
calls of mutex-lock! are replaced by calls to mutex-lock-anonymously!.

Below are the relevant changes to the SRFI document:


<H4>Mutex</H4>

<P>
A mutex can be in one of four states: locked (either owned or not
owned) and unlocked (either abandoned or not abandoned).  An attempt
to lock a mutex only succeeds if the mutex is in an unlocked state,
otherwise the current thread must wait.  A mutex in the locked/owned
state has an associated "owner" thread.  A mutex becomes locked/owned
when a thread locks it using the <CODE>mutex-lock!</CODE> primitive
(the thread becomes the mutex's owner) and when the mutex is created
with a call to the <CODE>make-mutex</CODE> primitive that specifies an
initial owner thread.  A mutex becomes locked/not-owned when a thread
locks it using the <CODE>mutex-lock-anonymously!</CODE> primitive.  A
mutex becomes unlocked/abandoned when the owner of a locked/owned
mutex terminates.  A mutex becomes unlocked/not-abandoned when a
thread unlocks it using the <CODE>mutex-unlock!</CODE> and
<CODE>condition-variable-wait!</CODE> primitives.  Mutexes are not
recursive (i.e. if a thread tries to lock a mutex that is currently
locked the thread will block even if it is the owner of the mutex).
</P>

<DT><PRE>
(mutex-owner <I>mutex</I>)                                   ;procedure
</PRE><DD>

    Returns information about the state of the <CODE><I>mutex</I></CODE>.  The
    possible results are:

       <UL>

       <LI><STRONG>thread T</STRONG>:
           the <CODE><I>mutex</I></CODE> is in the locked/owned state
           and thread T is the owner of the <CODE><I>mutex</I></CODE>

       <LI><STRONG>symbol <CODE>not-owned</CODE></STRONG>:
           the <CODE><I>mutex</I></CODE> is in the locked/not-owned state

       <LI><STRONG>symbol <CODE>abandoned</CODE></STRONG>:
           the <CODE><I>mutex</I></CODE> is in the unlocked/abandoned
           state

       <LI><STRONG>symbol <CODE>not-abandoned</CODE></STRONG>:
           the <CODE><I>mutex</I></CODE> is in the unlocked/not-abandoned
           state

       </UL>

<PRE>
    (mutex-owner (make-mutex))  ==>  not-abandoned

    (define (thread-alive? thread)
      (let* ((mutex (make-mutex thread))
             (result (eq? (mutex-owner mutex) thread)))
        (mutex-unlock! mutex) ; avoid space leak
        result))
</PRE>

<DT><PRE>
(mutex-lock! <I>mutex</I> [<I>timeout</I>])                         ;procedure
</PRE><DD>

    If the <CODE><I>mutex</I></CODE> is currently locked, the current
    thread is suspended until the <CODE><I>mutex</I></CODE> is
    unlocked, or until the timeout is reached if
    <CODE><I>timeout</I></CODE> is supplied.  If the timeout is
    reached, <CODE><I>#f</I></CODE> is returned.  Otherwise the
    <CODE><I>mutex</I></CODE> becomes locked/owned and the current
    thread is its owner.  An "abandoned mutex exception" is raised
    after locking the <CODE><I>mutex</I></CODE> if the
    <CODE><I>mutex</I></CODE> was unlocked/abandoned, otherwise
    <CODE>mutex-lock!</CODE> returns <CODE>#t</CODE>.  It is not an
    error if the <CODE><I>mutex</I></CODE> is owned by the current
    thread (but the current thread will block).

<DT><PRE>
(mutex-lock-anonymously <I>mutex</I> [<I>timeout</I>])              ;procedure
</PRE><DD>

    If the <CODE><I>mutex</I></CODE> is currently locked, the current
    thread is suspended until the <CODE><I>mutex</I></CODE> is
    unlocked, or until the timeout is reached if
    <CODE><I>timeout</I></CODE> is supplied.  If the timeout is
    reached, <CODE><I>#f</I></CODE> is returned.  Otherwise the
    <CODE><I>mutex</I></CODE> becomes locked/not-owned.  An "abandoned
    mutex exception" is raised after locking the
    <CODE><I>mutex</I></CODE> if the <CODE><I>mutex</I></CODE> was
    unlocked/abandoned, otherwise <CODE>mutex-lock-anonymously!</CODE>
    returns <CODE>#t</CODE>.  It is not an error if the
    <CODE><I>mutex</I></CODE> is owned by the current thread (but the
    current thread will block).

<PRE>
    ; an implementation of a mailbox object of depth one

    (define (make-empty-mailbox)
      (let ((put-mutex (make-mutex)) ; allow put! operation
            (get-mutex (make-mutex (current-thread))) ; prevent get! operation
            (cell #f))

        (define (put! obj)
          (mutex-lock-anonymously! put-mutex) ; prevent put! operation
          (set! cell obj)
          (mutex-unlock! get-mutex)) ; allow get! operation

        (define (get!)
          (mutex-lock-anonymously! get-mutex) ; wait until object in mailbox
          (let ((result cell))
            (set! cell #f) ; prevent space leaks
            (mutex-unlock! put-mutex) ; allow put! operation
            result))

        (lambda (msg)
          (case msg
            ((put!) put!)
            ((get!) get!)
            (else (error "unknown message"))))))

    (define (mailbox-put! m obj) ((m 'put!) obj))
    (define (mailbox-get! m) ((m 'get!)))

    ; an alternative implementation of thread-sleep!

    (define (sleep! timeout)
      (let ((m (make-mutex)))
        (mutex-lock-anonymously! m)
        (mutex-lock-anonymously! m timeout)))
</PRE>