|
Neutrino provides the POSIX-standard thread-level
synchronization primitives, some of which are useful even between threads in different processes. The
synchronization services include at least the following:
| Synchronization service
| Supported between processes
| Supported across a Neutrino LAN
|
| Mutexes |
Yes |
No |
| Condvars |
Yes |
No |
| Sleepon locks |
No |
No |
| Reader/writer locks |
No |
No |
| Semaphores |
Yes |
Yes (named only) |
| FIFO scheduling |
Yes |
No |
| Send/Receive/Reply |
Yes |
Yes |
| Atomic operations |
Yes |
No |
 |
These synchronization primitives are implemented directly by Neutrino, except
for:
- sleepon locks and reader/writer locks (which are built from mutexes and condvars)
- atomic operations (which are either implemented directly by the processor or emulated in the
kernel).
|
Mutual exclusion locks
Mutual exclusion locks, or mutexes, are the simplest of the
Neutrino synchronization services. A mutex is used to ensure exclusive access to data shared between threads.
It is typically acquired (pthread_mutex_lock()) and released (pthread_mutex_unlock()) around the
code that accesses the shared data (usually a critical section).
Only one thread may have the mutex locked at any given time.
Threads attempting to lock an already locked mutex will block until the thread is later unlocked. When the
thread unlocks the mutex, the highest-priority thread waiting to lock the mutex will unblock and become the new
owner of the mutex. In this way, threads will sequence through a critical region in priority-order.
On most processors, acquisition of a mutex doesn't require
entry to the kernel for a free mutex. What allows this is the use of the compare-and-swap opcode on x86
processors and the load/store conditional opcodes on most RISC processors.
Entry to the kernel is done at acquisition time only if the
mutex is already held so that the thread can go on a blocked list; kernel entry is done on exit if other
threads are waiting to be unblocked on that mutex. This allows acquisition and release of an uncontested
critical section or resource to be very quick, incurring work by the OS only to resolve contention.
A non-blocking lock function (pthread_mutex_trylock())
can be used to test whether the mutex is currently locked or not. For best performance, the execution time of
the critical section should be small and of bounded duration. A condvar should be used if the thread may block
within the critical section.
Priority inheritance
If a thread with a higher priority than the mutex owner
attempts to lock a mutex, then the effective priority of the current owner will be increased to that of the
higher-priority blocked thread waiting for the mutex. The owner will return to its real priority when it
unlocks the mutex. This scheme not only ensures that the higher-priority thread will be blocked waiting for the
mutex for the shortest possible time, but also solves the classic priority-inversion problem.
The attributes of the mutex can also be modified (using
pthread_mutex_setrecursive()) to allow a mutex to be recursively locked by the same thread. This can be
useful to allow a thread to call a routine that might attempt to lock a mutex that the thread already happens
to have locked.
|
Recursive mutexes are non-POSIX services -
they don't work with condvars. |
Condition variables
A condition variable, or condvar, is used to block a thread
within a critical section until some condition is satisfied. The condition can be arbitrarily complex and is
independent of the condvar. However, the condvar must always be used with a mutex lock in order to implement a
monitor.
A condvar supports three operations:
- wait (pthread_cond_wait())
- signal (pthread_cond_signal())
- broadcast (pthread_cond_broadcast()).
|
Note that there's no connection between a condvar signal and
a POSIX signal. |
Here's a typical example of how a condvar can be used:
pthread_mutex_lock( &m );
. . .
while (!arbitrary_condition) {
pthread_cond_wait( &cv, &m );
}
. . .
pthread_mutex_unlock( &m );
In this code sample, the mutex is acquired before the
condition is tested. This ensures that only this thread has access to the arbitrary condition being examined.
While the condition is true, the code sample will block on the wait call until some other thread performs a
signal or broadcast on the condvar.
The while loop is required for two reasons. First of
all, POSIX cannot guarantee that false wakeups will not occur (e.g. multi-processor systems). Second, when
another thread has made a modification to the condition, we need to retest to ensure that the modification
matches our criteria. The associated mutex is unlocked atomically by pthread_cond_wait() when the
waiting thread is blocked to allow another thread to enter the critical section.
A thread that performs a signal will unblock the
highest-priority thread queued on the condvar, while a broadcast will unblock all threads queued on the
condvar. The associated mutex is locked atomically by the highest-priority unblocked thread; the thread must
then unlock the mutex after proceeding through the critical section.
A version of the condvar wait operation allows a timeout to be
specified (pthread_cond_timedwait()). The waiting thread can then be unblocked when the timeout
expires.
Sleepon locks
Sleepon locks are very similar to condvars, with a few subtle
differences. Like condvars, sleepon locks (pthread_sleepon_lock()) can be used to block until a
condition becomes true (like a memory location changing value). But unlike condvars, which must be allocated
for each condition to be checked, sleepon locks multiplex their functionality over a single mutex and
dynamically allocated condvar, regardless of the number of conditions being checked. The maximum number of
condvars ends up being equal to the maximum number of blocked threads. These locks are patterned after the
sleepon locks commonly used within the UNIX kernel.
Reader/writer locks
More formally known as "Multiple readers, single writer
locks," these locks are used when the access pattern for a data structure consists of many threads reading the
data, and (at most) one thread writing the data. These locks are more expensive than mutexes, but can be useful
for this data access pattern.
This lock works by allowing all the threads that request a
read-access lock (pthread_rwlock_rdlock()) to succeed in their request. But when a thread wishing to
write asks for the lock (pthread_rwlock_wrlock()), the request is denied until all the current reading
threads release their reading locks (pthread_rwlock_unlock()).
Multiple writing threads can queue (in priority order) waiting
for their chance to write the protected data structure, and all the blocked writer-threads will get to run
before reading threads are allowed access again. The priorities of the reading threads are not
considered.
There are also calls (pthread_rwlock_tryrdlock() and
pthread_rwlock_trywrlock()) to allow a thread to test the attempt to achieve the requested lock, without
blocking. These calls return with a successful lock or a status indicating that the lock couldn't be granted
immediately.
Reader/writer locks aren't implemented directly within the
kernel, but are instead built from the mutex and condvar services provided by the kernel.
Semaphores
Semaphores are another common form of synchronization that
allows threads to "post" (sem_post()) and "wait" (sem_wait()) on a semaphore to control when
threads wake or sleep. The post operation increments the semaphore; the wait operation decrements
it.
If you wait on a semaphore that is positive, you will not
block. Waiting on a non-positive semaphore will block until some other thread executes a post. It is valid to
post one or more times before a wait. This use will allow one or more threads to execute the wait without
blocking.
A significant difference between semaphores and other
synchronization primitives is that semaphores are "async safe" and can be manipulated by signal handlers. If
the desired effect is to have a signal handler wake a thread, semaphores are the right choice.
Another useful property of semaphores is that they were
defined to operate between processes. Although Neutrino mutexes work between processes, the POSIX thread
standard considers this an optional capability and as such may not be portable across systems. For
synchronization between threads in a single process, mutexes will be more efficient than semaphores.
As a useful variation, a named semaphore service is
also available. It uses a resource manager and as such allows semaphores to be used between processes on
different machines connected by a network.
|
Note that named semaphores are slower than the
unnamed variety. |
Since semaphores, like condition variables, can legally return a non-zero value because of a false wakeup, correct usage requires a loop:
while (sem_wait(&s) == EINTR) { do_nothing(); }
do_critical_region(); /* Semaphore was decremented */
Synchronization via scheduling algorithm
By selecting the POSIX FIFO scheduling algorithm, we can
guarantee that no two threads of the same priority execute the critical section concurrently on a non-SMP
system. The FIFO scheduling algorithm dictates that all FIFO-scheduled threads in the system at the same
priority will run, when scheduled, until they voluntarily release the processor to another thread.
This "release" can also occur when the thread blocks as part
of requesting the service of another process, or when a signal occurs. The critical region must therefore
be carefully coded and documented so that later maintenance of the code doesn't violate this
condition.
In addition, higher-priority threads in that (or any other)
process could still preempt these FIFO-scheduled threads. So, all the threads that could "collide" within the
critical section must be FIFO-scheduled at the same priority. Having enforced this condition, the
threads can then casually access this shared memory without having to first make explicit synchronization
calls.
|
Note that this exclusive-access relationship doesn't apply in multi-processor
systems, since each CPU could run a thread simultaneously through the region that would otherwise be
serially scheduled on a single-processor machine. |
Synchronization via message passing
The Neutrino Send/Receive/Reply message-passing IPC services
(described later) implement an implicit synchronization by their blocking nature. These IPC services can, in
many instances, render other synchronization services unnecessary. They are also the only synchronization and
IPC primitives (other than named semaphores, which are built on top of messaging) that can be used across the
network.
Synchronization via atomic operations
In some cases, you may want to perform a short operation
(such as incrementing a variable) with the guarantee that the operation will perform atomically -
i.e. the operation won't be preempted by another thread or ISR (Interrupt Service Routine).
Under Neutrino, we provide atomic operations for:
- adding a value
- subtracting a value
- clearing bits
- setting bits
- toggling (complementing) bits
These atomic operations are available by including the C
header file <atomic.h>.
Although you can use these atomic operations just about
anywhere, you'll find them particularly useful in these two cases:
- between an ISR and a thread
- between two threads (SMP or single-processor).
Since an ISR can preempt a thread at any given point, the only
way that the thread would be able to protect itself would be to disable interrupts. Since you should
avoid disabling interrupts in a realtime system, we recommend that you use the atomic operations provided with
Neutrino.
On an SMP system, multiple threads can and
do run concurrently. Again, we run into the same situation as with interrupts above - you should use
the atomic operations where applicable to eliminate the need to disable and reenable interrupts.
Synchronization services implementation
The following table lists the various microkernel calls and
the higher-level POSIX calls constructed from them:
| Microkernel call
| POSIX call
| Description
|
| SyncCreate() |
pthread_mutex_init(), pthread_cond_init(), sem_init() |
Create object for mutex, condvars, and semaphore. |
| SyncDestroy() |
pthread_mutex_destroy(), pthread_cond_destroy(), sem_destroy() |
Destroy synchronization object. |
| SyncCondvarWait() |
pthread_cond_wait(), pthread_cond_timedwait() |
Block on a condvar. |
| SyncCondvarSignal() |
pthread_cond_broadcast(), pthread_cond_signal() |
Wake up condvar blocked threads. |
| SyncMutexLock() |
pthread_mutex_lock(), pthread_mutex_trylock() |
Lock a mutex. |
| SyncMutexUnlock() |
pthread_mutex_unlock() |
Unlock a mutex. |
| SyncSemPost() |
sem_post() |
Post a semaphore. |
| SyncSemWait() |
sem_wait(), sem_trywait() |
Wait on a semaphore. |
<< Previous |
Index |
Next >>
|
