DOC PREVIEW
U of I CS 241 - Synchronization & Queueing

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 241 - Synchronization & Queueing

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Synchronization & Queueing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Synchronization & Queueing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Synchronization & Queueing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?