Carnegie Mellon
14
–
513
18
–
613
1
Carnegie Mellon
Synchronization: Advanced
15-213/18-213/14-513/15-513/18-613: Introduction to Computer Systems
26th Lecture, Nov. 21, 2019
2
Carnegie Mellon
Reminder: Semaphores
¡é Semaphore: non-negative global integer synchronization variable
¡é Manipulated by P and V operations: ¡ì P(s): [ while (s == 0); s–; ]
¡ì Dutch for “Proberen” (test) ¡ì V(s): [ s++; ]
¡ì Dutch for “Verhogen” (increment)
¡é OS kernel guarantees that operations between brackets [ ] are
executed atomically
¡ì Only one P or V operation at a time can modify s. ¡ìWhenwhileloopinPterminates,onlythat Pcandecrements
¡é Semaphore invariant: (s >= 0)
3
Carnegie Mellon
Review: Using semaphores to protect shared resources via mutual exclusion
¡é Basic idea:
¡ì Associate a unique semaphore mutex, initially 1, with each shared
variable (or related set of shared variables)
¡ì Surround each access to the shared variable(s) with P(mutex) and
V(mutex) operations
mutex = 1
P(mutex)
cnt++
V(mutex)
4
Carnegie Mellon
Review: Using Lock for Mutual Exclusion ¡é Basic idea:
¡ì Mutex is special case of semaphore that only has value 0 (locked) or 1 (unlocked)
¡ì Lock(m): [ while (m == 0); m=0; ]
¡ì Unlock(m): [ m=1]
¡é ~2x faster than using semaphore for this purpose ¡ì And, more clearly indicates programmer¡¯s intention
mutex = 1
lock(mutex)
cnt++
unlock(mutex)
5
Carnegie Mellon
Review: Producer-Consumer Problem
producer consumer thread thread
¡é Common synchronization pattern:
¡ì Producer waits for empty slot, inserts item in buffer, and notifies consumer ¡ì Consumer waits for item, removes it from buffer, and notifies producer
¡é Examples
¡ì Multimedia processing:
¡ì Producer creates video frames, consumer renders them ¡ì Event-driven graphical user interfaces
¡ì Producer detects mouse clicks, mouse movements, and keyboard hits and inserts corresponding events in buffer
¡ì Consumer retrieves events from buffer and paints the display
shared buffer
6
Carnegie Mellon
Review: Using Semaphores to Coordinate Access to Shared Resources
¡é Basic idea: Thread uses a semaphore operation to notify another thread that some condition has become true
¡ì Use counting semaphores to keep track of resource state. ¡ì Use binary semaphores to notify other threads.
¡é The Producer-Consumer Problem
¡ì Mediating interactions between processes that generate
information and that then make use of that information
¡ì Single entry buffer implemented with two binary semaphores
¡ì One to control access by producer(s)
¡ì One to control access by consumer(s)
¡ì N-entry implemented with semaphores + circular buffer
7
Carnegie Mellon
Today
¡é Using semaphores to schedule shared resources
¡ì Readers-writers problem
¡é Other concurrency issues ¡ì Thread safety
¡ì Races
¡ì Deadlocks
¡ì Interactions between threads and signal handling
8
Carnegie Mellon
Readers-Writers Problem
W1 R1
Read/
Write W2 Access
Read-only Access
R2 W3 R3
¡é Problem statement:
¡ì Reader threads only read the object
¡ì Writer threads modify the object (read/write access) ¡ì Writers must have exclusive access to the object
¡ì Unlimited number of readers can access the object
¡é Occurs frequently in real systems, e.g., ¡ì Online airline reservation system
¡ì Multithreaded caching Web proxy
9
Carnegie Mellon
Readers/Writers Examples
W1 R1
W2 R2
W3 R3
W1 R1
W2 R2
W3 R3
10
Carnegie Mellon
Variants of Readers-Writers
¡é First readers-writers problem (favors readers)
¡ì No reader should be kept waiting unless a writer has already been granted permission to use the object.
¡ì A reader that arrives after a waiting writer gets priority over the writer.
¡é Second readers-writers problem (favors writers)
¡ì Once a writer is ready to write, it performs its write as soon as
possible
¡ì A reader that arrives after a writer must wait, even if the writer is also waiting.
¡é Starvation (where a thread waits indefinitely) is possible in both cases.
11
Carnegie Mellon
Solution to First Readers-Writers Problem
Readers: Writers:
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
} }
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
rw1.c
12
Carnegie Mellon
Readers/Writers Examples
W1 W2
W3
R1 R2
R3
w=1 readcnt = 0
W1 W2
W3
w=0 readcnt = 2
R1 R2
R3
w=0 readcnt = 0
R1 R2
R3
W1 W2
W3
13
Carnegie Mellon
Solution to First Readers-Writers Problem
Readers: Writers:
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
} }
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
Arrivals: R1 R2 W1 R3
rw1.c
14
Carnegie Mellon
Solution to First Readers-Writers Problem
Readers: Writers:
R1
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
} }
rw1.c
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
Arrivals: R1 R2 W1 R3
Readcnt == 1 W == 0
15
Carnegie Mellon
Solution to First Readers-Writers Problem
Readers: Writers:
R2 R1
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
} }
rw1.c
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
Arrivals: R1 R2 W1 R3
Readcnt == 2 W == 0
16
Carnegie Mellon
R2 R1
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
} }
rw1.c
Solution to First Readers-Writers Problem
Readers: Writers:
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
Arrivals: R1 R2 W1 R3
Readcnt == 2 W == 0
W1
17
Carnegie Mellon
Solution to First Readers-Writers Problem
Readers: Writers:
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
R2
rw1.c
R1
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
Arrivals: R1 R2 W1 R3
Readcnt == 1 W == 0
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
W1
} }
18
Carnegie Mellon
R3 R2
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
Solution to First Readers-Writers Problem
Readers: Writers:
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
W1
P(&w);
V(&mutex);
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
rw1.c
Arrivals: R1 R2 W1 R3
Readcnt == 2 W == 0
R1
} }
19
Carnegie Mellon
Solution to First Readers-Writers Problem
Readers: Writers:
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
R3
rw1.c
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
W1
R2
} }
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
Arrivals: R1 R2 W1 R3
Readcnt == 1 W == 0
20
Carnegie Mellon
Solution to First Readers-Writers Problem
Readers: Writers:
R3
Arrivals: R1 R2 W1 R3
Readcnt == 0 W == 1
int readcnt; /* Initially 0 */ sem_t mutex, w; /* Both initially 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Reading happens here */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
} }
rw1.c
void writer(void)
{
while (1) {
P(&w);
/* Writing here */
V(&w); }
}
W1
21
Carnegie Mellon
Other Versions of Readers-Writers ¡é Shortcoming of first solution
¡ì Continuous stream of readers will block writers indefinitely
¡é Second version
¡ì Once writer comes along, blocks access to later readers ¡ì Series of writes could block all reads
¡é FIFO implementation
¡ì See rwqueue code in code directory
¡ì Service requests in order received
¡ì Threads kept in FIFO
¡ì Each has semaphore that enables its access to critical section
22
Carnegie Mellon
Solution to Second Readers-Writers Problem
int readcnt, writecnt; // Initially 0 sem_t rmutex, wmutex, r, w; // Initially 1 void reader(void)
{
while (1) {
P(&r);
P(&rmutex);
readcnt++;
if (readcnt
P(&w);
V(&rmutex);
V(&r)
== 1) /* First in */
/* Reading happens here */
P(&rmutex);
readcnt–;
if (readcnt
V(&w);
V(&rmutex);
} }
== 0) /* Last out */
23
Carnegie Mellon
Solution to Second Readers-Writers Problem
void writer(void)
{
while (1) {
P(&wmutex);
writecnt++;
if (writecnt == 1)
P(&r);
V(&wmutex);
P(&w);
/* Writing here */
V(&w);
P(&wmutex);
writecnt–;
if (writecnt == 0);
V(&r);
V(&wmutex);
}
}
24
Carnegie Mellon
Managing Readers/Writers with FIFO
Time
R
R
W
R
R
R
W
W
R
W
Requests
Allowed Concurrency
¡é Idea
¡ì Read & Write requests are inserted into FIFO ¡ì Requests handled as remove from FIFO
¡ì Read allowed to proceed if currently idle or processing read
¡ì Write allowed to proceed only when idle
¡ì Requests inform controller when they have completed
¡é Fairness
¡ì Guarantee very request is eventually handled
25
Carnegie Mellon
Readers Writers FIFO Implementation ¡é Full code in rwqueue.{h,c}
/* Queue data structure */
typedef struct {
sem_t mutex; // Mutual exclusion
int reading_count; // Number of active readers int writing_count; // Number of active writers // FIFO queue implemented as linked list with tail rw_token_t *head;
rw_token_t *tail;
} rw_queue_t;
/* Represents individual thread’s position in queue */
typedef struct TOK {
bool is_reader;
sem_t enable; // Enables access
struct TOK *next; // Allows chaining as linked list } rw_token_t;
26
Carnegie Mellon
Readers Writers FIFO Use ¡é In rwqueue-test.c
/* Get write access to data and write */
void iwriter(int *buf, int v) {
rw_token_t tok; rw_queue_request_write(&q, &tok); /* Critical section */
*buf = v;
/* End of Critical Section */ rw_queue_release(&q);
}
/* Get read access to data and read */
int ireader(int *buf)
{
rw_token_t tok; rw_queue_request_read(&q, &tok); /* Critical section */
int v = *buf;
/* End of Critical section */ rw_queue_release(&q);
return v;
}
27
Carnegie Mellon
Library Reader/Writer Lock ¡é Datatypepthread_rwlock_t
¡é Operations
¡ì Acquire read lock
Pthread_rwlock_rdlock(pthread_rw_lock_t *rwlock)
¡ì Acquire write lock Pthread_rwlock_wrlock(pthread_rw_lock_t *rwlock)
¡ì Release (either) lock Pthread_rwlock_unlock(pthread_rw_lock_t *rwlock)
¡é Observation
¡ì Library must be used correctly!
¡ì Up to programmer to decide what requires read access and what requires write access
28
Carnegie Mellon
Today
¡é Using semaphores to schedule shared resources ¡ì Readers-writers problem
¡é Other concurrency issues ¡ì Races
¡ì Deadlocks
¡ì Thread safety
¡ì Interactions between threads and signal handling
29
Carnegie Mellon
One Worry: Races
¡é A race occurs when correctness of the program depends on one thread reaching point x before another thread reaches point y
/* a threaded program with a race */
int main(int argc, char** argv) { pthread_t tid[N];
int i;
for (i = 0; i < N; i++)
Pthread_create(&tid[i], NULL, thread, &i); for (i = 0; i < N; i++)
Pthread_join(tid[i], NULL); return 0;
}
/* thread routine */
void *thread(void *vargp) {
int myid = *((int *)vargp); printf("Hello from thread %d\n", myid); return NULL;
}
race.c
30
Carnegie Mellon
Data Race
31
Carnegie Mellon
Race Elimination ¡é Don¡¯t share state
¡ì E.g., use malloc to generate separate copy of argument for each thread
¡é Use synchronization primitives to control access to shared state
norace.c
32
Carnegie Mellon
Today
¡é Using semaphores to schedule shared resources ¡ì Producer-consumer problem
¡é Other concurrency issues ¡ì Races
¡ì Deadlocks
¡ì Thread safety
¡ì Interactions between threads and signal handling
33
Carnegie Mellon
A Worry: Deadlock
¡é Def: A process is deadlocked iff it is waiting for a condition that will never be true.
¡é Typical Scenario
¡ì Processes 1 and 2 needs two resources (A and B) to proceed ¡ì Process 1 acquires A, waits for B
¡ì Process 2 acquires B, waits for A
¡ì Both will wait forever!
34
Carnegie Mellon
Deadlocking With Semaphores
int main(int argc, char** argv) {
pthread_t tid[2];
Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */ Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */ Pthread_create(&tid[0], NULL, count, (void*) 0); Pthread_create(&tid[1], NULL, count, (void*) 1); Pthread_join(tid[0], NULL);
Pthread_join(tid[1], NULL);
printf("cnt=%d\n", cnt);
return 0;
}
void *count(void *vargp)
{
int i;
int id = (int) vargp;
for (i = 0; i < NITERS; i++) {
P(&mutex[id]); P(&mutex[1-id]); cnt++;
V(&mutex[id]); V(&mutex[1-id]);
}
return NULL;
}
Tid[0]: P(s0); P(s1); cnt++; V(s0); V(s1);
Tid[1]: P(s1); P(s0); cnt++; V(s1); V(s0);
35
Carnegie Mellon
Deadlock Visualized in Progress Graph
Thread 1
V(s0)
V(s1)
P(s0) P(s1)
s0=s1=1
Locking introduces the potential for deadlock: waiting for a condition that will never be true
Any trajectory that enters the deadlock region will eventually reach the deadlock state, waiting for
either s0 or s1 to become nonzero
Other trajectories luck out and skirt the deadlock region
Thread 0
Deadlock state
Forbidden region for s0
Deadlock region
Forbidden region for s1
P(s0) P(s1)
V(s0) V(s1)
Unfortunate fact: deadlock is often nondeterministic (race)
36
Carnegie Mellon
Deadlock
37
Carnegie Mellon
Avoiding Deadlock
Acquire shared resources in same order
int main(int argc, char** argv) {
pthread_t tid[2];
Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */ Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */ Pthread_create(&tid[0], NULL, count, (void*) 0); Pthread_create(&tid[1], NULL, count, (void*) 1); Pthread_join(tid[0], NULL);
Pthread_join(tid[1], NULL);
printf("cnt=%d\n", cnt);
return 0;
}
void *count(void *vargp)
{
int i;
int id = (int) vargp;
for (i = 0; i < NITERS; i++) {
P(&mutex[0]); P(&mutex[1]); cnt++;
V(&mutex[id]); V(&mutex[1-id]);
}
return NULL;
}
Tid[0]: P(s0); P(s1); cnt++; V(s0); V(s1);
Tid[1]: P(s0); P(s1); cnt++; V(s1); V(s0);
38
Carnegie Mellon
Avoided Deadlock in Progress Graph
Thread 1
V(s0)
V(s1)
P(s1) P(s0)
s0=s1=1
No way for trajectory to get stuck
Processes acquire locks in same order
Order in which locks released immaterial
Forbidden region for s0
Forbidden region for s1
P(s0) P(s1)
V(s0) V(s1)
Thread 0
39
Carnegie Mellon
Demonstration
¡é See program deadlock.c
¡é 100 threads, each acquiring same two locks
¡é Risky mode
¡ì Even numbered threads request locks in opposite order of odd-
numbered ones
¡é Safe mode
¡ì All threads acquire locks in same order
40
Carnegie Mellon
Quiz Time!
Check out:
https://canvas.cmu.edu/courses/10968
41
Carnegie Mellon
Today
¡é Using semaphores to schedule shared resources ¡ì Readers-writers problem
¡é Other concurrency issues ¡ì Races
¡ì Deadlocks
¡ì Thread safety
¡ì Interactions between threads and signal handling
42
Carnegie Mellon
Crucial concept: Thread Safety
¡é Functions called from a thread must be thread-safe
¡é Def: A function is thread-safe iff it will always produce correct results when called repeatedly from multiple concurrent threads.
¡é Classes of thread-unsafe functions:
¡ì Class 1: Functions that do not protect shared variables
¡ì Class 2: Functions that keep state across multiple invocations ¡ì Class 3: Functions that return a pointer to a static variable
¡ì Class 4: Functions that call thread-unsafe functions
43
Carnegie Mellon
Thread-Unsafe Functions (Class 1) ¡é Failing to protect shared variables
¡ì Fix: Use P and V semaphore operations (or mutex)
¡ì Example: goodcnt.c
¡ì Issue: Synchronization operations will slow down code
44
Carnegie Mellon
Thread-Unsafe Functions (Class 2)
¡é Relying on persistent state across multiple function invocations ¡ì Example: Random number generator that relies on static state
static unsigned int next = 1;
/* rand: return pseudo-random integer on 0..32767 */
int rand(void)
{
next = next*1103515245 + 12345;
return (unsigned int)(next/65536) % 32768; }
/* srand: set seed for rand() */
void srand(unsigned int seed) {
next = seed; }
45
Carnegie Mellon
Thread-Safe Random Number Generator ¡é Pass state as part of argument
¡ì and, thereby, eliminate static state
/* rand_r - return pseudo-random integer on 0..32767 */
int rand_r(int *nextp)
{
*nextp = *nextp*1103515245 + 12345;
return (unsigned int)(*nextp/65536) % 32768; }
¡é Consequence: programmer using rand_r must maintain seed
46
Carnegie Mellon
Thread-Unsafe Functions (Class 3)
¡é Returning a pointer to a static variable
¡é Fix 1. Rewrite function so caller passes address of variable to store result
¡ì Requires changes in caller and callee
¡é Fix 2. Lock-and-copy
¡ì Requires simple changes in
caller (and none in callee)
¡ì However, caller must free memory.
/* Convert integer to string */ char *itoa(int x)
{
static char buf[11];
sprintf(buf, "%d", x);
return buf;
}
char *lc_itoa(int x, char *dest) {
P(&mutex);
strcpy(dest, itoa(x));
V(&mutex);
return dest;
}
47
Carnegie Mellon
Thread-Unsafe Functions (Class 4) ¡é Calling thread-unsafe functions
¡ì Calling one thread-unsafe function makes the entire function that calls it thread-unsafe
¡ì Fix: Modify the function so it calls only thread-safe functionsJ
48
Carnegie Mellon
Reentrant Functions
¡é Def: A function is reentrant iff it accesses no shared variables when called by multiple threads.
¡ì Important subset of thread-safe functions
¡ì Require no synchronization operations
¡ì Only way to make a Class 2 function thread-safe is to make it reetnrant (e.g., rand_r )
All functions
Thread-safe functions
Reentrant functions
Thread-unsafe functions
49
Carnegie Mellon
Thread-Safe Library Functions
¡é All functions in the Standard C Library (at the back of your K&R text) are thread-safe
¡ì Examples: malloc, free, printf, scanf
¡é Most Unix system calls are thread-safe, with a few exceptions:
Thread-unsafe function
asctime
ctime
gethostbyaddr
gethostbyname
inet_ntoa
localtime
rand
Class Reentrant version
3 asctime_r
3 ctime_r
3 gethostbyaddr_r 3 gethostbyname_r 3 (none)
3 localtime_r
2 rand_r
50
Carnegie Mellon
Today
¡é Using semaphores to schedule shared resources ¡ì Readers-writers problem
¡é Other concurrency issues ¡ì Races
¡ì Deadlocks
¡ì Thread safety
¡ì Interactions between threads and signal handling
51
Carnegie Mellon
Signal Handling Review
¡é Action
Icurr Inext
Receive signal
Handler
¡ì Signal can occur at any point in program execution ¡ì Unless signal is blocked
¡ì Signal handler runs within same thread
¡ì Must run to completion and then return to regular program execution
52
Carnegie Mellon
Threads / Signals Interactions
fprintf.lock()
Icurr Inext
fprintf.unlock()
Receive signal
Handler
¡é Many library functions use lock-and-copy for thread safety
¡ì Because they have hidden state ¡ì malloc
¡ì Free lists
¡ì fprintf, printf, puts
¡ì So that outputs from multiple threads don¡¯t interleave ¡ì sprintf
¡ì Not officially asynch-signal-safe, but seems to be OK
¡é OK for handler that doesn¡¯t use these library functions
53
Carnegie Mellon
Bad Thread / Signal Interactions
fprintf.lock()
Icurr Inext
fprintf.unlock()
Receive signal
Handler
fprintf.lock()
fprintf.unlock()
¡é What if:
¡ì Signal received while library function holds lock ¡ì Handler calls same (or related) library function
¡é Deadlock!
¡ì Signal handler cannot proceed until it gets lock
¡ì Main program cannot proceed until handler completes
¡é Key Point
¡ì Threads employ symmetric concurrency ¡ì Signal handling is asymmetric
54
Carnegie Mellon
Threads Summary
¡é Threads provide another mechanism for writing concurrent programs
¡é Threads are growing in popularity ¡ì Somewhat cheaper than processes
¡ì Easy to share data between threads
¡é However, the ease of sharing has a cost: ¡ì Easy to introduce subtle synchronization errors ¡ì Tread carefully with threads!
¡é For more info:
¡ì D. Butenhof, ¡°Programming with Posix Threads¡±, Addison-Wesley, 1997
55