Synchronization:

Patterns

Condition
Variables
&
Semaphores

25-03-03 CMPT 201 Slides 8.2 © Dr. B. Fraser 1

 Topics

●
Can we do something more powerful than just locking?
– Condition variables to “signal” other threads.
– Semaphores to count how many things are available.
●
Can we allow multiple readers but only one writer?
●
What can we solve with synchronization?
– How do dining philosophers help us with sychronization?
– What’s a circular buffer?

25-03-03 2
 Condition Variables

25-03-03 3
 Producer-Consumer pattern -

●
Producer-Consumer
A common programming pattern.
– Producer(s): one set of threads creating data.
- 3 common
lication
– Consumer(s): one set of threads using the data.
-
– Store data: shared resource (e.g., variable or buffer) to hold
- -

the values that have been produced but not yet consumed.
-

-
.. needs protection
This shard resource

25-03-03 4
 ABCD: Data race
the variable informa
>
-
shared global ,
static
mases
linkage
static int avail = 0; outside
variabl which means nobody of this fil can
access it

int main() { static void *thread_func(void *arg) {

pthread_t t1; for (;;) {
pthread_create(&t1, NULL, thread_func, NULL); avail++;
sleep(1);
for (;;) { }
while (avail > 0) {
printf("I just consumed %d\n", avail); return 0;
no
avail--; }
} mutex
}
pthread_join(t1, NULL); 2 threads
- X
}
main t
●
Is there a data race in this code?
have a data van
-a) Yes, two threads change a shared variable. so we

b) No, one increments, the other decrements. Still It's a Race case

c) No, avail is static. > dosn't prevent

-

rais

d) No, main()’s while loop prevents concurrent edits to a shared variable.

X
val
It dosn't prevent
25-03-03 5
 Producer-Consumer
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static int avail = 0;

int main() { static void *thread_func(void *arg) {

pthread_t t1; for (;;) {
pthread_create(&t1, NULL, thread_func, NULL); pthread_mutex_lock(&mtx);
{
for (;;) {
pthread_mutex_lock(&mtx);
{ avail++;
Simulate making
while (avail > 0) { something one at
// Simulate "consume everything available" a time.
printf("I just consumed %d\n", avail); }
avail--; pthread_mutex_unlock(&mtx);
Simulate consuming sleep(1);
} something: decrement to 0 }
}
pthread_mutex_unlock(&mtx); return 0;
}
pthread_join(t1, NULL);
↓ }
} we sams

mute , in both to
↓ to stor data , avoids
data
serialize acces
rec

25-03-03 6

Program might work sometimes but fail due to

corvicncy
I just consumed 0
I just consumed 1
-output
I just consumed 1
 ABCD: Efficiency
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static int avail = 0;

int main() {
pthread_t t1; static void *thread_func(void *arg) {
pthread_create(&t1, NULL, thread_func, NULL); for (;;) {
pthread_mutex_lock(&mtx);
for (;;) { {
pthread_mutex_lock(&mtx); avail++;
{ }
while (avail > 0) { pthread_mutex_unlock(&mtx);
// Simulate "consume everything available" sleep(1);
printf("I just consumed %d\n", avail); }
avail--;
return 0;
} }
}

}
pthread_mutex_unlock(&mtx); ●
What is the major source of
pthread_join(t1, NULL); inefficiency in this program?
}

↑
a) Wasted space: Use of an int when a bool would be better for `avail`.

I
b) Wasted CPU: main keeps looping even when nothing to consume.
Y
c) Wasted CPU: main locking & unlocking mutex when there are
multiple values to consume. we don't lock again & again

25-03-03 d) Wasted CPU: Program will never end. True Out one
7
but not
thing
a bad

work hers
might lot
bring like
a consumer

