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 Reserved2ContentsSoftware SynchronizationHardware SynchronizationA Lock Class SemaphoresReduced 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 Reserved6RequirementsMutual ExclusionProgressBounded WaitNo 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 Reserved17DiscussionWhat hardware features would help implement synchronization?01/13/19 CS241 © 2005 Roy Campbell, All Rights Reserved18Hardware SolutionsThe earlier mutual exclusion examples depend on the memory hardware having a read/write cycleIf 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 SolutionsIn 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