Slide 1Slide 2Midterm StatisticsMP5 OverviewSlide 5Slide 6Classical Synchronization ProblemsExample 1: Producer-Consumer ProblemProducer-ConsumerSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24ChallengeSynchronization variablesProducer-Consumer ExampleExample 2: Dining PhilosophersDining Philosopher ChallengeThe simple implementationDeadlocked!Formal Requirements for DeadlockProblems for Week 7 (contd)CS 241 Section Week #7(10/22/09)Topics This SectionMidterm StatisticsMP5 ForwardClassical Synchronization ProblemsProblemsMidterm StatisticsAvg: 18.6Median: 19Max: 25Min: 10Standard Deviation: 3.3MP5 OverviewMP5 OverviewThis is your first long MP. You have two weeks to complete it. You are to create a “deadlock resilient semaphore” library. You should implement six functions.You need to implement:–Deadlock prevention•enforce a global ordering on all locks•Locks should be acquired in descending order–Deadlock avoidance•No cycle exist in a wait-for graph•You need to implement the cycle detection algorithmMP5 Overview–Deadlock detection•Periodically incur the cycle detection algorithm•once a deadlock is detected, you need only send a SIGINT signal. The library does NOT need to worry about how SIGINT is handled.Since we only allow one instance of each resource, you do not need to implement the Banker’s algorithm for deadlock prevention. You may use a resource allocation graph instead.The given test cases are far from complete. You should derive your own test cases.Classical Synchronization ProblemsExample 1:Producer-Consumer ProblemProducers insert items Consumers remove itemsShared bounded buffer e.g. a circular buffer with an insert and a removal pointer.Producer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrBUFFER FULL: Producer must be blocked!Producer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrBUFFER EMPTY: Consumer must be blocked!ChallengeNeed to prevent:Buffer OverflowProducer writing when there is no storageBuffer UnderflowConsumer reading nonexistent dataRace conditionTwo processes editing the list at the same timeSynchronization variablesCreate these variables to prevent these problems:items semaphoreCounts how many items are in the bufferCannot drop below 0slots semaphoreCounts how may slots are available in the bufferCannot drop below 0list mutexMakes buffer access mutually exclusiveProducer-Consumer Exampleds7-problem1.c shows an example implementation for one producer and one consumer, but without synchronization code.•Running it shows–Buffer underflows•Nonsense data is consumed–Buffer overflows•Unconsumed data is overwritten•Think: When should the consumer block? When should the producer block?Example 2:Dining PhilosophersDining 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 deadlockThe simple implementationwhile(true) {think()lock(chopstick[i])lock(chopstick[(i+1) % N])eat()unlock(chopstick[(i+1) % N])unlock(chopstick[i])}Does this work?Deadlocked!When every philosopher has picked up his left chopstick, and no philosopher has yet picked up his right chopstick, no philosopher can continue.Each philosopher waits for his right neighbor to put a chopstick down, which he will never do.This is a deadlock.Formal 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 chopstickThe simple implementations satisfies all of these.Problems for Week 7 (contd)2) ds7-problem2.c contains dining philosophers code. Alter the program to prevent deadlock. There are multiple ways to do this.Think: What are the conditions of deadlock? Can any of them be
View Full Document
Unlocking...