but when we
the Good can do 2 things
only
#include <pthread.h>
#include <stdio.h>
T = 0 seconds (Program starts)
#include <unistd.h>
1main() runs and creates t1 (producer thread).
2avail = 0.
static int avail = 0;
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER; T = 0s to 1s (First loop)
Producer thread (thread_func):
// Producer thread • Locks mutex.
void *thread_func(void *arg) { • Increments avail = 0 + 1 = 1.
• Unlocks mutex.
for (;;) { • Sleeps for 1 second (sleep(1)).
pthread_mutex_lock(&mtx); Consumer thread (main loop):
avail++; • Runs much faster (busy-loop).
pthread_mutex_unlock(&mtx); • Locks mutex.
• Sees avail == 0, so unlocks and repeats the loop.
sleep(1); • Keeps spinning, acquiring/releasing the mutex very quickly (until producer sets avail
} = 1).
return NULL;
}
The consumer thread is wasting CPU by busy-waiting:
// Consumer thread (main) • Even when there is nothing to consume (avail == 0), it keeps spinning inside the for (;;) loop.
int main() { • This is why the earlier quiz said "wasted CPU".
pthread_t t1;
pthread_create(&t1, NULL, thread_func, NULL);
If we remov
sleep (1) from p
for (;;) { avail grows rapidly:

pthread_mutex_lock(&mtx); • The producer will outpace the consumer thread.

avail will keep increasing: 1, 2, 3, 4, ..., 1000, ..., 10000, etc.
while (avail > 0) {
•
Consumer thread:

printf("I just consumed %d\n", avail); The consumer is slower because it:
• Prints text to the terminal (which takes time).
avail--; • Runs fewer iterations compared to the blazing-fast producer.

}
pthread_mutex_unlock(&mtx);
// Optional sleep to reduce CPU usage
Y output
-

,
}
I just consumed 1
pthread_join(t1, NULL); X neur I just consumed 1
return 0;
}
expected I just consumed 1

i
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static int avail = 0; Producer-Consumer
int main() {
pthread_t t1;
(with Error Checking)
int s = pthread_create(&t1, NULL, thread_func, NULL); =>
if (s != 0) {
perror("pthread_create");
exit(1);
}

for (;;) {
s = pthread_mutex_lock(&mtx);
if (s != 0) {
perror("pthread_mutex_lock");
exit(1);
}
static void *thread_func(void *arg) {
while (avail > 0) { for (;;) {
printf("I just consumed %d\n", avail); int s = pthread_mutex_lock(&mtx);
avail--; if (s != 0) {
} perror("pthread_mutex_lock");
pthread_exit((void *)1);
s = pthread_mutex_unlock(&mtx); }
if (s != 0) { avail++;
perror("pthread_mutex_unlock");
exit(1); s = pthread_mutex_unlock(&mtx);
} if (s != 0) {
} perror("pthread_mutex_unlock");
pthread_exit((void *)1);
s = pthread_join(t1, NULL); }
if (s != 0) { sleep(1);
perror("pthread_create"); }
exit(1);
} return 0;
} }
25-03-03 8
 Condition Variable
●
Condition variable purpose:
.. to signal a change in state
●
Using a condition variable:
-
(i) one thread sends a notification to the condition variable,
-
(ii) another thread waits until
a notification is sent to the condition variable.
While waiting,.. sleeps No IPV
usage)
– the thread

Main use is that

It anoids
busy-waiting
by letting Threads
sleep white waiting

25-03-03 9
 Integrates with Mutex
●
We want to ensure that consumer(s) are thread safe.
– .. the processing of value to

Let
a occus in a miles

●
A condition variable works closely with a mutex:

We need to hold the mutex We'll wait until there is data available,..
the mutes while
while processing data.. but not hous
waiting
so we don't corrupt
the That way the producer
shared resource (or other consumers)
can do work while we sleep.

25-03-03 10
 pthread Condition Variables
●
Define the variable pass pointer
pthread_cond_t cond = PTHREAD_COND_INITIALIZER; hays to

●
Wait on a condition variable >
- it
- pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
– Internally, it will: ↓
●
.. Atomically release the mutes & writ for
condition
to les

