1 of 45

​

Synchronization Pitfalls & Exercises

CS-446/646

C. Papachristos

Robotic Workers (RoboWork) Lab

University of Nevada, Reno

2 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

3 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

void deposit() { // properly synchronized

lock();

++ balance;

unlock();

}

void withdraw() { // no synchronization

-- balance;

}

Remember: Atomic operations

4 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

void deposit(account_t* acnt) {

lock(acnt->guard);

++ acnt->balance;

unlock(acnt->guard);

}

void withdraw(account_t* acnt) {

lock(acnt->guard);

-- acnt->balance;

unlock(acnt->guard);

}

int balance(account_t* acnt) {

int b;

lock(acnt->guard);

b = acnt->balance;

unlock(acnt->guard);

return b;

}

balance_stamped sum(account_t* a1, account_t* a2) {

balance_stamped sum_stamped;

gettimeofday(&sum_stamped.tv, NULL);

sum_stamped.balance = balance(a1) + balance(a2);

return sum_stamped;

}

​

void transfer(account_t* a1, account_t* a2) {

withdraw(a1);

deposit(a2);

}

void test() {

int A_bal= A.balance();

transfer(A, A);

assert(A.balance()==A_bal);

}

5 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

int sum(account *a1, account *a2) {

int s;

​

lock(a1->guard);

lock(a2->guard);

​

s = a1->balance;

s += a2->balance;

​

unlock(a2->guard);

unlock(a1->guard);

return s

}

Note: Can be prevented by a separate sum Lock, or by Static Ordering of Resources (more on that later)

sum(A, B);

Thread 1

sum(B, A);

Thread 2

lock(A->guard);

​

lock(B->guard);

​

lock(A->guard);

​

lock(B->guard);

Block

Block

6 of 45

Synchronization Errors

Example 4-a: Deadlock crossing Abstraction Boundaries

​

Example when composing operations of Mutex and a Condition Variable:

​

​

​

​

​

​

​

​

  • The Cond Var Parts could be inside functions foo and bar that are unknown to us implementation-wise

​

  • Caution: Dangerous to hold Locks (generally) across Abstraction Boundaries

CS446/646 C. Papachristos

lock(a);

​

lock(b);

​

while(!ready)

​

wait (cv, b);

​

unlock(b);

​

unlock(a);

Thread 1

lock(a);

​

lock(b);

​

ready = true;

​

signal (cv);

​

unlock(b);

​

unlock(a);

Thread 2

Thread 1 reaches :

wait (cv, b); b Unlocked,

but a Locked;

Thread 2 starts, but will never past its lock(a) to proceed to signal() Thread 1

​

  • Deadlock

Mutex

Part

Cond

Var

Part

foo();

bar();

7 of 45

Synchronization Errors

Example 4-b: Monitors also do not compose

​

​

​

​

​

​

​

​

​

  • Caution: Holding Locks (in this case Monitor Lock) across Abstraction Boundaries
    • foo and bar are internally using Condition Variables of another Monitor
    • The Monitor M2’s Procedure cannot know runtime semantics of M1 to ensure it adheres by the fundamental Monitor operations

CS446/646 C. Papachristos

monitor M1 {

cond_t cv;

foo() {

…

// releases monitor lock

wait(cv);

}

​

bar() {

…

signal(cv);

}

};

monitor M2 {

f1() {

…

M1.foo();

}

​

​

f2() {

…

M1.bar();

}

};

8 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

void foo() {

pthread_mutex_lock(&mut);

while (value <= 10.5 * 3.14159265358979)

pthread_cond_wait(&cond, &mut);

​

… // do work

}

void bar() {

… // do work

​

value += 0.1 * 3.14159265358979 ;

​

pthread_cond_signal(cond);

}

double value = 0.0; pthread_mutex_t mut; pthread_cond_t cond;

9 of 45

Synchronization Errors

Deadlock Conditions (all need to hold)

​

  • Mutual Exclusion
    • At least one Resource must be held exclusively (in a non-sharable mode)
  • Hold and Wait
    • There must be one process holding one Resource and waiting for another Resource
  • No Preemption
    • Resources are Non-Preemptable (Critical Sections cannot be aborted externally)
      • vs Preemptable (can be taken away from a process without hurting its execution)
  • Circular Wait
    • There must exist a set of processes [P1, P2,…,Pn] such that P1 is waiting for P2, P2 for P3, …, and Pn for P1

