You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Brian Pane <bp...@pacbell.net> on 2002/02/18 01:25:33 UTC
Request for comments: leader/follower MPM design
Now that APR is beginning to support atomic
compare-and-set (CAS) operations, I decided to
revisit an old idea: use a "leader/follower" design
to improve upon the efficiency of the worker MPM.
The following writeup describes my current design
idea. It's somewhat radical, particularly in the
parts where it tries to detect and correct race
conditions rather than avoiding them. Thus I'd
like to get a second opinion or two, from anyone
who has an interest in concurrent programming
problems and enough time to scrutinize the pseudocode.
Thanks,
--Brian
Leader/follower MPM design
Overview:
--------
Each httpd child process has a fixed number of worker threads.
There is no dedicated listener thread. Instead, the workers
take turns serving as listener. When the current listener
accepts a connection, it picks an idle worker thread to become
the new listener. The idle threads are stored in a stack;
when a worker finishes processing a connection, it pushes
itself onto the stack.
Thanks to IanH for pointing out that this is an implementation
of a leader/followers design pattern,
http://www.cs.wustl.edu/~schmidt/PDF/lf.pdf
Relative to the current worker MPM design, the potential
advantages of this new design are:
* Better cache utilization, because the stack makes it
more likely that a recently active thread will serve
the next request
* An implementation that uses the new APR atomic API
as a more scalable alternative to worker's global mutex
Per-worker data structure:
-------------------------
struct worker_thread_info {
apr_thread_mutex_t *mutex; /* normally locked by this worker, except
* when it's waiting on the condition var */
apr_thread_cond_t *condition_variable;
struct worker_thread_info *next; /* used to chain threads together in
* the idle worker stack (see below)
*/
}
Global data structures:
----------------------
/* The worker that's currently serving as a listener:
* can be in one of three states
* - pointing to some worker thread's info structure
* - NULL: there is no current listener
* - "pending" (points to a sentinel object with a unique address): the
* current listener has just accepted a connection and is in
* the process of selecting a new listener. (This state is
* used to let us detect and correct a rare race condition,
* rather than using a global mutex to prevent it.)
*/
static struct worker_thread_info *current_listener = NULL;
/* A stack holding idle worker threads. While in this stack,
* a worker thread is blocked on its own condition variable.
*/
static struct worker_thread_info *idle_worker_stack = NULL;
Algorithms:
----------
worker_thread()
{
lock(my_mutex); /* will be unlocked only by cond_wait calls */
for (;;) {
/* This thread must wait for its turn to become the listener:
* If there is no listener right now, this thread can become the
* new listener immediately. Otherwise, it must push itself onto
* the stack of idle listeners.
*/
int become_listener = 0;
do {
/* If the current_listener is NULL, replace it with a pointer
* to this thread's worker_thread_info struct
*/
last_listener = atomic_cas(current_listener, this, NULL);
switch (last_listener) {
case NULL:
/* This thread is now the listener */
become_listener = 1;
break;
case pending:
/* Intentional race condition:
* The old listener is in the middle of choosing a new listener.
* To keep things simple, just spin and retry until the old
* listener is finished.
* Note: the 100us sleep isn't strictly necessary. It's just
* here to increase the # of CPU cycles available to the old
* listener so that it can get out of pending state quickly.
*/
usleep(100us);
break;
default:
/* There already is a listener, so push this thread
* onto the idle stack
*/
atomic_push(idle_worker_stack, this);
cond_wait(this->condition_variable, this->mutex);
become_listener = 1;
}
} while (!become_listener);
accept_connection(...);
/* After accepting the connection, check the idle stack in
* hopes of finding another thread to take this thread's place
* as the listener.
* But first, set the current_listener to pending to avoid
* a race condition with any workers that might be trying
* to enter listener state at exactly the same time.
*/
(void)atomic_cas(current_listener, this, pending);
new_listener = atomic_pop(idle_worker_stack);
if (new_listener == NULL) {
/* There are no idle workers right now, so set the
* current_listener to NULL. The first idle_worker
* to finish handling its current connection will
* become the new listener.
*/
(void)atomic_cas(current_listener, NULL, pending);
}
else {
/* Tell the first idle worker to become the new listener
*/
(void)atomic_cas(current_listener, new_listener, pending);
lock(new_listener->mutex);
cond_signal(new_listener->condition_variable);
unlock(new_listener->mutex);
}
process_connection(...);
}
}
void atomic_push(worker_thread_info *stack, worker_thread_info *node)
{
worker_thread_info *prev;
node->next = *stack;
do {
prev = atomic_cas(stack, node, node->next);
} while (prev != node->next);
}
worker_thread_info *atomic_pop(worker_thread_info *stack)
{
worker_thread_info *prev, *node;
do {
node = *stack;
if (!first) {
return NULL;
}
prev = atomic_cas(stack, node->next, node);
} while (prev != node->next);
}
Re: Request for comments: leader/follower MPM design
Posted by Ian Holsman <ia...@apache.org>.
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
>>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.
linux is where the problem lies in general for CAS.
the have a cmpxchg function defined for most systems, which does a long
(max).
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
>
>
Re: Request for comments: leader/follower MPM design
Posted by Greg Ames <gr...@remulak.net>.
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
Re: Request for comments: leader/follower MPM design
Posted by Brian Pane <bp...@pacbell.net>.
Greg Ames wrote:
>Brian Pane wrote:
>
>>Relative to the current worker MPM design, the potential
>>advantages of this new design are:
>> * Better cache utilization, because the stack makes it
>> more likely that a recently active thread will serve
>> the next request
>> * An implementation that uses the new APR atomic API
>> as a more scalable alternative to worker's global mutex
>>
>
> * Fewer context switches?
>
>>worker_thread_info *atomic_pop(worker_thread_info *stack)
>>{
>> worker_thread_info *prev, *node;
>> do {
>> node = *stack;
>> if (!first) {
>>
>
>I assume you mean:
> if (!node) {
>
oops, yes, that should say "node" instead of "first"
>> return NULL;
>> }
>> prev = atomic_cas(stack, node->next, node);
>> } while (prev != node->next);
>>}
>>
>
>I think there's a subtle problem here. I've seen it before on SMP boxes,
>otherwise it would slip right past me.
>
>The line
>
> rev = atomic_cas(stack, node->next, node);
>
>can get pretty hairy.
>
>Assume thread Z is the listener and enters atomic_pop and starts to evaluate
>this line. "node" is A when it starts, and A->next is B when "node->next" is
>evaluated. Then an interrupt happens and thread Z takes a little nap (hence its
>name :)
>
>In the mean time, two other threads enter atomic_pop, and A and B are popped,
>leaving stack pointing to C. In the context of this discussion, I guess the
>threads represented by A and B both get their turn as a listener. Thread A gets
>a request for a tiny .gif, finishes the request and does an atomic_push and
>blocks. Now stack->A and A->next == C. Thread B is off serving a huge file.
>
>Next thread Z wakes up from its nap. It executes the guts of atomic_cas with
>the params it has already evaluated. It succeeds on most platforms because
>"stack" points to A once again, so we swap B into "stack" But node A's next
>field no longer points to B, its next field is now C. Our data structure is now
>hosed.
>
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. But the workaround that you
describe below will help solve another problem in the design:
>I've seen this fixed most often with a monotonically increasing counter in an
>adjacent field to "stack". This is incremented during atomic_pop (or _push).
>The counter and pointer are atomic_cas'ed as a pair. Then it's pretty easy to
>see that things have changed and the loop should start over.
>
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.
--Brian
>RS/6000 and PowerPC have load_and_reserve and store_conditional which lets you
>get by without the counter. In this scenario, thread Z's store_conditional
>would fail even though the value of "stack" is the same as when it started, so
>it knows enough to start over. Perhaps other platforms have something similar.
>
>Greg
>
Re: Request for comments: leader/follower MPM design
Posted by Greg Ames <gr...@remulak.net>.
Brian Pane wrote:
> Relative to the current worker MPM design, the potential
> advantages of this new design are:
> * Better cache utilization, because the stack makes it
> more likely that a recently active thread will serve
> the next request
> * An implementation that uses the new APR atomic API
> as a more scalable alternative to worker's global mutex
* Fewer context switches?
> worker_thread_info *atomic_pop(worker_thread_info *stack)
> {
> worker_thread_info *prev, *node;
> do {
> node = *stack;
> if (!first) {
I assume you mean:
if (!node) {
> return NULL;
> }
> prev = atomic_cas(stack, node->next, node);
> } while (prev != node->next);
> }
I think there's a subtle problem here. I've seen it before on SMP boxes,
otherwise it would slip right past me.
The line
rev = atomic_cas(stack, node->next, node);
can get pretty hairy.
Assume thread Z is the listener and enters atomic_pop and starts to evaluate
this line. "node" is A when it starts, and A->next is B when "node->next" is
evaluated. Then an interrupt happens and thread Z takes a little nap (hence its
name :)
In the mean time, two other threads enter atomic_pop, and A and B are popped,
leaving stack pointing to C. In the context of this discussion, I guess the
threads represented by A and B both get their turn as a listener. Thread A gets
a request for a tiny .gif, finishes the request and does an atomic_push and
blocks. Now stack->A and A->next == C. Thread B is off serving a huge file.
Next thread Z wakes up from its nap. It executes the guts of atomic_cas with
the params it has already evaluated. It succeeds on most platforms because
"stack" points to A once again, so we swap B into "stack" But node A's next
field no longer points to B, its next field is now C. Our data structure is now
hosed.
I've seen this fixed most often with a monotonically increasing counter in an
adjacent field to "stack". This is incremented during atomic_pop (or _push).
The counter and pointer are atomic_cas'ed as a pair. Then it's pretty easy to
see that things have changed and the loop should start over.
RS/6000 and PowerPC have load_and_reserve and store_conditional which lets you
get by without the counter. In this scenario, thread Z's store_conditional
would fail even though the value of "stack" is the same as when it started, so
it knows enough to start over. Perhaps other platforms have something similar.
Greg