Synchronization in Multithreading
CS 105
Spring 2024
Lecture 22: Synchronization
Review: Alternate View of a Process
•
Process = thread + other state
Thread context:
Data
registers
Stack pointer (rsp)
Condition codes
Program counter (rip)
Other data
rsp
Thread (main thread)
Kernel context:
VM structures
File table
brk pointer
Stack
0
brk
Review: Multi-threading
•
Multiple threads can be associated with a process
•
Each thread has its own logical control flow
•
Each thread has its own stack for local variables
•
Each thread has its own thread id (TID)
•
Each thread shares the same code, data, and kernel context
Thread 1 (main thread)
Shared data
Thread 2 (peer thread)
Thread 1 context:
Data
registers
Stack pointer
Condition codes
Program counter
rsp
Stack 1
Thread
2
context:
Data
registers
Stack pointer
Condition codes
Program counter
rsp
Stack 2
Kernel context:
VM structures
File table
brk pointer
0
brk
Review: Locks
•
A
l
o
c
k
(
a
k
a
a
m
u
t
e
x
)
i
s
a
s
y
n
c
h
r
o
n
i
z
a
t
i
o
n
p
r
i
m
i
t
i
v
e
t
h
a
t
p
r
o
v
i
d
e
s
m
u
t
u
a
l
e
x
c
l
u
s
i
o
n
.
W
h
e
n
o
n
e
t
h
r
e
a
d
h
o
l
d
s
a
l
o
c
k
,
n
o
o
t
h
e
r
t
h
r
e
a
d
c
a
n
h
o
l
d
i
t
.
•
a lock can be in one of two states: locked or unlocked
•
a lock is initially unlocked
•
function acquire(&lock) waits until the lock is unlocked, then
atomically sets it to locked
•
function release(&lock) sets the lock to unlocked
Review: use a lock
•
You and your roommate share a refrigerator. Being good
roommates, you both try to make sure that the refrigerator
is always stocked with milk.
A
l
g
o
r
i
t
h
m
6
:
acquire(&lock)
if (milk == 0) {// no milk
milk++;
// buy milk
}
release(&lock)
Correct!
Exercise : Locks
•
TODO: Modify this example
to guarantee correctness
/* Global shared variable */
volatile
long
cnt
= 0;
/* Counter */
int
main
(
int
argc
,
char
**
argv
)
{long
niters
;
pthread_t
tid1
,
tid2
;
niters = atoi(argv[1]);
Pthread_create(&tid1,
NULL
,
thread, &niters);
Pthread_create(&tid2,
NULL
,
thread, &niters);
Pthread_join(tid1,
NULL
);
Pthread_join(tid2,
NULL
);
/* Check result */
if
(cnt != (2 * niters))
printf(
"BOOM! cnt=%ld\n"
, cnt);
else
printf(
"OK cnt=%ld\n"
, cnt);
exit(0);
}
/* Thread routine */
void
*
thread
(
void
*
vargp
)
{long
i
,
niters
=
*((
long
*)vargp);
for
(i = 0; i < niters; i++){cnt++;
}
return
NULL
;
}
Problems with Locks
1.
Locks are slow
•
threads that fail to acquire a lock on the first attempt must "spin",
which wastes CPU cycles
•
threads get scheduled and de-scheduled while the lock is still
locked
2.
Using locks correctly is hard
•
hard to ensure all race conditions are eliminated
•
easy to introduce synchronization bugs (deadlock, livelock)
Blocking Lock (aka mutex)
•
Initial state of lock is 0 ("available")•
acquire(&lock)
•
b
l
o
c
k
(
s
u
s
p
e
n
d
t
h
r
e
a
d
)
u
n
t
i
l
v
a
l
u
e
n
>
0
•
when n > 0, decrement n by one
•
release(&lock)
•
increment value n by 1
•
r
e
s
u
m
e
a
t
h
r
e
a
d
w
a
i
t
i
n
g
o
n
s
(
i
f
a
n
y
)
acquire(&lock){ while(lock->s == 1){;
}
lock->s == 0
}
release(&lock){lock->s == 0
}
Example: Bounded Buffers
finite capacity (e.g. 20 loaves)
implemented as a queue
Threads A:
produce
loaves of bread and put
them in the queue
Threads B:
consume
loaves by taking them off
the queue
Example: Bounded Buffers
Threads A:
produce
loaves of bread and put
them in the queue
Threads B:
consume
loaves by taking them off
the queue
Separation of concerns:
1.
How do you implement a bounded buffer?
2.
How do you synchronize concurrent access to a
bounded buffer?
finite capacity (e.g. 20 loaves)
implemented as a queue
3
typedef struct {int* b; // ptr to buffer containing the queue
int n;
//
length of array (max # slots)
int count; // number of elements in array
int
front
;
//
index of first element,
0
<=
front
<
n
int rear; // (index of last elem)+1 % n, 0 <= rear < n
} bbuf_t
Example: Bounded Buffers
0 1 2 3 4 5 (n = 6)
2
4
1
Values wrap around!!
b
2
Exercise 1: What can go wrong?
typedef struct {int* b;
int n;
int count;
int
front
;
int rear;
} bbuf_t
Example: Bounded Buffers
3
4
1
b
2
pthread_mutex_t lock;
acquire(&(ptr->lock))
acquire(&(ptr->lock))
init(&(ptr->lock));
release(&(ptr->lock))
release(&(ptr->lock))
0 1 2 3 4 5 (n = 6)
while(ptr->count==ptr->n){release(&lock)
acquire(&lock)
}
while(ptr->count==0){release(&lock)
acquire(&lock)
}
Condition Variables
•
A condition variable cv is a stateless synchronization
primitive that is used in combination with locks (mutexes)
•
condition variables allow threads to efficiently wait for a change to
the shared state protected by the lock
•
a condition variable is comprised of a waitlist
•
Interface:
•
w
a
i
t
(
C
V
*
c
v
,
L
o
c
k
*
l
o
c
k
)
:
A
t
o
m
i
c
a
l
l
y
r
e
l
e
a
s
e
s
t
h
e
l
o
c
k
,
s
u
s
p
e
n
d
s
e
x
e
c
u
t
i
o
n
o
f
t
h
e
c
a
l
l
i
n
g
t
h
r
e
a
d
,
a
n
d
p
l
a
c
e
s
t
h
a
t
t
h
r
e
a
d
o
n
c
v
'
s
w
a
i
t
l
i
s
t
;
a
f
t
e
r
t
h
e
t
h
r
e
a
d
i
s
a
w
o
k
e
n
,
i
t
r
e
-
a
c
q
u
i
r
e
s
t
h
e
l
o
c
k
b
e
f
o
r
e
w
a
i
t
r
e
t
u
r
n
s
•
s
i
g
n
a
l
(
C
V
*
c
v
)
:
t
a
k
e
s
o
n
e
t
h
r
e
a
d
o
f
f
o
f
c
v
'
s
w
a
i
t
l
i
s
t
a
n
d
m
a
r
k
s
i
t
a
s
e
l
i
g
i
b
l
e
t
o
r
u
n
.
(
N
o
-
o
p
i
f
w
a
i
t
l
i
s
t
i
s
e
m
p
t
y
.
)
typedef struct {int* b;
int n;
int count;
int
front
;
int rear;
} bbuf_t
Example: Bounded Buffers
3
4
1
b
2
pthread_mutex_t lock;
init(&(ptr->lock));
release(&(ptr->lock))
release(&(ptr->lock))
0 1 2 3 4 5 (n = 6)
if(ptr->count == 0)
wait(&bread_added)
signal(&(ptr->bread_bought))
if(ptr->count == ptr->n)
wait(&bread_bought)
signal(&(ptr->bread_added))
CV bread_bought;
init(&(ptr->bread_bought));
while(ptr->count == ptr->n)
wait(&(ptr->bread_bought))
while(ptr->count == 0)
wait(&(ptr->bread_added))
CV bread_added;
init(&(ptr->bread_added));
acquire(&(ptr->lock))
acquire(&(ptr->lock))
Using Condition Variables
1.
Declare a lock. Each shared value needs a lock to
enforce mutually exclusive access to the shared value.
2.
Add code to acquire and release the lock. All code
access the shared value must hold the objects lock.
3.
Identify each place something could go wrong if the
next line is executed and declare a condition variable
that corresponds to when it is safe to proceed with the
function. Add a wait for that condition to ensure the
critical line is only executed under the right conditions.
4.
Add a signal when the condition becomes true.
5.
Add loops are your waits. Threads might not be
scheduled immediately after they are eligible to run.
Even if a condition was true when signal was called, it
might not be true when a thread resumes execution.
Exercise: Synchronization Barrier
•
With data parallel programming,
a computation proceeds in
parallel, with each thread
operating on a different section
of the data. Once all threads
have completed, they can
safely use each others results.
/* Thread routine */
void
*
thread
(
void
*
args
)
{parallel_computation(args)
done_count++;
use_results();
}
int done_count = 0;
Lock lock;
acquire(&lock);
release(&lock);
CV all_done;
if(done_count < n){wait(&all_done, &lock);
}
else {for(int i=0;i<n;i++)
signal(&all_done);
}
/* Thread routine */
void
*
thread
(
void
*
args
)
{parallel_computation(args)
done_count++;
use_results();
}
What can go wrong?
Condition Variables
•
A condition variable cv is a stateless synchronization
primitive that is used in combination with locks (mutexes)
•
condition variables allow threads to efficiently wait for a change to
the shared state protected by the lock
•
a condition variable is comprised of a waitlist
•
Interface:
•
w
a
i
t
(
C
V
*
c
v
,
L
o
c
k
*
l
o
c
k
)
:
A
t
o
m
i
c
a
l
l
y
r
e
l
e
a
s
e
s
t
h
e
l
o
c
k
,
s
u
s
p
e
n
d
s
e
x
e
c
u
t
i
o
n
o
f
t
h
e
c
a
l
l
i
n
g
t
h
r
e
a
d
,
a
n
d
p
l
a
c
e
s
t
h
a
t
t
h
r
e
a
d
o
n
c
v
'
s
w
a
i
t
l
i
s
t
;
a
f
t
e
r
t
h
e
t
h
r
e
a
d
i
s
a
w
o
k
e
n
,
i
t
r
e
-
a
c
q
u
i
r
e
s
t
h
e
l
o
c
k
b
e
f
o
r
e
w
a
i
t
r
e
t
u
r
n
s
•
s
i
g
n
a
l
(
C
V
*
c
v
)
:
t
a
k
e
s
o
n
e
t
h
r
e
a
d
o
f
f
o
f
c
v
'
s
w
a
i
t
l
i
s
t
a
n
d
m
a
r
k
s
i
t
a
s
e
l
i
g
i
b
l
e
t
o
r
u
n
.
(
N
o
-
o
p
i
f
w
a
i
t
l
i
s
t
i
s
e
m
p
t
y
.
)
•
b
r
o
a
d
c
a
s
t
(
C
V
*
c
v
)
:
t
a
k
e
s
a
l
l
t
h
r
e
a
d
s
o
f
f
c
v
'
s
w
a
i
t
l
i
s
t
a
n
d
m
a
r
k
s
t
h
e
m
a
s
e
l
i
g
i
b
l
e
t
o
r
u
n
.
(
N
o
-
o
p
i
f
w
a
i
t
l
i
s
t
i
s
e
m
p
t
y
.
)
Exercise: Readers/Writers
•
Consider a collection of concurrent threads that have access to a shared
object
•
Some threads are readers, some threads are writers
•
a unlimited number of readers can access the object at same time
•
a writer must have exclusive access to the object
int num_readers = 0;
int num_writers = 0;
Lock lock;
CV readable;
CV writeable;
int num_readers = 0;
int num_writers = 0;
int reader(void *shared){num_readers++;
int x = read(shared);
num_readers--;
return x
}
void writer(void *shared, int val){num_writers=1;
write(shared, val);
num_writers=0;
}
acquire(&lock);
release(&lock);
acquire(&lock);
release(&lock);
while(num_writers > 0)
wait(readable, &lock);
if(num_readers == 0)
signal(writeable);
acquire(&lock);
release(&lock);
while(num_readers > 0)
wait(writeable, &lock);
signal(writeable);
broadcast(readable);
void writer(void *shared, int val){num_writers=1;
write(shared, val);
num_writers=0;
}
int reader(void *shared){num_readers++;
int x = read(shared);
num_readers--;
return x
}
Programming with CVs
C
•
Initialization:
pthread_mutex_t lock =
PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cv =
PTHREAD_COND_INITIALIZER;
•
Lock acquire/release:
pthread_mutex_lock(&lock);
pthread_mutex_unlock(&lock);
•
CV operations:
pthread_cond_wait(&cv, &lock);
pthread_cond_signal(&cv);
pthread_cond_broadcast(&cv);
Python
•
Initialization:
lock = Lock()
cv = Condition(lock)
•
Lock acquire/release:
lock.acquire()
lock.release()
•
V
cv.wait()
cv.notify()
cv.notify_all()
Concepts of synchronization, multithreading, locks, and thread routines in the context of process management. Understand the importance of mutual exclusion and learn techniques to ensure correct concurrent operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lecture 22: Synchronization CS 105 Spring 2024
Review: Alternate View of a Process Process = thread + other state Thread (main thread) Other data brk Heap Stack Data rsp Code Thread context: Data registers Stack pointer (rsp) Condition codes Program counter (rip) 0 Kernel context: VM structures File table brk pointer
Review: Multi-threading Multiple threads can be associated with a process Each thread has its own logical control flow Each thread has its own stack for local variables Each thread has its own thread id (TID) Each thread shares the same code, data, and kernel context Thread 1 (main thread) Thread 2 (peer thread) Shared data brk Heap Stack 1 Stack 2 Data rsp rsp Code Thread 1 context: Data registers Stack pointer Condition codes Program counter Thread 2 context: Data registers Stack pointer Condition codes Program counter 0 Kernel context: VM structures File table brk pointer
Review: Locks A lock (aka a mutex) is a synchronization primitive that provides mutual exclusion. When one thread holds a lock, no other thread can hold it. a lock can be in one of two states: locked or unlocked a lock is initially unlocked function acquire(&lock) waits until the lock is unlocked, then atomically sets it to locked function release(&lock) sets the lock to unlocked
Review: use a lock You and your roommate share a refrigerator. Being good roommates, you both try to make sure that the refrigerator is always stocked with milk. Algorithm 6: acquire(&lock) if (milk == 0) { milk++; } release(&lock) // no milk // buy milk Correct!
Exercise : Locks /* Thread routine */ void *thread(void *vargp) { long i, niters = *((long *)vargp); for (i = 0; i < niters; i++){ cnt++; } /* Global shared variable */ volatile long cnt = 0; /* Counter */ int main(int argc, char **argv) { long niters; pthread_t tid1, tid2; niters = atoi(argv[1]); Pthread_create(&tid1, NULL, thread, &niters); Pthread_create(&tid2, NULL, thread, &niters); Pthread_join(tid1, NULL); Pthread_join(tid2, NULL); return NULL; } TODO: Modify this example to guarantee correctness /* Check result */ if (cnt != (2 * niters)) printf("BOOM! cnt=%ld\n", cnt); else printf("OK cnt=%ld\n", cnt); exit(0); }
Problems with Locks 1. Locks are slow threads that fail to acquire a lock on the first attempt must "spin", which wastes CPU cycles threads get scheduled and de-scheduled while the lock is still locked 2. Using locks correctly is hard hard to ensure all race conditions are eliminated easy to introduce synchronization bugs (deadlock, livelock)
Blocking Lock (aka mutex) Initial state of lock is 0 ("available") acquire(&lock) block (suspend thread) until value n > 0 when n > 0, decrement n by one acquire(&lock){ while(lock->s == 1){ ; } lock->s == 0 } release(&lock) increment value n by 1 resume a thread waiting on s (if any) release(&lock){ lock->s == 0 }
Example: Bounded Buffers finite capacity (e.g. 20 loaves) implemented as a queue Threads B: consume loaves by taking them off the queue Threads A: produce loaves of bread and put them in the queue
Example: Bounded Buffers finite capacity (e.g. 20 loaves) implemented as a queue Separation of concerns: 1. How do you implement a bounded buffer? 2. How do you synchronize concurrent access to a bounded buffer? Threads B: consume loaves by taking them off the queue Threads A: produce loaves of bread and put them in the queue
Example: Bounded Buffers 0 1 2 3 4 5 (n = 6) 2 4 b 2 3 1 Values wrap around!! rear front typedef struct { int* b; // ptr to buffer containing the queue int n; // length of array (max # slots) int count; // number of elements in array int front; // index of first element, 0<= front < n int rear; // (index of last elem)+1 % n, 0 <= rear < n } bbuf_t void put(bbuf_t* ptr, int val){ ptr->b[ptr->rear]= val; ptr->rear= ((ptr->rear)+1)%(ptr->n); ptr->count++; } int get(bbuf_t* ptr){ int val= ptr->b[ptr->front]; ptr->front= ((ptr->front)+1)%(ptr->n); ptr->count--; return val; } Exercise 1: What can go wrong? void init(bbuf_t* ptr, int n){ ptr->b = malloc(n*sizeof(int)); ptr->n = n; ptr->count = 0; ptr->front = 0; ptr->rear = 0; }
Example: Bounded Buffers 0 1 2 3 4 5 (n = 6) void put(bbuf_t* ptr, int val){ acquire(&(ptr->lock)) while(ptr->count==ptr->n){ release(&lock) acquire(&lock) } 2 b 3 4 1 typedef struct { int* b; int n; int count; int front; int rear; pthread_mutex_t lock; front rear ptr->b[ptr->rear]= val; ptr->rear= ((ptr->rear)+1)%(ptr->n); ptr->count++; release(&(ptr->lock)) } } bbuf_t void init(bbuf_t* ptr, int n){ ptr->b = malloc(n*sizeof(int)); ptr->n = n; ptr->count = 0; ptr->front = 0; ptr->rear = 0; init(&(ptr->lock)); int get(bbuf_t* ptr){ acquire(&(ptr->lock)) while(ptr->count==0){ release(&lock) acquire(&lock) } int val= ptr->b[ptr->front]; ptr->front= ((ptr->front)+1)%(ptr->n); ptr->count--; release(&(ptr->lock)) } return val;
Condition Variables A condition variable cv is a stateless synchronization primitive that is used in combination with locks (mutexes) condition variables allow threads to efficiently wait for a change to the shared state protected by the lock a condition variable is comprised of a waitlist Interface: wait(CV* cv, Lock* lock): Atomically releases the lock, suspends execution of the calling thread, and places that thread on cv's waitlist; after the thread is awoken, it re-acquires the lock before wait returns signal(CV* cv): takes one thread off of cv's waitlist and marks it as eligible to run. (No-op if waitlist is empty.)
Example: Bounded Buffers 0 1 2 3 4 5 (n = 6) void put(bbuf_t* ptr, int val){ acquire(&(ptr->lock)) 2 b 3 4 1 while(ptr->count == ptr->n) if(ptr->count == ptr->n) wait(&bread_bought) wait(&(ptr->bread_bought)) typedef struct { int* b; int n; int count; int front; int rear; pthread_mutex_t lock; CV bread_bought; CV bread_added; front rear ptr->b[ptr->rear]= val; ptr->rear= ((ptr->rear)+1)%(ptr->n); ptr->count++; signal(&(ptr->bread_added)) } release(&(ptr->lock)) } bbuf_t void init(bbuf_t* ptr, int n){ ptr->b = malloc(n*sizeof(int)); ptr->n = n; ptr->count = 0; ptr->front = 0; ptr->rear = 0; init(&(ptr->lock)); init(&(ptr->bread_bought)); init(&(ptr->bread_added)); int get(bbuf_t* ptr){ acquire(&(ptr->lock)) while(ptr->count == 0) if(ptr->count == 0) wait(&bread_added) wait(&(ptr->bread_added)) int val= ptr->b[ptr->front]; ptr->front= ((ptr->front)+1)%(ptr->n); ptr->count--; signal(&(ptr->bread_bought)) release(&(ptr->lock)) return val; } }
Using Condition Variables 1. Declare a lock. Each shared value needs a lock to enforce mutually exclusive access to the shared value. 2. Add code to acquire and release the lock. All code access the shared value must hold the objects lock. 3. Identify each place something could go wrong if the next line is executed and declare a condition variable that corresponds to when it is safe to proceed with the function. Add a wait for that condition to ensure the critical line is only executed under the right conditions. 4. Add a signal when the condition becomes true. 5. Add loops are your waits. Threads might not be scheduled immediately after they are eligible to run. Even if a condition was true when signal was called, it might not be true when a thread resumes execution.
Exercise: Synchronization Barrier With data parallel programming, a computation proceeds in parallel, with each thread operating on a different section of the data. Once all threads have completed, they can safely use each others results. int done_count = 0; Lock lock; CV all_done; /* Thread routine */ void *thread(void *args) { parallel_computation(args) acquire(&lock); done_count++; /* Thread routine */ void *thread(void *args) { parallel_computation(args) done_count++; if(done_count < n){ wait(&all_done, &lock); }else { for(int i=0;i<n;i++) signal(&all_done); } What can go wrong? release(&lock); use_results(); use_results(); } }
Condition Variables A condition variable cv is a stateless synchronization primitive that is used in combination with locks (mutexes) condition variables allow threads to efficiently wait for a change to the shared state protected by the lock a condition variable is comprised of a waitlist Interface: wait(CV * cv, Lock * lock): Atomically releases the lock, suspends execution of the calling thread, and places that thread on cv's waitlist; after the thread is awoken, it re-acquires the lock before wait returns signal(CV * cv): takes one thread off of cv's waitlist and marks it as eligible to run. (No-op if waitlist is empty.) broadcast(CV * cv): takes all threads off cv's waitlist and marks them as eligible to run. (No-op if waitlist is empty.)
Exercise: Readers/Writers Consider a collection of concurrent threads that have access to a shared object Some threads are readers, some threads are writers a unlimited number of readers can access the object at same time a writer must have exclusive access to the object int num_readers = 0; int num_writers = 0; Lock lock; CV readable; CV writeable; int num_readers = 0; int num_writers = 0; void writer(void *shared, int val){ void writer(void *shared, int val){ acquire(&lock); while(num_readers > 0) wait(writeable, &lock); num_writers=1; int reader(void *shared){ int reader(void *shared){ acquire(&lock); while(num_writers > 0) wait(readable, &lock); num_readers++; int x = read(shared); num_readers--; return x } num_readers++; int x = read(shared); num_readers--; return x } num_writers=1; release(&lock); write(shared, val); num_writers=0; write(shared, val); num_writers=0; broadcast(readable); acquire(&lock); if(num_readers == 0) signal(writeable); signal(writeable); release(&lock); release(&lock); } }
Programming with CVs C Python Initialization: pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t cv = PTHREAD_COND_INITIALIZER; Lock acquire/release: pthread_mutex_lock(&lock); pthread_mutex_unlock(&lock); CV operations: pthread_cond_wait(&cv, &lock); pthread_cond_signal(&cv); pthread_cond_broadcast(&cv); Initialization: lock = Lock() cv = Condition(lock) Lock acquire/release: lock.acquire() lock.release() V cv.wait() cv.notify() cv.notify_all()
