Synchronization

1 .Steve’s Concurrency Slides

2 .What is Synchronization? Ability of Two or More Serial Processes to Interact During Their Execution to Achieve Common Goal Recognition that “Today’s” Applications Require Multiple Interacting Processes Client/Server and Multi-Tiered Architectures Inter-Process Communication via TCP/IP Fundamental Concern: Address Concurrency Control Access to Shared Information Historically Supported in Database Systems Currently Available in Many Programming Languages

3 .Thread Synchronization Suppose X and Y are Concurrently Executing in Same Address Space What are Possibilities? X Y 1 2 3 What Does Behavior at Left Represent? Synchronous Execution! X Does First Part of Task Y Next Part Depends on X X Third Part Depends on Y Threads Must Coordinate Execution of Their Effort

4 .Thread Synchronization Will Second Part Still Finish After Third Part? Will Second Part Now Finish Before Third Part? What Happens if Variables are Shared? X Y 1 2 3 Now, What Does Behavior at Left Represent? Asynchronous Execution! X Does First Part of Task Y Does Second Part Concurrent with … X Doing Third Part What are Issues?

5 .What are Potential Problems without Synchronization? Data Inconsistency Lost-Update Problem Impact on Correctness of Executing Software Deadlock Two Processes Each Hold Unique Resource and Want Resource of Other Process Processes Wait Forever Non-Determinacy of Computations Behavior of Computation Different for Different Executions Two Process Produce Different Results When Executed More than Once on Same Data

6 .What are Classic Synchronization Techniques? Goal: Shared Variables and Resources Two Approaches: Critical Sections Define a Segment of Code as Critical Section Once Execution Enters Code Segment it Cannot be Interrupted by Scheduler Release Point for Critical Section for Interrupts Semaphores Proposed in 1960s by E. Dijkstra Utilizes ADTs to Design and Implement Behavior that Guarantees Consistency and Non-Deadlock

7 .shared float balance; Code for p 1 Code for p 2 . . . . . . balance = balance + amount; balance = balance - amount; . . . . . . p 1 p 2 balance Critical Sections Two Processes Share “balance” Data Item Remember, Assignment is Not Atomic, but May Correspond to Multiple Assembly Instructions What is Potential Problem?

8 .shared double balance; Code for p 1 Code for p 2 . . . . . . balance = balance + amount; balance = balance - amount; . . . . . . Critical Sections Recall the Code Below What Happens if Time Slice Expires at Arrow and an Interrupt is Generated? Code for p 1 Code for p 2 load R1, balance load R1, balance load R2, amount load R2, amount add R1, R2 sub R1, R2 store R1, balance store R1, balance

9 .Critical Sections (continued) There is a Race to Execute Critical Sections Sections May Be Different Code in Different Processes: Cannot Detect With Static Analysis Results of Multiple Execution Are Not Determinate Need an OS Mechanism to Resolve Races If p 1 Wins, R1 and R2 Added to Balance - Okay If p 2 Wins, its Changed Balance Different from One Held by p 1 which Adds/Writes Wrong Value Code for p 1 Code for p 2 load R1, balance load R1, balance load R2, amount load R2, amount add R1, R2 sub R1, R2 store R1, balance store R1, balance

10 .shared double balance; Code for p 1 Code for p 2 disableInterrupts(); disableInterrupts(); balance = balance + amount; balance = balance - amount; enableInterrupts(); enableInterrupts(); One Solution: Disabling Interrupts In Code Below, Disable Interrupts What are Potential Problems? Interrupts Could Be Disabled Arbitrarily Long Were Trusting Software Engineers Unintentional(Infinite Loop) or Malicious Code Concurrent PLs Enforce Primitives at Compile Really Only Want to Prevent P 1 and P 2 From Interfering With One Another Another Solution: Using Shared “Lock” Variable

