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 > >
