Expertiza_Wiki - User contributions [en]

CSC 456 Fall 2013/7a ac

2013-11-26T04:20:35Z

Cejohns2: /* Findings */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 available. The <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><ref name="semaphore"/>:

'''function''' acquire(semaphore S):
[S ← S + 1]

'''function''' release(semaphore S):
repeat:
[if S >= 0:
S ← S - 1
break]

===Synchronized===
In Java, the <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> keyword which functions in much the same way. All code within a <code>synchronized</code> method or <code>lock</code> statement is executed with mutual exclusion.

This Java code shows how its <code>synchronized</code> 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 <code>lock</code>:<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;
}
}
}

For Java, the <code>synchronized</code> keyword is required for every method that needs to be synchronized. In the C# example, the locking actually takes place within the functions, meaning multiple threads could be accessing the same function at the same time, just not that piece of code within the <code>lock</code>.

===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.

The following example shows an example of a Monitor class using Java-like syntax.<ref name="monitor"/>

'''monitor class''' ''Account'' {
'''private''' ''int'' balance := 0
'''invariant''' balance >= 0

'''public method''' ''boolean'' withdraw(''int'' amount)
'''precondition''' amount >= 0
{
'''if''' balance < amount '''then''' '''return false'''
'''else''' { balance := balance - amount ; '''return true''' }
}

'''public method''' deposit(''int'' amount)
'''precondition''' amount >= 0
{
balance := balance + amount
}
}

Notice that there is no use of locks, <code>synchronized</code> statements, or any other explicit synchronization code other than the <code>'''monitor'''</code> keyword. By definition, all the methods in the class are executed with mutual exclusion, removing the need to deal with synchronization independently.
 

==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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed: accessing a global FIFO queue, and modifying a global chained hash table. Finally, these tests were performed on two different architectures, Intel Nehalem and AMD Bulldozer, with the languages C++, Java, and C# (.NET and Mono).

===Findings===

The results of the study appear in the graphs below. For throughput, note that the vertical axes do not represent the same ranges of values.

[[Image:cederman_queues.jpg|center|alt=Queue Results]]
[[Image:cederman_hashTs.jpg|center|alt=Hash Table Results]]

===Conclusions===
As can be seen, some synchronization methods perform much better for some jobs in some languages. For C++ it can be seen that lock-free methods outperform everything else for hash table access (Figure 4), and while lock-free was a top performer for C# and Java it was not the clear winner. Also to note, for the hash table throughput graphs the scale of the C++ throughput access is much higher than all the others. In terms of fairness, the lock-free methods are roughly the same as all the other methods. .NET is the clear loser for fairness across all methods as the number of threads passes 12 it quickly drops off. 

Looking at throughput for the queues (Figure 1), C#(.NET) had the best throughput up until about 12 threads using TTAS (Test Test and Set), then Java's Reentrant Lock was the winner for 24 threads, then C#(Mono & .Net) have the best throughput for queue access using TTAS. In C++ most of the methods performed more or less equivalently, with TTAS staying near the top most of the time. Interestingly every method decreased in throughput with the addition of more threads except Java's Reentrant Lock and C# (Mono)'s TTAS. They both grew out until 24 threads. So Java's Reentrant Lock and C#'s TTAS are good choices for synchronization of a FIFO Queue. In terms of fairness all the methods in all languages dropped off drastically after 24 threads. In C++ TTAS, Array Lock, & TAS dropped to starvation levels. In Java all methods dropped low except the Reentrant Fair lock, which seems logical. That lock had the worst throughput performance by far though, so it does not seem to be a good trade. In C# the TTAS dropped off on par with the other methods, with .NET being worse for starvation with more threads than Mono.

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-26T04:13:58Z

Cejohns2: /* Introduction */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 available. The <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><ref name="semaphore"/>:

'''function''' acquire(semaphore S):
[S ← S + 1]

'''function''' release(semaphore S):
repeat:
[if S >= 0:
S ← S - 1
break]

===Synchronized===
In Java, the <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> keyword which functions in much the same way. All code within a <code>synchronized</code> method or <code>lock</code> statement is executed with mutual exclusion.

This Java code shows how its <code>synchronized</code> 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 <code>lock</code>:<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;
}
}
}