​

Two approaches to dealing with a Deadlock

  • Proactive: Prevention
  • Reactive: Detection & Correction

CS446/646 C. Papachristos

10 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

Pi

Rj

Pi

Rj

Pi

Rj

Note: Edge removed on unlock()

Note: Request Edge Converted to Assignment Edge on return of lock()

11 of 45

Synchronization Errors

Deadlock Prevention by Elimination of Circular Waiting

​

Example:

Resource Allocation Graph

​

​

CS446/646 C. Papachristos

12 of 45

Synchronization Errors

Deadlock Prevention by Elimination of Circular Waiting

​

Example:

Resource Allocation Graph

with a definite

Deadlock

​

​

​

Note:

Resources that participate in

Circular Wait are exhausted,

and entirely allocated to the�waiting processes

CS446/646 C. Papachristos

13 of 45

Synchronization Errors

Deadlock Prevention by Elimination of Circular Waiting

​

Example:

Resource Allocation Graph

and a possible

Deadlock

​

​

​

Note:

Resources that participate in

Circular Wait are exhausted,

but allocated to different�processes than the waiting ones

CS446/646 C. Papachristos

14 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

Note: E.g. to avoid multi-Mutex Deadlocks, we can make sure that there is a Static Global Order for all Mutexes (How?),�and every program always takes and releases Locks in that order (But also look at C++ std::lock() with Deadlock Avoidance)

Remember: Example 3 where Lock objects a->guard & b->guard are�flipped in the order they are lock()ed by the 2 different Threads

15 of 45

Synchronization Errors

Dealing with a Deadlock

​

  • Ignore it (until it goes away) – “Ostrich” approach

​

  • Deadlock Prevention – Make it impossible for a Deadlock to happen

​

  • Deadlock Avoidance – Control allocation of Resources
    • Provide information in advance about what Resources will be needed by Processes to guarantee that Deadlock will not happen
    • System only grants Resource Requests if it is guaranteed that the Process can obtain all Resources it is going to need in every future Requests
    • Effectively avoids Circular-Waits (Wait Dependencies), but it is impractical (and hard) to have to determine in advance all Resources that will be needed

​

  • Deadlock Detection & Recovery – Look for a Cycle in dependencies; “break” the Cycle

CS446/646 C. Papachristos

16 of 45

Synchronization Errors

Banker’s Algorithm

​

Classic Deadlock Avoidance approach for Resources with multiple units

​

1. Assign a Credit Limit to each Customer (Process)

  • For every Process, we must establish its required Credit Limit (max number of Resources expected to be Requested) in advance – impractical

​

2. Reject any Request that leads to an Unsafe State

  • Unsafe State: One where a Sudden Request by any Customer�up to their full Max Credit Limit could lead to a Deadlock
  • Use a recursive reduction procedure to discover Unsafe States�and skip them (allow Rj allocation only for Safe Pi Requests,�and iterate to find sequence of only Safe Pi Requests)

​

3. In practice: System must keep Resource usage well� below capacity to maintain a surplus

  • Should rarely have to be invoked due to low Resource utilization

CS446/646 C. Papachristos

Process

Allocated

Max

Available

A B C

A B C

A B C

P0

0 1 0

7 5 3

3 3 2

P1

2 0 0

3 2 2

P2

3 0 2

9 0 2

P3

2 1 1

2 2 2

P4

0 0 2

4 3 3

*Sudden Request: Customer requests all its Max Resources (but then finishes)

17 of 45

Synchronization Errors

Deadlock Detection & Recovery

​

Deadlock Detection

​

  • Detection
    • Traverse the Resource Allocation Graph looking for Cycles
    • If a Cycle is found, Preempt Resource (force a Process that holds it to release it)

​

  • Expensive
    • Many Processes and Resources to traverse
      • Cycle Detection algorithm (e.g. Depth-First Search) has to be ran and parse every Node of the Graph (can have multiple connected components)

​

  • Algorithm invoked depending on
    • How frequent or likely Deadlock is
    • How many Processes are likely to be affected when it occurs

CS446/646 C. Papachristos

18 of 45

