Slide 1TodayAnother worry: DeadlockDeadlocking With POSIX SemaphoresDeadlock Visualized in Progress GraphAvoiding DeadlockAvoided Deadlock in Progress GraphCrucial concept: Thread SafetyThread-Unsafe Functions (Class 1)Thread-Unsafe Functions (Class 2)Making Thread-Safe RNGThread-Unsafe Functions (Class 3)Thread-Unsafe Functions (Class 4)Thread-Safe Library FunctionsNotifying With SemaphoresProducer-Consumer on a Buffer That Holds One ItemProducer-Consumer (cont)Counting with SemaphoresCounting with semaphores (cont)Producer-Consumer on a Buffer That Holds More than One ItemProducer-Consumer (cont)Threads SummarySlide 25Slide 26Slide 27Slide 28Interaction With the Operating SystemSlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Carnegie MellonIntroduction to Computer Systems15-213/18-243, spring 200927th Lecture, Apr. 30thInstructors: Gregory Kesden and Markus PüschelCarnegie MellonTodayRaces, deadlocks, thread safetyMulti-codeThread Level Parallelism (TLP)Simultaneous Multi -Threading (SMT)Carnegie MellonAnother worry: DeadlockProcesses wait for condition that will never be trueTypical ScenarioProcesses 1 and 2 needs two resources (A and B) to proceedProcess 1 acquires A, waits for BProcess 2 acquires B, waits for ABoth 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 s0 or s1 to 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 SafetyFunctions called from a thread (without external synchronization) must be thread-safeMeaning: it must always produce correct results when called repeatedly from multiple concurrent threadsSome examples of thread-unsafe functions:Failing to protect shared variablesRelying on persistent state across invocationsReturning a pointer to a static variableCalling thread-unsafe functionsCarnegie MellonThread-Unsafe Functions (Class 1)Failing to protect shared variablesFix: Use P and V semaphore operationsExample: goodcnt.cIssue: Synchronization operations will slow down codee.g., badcnt requires 0.5s, goodcnt requires 7.9sCarnegie MellonThread-Unsafe Functions (Class 2)Relying on persistent state across multiple function invocationsExample: 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 RNGPass state as part of argumentand, 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 variableFixes: 1. Rewrite code so caller passes pointer to struct–Issue: Requires changes in caller and callee2. 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 functionsCalling one thread-unsafe function makes the entire function that calls it thread-unsafeFix: Modify the function so it calls only thread-safe functions Carnegie MellonThread-Safe Library FunctionsAll functions in the Standard C Library (at the back of your K&R text) are thread-safeExamples: malloc, free, printf, scanfMost 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 SemaphoresCommon synchronization pattern:Producer waits for slot, inserts item in buffer, and notifies consumerConsumer waits for item, removes it from buffer, and
View Full Document