11 .shared boolean lock = FALSE; shared double balance; Code for p 1 /* Acquire the lock */ while( lock ) ; lock = TRUE; /* Execute critical sect */ balance = balance + amount; /* Release lock */ lock = FALSE; Code for p 2 /* Acquire the lock */ while( lock ) ; lock = TRUE; /* Execute critical sect */ balance = balance + amount; /* Release lock */ lock = FALSE; Using a Lock Variable Shared lock Flag Initialized to False First Process to be Active Sets lock to TRUE Enter Critical Section Change balance Set lock to FALSE Leave Critical Section Where are Two Trouble Spots? What if Interrupt Occurs Here? What if Interrupt Occurs Here?

12 .p 1 p 2 Blocked at while lock = TRUE lock = FALSE Interrupt Interrupt Interrupt Using a Lock Variable shared boolean lock = FALSE; shared double balance; Code for p 1 /* Acquire the lock */ while( lock ) ; lock = TRUE; /* Execute critical sect */ balance = balance + amount; /* Release lock */ lock = FALSE; Code for p 2 /* Acquire the lock */ while( lock ) ; lock = TRUE; /* Execute critical sect */ balance = balance + amount; /* Release lock */ lock = FALSE;

13 .enter(lock) { exit(lock) { disableInterrupts(); disableInterrupts(); /* Loop until lock is TRUE */ lock = FALSE; while(lock) { enableInterrupts(); /* Let interrupts occur */ } enableInterrupts(); disableInterrupts(); } lock = TRUE; enableInterrupts(); } Lock Manipulation Consider the Following enter/exit Primitives that Will be Utilized to Insure No Interrupts During How Does Code Below Insure that Interrupts are Disabled? What Occurs Here? Remember, Need Location for Interrupts to Occur During Attempt to Acquire Lock!

14 .Utilizing Enter and Exit Example: List Manipulator Add or Delete an Element From a List Adjust the List Descriptor, e.g., Length Modify List Content and Length A Transaction is a List of Operations The System Begins to Execute a Transaction Execution Must Occur on All Operations that Comprise Transaction Without Interruption Or, the Transaction Must Not Execute Any Operations at All Concept of Atomic Transaction

15 .shared boolean lock2 = FALSE;lock1 = FALSE; shared list L; Code for p 1 Code for p 2 . . . . . . /* Enter CS to delete elt */ /* Enter CS to update len */ enter( lock1 ); enter( lock2 ); <delete element>; <update length>; /* Exit CS */ /* Exit CS */ exit( lock1 ); exit( lock2 ); <intermediate computation>; <intermediate computation> /* Enter CS to update len */ /* Enter CS to add elt */ enter( lock2 ); enter( lock1 ); <update length>; <add element>; /* Exit CS */ /* Exit CS */ exit( lock2 ); exit( lock1 ); . . . . . . Processing Two Transactions Notice Any Problems with Code for Processes? Interrupt of p 1 After Delete But Before Update If p 2 Adds Element and Updates Length, Inconsistency Occurs

16 .shared boolean lock1 = FALSE; lock2 = FALSE;shared list L; Code for p 1 Code for p 2 . . . . . . /* Enter CS to delete elt */ /* Enter CS to upd len */ enter( lock1 ); enter( lock2 ); <delete element>; <update length>; <intermediate computation>; <intermediate comp> /* Enter CS to update len */ /* Enter CS to add elt */ enter( lock2 ); enter( lock1 ); <update length>; <add element>; /* Exit both CS */ /* Exit both CS */ exit( lock1 ); exit( lock2 ); exit( lock2 ); exit( lock1 ); . . . . . . Deadlock Why and How Does Deadlock Occur?

17 .Coordinating Processes Can Synchronize With FORK, JOIN & QUIT Terminate Processes With QUIT to Synchronize Create Processes Whenever Critical Section is Complete See Figure 8.7 Problems with All Approaches so Far Reliance on Software Engineers Error Prone and Difficult to Enforce Alternative is to Create OS Primitives Similar to the enter/exit Primitives

