Synchronization & QueueingOutlineExample 1: Producer-Consumer ProblemProducer-ConsumerSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19ChallengeSynchronization variablesProducer-Consumer ExampleExample 2: Dining PhilosophersDining Philosopher ChallengeThe simple implementationDeadlocked!Formal Requirements for DeadlockProblems for Week 7Problems for Week 7 (contd)Queueing TheorySteady state Poisson arrival with l constant arrival rate (customers per unit time) each arrival is independent. P( t£t ) = 1- e–ltAnalysis of Queueing BehaviorSlide 34Useful Facts From Queuing TheoryServer Utilization: r = l/m Time in System: W = 1/(m-l) Time in Queue: Wq = r/(m-l) Number in Queue (Little): Lq = r2/(1-r)Slide 37Synchronization & QueueingCS241 Discussion Section Fall 2007Week 7Outline•Synchronization problems–Producer-consumer–Dining Philosophers•Queueing theoryExample 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 overwrittenExample 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 71) ds7-problem1.c contains producer-consumer code. Use the provided semaphores and mutexes to prevent buffer overflows, underflows, and race conditions.Think: When should the consumer block? When should the producer block?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 removed?Queueing TheoryQueuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPUSteady statePoisson arrival with constant arrival rate (customers per unit time) each arrival is independent. P( t ) = 1- e–t Queueing Theory01tAv λ0.5Analysis of Queueing BehaviorProbability n customers arrive in time interval t is: e–t t) n/ n!Assume random service times (also Poisson): constant service rate (customers per unit time)Queuing Diagram for Processes StartStartEvent QueueEvent QueueExitExitTime SliceTime SliceARRIVAL RATE ARRIVAL RATE SERVICE RATE SERVICE RATE SERVICE RATE SERVICE RATE 11ARRIVAL RATE ARRIVAL RATE 11Useful Facts From Queuing TheoryWq= mean time a customer spends in the queue = arrival rateLq = Wq number of customers in queueW = mean time a customer spends in the systemL = W ( Little's theorem) number of customers in the systemIn words – average length of queue is arrival rate times average waiting timeServer Utilization: = /Time in System: W = 1/(-)Time in Queue: Wq = /(-)Number in Queue (Little): Lq = 2/(1-)Analysis of Single Server QueuePoisson Arrival & ServiceRates Sum ARRIVAL RATE ARRIVAL RATE 11SERVICE RATE SERVICE RATE Input QueueInput QueueServerServerARRIVAL RATE ARRIVAL RATE 22== 11++
View Full Document