Þ   briarpig  » thorn  » demos  » mutex

     When Wil works on projects using the pthread library for threads, mutex, condition variables etc, Wil uses C++ wrapper classes around pthread objects instead of using the naked C api directly.

     Since pthread's api is not used directly, it's feasible to replace pthread infrastructure without something else while keeping the same C++ api. But this isn't the main reason to use C++ wrappers. Wil's main reason to use pthread under a C++ api is to add support for RAII (resource acquisition is initialization) which does a better job of ensuring resources like mutexes are released.

     The same trick is used in more than one place: because C++ destructors for stack-based objects are guaranteed to execute at end of scope — even if an exception causes a non-local exit — Wil can put crucial cleanup code in a destructor to ensure the code is run, even if an exception is thrown.

     When Wil constructs a guard object at start of a scope enclosing a critical section, he is assured the destructor runs when the scope exits, even if exiting from early return or an exception. This is particularly important with a mutex since otherwise deadlock looms in the near future when unlock never occurs.

     However, brevity of code is definitely a reason to use a C++ wrapper since using C calls for mutex is verbose. When Wil changes non-thread-safe to thread-safe, at times much of the work is adding locks in the right places, then unlocking correctly later despite control flow with returns sprinkled throughout.

     A third reason to use a C++ wrapper class for mutex is to add error detection or logging on a per mutex instance basis. Wil usually codes a mutex wrapper so it tracks whether it's currently locked or not, because this is instrumental in detecting a common failure mode: destruction of a mutex while still locked.

     Material on api and use of mutex might seem to implicitly advocate use of threads generally in designs. Please avoid this reading. Instead you should think: if using threads, then use mutex.

     Wil is neither especially for or against the use of threads, and has refactored systems more than one time in each direction: adding threads and removing threads. Whether to use them or not is often a function of circumstances and legacy code. Wil is rarely in a position to do more than influence opinion about thread use in day-job projects. So Wil simply doesn't worry about it either way.

     (When posix threads are used in a project, Wil usually plays a slightly larger role than other developers in making thread-safe shared data structures, because he's had a lot of practice, represents himself as capable, and never shows a trace of fear because he has none. Making data structures thread-safe with high performance is fun, and not very hard. And though complex, even the scary case isn't much trouble: making an old single-threaded system safe under threads.)

     Use of threads and locks does have a performance impact, but not a large one in Wil's experience when an operating system has a good scheduler, and developers are careful to make critical sections small and use high granularity locks. A code model under threads is much less complex than some single-threaded ways to do async code; simplicity pays dividends when less complex code is easier to understand.

     Wil avoids using threads until doing so is the least complex or best performing solution going forward in some problem context. However, usually other developers have trouble following control flow under threads, especially when inter-thread messages sync with single-threaded parts of a system. Explaining threads is time consuming, so Wil hates to spend time on the topic unless paid.

     Wil's preferred thread model uses thread-safe request queues with pools of worker threads to process requests.

     Note sometimes you can use shared mutable data structures under pre-emptive threads without using a mutex, provided you can cope with values changing unpredictably when races occur. Under carefully designed circumstances, you can make a data structure still work (or rather fail to do any harm) when it becomes corrupt. And this sort of structure can skip use of mutex.

     All class names shown on this page are obnoxiously short. Wil feels slightly apologetic about using yx as a name for mutex despite his preference for very short names in þ. However, if yx was not the name of a mutex class, nothing else would use that name and it would lie fallow. And Wil thinks mutex is so important and primitive a two letter class name is appropriate — it's definitely on the list of names you must memorize.

     The most questionable name is yxk for condition, using k for a name beginning with c. Guard classes append g to the end of names for classes that lock and unlock an underlying mutex or condition: yxg guards yx and yxkg guards yxk. Guard classes provide the raii support mentioned earlier, and appear often in code, since one must be constructed each time a mutex or condition is locked.

     The way you use a mutex instance in þ is so terse you'll miss it if you blink. But you recognize it automatically after a little practice. By convention the name guard is often used for guard instances, to remind you what yxg and yxkg mean.

     Here's a very short example of code using a mutex to increment and return a global variable:

     Changes in the value of g_foo_count are thread-safe if they always occur under mutex. In the code shown, only one thread can reach the increment code at a time, so only one thread can increment the integer and the number of calls to incr_foo_count will appear in g_foo_count even when multiple threads attempt to call concurrently. The yxg::~yxg() destructor at the end of the function gracefully unlocks the mutex (cf »).

     A better example of mutex style will be shown later. In general the idea is to identify state that must change atomically under a mutex, then ensure every place this state is read or written occurs under protection by one mutex instance.

     The api for yx is one of the longer ones because it has a lot of error detection support. Here's the state:

     Only x_mutex is necessary because this is what pthread lib uses. (Typically it's large: around 40 bytes in size.) The other two fields are used to detect usage errors that are quite painful to debug without some automated detection: x_use shows whether the mutex is locked and x_tenant shows the thread ID of the locker.

     The most common form of deadlock Wil sees in normal use is locking a mutex in the same thread that already has it locked — so x_tenant is used to log a message saying deadlock is about to occur when a current thread already matches the tenant ID.

     (Mutexes shown here are not recursive locks permitting a current thread to re-lock the same mutex. You can do this with a pthread api by intializing a mutex to allow recursive/nesting locks. But Wil thinks it's always a bad idea: you should work out exactly when you need to lock, and deadlock is the sign you're confused. Developers use nesting lock support as a way of abdicating responsibility to figure out how to lock correctly. Don't give up so easily.)

     Neither value stored in x_use or x_tenant is really thread-safe since they are only written under mutex; readers can see them without mutex. Note the resulting race condition only causes false negatives: a mutex can look unlocked when it actually is not, because x_use is set after locking and is unset before unlocking. However, false positives cannot occur: a mutex is locked when it says it is locked. So destructor yx::~yx() can check if a mutex is locked, and report oops when it occurs (cf »).

     Over several years in systems using Wil's mutex, a backtrace in a mutex destructor saying oops-still-locked occurs every few months, and always reveals a subtle developer error in race conditions shutting down shared objects. Sometimes developers show Wil a system crash trace in a part of the system under Wil's control, so Wil asks, "Is there a log message a little earlier saying 'mutex destroyed while still locked'?" Often this message appears, letting Wil explain one thread A was deleting a global service while another thread B was still inside a mutexed critical section, using data structures being destroyed by thread A. You would never figure this out except by using the kind of mutex code Wil does.

     Wil uses a similar trick in a mock mutex class not shown on this page. Wil has an object with an api like a mutex that doesn't actually lock or provide mutex. Instead it only looks for concurrent access to "critical sections" by more than one thread. Wil uses a mock mutex in places where other developers swear up and down no more than one thread could ever be extant in some scope at the same time, if they forbid use of an actual mutex. When a mock mutex catches and reports the problem (by reporting backtraces for both offending threads) other developers can clean up the problem.

     Now let's look at more of the yx api:

     Normally you won't use xlock() or xunlock() directly because that's what guard class yxg does for you (cf »). The odd looking xlocked2open() is used internally by yxx (cf ») to punch a hole in the mutex; since yxx can only be used inside a critical section to turn a mutex off, the specialized xlocked2open() way to unlock logs an error if a mutex is not already safely under lock.

     Most of the rest of yx is getters, with exception of nested class yx::Xcut shown a little further below.

     The following nested class is mainly used internally by condition class yxk (cf ») because the nature of a condition variable is such that signaling another waiter on a condition variable allows another thread to lock a mutex while still inside the scope of the signalling threads critical section. Unless x_use is turned off in this context, a spurious error message will be logged about a mutex already looking locked. (In other words, the way x_use detects locking errors is slightly broken in terms of reporting false positives without using yx::Xcut to fix the problem.) Wil found this out the hard way. The issue is trivial, but seeing how to squelch false positives would confuse you if Wil didn't include this part of the api.

     Okay, now let's turn back to implementation starting with construction and methods using phtread's C api.

     Obviously you can see no attributes are used when constructing a mutex. If you prefer some other way to init your mutexes, then add it here. We also mark the mutex as unused (free) with no current thread ID. What about destruction?

     You also want a backtrace to appear every place a message is logged above, because you'll want to know exactly where you are in the call stack when this happens. Every message is bad. An assert early in development might also help. But you should not deploy with asserts still in place, because you are likely to hit them, and you'll get slightly more information in the log if you let the process keep running.

     Incidentally, you can work out from first principles that both constructor and destructor should execute single threaded because no other thread should be able to access yx at that time. If you destroy a mutex when another thread is still able to reach it, then you have a problem you must fix. A message when a mutex is still locked when destroyed aims specifically to show such conflict.

     Let's go onto the meat. Here's where we lock:

     The self-deadlock check is often helpful. Wil has been thanked many times for putting it there. (Note cost of calling pthread_self() approaches zero; you should tread it as zero cost.) The values of x_use and x_tenant are set only after the lock is held. No other thread can be setting them at the same time.

     However, nothing stops another thread from pre-empting this one just after getting the lock and before setting x_use and x_tenant. So this mutex could look unlocked very briefly after it's locked. This is a false negative: this api can say a mutex is unlocked when it's not. We only take care to avoid false positives.

     Unlocking is the next most important method:

     Since x_use and x_tenant are cleared before unlocking, when we still have mutex, we ensure that marked locked really means actually locked (though the reverse need not be true); thus we prevent false positives.

     Other methods are less important. Here's the wrapper for attempted locking which fails if the mutex is already locked, rather than blocking until it can be acquired:

     Using the pthread api only, you can test whether a mutex is already locked as shown below. But this only tells you if it was locked right when you asked — status can reverse by return time.

     Here's a variant of basic xunlock() which first checks whether the mutex is locked:

     Wil uses xlocked2open() in places where a mutex is assumed already locked, and the idea is to unlock before later re-locking. If you're the one holding a mutex and it says it isn't currently locked, that would be a problem. (Wil encapsulates this specialized behavior in class yxx, cf », punching a nested hole in a mutex.)

     When the mutex isn't locked as expected, here's how xbadheld() reports a problem:

     Note the use of global count _bad_mux_held_count of such occasions, which itself is not thread-safe because it's not covered by a mutex. This is one of many examples of such global counters: Wil doesn't care if race on update rarely loses a count update. The count is only vaguely informative; exactness doesn't matter.

     Which uses _use_name() to fetch names of use enums:

     Okay, now what's left? Just a few methods logging messages when the current value of x_use is unexpected:

     Note though xlock() and xunlock() are public methods, you should almost never use them directly. Instead you should use a guard class like yxg shown below.

     This section shows guard class yxg which handles most normal lock/unlock use of mutex in a RAII safe manner.

     Perhaps you expected something more involved. The mechanism is actually trivial when you take guaranteed destructor execution for granted: yxg guarantees a mutex is locked during the scope of one instance lifetime. All you do is declare one at the start of the scope in which you need mutex held. Destruction and mutex release occur when the scope exits.

     Under some circumstances, to make the scope as small as you need, you can add {} curly braces around exactly that scope you want protected, to ensure destruction occurs promptly at the closing curly brace and no later.

     For example, what happens when you need to hold two mutexes in virtually the same scope? What if you want to ensure release order occurs exactly opposite to lock order, and you can't recall rules for destructor order? Just use explicit curly braces to force explicit order. (Add warning comments about order significance.)

     Class yxx is basically the opposite of yxg: it unlocks a mutex on creation and relocks it on destruction. The name is a bit arbitrary, but more descriptive names tend to create verbal distractions. (Wil understands the second x to mean max or extent indicating the limit of the mutex; so the name means something like mutex extent.)

     Instances of yxx are expected to only appear on the stack, and only in the scope of yxg earlier on the stack, so a lexically scoped hole is punched in the mutex scope created by yxg.

     Using this behavior would only make sense in exceptional circumstances, which won't be explained here. If you can't think of a good use, then don't use it. Wil has used yxx before when resources acquired had a well-defined lexical scope best matching a yxg on the stack for the duration; but in the middle, Wil had a phase when the mutexed resource was not actually used, and other threads needed to reach the inner scope. Let's just say it was complex.

      However, if you use yxx to punch a hole in mutex, bear in mind it will behave like two different locks with different critical sections. It will only be safe to do this if no condition protected by mutex need survive across unlocked scope of yxx.

     Wil stripes both mutex yx and read-write lock yrwl (cf ») when higher granularity is needed. Given a large population of objects needing mutex (or shared-read/exclusive-write access) Wil often uses one mutex or lock to protect more than one object. This practice is called striping when each object is associated with exactly one particular mutex or lock. The purpose is to avoid using just one mutex (or lock), and yet avoid the space cost of having one separate mutex (or lock) for every single thread-safe object involved.

     A pthread mutex instance is large and Wil makes it even larger by adding several bytes more space to track use and locking thread ID. For a population of tens or hundreds of thousands of thread-safe objects, one mutex apiece would use quite a lot of space unnecessarily.

     When Wil uses posix threads, he rarely uses more than a few dozen thread instances. (The "correct" number of threads to have in a worker thread pool is one thread per CPU, and one more thread per each concurrent blocking operation you might have at one time. The goal is to keep each processor busy, so more threads are unnecessary. However, if threads make blocking calls, a blocked thread won't keep a processor busy. So for an expected highwater mark of N simultaneous blocking operations, you need N more threads.)

     But compared to a count of threads in the dozens, Wil might have tens of thousands (or millions) of thread-safe objects needing a mutex or lock. One mutex each would be overkill because there aren't many threads — you only need enough mutexes so it's relatively unlikely two threads will try to lock the same mutex for different objects. So just an order of magnitude more mutexes than threads is enough.

     Wil assigns each object to a stripe protected by one mutex (or lock), usually by hashing the object's index or address in some simple but fast way. Then for a total of M mutexes, the mutex associated with hash H is just the mod: M % H. Objects in the same stripe use the same mutex. But with many more mutexes than threads, on average you'll rarely have contention on a mutex. And all you really need is safety without contention.

     (Unless QA folks write a degenerate test case where thousands of connections all attempt to read one single thread-safe object all at the same time. And then you should have been using a read-write lock instead of mutex to support shared read access.)

     Pick a prime number like 911 for the number of mutexes, so a mod distributes with fewer collisions. Make sure it's more than ten times the maximum number of threads.

     When Wil adds new locks in a multi-threaded system (or studies locks in an old system) a question about average latency to acquire a lock always comes up. Folks suspect each lock might throttle app or server performance. And a centrol lock everyone locks all the time with high frequency? This lock gives everyone hives.

     What does Wil do?

     Wil measures latency to lock a mutex directly, by building this feature into specific new types of guard class. Of course such code requires a specific time api, so the code to do this will not be shown here. (But it might appear in a future time demo.) Wil usually measures latency to lock every single occasion by reading a hardware register with inline assembler, which costs virtually nothing to do.

     All that's necessary is capturing a timestamp before locking and after locking, then subtracting before converting to units you want — Wil usually wants microseconds. Wil captures the count, sum, and sum of squares in some global stat so latency to lock a particular mutex can be summarized on demand.

     But what you really want to do is somewhat more complex: a window of stats covering recent history should be maintained separately, in case the latency to lock has been trending in some bad direction. Bad news might be overwhelmed by averages over a long period of time.

     In addition, Wil wants to capture the longest latency ever seen. For example, did your server ever wait several seconds to acquire a mutex? That would be bad even if it happens very rarely.

     (In fact, just spending 100% of all cpu cycles for several seconds is enough to make traffic bounce and back off if network traffic cannot be serviced fast enough, even if you don't have the server literally waiting on a mutex for the duration.)

     "Where's your sample thread pool code?" wondered Stu.

     "In the future thread demo," replied Wil.

     "I'm sure I know the answer already," Stu disclaimed, "but what do you mean by thread pool?"

     "It's a set of threads serving requests from a request queue," explained Wil. "All you need is a queue — like yxlqt shown column right — and a set of N threads trying to pop requests."

     "Where do the threads come from," Stu asked. "Are they threads I create? Do I define them?"

     "Yes, you make them," Wil confirmed. "When you spawn a new thread using the posix api, you provide a starting method for the thread to call once up and running. You just need to loop popping requests and replying however you like."

     All this code is available only under the BriarPig mu-babel license described fully on the rights page. You do not have permission to reprint this page in any way. No feeds or repackaging is allowed. You can link this page if you want folks to read it.

     thorn: todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack, atomic, lock, mutex « Þ, thread, map, meter, list, iter, ctype

     (mu: toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile)

     Some demos are stubs: todo is a demo guide. See toy for mu updates on language pages; names introduces naming schemes.

     Posix threads also have an api for condition variables, which Wil wraps in a C++ class named yxk to mean mutex condition, which requires an instance of yx to provide mutex support for the condition variable. You need a constructed instance of a yx mutex to instantiate a yxk condition.

     Integer member k_live is equal to e_klive (a magic signature) after construction and before destruction. The actual pthread condition state is k_cond, which gets passed to the pthread lib api. And k_mutex is the mutex associated with condition variable k_cond.

     The wait and timedwait operations can only be done with the associated mutex locked, as you can see when reading the man pages for pthread_cond_wait() and pthread_cond_timedwait().

     Member k_mutex is a reference to a mutex because embedding a mutex instance inside condition yxk would cause a complication when multiple condition variables need to use the same mutex, such as when implementing read-write locks (cf »).

     Above you see api to make and destroy yxk conditions, then get the mutex via kmutex(), or check it for liveness.

     The rest of the condition api is just the same as the api of pthread conditions, which you can learn by reading man pages. But since you aren't expected to read docs elsewhere to use þ interfaces, the comments below tell you how the methods work.

     Now the postcondition described for wait() and timedwait() might confuse you. What does that mean? Well, you lock the mutex first before calling these methods (normally using guard class yxkg, cf »). Locking before call is a pre-condition. But if you need to wait on the condition variable (because the condition isn't true yet), then pthread lib releases the mutex and blocks your calling thread until the condition is indicated by signal or broadcast. And pthread lib will always relock the mutex before returning from kwait() and ktimedwait(). So then: you lock the mutex before calling, and it will still be locked on return; but in the middle it can be released if you block.

     (Remember how yx uses member x_use to keep track of whether the mutex is locked or not? Well, the mutex can be released in kwait() and ktimedwait() so the mutex is always marked unlocked during wait() and timedwait() because we don't know, and we insist on avoiding false positives when we test for mutex being locked. Sounds tricky, right?)

     Construction installs the right magic signature and initializes the k_cond pthread condition. Destruction destroys the k_cond pthread condition and complains about any errors seen:

     Here's how a bad magic signature is logged:

     Logged errors include string values for errno, using the re-entrant version when possible. (Old standard strerror uses static space that might get clobbered under races.) In both methods, backtraces should accompany logged messages, but a non-standard backtrace api hasn't been shown yet.

     The rest of this section wraps the pthread condition api. If at least one thead is waiting on the condition then ksignal() wakes only one:

     Note ksignal() does nothing if no thread currently waits on the condition. Use kbroadcast() below when more than one thread should awake when the condition changes — all threads waiting on the condition are woken by kbroadcast() (inefficient if most threads just go back to waiting).

     If you need to wait indefinitely for a signal or broadcast, use kwait() to block the current thread until some other thread signals or broadcasts. Note when kwait() returns you'll need to recheck whether the situation you wanted is present, and perhaps wait again if it isn't.

     Both kwait() and ktimedwait() require a locked mutex. You can use yxg to guard the cond's mutex, or you can simply use a guard specific to yxk instead: see yxkg in the next section (cf »). You can see examples of kwait() use in the implementation of read-write lock yrwl (cf »).

     Use ktimedwait() when you're not willing to wait forever. You can specify a max time to wait in seconds. If neither a signal nor broadcast has woken your thread by then, ktimedwait() returns ETIMEDOUT.

     You should make calls to ktimedwait() and kwait() only inside the scope of a yxkg guard instance for the condition variable, because this will lock the mutex for you.

     The preferred way to guard condition yxk is using yxkg:

     Of course the actual work is done by yxg (cf «).

     This section shows a practical application of yxk condition variables. Wil uses this yrwl (read write lock) class whenever mutex yx is too strong because multiple readers are not only okay, but actually essential.

     Other than constructor and destructor, you don't use the public api directly. Instead you use a guard to establish either a read lock or a write lock, using a yrlg read lock guard for shared read access, or else a ywlg write lock guard for exclusive write access. Here's the read lock guard:

     Of course the write lock guard looks very nearly the same, other than replacing read with write in each spot:

     Constructing yrwl is interesting because mutex l_x must be initialized first, and it's passed to both the condition variables l_rcond and l_wcond:

     When any of the counters is decremented, this is done by _down() to centralize logging underflow (subtracting one more than exists).

     Now let's start the interesting methods which lock and unlock for readers and writers. The basic ideas to remember are these:

• Any number of shared concurrent readers can lock.
• At most one exclusive writer can lock.
• Each reader must wait for writers to depart.
• Each writer must wait for everyone to depart.
• You must choose a reader or writer preference.

     The current code favors letting another reader enter over a writer; this is called read priority. The current readLock() code allows readers to starve writers, which might not suit your needs. To vary this strategy Wil can add a yrwl bool member indicating whether reads or writes take priority.

     Because counts of readers, writers, and waiters of both sorts are used only when the mutex is locked, yrwl assumes these values can be examined freely to make all decisions, provided the numbers are always correct. (Which they should be if mutex discipline is done right.)

     These methods first lock mutex l_x with a yxg guard instance, locking the mutex for the rest of the scope of each method. Note locking a mutex is rather cheap when no contention is present, and when uncontended locking does not provoke context switches. (Some systems context switch eagerly for fair scheduling, with potentially unpleasant consequences.)

     With no writers (l_writers is zero) readLock() just bumps the count of readers and lets the current thread through. But when a writer is known, the count of waiting readers (like the current thread) is bumped and readLock() waits on the condition saying reads are okay. When no writer remains _down() undoes the earlier increment of read waiters.

     To prioritize letting waiting writers stall new readers, we could also make readLock() wait if l_w_waiters's count of write waiters is nonzero.

     When a reader unlocks with readUnlock() above, the first step is dropping the count of readers with _down() (which logs on underflow: the count of readers had better be positive here). If any writer is waiting and no readers remain, readUnlock() signals a write condition to wake a writer.

     Because writers are exclusive, only one can hold the lock at once, so writeLock() waits on a write condition when any readers or writers currently hold the lock. If waiting is necessary, the l_w_waiters count of waiting writers is bumped before the wait to ensure another thread signals the write condition on lock exit. When the wait is over a count of writers must be zero; then the count is set to exactly one to account for the current thread.

     When a writer unlocks with writeUnlock(), the count of writers holding the lock must be exactly one for the current thread alone. So the count is set to zero before signalling any waiting reader or writer. If one or more readers are waiting, they are woken first with a broadcast, and then any waiting writer is signaled. This order favors readers over writers and should be reversed if we later want to favor writers over readers.

     Here's an implementation of a thread-safe request queue for driving a thread pool. This is just a blocking queue, and in day jobs Wil usually names a class similar to this one BlockingQueue. But here Wil uses an obnoxiously short letter-coded name: yxlqt meaning mutexed (STL) list queue template.

     Another version of this class named yxqt — avoiding STL — might appear in a future list demo, using queues with more efficient intrinsic links, unlike STL lists using extrinsic links (STL allocates space for each member pushed). Wil prefers to avoid STL as much as possible when time for space allocation might be a nuisance. But in day jobs, Wil just asks folks, "Do you want me to use STL?" When the answer is yes, you get code something like that shown below.

     And conveniently for this demo, Wil can assume you're familiar with STL to simplify this code sample.

     Note this yxlqt class starts with a nested struct of statistics that can be returned from thread-safe getter qstats().

     (As a consequence of defining yxlqt as a template, all methods are inlines, because the compiler needs to see all the code to specialize methods for any given type T. It might seem odd to see complex inline methods, but it's normal for C++ templates.)

     All the state is shown above. The queue itself is stored in q_list. A list length equal to q_list.size() is maintained independently in q_n.s_len because size() in STL lists is a linear operation: it actually walks the list to count the members. (Don't believe me: read web pages discussing splice and size operations in STL lists.)

     Now here's the public api — all methods are inline:

     Getting all stats with qstats() is more useful than getting length alone with qsize(), so the latter is defined more to increase clarity than anything else. Mutex here and in all methods is handled just by declaring a guard at start of each scope needing mutex.

     Length stats are maintained after pushing a new T request. The condition saying "contains a request" is signaled only when a count of waiters is nonzero.

     When the queue is empty, qpop() blocks the calling thread until a T request is pushed, by waiting on the condition. Each time through the loop, waiter count q_n.s_waiters is bumped once before the wait to ensure qpush() signals after push.

     When the queue has a request to pop, qpop() asserts the length is nonzero and maintains the length stat after popping. When the length becomes quite short (two or less), qpop() asserts the actual q_list size equals the separately maintained q_n.s_len. Wil thinks it's okay to call STL's linear size() when cost is constant.

     The final method is a non-blocking version of qpop() so a caller can pop a request if one is present without being forced to block until a request arrives if the queue is empty.

     When the queue is empty, qtrypop() makes an empty request and returns that, implicitly assuming an empty constructor for a T request creates a value the caller can distinguish from a useful queued request. But this is up to the designer of type T.

     The following code sample shows use of the queue api assuming only one thread (it avoids a blocking call, which would hang). Hypothetical struct yreq is used as request type T:

     Type yreq converts to and from int; an empty value is negative so we can see if qtrypop() returns an empty value. The following code pushes two values, then pops two before a try-pop of a third value, then prints the popped values along with a couple stats:

     The following appears on stderr as output: