Mutual Exclusion, Synchronization and Classical InterProcess Communication (IPC) ProblemsIntroductionTopics for discussionPrinciples of Concurrency...Concurrency (contd.)Interactions among processesInteractions ...(contd.)Race ConditionMutual exclusion problemMutual exclusionSoftware Solutions: Algorithm 1Algorithm 2Algorithm 3Synchronization HardwareMutual Exclusion with Test-and-SetSynchronization HardwareMutual Exclusion with SwapSemaphoresSemaphoresCritical Section of n ProcessesSemaphore ImplementationImplementationSemaphore as a General Synchronization ToolSemaphores for CSDeadlock and StarvationTwo Types of SemaphoresImplementing S as a Binary SemaphoreImplementing SClassical Problems of SynchronizationProducer/Consumer problemSolution for P/C using SemaphoresP/C: improved solutionP/C problem: Bounded bufferP/C: Bounded Buffer solutionSemaphores - commentsMonitorsMonitorsMonitorsSchematic View of a MonitorMonitor With Condition VariablesMessage passingIssues in message passingReader/Writer problemReader/writer: Priority ReadersDining Philosophers ExampleDining PhilosophersDining PhilosophersSummary3/16/2003 B.Ramamurthy 1Mutual Exclusion, Synchronization and Classical InterProcessCommunication (IPC) ProblemsB.RamamurthyCSE4213/16/2003 B.Ramamurthy 2IntroductionAn important and fundamental feature in modern operating systems is concurrent execution of processes/threads. This feature is essential for the realization of multiprogramming, multiprocessing, distributed systems, and client-server model of computation.Concurrency encompasses many design issues including communication and synchronization among processes, sharing of and contention for resources.In this discussion we will look at the various design issues/problems and the wide variety of solutions available.3/16/2003 B.Ramamurthy 3Topics for discussionThe principles of concurrencyInteractions among processesMutual exclusion problemMutual exclusion- solutions Software approaches (Dekker’s and Peterson’s) Hardware support (test and set atomic operation) OS solution (semaphores) PL solution (monitors) Distributed OS solution ( message passing)Reader/writer problemDining Philosophers Problem3/16/2003 B.Ramamurthy 4Principles of ConcurrencyInterleaving and overlapping the execution of processes.Consider two processes P1 and P2 executing the function echo:{input (in, keyboard);out = in;output (out, display);}3/16/2003 B.Ramamurthy 5...Concurrency (contd.)P1 invokes echo, after it inputs into in , gets interrupted (switched). P2 invokes echo, inputs into in and completes the execution and exits. When P1 returns in is overwritten and gone. Result: first ch is lost and second ch is written twice.This type of situation is even more probable in multiprocessing systems where real concurrency is realizable thru’ multiple processes executing on multiple processors.Solution: Controlled access to shared resource Protect the shared resource : inbuffer; “critical resource” one process/shared code. “critical region”3/16/2003 B.Ramamurthy 6Interactions among processesIn a multi-process application these are the various degrees of interaction:1. Competing processes: Processes themselves do not share anything. But OS has to share the system resources among these processes “competing” for system resources such as disk, file or printer.Co-operating processes : Results of one or more processes may be needed for another process. 2. Co-operation by sharing : Example: Sharing of an IO buffer. Concept of critical section. (indirect)3. Co-operation by communication : Example: typically no data sharing, but co-ordination thru’ synchronization becomes essential in certain applications. (direct)3/16/2003 B.Ramamurthy 7Interactions ...(contd.)Among the three kinds of interactions indicated by 1, 2 and 3 above:1 is at the system level: potential problems : deadlock and starvation.2 is at the process level : significant problem is in realizing mutual exclusion.3 is more a synchronization problem.We will study mutual exclusion and symchronization here, and defer deadlock, and starvation for a later time.3/16/2003 B.Ramamurthy 8Race ConditionRace condition: The situation where several processes access – and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last.To prevent race conditions, concurrent processes must be synchronized.3/16/2003 B.Ramamurthy 9Mutual exclusion problemSuccessful use of concurrency among processes requires the ability to define critical sections and enforce mutual exclusion.Critical section : is that part of the process code that affects the shared resource.Mutual exclusion: in the use of a shared resource is provided by making its access mutually exclusive among the processes that share the resource.This is also known as the Critical Section (CS) problem.3/16/2003 B.Ramamurthy 10Mutual exclusionAny facility that provides mutual exclusion should meet these requirements: 1. No assumption regarding the relative speeds of the processes.2. A process is in its CS for a finite time only.3. Only one process allowed in the CS.4. Process requesting access to CS should not wait indefinitely.5. A process waiting to enter CS cannot be blocking a process in CS or any other processes.3/16/2003 B.Ramamurthy 11Software Solutions: Algorithm 1Process 0...while turn != 0 donothing;// busy waiting< Critical Section>turn = 1;...Problems : Strict alternation, Busy WaitingProcess 1...while turn != 1 donothing;// busy waiting< Critical Section>turn = 0;...3/16/2003 B.Ramamurthy 12Algorithm 2PROCESS 0...flag[0] = TRUE;while flag[1] do nothing;<CRITICAL SECTION>flag[0] = FALSE;PROBLEM : Potential for deadlock, if one of the processes fail within CS.PROCESS 1...flag[1] = TRUE;while flag[0] do nothing;<CRITICAL SECTION>flag[1] = FALSE;3/16/2003 B.Ramamurthy 13Algorithm 3Combined shared variables of algorithms 1 and 2.Process Pido {flag [i]:= true;turn = j;while (flag [j] and turn = j) ;critical sectionflag [i] = false;remainder section} while (1);Meets all three requirements; solves the critical-section problem for two processes.3/16/2003 B.Ramamurthy 14Synchronization HardwareTest and modify the content of a word atomically.boolean TestAndSet(boolean &target) {boolean rv = target;tqrget = true;return rv;}3/16/2003 B.Ramamurthy 15Mutual Exclusion with Test-and-SetShared data: boolean lock = false;Process Pido {while (TestAndSet(lock)) ;critical
View Full Document
Unlocking...