249 lines
9.7 KiB
Plaintext
249 lines
9.7 KiB
Plaintext
nsync is a C library that exports various synchronization primitives:
|
|
locks
|
|
condition variables
|
|
run-once initialization
|
|
waitable counter (useful for barriers)
|
|
waitable bit (useful for cancellation, or other conditions)
|
|
|
|
It is not an offical Google product.
|
|
|
|
nsync may be desirable in place of pthread primitives in some cases:
|
|
- nsync locks are reader-writer locks (but are as efficient as mutexes).
|
|
- nsync locks and condition variables occupy only two words each.
|
|
- nsync works on Unix-like systems and Windows. It should be portable to
|
|
other platforms straightforwardly.
|
|
- nsync provides conditional critical sections. These fill the same role
|
|
as condition variables, but are usually easier to use, and in most common
|
|
cases are comparable in speed. They can be easier to use in two ways:
|
|
- it's not necessary to surround the "wait" operation in a while loop;
|
|
instead the condition is passed to the call as a function and arbitrary
|
|
pointer argument.
|
|
- it's not necessary to wake or signal explicitly when the condition(s)
|
|
become true; they are checked automatically.
|
|
The primary downsides are:
|
|
- they are not available in most other common synchronization APIs, and so
|
|
they may be unfamiliar (even though they date back to the 1960s), and
|
|
- if threads routinely wait on many distinct, false conditions
|
|
associated with the same lock, they may be slower than condition variables.
|
|
In this case, clients can use condition variables in the normal way;
|
|
conditional critical sections and condition variables can be used with
|
|
the same lock.
|
|
- nsync waits can be cancelled via an object passed to the wait calls, unlike
|
|
the pthread model in which threads are cancelled. This difference can be
|
|
useful if the computation needs multiple threads, or if cancellation affects
|
|
only sub-operations within a larger operation by the thread.
|
|
See the section "Extensions to locks and condition variables" below.
|
|
|
|
Portability
|
|
===========
|
|
The library is intended to be portable, and to be compilable on a system with
|
|
only a C90 compiler, assuming atomic operations are available from the
|
|
compiler, operating system, or assembler routines. It is able to use C11 or
|
|
C++11 atomic operations if they are available.
|
|
It can be compiled with a C++ compiler, and in its own C++ name space, if
|
|
desired, though no attempt has been made to present a class-based interface.
|
|
|
|
Building
|
|
========
|
|
The builds/ directory may already contain a subdirectory that
|
|
matches your platform. For example, if you're on an x86_64,
|
|
running Linux, using gcc, you might pick "x86_64.linux.gcc".
|
|
|
|
If there is an appropriate subdirectory, in that subdirectory type:
|
|
make depend test
|
|
which will calculate dependencies, build the library and its tests, and then
|
|
run them. (On Windows, using Visual Studio ("x86_64.win32.msvc")
|
|
use "nmake" instead of "make".)
|
|
|
|
If there is no suitable subdirectory, on most Unix-like systems you can create
|
|
one with
|
|
tools/mkmakefile.sh
|
|
|
|
The main reason it might fail is if it cannot find a suitable implentation of
|
|
atomic operations on the platform. Atomic operations may be provided by
|
|
- compiler-dependent interfaces (currently, gcc and clang)
|
|
These are auto detected by mkmakefile.sh.
|
|
- language-specific standards (currently, C11 and C++11)
|
|
Selected in mkmakefile.sh via "-atomic c11" or "-atomic c++11".
|
|
- operating system-dependent libraries (e.g., NetBSD, MacOS, Windows)
|
|
Selected in mkmakefile.sh via "-atomic os".
|
|
- architecture-dependent libraries (e.g., x86_64, x86_32, aarch64,
|
|
arm, mips, alpha)
|
|
Selected in mkmakefile.sh via "-atomic asm"; file should be
|
|
named platforms/<architecture>/src/nsync_atm_<architecture>.[csS]
|
|
to be found by mkmakefile.sh.
|
|
If none of these match your platform, you may need to provide
|
|
an assembly language implementation.
|
|
|
|
Other possible issues:
|
|
- Some platforms put clock_gettime() in the realtime library.
|
|
Give "-lrt" to mkmakefile.sh.
|
|
- The version identifier of "clang" can vary by installation,
|
|
and so it may not be identified if invoked as "cc".
|
|
Give "-cc clang" to mkmakefile.sh, if clang is not detected automatically.
|
|
- Some CPU architectures have many variants, making it
|
|
difficult to rely on a single identifier.
|
|
Give "-arch <architecture>" to mkmakefile.sh to specify
|
|
a particular string.
|
|
|
|
mkmakefile.sh recognises a couple of special cases:
|
|
- MacOS doesn't provide clock_gettime(); a compatibility routine
|
|
is found in platform/posix/src/clock_gettime.c
|
|
See builds/x86_64.macos.clang/Makefile
|
|
- OpenBSD and Irix do not provide thread-local storage, which is accommodated
|
|
by adding -I../../platform/gcc_no_tls to the include path.
|
|
See, for example, builds/x86_64.openbsd.gcc/Makefile.
|
|
|
|
Further customization is possible by editing the Makefile, directly.
|
|
For Unix-like systems is typically only a few lines long.
|
|
For example, compare
|
|
builds/x86_64.linux.g++/Makefile
|
|
with
|
|
builds/x86_64.linux.gcc/Makefile
|
|
to see how to compile the entire library in C++, rather than C.
|
|
|
|
CMake
|
|
-----
|
|
|
|
CMake can also be used to build:
|
|
|
|
$ mkdir out
|
|
$ cd out/
|
|
$ cmake ..
|
|
$ make
|
|
$ make install
|
|
|
|
The C library will be called libnsync and C++ is libnsync_cpp.
|
|
|
|
Tests can be disabled with the CMake option: -DNSYNC_ENABLE_TESTS=0.
|
|
To build shared libraries instead of static use: -DBUILD_SHARED_LIBS=ON.
|
|
|
|
CMake version >= 3.0 is strongly recommended.
|
|
|
|
Code structure
|
|
==============
|
|
public/ Public header files for library.
|
|
builds/*/ Platform-dependent build directories, each with Makefile.
|
|
internal/ Platform-independent library source code, and Makefile fragment.
|
|
platform/*/ Platform-dependent source code.
|
|
testing/ Platform-independent testing source code is in "testing".
|
|
tools/ Optional tools that can be used to create Makefile
|
|
dependencies and run tests.
|
|
|
|
Where possible, the code avoids conditional compilation (#if, etc.),
|
|
to avoid becoming a mess of C-preprocessor directives.
|
|
The platform-dependent Makefiles set the appropriate include
|
|
paths and specify platform-dependent modules where needed.
|
|
|
|
The build directories of the various platforms are kept separate to allow
|
|
multiple platforms to be accommodated in one shared file system.
|
|
|
|
Differences from pthread locks and condition variables
|
|
======================================================
|
|
|
|
Conditional critical sections
|
|
-----------------------------
|
|
Consider the following use of a condition variable:
|
|
/* variable declarations */
|
|
nsync_mu mu = NSYNC_MU_INIT; /* protects i */
|
|
int i = 1;
|
|
nsync_cv cv = NSYNC_CV_INIT; /* signalled when i reaches 0 */
|
|
|
|
...
|
|
|
|
/* Waiter */
|
|
nsync_mu_lock (&mu);
|
|
while (i != 0) {
|
|
nsync_cv_wait (&cv, &mu);
|
|
}
|
|
/* i is zero ... */
|
|
nsync_mu_unlock (&mu);
|
|
|
|
...
|
|
|
|
/* Decrementer */
|
|
nsync_mu_lock (&mu)
|
|
i--;
|
|
if (i == 0) {
|
|
nsync_cv_broadcast (&cv);
|
|
}
|
|
nsync_mu_unlock (&mu);
|
|
|
|
With conditional critical sections, the equivalent is:
|
|
/* variable declarations */
|
|
nsync_mu mu = NSYNC_MU_INIT; /* protects i */
|
|
int i = 1;
|
|
|
|
/* Condition */
|
|
int int_is_zero (void *v) {
|
|
return (*(int *)v == 0);
|
|
}
|
|
|
|
...
|
|
|
|
/* Waiter */
|
|
nsync_mu_lock (&mu);
|
|
nsync_mu_wait (&mu, &int_is_zero, &i)
|
|
/* i is zero ... */
|
|
nsync_mu_unlock (&mu);
|
|
|
|
...
|
|
|
|
/* Decrementer */
|
|
nsync_mu_lock (&mu)
|
|
i--;
|
|
nsync_mu_unlock (&mu);
|
|
|
|
For the cost of writing a function that evaluates the desired
|
|
condition, the waiter's while-loop, and the decrementer's
|
|
signalling are handled by the implementation.
|
|
|
|
In most cases, this makes code easier to write and debug.
|
|
|
|
The primary cost is that the implementation must check whether any waiters'
|
|
conditions have become true when releasing the lock. This cost becomes most
|
|
noticable when threads wait on many distinct, false conditions. In such cases,
|
|
some or all of the conditions can be converted to use condition variables and
|
|
explicit signalling.
|
|
|
|
C++ users may be tempted to wrap this functionality in a way that uses
|
|
lambda expressions for the conditions. This will work, but may be less
|
|
efficient, because C++ does not provide a means to detect whether two lambda
|
|
expressions evaluate the same function. This may force the implementation to
|
|
evaluate the same false condition many more times than it otherwise might.
|
|
|
|
Reader/writer locks
|
|
-------------------
|
|
There is no particular reason why a reader/writer lock need be
|
|
significantly slower than a simple mutex. In both cases, the lock can be
|
|
acquired or released with a single atomic read-modify-write sequence.
|
|
Thus, the type nsync_mu is a reader/writer lock. Locks with reader-sections
|
|
can be used with condition variables and conditional critical sections
|
|
without affecting correctness.
|
|
|
|
Cancellation
|
|
------------
|
|
The pthread API allows the cancellation of individual threads,
|
|
and once a thread has been cancelled, it is expected to terminate soon. This
|
|
can work well in some cases, but may not be convenient if an activity is
|
|
associated with many threads, or if threads routinely act on behalf of multiple
|
|
activities.
|
|
|
|
In nsync, cancellation involves an object separate from the thread, called an
|
|
nsync_note. An nsync_note is conceptually a boolean that makes a single
|
|
transition from false to true: it starts off "unnotified", can be notified:
|
|
- by an explicit nsync_note_notify() call,
|
|
- due to a timeout, or
|
|
- due to the transition of an optional parent nsync_note.
|
|
So, for example, in a network server, a request with a deadline
|
|
might have an nsync_note associated with it. Activities associated with
|
|
that request might each have a child nsync_note, possibly with shorter
|
|
deadlines. A cancellation request from the original caller
|
|
might cancel the parent, which would cancel all the children.
|
|
|
|
The calls nsync_cv_wait_with_deadline() and nsync_mu_wait_with_deadline() take
|
|
both a deadline and a pointer to an nsync_note, and will wake when the awaited
|
|
condition becomes true, when the deadline (if any) expires, or when the
|
|
nsync_note becomes notified. The return value indicates which of these
|
|
occurred.
|