Synchronization Errors

Deadlock Detection & Recovery

​

Deadlock Recovery

​

After a Deadlock has been detected, two main options:

  • i) Abort Processes
    • Abort all Deadlocked Processes
      • Processes need to be started over
    • Abort one Process at a time until Cycle is eliminated
      • System needs to rerun Deadlock Detection after each abort
  • ii) Preempt Resources (force their release)
    • Need to: a) Select Process and Resource to Preempt; b) Suspend selected Process until Resource becomes available again; c) Allocate released Resource to a Requesting Process

​

  • Other methods:
    • Priority Inversion (more on that later in Scheduling Lecture); can lead to Starvation
    • Rollback to previous state (used in Database systems)

CS446/646 C. Papachristos

19 of 45

Synchronization Errors

Race Detection

​

Data Race Detection

​

Will only focus on Data Race Detection

  • Techniques also exist to detect Atomicity and Order Race bugs

​

  • Approach 1:
    • Happens-Before

​

  • Approach 2:
    • Lockset (Eraser Algorithm)

CS446/646 C. Papachristos

20 of 45

Synchronization Errors

Race Detection

​

Happens-Before relationship & proper Synchronization

​

Definition: Event A “Happens-Before” Event B if:

  • Case I: When both in the same Thread
    • B follows A
  • Case II: When A in Thread 1, and B in Thread 2, exists a Synchronization Event C such that
    • A happens in Thread 1
    • C is after A in Thread 1 and before B in Thread 2
    • B happens in Thread 2

​

  • To detect Data Race, have to monitor all data Accesses & Synch operations, watch for:
    • Access of shared location v happens in Thread T1
    • Access of shared location v happens in Thread T2
    • No Synchronization operation happens between the accesses
    • One of the accesses is a Write

CS446/646 C. Papachristos

21 of 45

Synchronization Errors

Race Detection

​

Violation of Happens-Before for Data Race Detection

​

Problems:

  • Expensive
    • Requires per-Thread:
      • List of all Accesses to shared data
      • List of all Synchronization operations

​

  • High False-Negative rate

​

    • Happens-Before looks out for Data Races that will take place during Runtime
      • i.e. moments when different Threads actually Access shared data w/o any Synchronization operation having taken place inbetween

Note: “any” – approach has no nuance about relationship between shared data and Synch operations

​

    • Depends on Scheduler-controlled interleaving of events to elicit actual Data Races

CS446/646 C. Papachristos

22 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

23 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

24 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

25 of 45

Synchronization Errors

 

CS446/646 C. Papachristos

more strict refinement rule for Write-access

26 of 45

Synchronization Errors

Race Detection

​

Eraser – Implementation

​

​

  • Binary (Runtime) tool

Pros:

      • Does not require source code

Cons:

      • Loses source code semantics
      • Can track Memory accesses at Word-level granularity

​

  • How to monitor Memory access to implement tracking for the Lockset Algorithm?
    • Keep a Shadow Word for each Memory Word in the Program’s Data Section and on the Heap
    • Each Shadow Word stores the index of a Lockset
    • A Table used to map from Lockset index to a set of Locks
    • Assumption: Not excessively many distinct Locksets

CS446/646 C. Papachristos

27 of 45

Synchronization Errors

Race Detection

​

Eraser – Overview

​

​

  • Successes
    • Can help detect bugs in mature software
    • Still suffers from limitations;
      • Major: Benign Races (“intentional” Races)

​

  • Drawbacks
    • Slow: Monitoring each Memory access is costly
      • Can incur 10-30x slowdowns
    • Improvement:
      • Code Static Analysis
      • Smart instrumentation (e.g. sampling)

​

  • Lockset Algorithm is influential & used by many tools
    • e.g. Helgrind (a Race Detection tool in Valgrind)

CS446/646 C. Papachristos

Example Benign Race 1:

“Double-Checks” for Lazy Initialization

if (!init_flag) {

lock();

if (!init_flag) {

my_data = ...;

init_flag = true;

}

unlock();

}

tmp = my_data;

Idea: Faster if init_flag is true most of the time (i.e. data initialized already)

But: Wrong! Compiler/Hardware may reorder lines, loads/stores, etc.

Example Benign Race 2:

“Statistical” counter

