Slide 1Slide 2Slide 3BackgroundPROCESS SYNCHRONIZATIONSlide 6Slide 7Critical-Section ProblemSlide 9Solution to Critical-Section ProblemSlide 11Critical Regions (1)Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18TestAndndSet InstructionSolution using TestAndSetSwap InstructionSolution using SwapBounded-waiting Mutual Exclusion with TestandSet()Brief Segue: Edsger W. Dijkstra (1930-2002)SemaphoresSlide 26Slide 27Semaphores in CSSemaphores: Key ConceptsSemaphoreSemaphore as General Synchronization ToolSlide 32Semaphore ImplementationSemaphore Implementation with no Busy waitingSemaphore Implementation with no Busy waiting (Cont.)Deadlock and StarvationClassical Problems of SynchronizationBounded-Buffer ProblemBounded Buffer Problem (Cont.)Slide 40Dining Philosophers (1)Dining Philosophers (2)Dining Philosophers (3)Dining Philosophers (4)Readers-Writers ProblemReaders-Writers Problem (Cont.)Slide 47The Readers and Writers ProblemThree Level of Readers-Writers problemProblems with SemaphoresMonitorsSchematic view of a MonitorCondition VariablesMonitor with Condition VariablesSolution to Dining PhilosophersSolution to Dining Philosophers (cont)Monitor Implementation Using SemaphoresMonitor ImplementationA Monitor to Allocate Single ResourceAtomic TransactionsSystem ModelTypes of Storage MediaLog-Based RecoveryLog-Based Recovery AlgorithmCheckpointsConcurrent TransactionsSerializabilitySchedule 1: T0 then T1Nonserial ScheduleSchedule 2: Concurrent Serializable ScheduleLocking ProtocolTwo-phase Locking ProtocolTimestamp-based ProtocolsTimestamp-based Protocol ImplementationTimestamp-ordering ProtocolEnd of Lecture 6Saurav Karmakar1OPERATING SYSTEMS Lecture 6PROCESS SYNCHRONIZATIONCSC 4320/6320What Is In This Chapter?•This is about getting processes to coordinate with each other.•How do processes work with resources that must be shared between them?•How do we go about acquiring locks to protect regions of memory?•How is synchronization really used?6: Process Synchronization2OPERATING SYSTEM SynchronizationTopics Covered•Background•The Critical-Section Problem•Peterson’s Solution•Synchronization Hardware•Semaphores•Classic Problems of Synchronization•Synchronization Examples •Atomic Transactions6: Process Synchronization3OPERATING SYSTEM SynchronizationBackground•Concurrent access to shared data may result in data inconsistency•Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes•To SOLVE the consumer-producer problem that fills all the buffers. •We can do so by having an integer counter that keeps track of the number of full buffers. •Initially, counter is set to 0. It is incremented by the producer after it produces a new buffer and is decremented by the consumer after it consumes a buffer.46: Process SynchronizationPROCESS SYNCHRONIZATIONA producer process "produces" information "consumed" by a consumer process.Here are the variables needed to define the problem: 6: Process Synchronization5The ProducerConsumer Problem#define BUFFER_SIZE 10typedef struct { DATA data;} item;item buffer[BUFFER_SIZE];int in = 0; // Location of next input to bufferint out = 0; // Location of next removal from bufferint counter = 0; // Number of buffers currently fullConsider the code segments on the next page:• Does it work?• Are all buffers utilized?PROCESS SYNCHRONIZATIONA producer process "produces" information "consumed" by a consumer process. 6: Process Synchronization6The ProducerConsumer Problemitem nextProduced;while (TRUE) {while (counter == BUFFER_SIZE);buffer[in] = nextProduced;in = (in + 1) % BUFFER_SIZE;counter++;}item nextConsumed;while (TRUE) {while (counter == 0);nextConsumed = buffer[out];out = (out + 1) % BUFFER_SIZE;counter--;}#define BUFFER_SIZE 10typedef struct { DATA data;} item;item buffer[BUFFER_SIZE];int in = 0;int out = 0;int counter = 0;PRODUCERCONSUMERproducer consumerPROCESS SYNCHRONIZATION Note that counter++;  this line is NOT what it seems!! is really --> register = counter register = register + 1 counter = register At a micro level, the following scenario could occur using this code:This is RACE Condition6: Process Synchronization7The ProducerConsumer ProblemTO; Producer Execute register1 = counter register1 = 5T1; Producer Execute register1 = register1 + 1 register1 = 6T2; Consumer Execute register2 = counter register2 = 5T3; Consumer Execute register2 = register2 - 1 register2 = 4T4; Producer Execute counter = register1 counter = 6T5; Consumer Execute counter = register2 counter = 4Critical-Section Problem•Solution  not to allow any other process to access the shared data (variable) while one process is using it.•The section of the process’s program that contains the shared data will be called the critical section of the process. •Each process sharing some variables has a corresponding critical section where its code uses the shared memory.•What we require to solve, called the critical section problem (also the race condition problem), is to ensure that only one process at a time will be executing in its critical section.86: Process SynchronizationPROCESS SYNCHRONIZATIONA section of code, common to n cooperating processes, in which the processes may be accessing common variables. A Critical Section Environment contains:Entry Section Code requesting entry into the critical section.Critical Section Code in which only one process can execute at any one time.Exit Section The end of the critical section, releasing or allowing others in.Remainder Section Rest of the code AFTER the critical section.6: Process Synchronization9Critical SectionsSolution to Critical-Section Problem•Here is a general structure of typical process P, as given in the textbook, when critical section problem discussed:do {entry sectioncritical sectionexit sectionreminder section} while (1);•The entry and exit sections are enclosed in boxes to highlight these important segments of code.•Note that infinite looping is not necessary, since a process may go through its critical section limited number of times.10PROCESS SYNCHRONIZATION6: Process Synchronization11The critical section must ENFORCE ALL THREE of the following rules:Mutual Exclusion: No more than one process can execute in its critical section at one time.Progress: If no one is in the critical section and someone wants