Synchronization:

Intro & Mutex

25-02-24 CMPT 201 Slides 8.1 © Dr. B. Fraser 1

 Synchronization:
Intro & Mutex

25-02-24 CMPT 201 Slides 8.1 © Dr. B. Fraser 1

 Topics

●
How can we prevent two threads form having a race case?
●
How can we code a mutex in C?
●
What’s important to get right about locks?

25-02-24 2
 Intro
●
Synchronization
.. Refers to coordinating the execution liff threads
among
– Careful synchronization avoids difficult to debug race cases.
– Race cases are hard because:
●
.. They don't always occursIsome very vari) that's
why
.. You must reason about multiple

Trade
●

not just single path’s correctness.

●
We'll learn synchronization primitives: &
– locks (mutex) not
one
– condition variables (next slide deck)
– semaphores (next slide deck)

25-02-24 3
 Details
●
Can find more info in OSTEP book
(more depth than we require)
– Chapter 28 Locks
https://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf
– Chapter 30 Condition Variables
https://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf
– Chapter 31 Semaphores
https://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf
– Chapter 32 Concurrency Bugs
https://pages.cs.wisc.edu/~remzi/OSTEP/threads-bugs.pdf

25-02-24 4
 Locks:
Mutexes

25-02-24 5
 Motivation
●
Recall race case from Threads notes (assume counter = 5):
Thread 1 Thread 2 Thread 1 Thread 2
int tmp1 = counter int tmp1 = counter
tmp1++ int tmp2 = counter
=6
counter = tmp1 tmp1++
int tmp2 = counter tmp2++
tmp2++ counter = tmp1
=7 counter = tmp2 counter = tmp2
=6
=6

●
What looks like one operation
.. can actually be number of sub operations
a
.

– We need to prevent this mix-up of sub-operations

from different threads.
#mutual
– Use a lock or a mutex: .. usion
25-02-24 6

that only thread at a time can accessa

A lock ensures one

shared resource
 Locks
●
Lock mechanisms consists of:
– .. Define the lock variable to create the lock
– .. lock() function that grabs a lock
– .. unlock () function that releases a lock
(he
Initializes
●
E.g.: pthread library's lock:
mutes type metes
– Define lock: -
>
-
pthread_mutex_t myLock = PTHREAD_MUTEX_INITIALIZER;
-

– Mutex -
lock function:

Y
int pthread_mutex_lock(pthread_mutex_t *mutex)
– -
Mutex unlock function:
int pthread_mutex_unlock(pthread_mutex_t *mutex)
Other languages (e.g., Java, Python, etc.)
have similar lock mechanisms.
25-02-24 7

upass in a
pointer
sour can
change the
actual one not a
copy .
 pthread Example
thread hold lock
●
Locks guarantee: .. only a
single can a

there is
static pthread_mutex_t data_mutex = PTHREAD_MUTEX_INITIALIZER;
>
-
uneures
only one

thread that cruses the

static int data[10]; data() at a
static void *thread1(void *arg) { Timo
static void *thread0(void *arg) { T0 locks
int count = 0;
mutex
pthread_mutex_lock(&data_mutex); T0h tries to pthread_mutex_lock(&data_mutex);

6
{ lock mutex T
Mute is locked
for (int i = 0; i < 10; i++) { so lock 1) blocks thread

unlocke
count += data[i]; T0 access
} data[] until mutes , is free
}
-mutes
pthread_mutex_unlock(&another_lock); {
printf("Sum is %d\n", count); for (int i = 0; i < 10; i++) {
pthread_exit(0); data[i] += 1;
}
} T0 unlocks mutex. } & data_mutes
This unblocks T0
&T1
pthread_mutex_unlock(&another_lock);
>

If threado1) is
using the mules printf("Done update!\n");
pthread_exit(0);
1 thread11) must wait }
25-02-24 8
 Operation of Lock
●
pthread_mutex_lock(&mutex) either:
a) .. If its fre , locks mutes & returns immediately
, or

b) .. blocks ,
then Its
once free it looks the mutes & returns
.

●
Mutual Exclusion
– Even if multiple threads call lock() at once,
.. only single thread an hold a lock
a :

all other threads wait

– We cannot control the order in which threads grab the lock.
-

It depends on the underlying lock mechanism.

-

●
Non-deterministic
– This behaviour is non-deterministic:
.. exhibits
-

different
behaviour every time it runs
.

– Opposed of deterministic behaviour.

25-02-24 9
 ABCD: Code with Data Race
int cnt = 0; This code suffers
static void *thread_func(void *arg) { a data race.
for (int i = 0; i < 10000000; i++)
cnt++;
pthread_exit(0); What is the cause
} of this data race?
int main(int argc, char *argv[]) { ruch thread has its own
pthread_t t1; stath i is a local
pthread_t t2; ,

variables So don't
pthread_create(&t1, NULL, thread_func, NULL);
they
pthread_create(&t2, NULL, thread_func, NULL); conflict but they share
the same globed variatr

pthread_join(t1, NULL); a) T2 may start before T1

pthread_join(t2, NULL);
b) T2 may end before T1
printf("%d\n", cnt);
V
c) T1 and T2 share cnt
exit(EXIT_SUCCESS); d) T1 and T2 share i
}

25-02-24 10
 Code with error checking
int cnt = 0;

static void *thread_func(void *arg) {

for (int i = 0; i < 10000000; i++)
cnt++;
pthread_exit(0);
}

int main(int argc, char *argv[]) {

pthread_t t1;
pthread_t t2;

if (pthread_create(&t1, NULL, thread_func, NULL) != 0)

perror("pthread_create");

if (pthread_create(&t2, NULL, thread_func, NULL) != 0)

perror("pthread_create");

if (pthread_join(t1, NULL) != 0)
This is the same code
perror("pthread_join"); as previous slide,
if (pthread_join(t2, NULL) != 0) but shows error
perror("pthread_join");
=>
checking on functions.
printf("%d\n", cnt);
You should do this!
exit(EXIT_SUCCESS); (Slides omit for brevity)
}
25-02-24 11
 Mutex Protected
int cnt = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
- ●
Protect the critical
static void *thread_func(void *arg) {
for (int i = 0; i < 10000000; i++) { section with a lock.
pthread_mutex_lock(&mutex);
-

cnt++;
●
A thread trying to
}
pthread_mutex_unlock(&mutex);
-
change cnt must do
pthread_exit(0); so with mutex
}
locked.
int main(int argc, char *argv[]) {
pthread_t t1;
●
man
pthread_t t2; pthread_mutex_lock
It has more context
pthread_create(&t1, NULL, thread_func, NULL); switch
pthread_create(&t2, NULL, thread_func, NULL);
>
-
-
overlay
●
Why not lock outside
pthread_join(t1, NULL); the loop?
pthread_join(t2, NULL); Then this no point in having

printf("%d\n", cnt);
2 Threads which are imp for
exit(EXIT_SUCCESS); parallelism
}
25-02-24 12
 Lock Usage

25-02-24 13
 Atomicity
It means an operation is indivisible it can't be interrupted or

Atomicity
,
● .

interleaved with other operations

– Atomic:
.. multiple operations run us if they a single operation
are

Cannot be interfered with by other sections with same lock.

-
– Mutex lock makes a section of code atomic.
-

Atomicity: all or nothing as it runs either

> True truff
–

-
all operations or no operations at all.
●
Serialization and interleaving
– Lock effectively Eserializes operations:
.. only onethread at time
a operations guided by a lock
can run

– Operations from different threads are interleaved in some order. -

We cannot control the order in which different threads run. Yos

Schedules
cluide
25-02-24 This 14

serialization refers to
executing operations
in sequential
the other
order ,
one after
 Protecting shared variables