++ nrequests;

Even this can happen (speculatively)

Possible

reordering

28 of 45

Synchronization Errors

Memory Synchronization Ordering

​

Since we touched the subject…

​

​

  1. Cache (Memory) Coherence
  2. Property concerning an individual Memory location
    • System must appear to execute all Threads’ loads and stores to a single Memory location in a Total Order * that respects the Program Order of each Thread.

​

  1. Memory Consistency
  2. Property concerning order of access of all Memory locations
    • ( Sequential Consistency model: ) System must appear to execute all Threads’ loads and stores to all Memory locations in a Total Order * that respects the Program Order of each Thread.

​

* Each load gets the value of the most recent store in that Total Order.

CS446/646 C. Papachristos

Previous Broken Example:

“Double Checked Locking”

if (!init_flag) {

lock();

if (!init_flag) {

my_data = ...;

init_flag = true;

}

unlock();

}

tmp = my_data;

Wrong! Compiler/Hardware may reorder lines, loads/stores, etc.

Possible

reordering

Even without Compiler reordering, how to guarantee Memory Consistency across multiple Threads of a Multi-Processor system?

Even this can happen (speculatively)

29 of 45

Synchronization Errors

Memory Synchronization Ordering

​

  1. Cache (Memory) Coherence

​

  • Performance requires Memory Caches
    • Divided into chunks called Cache Lines (e.g. 64 Bytes)
    • Caches create an opportunity for different Cores to disagree about Memory

​

  • A solution: Bus-based approaches
    • “Snoopy” protocols, each CPU listens to Memory Bus
    • Use “Write-Through” (vs “Write-Back”) and invalidate when you see a Write bit
    • Bus-based schemes limit scalability

​

  • Modern CPUs use Networks

(e.g. AMD’s Hypertransport, Intel’s QPI (Quick Path Interconnect) & UPI (Ultra Path Interconnect))

    • CPUs pass each other Messages about Cache Lines

CS446/646 C. Papachristos

30 of 45

Synchronization Errors

Memory Synchronization Ordering

​

  1. Cache (Memory) Coherence - MESI Coherence Protocol
  2. Modified
    • The Cache Line is present in current Cache, but is Dirty

i.e. needs to be written-back to Memory at some point in the future, before allowing more reads from Memory

    • Must Invalidate (change to Invalid state) all copies in other Caches before entering this state
    • The write-back changes the Cache Line into the Shared state
  • Exclusive
    • The Cache Line is only present in current Cache, and is Clean (matches the Main Memory)
  • Shared
    • The Cache Line may be present in other Caches as well, and is Clean (matches the Main Memory)
  • Invalid
    • The Cache Line is Invalid (unused)
  • Owned (enhanced “MOESI” Protocol – “Owned” state used to represent data both Dirty and Shared)
    • This Cache Line is one of several copies in the system (sort of like Shared state)
    • This Cache cannot modify the copy, and it is Dirty (like Modified state) and this Cache is exclusively responsible to eventually write-back to Main Memory
    • Has to respond to Snoop requests (ensure stale Memory isn’t used)
    • Can have both one Owned and multiple Shared copies of the same Line
      • Allows longer deferring of write-back to Main Memory

CS446/646 C. Papachristos

31 of 45

Synchronization Errors

Memory Synchronization Ordering

​

  1. Cache (Memory) Coherence – Core & Bus Actions
  2. Actions performed by CPU Core
    • Read
    • Write
    • Evict (if Modified, must Write-Back)

​

  • Transactions on Bus (/ Interconnect)
    • Read : Without intent to modify, data can come from Memory or another Cache
    • Read-Exclusive : With intent to modify, must Invalidate all other Cache copies
    • Write-Back : Contents put on Bus and Memory is updated

​

  • Modern Machines use cc-NUMA (cache-coherent Non-Uniform Memory Access) Architectures
      • Older Machines had “Dance Hall” Architectures, with every CPU “dancing” equally with Memory
    • In cc-NUMA, each CPU has faster access to some “closer” Memory, and slower access to farther Memory
    • Use a Directory to keep track of who is Caching what

​

  • Shared Memory programming & parallel execution with arbitrarily many CPU Cores lends itself to dynamic (i.e. Runtime) performance optimizations

