Concurrency: Mutual Exclusion and SynchronizationDefinitionsConventional solutions for MESoftware reservationProblems with concurrent executionAn exampleRace ConditionsThe critical section problemSlide 9Framework for analysis of solutionsRequirements for a valid solution to the critical section problemRequirements for a valid solution to the critical section problem (cont.)What about process failures?Types of solutionsDrawbacks of software solutionsHardware solutions: interrupt disablingHardware solutions: special machine instructionsThe test-and-set instructionThe test-and-set instruction (cont.)Using xchg for mutual exclusionMutual Exclusion Machine InstructionsSlide 22Spin-locks (busy waiting)Cache coherence effectSpinning vs blockingOS Solutions: SemaphoresSemaphoresSemaphore’s operationsSemaphores: observationsSlide 30Using semaphores for solving critical section problemsUsing semaphores to synchronize processesThe producer/consumer problemP/C: unbounded bufferSlide 35Slide 36Solution of P/C: unbounded bufferSlide 38P/C: finite circular buffer of size kSlide 40Solution of P/C: finite circular buffer of size kThe Dining Philosophers ProblemSlide 43Slide 44Binary semaphoresSlide 46Problems with semaphoresMonitorsMonitorSlide 50Condition variablesSlide 52Producer/Consumer problemMonitor for the bounded P/C problemMonitor for the bounded P/C problemMessage PassingSynchronization in message passingSlide 58Addressing in message passingEnforcing mutual exclusion with message passingThe bounded-buffer P/C problem with message passingSlide 62Kernel emulation of atomic operation on uniprocessorsTST emulation using RASUnix SVR4 concurrency mechanismsUnix PipesUnix MessagesShared memory in UnixUnix signalsUnix SemaphoresConcurrency: Mutual Exclusion and SynchronizationChapter 5Definitionscritical section: a section of code which reads/writes shared datarace condition: potential for interleaved execution of a critical section by multiple threads => results are non-deterministicmutual exclusion: synchronization mechanism to avoid race conditions by ensuring exclusive execution of critical sections deadlock: permanent blocking of threadsstarvation: execution but no progressConventional solutions for MEsoftware reservation: a thread must register its intent to enter CS and then wait until no other thread has registered a similar intention before proceedingspin-locks using memory-interlocked instructions: require special hardware to ensure that a given location can be read, modified and written without interruption (i.e. TST: test&set instruction)they are equivalent !OS-based mechanisms for ME: semaphores, monitors, message passing, lock filesthey are equivalent !Software reservationworks both for uniprocessors and multiprocessors but have overheads and memory requirementsmultiple algorithms: Dekker and Peterson (in recitation) Lamport (common case: 2 loads + 5 stores)start:b[i] = true;x=i;if (y<>0) { /* contention */b[i] = false;await (y==0);goto start;} y = i; if (x != i) { /* collision */ b[i] = false;for j=1 to N await(b[j]==false);if (y != i) {await (y==0);goto start;}}CRITICAL SECTIONy = 0;b[i] = false;Problems with concurrent execution•Concurrent processes (or threads) often need to share data (maintained either in shared memory or files) and resources•If there is no controlled access to shared data, some processes will obtain an inconsistent view of this data•The action performed by concurrent processes will then depend on the order in which their execution is interleavedAn example•Process P1 and P2 are running this same procedure and have access to the same variable “a”•Processes can be interrupted anywhere•If P1 is first interrupted after user input and P2 executes entirely•Then the character echoed by P1 will be the one read by P2 !!static char a;void echo(){ cin >> a; cout << a;}Race Conditions•Situations like this where processes access the same data concurrently and the outcome of execution depends on the particular order in which the access takes place is called a race condition •How must the processes coordinate (or synchronise) in order to guard against race conditions?The critical section problem•When a process executes code that manipulates shared data (or resource), we say that the process is in it’s critical section (CS) (for that shared data) •The execution of critical sections must be mutually exclusive: at any time, only one process is allowed to execute in its critical section (even with multiple CPUs)•Then each process must request the permission to enter it’s critical section (CS)The critical section problem•The section of code implementing this request is called the entry section•The critical section (CS) might be followed by an exit section•The remaining code is the remainder section•The critical section problem is to design a protocol that the processes can use so that their action will not depend on the order in which their execution is interleaved (possibly on many processors)Framework for analysis of solutions•Each process executes at nonzero speed but no assumption on the relative speed of n processes•General structure of a process:•many CPU may be present but memory hardware prevents simultaneous access to the same memory location•No assumption about order of interleaved execution •For solutions: we need to specify entry and exit sections repeat entry section critical section exit section remainder sectionforeverRequirements for a valid solution to the critical section problem•Mutual Exclusion–At any time, at most one process can be in its critical section (CS)•Progress–Only processes that are not executing in their RS can participate in the decision of who will enter next in the CS. –This selection cannot be postponed indefinitely•Hence, we must have no deadlockRequirements for a valid solution to the critical section problem (cont.)•Bounded Waiting–After a process has made a request to enter it’s CS, there is a bound on the number of times that the other processes are allowed to enter their CS •otherwise the process will suffer from starvationWhat about process failures?•If all 3 criteria (ME, progress, bounded waiting) are satisfied, then a valid solution will provide robustness against failure of a process in its remainder section (RS)–since failure in RS is just like having an infinitely long RS•However, no valid
View Full Document
Unlocking...