●
Can have a data race when threads share a variable
– e.g. Accessing same..
- global variatel cnt++
- – e.g. Accessing same.. memory via
pSharedBuffer[i] = 52;
pointer

●
Solve data race with a lock
-
– Controls and serializes access shared variable
●
Where in the code?
– Data race may be.. from onepice of code
e.g.: One function called by multiple threads
tracking next free block to allocate.
– May be in.. differentsections of code
Each using the same lock
thread fills buffer, one thread empties buffer.

25-02-24 15
 Multiple locks
●
Can have multiple locks..
-
if they are protecting independent shared variables
– e.g.: data_samples_mutex, printer_mutex
– Each code section / thread locks the mutex(es)
it needs to lock be safe.
– Reducing *lock contention* is important for performance.

Reducing Lock Contention

• If one lock is used for everything, threads wait longer even if they are working on independent
data.
• Using separate locks allows better parallel execution.

25-02-24 16
 Non-Blocking Lock
●
Options to allow us to control blocking behaviour:
– pthread_mutex_trylock()

&
.. res immediately If cabe to
– pthread_mutex_timedlock()
waits a maximum amount of time before returning if unable to
lock.

If a thread cannot acquire a lock immediately, it should continue doing other tasks instead of waiting.

25-02-24 17
 Critical Section (CS)
and
Thread Safety

25-02-24 18
 Critical Section (CS)
part of
the program where shared
-
●
Critical Section: resources are

accessed or
A critical section is a piece of code that
.. accesses shared variable
.
a modifie
(or more generally, a shared resource) and
.. must not be concurrently executed by than
more thread
one

-- From OSTEP

●
Rephrased:
– If a thread is executing the CS,
=
no other threads should execute the CS.

25-02-24 19
 Critical Section (CS)
●
An ideal solution for CS problem must satisfy 3 requirements:
– Mutual exclusion >
- acheiver through Locks

.. only one thread should be allowed to run in the IS

– Progress
.. A thread

I
should
centually complete (ix make
progress)
– Bounded waiting
.. An upper bound must exist for the amount
of time a

thread waits to Enter the IS .

i.e., a thread should only be blocked for a finite amount of time.

-ar vation
prevents
Definition: Progress means that if no thread is executing in the critical section, and there are threads that
want to enter the critical section, one of the waiting threads must be allowed to proceed.

25-02-24 20
 Thread safety & Reentrant
●
Thread safe function
.. a function that multiple threads can ren
racily
It either:
a) does not access shared resources or using
-mutes
b) provides proper protection for CS that access shared
resources.
●
Reentrant vs nonreentrant functions (related concept)
Y – A reentrant function is a function that
It can
.. broduces the correct output ruen
be
when called again
safely
interupple while executing
middle
in the

of it execution
– Must work with different threads (thread safe), and also
& calledagain .. the sarme thread (such as a signal hander)
lufore previous
executions
and – i.e., a function called by main() might also be called by a
complete
signal handler on the same thread.
.

25-02-24 21

All rentrant functions are thread safe ,

but not all
rentrant
thread-safe functions are
 a) Thread safe: YES Reentrant YES
ABCD: Thread safety (1) b) Thread safe: YES Reentrant NO
c) Thread safe: NO Reentrant YES

●
How thread safe is this function? X
d) Thread safe: NO Reentrant NO

int tmp = 0;

int swap(int *pA, int *pB) {

tmp = *pA;
*pA = *pB;
*pB = tmp;
}

b
Not thread safe
: can
zmp
Call shared by
with
shared variabl our by rack
multiple
Therefore not Reentrant threads

25-02-24 22
 a) Thread safe: YES Reentrant YES
ABCD: Thread safety (2) -
b) Thread safe: YES Reentrant NO
c) Thread safe: NO Reentrant YES
d) Thread safe: NO Reentrant NO
●
How thread safe is this function?
int tmp = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

int swap(int *pA, int *pB) {

pthread_mutex_lock(&mutex);
tmp = *pA;
*pA = *pB;
*pB = tmp;
pthread_mutex_unlock(&mutex);
}

