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.

Multithreading on Carbon

Apple’s Carbon Multiprocessing Services seems to implement the kind of “Abort” functionality I thought about in the previous blog entry. MPDeleteQueue, MPDeleteSemaphore, MPDeleteEvent, MPDeleteNotification, and MPDeleteCriticalRegion all cause the corresponding waiting task to return with a special kMPDeletedErr code.

Also, there are timeouts supported, returning kMPTimeoutErr when the waiting process times out.

Multithreaded notes

Some material I captured in my Google Notebook having to do with multithreaded programming:

The Little Book of Semaphores is a free (in both senses of the word) textbook that introduces the principles of synchronization for concurrent programming.

The basic functionality supported by semaphores has a certain amount of variability. The Little Book of Semaphores presents a view where only the single increment and decrement can be requested, and blocking always occurs when the resource is not available.

One particular thing that I’ve run into is that the underlying resource might be “irretrievably destroyed”; e.g. a network connection, where a list of packets is controlled by a semaphore, gets permanently closed by an error condition or network operation. Presumably, consumers of packets would wish to be awakened, but would not be able to access the resource the semaphore usually controls, and would have to notice (or be notified through an “abnormal” signalling of the semaphore) that the resource is *not* available, semaphore signal notwithstanding.But at least they are no longer blocking forever.

There are multiple ways this might be achieved

“Signal ‘enough’ to clear out any blocking consumers”

• consumers must be programmed to check an error signal before assuming the resource became available
• must avoid too many other consumers coming in (consumers have to check before and after blocking?)
• arbitrary choice of “maximum”, or access to current count of semaphore (and signalling “go to zero” atomically)

“Signal all currently blocking consumers”

• consumers must be programmed to check an error signal before assuming the resource became available
• must avoid other consumers coming in (consumers have to check before and after blocking?)
• i.e., notion of “currently blocking consumers” must be controlled to keep this operation atomic

“Abort”

• wraps above functionality without explicit consumer checks; except in the sense of checking a return value for the block routine; high-level languages might trigger an exception automatically
• could be automatically triggered by a “destroy” operation on the semaphore
• optionally, producer could leave behind a “explanation”

“Consumers choose to timeout”

• requires arbitrary choice of timeout
• consumer must check for timeout vs. successful acquisition
• producer could also leave behind “explanation”

Some of this came about through David Rager’s response to my question on the OpenMCL-devel list.