Carnegie Mellon Introduction to Computer Systems 15 213 18 243 spring 2009 27th Lecture Apr 30th Instructors Gregory Kesden and Markus P schel Carnegie Mellon Today Races deadlocks thread safety Multi code Thread Level Parallelism TLP Simultaneous Multi Threading SMT Carnegie Mellon Another 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 Mellon Deadlocking With POSIX Semaphores int 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 Mellon Deadlock Visualized in Progress Graph Thread 2 V s0 deadlock state Forbidden region for s1 Locking introduces the potential for deadlock waiting for a condition that will never be true V s1 Any trajectory that enters the deadlock region will eventually reach the deadlock state waiting for P s0 either s0 or s1 to become nonzero P s1 deadlock region P s0 s0 s1 1 Forbidden region for s2 P s1 V s0 V s1 Other trajectories luck out and skirt the deadlock region Thread 1 Unfortunate fact deadlock is often non deterministic Carnegie Mellon Avoiding Deadlock Acquire shared resources in same order int 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 Carnegie Mellon Avoided Deadlock in Progress Graph Thread 2 V s1 No way for trajectory to get stuck Processes acquire locks in same order Forbidden region for s1 Order in which locks released immaterial V s0 P s1 Forbidden region for s2 P s0 Thread 1 P s0 s0 s1 1 P s1 V s0 V s1 Carnegie Mellon Crucial 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 functions Carnegie Mellon Thread 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 9s Carnegie Mellon Thread 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 Mellon Making Thread Safe RNG Pass state as part of argument and thereby eliminate static state rand 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 must maintain seed Carnegie Mellon Thread 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 memory struct hostent gethostbyname char name static struct hostent h contact DNS and fill in h return h hostp Malloc gethostbyname r name hostp 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 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 functions 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 Class asctime ctime gethostbyaddr gethostbyname inet ntoa localtime rand Reentrant version 3 asctime r 3 ctime r 3 gethostbyaddr r 3 gethostbyname r 3 none 3 localtime r 2 rand r Carnegie Mellon Notifying With Semaphores producer thread shared buffer consumer thread 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 display Carnegie Mellon Producer Consumer on a Buffer That Holds One Item buf1 c producer consumer on 1 element buffer include csapp h int main pthread t tid producer pthread t tid consumer define NITERS 5 initialize the semaphores Sem init shared empty 0 1 Sem init shared full 0 0 void producer void arg void consumer void arg create threads and wait Pthread create tid producer NULL producer NULL Pthread create tid consumer NULL consumer NULL Pthread join tid producer NULL Pthread join tid consumer NULL struct int buf shared var sem t full sems sem t empty shared exit 0 Carnegie Mellon Producer Consumer cont Initially empty 1 full 0 producer thread void producer void arg int i item consumer thread void consumer void arg int i item for i 0 i NITERS i read item from buf P shared full item shared buf V shared empty for i 0 i NITERS i produce item item i printf produced d n item write item to buf P shared empty shared buf item V shared full return NULL consume item printf consumed d n item return NULL Carnegie Mellon Counting with Semaphores
View Full Document
Unlocking...