For Java, the <code>synchronized</code> keyword is required for every method that needs to be synchronized. In the C# example, the locking actually takes place within the functions, meaning multiple threads could be accessing the same function at the same time, just not that piece of code within the <code>lock</code>.

===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.

The following example shows an example of a Monitor class using Java-like syntax.<ref name="monitor"/>

'''monitor class''' ''Account'' {
'''private''' ''int'' balance := 0
'''invariant''' balance >= 0

'''public method''' ''boolean'' withdraw(''int'' amount)
'''precondition''' amount >= 0
{
'''if''' balance < amount '''then''' '''return false'''
'''else''' { balance := balance - amount ; '''return true''' }
}

'''public method''' deposit(''int'' amount)
'''precondition''' amount >= 0
{
balance := balance + amount
}
}

Notice that there is no use of locks, <code>synchronized</code> statements, or any other explicit synchronization code other than the <code>'''monitor'''</code> keyword. By definition, all the methods in the class are executed with mutual exclusion, removing the need to deal with synchronization independently.
 

==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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed: accessing a global FIFO queue, and modifying a global chained hash table. Finally, these tests were performed on two different architectures, Intel Nehalem and AMD Bulldozer, with the languages C++, Java, and C# (.NET and Mono).

===Findings===
[[Image:cederman_queues.jpg|center|alt=Queue Results]]
[[Image:cederman_hashTs.jpg|center|alt=Hash Table Results]]

===Conclusions===
As can be seen, some synchronization methods perform much better for some jobs in some languages. For C++ it can be seen that lock-free methods outperform everything else for hash table access (Figure 4), and while lock-free was a top performer for C# and Java it was not the clear winner. Also to note, for the hash table throughput graphs the scale of the C++ throughput access is much higher than all the others. In terms of fairness, the lock-free methods are roughly the same as all the other methods. .NET is the clear loser for fairness across all methods as the number of threads passes 12 it quickly drops off. 

Looking at throughput for the queues (Figure 1), C#(.NET) had the best throughput up until about 12 threads using TTAS (Test Test and Set), then Java's Reentrant Lock was the winner for 24 threads, then C#(Mono & .Net) have the best throughput for queue access using TTAS. In C++ most of the methods performed more or less equivalently, with TTAS staying near the top most of the time. Interestingly every method decreased in throughput with the addition of more threads except Java's Reentrant Lock and C# (Mono)'s TTAS. They both grew out until 24 threads. So Java's Reentrant Lock and C#'s TTAS are good choices for synchronization of a FIFO Queue. In terms of fairness all the methods in all languages dropped off drastically after 24 threads. In C++ TTAS, Array Lock, & TAS dropped to starvation levels. In Java all methods dropped low except the Reentrant Fair lock, which seems logical. That lock had the worst throughput performance by far though, so it does not seem to be a good trade. In C# the TTAS dropped off on par with the other methods, with .NET being worse for starvation with more threads than Mono.

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-26T04:13:23Z

Cejohns2: /* Introduction */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 available. The <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><ref name="semaphore"/>:

'''function''' acquire(semaphore S):
[S ← S + 1]

'''function''' release(semaphore S):
repeat:
[if S >= 0:
S ← S - 1
break]

===Synchronized===
In Java, the <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> keyword which functions in much the same way. All code within a <code>synchronized</code> method or <code>lock</code> statement is executed with mutual exclusion.

This Java code shows how its <code>synchronized</code> 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 <code>lock</code>:<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;
}
}
}

For Java, the <code>synchronized</code> keyword is required for every method that needs to be synchronized. In the C# example, the locking actually takes place within the functions, meaning multiple threads could be accessing the same function at the same time, just not that piece of code within the <code>lock</code>.

===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.

The following example shows an example of a Monitor class using Java-like syntax.<ref name="monitor"/>

'''monitor class''' ''Account'' {
'''private''' ''int'' balance := 0
'''invariant''' balance >= 0

'''public method''' ''boolean'' withdraw(''int'' amount)
'''precondition''' amount >= 0
{
'''if''' balance < amount '''then''' '''return false'''
'''else''' { balance := balance - amount ; '''return true''' }
}

'''public method''' deposit(''int'' amount)
'''precondition''' amount >= 0
{
balance := balance + amount
}
}

Notice that there is no use of locks, <code>synchronized</code> statements, or any other explicit synchronization code other than the <code>'''monitor'''</code> keyword. By definition, all the methods in the class are executed with mutual exclusion, removing the need to deal with synchronization independently.
 

