Syncronization Patterns
We provide a set of global invariant patterns or idioms that can be used directly or composed to produce more complex synchronization specifications.
- Bound(R, n): at most n threads can be in R at any point in time.
- Exclusion (R_1, R_2, ..., R_n): at any point in time, threads can be in at most one synchronization region out of the n synchronization regions.
- Resource((R_P, N_P), (R_C, N_C), n): a pool of resources (with n items in the pool initially) accessed by a producer region R_P that produces N_P resource items each time a thread executes it, and a consumer region R_C that consumes N_C resource items each time a thread executes it. If there are fewer than N_C resource items in the pool, a thread executing R_C waits at the entrance of the region until there are at least N_C resources in the pool.
- Barrier(R_1,R_2): the k'th thread to enter R_1 and the k'th thread to enter R_2 meet at their respective synchronization regions and leave together.
- Relay(R_1, R_2): a thread entering R_1 can leave R_1
immediately; however, the k'th thread entering R_2 is blocked
and cannot leave R_2 until the k'th thread arrives
at R_1.
In this situation, an arrival of a thread at R_1 triggers
a release of a thread at R_2.
It is convenient to extend the barrier synchronization to the following more general form, called the Group synchronization. - Group((R_1, N_1), (R_2, N_2), ..., (R_n, N_n)): N_i threads entering R_i for i between 1 and n meet, form a group, and leave the respective synchronization regions together. For example, let n = 3, N_1 = 2, N_2 = 3, and N_3 = 4. Then, 2 threads in R_1, 3 threads in R_2, and 4 threads in R_3 form a group and leave together.
- Asymmetric Group((n,R_11,N_11,R_12,N_12...,R_1n,N_1n,m,R_21,N_21,R_22,N_22,...,R_2m,N_2m):
A cluster consists of multiple synchronization regions.
The regions are divided into two sets. One set has
n regions R_1i, and another has
m regions R_2j. The two sets may overlap.
For 0 <= k, all threads from the (k * N_2j)th thread to
the ((k+1) * N_2j - 1)th thread entering R_2j
may leave their respective regions only if all
threads from the (k * N_1i)th thread to the
((k+1) * N_1i - 1)th thread have arrived at regions
R_1i.
Pattern-based synchronization specifications are formed by composing instances of the above patterns where composition is interpreted as logical conjunction.