CS446/646 C. Papachristos

32 of 45

Synchronization Errors

Memory Synchronization Ordering

​

  1. Memory Consistency – Consistency Model

​

  • Contract whereby the system guarantees that if the rules of the model’s Memory Semantics are followed, the Memory will be consistent and the results of reading, writing, or updating Memory will be predictable (repeatable)
  • Consistency deals with the Ordering of operations to multiple Memory locations with respect to all Processors

​

  • Strict Consistency
    • A Write to a variable by any Processor needs to be seen instantaneously by all Processors
    • Strongest model, fully deterministic, but only theoretical (instantaneous message-passing is impossible)

​

  • Sequential Consistency
    • “If reads & writes of all Processes are executed in some sequential order, and the Operations of each individual Processor appear in this sequence in the Order specified by its Program”

​

    • Writes to variables by different Processors have to be seen in the same order by all Processors
      • A Process can see the Writes of all other Processes, but only its own Read operations
    • A Processor’s Operations have to appear to be executed instantaneously (/Atomically) w.r.t. every other Processor
      • e.g. with a globally shared Bus, posting a line with information is seen by all Processors instantaneously

​

    • Model has no notion of Time, only Order of Operations

CS446/646 C. Papachristos

33 of 45

Synchronization Errors

Memory Synchronization Ordering

​

  1. Memory Consistency – Consistency Model
  2. Relaxed Memory Consistency
    • Relaxation of one or more requirements of Sequential Memory Consistency

​

Relaxation of Program Order :

      • relax any or all the ordering of Operation pairs, Write-after-Write, Read-after-Write, or Read/Write-after-Read
        • i.e. can accomplish increased performance at the cost of Memory Inconsistency; there is a need for Hardware-aware programming (Software) to ensure Memory Consistency through proper Synchronization

Relaxation of Atomicity :

      • a Process can view its own Writes before any other Processors
        • i.e. a Processor is allowed to Read the value of its own Write, and prevents other Processors from Reading another Processor’s Write before the Write is visible to all other Processors

​

  • Different Processor Architectures follow different models
    • Intel x86 follows the Total Store Order (TSO) model: “Weak Ordering” allows reordering of Memory Operations but ensures that Operations to the same Memory location are seen in the same Order by all Processors
    • ARMs have a “Weaker” model: Non-Globally Consistent; allows Operations to become�visible to other Processors in a different Order than they appear in the Program

C. Papachristos

34 of 45

Synchronization Errors

Memory Synchronization Ordering

​

Back to our problem…

​

Architectures offer Memory Ordering Instructions

  • e.g. x86 Architecture sfence, mfence, lfence …
    • sfence: Processor ensures that every store prior to sfence is�Globally Visible before any store after sfence becomes Globally�Visible.
    • mfence: Guarantees that every load and store Instruction that pre-�cedes mfence in Program Order becomes Globally Visible before any load or store Instruction that follows mfence.
    • lfence: Performs a serializing operation on all load-from-Memory Instructions that were issued prior to lfence. Instruction does not execute until all prior Instructions have completed locally, and no later Instruction begins execution until lfence completes.

​

Can be emitted with known tools (Extended Assembly):

  • e.g. asm volatile ("sfence" ::: "memory");

Previous Broken Example:

“Double Checked Locking”

if (!init_flag) {

lock();

if (!init_flag) {

my_data = ...;

init_flag = true;

}

unlock();

}

tmp = my_data;

Possible

reordering

Even this can happen (speculatively)

Remember: The “memory” clobber that�forms a Memory Barrier for the Compiler

CS446/646 C. Papachristos

35 of 45

Synchronization Errors

Memory Synchronization Ordering

​

Back to our problem…

​

C (/C++) offers portable Atomics

  • Definitions contained in <stdatomic.h>
    • Atomic Types: atomic_bool, atomic_int, atomic_long, …�Even with types that an Architecture is expected to Atomically execute�Operations (e.g. int store), the Compiler is free to perform many�unexpected optimizations, e.g. combine a variable with another in�the same Memory location, completely remove it from a loop, keep it in a CPU Register, etc. �Atomic Types is a portable way to inform the Compiler how to properly treat the variable (for Concurrency)

