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

73 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



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?