CSC 456 Fall 2013/7a ac

Survey of Primitives for Synchronization

Assignment

7a. Survey of primitives for synchronization Section 7.3 of Solihin covers the need for synchronization at the program level. It mentions lock and unlock operations. But real programs do not usually call lock and unlock mechanisms. Instead, they use higher-level operations, such as Java’s synchronized statement, or Open MP pragmas. Consider popular languages and common OSs such as Linux, MacOS, and Windows. How would programs do synchronization in these environments?

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 have an inherent support for locks, such as C#:

 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;
     }
   }
 }

Semaphores and Mutexes

Semaphores are simple data types used for controlling access to variables. They classically have two operations, wait() and signal(), sometimes known as acquire() and release(). There are two types of semaphores, binary semaphores and counting semaphores. Binary semaphores can only hold a value of 0 or 1, basically meaning that only one thread can access the semaphore at a time. Counting semaphores can have any number of resource instances. A mutex is essentially a binary semaphore with a few extra safety features that make them more desirable to use than plain semaphores.<ref name="semaphore"/>

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.

OpenMP

OpenMP is an API (Application Programming Interface) that supports multi-platform shared memory multiprocessing programming in C, C++, and Fortran. OpenMP makes it significantly simpler to parallelize code in supported languages by giving the programmer a set of compiler directives, library routines, and environment variables that influence run-time behavior.<ref name="openmp"/>

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.

Supported Synchronization in Different Languages

The following table shows different programming languages and their support for various synchronization methods. The cells are color coded based on the following key:

Supported Operating Systems Key

None

Windows Only

Mac Only

Linux Only

Windows & Mac

Windows & Linux

Mac & Linux

All

Synchronization Support

Language	Semaphore/Mutex	Monitor	OpenMP	Synchronized	Other
C
Java
C++					Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
C#
Ruby					Get Sources
Python					Get Sources
PHP					Get Sources
Fortran					Co-Array<ref name="coarray"/>

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> </references>

A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.

Apple Synchronization

C++ Sync Article

Ideas (temporary)

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.