​

    • Atomic Loading / Storing: atomic_load_explicit() / atomic_store_explicit()�Atomically reads and returns / replaces the value of an Atomic object. Allows specification of memory_order semantics to be used (memory_order_relaxed, memory_order_acquire / memory_order_release, …)

​

    • Memory Synchronization Ordering: atomic_thread_fence(memory_order order)�Impose Ordering of non-Atomic and Relaxed Atomic accesses, as instructed by the order.

​

Previous Broken Example:

“Double Checked Locking”

if (!init_flag) {

lock();

if (!init_flag) {

my_data = ...;

init_flag = true;

}

unlock();

}

tmp = my_data;

Possible

reordering

Even this can happen (speculatively)

CS446/646 C. Papachristos

36 of 45

Synchronization Errors

Memory Synchronization Ordering

​

Back to our problem…

​

Fixing Double-Checked Locking with explicit Memory Barriers

CS446/646 C. Papachristos

atomic_bool init_flag;

…

​

bool flag = atomic_load_explicit(&init_flag, memory_order_relaxed);

​

atomic_thread_fence(memory_order_acquire);

​

if (!flag) { // replaces: if(!init_flag)

​

pthread_mutex_lock(&mut);

​

f = atomic_load_explicit(&init_flag, memory_order_relaxed);

​

if (!flag) { // replaces: if(!init_flag)

​

my_data = ...; // some expensive data initialization

​

atomic_thread_fence(memory_order_release);

​

atomic_store_explicit(&init_flag, true , memory_order_relaxed); // replaces: init_flag=true;

​

}

pthread_mutex_unlock(&mut);

}

​

tmp = my_data;

Guarantees that Read/Write Operations before a Memory Barrier cannot be reordered with Write Operations after the Memory Barrier

Guarantees that Read/Write Operations after a Memory Barrier cannot be reordered with Read Operations before the Memory Barrier

37 of 45

Synchronization Errors

Memory Synchronization Ordering

​

Back to our problem…

​

Fixing Double-Checked Locking with explicit Memory Barriers

CS446/646 C. Papachristos

atomic_bool init_flag;

…

​

bool flag = atomic_load_explicit(&init_flag, memory_order_relaxed);

​

atomic_thread_fence(memory_order_acquire);

​

if (!flag) { // replaces: if(!init_flag)

​

pthread_mutex_lock(&mut);

​

f = atomic_load_explicit(&init_flag, memory_order_relaxed);

​

if (!flag) { // replaces: if(!init_flag)

​

my_data = ...; // some expensive data initialization

​

atomic_thread_fence(memory_order_release);

​

atomic_store_explicit(&init_flag, true , memory_order_relaxed); // replaces: init_flag=true;

​

}

pthread_mutex_unlock(&mut);

}

​

tmp = my_data;

Why not just a bool (its Read/Write accesses should be Atomic, right) ?

Note:� volatile could work…

38 of 45

Synchronization Exercises

Reader(s)-Writer(s)

​

Remember: Allow exclusively either a single Writer or multiple Readers

​

​

CS446/646 C. Papachristos

// number of readers

int readcount = 0;

// mutual exclusion to readcount

mutex_t mutex;

// exclusive writer or reader (binary sem)

semaphore_t w_or_r(1);

​

​

​

void writer() {

wait(&w_or_r); // lock out readers

// write()

​

post(&w_or_r); // up for grabs

}

void reader() {

lock(&mutex); // lock readcount

​

readcount += 1; // have one more reader

if (readcount == 1) // NOT(!): >= 1

wait(&w_or_r); // synch w/ writers

​

unlock(&mutex); // unlock readcount

​

// read()

​

lock(&mutex); // lock readcount

​

readcount -= 1; // have one less reader

if (readcount == 0)

post(&w_or_r); // up for grabs

​

unlock(&mutex); // unlock readcount

}

39 of 45

Synchronization Exercises

 

CS446/646 C. Papachristos

40 of 45

Synchronization Exercises

Bounded-Buffer

​

Remember: Ring Buffer with Empty / Full limitations

​

​

CS446/646 C. Papachristos

// mutex to shared buffer internal properties (e.g. head, tail)

mutex_t mutex;

// count of empty slots

semaphore_t empty(N);

// count of filled-up slots

semaphore_t filled(0);

​