==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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed: accessing a global FIFO queue, and modifying a global chained hash table. Finally, these tests were performed on two different architectures, Intel Nehalem and AMD Bulldozer, with the languages C++, Java, & C# (.NET & Mono).

===Findings===
[[Image:cederman_queues.jpg|center|alt=Queue Results]]
[[Image:cederman_hashTs.jpg|center|alt=Hash Table Results]]

===Conclusions===
As can be seen, some synchronization methods perform much better for some jobs in some languages. For C++ it can be seen that lock-free methods outperform everything else for hash table access (Figure 4), and while lock-free was a top performer for C# and Java it was not the clear winner. Also to note, for the hash table throughput graphs the scale of the C++ throughput access is much higher than all the others. In terms of fairness, the lock-free methods are roughly the same as all the other methods. .NET is the clear loser for fairness across all methods as the number of threads passes 12 it quickly drops off. 

Looking at throughput for the queues (Figure 1), C#(.NET) had the best throughput up until about 12 threads using TTAS (Test Test and Set), then Java's Reentrant Lock was the winner for 24 threads, then C#(Mono & .Net) have the best throughput for queue access using TTAS. In C++ most of the methods performed more or less equivalently, with TTAS staying near the top most of the time. Interestingly every method decreased in throughput with the addition of more threads except Java's Reentrant Lock and C# (Mono)'s TTAS. They both grew out until 24 threads. So Java's Reentrant Lock and C#'s TTAS are good choices for synchronization of a FIFO Queue. In terms of fairness all the methods in all languages dropped off drastically after 24 threads. In C++ TTAS, Array Lock, & TAS dropped to starvation levels. In Java all methods dropped low except the Reentrant Fair lock, which seems logical. That lock had the worst throughput performance by far though, so it does not seem to be a good trade. In C# the TTAS dropped off on par with the other methods, with .NET being worse for starvation with more threads than Mono.

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-26T03:56:53Z

Cejohns2: /* Synchronized */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 available. The <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><ref name="semaphore"/>:

'''function''' acquire(semaphore S):
[S ← S + 1]

'''function''' release(semaphore S):
repeat:
[if S >= 0:
S ← S - 1
break]

===Synchronized===
In Java, the <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> keyword which functions in much the same way. All code within a <code>synchronized</code> method or <code>lock</code> statement is executed with mutual exclusion.

This Java code shows how its <code>synchronized</code> 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 <code>lock</code>:<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;
}
}
}

For Java, the <code>synchronized</code> keyword is required for every method that needs to be synchronized. In the C# example, the locking actually takes place within the functions, meaning multiple threads could be accessing the same function at the same time, just not that piece of code within the <code>lock</code>.

===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.

The following example shows an example of a Monitor class using Java-like syntax.<ref name="monitor"/>

'''monitor class''' ''Account'' {
'''private''' ''int'' balance := 0
'''invariant''' balance >= 0

'''public method''' ''boolean'' withdraw(''int'' amount)
'''precondition''' amount >= 0
{
'''if''' balance < amount '''then''' '''return false'''
'''else''' { balance := balance - amount ; '''return true''' }
}

'''public method''' deposit(''int'' amount)
'''precondition''' amount >= 0
{
balance := balance + amount
}
}

Notice that there is no use of locks, <code>synchronized</code> statements, or any other explicit synchronization code other than the <code>'''monitor'''</code> keyword. By definition, all the methods in the class are executed with mutual exclusion, removing the need to deal with synchronization independently.
 

==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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed, accessing a global FIFO queue, and modifying a global chained hash table. Finally these tests were performed on two different architectures, the Intel Nehalem and AMD Bulldozer with the languages C++, Java, & C# (.NET & Mono).

===Findings===
[[Image:cederman_queues.jpg|center|alt=Queue Results]]
[[Image:cederman_hashTs.jpg|center|alt=Hash Table Results]]

===Conclusions===

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

==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.

[[File:Koala.jpg]]

CSC 456 Fall 2013/7a ac

2013-11-26T03:54:29Z

Cejohns2: /* Semaphores and Mutexes */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 available. The <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><ref name="semaphore"/>:

'''function''' acquire(semaphore S):
[S ← S + 1]

'''function''' release(semaphore S):
repeat:
[if S >= 0:
S ← S - 1
break]

