| 1 |
nsync is a C library that exports various synchronization primitives: |
| 2 |
locks |
| 3 |
condition variables |
| 4 |
run-once initialization |
| 5 |
waitable counter (useful for barriers) |
| 6 |
waitable bit (useful for cancellation, or other conditions) |
| 7 |
|
| 8 |
It is not an offical Google product. |
| 9 |
|
| 10 |
nsync may be desirable in place of pthread primitives in some cases: |
| 11 |
- nsync locks are reader-writer locks (but are as efficient as mutexes). |
| 12 |
- nsync locks and condition variables occupy only two words each. |
| 13 |
- nsync works on Unix-like systems and Windows. It should be portable to |
| 14 |
other platforms straightforwardly. |
| 15 |
- nsync provides conditional critical sections. These fill the same role |
| 16 |
as condition variables, but are usually easier to use, and in most common |
| 17 |
cases are comparable in speed. They can be easier to use in two ways: |
| 18 |
- it's not necessary to surround the "wait" operation in a while loop; |
| 19 |
instead the condition is passed to the call as a function and arbitrary |
| 20 |
pointer argument. |
| 21 |
- it's not necessary to wake or signal explicitly when the condition(s) |
| 22 |
become true; they are checked automatically. |
| 23 |
The primary downsides are: |
| 24 |
- they are not available in most other common synchronization APIs, and so |
| 25 |
they may be unfamiliar (even though they date back to the 1960s), and |
| 26 |
- if threads routinely wait on many distinct, false conditions |
| 27 |
associated with the same lock, they may be slower than condition variables. |
| 28 |
In this case, clients can use condition variables in the normal way; |
| 29 |
conditional critical sections and condition variables can be used with |
| 30 |
the same lock. |
| 31 |
- nsync waits can be cancelled via an object passed to the wait calls, unlike |
| 32 |
the pthread model in which threads are cancelled. This difference can be |
| 33 |
useful if the computation needs multiple threads, or if cancellation affects |
| 34 |
only sub-operations within a larger operation by the thread. |
| 35 |
See the section "Extensions to locks and condition variables" below. |
| 36 |
|
| 37 |
Portability |
| 38 |
=========== |
| 39 |
The library is intended to be portable, and to be compilable on a system with |
| 40 |
only a C90 compiler, assuming atomic operations are available from the |
| 41 |
compiler, operating system, or assembler routines. It is able to use C11 or |
| 42 |
C++11 atomic operations if they are available. |
| 43 |
It can be compiled with a C++ compiler, and in its own C++ name space, if |
| 44 |
desired, though no attempt has been made to present a class-based interface. |
| 45 |
|
| 46 |
Building |
| 47 |
======== |
| 48 |
The builds/ directory may already contain a subdirectory that |
| 49 |
matches your platform. For example, if you're on an x86_64, |
| 50 |
running Linux, using gcc, you might pick "x86_64.linux.gcc". |
| 51 |
|
| 52 |
If there is an appropriate subdirectory, in that subdirectory type: |
| 53 |
make depend test |
| 54 |
which will calculate dependencies, build the library and its tests, and then |
| 55 |
run them. (On Windows, using Visual Studio ("x86_64.win32.msvc") |
| 56 |
use "nmake" instead of "make".) |
| 57 |
|
| 58 |
If there is no suitable subdirectory, on most Unix-like systems you can create |
| 59 |
one with |
| 60 |
tools/mkmakefile.sh |
| 61 |
|
| 62 |
The main reason it might fail is if it cannot find a suitable implementation of |
| 63 |
atomic operations on the platform. Atomic operations may be provided by |
| 64 |
- compiler-dependent interfaces (currently, gcc and clang) |
| 65 |
These are auto detected by mkmakefile.sh. |
| 66 |
- language-specific standards (currently, C11 and C++11) |
| 67 |
Selected in mkmakefile.sh via "-atomic c11" or "-atomic c++11". |
| 68 |
- operating system-dependent libraries (e.g., NetBSD, MacOS, Windows) |
| 69 |
Selected in mkmakefile.sh via "-atomic os". |
| 70 |
- architecture-dependent libraries (e.g., x86_64, x86_32, aarch64, |
| 71 |
arm, mips, alpha) |
| 72 |
Selected in mkmakefile.sh via "-atomic asm"; file should be |
| 73 |
named platforms/<architecture>/src/nsync_atm_<architecture>.[csS] |
| 74 |
to be found by mkmakefile.sh. |
| 75 |
If none of these match your platform, you may need to provide |
| 76 |
an assembly language implementation. |
| 77 |
|
| 78 |
Other possible issues: |
| 79 |
- Some platforms put clock_gettime() in the realtime library. |
| 80 |
Give "-lrt" to mkmakefile.sh. |
| 81 |
- The version identifier of "clang" can vary by installation, |
| 82 |
and so it may not be identified if invoked as "cc". |
| 83 |
Give "-cc clang" to mkmakefile.sh, if clang is not detected automatically. |
| 84 |
- Some CPU architectures have many variants, making it |
| 85 |
difficult to rely on a single identifier. |
| 86 |
Give "-arch <architecture>" to mkmakefile.sh to specify |
| 87 |
a particular string. |
| 88 |
|
| 89 |
mkmakefile.sh recognises a couple of special cases: |
| 90 |
- MacOS doesn't provide clock_gettime(); a compatibility routine |
| 91 |
is found in platform/posix/src/clock_gettime.c |
| 92 |
See builds/x86_64.macos.clang/Makefile |
| 93 |
- OpenBSD and Irix do not provide thread-local storage, which is accommodated |
| 94 |
by adding -I../../platform/gcc_no_tls to the include path. |
| 95 |
See, for example, builds/x86_64.openbsd.gcc/Makefile. |
| 96 |
|
| 97 |
Further customization is possible by editing the Makefile, directly. |
| 98 |
For Unix-like systems is typically only a few lines long. |
| 99 |
For example, compare |
| 100 |
builds/x86_64.linux.g++/Makefile |
| 101 |
with |
| 102 |
builds/x86_64.linux.gcc/Makefile |
| 103 |
to see how to compile the entire library in C++, rather than C. |
| 104 |
|
| 105 |
CMake |
| 106 |
----- |
| 107 |
|
| 108 |
CMake can also be used to build: |
| 109 |
|
| 110 |
$ mkdir out |
| 111 |
$ cd out/ |
| 112 |
$ cmake .. |
| 113 |
$ make |
| 114 |
$ make install |
| 115 |
|
| 116 |
The C library will be called libnsync and C++ is libnsync_cpp. |
| 117 |
|
| 118 |
Tests can be disabled with the CMake option: -DNSYNC_ENABLE_TESTS=0. |
| 119 |
To build shared libraries instead of static use: -DBUILD_SHARED_LIBS=ON. |
| 120 |
|
| 121 |
CMake version >= 3.0 is strongly recommended. |
| 122 |
|
| 123 |
Code structure |
| 124 |
============== |
| 125 |
public/ Public header files for library. |
| 126 |
builds/*/ Platform-dependent build directories, each with Makefile. |
| 127 |
internal/ Platform-independent library source code, and Makefile fragment. |
| 128 |
platform/*/ Platform-dependent source code. |
| 129 |
testing/ Platform-independent testing source code is in "testing". |
| 130 |
tools/ Optional tools that can be used to create Makefile |
| 131 |
dependencies and run tests. |
| 132 |
|
| 133 |
Where possible, the code avoids conditional compilation (#if, etc.), |
| 134 |
to avoid becoming a mess of C-preprocessor directives. |
| 135 |
The platform-dependent Makefiles set the appropriate include |
| 136 |
paths and specify platform-dependent modules where needed. |
| 137 |
|
| 138 |
The build directories of the various platforms are kept separate to allow |
| 139 |
multiple platforms to be accommodated in one shared file system. |
| 140 |
|
| 141 |
Differences from pthread locks and condition variables |
| 142 |
====================================================== |
| 143 |
|
| 144 |
Conditional critical sections |
| 145 |
----------------------------- |
| 146 |
Consider the following use of a condition variable: |
| 147 |
/* variable declarations */ |
| 148 |
nsync_mu mu = NSYNC_MU_INIT; /* protects i */ |
| 149 |
int i = 1; |
| 150 |
nsync_cv cv = NSYNC_CV_INIT; /* signalled when i reaches 0 */ |
| 151 |
|
| 152 |
... |
| 153 |
|
| 154 |
/* Waiter */ |
| 155 |
nsync_mu_lock (&mu); |
| 156 |
while (i != 0) { |
| 157 |
nsync_cv_wait (&cv, &mu); |
| 158 |
} |
| 159 |
/* i is zero ... */ |
| 160 |
nsync_mu_unlock (&mu); |
| 161 |
|
| 162 |
... |
| 163 |
|
| 164 |
/* Decrementer */ |
| 165 |
nsync_mu_lock (&mu) |
| 166 |
i--; |
| 167 |
if (i == 0) { |
| 168 |
nsync_cv_broadcast (&cv); |
| 169 |
} |
| 170 |
nsync_mu_unlock (&mu); |
| 171 |
|
| 172 |
With conditional critical sections, the equivalent is: |
| 173 |
/* variable declarations */ |
| 174 |
nsync_mu mu = NSYNC_MU_INIT; /* protects i */ |
| 175 |
int i = 1; |
| 176 |
|
| 177 |
/* Condition */ |
| 178 |
int int_is_zero (void *v) { |
| 179 |
return (*(int *)v == 0); |
| 180 |
} |
| 181 |
|
| 182 |
... |
| 183 |
|
| 184 |
/* Waiter */ |
| 185 |
nsync_mu_lock (&mu); |
| 186 |
nsync_mu_wait (&mu, &int_is_zero, &i) |
| 187 |
/* i is zero ... */ |
| 188 |
nsync_mu_unlock (&mu); |
| 189 |
|
| 190 |
... |
| 191 |
|
| 192 |
/* Decrementer */ |
| 193 |
nsync_mu_lock (&mu) |
| 194 |
i--; |
| 195 |
nsync_mu_unlock (&mu); |
| 196 |
|
| 197 |
For the cost of writing a function that evaluates the desired |
| 198 |
condition, the waiter's while-loop, and the decrementer's |
| 199 |
signalling are handled by the implementation. |
| 200 |
|
| 201 |
In most cases, this makes code easier to write and debug. |
| 202 |
|
| 203 |
The primary cost is that the implementation must check whether any waiters' |
| 204 |
conditions have become true when releasing the lock. This cost becomes most |
| 205 |
noticable when threads wait on many distinct, false conditions. In such cases, |
| 206 |
some or all of the conditions can be converted to use condition variables and |
| 207 |
explicit signalling. |
| 208 |
|
| 209 |
C++ users may be tempted to wrap this functionality in a way that uses |
| 210 |
lambda expressions for the conditions. This will work, but may be less |
| 211 |
efficient, because C++ does not provide a means to detect whether two lambda |
| 212 |
expressions evaluate the same function. This may force the implementation to |
| 213 |
evaluate the same false condition many more times than it otherwise might. |
| 214 |
|
| 215 |
Reader/writer locks |
| 216 |
------------------- |
| 217 |
There is no particular reason why a reader/writer lock need be |
| 218 |
significantly slower than a simple mutex. In both cases, the lock can be |
| 219 |
acquired or released with a single atomic read-modify-write sequence. |
| 220 |
Thus, the type nsync_mu is a reader/writer lock. Locks with reader-sections |
| 221 |
can be used with condition variables and conditional critical sections |
| 222 |
without affecting correctness. |
| 223 |
|
| 224 |
Cancellation |
| 225 |
------------ |
| 226 |
The pthread API allows the cancellation of individual threads, |
| 227 |
and once a thread has been cancelled, it is expected to terminate soon. This |
| 228 |
can work well in some cases, but may not be convenient if an activity is |
| 229 |
associated with many threads, or if threads routinely act on behalf of multiple |
| 230 |
activities. |
| 231 |
|
| 232 |
In nsync, cancellation involves an object separate from the thread, called an |
| 233 |
nsync_note. An nsync_note is conceptually a boolean that makes a single |
| 234 |
transition from false to true: it starts off "unnotified", can be notified: |
| 235 |
- by an explicit nsync_note_notify() call, |
| 236 |
- due to a timeout, or |
| 237 |
- due to the transition of an optional parent nsync_note. |
| 238 |
So, for example, in a network server, a request with a deadline |
| 239 |
might have an nsync_note associated with it. Activities associated with |
| 240 |
that request might each have a child nsync_note, possibly with shorter |
| 241 |
deadlines. A cancellation request from the original caller |
| 242 |
might cancel the parent, which would cancel all the children. |
| 243 |
|
| 244 |
The calls nsync_cv_wait_with_deadline() and nsync_mu_wait_with_deadline() take |
| 245 |
both a deadline and a pointer to an nsync_note, and will wake when the awaited |
| 246 |
condition becomes true, when the deadline (if any) expires, or when the |
| 247 |
nsync_note becomes notified. The return value indicates which of these |
| 248 |
occurred. |