DOC PREVIEW
U of I CS 241 - Synchronization Problems

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 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 33 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 33 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 33 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 33 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 33 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 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS241 Systems Programming Synchronization ProblemsCS241 AdministrativeThis lectureProducer ConsumerProducer-ConsumerProducer-Consumer ProblemChallenge?ChallengeBuffer underflowBuffer overflowMutual ExclusionWhat could possibly go wrong?Slide 13Other edge casesImplementation?2 Counting Semaphores and a mutexAssembling the solutionPseudocode getItem()Pseudocode putItem(data)Analysis#1 What's the precise problem?Deadlock e.g Consumer waits for producer to insert a new item but Producer is waiting for Consumer to release mutexAnalysis#2Buffer overflow when reader removes item from a full buffer: Producer inserts item too earlyOther considerationsDining PhilosophersHistoryDining Philosopher ChallengeSeems simple enough …?… Deadlock (Each P. holds left fork)What if?Slide 31Formal requirements for deadlockSlide 33CS 241 Spring 2007System Programming 01/13/19 CS241 © 2006,2007 LA, RHC and YZ, All Rights Reserved1CS241 Systems ProgrammingSynchronization ProblemsLawrence Angrave2CS241 AdministrativeThis weekHW due FridayNext weekMidterm Monday in class3This lectureGoals:Introduce classic synchronization problemsTopicsProducer-ConsumerDining Philosophers4Producer ConsumerProblem occurs in system & application programminge.g. Web Server dispatches incoming web requests to a waiting process(es)e.g. GUI events from keyboard,& mouse are queued by O/S and consumed by applications.Pipelines (Hardware & software examples)5Producer-ConsumerinsertPtrremovePtr6Producer-Consumer ProblemProducers insert items Consumers remove itemsShared bounded buffer ** Efficient implementation is a circular buffer with an insert and a removal pointer.7Challenge?What the abstract requirements that our solution must satisfy?8ChallengePrevent buffer overflowPrevent buffer underflowProper synchronizationMutual ExclusionProgressBounded waiti.e. Prevent deadlock9Buffer underflowImagine:Producer inserts an itemConsumer removes an itemConsumer removes another itemConclusions:Make sure consumer only retrieves valid items from the bufferConsumer should block (or return an error code) if there are no items available10Buffer overflowProducer inserts too many items and the buffer overflowsConclusion:Block Producer if the buffer is full11Mutual ExclusionProducer inserts items. Updates insertion pointer.Consumer executes destructive reads on the buffer. Update removal pointerBoth update information about how full/empty the buffer is. Solution should allow multiple readers/writers12What could possibly go wrong?Check the tricky "Edge cases"e.g. Producer is waiting(blocked) but the buffer is already full. Now Consumer reads an item.What could go wrong at this point?13What could possibly go wrong?Check the tricky "Edge cases"e.g. Producer is waiting(blocked) but the buffer is already full. Now Consumer calls remove()What could go wrong at this point?oConsumer cannot continue because Producer is in critical section => deadlockoProducer is never unblocked => deadlockoConsumer unblocks Producer too early. Failed mutual exclusion => corrupt data.oSuppose another consumer/producer arrives… will our implementation still work?14Other edge casesoTwo producers call insert() at the same timeoConsumer(s) is/are waiting on an empty buffer. Producer tries to insert one item.15Implementation?What do we need to prevent buffer underflow?What do we need to prevent buffer overflow?What do we need to protect updates to buffer?162 Counting Semaphores and a mutexCounting semaphore to count # items in bufferCounting semaphore to count # free slotsMutex to protect accesses to shared buffer & pointers.17Assembling the solutionsem_wait(slots), sem_post(slots)sem_wait(items), sem_post(items)mutex_lock(m) mutex_unlock(m)insertptr=(insertptr+1) % Nremovalptr=(removalptr+1) % NInitialize semaphore slots to size of bufferInitialize semaphore items to zero.18Pseudocode getItem()Error checking/EINTR handling not shownsem_wait(items)mutex_lock(mutex)result=buffer[ removePtr ];removePtr=(removePtr +1 ) % Nmutex_unlock(mutex)sem_post(slots)so what about insertItem()?19Pseudocode putItem(data)Error checking/EINTR handling not shownsem_wait(slots)mutex_lock(mutex)buffer[ insertPtr]= data;insertPtr=(insertPtr + 1 ) % Nmutex_unlock(mutex)sem_post(items)20Analysis#1 What's the precise problem?putItem(data) {mutex_lock(mutex)sem_wait(slots) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}Underflow?Overflow?getItem() {mutex_lock(mutex)sem_wait(items) result=buffer[ removePtr ]; removePtr=…sem_post(slots)mutex_unlock(mutex)}Deadlock? Failed Mut Excl?21Deadlock e.g Consumer waits for producer to insert a new item but Producer is waiting for Consumer to release mutexputItem(data) {mutex_lock(mutex) #2sem_wait(slots) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}getItem() {mutex_lock(mutex)sem_wait(items) BLOCKS #1 result=buffer[ removePtr ]; removePtr=…sem_post(slots)mutex_unlock(mutex)}22Analysis#2 putItem(data) {sem_wait(slots)mutex_lock(mutex) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}getItem() {sem_wait(items)sem_post(slots)mutex_lock(mutex) result=buffer[ removePtr ]; removePtr=…mutex_unlock(mutex)}23Buffer overflow when reader removes item from a full buffer: Producer inserts item too earlyputItem(data) {sem_wait(slots)mutex_lock(mutex) buffer[ insertPtr]= … insertPtr=…sem_post(items)mutex_unlock(mutex)}getItem() {sem_wait(items)sem_post(slots)mutex_lock(mutex) result=buffer[ removePtr ]; removePtr=…mutex_unlock(mutex)}24Other considerationsEarly cancelation using signals?Limited Production?(Possibly no items)… Consumers wait forever… Consumers quit too early? One implementation: Insert special end-value into queue which consumers read (but may not consume) Other reasonable implementations (condition variables;not covered in CS241)Priority of Consumers & Producers25Dining Philosophers26HistoryDijkstra 1971Originally set as a exam questionIllustrates Starvation, DeadlockTest shared resource allocation algorithmsSee Stallings Ch.6.6 p.27627Dining Philosopher Challenge{ Think | Eat }N Philosophers circular table with N chopsticksTo eat the Philosopher must first pickup two chopsticksith Philosopher needs ith & i+1th chopstickOnly put down chopstick when Philosopher has finished eatingDevise a solution which satisfies mutual exclusion but avoids starvation and deadlock28Seems simple enough …?while(true) { think()


View Full Document

U of I CS 241 - Synchronization Problems

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