===Synchronized===
In Java, the <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> 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 <code>lock</code>:<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;
}
}
}

For Java, the <code>synchronized</code> keyword is required for every method that needs to be synchronized. In the C# example, the locking actually takes place within the functions, meaning multiple threads could be accessing the same function at the same time, just not that piece of code within the <code>lock</code>.

===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.

The following example shows an example of a Monitor class using Java-like syntax.<ref name="monitor"/>

'''monitor class''' ''Account'' {
'''private''' ''int'' balance := 0
'''invariant''' balance >= 0

'''public method''' ''boolean'' withdraw(''int'' amount)
'''precondition''' amount >= 0
{
'''if''' balance < amount '''then''' '''return false'''
'''else''' { balance := balance - amount ; '''return true''' }
}

'''public method''' deposit(''int'' amount)
'''precondition''' amount >= 0
{
balance := balance + amount
}
}

Notice that there is no use of locks, <code>synchronized</code> statements, or any other explicit synchronization code other than the <code>'''monitor'''</code> keyword. By definition, all the methods in the class are executed with mutual exclusion, removing the need to deal with synchronization independently.
 

==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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed, accessing a global FIFO queue, and modifying a global chained hash table. Finally these tests were performed on two different architectures, the Intel Nehalem and AMD Bulldozer with the languages C++, Java, & C# (.NET & Mono).

===Findings===
[[Image:cederman_queues.jpg|center|alt=Queue Results]]
[[Image:cederman_hashTs.jpg|center|alt=Hash Table Results]]

===Conclusions===

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

==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.

[[File:Koala.jpg]]

CSC 456 Fall 2013/7a ac

2013-11-26T03:50:58Z

Cejohns2: /* Types of Synchronization */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><ref name="semaphore"/>:

'''function''' acquire(semaphore S):
[S ← S + 1]

'''function''' release(semaphore S):
repeat:
[if S >= 0:
S ← S - 1
break]

===Synchronized===
In Java, the <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> 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 <code>lock</code>:<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;
}
}
}

For Java, the <code>synchronized</code> keyword is required for every method that needs to be synchronized. In the C# example, the locking actually takes place within the functions, meaning multiple threads could be accessing the same function at the same time, just not that piece of code within the <code>lock</code>.

===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.

The following example shows an example of a Monitor class using Java-like syntax.<ref name="monitor"/>

'''monitor class''' ''Account'' {
'''private''' ''int'' balance := 0
'''invariant''' balance >= 0

'''public method''' ''boolean'' withdraw(''int'' amount)
'''precondition''' amount >= 0
{
'''if''' balance < amount '''then''' '''return false'''
'''else''' { balance := balance - amount ; '''return true''' }
}

'''public method''' deposit(''int'' amount)
'''precondition''' amount >= 0
{
balance := balance + amount
}
}

Notice that there is no use of locks, <code>synchronized</code> statements, or any other explicit synchronization code other than the <code>'''monitor'''</code> keyword. By definition, all the methods in the class are executed with mutual exclusion, removing the need to deal with synchronization independently.
 

==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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed, accessing a global FIFO queue, and modifying a global chained hash table. Finally these tests were performed on two different architectures, the Intel Nehalem and AMD Bulldozer with the languages C++, Java, & C# (.NET & Mono).

===Findings===
[[Image:cederman_queues.jpg|center|alt=Queue Results]]
[[Image:cederman_hashTs.jpg|center|alt=Hash Table Results]]

===Conclusions===

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

==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.

[[File:Koala.jpg]]

CSC 456 Fall 2013/7a ac

2013-11-26T03:45:56Z

Cejohns2: /* Monitors */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><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.

The following example shows an example of a Monitor class using Java-like syntax.

'''monitor class''' ''Account'' {
'''private''' ''int'' balance := 0
'''invariant''' balance >= 0

'''public method''' ''boolean'' withdraw(''int'' amount)
'''precondition''' amount >= 0
{
'''if''' balance < amount '''then''' '''return false'''
'''else''' { balance := balance - amount ; '''return true''' }
}

'''public method''' deposit(''int'' amount)
'''precondition''' amount >= 0
{
balance := balance + amount
}
}

Notice that there is no use of locks, <code>synchronized</code> statements, or any other explicit synchronization code other than the <code>'''monitor'''</code> keyword. By definition, all the methods in the class are executed with mutual exclusion, removing the need to deal with synchronization independently.