released
●
Once signalled,.. wakes up a grabs the mutes.
– Why release mutex when waiting?
.. While we don't stop because
other
holding lock
a

Anrcs can't acques the

●
Lock-safe Sleep mutes to change the condition

cond is paired with a mutex so consumer can be sure that:

-– No items added between unlocking mutex and waiting for cond.
(important because a signal with no thread waiting is lost).
–
-
Once woken up, it again holds the mutex.
25-03-03 11
 pthread Condition Variables (cont)
●
Wake
- up one thread waiting on cond notify/ signa
--
to
pthread_cond_signal(pthread_cond_t *cond);
the waiting
– How many threads are waiting on cond? threads
1: It wakes it up one thread.
2+: One wakes up, no control over which one.
0: .. Signal is lost
doesn't count how many signal are
finding .

●
Wake up all threads waiting on cond
pthread_cond_broadcast(pthread_cond_t *cond);
-
– All threads wake up and try to grab mutex;
-
.. lock
the
they compete for

25-03-03 12
 pthread Condition Variables (cont)
●
Guideline on Signalling
signal() and broadcast() are similar; how to choose?
– If any of the waiting threads is sufficient to process the event:
.. use biwed-coud-signal I useful when
threads
●
It’s likely that all the threads do the same thing.
-
c

– If all of the waiting threads need to respond to an event:

.. use ptheed-cond Groadcast 1).
-

●
It’s likely each thread does something different
in response to the event; all need to happen

25-03-03 13
 Usage Pattern
Producer: Consumer: While (NU) - ? Why -

pthread_mutex_lock(&mutex); pthread_mutex_lock(&mutex); wapto

on

<do some work producing an item> while ( <no work to do> ) { oreuning
pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex); }

pthread_cond_signal(&cond); <do some work>

f unlocking pthread_mutex_unlock(&mutex);
after
ignalanyone care
thatonsume of