18 .Some Constraints for “Ideal” Synchronization Mechanism Processes will Enter Critical Sections Mutual Exclusion: Only One Process at any One Time in Allowed in the CS Only Processes Competing for a CS are Involved in Resolving Who Enters the CS Once a Process Attempts to Enter its CS, it Cannot be Postponed Indefinitely After Requesting Entry, Only a Bounded Number of Other Processes May Enter Before the Requesting Process Latter Two Points Prevent Starvation!

19 .Assumptions About Solutions Memory Read/Writes Are Indivisible Process A Reads X; Process B Writes X Either A Reads X ; B Writes X B Writes X ; A Reads X Simultaneous Attempts Result in Some Arbitrary Order of Access There is No Priority Among the Processes Relative Speeds of the Processes/Processors is Unknown Processes Are Cyclic and Sequential

20 .Classic Paper Describes Several Software Attempts to Solve the Problem (See Exercise 4, Section 8.6) Dijkstra First Found a Software Solution Then Proposed Simpler Hardware-Based Solution What is a Semaphore S? A Nonnegative Integer Variable Can Only Be Changed or Tested by Two Indivisible Functions: For V(s) , No Interrupt is Possible For P(s) , Interrupt During {wait}; Only V(s): [s = s + 1] P(s): [while(s == 0){ wait }; s = s - 1] Dijkstra Semaphore

21 .What is the Initial Value of Binary Semaphore? Initial Value Set as Part of Shared Variable semaphore mutex = 1; Followed by Spawning of Two or More Processes What Does it Mean When mutex = 0 ? Process X Executed P(mutex) with mutex = 1 What About Other Processes Trying P(mutex) ? Others Wait Until Process X Does V(mutex) If X is Interrupt Before V , Others Still Wait V(mutex): [mutex = mutex + 1] P(mutex): [while(mutex == 0){ wait }; mutex = mutex - 1] How Do P & V Work?

