httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ian Holsman <>
Subject Re: Request for comments: leader/follower MPM design
Date Tue, 19 Feb 2002 18:25:34 GMT
Greg Ames wrote:
> 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
>>              |                                     |
>>              |                                     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.

linux is where the problem lies in general for CAS.
the have a cmpxchg function defined for most systems, which does a long 

I'll get the 32-bit versions up&running first.. but I don't hold much 
hope of getting a apr-atomic-cas-64 going for all platforms..

> Greg

View raw message