ICS 143 - Principles of Operating SystemsOutlineProducer-Consumer ProblemSlide 4Bounded Buffer using IPC (messaging)Bounded-buffer - Shared Memory SolutionBounded Buffer - Shared Memory SolutionSlide 8Shared dataBounded BufferSlide 11Slide 12Problem is at the lowest levelThe Critical-Section ProblemSolution: Critical Section Problem - RequirementsSlide 16Solution: Critical Section Problem -- Initial AttemptAlgorithm 1Algorithm 2Algorithm 3Algorithm 4Bakery AlgorithmBakery Algorithm (cont.)Slide 24Supporting SynchronizationHardware Solutions for SynchronizationSynchronization HardwareMutual Exclusion with Test-and-SetBounded Waiting Mutual Exclusion with Test-and-SetHardware Support: Other examplesSemaphoreExample: Critical Section for n ProcessesSemaphore as a General Synchronization ToolProblem...Semaphore ImplementationSemaphore Implementation(cont.)Block/Resume Semaphore ImplementationDeadlock and StarvationTwo Types of SemaphoresImplementing S (counting sem.) as a Binary SemaphoreImplementing SClassical Problems of SynchronizationBounded Buffer ProblemBounded Buffer ProblemSlide 45DiscussionReaders/Writers ProblemReaders-Writers ProblemReaders-Writers ProblemDining-Philosophers ProblemDining Philosophers ProblemHigher Level SynchronizationMotivation for Other Sync. ConstructsConditional Critical RegionsCritical Regions (cont.)Example - Bounded BufferBounded Buffer ExampleMonitorsMonitor with Condition VariablesMonitors with condition variablesDining PhilosophersDining Philosophers (cont.)Mesa vs. Hoare monitorsAdditional slidesImplementing RegionsImplementationSlide 67Principles of Operating Systems - Process Synchronization 1ICS 143 - Principles of Operating SystemsLecture 6 - Process SynchronizationProf. Dmitri V. Kalashnikovdvk (@) ics.uci.eduSlides © Prof. Nalini Venkatasubramanian.Principles of Operating Systems - Process Synchronization 2OutlineThe Critical Section ProblemSynchronization HardwareSemaphoresClassical Problems of SynchronizationCritical RegionsMonitorsSynchronization in Solaris 2Atomic TransactionsProducer-Consumer ProblemParadigm for cooperating processes; producer process produces information that is consumed by a consumer process.We need buffer of items that can be filled by producer and emptied by consumer.•Unbounded-buffer places no practical limit on the size of the buffer. Consumer may wait, producer never waits.•Bounded-buffer assumes that there is a fixed buffer size. Consumer waits for new item, producer waits if buffer is full.Producer and Consumer must synchronize.Producer-Consumer ProblemBounded Buffer using IPC (messaging)Producerrepeat… produce an item in nextp; … send(consumer, nextp);until false;Consumerrepeatreceive(producer, nextc);… consume item from nextc; …until false;Bounded-buffer - Shared Memory SolutionShared datavar n;type item = ….;var buffer: array[0..n-1] of item;in, out: 0..n-1; in :=0; out:= 0; /* shared buffer = circular array *//* Buffer empty if in == out *//* Buffer full if (in+1) mod n == out *//* noop means ‘do nothing’ */Bounded Buffer - Shared Memory SolutionProducer process - creates filled buffersrepeat… produce an item in nextp … while in+1 mod n = out do noop; buffer[in] := nextp; in := in+1 mod n;until false;Bounded Buffer - Shared Memory SolutionConsumer process - Empties filled buffersrepeat while in = out do noop; nextc := buffer[out] ; out:= out+1 mod n; … consume the next item in nextc …until falsePrinciples of Operating Systems - Process Synchronization 9Shared data Concurrent access to shared data may result in data inconsistency.Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.Shared memory solution to the bounded-buffer problem allows at most (n-1) items in the buffer at the same time.Principles of Operating Systems - Process Synchronization 10Bounded BufferA solution that uses all N buffers is not that simple.Modify producer-consumer code by adding a variable counter, initialized to 0, incremented each time a new item is added to the buffer Shared datatype item = ….;var buffer: array[0..n-1] of item;in, out: 0..n-1; counter: 0..n; in, out, counter := 0;Principles of Operating Systems - Process Synchronization 11Bounded BufferProducer process - creates filled buffersrepeat… produce an item in nextp … while counter = n do noop; buffer[in] := nextp; in := in+1 mod n; counter := counter+1;until false;Principles of Operating Systems - Process Synchronization 12Bounded BufferConsumer process - Empties filled buffersrepeat while counter = 0 do noop; nextc := buffer[out] ; out:= out+1 mod n; counter := counter - 1; … consume the next item in nextc …until false;The statementscounter := counter + 1;counter := counter - 1; must be executed atomically. Atomic OperationsAn operation that runs to completion or not at all.Problem is at the lowest levelIf threads are working on separate data, scheduling doesn’t matter:Thread A Thread Bx = 1; y = 2;However, What about (Initially, y = 12):Thread A Thread Bx = 1; y = 2;x = y+1; y = y*2;What are the possible values of x? Or, what are the possible values of x below?Thread A Thread Bx = 1; x = 2;X could be non-deterministic (1, 2??)Principles of Operating Systems - Process Synchronization 14The Critical-Section ProblemN processes all competing to use shared data.•Structure of process Pi ---- Each process has a code segment, called the critical section, in which the shared data is accessed.repeat entry section /* enter critical section */ critical section /* access shared variables */ exit section /* leave critical section */ remainder section /* do other work */ until falseProblem •Ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section.Principles of Operating Systems - Process Synchronization 15Solution: Critical Section Problem - RequirementsMutual Exclusion•If process Pi is 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 there exists some processes that wish to enter their critical section, then the selection of the processes that will enter the critical