22 .Using Semaphores to Solve the Canonical Problem proc_0() { proc_1() { while(TRUE) { while(TRUE { <compute section>; <compute section>; P( mutex ); P( mutex ); <critical section>; <critical section>; V( mutex ); V( mutex ); } } } } semaphore mutex = 1; // Shared variable fork(proc_0, 0); fork(proc_1, 0); V(s):[s = s + 1] P(s):[while(s==0) { wait }; s = s - 1] What if First P( mutex ); Called by proc_0 ? s = 1 while false so s = 0 What if Interrupt Occurs in CS of proc_0 ? proc_1() Waits Until proc_0 Resumes When CS Finishes V is Fired to Set s = 1

23 .Shared Account Problem proc_0() { proc_1() { . . . . . . /* Enter the CS */ /* Enter the CS */ P( mutex ); P( mutex ); balance += amount; balance -= amount; V( mutex ); V( mutex ); . . . . . . } } semaphore mutex = 1; // Shared variable fork(proc_0, 0); fork(proc_1, 0); V(s):[s = s + 1] P(s):[while(s==0) { wait }; s = s - 1] Assume Following Values: balance = 200 amount = 50 amount = 75 What are Possible Results? Is there a Lost Update?

24 .proc_0() { proc_1() { . . . . . . /* Enter the CS */ /* Enter the CS */ P( mutex ); P( mutex ); balance += amount; balance -= amount; V( mutex ); V( mutex ); . . . . . . } } V(s):[s = s + 1] P(s):[while(s==0) { wait };s=s-1] balance = 200 amount = 50 amount = 75 proc_0 Executes P First If proc_0 Interrupted Waits proc_1 Eventually proc_0 Resumes balance = 250 proc_0 Executes V proc_1 Executes P Sets balance = 175 proc_1 Executes V proc_1 Executes P First If proc_1 Interrupted proc_0 Waits Eventually proc_1 Resumes balance = 125 proc_1 Executes V proc_0 Executes P Sets balance = 175 proc_0 Executes V

25 .Two Shared Variables proc_A() { while(TRUE) { <compute section A1>; update( x ); /* Signal proc_B */ V( s1 ); <compute section A2>; /* Wait for proc_B */ P( s2 ); retrieve( y ); } } semaphore s1 = 0; semaphore s2 = 0; fork(proc_A, 0); fork(proc_B, 0); proc_B() { while(TRUE) { /* Wait for proc_A */ P( s1 ); retrieve( x ); <compute section B1>; update( y ); /* Signal proc_A */ V( s2 ); <compute section B2>; } } What is Execution Process That Guarantees x and y are Read After They’re Written?

26 .Execution Process Two Shared Variables proc_A() { while(TRUE) { <compute section A1>; update( x ); /* Signal proc_B */ V( s1 ); <compute section A2>; /* Wait for proc_B */ P( s2 ); retrieve( y ); } } proc_B() { while(TRUE) { /* Wait for proc_A */ P( s1 ); retrieve( x ); <compute section B1>; update( y ); /* Signal proc_A */ V( s2 ); <compute section B2>; } } integer x,y; semaphore s1=0; semaphore s2=0; P(s1) will not Execute Until V(s1) sets s1 to 1 x Written Before Read P(s2) will not Execute Until V(s2) sets s2 to 1 y Written Before Read Doesn’t Matter if Interrupt Occurs Anywhere Read of Written Data Only After Semaphore Secured

27 .Bounded Buffer Producer Consumer Empty Pool Full Pool Producer/Consumer Model Processes Communicate by Producer Obtains Empty Buffer fr. Pool Producer Fills Buffer & Places in Full Pool Consumer Obtains Info. By Picking Buffer fr. Full Pool Consumer Copies Info Out of Buffer Consumer Places Buffer in Empty Pool N Fixed Number of Buffers Utilize Counting/Binary Semaphores

28 .Bounded Buffer producer() { buf_type *next, *here; while(TRUE) { produce_item(next); /* Claim an empty */ P( empty ); P( mutex ); here = obtain( empty ); V( mutex ); copy_buffer(next, here); P( mutex ); release(here, fullPool ); V( mutex ); /* Signal a full buffer */ V( full ); } } semaphore mutex = 1; /* A binary semaphore */ semaphore full = 0; /* A general (counting) semaphore */ semaphore empty = N; /* A general (counting) semaphore */ buf_type buffer[N]; fork(producer, 0); fork(consumer, 0); consumer() { buf_type *next, *here; while(TRUE) { /* Claim full buffer */ P( full ); P( mutex ); here = obtain( full ); V( mutex ); copy_buffer(here, next); P( mutex ); release(here, emptyPool ); V( mutex ); /* Signal an empty buffer */ V( empty ); consume_item(next); } }

29 .Execution Process Bounded Buffer producer() { buf_type *next, *here; while(TRUE) { produce_item(next); /* Claim an empty */ P( empty ); P( mutex ); here = obtain( empty ); V( mutex ); copy_buffer(next, here); P( mutex ); release(here, fullPool ); V( mutex ); /* Signal a full buffer */ V( full ); } } consumer() { buf_type *next, *here; while(TRUE) { /* Claim full buffer */ P( full ); P( mutex ); here = obtain( full ); V( mutex ); copy_buffer(here, next); P( mutex ); release(here, emptyPool ); V( mutex ); /* Signal an empty buffer */ V( empty ); consume_item(next); } } semaphore mutex = 1; semaphore full = 0; semaphore empty = N; buf_type buffer[N]; Producers Want Empty Buffers Consumers Want Full Buffers Distinct Empty Buffer Goes to Only 1 Producer Protect Changes to Full Pool Only One Process Accesses Full Pool Protect Changes to Empty Pool Full Buffer Now Available Empty Buffer Now Available