More thinking about multithreaded queueing

Looking back on my previous post about multithreaded queues, and based on a little hacking I was able to do last night on my multithreaded-Lisp-user-mode-Chaos-client, and having read a bit more in the Little Book of Semaphores, (must stop typing 'sempahores'!), in particular the turnstile pattern, and the barbershop problem, there are a few other ways to slice the onion.

1. A "waiting room", i.e., the privilege of blocking on the queue is exclusive. That actually makes a certain amount of sense when, for instance, Chaos packets are already sorted by the destination connection. Does it really make sense for multiple consumers to be concurrently transacting on a single connection? What would make sense, in a C10k kind of way, is rapidly generating server connections in response to RFCs, and handing these connections to waiting server threads. Or, if a connection is known to have independent incoming packets, or is deliberately recycled, connections can queue through a turnstile, each take one incoming packet, then go off to chew on it. I think the mechanism could be a simple lock.


2. "Signal enough" can be expanded to include a "turnstile" approach, where a disappointed consumer signals the semaphore on his way "out" so that the next waiting consumer can be disappointed as well. The idea that the reason for the disappointment should be visible to incoming consumers before they block is really optional. The main reason to prefer it is that, if we believe the "disappointment" is permanent, that we will eventually want to discard the queue, but we presumably cannot do so if consumers can continue to block. That is, if the disposal process must race against the arrival of new consumers. Discarding a queue when the semaphore still indicates the presence of (non-existent) packets and no threads are waiting is OK. Discarding a queue when the semaphore indicates no packets, but threads are blocking requires a well-defined mechanism for blocking threads to cleanly deal with a "killed" semaphore. I.e. the "abort" mechanism.

I really like the Little Book of Semaphores. However, I find it hard to be sure that I truly grasp the concepts. I can read through the solutions to the problems, and understand the discussion, but that doesn't give me a huge amount of confidence in my own solutions to slight variations on the problem. Maybe this kind of programming is simply hard.

I've tried casting some of the solutions in OpenMCL Common Lisp. It's hard to verify that things don't work by accident. One thing that wasn't particularly clear to me is whether it is kosher to do things like

(let ((semaphore (ccl:make-semaphore)))
   (labels ((client-function () #|...|#)
             (server-function () #|...|#))
      (let ((thread1 (ccl:process-run-function #'client-function))
             (thread2 (ccl:process-run-function #'server-function)))
         (#|...some way to wait for both threads to terminate..|#))))

It seems to work, except I haven't yet tried to make a clean "wait for both threads to terminate", and have just waited for the length of a global list to get to a certain point, or similar kludges. The idea, however, that the let can create "global" variables, but the lambdas can have "thread-local" storage, seems not to be formally specified.