●
Details
– .. A condition variable must always use the same
mutes (
– Producer should signal after releasing mutex to avoid waking up a
consumer with cond only to wait for mutex (extra context switch)
– Some systems optimize with "wait morphing" to just move process
from one wait queue to another in the OS
25-03-03 14
 Producer-Consumer with Condition Variable
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

static int avail = 0;

int main() { static void *thread_func(void *arg) {

pthread_t t1; for (;;) {
pthread_create(&t1, NULL, thread_func, NULL); pthread_mutex_lock(&mtx);

for (;;) { avail++;

pthread_mutex_lock(&mtx); printf("Producer: %d.\n", avail);

// This while loop is new. pthread_mutex_unlock(&mtx);

while (avail == 0) {
pthread_cond_wait(&cond, &mtx); // This signal is new.
} pthread_cond_signal(&cond);
sleep(1);
while (avail > 0) { }
// Simulate "consume everything" }
printf("--> Consumer:%d.\n", avail);
avail--;
}

pthread_mutex_unlock(&mtx);
}

pthread_join(t1, NULL);
}

25-03-03 15
 Discussion of Code
●
Use of Condition Variables Discussion
– mutex still protects the shared variable avail.
– After producing an item, producer sends a signal to cond to
wake up a waiting thread, if any: pthread_cond_signal(&cond)
●
This notifies other thread there is something to consume.
– At each iteration, consumer checks if there is any available
item to consume (the new while loop).
●
If nothing's available (avail == 0), it sleeps:
pthread_cond_wait()
●
This releases the mutex before sleeping
– Consumer wakes up when signalled by the producer:
●
pthread_cond_wait() grabs mutex before returning.

25-03-03 16
 pthread_cond_wait() in loop?
●
Why put pthread_cond_wait() in a loop?
– Consumer only has work to do when: (avail != 0)
(avail != 0) is called the..
– Consumer only waits if there is no data to process.
For this, just if (avial == 0) seems fine.
– But, we must recheck the int main() {
predicate after we are signalled: for (;;) {
pthread_mutex_lock(&mtx);
●
We were waiting on the // This while loop is new.
mutex as well as cond, while (avail == 0) {
pthread_cond_wait(&cond, &mtx);
.. }

while (avail > 0) {

// Simulate "consume everything"
●
Therefore, no guarantee after }
avail--;

a wake-up that data is available.

pthread_mutex_unlock(&mtx);
}
}

25-03-03 17
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
static int avail = 0;
Producer-Consumer
int main() {
pthread_t t1;
with Condition Variable
void *res;
int s; with Error Checking
s = pthread_create(&t1, NULL, thread_func, NULL);
if (s != 0) {
perror("pthread_create");
exit(1);
}

for (;;) { static void *thread_func(void *arg) {

s = pthread_mutex_lock(&mtx); for (;;) {
if (s != 0) { int s = pthread_mutex_lock(&mtx);
perror("pthread_mutex_lock"); if (s != 0) {
exit(1); perror("pthread_mutex_lock");
} pthread_exit((void *)1);
}
// This while loop is new. avail++;
while (avail == 0) { printf("Producer: avail up to %d.\n", avail);
s = pthread_cond_wait(&cond, &mtx);
if (s != 0) { s = pthread_mutex_unlock(&mtx);
perror("pthread_mutex_lock"); if (s != 0) {
exit(1); perror("pthread_mutex_unlock");
} pthread_exit((void *)1);
} }

while (avail > 0) { // This signal is new.

/* This is simulating "consume everything available" */ s = pthread_cond_signal(&cond);
printf("--> Consumer: avail at %d.\n", avail); if (s != 0) {
avail--; perror("pthread_cond_signal");
} pthread_exit((void *)1);
}
s = pthread_mutex_unlock(&mtx); sleep(1);
if (s != 0) { }
perror("pthread_mutex_unlock");
exit(1); return 0;
} }
}
25-03-03
} 18
 Condition Variable Template for Consumer
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;

static pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int main() {
int s = pthread_mutex_lock(&mtx);

if (s != 0) {
perror("pthread_mutex_lock");
exit(1);
}

while (/* Check if there is nothing to consume */) {

/* Use while, not if, other threads might have woken
up first and changed the shared variable. */
pthread_cond_wait(&cond, &mtx);
}

// Do the necessary work with the shared variable, e.g., consume.

s = pthread_mutex_unlock(&mtx);
if (s != 0) {
perror("pthread_mutex_lock");
exit(1);
}
}
25-03-03 19
 Semaphores

25-03-03 20
 Semaphores
●
.. A semaphore is a clock with a count
– A lock (mutex) is either available or not available, i.e., binary.
– A semaphore is more flexible:
.. It indicates the availability as a count
,
i.e., how many are available.
●
Useful when availability is not binary but a count
-

e.g., how many items are available to consume?

– If the availability count is 0,
it means the semaphore is.. unavailable
-

– If the availability count is greater than 0,

- -

it means the semaphore is.. available

-

– Must initialize the semaphore with

an initial max availability count.

25-03-03 21
 pthread Semaphore Functions
●
Create & Initialize the semaphore
- sem_t sem;
~ sem_init(sem_t *sem, int pshared, unsigned int value);
– Sets current # available to value for sem. -
-

– pshared indicates if sem is for threads (0) or processes (1).

-

25-03-03 22
 pthread Semaphore Functions
●
Wait to "acquire" one of the semaphore's count
sem_wait(sem_t *sem);
– If count is 0, it blocks until count > 0.
-

– When count -
is > 0 it decrements count and returns.
– -
>
Does not guarantee mutual exclusion to a critical section:
.. It availability of
counts the the resource

●
Signal to count-up the semaphore:
sem_post(sem_t *sem);
– If synchronizing access a.. limited resource
then posting can be like.. releasing a resource

●
E.g., allow at most 50 students registered in a course.
– If synchronizing between different sections of code,
then it might indicate a new resource produced.
25-03-03 23
 ABCD: Semaphore
●
Which of these creates a semaphore which
behaves the same as a mutex?
a) sem_init(&sem, 0, 0);
X
b) sem_init(&sem, 0, 1);
c) sem_init(&sem, 0, 2);
d) sem_init(&mutex, 0, 10);

