Introduction to SynchronizationCS241 AdministrativeOverviewInter-Process Communication (IPC)Spooling Example: CorrectSpooling Example: Data RacesCritical Region (Critical Section)Critical Region Requirements Critical Region Requirements 1 of 2 Critical Region Requirements Critical Regions (2)Mutual Exclusion With Busy WaitingLock VariablesTurn-based Mutual Exclusion with strict alternationTurn-based Mutual Exclusion with strict alternationTurn-based Mutual Exclusion with strict alternationTurn-based Mutual Exclusion with strict alternation Other Flag Mutual ExclusionOther Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag Mutual Exclusion2 Flag and Turn Mutual Exclusion2 Flag and Turn Mutual ExclusionDiscussionDiscussionSummaryCS 241 Spring 2007System Programming09/14/06 CS241 © 2006 RHC and YZ, All Rights Reserved1Introduction to SynchronizationKlara NahrstedtLecture 102/7/072CS241 AdministrativeThis week SMP2, Deadline Monday 9am, 2/12/07 Regular Quiz 3 on Friday, 2/9/07Reminder:Read Stallings Chapter 5 and R & R Chapter 13 and 143OverviewIntroduction to synchronizationWhy do we need synchronization?What is a data race?Critical region, mutual exclusion, progress, bounded waiting4Inter-Process Communication (IPC)IPC needed in multiprogramming – management of multiple processes within a uni-processor systemmultiprocessing – management of multiple processes within a multi-processor systemPass information to each other via shared resource Mutual exclusion & SynchronizationProper sequencing5Spooling Example: CorrectShared memoryabcProg.cProg.n4567F2……outinProcess 1next_free = in;int next_free;Stores F1 into next_free;Process 2int next_free;next_free = inStores F2 into next_free;124in=next_free+1F1in=next_free+13566Spooling Example: Data RacesShared memoryabcProg.cProg.n4567……outinProcess 1next_free = in;int next_free;Stores F1 into next_free;Process 2int next_free;next_free = in/* value: 7 */Stores F2 into next_free;132in=next_free+1F1in=next_free+1456F27Critical Region (Critical Section)Process { while (true) { ENTER CRITICAL SECTIONAccess shared variables; // Critical Section; LEAVE CRITICAL SECTIONDo other work } }8Critical Region RequirementsMutual ExclusionProgressBounded WaitNo Speed and Number of CPU assumptions9Critical Region Requirements 1 of 2Mutual Exclusion: No other process must execute within the critical section while a process is in it. Progress: If no process is waiting in its critical section and several processes are trying to get into their critical section, then entry to the critical section cannot be postponed indefinitely.10Critical Region RequirementsMutual ExclusionProgressBounded Wait: A process requesting entry to a critical section should only have to wait for a bounded number of other processes to enter and leave the critical section. Speed and Number of CPUs: No assumption may be made about speeds or number of CPUs.11ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsGood concrete example...12ProgressMutual ExclusionBounded WaitOversimplifying Assumptionsvisual learning aid: ‘bmp’ in alphabetical order13ProgressMutual ExclusionBounded WaitOversimplifying Assumptions14ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsNo cutting in!15ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsAre there door locks?No cutting in!16ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsAre there door locks?We'll be first if we sprintNo cutting in!17ProgressMutual ExclusionBounded WaitOversimplifying AssumptionsAre there door locks?We'll be first if we sprintNo cutting in!Well, Did you see anybody go in?18Progress?Bounded Wait?What's the difference?19Progress?If no process is waiting in its critical section and several processes are trying to get into their critical section, then entry to the critical section cannot bepostponed indefinitely20Progress?If no process is waiting in its critical section and several processes are trying to get into their critical section, then entry to the critical section cannot be postponed indefinitelyBounded Wait?A process requesting entry to a critical section should only have to wait for a bounded number of other processes to enter and leave the critical section.21Critical Regions (2)Mutual exclusion using critical regions22Mutual Exclusion With Busy Waiting Possible Solutions Software-only candidate solutions (Two-Process Solutions) Lock Variables Turn Mutual Exclusion Other Flag Mutual Exclusion Two Flag Mutual Exclusion Two Flag and Turn Mutual Exclusion Hardware solutions Disabling Interrupts; Test-and-set; Swap (Exchange) Semaphores23Lock Variableswhile (lock) {/* spin spin spin spin */}lock = 1;/* EnterCriticalSection; */access shared variable;/* LeaveCriticalSection; */lock = 0;What's the problem?24Turn-based Mutual Exclusionwith strict alternationProcessMe/* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }25Turn-based Mutual Exclusionwith strict alternationSatisfies Mutual Exclusion?ProcessMe/* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }26Turn-based Mutual Exclusion with strict alternationSatisfies Bounded Waiting?ProcessMe/* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }27Turn-based Mutual Exclusion with strict alternationProcessMe /* For two processes */{while (true){ while ( turn != my_process_id) { }access shared variablesturn = other_process_iddo other work} }Satisfies Progress?z28Other Flag Mutual ExclusionProgress?int owner[2] = {false, false}ProcessMe{ while (true){ while (owner[other_process_id] ) { }owner[my_process_id] = trueaccess shared variablesowner[my_process_id] = falsedo other work} }29Other Flag Mutual ExclusionMutual exclusion?int owner[2] = {false, false}ProcessMe{ while (true){ while (owner[other_process_id] ) { }owner[my_process_id] = trueaccess shared variablesowner[my_process_id] = falsedo other work} }z302 Flag Mutual ExclusionMutual Exclusion? int owner[2]= {false, false}ProcessMe { while (true) {owner[my_process_id] = truewhile (owner[other_process_id] ) { }access shared variablesowner[my_process_id] = falsedo other work} }312 Flag Mutual Exclusionint owner[2]= {false, false}ProcessMe { while (true)
View Full Document