Carnegie MellonIntroduction to Computer Systems15-213/18-243, spring 200927thLecture, Apr. 30thInstructors:Gregory Kesden and Markus PüschelCarnegie MellonToday Races, deadlocks, thread safety Multi-code Thread Level Parallelism (TLP) Simultaneous Multi -Threading (SMT)Carnegie MellonAnother worry: Deadlock Processes wait for 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!Carnegie MellonDeadlocking With POSIX Semaphoresint main() {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);exit(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);Carnegie MellonDeadlock Visualized in Progress GraphLocking introduces thepotential for deadlock: waiting for a condition that will never be trueAny trajectory that entersthe deadlock region willeventually reach thedeadlock state, waiting for either s0or s1to become nonzeroOther trajectories luck out and skirt the deadlock regionUnfortunate fact: deadlock is often non-deterministicThread 1Thread 2P(s0) V(s0)P(s1) V(s1)V(s1)P(s1)P(s0)V(s0)Forbidden regionfor s1Forbidden regionfor s2deadlockstatedeadlockregions0=s1=1Carnegie MellonAvoiding Deadlockint main() {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);exit(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);Acquire shared resources in same orderCarnegie MellonAvoided Deadlock in Progress GraphThread 1Thread 2P(s0) V(s0)P(s1) V(s1)V(s0)P(s0)P(s1)V(s1)Forbidden regionfor s1Forbidden regionfor s2s0=s1=1No way for trajectory to get stuckProcesses acquire locks in same orderOrder in which locks released immaterialCarnegie MellonCrucial concept: Thread Safety Functions called from a thread (without external synchronization) must be thread-safe Meaning: it must always produce correct results when called repeatedly from multiple concurrent threads Some examples of thread-unsafe functions: Failing to protect shared variables Relying on persistent state across invocations Returning a pointer to a static variable Calling thread-unsafe functionsCarnegie MellonThread-Unsafe Functions (Class 1) Failing to protect shared variables Fix: Use P and V semaphore operations Example: goodcnt.c Issue: Synchronization operations will slow down code e.g., badcnt requires 0.5s, goodcnt requires 7.9sCarnegie MellonThread-Unsafe Functions (Class 2) Relying on persistent state across multiple function invocations Example: Random number generator (RNG) that relies on static state /* rand: return pseudo-random integer on 0..32767 */ static unsigned int next = 1; 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; }Carnegie MellonMaking Thread-Safe RNG Pass state as part of argument and, thereby, eliminate static state Consequence: programmer using rand must maintain seed/* rand - return pseudo-random integer on 0..32767 */ int rand_r(int *nextp) { *nextp = *nextp*1103515245 + 12345; return (unsigned int)(*nextp/65536) % 32768; }Carnegie MellonThread-Unsafe Functions (Class 3) Returning a ptr to a static variable Fixes: 1. Rewrite code so caller passes pointer to struct– Issue: Requires changes in caller and callee 2. Lock-and-copy– Issue: Requires only simple changes in caller (and none in callee)– However, caller must free memoryhostp = Malloc(...);gethostbyname_r(name, hostp);struct hostent *gethostbyname(char name){static struct hostent h;<contact DNS and fill in h>return &h;}struct hostent *gethostbyname_ts(char *name) {struct hostent *q = Malloc(...);struct hostent *p;P(&mutex); /* lock */p = gethostbyname(name);*q = *p; /* copy */V(&mutex);return q;}Carnegie MellonThread-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 functions Carnegie MellonThread-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 Class Reentrant versionasctime 3 asctime_rctime 3 ctime_rgethostbyaddr 3 gethostbyaddr_rgethostbyname 3 gethostbyname_rinet_ntoa 3 (none)localtime 3 localtime_rrand 2 rand_rCarnegie MellonNotifying With Semaphores Common synchronization pattern: Producer waits for slot, inserts item in buffer, and notifies consumer Consumer waits for item, removes it from buffer, and notifies producer Examples Multimedia processing: Producer creates MPEG 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 displayproducerthreadsharedbufferconsumerthreadCarnegie MellonProducer-Consumer on a Buffer That Holds One Item/* buf1.c - producer-consumeron 1-element buffer */#include “csapp.h”#define NITERS 5void *producer(void *arg);void *consumer(void *arg);struct {int buf; /* shared var */sem_t full; /* sems */sem_t empty;} shared;int main() {pthread_t tid_producer;pthread_t tid_consumer;/* initialize the semaphores */Sem_init(&shared.empty, 0, 1); Sem_init(&shared.full, 0, 0);/* create threads and wait */Pthread_create(&tid_producer, NULL, producer,
View Full Document
Unlocking...