sem_init(sem_t *sem, int pshared, unsigned int value);

25-03-03 24
 Semaphore Use Ideas
●
Places to use a Semaphore
Can have a.. single section of code wait & then
–
post
to acquire and release the mutex.
– Can have different parts of the code use them, such as:

fE Produce: .. post when itsm is

● an
ready
●
Consumer: .. wait until itsm is
rady
an

doing ●
May still need a mutex to protect shared data.
This

25-03-03 25
 Read-Write Lock

25-03-03 26
 Read-Write Lock
●
Read-write lock
– Another synchronization primitive.
.. Allows rither unlimited readers or
– a
single
write
●
Multiple readers can all read at the same time!
-
●
Nobody else can access data while anyone writes.
-
●
Acquire lock for reading
-

pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
– Allows any thread(s) to grab rwlock for reading as long as
-
there is no thread that hold it for writing.
-
●
Acquire lock for writing
-

pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
-

– This allows only one thread to grab rwlock for writing.

-

25-03-03 27
 Dining Philosophers

25-03-03 28
 Dining Philosophers
●
Problem Description
– Philosophers sit at a round table.
– Philosophers alternate between eating and thinking.
– To eat, a philosopher needs two forks (at their left and right).
To think, no forks are needed.
– One fork between adjacent philosophers.
●
.. run fork is a
resources

shared by a adjaint philosopher

●
We can model this as
a synchronization problem:
– .. each thread is philospher
a

– A fork is a shared resource that

only one should access at a time
25-03-03 For more info: https://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf 29
 Try 1: Big lock!
●
Challenge
– come up with a solution that protects shared resources
correctly and does not deadlock.
●
Try 1: One big lock (not efficient)
– Idea:
.. use one mutes to guard all
forks & control access

– Correctly avoids deadlocks but

.. allows only one philosopher to ret
– Linux used to use this approach to
protect kernel resource during a syscall:
“the big kernel lock”

25-03-03 30
 Try 1: Lock each fork
●
Try 2: One lock per fork. &
●
Let’s create a bad “solution”:
– Have all threads grab their right fork and then their left fork.
-

– But if every philosopher grabs their right fork at the same time,
then.. no philosophers an grab their left forh
– The result:.. deadlock du to hold I wait &
circular
●
Recall: deadlock conditions discussed previously wait
– We can break any of these conditions to avoid a deadlock.
1) Hold-and-wait
2) Circular wait
3) Mutual exclusion
4) No preemption

25-03-03 31
 Possible Solutions
●
Solution 1:
.. Havephilospher forks in deff order
a a

– E.g., Most philosophers grab right fork then left fork. Have
have one philosopher grab left fork then right fork.
– .. This orvabs circular-wait condition from
●
Solution 2: curring
.. Try grabbing both locks at once
– Grab the left lock. Try the right lock. If you can't grab it,
..
give up the left lock & try again
– .. This breaks hold
I wait
condition
since no philosopher can hold a fork and wait.
– This does not prevent starvation
-

and could also lead to livelock.

-

25-03-03 32
 Dining Philosophers Implementation
#define NUMBER 5

static pthread_mutex_t mtx[NUMBER] = {PTHREAD_MUTEX_INITIALIZER};

int main() { static void *thread_func(void *arg) {

pthread_t t[NUMBER]; int left = (int)arg;
int right = ((int)arg + 1) % NUMBER;
for (int i = 0; i < NUMBER; ++i) { for (;;) {
pthread_create(&t[i], NULL, printf("Thread %d: thinking\n", (int)arg);
thread_func, i); sleep(5);
}
pthread_mutex_lock(&mtx[left]);
for (int i = 0; i < NUMBER; ++i) {
pthread_join(t[i], NULL); if (pthread_mutex_trylock(&mtx[right]) != 0) {
} pthread_mutex_unlock(&mtx[left]);
} continue;
}

printf("Thread %d: eating\n", (int)arg);

pthread_mutex_unlock(&mtx[left]);

pthread_mutex_unlock(&mtx[right]);
}

return 0;
}
25-03-03 33
 Bounded Buffer