To thrud safe , multiple thread will block

Non-Reentrant : If threads gets intrupted by a signal
while
holding mutes this signal hand will get blocked
due to mutes
25-02-24 23
 -
a) Thread safe: YES Reentrant YES
ABCD: Thread safety (2) b) Thread safe: YES Reentrant NO
c) Thread safe: NO Reentrant YES
d) Thread safe: NO Reentrant NO
●
How thread safe is this function?

int swap(int *pA, int *pB) { -Local variable

int tmp = 0; stack
in
deff
tmp = *pA;
*pA = *pB;
*pB = tmp;

Thered safe :
no shard date

Es Rentrant : no said or shared data

25-02-24 24
 Making Functions Reentrant
●
What makes a function non-reentrant?
A function might work with some data, like a buffer:
– use a shared global buffer
– use a shared thread-local buffer
●
Solutions:
– allocate its own local variable buffer on the stack
-
– dynamically allocate and free new buffer in the heap

have calling code allocate space and pass it in

anation argument
–
-i
●
Caller Allocates Technique
– Many functions make calling code pass in the buffer.
e.g., write() =
takes buffer
– .. Any space
returned to caller
es an argument
calls is
or maintained across
function allocated
by aller

25-02-24 25
 Deadlock and Livelock

25-02-24 26
 Deadlock
●
Deadlock
a condition where a set of threads
.. Much hold a resource Iwait to acquire a resourc

held by another thread

– The threads get stuck and make no progress.

●
E.g.:
– Create mutex locks A & B
-

-– Thread 1: locks A
-– Thread 2: locks B, then blocks trying to lock A
-– Thread 1: blocks trying to lock B

25-02-24 27
 Deadlock Activity
●
[15 min]
Write a program that creates two threads and two locks:
Thread #0: Thread #1: Useful Thread Code
Lock A Lock B #include <pthread.h>
static void *func(void *arg) {
Print Print pthread_exit(0);
Lock B Lock A }
Print Print int main(int argc, char *argv[]) {
Unlock B Unlock A pthread_t t1;
Unlock A Unlock B
pthread_create(&t1, NULL, func, NULL);
Print Print
pthread_join(t1, NULL);
}
●
Investigation
– Does it always finish (run multiple times)? no deadlock ocurs

– Does it always not finish (run multiple times)? finish sometimes

no can

– What happens if both threads lock A and B in the same order?

G
doesn'tr ur cause a deadlock
25-02-24 Demo: deadlock.c 28

Thead O Tread 1
Lock A LockA
Loch B Lock B
#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lockA = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_t lockB = PTHREAD_MUTEX_INITIALIZER;

void *thread0_func(void *arg) {

pthread_mutex_lock(&lockA); // Lock A Deadlock occurs when both threads are waiting for resources held by the other.
printf("Thread 0: Locked A\n"); For example:
pthread_mutex_lock(&lockB); // Lock B •Thread 0 locks A and then waits to lock B.
printf("Thread 0: Locked B\n"); •Thread 1 locks B and then waits to lock A.
pthread_mutex_unlock(&lockB); // Unlock B This situation results in a deadlock because each thread is holding one lock and
pthread_mutex_unlock(&lockA); // Unlock A waiting for the other, preventing both from proceeding.
printf("Thread 0: Finished\n");
return NULL;
}
• hread 0 locks lockA and then tries to lock lockB.
void *thread1_func(void *arg) { • Thread 1 locks lockB and then tries to lock lockA.
pthread_mutex_lock(&lockB); // Lock B Since Thread 0 has lockA and is waiting for lockB, and Thread 1 has lockB and is waiting for lockA,
both threads are stuck waiting for each other to release the lock they need. Neither thread can proceed,
printf("Thread 1: Locked B\n"); and they will both be blocked indefinitely.
pthread_mutex_lock(&lockA); // Lock A
printf("Thread 1: Locked A\n");
pthread_mutex_unlock(&lockA); // Unlock A
pthread_mutex_unlock(&lockB); // Unlock B
printf("Thread 1: Finished\n");
Non-deadlock scenario (lucky execution):
return NULL;
} 1 Thread 0 locks lockA.
2 Before Thread 1 locks lockB, Thread 0 proceeds to also lock lockB.
3 Thread 0 completes its critical section, unlocks both lockB and lockA.
int main() { 4 Then Thread 1 can proceed and lock both locks successfully.

pthread_t t0, t1; -

S
have only Thread
one O with one
Let's say we
if (pthread_create(&t0, NULL, thread0_func, NULL) != 0) A Thread O receive
perror("pthread_create"); lock t - While holding ,
a
signal
if (pthread_create(&t1, NULL, thread1_func, NULL) != 0)
signal hander tries to lock mute, A
perror("pthread_create");
&
of the

if (pthread_join(t0, NULL) != 0) Then signar handers starts running inside

the
& Thread O
perror("pthread_join"); Thrado , it pauses it jumps to signal
if (pthread_join(t1, NULL) != 0) handle
perror("pthread_join");
Inside the Signal hander we
again My to lock At

return 0;
} So It
locked causes a
ButIt already is

deadlock
 Necessary Conditions for Deadlock
●
4 conditions are necessary for deadlock:
These do not guarantee deadlock:
deadlock also depends on timing of thread execution.
1) Hold and wait:
.. Threads are already holding resources but also are

