CS241 Systems Programming Synchronization ProblemsCS241 AdministrativeThis lectureProducer ConsumerProducer-ConsumerProducer-Consumer ProblemChallenge?ChallengeBuffer underflowBuffer overflowMutual ExclusionWhat could possibly go wrong?Slide 13Other edge casesImplementation?2 Counting Semaphores and a mutexAssembling the solutionPseudocode getItem()Pseudocode putItem(data)Analysis#1 What's the precise problem?Deadlock e.g Consumer waits for producer to insert a new item but Producer is waiting for Consumer to release mutexAnalysis#2Buffer overflow when reader removes item from a full buffer: Producer inserts item too earlyOther considerationsDining PhilosophersHistoryDining Philosopher ChallengeSeems simple enough …?… Deadlock (Each P. holds left fork)What if?Slide 31Formal requirements for deadlockSlide 33CS 241 Spring 2007System Programming 01/13/19 CS241 © 2006,2007 LA, RHC and YZ, All Rights Reserved1CS241 Systems ProgrammingSynchronization ProblemsLawrence Angrave2CS241 AdministrativeThis weekHW due FridayNext weekMidterm Monday in class3This lectureGoals:Introduce classic synchronization problemsTopicsProducer-ConsumerDining Philosophers4Producer ConsumerProblem occurs in system & application programminge.g. Web Server dispatches incoming web requests to a waiting process(es)e.g. GUI events from keyboard,& mouse are queued by O/S and consumed by applications.Pipelines (Hardware & software examples)5Producer-ConsumerinsertPtrremovePtr6Producer-Consumer ProblemProducers insert items Consumers remove itemsShared bounded buffer ** Efficient implementation is a circular buffer with an insert and a removal pointer.7Challenge?What the abstract requirements that our solution must satisfy?8ChallengePrevent buffer overflowPrevent buffer underflowProper synchronizationMutual ExclusionProgressBounded waiti.e. Prevent deadlock9Buffer underflowImagine:Producer inserts an itemConsumer removes an itemConsumer removes another itemConclusions:Make sure consumer only retrieves valid items from the bufferConsumer should block (or return an error code) if there are no items available10Buffer overflowProducer inserts too many items and the buffer overflowsConclusion:Block Producer if the buffer is full11Mutual ExclusionProducer inserts items. Updates insertion pointer.Consumer executes destructive reads on the buffer. Update removal pointerBoth update information about how full/empty the buffer is. Solution should allow multiple readers/writers12What could possibly go wrong?Check the tricky "Edge cases"e.g. Producer is waiting(blocked) but the buffer is already full. Now Consumer reads an item.What could go wrong at this point?13What could possibly go wrong?Check the tricky "Edge cases"e.g. Producer is waiting(blocked) but the buffer is already full. Now Consumer calls remove()What could go wrong at this point?oConsumer cannot continue because Producer is in critical section => deadlockoProducer is never unblocked => deadlockoConsumer unblocks Producer too early. Failed mutual exclusion => corrupt data.oSuppose another consumer/producer arrives… will our implementation still work?14Other edge casesoTwo producers call insert() at the same timeoConsumer(s) is/are waiting on an empty buffer. Producer tries to insert one item.15Implementation?What do we need to prevent buffer underflow?What do we need to prevent buffer overflow?What do we need to protect updates to buffer?162 Counting Semaphores and a mutexCounting semaphore to count # items in bufferCounting semaphore to count # free slotsMutex to protect accesses to shared buffer & pointers.17Assembling the solutionsem_wait(slots), sem_post(slots)sem_wait(items), sem_post(items)mutex_lock(m) mutex_unlock(m)insertptr=(insertptr+1) % Nremovalptr=(removalptr+1) % NInitialize semaphore slots to size of bufferInitialize semaphore items to zero.18Pseudocode getItem()Error checking/EINTR handling not shownsem_wait(items)mutex_lock(mutex)result=buffer[ removePtr ];removePtr=(removePtr +1 ) % Nmutex_unlock(mutex)sem_post(slots)so what about insertItem()?19Pseudocode putItem(data)Error checking/EINTR handling not shownsem_wait(slots)mutex_lock(mutex)buffer[ insertPtr]= data;insertPtr=(insertPtr + 1 ) % Nmutex_unlock(mutex)sem_post(items)20Analysis#1 What's the precise problem?putItem(data) {mutex_lock(mutex)sem_wait(slots) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}Underflow?Overflow?getItem() {mutex_lock(mutex)sem_wait(items) result=buffer[ removePtr ]; removePtr=…sem_post(slots)mutex_unlock(mutex)}Deadlock? Failed Mut Excl?21Deadlock e.g Consumer waits for producer to insert a new item but Producer is waiting for Consumer to release mutexputItem(data) {mutex_lock(mutex) #2sem_wait(slots) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}getItem() {mutex_lock(mutex)sem_wait(items) BLOCKS #1 result=buffer[ removePtr ]; removePtr=…sem_post(slots)mutex_unlock(mutex)}22Analysis#2 putItem(data) {sem_wait(slots)mutex_lock(mutex) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}getItem() {sem_wait(items)sem_post(slots)mutex_lock(mutex) result=buffer[ removePtr ]; removePtr=…mutex_unlock(mutex)}23Buffer overflow when reader removes item from a full buffer: Producer inserts item too earlyputItem(data) {sem_wait(slots)mutex_lock(mutex) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}getItem() {sem_wait(items)sem_post(slots)mutex_lock(mutex) result=buffer[ removePtr ]; removePtr=…mutex_unlock(mutex)}24Other considerationsEarly cancelation using signals?Limited Production?(Possibly no items)… Consumers wait forever… Consumers quit too early? One implementation: Insert special end-value into queue which consumers read (but may not consume) Other reasonable implementations (condition variables;not covered in CS241)Priority of Consumers & Producers25Dining Philosophers26HistoryDijkstra 1971Originally set as a exam questionIllustrates Starvation, DeadlockTest shared resource allocation algorithmsSee Stallings Ch.6.6 p.27627Dining Philosopher Challenge{ Think | Eat }N Philosophers circular table with N chopsticksTo eat the Philosopher must first pickup two chopsticksith Philosopher needs ith & i+1th chopstickOnly put down chopstick when Philosopher has finished eatingDevise a solution which satisfies mutual exclusion but avoids starvation and deadlock28Seems simple enough …?while(true) { think()
View Full Document