httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Greg Ames <grega...@remulak.net>
Subject Re: Request for comments: leader/follower MPM design
Date Tue, 19 Feb 2002 16:27:25 GMT
Brian Pane wrote:

> Thanks for catching that.  In this particular design, I think
> we'll be safe because only the current listener thread is ever
> allowed to pop from the stack. 

yeah, that occurred to me driving home yesterday.  If we can guarantee there is
only one popper at a time, that problem can't happen.  But if we want a more
general apr_atomic_pop which is safe to use with multiple simultaneous pops,
we'll have to fix it.  

> But the workaround that you
> describe below will help solve another problem in the design:
 
> I like this technique of CAS'ing two variables at once.  In the
> leader/follower algorithm that I originally posted, there is a
> race condition that can occur when all the workers are busy and
> one of them finishes handling its connection at about the same
> time that the current listener accepts a new connection:
> 
> worker becoming idle:                      listener:
>    atomically checks current_listener;        waiting for connection
>      finds that there's already a                   |
>      listener and decides to push                   |
>      self onto idle_workers stack                   |
>    [context switch happens here]                    v
>               |                                [connection arrives]
>               |                                     |
>               |                                     v
>               |                                atomically checks the stack;
>               |                                  but the stack is empty, so
>               |                                  it sets
> current_listener=NULL
>               |                                     |
>               |                                     v
>               |                               [processing the request]
>               v
>     [thread wakes up here]
>               |
>               v
>     atomically pushes self onto stack
> 
> In this scenario, we end up with no listener, but there's
> an idle thread in the stack that ought to have become the
> new listener.  The problem is that the current_listener
> update and the stack push need to happen atomically.
> 
> We could solve this problem by combining the current_listener
> pointer and the top-of-stack pointer into a single 32-bit
> int so that threads can do a CAS on both at once.  Both of
> these pointers can be replaced by thread IDs, so we can
> pack them both into a 32-bit value as long as there are
> fewer than 2^16 worker threads.

That should work.  I've also seen this type of problem solved with the
following:

* Check the other guy's stack
* If empty, add myself to my stack
* Check the other guy's stack again 
* If it's no longer empty, back out and start over. 

Both the producer and consumer have to do this.  In this case, think of
current_listener as being sort of a one deep stack.

I hope we will be able to do 64-bit CAS on most 32-bit platforms.  That would
simplify things greatly.

Greg

Mime
View raw message