Event logging
Ian Emmons
In recent months, there have been several discussions about FIFO mutexes in
this newsgroup. (Background: a FIFO mutex is one that guarantees that when
it is unlocked, waiting threads are unblocked in the same order that they
tried to lock it.)
In general, the conclusion of these discussions has been that FIFO mutexes
are hard to implement, as well as unnecessary. However, I have a situation
that, at first glance, seems to require a FIFO mutex. I would appreciate it
if someone out there could show me how to solve my problem another way.
Here is the problem: I have a multi-threaded server application, and I want
it to have a logging service so that I can log interesting events and errors
from the worker threads. In order to keep the worker threads from spending
too much time in the logging function logEvent(), I want to have that
function merely queue the events, and have a separate thread do the actual
I/O to the log file. Now, here's the kicker: I'd like the events to be
written to the log in the same order that the worker threads call the
logEvent() function. How can I accomplish this ordering without putting a
FIFO mutex on the queue?
On Win32 platforms, this is easy. WinNT has an extensible event log
service, which will do all this for me. And if I choose to roll my own (so
it will work on Win95), I can replace the event queue with the logging
thread's message queue (or even it's APC queue), which will efficiently
serialize the events for me.
On POSIX threads platforms, the only idea I've had is to "time-stamp" the
events as they go into the queue, and let the logging thread sort them into
order later. But what can I time-stamp them with that has a fine-enough
time resolution and doesn't cause any threads to block (which potentially
would cause them to be misordered)? Of course, the "time-stamp" doesn't
have to have anything to do with actual time -- it could simply be a counter
that gets incremented for each event. This gets around the resolution
problem, but how to do it without blocking any threads?
Thanks in advance,
Ian
___________________________________________________________________________
Ian Emmons Work phone: (415) 372-3623
i...@persistence.com Work fax: (415) 341-8432
Persistence Software, 1720 S. Amphlett Blvd. Suite 300, San Mateo, CA 94402
Douglas C. Schmidt
In article <331391...@persistence.com>,
Ian Emmons <i...@persistence.com> wrote:
++ In recent months, there have been several discussions about FIFO mutexes in
++ this newsgroup. (Background: a FIFO mutex is one that guarantees that when
++ it is unlocked, waiting threads are unblocked in the same order that they
++ tried to lock it.)
++
++ In general, the conclusion of these discussions has been that FIFO mutexes
++ are hard to implement, as well as unnecessary.
Once you've got features like normal mutexes and condition variables
it's simple to implement a FIFO mutex. In fact, there's one in ACE
that's freely available at:
http://www.cs.wustl.edu/~schmidt/ACE_wrappers/ace/Token.{h,i,cpp}
There's a simple test of this at:
http://www.cs.wustl.edu/~schmidt/ACE_wrappers/examples/Threads/token.cpp
and some documentation is available at
http://www.cs.wustl.edu/~schmidt/ACE-concurrency.ps.gz
This code works portably on Win32 and POSIX platforms once you've
built ACE, which you can get at
http://www.cs.wustl.edu/~schmidt/ACE-obtain.html. In fact, there's
already a multi-threaded logging service in ACE
(http://www.cs.wustl.edu/~schmidt/ACE_wrappers/netsvcs/lib/Server_Logging_Handler.{h,cpp}).
BTW, for a discussion on how to implement FIFO mutexes in Java, you
might want to take a look at an interesting paper called "Specific
Notification in Java" by Tom Cargill
(http://www.cs.wustl.edu/~schmidt/PLoP-96/cargill.ps).
Take care,
Doug
--
Dr. Douglas C. Schmidt (sch...@cs.wustl.edu)
Department of Computer Science, Washington University
St. Louis, MO 63130. Work #: (314) 935-4215; FAX #: (314) 935-7302
http://www.cs.wustl.edu/~schmidt/
Dave Butenhof
Ian Emmons wrote:
> In recent months, there have been several discussions about FIFO mutexes in
I'm not going to get too deep into this discussion yet again, but I
thought I'd correct your summary before anyone gets too confused. What
you've described is, in fact, what the POSIX standard REQUIRES of any
mutex when utilized by threads in the SCHED_FIFO or SCHED_RR scheduling
policy. That is, specifically, "waiting threads are UNBLOCKED in the
same order that they blocked."
The important word, however, (in case you didn't notice my ALL CAPS) is
"unblocked". That is, there's no guarantee at all in POSIX about the
order in which these waiting threads will LOCK the mutex -- only the
order in which they will be released from the mutex wait state
(becomming READY to run, or RUNNING if they preempt the currently
running thread) so that they can CONTEND for the mutex. If the thread
that unblocked the waiter is of higher priority, or on an SMP system
(where another thread, of any priority, may already be locking the mutex
on another processor), then it is not guaranteed to be the next owner of
the mutex merely because it has been waiting longer.
> In general, the conclusion of these discussions has been that FIFO mutexes
> are hard to implement, as well as unnecessary. However, I have a situation
> that, at first glance, seems to require a FIFO mutex. I would appreciate it
> if someone out there could show me how to solve my problem another way.
What you really mean by "FIFO mutexes" (an ambiguous term, given the
precise, and contradictory, definition of FIFO scheduling behavior in
POSIX) is that the order of mutex OWNERSHIP is FIFO. That's an entirely
different game.
On a uniprocessor, there's not much difference as long as the unlocking
thread has lower priority than the locking thread (and they're both
SCHED_FIFO policy). The unblocked thread will preempt the unlocking
thread, and immediately take ownership of the mutex. Of course, once
you've got two threads of differing priority contending for the same
mutex, the chain breaks down -- because when the higher priority thread
unblocks the lower, it won't preempt.
On a multiprocessor, there's no (POSIX) guarantee even when the
unblocked thread has higher priority, because a lower priority thread
could be simultaneously locking the mutex on another processor. It can
be prohibitively (and pointlessly) expensive to prevent that from
happening. (At best, you'll get unproductive extra context switches; in
many cases, it'll require a cascade of very expensive cross-processor
interrupts to reevaluate scheduler state and ensure that everyone's
running the highest-possible priority thread.) While all that overhead
may be good for highly-predictable realtime programming, it's wasted for
the typical concurrent application, which mostly wants throughput
(either compute or I/O). That's why POSIX says that the predictability
rules of realtime priority scheduling don't apply for an "allocation
domain" greater than 1 (that is, on a multiprocessor).
But the fact remains that there are some cases where threads need to
interact "fairly" with each other, and throughput is not the major
consideration. One way (though not necessarily the best) would be some
form of synchronization with "FIFO ownership" characteristics. You can
do this "easily" yourself by having threads queue themselves in order.
There would probably be some value in a new mutex type attribute that
supported FIFO ownership directly. (Maybe.)
Finally, in the case of logging, I'd be tempted to say that two events
that occur so closely together, (that short-term mutex blocking can
cause them to be reversed in the log), are so nearly simultaneous that
their order is essentially random anyway. It may not be worth the effort
to try to maintain an order that is practically imaginary anyway.
/---[ Dave Butenhof ]-----------------------[ bute...@zko.dec.com ]---\
| Digital Equipment Corporation 110 Spit Brook Rd ZKO2-3/Q18 |
| 603.881.2218, FAX 603.881.0120 Nashua NH 03062-2698 |
\-----------------[ Better Living Through Concurrency ]----------------/