(Circular Buffer)

25-03-03 34
 Bounded Buffer
●
Problem Description
– Multiple threads share a buffer.
– Producer threads place items into the buffer.
●
They must wait.. If unfor is full
– Consumers threads take items from the buffer.
They must wait.. If buffer is not
full/empty
●

●
Details
– Producers:
place items from index 0 to higher indices, one at a time.
– Consumers:
remove items from index 0 to higher indices, one at a time.
– When get to last element,.. wrap-around to indess O

25-03-03 35
 Solution
●
Possible solution:
.. Mutex + condition variable
– Mutex protects the data structure for all threads
– Condition variable signals consumer (and producer?)
– Inefficient because..
all threads need to compete
I huck
for
availability
.

25-03-03 36
#define SIZE 10
Semaphores:
static
static
char buf[SIZE] = {0};
int in = 0, out = 0; Elegant Solution
static sem_t filled_cnt;
static sem_t avail_cnt;
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;

int main() {
pthread_t t1;
sem_init(&filled_cnt, 0, 0);
sem_init(&avail_cnt, 0, SIZE);

pthread_create(&t1, NULL, thread_func, NULL);

static void *thread_func(void *arg) {
// Producer Code
for (;;) {
for (int i = 0;; i++) {
sleep(1);
sem_wait(&avail_cnt);
sem_wait(&filled_cnt);
pthread_mutex_lock(&mtx);
pthread_mutex_lock(&mtx);
// Produce
// Consume
buf[in] = i;
printf("Consumed: %d\n", buf[out]);
printf("Produced: %d in %d\n", buf[in], in);
out = (out + 1) % SIZE;
in = (in + 1) % SIZE;
pthread_mutex_unlock(&mtx);
pthread_mutex_unlock(&mtx);
sem_post(&avail_cnt);
sem_post(&filled_cnt);
}
}
return 0;
pthread_join(t1, NULL);
}
}
25-03-03 37
 Summary
●
Condition Variable
– One thread signals another for an event.

– Paired with a mutex for mutual exclusion.

●
Produce-Consumer Pattern
– Shared data structure storing waiting items.

●
Semaphore
– Synchronization with a count

●
Read-Write Lock
– Multiple readers allowed; only one writer.

●
Classing problems
– Dining Philosophers: worry about deadlock / livelock

– Bounded buffer: elegant semaphore solution.

25-03-03 38
 Summary
●
Condition Variable
– One thread signals another for an event.

– Paired with a mutex for mutual exclusion.

●
Produce-Consumer Pattern
– Shared data structure storing waiting items.

●
Semaphore
– Synchronization with a count

●
Read-Write Lock
– Multiple readers allowed; only one writer.

●
Classing problems
– Dining Philosophers: worry about deadlock / livelock

– Bounded buffer: elegant semaphore solution.

25-03-03 38
 Summary
●
Condition Variable
– One thread signals another for an event.

– Paired with a mutex for mutual exclusion.

●
Produce-Consumer Pattern
– Shared data structure storing waiting items.

●
Semaphore
– Synchronization with a count

●
Read-Write Lock
– Multiple readers allowed; only one writer.

●
Classing problems
– Dining Philosophers: worry about deadlock / livelock

– Bounded buffer: elegant semaphore solution.

25-03-03 38
 Summary
●
Condition Variable
– One thread signals another for an event.

– Paired with a mutex for mutual exclusion.

●
Produce-Consumer Pattern
– Shared data structure storing waiting items.

●
Semaphore
– Synchronization with a count

●
Read-Write Lock
– Multiple readers allowed; only one writer.

●
Classing problems
– Dining Philosophers: worry about deadlock / livelock

– Bounded buffer: elegant semaphore solution.

25-03-03 38