void producer() {

while (1) {

// produce_new_resource()

wait(&empty); // wait for 1 empty slot

lock(&mutex); // lock buffer list

// insert_resource_to_buffer()

unlock(&mutex); // unlock buffer list

post(&filled); // notify +1 filled slot

}

}

void consumer() {

while (1) {

wait(&filled); // wait for 1 filled slot

lock(&mutex); // lock buffer list

// extract_resource_from_buffer()

unlock(&mutex); // unlock buffer list

post(&empty); // notify +1 empty slot

// consume_resource()

}

}

41 of 45

Synchronization Exercises

Bounded-Buffer

​

Why is mutex required?

​

Where are the Critical Sections?

​

What conditions lead to a Deadlock?

  • N = 0
  • empty = 0 and filled = 0 , and no Thread has yet entered their Critical Section
    • Also, empty = 0 and filled = 0 can lead to single-Producer single-Consumer “ping-pong”

​

What happens if operations on mutex and filled/empty are switched around?

    • i.e. a Consumer doing:

​

    • e.g. sequences such as:
      • (from empty) – 1 Consumer, then anyone
      • (from empty) – N+1 Producers, then 1 Consumer
  • The pattern of post/wait on filled/empty is a common construct often called an Interlock

CS446/646 C. Papachristos

while (1) {

lock(&mutex);

wait(&filled);

If we Block here (due to filled=0 slots available), the mutex is also Locked, and will remain, because no Producer will be able to proceed into its Critical Section to produce & post() (increment) filled.

42 of 45

Synchronization Exercises

H2O Problem

​

Form water out of two Hydrogen Threads and one Oxygen Thread (H2O)

    • Two procedures: HArrives() and OArrives()
    • A water molecule forms when two (2) H Threads are present and one (1) O Thread
    • Otherwise, the “atoms” must wait
    • Once all three are present, one of the Threads calls make_water() and only then, all three depart

​

Key variables:

    • int numH – Keeps track of number of H Threads waiting
    • int numO – Keeps track of number of O Threads waiting
    • mutex_t mutex – Control access to numH and numO
    • List<thread_status *> waitingH – H Threads waiting Queue
    • List<thread_status *> waitingO – O Threads waiting Queue

​

    • struct thread_status { // to keep in a queue allowing to suspend/wakeup threads� bool ready; // condition predicate� condition_t cv; // condition variable (controls thread suspension)�};

CS446/646 C. Papachristos

43 of 45

Synchronization Exercises

H2O

Problem

​

​

CS446/646 C. Papachristos

int numH = 0; // (global) number of H threads waiting

int numO = 0; // (global) number of O threads waiting

mutex_t mutex; // mutual exclusion

List<thread_status *> waitingH; // H threads waiting queue

List<thread_status *> waitingO; // O threads waiting queue

void HArrives() {

lock(&mutex);

numH++;

if (numH == 2 && numO >= 1) {

h = waitingH.pop();

o = waitingO.pop();

h->ready = true;

o->ready = true;

cond_signal(&h->cv);

cond_signal(&o->cv);

numH -= 2;

numO -= 1;

// make_water()

}

else {

h = new thread_status;

waitingH.push(h);

while (!h->ready)

cond_wait(&h->cv, &mutex); // releases mutex

delete h;

}

unlock(&mutex);

}

44 of 45

Synchronization Exercises

H2O

Problem

​

​

CS446/646 C. Papachristos

int numH = 0; // (global) number of H threads waiting

int numO = 0; // (global) number of O threads waiting

mutex_t mutex; // mutual exclusion

List<thread_status *> waitingH; // H threads waiting queue

List<thread_status *> waitingO; // O threads waiting queue

void OArrives() {

lock(&mutex);

numO++;

if (numH >= 2) {

h1 = waitingH.pop();

h2 = waitingH.pop();

h1->ready = true;

h2->ready = true;

cond_signal(&h1->cv);

cond_signal(&h2->cv);

numH -= 2;

numO -= 1;

// make_water()

}

else {

o = new thread_status;

waitingO.push(o);

while (!o->ready)

cond_wait(&o->cv, &mutex); // releases mutex

delete o;

}

unlock(&mutex);

}

45 of 45

Time for Questions !

CS-446/646

CS446/646 C. Papachristos