===Synchronized===
In Java, the <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> 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 <code>lock</code>:<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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed, accessing a global FIFO queue, and modifying a global chained hash table. Finally these tests were performed on two different architectures, the Intel Nehalem and AMD Bulldozer with the languages C++, Java, & C# (.NET & Mono).

===Findings===
[[Image:cederman_queues.jpg|center|alt=Queue Results]]
[[Image:cederman_hashTs.jpg|center|alt=Hash Table Results]]

===Conclusions===

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

==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.

[[File:Koala.jpg]]

CSC 456 Fall 2013/7a ac

2013-11-26T03:38:45Z

Cejohns2: /* Ideas (temporary) */

=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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><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 <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> 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 <code>lock</code>:<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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#000000;color:#ffffff"|'''Windows, Linux, & Mac'''
|}

{|class="wikitable"
|+ Native Synchronization Support
!Language !! Semaphore/Mutex !! Monitor/Cond. Var !! Synchronized !! Other
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_java"/>
|-
|C/C++
|style="background:#000000"|<ref name="semaphore_c"/>
|style="background:#000000"|<ref name="conditional_c"/>
|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_ruby"/>
|style="background:#ffffff"|
|style="background:#ffffff"|
|-
|Python
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000;color:white"|Reentrant Lock<ref name="reentrant_python"/>
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|<ref name="sync_php"/>
|style="background:#ffffff"|
|-
|Perl
|style="background:#000000"|
|style="background:#000000"|<ref name="conditional_perl"/>
|
|style="background:#000000;color:white"|flock<ref name="flock_perl"/>
|-
|Fortran
|
|
|
|style="background:#000000;color:white"|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.

{|class="wikitable"
|+ External Synchronization Support
!Language !! OpenMP<ref name="openmp"/> !! PaStiX<ref name="pastix"/> !! Intel TBB !! RubySync
|-
|Fortran
|style="background:#000000"|
|style="background:#000000"|
|
|
|-
|C/C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|
|-
|Python
|
|style="background:#000000"|
|
|
|-
|Ruby
|
|
|
|style="background:#000000"|<ref name="rubysync"/>
|}
 

==A Study on the Behavior of Synchronization Methods [...]==
===Introduction===
There was a study in 2013 by the Computer Science and Engineering department at Chalmers University of Technology entitled: A Study on the Behavior of Synchronization Methods in Commonly Used Languages and Systems<ref name="cederman"/>, by Cederman et al. This paper analyzed the throughput and fairness of different lock methods across two architectures and three languages. Most benchmarks focus on throughput because this is a rough measurement of the 'speed' in terms of how much processing can be completed in a given amount of time. However the methods with the highest throughput usually have the lowest fairness, meaning they tend to starve one or more threads. This aspect is largely overlooked in synchronization methods and this paper addresses this issue. It uses a scale where 1 means all threads received equal work and 0 means at least one thread starved completely. They also measure synchronization across three different approaches: fine grain, coarse grain, and lock-free. These are implemented differently for the two tests that were perfomed, accessing a global FIFO queue, and modifying a global chained hash table. Finally these tests were performed on two different architectures, the Intel Nehalem and AMD Bulldozer with the languages C++, Java, & C# (.NET & Mono).

===Findings===
[[Image:cederman_queues.jpg|thumb|center|400px|alt=Queue Results]]
[[File:cederman_hashTs.jpg|thumb|center|400px|alt=Hash Table Results]]

[[Image:cederman_queuesA.jpg|thumbnail|right|600px|Figure 1[[#4foot|[4]]]]]

===Conclusions===

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
<ref name="reentrant_python">[http://effbot.org/zone/thread-synchronization.htm Python: ReLocks, Mutex, Cond. Vars]</ref>
<ref name="reentrant_java">[http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html Reentrant Lock (Java)]</ref>
<ref name="semaphore_c">[http://www.cplusplus.com/reference/mutex/mutex/?kw=mutex C Mutex]</ref>
<ref name="conditional_c">[http://www.cplusplus.com/reference/condition_variable/condition_variable/ C Conditional]</ref>
<ref name="conditional_ruby">[http://ruby-doc.org/stdlib-1.9.3/libdoc/thread/rdoc/ConditionVariable.html Ruby Conditional]</ref>
<ref name="sync_php">[http://www.php.net/manual/en/thread.synchronized.php PHP Synchronized]</ref>
<ref name="conditional_perl">[http://perldoc.perl.org/perlthrtut.html Perl: Mutex, Cond. Var]</ref>
<ref name="flock_perl">[http://perldoc.perl.org/functions/flock.html Perl flock]</ref>
<ref name="pastix">[http://pastix.gforge.inria.fr/files/README-txt.html PaStiX]</ref>
<ref name="rubysync">[http://www.ohloh.net/p/rubysync RubySync]</ref>
<ref name="cederman">[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf Cederman et al]</ref>

</references>

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

==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.

[[File:Koala.jpg]]

File:Koala.jpg

2013-11-26T03:37:38Z

Cejohns2: Test. Also, it's a Koala.

Test. Also, it's a Koala.

CSC 456 Fall 2013/7a ac

2013-11-19T17:06:36Z

Cejohns2: /* Supported Synchronization in Different Languages */

=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--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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><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.

===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 <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> 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 <code>lock</code>:<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 different programming languages and their support for various synchronization methods. The cells are color coded based on the following key:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#ff00ff;color:white"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ff00ff;color:white"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T17:00:29Z

Cejohns2: /* Synchronized */

=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--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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><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.

===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 <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> 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 <code>lock</code>:<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 different programming languages and their support for various synchronization methods. The cells are color coded based on the following key:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:52:35Z

Cejohns2: /* Semaphores and Mutexes */

=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--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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. Semaphores have an integer value representing the number of available units of a resource available. The <code>wait()</code> or <code>acquire()</code> 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 <code>signal()</code> or <code>release()</code> 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 <code>acquire()</code> and <code>release()</code><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.

===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 <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> keyword can be used to achieve synchronization:<ref name="java-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 <code>lock</code>:<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 different programming languages and their support for various synchronization methods. The cells are color coded based on the following key:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:35:28Z

Cejohns2: /* Semaphores and Mutexes */

=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--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, <code>wait()</code> and <code>signal()</code>, also known as <code>acquire()</code> and <code>release()</code>. 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 <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> keyword can be used to achieve synchronization:<ref name="java-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 <code>lock</code>:<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 different programming languages and their support for various synchronization methods. The cells are color coded based on the following key:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:34:04Z

Cejohns2: /* Synchronized */

=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--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()'', 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 <code>synchronized</code> keyword forces methods or even smaller pieces of code to be executed with mutual exclusion.<ref name="synchronized"/> C# has a <code>lock</code> 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 <code>synchronized</code> keyword can be used to achieve synchronization:<ref name="java-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 <code>lock</code>:<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 different programming languages and their support for various synchronization methods. The cells are color coded based on the following key:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:30:39Z

Cejohns2: /* Synchronized */

=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--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()'', 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.

This Java code shows how its ''synchronized'' keyword can be used to achieve synchronization:<ref name="java-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 different programming languages and their support for various synchronization methods. The cells are color coded based on the following key:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:27:16Z

Cejohns2: /* Locks */

=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--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()'', 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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:22:34Z

Cejohns2: /* Locks */

=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#:<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;
}
}
}

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:22:10Z

Cejohns2: /* Locks */

=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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:19:37Z

Cejohns2: /* Locks */

=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#:

<source lang=CSharp>
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;
}
}
}
</source>

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T16:08:16Z

Cejohns2: /* Semaphores and Mutexes */

=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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T04:40:38Z

Cejohns2: /* Supported Synchronization in Different Languages */

=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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#0000ff;color:white"|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T04:38:47Z

Cejohns2:

=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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx 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.

CSC 456 Fall 2013/7a ac

2013-11-19T04:37:39Z

Cejohns2: /* References */

=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?
==Ideas==
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.

==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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="slimrdwr">[http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Slim Reader/Writer Lock]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-19T04:37:07Z

Cejohns2: /* Supported Synchronization in Different Languages */

=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?
==Ideas==
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.

==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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|Slim Rd/Wr Lock (SRW)<ref name="slimrdwr"/>
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-19T04:35:44Z

Cejohns2: /* References */

=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?
==Ideas==
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.

==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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|Slim Rd/Wr Lock (SRW)
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="semaphore">[http://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-19T04:35:11Z

Cejohns2: /* References */

=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?
==Ideas==
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.

==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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|Slim Rd/Wr Lock (SRW)
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="lock">[http://en.wikipedia.org/wiki/Lock_(computer_science) Lock]</ref>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="openmp">[http://en.wikipedia.org/wiki/OpenMP OpenMP]</ref>
<ref name="synchronized">[http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html Java Synchronization]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-19T04:33:11Z

Cejohns2: /* Types of Synchronization */

=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?
==Ideas==
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.

==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.

===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:

{|class="wikitable"
|+ Supported Operating Systems Key
|'''None'''
|style="background:#0000ff;color:white"|'''Windows Only'''
|style="background:#00ff00"|'''Mac Only'''
|style="background:#ff0000;color:white"|'''Linux Only'''
|style="background:#00ffff"|'''Windows & Mac'''
|style="background:#ff00ff;color:white"|'''Windows & Linux'''
|style="background:#ffff00"|'''Mac & Linux'''
|style="background:#000000;color:#ffffff"|'''All'''
|}

{|class="wikitable"
|+ Synchronization Support
!Language !! Semaphore/Mutex !! Monitor !! OpenMP !! Synchronized !! Other
|-
|C
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|
|-
|Java
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|C++
|style="background:#000000"|
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|Slim Rd/Wr Lock (SRW)
|-
|C#
|style="background:#000000"|
|style="background:#ff0000"|
|style="background:#ffffff"|
|style="background:#000000"|
|
|-
|Ruby
|style="background:#000000"|
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Python
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|PHP
|style="background:#000000"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#ffffff"|
|Get Sources
|-
|Fortran
|style="background:#ffffff"|
|style="background:#ffffff"|
|style="background:#000000"|
|style="background:#ffffff"|
|Co-Array<ref name="coarray"/>
|}

==References==
<references>
<ref name="monitor">[http://en.wikipedia.org/wiki/Monitor_(synchronization) Monitor (synchronization)]</ref>
<ref name="coarray">[http://www.co-array.org Co-Array Fortran]</ref>
</references>

[http://www.cse.chalmers.se/~tsigas/papers/StudySynchronization-IPDPS13.pdf A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems Cederman et al.]

[https://developer.apple.com/library/mac/documentation/cocoa/conceptual/Multithreading/ThreadSafety/ThreadSafety.html Apple Synchronization]

[http://msdn.microsoft.com/en-us/magazine/jj721588.aspx C++ Sync Article]

CSC 456 Fall 2013/7a ac

2013-11-19T04:25:49Z

Cejohns2: /* Types of Synchronization */

CSC 456 Fall 2013/7a ac

2013-11-19T04:15:43Z

Cejohns2: /* Semaphores and Mutexes */

CSC 456 Fall 2013/7a ac

2013-11-19T04:14:57Z

Cejohns2: /* Types of Synchronization */

CSC 456 Fall 2013/7a ac

2013-11-19T03:59:05Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-14T15:45:28Z

Cejohns2: /* Types of Synchronization */

CSC 456 Fall 2013/7a ac

2013-11-12T20:27:16Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T20:26:26Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T20:24:54Z

Cejohns2: /* Survey of Primitives for Synchronization */

CSC 456 Fall 2013/7a ac

2013-11-12T19:43:56Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T19:43:19Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T19:41:43Z

Cejohns2:

CSC 456 Fall 2013/7a ac

2013-11-12T19:39:21Z

Cejohns2:

CSC 456 Fall 2013/7a ac

2013-11-12T19:32:18Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T19:30:11Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T19:30:03Z

Cejohns2: /* Supported Synchronization in Different Languages */

CSC 456 Fall 2013/7a ac

2013-11-12T19:29:41Z

Cejohns2: /* Supported Synchronization in Different Languages */

CSC 456 Fall 2013/7a ac

2013-11-12T19:27:38Z

Cejohns2:

CSC 456 Fall 2013/7a ac

2013-11-12T19:21:29Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T19:20:40Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T19:10:17Z

Cejohns2: /* Supported Synchronization in Different Languages */

CSC 456 Fall 2013/7a ac

2013-11-12T19:05:59Z

Cejohns2: /* References */

CSC 456 Fall 2013/7a ac

2013-11-12T19:03:43Z

Cejohns2: /* Supported Synchronization in Different Languages */

CSC 456 Fall 2013/7a ac

2013-11-12T17:22:09Z

Cejohns2: /* References */