DOC PREVIEW
U of I CS 241 - Synchronization

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

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

Unformatted text preview:

SynchronizationContentsInterprocess Communication Race ConditionsCritical Regions (1)Critical Regions (2)RequirementsSolution HistoryTurn Mutual ExclusionSlide 9Other Flag Mutual ExclusionSlide 112 Flag Mutual ExclusionSlide 13Slide 142 Flag and Turn Mutual ExclusionSlide 16DiscussionHardware SolutionsSlide 19Slide 20Test and Set SolutionSwapA Lock Class that uses Test And SetLock Class DefnSemaphoreSlide 26Busy Wait Semaphore ClassSlide 28Slide 29Example Semaphore Critical Section for N ProcessesBusy Wait SemaphoreSlide 32Busy Wait Semaphore IssuesSlide 34Slide 35Slide 36Blocking SemaphoreBlocking Semaphore P()Wakeup Semaphore V()P,V Critical Section SchemesSlide 41Summary01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved1SynchronizationCS 241 Lecture 7(T: Chapter 2 pp 100-114)Andrew Bennett01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved2ContentsSoftware SynchronizationHardware SynchronizationA Lock Class SemaphoresReduced Busy Waiting01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved3Interprocess CommunicationRace ConditionsTwo processes want to access shared memory at same time01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved4Critical Regions (1)Four conditions to provide mutual exclusion1. No two processes simultaneously in critical region2. No assumptions made about speeds or numbers of CPUs3. No process running outside its critical region may block another process4. No process must wait forever to enter its critical region01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved5Critical Regions (2)Mutual exclusion using critical regions01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved6RequirementsMutual ExclusionProgressBounded WaitNo Blocking Forever01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved7 Solution HistoryApproaches:1. Turn Mutual Exclusion2. Other Flag Mutual Exclusion3. Two Flag Mutual Exclusion4. Two Flag and Turn Mutual Exclusion01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved8Turn Mutual ExclusionProcess; /* For two processes */{ while (true) { while ( turn != my_process_id) { }; Access shared variables; // Critical Section; turn = other_process_id; Do other work } }mutual exclusion a) yes, b) noWhat Properties does this satisfy?01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved9Turn Mutual ExclusionProcess; /* For two processes */{ while (true) { while ( turn != my_process_id) { }; Access shared variables; // Critical Section; turn = other_process_id; Do other work } }Progress: a) yes, b) noWhat Properties does this satisfy?01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved10Other Flag Mutual Exclusionint owner[2] = {false, false};Process Me;{ while (true) { while (owner[other_process_id] ) { }; owner[my_process_id] = true; Access shared variables; // Critical Section; owner[my_process_id] = false; Do other work } }mutual exclusion? a) yes, b) no What Properties does this satisfy?01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved11Other Flag Mutual Exclusionint owner[2] = {false, false};Process Me;{ while (true) { while (owner[other_process_id] ) { }; owner[my_process_id] = true; Access shared variables; // Critical Section; owner[my_process_id] = false; Do other work } }Progress? a) yes, b) no What Properties does this satisfy?01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved122 Flag Mutual Exclusionint owner[2]= {false, false};Process Me; { while (true) { owner[my_process_id] = true; while (owner[other_process_id] ) { }; Access shared variables; // Critical Section; owner[my_process_id] = false; Do other work } }What Properties does this satisfy?Mutual exclusion a) yes, b) no01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved132 Flag Mutual Exclusionint owner[2]= {false, false};Process Me; { while (true) { owner[my_process_id] = true; while (owner[other_process_id] ) { }; Access shared variables; // Critical Section; owner[my_process_id] = false; Do other work } }What Properties does this satisfy?Progress a) yes, b) no01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved142 Flag Mutual Exclusionint owner[2]= {false, false};Process Me; { while (true) { owner[my_process_id] = true; while (owner[other_process_id] ) { }; Access shared variables; // Critical Section; owner[my_process_id] = false; Do other work } }What Properties does this satisfy?Blocking a) yes, b no01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved152 Flag and Turn Mutual Exclusion int owner[2]={false, false}; int turn;Process Me; { while (true) { owner[my_process_id] = true; turn = other_process_id; while (owner[other_process_id] and turn == other_process_id ) { }; Access shared variables; // Critical Section; owner[my_process_id] = false; Do other work } } Is this ok?Is this ok?a) yes, b) noa) yes, b) no01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved162 Flag and Turn Mutual Exclusion int owner[2]={false, false}; int turn;Process Me; { while (true) { owner[my_process_id] = true; turn = other_process_id; while (owner[other_process_id] and turn == other_process_id ) { }; Access shared variables; // Critical Section; owner[my_process_id] = false; Do other work } } Yeah!!!Yeah!!!01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved17DiscussionWhat hardware features would help implement synchronization?01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved18Hardware SolutionsThe earlier mutual exclusion examples depend on the memory hardware having a read/write cycleIf multiple reads and writes could occur to the same memory location at the same time, they would not work01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved19Hardware SolutionsProcessors with caches but no cache coherency cannot use the solutions provided01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved20Hardware SolutionsIn general, it is IMPOSSIBLE to build mutual exclusion without a primitive that provides some form of mutual exclusion.What is the most convenient form of primitive that can be built in hardware?01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved21Test and Set Solutionchar Test_and_Set ( char* target);\\ All done atomically{ char temp = *target; *target = true; return(temp)}01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved22SwapAn


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?