SynchronizationCS241 AdministrativeThis lectureProducer-ConsumerSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Producer-Consumer ProblemSlide 27ChallengeSolutionAssembling the solutionPseudocode getItem()Pseudocode putItem(data)Dining PhilosophersDining Philosopher ChallengeSeems simple enough …?What if?Slide 37Formal Requirements for DeadlockSlide 39Define the Input and Output of the FollowingCopyright ©: Nahrstedt, Angrave, Abdelzaher 1SynchronizationCopyright ©: Nahrstedt, Angrave, Abdelzaher2CS241 AdministrativeThis weekSMP4 is due todayHW1 will be out next (practice for midterm)Copyright ©: Nahrstedt, Angrave, Abdelzaher3This lectureGoals:Introduce classic synchronization problemsTopicsProducer-ConsumerDining PhilosophersCopyright ©: Nahrstedt, Angrave, Abdelzaher4Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher5Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher6Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher7Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher8Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher9Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher10Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher11Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher12Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher13Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher14Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher15Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher16Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher17Producer-ConsumerinsertPtrremovePtrBUFFER FULL: Producer must be blocked!Copyright ©: Nahrstedt, Angrave, Abdelzaher18Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher19Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher20Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher21Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher22Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher23Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher24Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher25Producer-ConsumerinsertPtrremovePtrBUFFER EMPTY: Consumer must be blocked!Copyright ©: Nahrstedt, Angrave, Abdelzaher26Producer-Consumer ProblemProducers insert items Consumers remove itemsShared bounded buffer ** Efficient implementation is a circular buffer with an insert and a removal pointer.Copyright ©: Nahrstedt, Angrave, Abdelzaher27Producer-Consumer ProblemProducer inserts items. Updates insertion pointer.Consumer executes destructive reads on the buffer. Updates removal pointerBoth update information about how full/empty the buffer is. Solution should allow multiple readers/writersCopyright ©: Nahrstedt, Angrave, Abdelzaher28ChallengePrevent buffer overflowPrevent buffer underflowProper synchronizationCopyright ©: Nahrstedt, Angrave, Abdelzaher29SolutionPrevent overflow: block producer when full! Counting semaphore to count #free slots 0 block producerPrevent underflow: block consumer when empty!Counting semaphore to count #items in buffer 0 block consumerMutex to protect accesses to shared buffer & pointers.Copyright ©: Nahrstedt, Angrave, Abdelzaher30Assembling 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.Copyright ©: Nahrstedt, Angrave, Abdelzaher31Pseudocode getItem()Error checking/EINTR handling not shownsem_wait(items)mutex_lock(mutex)result=buffer[ removePtr ];removePtr=(removePtr +1 ) % Nmutex_unlock(mutex)sem_post(slots)Copyright ©: Nahrstedt, Angrave, Abdelzaher32Pseudocode 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)Copyright ©: Nahrstedt, Angrave, Abdelzaher33Dining PhilosophersCopyright ©: Nahrstedt, Angrave, Abdelzaher34Dining Philosopher Challenge{ Think | Eat }N Philosophers circular table with N chopsticksTo eat the Philosopher must first pickup two chopsticksith Philosopher needs ith & i+1st chopstickOnly put down chopstick when Philosopher has finished eatingDevise a solution which satisfies mutual exclusion but avoids starvation and deadlockCopyright ©: Nahrstedt, Angrave, Abdelzaher35Seems simple enough …?while(true) {think()lock(chopstick[i])lock(chopstick[(i+1) % N])eat()unlock(chopstick[(i+1) % N])unlock(chopstick[i])}Copyright ©: Nahrstedt, Angrave, Abdelzaher36What if?Made picking up left and right chopsticks an atomic operation?or,N-1 Philosophers but N chopsticks?Copyright ©: Nahrstedt, Angrave, Abdelzaher37What if?Made picking up left and right chopsticks an atomic operation?or,N-1 Philosophers but N chopsticks?… both changes prevent deadlock.Copyright ©: Nahrstedt, Angrave, Abdelzaher38Formal Requirements for DeadlockMutual exclusionHold and wait conditionNo preemption conditionCircular wait conditionOriginal scenario & our proposed ritual had all four of these properties.Copyright ©: Nahrstedt, Angrave, Abdelzaher39Formal Requirements for DeadlockMutual exclusion Exclusive use of chopsticksHold and wait conditionHold 1 chopstick, wait for nextNo preemption conditionCannot force another to undo their holdCircular wait conditionEach waits for next neighbor to put down chopstickCopyright ©: Nahrstedt, Angrave, Abdelzaher40Define the Input and Output of the
View Full Document