Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!uccba!spca6!kgw2!erich
From: erich@kgw2.bwi.WEC.COM (Eric Hammond)
Newsgroups: comp.os.mach
Subject: summary: timeout on condition_wait() [LONG]
Message-ID: <419@kgw2.bwi.WEC.COM>
Date: 6 Mar 90 17:51:06 GMT
Distribution: usa
Organization: Xetron Corporation, Cincinnati, Ohio
Lines: 143

My thanks go out to those who responded to my post requesting help
in implementing condition_wait()s with timeouts.  In alphabetical
order:

    Eric.Cooper@CS.CMU.EDU
    Richard.Draves@CS.CMU.EDU
    Richard H. E. Eiger <rheiger@ccng.waterloo.edu>
    Alessandro.Forin@SPICE.CS.CMU.EDU
    Arul A. Menezes <arul@Neon.Stanford.EDU>
    Michael_Young@transarc.com

A rough summary of the problem is as follows:

    I need to do a condition_wait() on a condition, but
    want that condition to be signalled after n seconds
    (if and only if it hasn't been signalled already).  Only
    one thread will ever be waiting on this condition,
    and only one thread will ever signal this condition.
    This condition and the waiting thread might dissappear
    after the condition is signalled.  There are multiple
    thread/condition pairs in the same task that need this
    capability.

Following is a list of possible solutions.  Incorporated into
these are summaries of suggestions I've received:

    Let thread A be a thread which wants to wait on the condition.
    Let thread T be a "timeout thread".

    1) Before thread A waits on the condition it forks a new
       thread T.  Thread T sleeps for n seconds then signals
       the condition.

       pro:
           - Simple.

       con:
           - Uses system resources (?): one thread created per
             condition.
           - In my application the condition might have been
             deallocated by the time thread T wakes up.
           - In my application thread A might have decided
             to do another condition wait with another timeout
             while thread T is still sleeping.  Then when thread
             T wakes up it will signal the condition before the
             timeout now in effect.

    2) Same as (1) but add a sequence number to each timeout.
       When thread T wakes up it checks to see if the sequence
       number is the same as when it was forked.  If so, it
       signals the condition.  If not, it simply exits.

        pro:
            - Solves third con in (1).
        
        con:
            - Still uses one thread per condition.
            - Still might signal a deallocated condition.

    3) Create one timer thread T (per task) which will handle
       all timeouts.  This thread will provide services
       by receiving requests on a port.  One request will be to
       start a condition wait with timeout.  Another will be to
       signal a condition.
       
       The timer thread will keep a queue of conditions being
       waited for in order of the time they will timeout.  (Implement
       this in the standard method with each node indicating its
       timeout time and the length of time between its timeout and
       the timeout of the next node on the queue.)  
       
       A timeout will then be added to the msg_receive() call
       corresponding to the timeout of the first condition wait in
       the queue.
       
       When a condition times out it will be signalled and removed
       from the queue.  The same will be done when a request to
       signal a condition is received on the message port.
       
       pro:
           - Uses only one thread per task.
           - Will never signal a deallocated condition.
           - Will never signal a condition after it has already
             been signalled.
       
       con:
           - More complex to implement.
    
    4) Same as (3), but why use condition variables at all?
       Have the condition wait implemented as a msg_rpc()
       and when the "condition" should be "signalled" simply
       reply to the rpc.
       
       pro:
           - Simpler than (3).
    
    5) Don't use another thread at all.  Implement conditions
       using Mach ports and messages.  Here is a correlation
       between the concepts in conditions and what should be
       used to implement them.
       
           condition_t        - port_name_t
           condition_alloc()  - port_allocate()
           condition_free()   - port_deallocate()
           condition_signal() - msg_send()
           condition_wait()   - msg_receive()     [ with timeout ]
       
       pro:
           - Fairly easy to implement.
           - No extra threads.
           - Solves all problems stated above.
       
       con:
           - When nobody is waiting on a real condition
             signalling it has no effect.  Using this
             scheme a message is placed on the port's queue.
       
       This con might be solved a couple of ways:
       
           a. Clear the queue before doing a msg_receive().
              (What about the queue filling up, though?)
       
           b. Since a msg_send() to PORT_NULL has no effect (?)
              store a copy of the name of the allocated port
              and msg_send() to this copy.  Between calls to
              msg_receive() set this copy to PORT_NULL.

And, of course, any of the above should be written in such a way that
the actual implementation is hidden from the user.

I'm going to be attacking the problem using (5) and (5b).  I am not
absolutely sure about the comment I made " a msg_send() to PORT_NULL
has no effect".  The worst I could see it doing would be to return
the "invalid port" error which could be ignored.  I'd like to hear
from someone who knows.

If anyone has further suggestions or comments about these or other
solutions, I am still interested in hearing them.

Eric.
-- 
Eric Hammond @ Xetron Corporation, Cincinnati, Ohio
erich@kgw2.bwi.wec.com