writing for additional resources being held by other threads

2) .. Fircular wait
there exists a set {T0, T1, ..., Tn-1} of threads such that
T0 is waiting for a resource that is held by T1,
T1 is waiting for T2, ..., Tn–1 is waiting for T0.
3) Mutual exclusion: A mutes allows only
.. Threads hold rusources exclusively - one thread to hold at a

time
4) No preemption:
resource released only voluntarily by the thread holding it
25-02-24
they
I
can't s
forcibly taken
away 29
&
If Thread 0 holds lock A, no other thread can forcibly unlock lock A; only Thread 0 can unlock it.
 Apply Deadlock Conditions
●
E.g.: Thread 1 Thread 2
Lock A Lock B
Print Print
Lock B Lock A
Print Print
Unlock B Unlock A
Unlock A Unlock B
Print Print another
lock I wait for
hold one
Threads
●
4 Conditions to Check
– Hold and wait? -- holding B
C o waits For A while All 4 conditions hold.
Y – Circular wait? -I waits For B while
holding Therefore, it’s
A
we curo
Lock & B POSSIBLE to have
change – Mutual Exclusion? ~
are
mutesses
deadlock.
(non-sharrable
– No preemption? -

-
> released
Locks can only be voluntarily
.

●
Deadlock Prevention
– Break one of these for conditions to prevent deadlocks.
25-02-24 30
 Preventing Deadlocks
●
Technique 1:.. Grab all locks at once , atomically
– .. Breaks hold I wait condition
you grab all the locks together or no locks at all
static pthread_mutex_t mutex0 = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t another_lock = PTHREAD_MUTEX_INITIALIZER;
both > so made it atomi
lock
-

static void *thread0(void *arg) { - A static void *thread1(void *arg) {

pthread_mutex_lock(&another_lock); B pthread_mutex_lock(&another_lock);
meetxx
{ {
pthread_mutex_lock(&mutex0); pthread_mutex_lock(&mutex1);
printf("thread0: mutex0\n"); printf("thread1: mutex1\n");
pthread_mutex_lock(&mutex1); pthread_mutex_lock(&mutex0);
} }
pthread_mutex_unlock(&another_lock); pthread_mutex_unlock(&another_lock);

printf("thread0: mutex1\n"); printf("thread1: mutex0\n");

pthread_mutex_unlock(&mutex1); pthread_mutex_unlock(&mutex0);
pthread_mutex_unlock(&mutex0); pthread_mutex_unlock(&mutex1);
pthread_exit(0); pthread_exit(0);
} }

25-02-24 31
 Preventing Deadlocks
Technique 2:.. Acquirs
●
locks in same order

– Acquiring locks in the same global order for all threads:

.. ↓ reaks the circular wait condition
as all threads try to grab locks in the exact same order.

static pthread_mutex_t mutex0 = PTHREAD_MUTEX_INITIALIZER;

static pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;

static void *thread0(void *arg) { sams static void *thread1(void *arg) {

pthread_mutex_lock(&mutex0);- lock
pthread_mutex_lock(&mutex0);
printf("thread0: mutex0\n"); no
printf("thread1: mutex0\n");
circular
pthread_mutex_lock(&mutex1); pthread_mutex_lock(&mutex1);
printf("thread0: mutex1\n"); printf("thread1: mutex1\n");

pthread_mutex_unlock(&mutex1); pthread_mutex_unlock(&mutex1);
pthread_mutex_unlock(&mutex0); pthread_mutex_unlock(&mutex0);
pthread_exit(0); pthread_exit(0);
} }

25-02-24 32
 Livelock
●
Livelock:
where a set of threads each execute instructions actively,
but.. they still not make any progress
●
E.g.: Threads T0 and T1
Each attempts to acquire two resources R0 and R1
while (true) while (true)
Acquire R0 Acquire R1
if R1 is free, then if R0 is free, then
Acquire R1 Acquire R0
do work do work
Free R1, R0 Free R0, R1
return return
else else
Free R0 Free R1

– Problem: T0 and T1 run concurrently:

.. each locking first resource then trying to lock second
– Each frees first resource, and then tries again forever.
25-02-24 33
• T0 grabs R0, checks R1, and if R1 is not free, it releases R0 and retries.
• T1 grabs R1, checks R0, and if R0 is not free, it releases R1 and retries.

What happens in livelock:

• Both threads are "polite":

They keep releasing and retrying but constantly interfere with each other.
Example livelock sequence:

1 T0 acquires R0, sees R1 busy → releases R0.

2 T1 acquires R1, sees R0 busy → releases R1.
3 Repeat forever...
 Livelock vs Deadlock
while (true) while (true)
Acquire R0 Acquire R1
if R1 is free, then if R0 is free, then
Acquire R1 Acquire R0
do work do work
Free R1, R0 Free R0, R1
return return
else else
Free R0 Free R1

●
Livelock:
Thread 0 and Thread 1 actively execute code
but do not make any progress.
●
Deadlock vs Livelock
– Both deadlocks and livelocks do not make any progress.
In a livelock scenario, threads do still execute.
– In a deadlock scenario,
.. threads are stuck I do not Meet anything
25-02-24 actively 34
 ABCD: Identify the problem
●
What synchronization problem is present in this code with
two threads (left and right), where M0 and M1 are mutexes.
global int cnt = 0;
>
- Breaks
while (true): while (true): ircular
lock M0 lock M0 wait
So can't
if cnt % 2 == 1 then: if cnt % 2 == 0 then:
lock M1 lock M1 be deadlock
cnt++ cnt++
unlock M1 unlock M1

unlock M0 unlock M0

X
a) Race case >
- mute , prevent vau cases

have lock I cuse

b) Non-reentrant > because they signal cas
!
- a

deadlock
↑
c) Livelock > No continuous Vetrying
-

d) Deadlock
X

25-02-24 35
 Summary
●
Mutex
– Used for Mutual Exclusion from a critical section.

– Guarantees only one thread can hold the lock

●
Critical Section
– Area of the code which accesses a shared variable that
must not be concurrently accessed from another thread.
●
Thread safe: Correctly runs with multiple threads.
●
Reentrant: Correctly runs when called again while running (same thread?)
●
Deadlock: Two threads blocking each other. Necessary conditions:
– Hold and wait

– Circular wait
– Mutual exclusion
– No preemption
25-02-24 36