Unformatted text preview:

SynchronizationAnnouncementsFrom last time...SynchronizationCritical SectionCritical SectionCritical SectionDisabling InterruptsCritical SectionFirst Try at Lock ImplementationFirst Try at Lock ImplementationFirst Try at Lock ImplementationAtomic Lock ManipulationAtomic Lock ManipulationAtomic Lock ManipulationAtomic Lock ManipulationSemaphoresSemaphoresSemaphoresSemaphoresSemaphoresSemaphoresSynchronizationCSCI 3753 Operating SystemsSpring 2005Prof. Rick HanAnnouncements• HW #3 is coming, due Friday Feb. 25, a week+ from now• PA #2 is coming, assigned about next Tuesday• Midterm is tentatively scheduled for Thursday March 10• Read chapter 8From last time...• There are many cases where processes and threads want to access shared common variables, buffers, etc.• Example: Producer and Consumer processes with a shared bounded buffer in between– Producer increments counter++– Consumer decrements counter--• race conditions occur between producer and consumer– Machine-level instructions can be interleaved, resulting in unpredictable final value of shared counter variableSynchronization// counter++reg1 = counter;reg1 = reg1 + 1;counter = reg1;// counter--; reg2 = counter;reg2 = reg2 - 1;counter = reg2;(1) [5](3) [6](2) [5](4) [4](5) [6] (6) [4]• Suppose we have the following sequence of interleaving, where the brackets [value] denote the local value of counter in either the producer or consumer’s process. Let counter=5 initially.• At the end, counter = 4. But if steps (5) and (6) were reversed, then counter=6 !!!• Value of shared variable counter changes depending upon (an arbitrary) order of writes - very undesirable!Critical Section• Some kernel data structures could be subject to race conditions, e.g. access to list of open files• Kernel developer must ensure that no such race conditions occur• User or kernel developer identifies critical sections in code where each process accesses shared variables– access to critical sections is controlled by special entry and exit codewhile(1) {entry sectioncritical section (manipulate common var’s)exit sectionremainder code}Critical Section• Critical section access should satisfy multiple properties– mutual exclusion• if process Piis executing in its critical section, then no other processes can be executing in their critical sections– progress• if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision on which will enter its critical section next• this selection cannot be postponed indefinitely– bounded waiting• there exists a bound, or limit, on the number of times other processes can enter their critical sections after a process X has made a request to enter its critical section and before that request is granted• For most of the following slides, we will primarily be concerned with how to achieve mutual exclusionCritical Section• How do we protect access to critical sections?– want to prevent another process from executing while current process is modifying this variable - mutual exclusion– disable interrupts• before entering critical section, disable interrupts• after exiting critical section, reenable interrupts• This provides mutual exclusionDisabling Interruptsshared int counter;Code for p1Code for p2disableInterrupts(); disableInterrupts();counter++; counter--;enableInterrupts(); enableInterrupts();• Unfortunately, this approach to critical sections has many drawbacks:– Interrupts could be disabled arbitrarily long, e.g. the program may have an intentional or mistaken infinite loop while(1)– Interrupts can be disabled too long, e.g. if the critical section has many lines of code, then other process are blocked from executing until this process reenables interrupts• Really only want to prevent p1and p2from interfering with one another; this blocks all pi• overlapped I/O may be preventedCritical Section• Alternative: don’t disable interrupts for the entire time you’re in the critical section• Alternative Solution: Set a variable/flag called a lock to indicate that the critical section is busy, then unset the flag when critical section is done– doesn’t disable interrupts in the critical section– a process P can now be interrupted in the critical section, but if it is, P still has the lock, so no other process will be able to acquire the lock and execute its critical code (provided all processes properly surround critical sections with entry and exit code)First Try at Lock Implementationshared boolean lock = FALSE;shared int counter;Code for p1Code for p2/* Acquire the lock */ /* Acquire the lock */while(lock) ; while(lock) ;lock = TRUE; lock = TRUE;/* Execute critical sect */ /* Execute critical sect */counter++; counter--;/* Release lock */ /* Release lock */lock = FALSE; lock = FALSE;modified version of Pearson slidesFirst Try at Lock Implementationshared boolean lock = FALSE;shared int counter;Code for p1Code for p2/* Acquire the lock */ /* Acquire the lock */while(lock) ; while(lock) ;lock = TRUE; lock = TRUE;/* Execute critical sect */ /* Execute critical sect */counter++; counter--;/* Release lock */ /* Release lock */lock = FALSE; lock = FALSE;p1p2Blockedat whilelock = TRUElock = FALSEInterruptInterruptInterruptmodified version of Pearson slidesIf P1 is blocked onI/O and has thelock, then P2blocks as expected(P2 busy waits untilP1 unblocks its I/Oand releases the lock)First Try at Lock Implementationshared boolean lock = FALSE;shared double balance;Code for p1Code for p2/* Acquire the lock */ /* Acquire the lock */while(lock) ; while(lock) ;lock = TRUE; lock = TRUE;/* Execute critical sect */ /* Execute critical sect */counter++; counter--;/* Release lock */ /* Release lock */lock = FALSE; lock = FALSE;• This approach to protecting critical sections is unsafe, because it is subject to a race condition– If P1 is has just completed the test “while(lock)” and is just before the setting of “lock=TRUE”, P1 can get context switched out– Then P2 executes and sees lock=FALSE in its while(lock) test, and also drops through to the


View Full Document

CU-Boulder CSCI 3753 - Synchronization

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?