Khoa học máy tính - Chapter 6: Process synchronization

Chapter 6Process SynchronizationCopyright © 20081Operating Systems, by Dhananjay Dhamdhere*IntroductionWhat is Process Synchronization?Race ConditionsCritical SectionsControl Synchronization and Indivisible OperationsSynchronization ApproachesStructure of Concurrent Systems2Operating Systems, by Dhananjay Dhamdhere*Introduction (continued)Classic Process Synchronization ProblemsAlgorithmic Approach to Implementing Critical SectionsSemaphoresMonitorsCase Studies of Process Synchronization3Operating Systems, by Dhananjay Dhamdhere*What is Process Synchronization?The term process is a generic term for both a process and a threadProcesses that do not interact are independent processesProcess synchronization is a generic term for the techniques used to delay and resume processes to implement process interactions4Operating Systems, by Dhananjay Dhamdhere*5Operating Systems, by Dhananjay Dhamdhere*Race ConditionsUncoordinated accesses to shared data may affect consistency of dataConsider processes Pi and Pj that update the value of ds through operations ai and aj , respectively:Operation ai : ds := ds + 10; Let fi(ds) represent its resultOperation aj : ds := ds + 5; Let fj(ds) represent its resultWhat situation could arise if they execute concurrently?6Operating Systems, by Dhananjay Dhamdhere*An Example of Race ConditionRace conditionsin cases 2 and 37Operating Systems, by Dhananjay Dhamdhere*Race Conditions (continued)Race conditions in Figure 6.2 are prevented by ensuring that operations ai and aj of Definition 6.2 do not execute concurrentlyThis is called mutual exclusionData access synchronization is coordination of processes to implement mutual exclusion over shared data8Operating Systems, by Dhananjay Dhamdhere*Critical SectionsMutual exclusion is implemented by using critical sections (CS) of codeUsing CSs causes delays in operation of processesProcess must not execute for too long inside CSProcess must not make system calls while in the CS that might put it in blocked stateKernel must not preempt a process that is engaged in executing a CSWe use a dashed box in the code to mark a CS9Operating Systems, by Dhananjay Dhamdhere*Critical Sections (continued)10Operating Systems, by Dhananjay Dhamdhere*Properties of a Critical Section Implementation The progress and bounded wait properties together prevent starvation11Operating Systems, by Dhananjay Dhamdhere*Control Synchronization and Indivisible OperationsInteracting processes need to coordinate their execution with respect to one another, to perform their actions in a desired orderRequirement met through control synchronizationSignaling is a general technique of control synchronization12Operating Systems, by Dhananjay Dhamdhere*Control Synchronization and Indivisible Operations (continued)13Operating Systems, by Dhananjay Dhamdhere*Control Synchronization and Indivisible Operations (continued)Naive signaling in previous example does not workPi may face indefinite blocking in some situationsUse indivisible or atomic operations instead14Operating Systems, by Dhananjay Dhamdhere*Control Synchronization and Indivisible Operations (continued)15Operating Systems, by Dhananjay Dhamdhere*Synchronization ApproachesLooping versus BlockingHardware Support for Process SynchronizationAlgorithmic Approaches, Synchronization Primitives, and Concurrent Programming Constructs16Operating Systems, by Dhananjay Dhamdhere*Looping versus BlockingBusy wait:A busy wait has many consequencesCannot provide the bounded wait propertySystem performance degradation due to loopingDeadlockPriority inversionTypically addressed through the priority inheritance protocol17Operating Systems, by Dhananjay Dhamdhere*Looping versus Blocking (continued)To avoid busy waits, a process waiting for entry to a CS is put in blocked stateChanged to ready only when it can enter the CSProcess decides to loop or blockDecision is subject to race conditions. Avoided throughAlgorithmic approachUse of computer hardware features18Operating Systems, by Dhananjay Dhamdhere*Hardware Support for Process SynchronizationIndivisible instructionsAvoid race conditions on memory locationsUsed with a lock variable to implement CS and indivisible operationsentry_test performed with indivisible instructionTest-and-set (TS) instructionSwap instruction19Operating Systems, by Dhananjay Dhamdhere*Hardware Support for Process Synchronization (continued)20Operating Systems, by Dhananjay Dhamdhere*Algorithmic Approaches, Synchronization Primitives, and Concurrent Programming ConstructsAlgorithmic ApproachesFor implementing mutual exclusionIndependent of hardware or software platformBusy waiting for synchronizationSynchronization PrimitivesImplemented using indivisible instructionsE.g., wait and signal of semaphoresProblem: can be used haphazardlyConcurrent Programming ConstructsMonitors21Operating Systems, by Dhananjay Dhamdhere*Structure of Concurrent SystemsThree key components:Shared dataApplication data used and manipulated by processes Synchronization dataOperations on shared dataConvenient unit of code which accesses and manipulates shared dataA synchronization operation is on synchronization dataInteracting processesA snapshot of a concurrent system is a view of the system at a specific time instant22Operating Systems, by Dhananjay Dhamdhere*Structure of Concurrent Systems (continued)23Operating Systems, by Dhananjay Dhamdhere*Example: Snapshots of a Concurrent System Pi performs operation check_aj Pi is blocked; Pj performs operation post_aj post_aj activates Pi; Pj exits post_aj24Operating Systems, by Dhananjay Dhamdhere*Classic Process Synchronization ProblemsA solution to a process synchronization problem should meet three important criteria:CorrectnessMaximum concurrencyNo busy waitsSome classic problems:Producers-Consumers with Bounded BuffersReaders and WritersDining Philosophers25Operating Systems, by Dhananjay Dhamdhere*Producers-Consumers with Bounded BuffersA solution must satisfy the following:A producer must not overwrite a full bufferA consumer must not consume an empty bufferProducers and consumers must access buffers in a mutually exclusive manner(Optional) Information must be consumed in the same order in which it is put into the buffers26Operating Systems, by Dhananjay Dhamdhere*Producers-Consumers with Bounded Buffers (continued)Suffers from two problems:Poor concurrency and busy waits27Operating Systems, by Dhananjay Dhamdhere*Producers-Consumers with Bounded Buffers (continued)28Operating Systems, by Dhananjay Dhamdhere*Producers-Consumers with Bounded Buffers (continued)29Operating Systems, by Dhananjay Dhamdhere*Readers and WritersA solution must satisfy the following:Many readers can perform reading concurrentlyReading is prohibited while a writer is writingOnly one writer can perform writing at any time(optional) A reader has a nonpreemptive priority over writers─ Called readers preferred readers–writers system30Operating Systems, by Dhananjay Dhamdhere*Readers and Writers (continued)31Operating Systems, by Dhananjay Dhamdhere*Dining PhilosophersDesign processes to represent the philosophers so that each philosopher can eat when hungry and none dies of hungerSolution shouldn’t suffer from deadlocks or livelocks32Operating Systems, by Dhananjay Dhamdhere*Dining Philosophers (continued)Prone to deadlocks and race conditions, unless:If right fork is unavailable, release left fork, retry laterIt suffers from livelocks33Operating Systems, by Dhananjay Dhamdhere*Dining Philosophers (continued)Problem: loop causes a busy wait condition34Operating Systems, by Dhananjay Dhamdhere*Algorithmic Approach to Implementing Critical SectionsTwo-Process Algorithmsn-Process Algorithms35Operating Systems, by Dhananjay Dhamdhere*Two-Process AlgorithmsViolates the progress condition36Operating Systems, by Dhananjay Dhamdhere*Two-Process Algorithms (continued)Violates mutual exclusion conditionCan lead to deadlock37Operating Systems, by Dhananjay Dhamdhere*Turn is effective only when Both processes try to enter CS at the same time 38Operating Systems, by Dhananjay Dhamdhere*Two-Process Algorithms (continued)39Operating Systems, by Dhananjay Dhamdhere*n-Process AlgorithmsContains a certain form of unfairness since processes do not enter their CSs in the same order in which they requested entry to a CS.40Operating Systems, by Dhananjay Dhamdhere*(number[j],j) < number[i],i) if number[j] < number[i], or number[j] = number[i] and j < i41Operating Systems, by Dhananjay Dhamdhere*Semaphores Also called counting semaphores due to operations on S42Operating Systems, by Dhananjay Dhamdhere*Uses of Semaphores in Concurrent Systems43Operating Systems, by Dhananjay Dhamdhere*Uses: Mutual Exclusion44Operating Systems, by Dhananjay Dhamdhere*Uses: Bounded ConcurrencyImplemented by initializing a semaphore sem_c to cEvery process wishing to perform opi performs a wait(sem_c) before performing opi and a signal(sem_c) after performing itUp to c processes can concurrently perform opi 45Operating Systems, by Dhananjay Dhamdhere*Uses: Signaling between ProcessesRace conditions cannot arise because the wait and signal operations are indivisibleBinary semaphore: Can have values 0 and 1 only46Operating Systems, by Dhananjay Dhamdhere*Producers-Consumers Using SemaphoresAvoids busy waits since semaphores are used to check for empty or full buffersTotal concurrency in system is 147Operating Systems, by Dhananjay Dhamdhere*Example: Producers-Consumers with a Single Buffer through Semaphores48Operating Systems, by Dhananjay Dhamdhere*Producers-Consumers Using Semaphores (continued)Solution to n-buffer producers–consumers problem:49Operating Systems, by Dhananjay Dhamdhere*Readers-Writers Using Semaphores Significance of counters: – runread: Number of readers reading – totread: Number of readers wishing to read or reading – Similarly runwrite and totwrite5051Operating Systems, by Dhananjay Dhamdhere*Implementation of SemaphoresImplementations of wait and signal:Kernel-Level: Through system callsUser-Level: System calls only to block/activateHybrid: Combination of the two52Operating Systems, by Dhananjay Dhamdhere*MonitorsA monitor type resembles a class in a language like C++ or JavaContains declarations of shared dataIts procedures encode operations that manipulate shared data and implement process synchronizationA condition is a situation of interest in a monitorA condition variable is associated with a condition A process executing a wait operation on condition variable is blocked until some process performs a signal operationIn a concurrent system, processes share data by creating a monitor objectWe call it simply monitor53Operating Systems, by Dhananjay Dhamdhere*Example: Monitor Implementation of a Binary Semaphore54Operating Systems, by Dhananjay Dhamdhere*Example: Producers-Consumers Using Monitors55Operating Systems, by Dhananjay Dhamdhere*Monitors in JavaA Java class becomes a monitor type when the attribute synchronized is associated with one or more methods in the classAn object of such a class is a monitorEach monitor contains a single unnamed condition variableCan lead to busy waits in an application that has many conditions56Operating Systems, by Dhananjay Dhamdhere*Case Studies of Process SynchronizationSynchronization of POSIX ThreadsProcess Synchronization in UnixProcess Synchronization in LinuxProcess Synchronization in SolarisProcess Synchronization in Windows57Operating Systems, by Dhananjay Dhamdhere*Synchronization of POSIX ThreadsPOSIX threads provide:Mutexes for mutual exclusion A mutex is a binary semaphoreCondition variables for control synchronization between processesAn OS may implement POSIX threads as kernel-level threads or user-level threads58Operating Systems, by Dhananjay Dhamdhere*Process Synchronization in UnixUnix system V provides a kernel-level implementation of semaphoresName of a semaphore is called a keyKey is associated with an array of semaphoresProcesses share a semaphore by using the same keyUnix SVR4 keeps track of all operations performed by a process on each semaphore used by itPerforms an undo on them when process terminatesIt helps to make programs more reliableUnix 4.4BSD places a semaphore in shared memory areas and uses a hybrid implementation59Operating Systems, by Dhananjay Dhamdhere*Process Synchronization in LinuxLinux has Unix-like semaphore for user processesAlso provides semaphores for use by the kernel:Conventional semaphoreUses efficient kernel-level implementation schemeReader–writer semaphoreKernels older than 2.6 implemented mutual exclusion in the kernel space through system calls2.6 kernel has a fast user space mutex called futexUses a hybrid implementationProvides time-bound wait operation60Operating Systems, by Dhananjay Dhamdhere*Process Synchronization in SolarisInteresting features:Reader–writer semaphoresAnalogous to the one in LinuxAdaptive mutexesUseful in a multiprocessor OSUses the priority inheritance protocol to reduce synchronization delaysData structure called a turnstileHolds information concerning threads that are blocked on a mutex or reader–writer semaphoreUsed for synchronization and priority inheritance61Process synchronization in WindowsDispatcher object is embedded in every object over which synchronization is neededIt can be in signaled/nonsignaled stateDispatcher objects used in process, file, etc. (next slide)Provides spinlock, queued spinlock, fast mutex and push locksVista provides a reader-writer lockOperating Systems, by Dhananjay Dhamdhere*62Operating Systems, by Dhananjay Dhamdhere*Process Synchronization in Windows63Operating Systems, by Dhananjay Dhamdhere*SummaryProcess synchronization is a generic term for data access synchronization and control synchronizationA race condition occurs when actions of concurrent processes may have unexpected consequencesAvoided through mutual exclusionAvoidance of race conditions is a primary issue in process synchronizationCritical section: section of code that accesses some shared data in a mutually exclusive mannerSynchronization achieved through: indivisible instructions, semaphores, monitors64