DOC PREVIEW
U of I CS 241 - Synchronization

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

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

Unformatted text preview:

SynchronizationCS241 AdministrativeThis lectureProducer-ConsumerSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Producer-Consumer ProblemSlide 27ChallengeSolutionAssembling the solutionPseudocode getItem()Pseudocode putItem(data)Dining PhilosophersDining Philosopher ChallengeSeems simple enough …?What if?Slide 37Formal Requirements for DeadlockSlide 39Define the Input and Output of the FollowingCopyright ©: Nahrstedt, Angrave, Abdelzaher 1SynchronizationCopyright ©: Nahrstedt, Angrave, Abdelzaher2CS241 AdministrativeThis weekSMP4 is due todayHW1 will be out next (practice for midterm)Copyright ©: Nahrstedt, Angrave, Abdelzaher3This lectureGoals:Introduce classic synchronization problemsTopicsProducer-ConsumerDining PhilosophersCopyright ©: Nahrstedt, Angrave, Abdelzaher4Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher5Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher6Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher7Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher8Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher9Producer-ConsumerCopyright ©: Nahrstedt, Angrave, Abdelzaher10Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher11Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher12Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher13Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher14Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher15Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher16Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher17Producer-ConsumerinsertPtrremovePtrBUFFER FULL: Producer must be blocked!Copyright ©: Nahrstedt, Angrave, Abdelzaher18Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher19Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher20Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher21Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher22Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher23Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher24Producer-ConsumerinsertPtrremovePtrCopyright ©: Nahrstedt, Angrave, Abdelzaher25Producer-ConsumerinsertPtrremovePtrBUFFER EMPTY: Consumer must be blocked!Copyright ©: Nahrstedt, Angrave, Abdelzaher26Producer-Consumer ProblemProducers insert items Consumers remove itemsShared bounded buffer ** Efficient implementation is a circular buffer with an insert and a removal pointer.Copyright ©: Nahrstedt, Angrave, Abdelzaher27Producer-Consumer ProblemProducer inserts items. Updates insertion pointer.Consumer executes destructive reads on the buffer. Updates removal pointerBoth update information about how full/empty the buffer is. Solution should allow multiple readers/writersCopyright ©: Nahrstedt, Angrave, Abdelzaher28ChallengePrevent buffer overflowPrevent buffer underflowProper synchronizationCopyright ©: Nahrstedt, Angrave, Abdelzaher29SolutionPrevent overflow: block producer when full! Counting semaphore to count #free slots 0  block producerPrevent underflow: block consumer when empty!Counting semaphore to count #items in buffer 0  block consumerMutex to protect accesses to shared buffer & pointers.Copyright ©: Nahrstedt, Angrave, Abdelzaher30Assembling the solutionsem_wait(slots), sem_post(slots)sem_wait(items), sem_post(items)mutex_lock(m) mutex_unlock(m)insertptr=(insertptr+1) % Nremovalptr=(removalptr+1) % NInitialize semaphore slots to size of bufferInitialize semaphore items to zero.Copyright ©: Nahrstedt, Angrave, Abdelzaher31Pseudocode getItem()Error checking/EINTR handling not shownsem_wait(items)mutex_lock(mutex)result=buffer[ removePtr ];removePtr=(removePtr +1 ) % Nmutex_unlock(mutex)sem_post(slots)Copyright ©: Nahrstedt, Angrave, Abdelzaher32Pseudocode 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)Copyright ©: Nahrstedt, Angrave, Abdelzaher33Dining PhilosophersCopyright ©: Nahrstedt, Angrave, Abdelzaher34Dining 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 deadlockCopyright ©: Nahrstedt, Angrave, Abdelzaher35Seems simple enough …?while(true) {think()lock(chopstick[i])lock(chopstick[(i+1) % N])eat()unlock(chopstick[(i+1) % N])unlock(chopstick[i])}Copyright ©: Nahrstedt, Angrave, Abdelzaher36What if?Made picking up left and right chopsticks an atomic operation?or,N-1 Philosophers but N chopsticks?Copyright ©: Nahrstedt, Angrave, Abdelzaher37What if?Made picking up left and right chopsticks an atomic operation?or,N-1 Philosophers but N chopsticks?… both changes prevent deadlock.Copyright ©: Nahrstedt, Angrave, Abdelzaher38Formal Requirements for DeadlockMutual exclusionHold and wait conditionNo preemption conditionCircular wait conditionOriginal scenario & our proposed ritual had all four of these properties.Copyright ©: Nahrstedt, Angrave, Abdelzaher39Formal 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 chopstickCopyright ©: Nahrstedt, Angrave, Abdelzaher40Define the Input and Output of the


View Full Document

U of I CS 241 - Synchronization

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