CPSC-410/611 Operating Systems Process Synchronization 1Process Management: Synchronization• Why? Examples• What? The Critical Section Problem• How? Software solutions• Hardware-supported solutions• The basic synchronization mechanism:Semaphores• More sophisticated synchronizationmechanisms: Monitors, Message Passing• Classical synchronization problemsProcess Management: Synchronization• Why? Examples• What? The Critical Section Problem• How? Software solutions• Hardware-supported solutions• The basic synchronization mechanism:Semaphores• More sophisticated synchronizationmechanisms: Monitors, Message Passing• Classical synchronization problemsCPSC-410/611 Operating Systems Process Synchronization 2The Critical Section Problem: Example 1char in; /* shared variables */char out;void echo() { input(in, keyboard); out := in; output(out, display);} Process 1 Process 2 Operation: Echo() Echo() Interleaved execution ﾉ input(in,keyboard) out = in; ﾉ ﾉ ﾉ output(out,display) ﾉ ﾉ ﾉ input(in,keyboard); out = in; output(out,display); ﾉ Race condition !The Critical Section Problem: Example 2Producer-consumer with bounded, shared-memory, buffer.Consumer:Item * remove() { while (counter == 0) no_op; next = buffer[out]; out = (out+1) MOD n; counter = counter - 1; return next;}outinProducer:void deposit(Item * next) { while (counter == n) no_op; buffer[in] = next; in = (in+1) MOD n; counter = counter + 1;}circular buffer of size nint in, out;Item buffer[n];int counter;CPSC-410/611 Operating Systems Process Synchronization 3This Implementation is not Correct!Producercounter = counter + 1reg1 = counterreg1 = reg1 + 1counter = reg1reg1 = counterreg1 = reg1 + 1counter = reg1Consumercounter = counter - 1reg2 = counterreg2 = reg2 - 1counter = reg2reg2 = counterreg2 = reg2 - 1counter = reg2operation:on CPU:interleavedexecution:• Race condition!• Need to ensure that only one process can manipulate variable counter at atime : synchronization.prevprevprevprev prevprevprev prevprevprev prevprevprev prevprevCritical Section Problem: Example 3Insertion of an element into a list.void insert(new, curr) { /*1*/ new.next = curr.next; /*2*/ new.prev = c.next.prev; /*3*/ curr.next = new; /*4*/ new.next.prev = new;}nextnext nextnewcurrnextnext nextnewcurrnextnext nextnewcurrnextnext nextnewcurrnextnext nextnewcurr1.2.3.4.CPSC-410/611 Operating Systems Process Synchronization 4Interleaved Execution causes Errors!new1.next = curr.next;new1.prev = c.next.prev;…………curr.next = new1;new.next.prev = new1;Process 1……new2.next = curr.next;new2.prev = c.next.prev;curr.next = new2;new.next.prev = new2;……Process 2prevprev prevnextnext nextnew1currprevnextnew2• Must guarantee mutually exclusive access to list data structure!Process Management: Synchronization• Why? Examples• What? The Critical Section Problem• How? Software solutions• Hardware-supported solutions• The basic synchronization mechanism:Semaphores• More sophisticated synchronizationmechanisms: Monitors, Message Passing• Classical synchronization problemsCPSC-410/611 Operating Systems Process Synchronization 5Critical Sections• Execution of critical section by processes must be mutuallyexclusive.• Typically due to manipulation of shared variables.• Need protocol to enforce mutual exclusion.while (TRUE) { enter section; critical section; exit section; remainder section;}Criteria for a Solution of the C.S. Problem1. Only one process at a time can enter the critical section.2. A process that halts in non-critical section cannot prevent otherprocesses from entering the critical section.3. A process requesting to enter a critical section should not bedelayed indefinitely.4. When no process is in a critical section, any process thatrequests to enter the critical section should be permitted toenter without delay.5. Make no assumptions about the relative speed of processors (ortheir number).6. A process remains within a critical section for a finite time only.CPSC-410/611 Operating Systems Process Synchronization 6A (Wrong) Solution to the C.S. Problem• Two processes P0 and P1• int turn; /* turn == i : Pi is allowed to enter c.s. */Pi: while (TRUE) { while (turn != i) no_op; critical section; turn = j; remainder section; }Another Wrong Solutionbool flag[2]; /* initialize to FALSE *//* flag[i] == TRUE : Pi intends to enter c.s.*/Pi: while (TRUE) { while (flag[j]) no_op; flag[i] = TRUE; critical section; flag[i] = FALSE; remainder section; }CPSC-410/611 Operating Systems Process Synchronization 7Yet Another Wrong Solutionbool flag[2]; /* initialize to FALSE *//* flag[i] == TRUE : Pi intends to enter c.s.*/while (TRUE) { flag[i] = TRUE; while (flag[j]) no_op; critical section; flag[i] = FALSE; remainder section;}A Combined Solution (Petersen)int turn;bool flag[2]; /* initialize to FALSE */while (TRUE) { flag[i] = TRUE; turn = j; while (flag[j]) && (turn == j) no_op; critical section; flag[i] = FALSE; remainder section;}CPSC-410/611 Operating Systems Process Synchronization 8Process Management: Synchronization• Why? Examples• What? The Critical Section Problem• How? Software solutions• Hardware-supported solutions• The basic synchronization mechanism:Semaphores• More sophisticated synchronizationmechanisms: Monitors, Message Passing• Classical synchronization problemsHardware Support For Synchronization• Disallow interrupts– simplicity– widely used– problem: interrupt service latency– problem: what about multiprocessors?• Atomic operations:– Operations that check and modify memory areas ina single step (i.e. operation can not be interrupted)– Test-And-Set– Exchange, Swap, Compare-And-SwapCPSC-410/611 Operating Systems Process Synchronization 9Test-And-Setbool TestAndSet(bool & var) { bool temp; temp = var; var = TRUE; return temp;}bool lock; /* init to FALSE */while (TRUE) { while (TestAndSet(lock)) no_op; critical section; lock = FALSE; remainder section;}atomic!Mutual Exclusion withTest-And-SetExchange (Swap)void Exchange(bool & a, bool & b){ bool temp; temp = a; a = b; b = temp;}bool lock; /*init to FALSE */while (TRUE) { dummy = TRUE; do Exchange(lock, dummy); while(dummy); critical section; lock = FALSE; remainder section;}atomic!Mutual Exclusion withExchangeCPSC-410/611 Operating Systems Process Synchronization 10Process Management: Synchronization• Why? Examples• What?