Carnegie Mellon Synchroniza on Advanced 15 213 Introduc0on to Computer Systems 24th Lecture Nov 18 2010 Instructors Randy Bryant and Dave O Hallaron 1 Carnegie Mellon Today Producer consumer problem Readers writers problem Thread safety Races Deadlocks 2 Carnegie Mellon Using Semaphores to Schedule Access to Shared Resources Basic idea Thread uses a semaphore opera on to no fy another thread that some condi on has become true Use coun0ng semaphores to keep track of resource state Use binary semaphores to no0fy other threads Two classic examples The Producer Consumer Problem The Readers Writers Problem 3 Carnegie Mellon Producer Consumer Problem producer thread shared bu er consumer thread Common synchroniza on paGern Producer waits for empty slot inserts item in bu er and no0 es consumer Consumer waits for item removes it from bu er and no0 es producer Examples Mul0media 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 bu er Consumer retrieves events from bu er and paints the display 4 Carnegie Mellon Producer Consumer on 1 element Bu er include csapp h define NITERS 5 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 void producer void arg void consumer void arg struct int buf shared var sem t full sems sem t empty shared 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 exit 0 5 Carnegie Mellon Producer Consumer on 1 element Bu er Ini ally 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 Consume item printf consumed d n item Write item to buf P shared empty shared buf item V shared full return NULL return NULL 6 Carnegie Mellon Producer Consumer on an n element Bu er Requires a mutex and two coun ng semaphores mutex enforces mutually exclusive access to the the bu er slots counts the available slots in the bu er items counts the available items in the bu er Implemented using a shared bu er package called sbuf 7 Carnegie Mellon sbuf Package Declara ons include csapp h typedef struct int buf int n int front int rear sem t mutex sem t slots sem t items sbuf t Buffer array Maximum number of slots buf front 1 n is first item buf rear n is last item Protects accesses to buf Counts available slots Counts available items void sbuf init sbuf t sp int n void sbuf deinit sbuf t sp void sbuf insert sbuf t sp int item int sbuf remove sbuf t sp sbuf h 8 Carnegie Mellon sbuf Package Implementa on Ini alizing and deini alizing a shared bu er Create an empty bounded shared FIFO buffer with n slots void sbuf init sbuf t sp int n sp buf Calloc n sizeof int sp n n Buffer holds max of n items sp front sp rear 0 Empty buffer iff front rear Sem init sp mutex 0 1 Binary semaphore for locking Sem init sp slots 0 n Initially buf has n empty slots Sem init sp items 0 0 Initially buf has zero items Clean up buffer sp void sbuf deinit sbuf t sp Free sp buf sbuf c 9 Carnegie Mellon sbuf Package Implementa on Inser ng an item into a shared bu er Insert item onto the rear of shared buffer sp void sbuf insert sbuf t sp int item P sp slots Wait for available slot P sp mutex Lock the buffer sp buf sp rear sp n item Insert the item V sp mutex Unlock the buffer V sp items Announce available item sbuf c 10 Carnegie Mellon sbuf Package Implementa on Removing an item from a shared bu er Remove and return the first item from buffer sp int sbuf remove sbuf t sp int item P sp items P sp mutex item sp buf sp front sp n V sp mutex V sp slots return item Wait for available item Lock the buffer Remove the item Unlock the buffer Announce available slot sbuf c 11 Carnegie Mellon Today Producer consumer problem Readers writers problem Thread safety Races Deadlocks 12 Carnegie Mellon Readers Writers Problem Generaliza on of the mutual exclusion problem Problem statement Reader threads only read the object Writer threads modify the object 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 reserva0on system Mul0threaded caching Web proxy 13 Carnegie Mellon Variants of Readers Writers First readers writers problem favors readers No reader should be kept wai0ng unless a writer has already been granted permission to use the object A reader that arrives a er a wai0ng 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 a er a writer must wait even if the writer is also wai0ng Starva5on where a thread waits inde nitely is possible in both cases 14 Carnegie Mellon Solu on to First Readers Writers Problem Readers 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 Writers void writer void while 1 P w Writing here V w rw1 c P mutex readcnt if readcnt 0 Last out V w V mutex 15 Carnegie Mellon Case Study Prethreaded Concurrent Server Pool of worker threads Service client Client Master thread Bu er Remove descriptors Client Service client Accept connec5ons Insert descriptors Worker thread Worker thread 16 Carnegie Mellon Prethreaded Concurrent Server sbuf t sbuf Shared buffer of connected descriptors int main int argc char argv int i listenfd connfd port socklen t clientlen sizeof struct sockaddr in struct sockaddr in clientaddr pthread t tid port atoi argv 1 sbuf init sbuf SBUFSIZE listenfd Open listenfd port for i 0 i NTHREADS i Create worker threads Pthread create tid NULL thread NULL while 1 connfd Accept listenfd SA clientaddr clientlen sbuf insert sbuf connfd Insert connfd in buffer echoservert pre c 17 Carnegie Mellon Prethreaded Concurrent Server Worker thread rou ne void thread void vargp Pthread detach pthread self while 1 int connfd sbuf remove sbuf Remove connfd from buffer echo cnt connfd Service client Close connfd echoservert pre c 18 Carnegie Mellon Prethreaded Concurrent Server echo cnt ini aliza on rou ne static int byte cnt
View Full Document
Unlocking...