U of I CS 241 - Synchronization & Queueing (37 pages)

Previewing pages 1, 2, 17, 18, 19, 36, 37 of 37 page document View the full content.
View Full Document

Synchronization & Queueing



Previewing pages 1, 2, 17, 18, 19, 36, 37 of actual document.

View the full content.
View Full Document
View Full Document

Synchronization & Queueing

106 views


Pages:
37
School:
University of Illinois
Course:
Cs 241 - Intermediate Programming in C++
Intermediate Programming in C++ Documents
Unformatted text preview:

Synchronization Queueing CS241 Discussion Section Fall 2007 Week 7 Outline Synchronization problems Producer consumer Dining Philosophers Queueing theory Example 1 Producer Consumer Problem Producers insert items Consumers remove items Shared bounded buffer e g a circular buffer with an insert and a removal pointer Producer Consumer insertPtr removePtr Producer Consumer insertPtr removePtr Producer Consumer insertPtr removePtr Producer Consumer insertPtr removePtr Producer Consumer insertPtr removePtr Producer Consumer insertPtr removePtr Producer Consumer insertPtr removePtr Producer Consumer BUFFER FULL Producer must be blocked insertPtr removePtr Producer Consumer removePtr insertPtr Producer Consumer removePtr insertPtr Producer Consumer removePtr insertPtr Producer Consumer removePtr insertPtr Producer Consumer removePtr insertPtr Producer Consumer removePtr insertPtr Producer Consumer removePtr insertPtr Producer Consumer BUFFER EMPTY Consumer must be blocked removePtr insertPtr Challenge Need to prevent Buffer Overflow Producer writing when there is no storage Buffer Underflow Consumer reading nonexistent data Race condition Two processes editing the list at the same time Synchronization variables Create these variables to prevent these problems items semaphore Counts how many items are in the buffer Cannot drop below 0 slots semaphore Counts how may slots are available in the buffer Cannot drop below 0 list mutex Makes buffer access mutually exclusive Producer Consumer Example ds7 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 Example 2 Dining Philosophers Dining Philosopher Challenge Think Eat N Philosophers circular table with N chopsticks To eat the Philosopher must first pickup two chopsticks ith Philosopher needs ith i 1st chopstick Only put down chopstick when Philosopher has finished eating Devise a solution which satisfies mutual exclusion but avoids starvation and deadlock The simple implementation while 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 Deadlock Mutual exclusion Exclusive use of chopsticks Hold and wait condition Hold 1 chopstick wait for next No preemption condition Cannot force another to undo their hold Circular wait condition Each waits for next neighbor to put down chopstick The simple implementations satisfies all of these Problems for Week 7 1 ds7 problem1 c contains producerconsumer 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 Theory Queuing Diagram for Processes Exit Start Ready Queue Time Slice Event Event Queue CPU Queueing Theory Steady state Poisson arrival with constant arrival rate customers per unit time each arrival is independent P t 1 e t 0 0 5 1 Av t Analysis of Queueing Behavior Probability 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 Exit Start ARRIVAL RATE SERVICE RATE Time Slice SERVICE RATE 1 ARRIVAL RATE 1 Event Queue Useful Facts From Queuing Theory Wq mean time a customer spends in the queue arrival rate Lq Wq number of customers in queue W mean time a customer spends in the system L W Little s theorem number of customers in the system In words average length of queue is arrival rate times average waiting time Analysis of Single Server Queue Server Utilization Time in System W 1 Time in Queue Wq Number in Queue Little Lq 2 1 Poisson Arrival Service Rates Sum ARRIVAL RATE 1 Server Input Queue ARRIVAL RATE 2 1 2 SERVICE RATE


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

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 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?