CSC 456 Fall 2013/7a ac
Survey of Primitives for Synchronization
This wiki touches on high level synchronization methods across multiple languages and platforms. First it will define the most common of these high level constructs, their purpose, and appropriate use. Next it will show what languages support these constructs and in what Operating Systems. Then an example of external libraries providing API's for different types of synchronization will be shown. Finally a major paper describing some common synchronization methods' performance will be summarized.
Types of Synchronization
Locks
A lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy.<ref name="lock"/> There are several different implementations of locks, as well as higher level constructs that use them, which will be briefly examined below. Several languages--such as C#--have an inherent support for locks, but these implementations are closer to the Java synchronized keyword below.
Semaphores and Mutexes
Semaphores are simple data types used for controlling access to variables. They classically have two operations, wait() and signal(), also known as acquire() and release(). Semaphores have an integer value representing the number of available units of a resource available. The wait() or acquire() operation attempts to decrement the value of the semaphore (signifying that a thread is taking one of the units) but will only succeed if the value is greater than 0. This makes sense since it would be impossible for there to be a negative number of units of a resource to be available. The signal() or release() operation increments the value of the semaphore, signifying that the thread has freed its resource.
There are two types of semaphores, binary semaphores and counting semaphores. Binary semaphores can only hold a value of 0 or 1, meaning that only one thread can access the semaphore at a time. Counting semaphores can have any number of resource instances. Mutexes are essentially binary semaphores with a few extra safety features that make them more desirable to use than plain semaphores.<ref name="semaphore"/>
The following pseudocode shows an implementation of acquire() and release()<ref name="semaphore"/>:
function acquire(semaphore S):
[S ← S + 1]
function release(semaphore S):
repeat:
[if S >= 0:
S ← S - 1
break]
Monitors
According to Wikipedia, a monitor is "a thread-safe class, object, or module that uses wrapped mutual exclusion in order to transparently safely be used by more than one thread."<ref name="monitor"/> In more basic terms, a monitor consists of a mutex and a condition variable. This combination allows threads to try and acquire the mutex, but then allows them to release the monitor and wait on the condition variable if acquisition fails, which helps to prevent deadlock.
A monitor can also be a thread-safe class that's methods are executed with mutual exclusion, allowing the programmer an easier way to implement synchronization.<ref name="monitor"/> Java's monitor class for example falls into this second category.
Synchronized
In Java, the synchronized keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a lock keyword which functions in much the same way. Both are similar to the second definition of monitors, but they allow finer grained synchronization.
This Java code shows how its synchronized keyword can be used to achieve synchronization:<ref name="synchronized"/>
public class SynchronizedCounter {
private int c = 0;
public synchronized void increment() {
c++;
}
public synchronized void decrement() {
c--;
}
public synchronized int value() {
return c;
}
}
The following example in C# shows a high level implementation of a lock:<ref name="lock"/>
class Account { // this is a monitor of an account
long val = 0;
object thisLock = new object();
public void Deposit(const long x) {
lock (thisLock) { // only 1 thread at a time may execute this statement
val += x;
}
}
public void Withdraw(const long x) {
lock (thisLock) {
val -= x;
}
}
}
Supported Synchronization in Different Languages
The following table shows the major well known native synchronization methods for some popular languages and what OS they are supported in. Mostly if there is a compiler for that language in an OS it supports all its features. Some synchronization types have been grouped together due to how similar they perform, such as the Semaphore and Mutex. Others such as Condition Variables are grouped with Monitors because they extend the same abilities to a language. This list is not comprehensive, for instance Java has Classes to support almost every synchronization method even though they are mostly all simulated and not truly atomic at the hardware level. The OS support key is as follows:
| None | Windows Only | Mac Only | Linux Only | Windows & Mac | Windows & Linux | Mac & Linux | All |
| Language | Semaphore/Mutex | Monitor/Cond. Var | Synchronized | Other |
|---|---|---|---|---|
| Java | Reentrant Lock<ref name="reentrant_java"/> | |||
| C/C++ | <ref name="semaphore_c"/> | <ref name="conditional_c"/> | Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/> | |
| C# | ||||
| Ruby | <ref name="conditional_ruby"/> | |||
| Python | Reentrant Lock<ref name="reentrant_python"/> | |||
| PHP | <ref name="sync_php"/> | |||
| Perl | <ref name="conditional_perl"/> | flock<ref name="flock_perl"/> | ||
| Fortran | Coarray<ref name="coarray"/> |
This table is an example of some external libraries that provide an API for synchronization, thread support, or some type of parallelization specialization. It is by no means exhaustive and is simply meant to give some example and show the diversity of possible libraries. OpenMP uses compiler directives called pragmas to divide a program into threads accordingly and includes support for synchronization techniques such as barriers, critical section declarations, and synchronization constructs. PaStiX is an API specifically for parallelizing direct solving methods of sparse matrices. Intel TBB is the Thread Building Blocks library meant specifically for maximizing the use of mulit-core processors by means of task stealing. RubySync is an open source project that is on a much higher level than the others here, it is meant for synchronization across databases.
| Language | OpenMP | PaStiX<ref name="pastix"/> | Intel TBB | RubySync |
|---|---|---|---|---|
| Fortran | ||||
| C/C++ | ||||
| Python | ||||
| Ruby | <ref name="rubysync"/> |
References
<references> <ref name="lock">Lock</ref> <ref name="semaphore">Semaphore</ref> <ref name="monitor">Monitor (synchronization)</ref> <ref name="openmp">OpenMP</ref> <ref name="synchronized">Java Synchronization</ref> <ref name="slimrdwr">Slim Reader/Writer Lock</ref> <ref name="coarray">Co-Array Fortran</ref> <ref name="reentrant_python">Python: ReLocks, Mutex, Cond. Vars</ref> <ref name="reentrant_java">Reentrant Lock (Java)</ref> <ref name="semaphore_c">C Mutex</ref> <ref name="conditional_c">C Conditional</ref> <ref name="conditional_ruby">Ruby Conditional</ref> <ref name="sync_php">PHP Synchronized</ref> <ref name="conditional_perl">Perl: Mutex, Cond. Var</ref> <ref name="flock_perl">Perl flock</ref> <ref name="pastix">PaStiX</ref> <ref name="rubysync">RubySync</ref>
</references>
Ideas (temporary)
HEY CHRIS!!!! ->FYI: i figured out a good idea for the table, split it into 2, 1 table being native synchros, the second being certain libraries for synchro that support that language, i.e. OpenMP would be for the second table. Also, I'll implement that since it was my idea. Also I should be done filling in my portions by sometime Friday night [11/22].
synchronization constucts
syncs in clr semaphores in monitors (how many langs available in?)
Different Synchronization Constructs, languages that support them, general info.
Test-and-Set
Test-and-Test-and-Set
Lock-free
Array-lock
Semaphore-Java, C Acquire/Release the semaphore to enter the critical section. Only 1 thread can have the semaphore at a time.
Mutex-Java, C Like a binary semaphore, but with a few differences such as deletion safety (a process holding a mutex cannot be deleted).
Monitor-Java, C
Synchronized-Java
pragma-C (OpenMP)
a study of behavior of synchronization methods in commonly used languages and systems cederman et al.