Process Synchronization Chapter 5

• CH 5 - Process Synchronization

Recap

• Cooperating processes can affect or be affected by other processes in execution.
• Processes can share data in two ways: sharing a logical address space (done by threads) or sharing data through messages/files which requires concurrent access.
• Running processes can be interrupted, leading to data inconsistency.
• Data consistency is needed to ensure cooperating processes run in order.
• To solve the producer-consumer problem when all buffers are full, an integer counter tracks the number of full buffers.
• The counter is initially set to 0, incremented by the producer, and decremented by the consumer.

Peterson's Solution

• Peterson's Solution synchronizes two processes competing for a shared resource.
• It solves the critical section problem without special hardware.
• Peterson's solution uses busy waiting (spinlock).
• It assumes atomic load and store instructions to avoid interruptions.
• It has two shared variables: 'turn' (indicates whose turn it is) and 'flag' (indicates if a process is ready).
• If flag[i] is true, process i is ready; otherwise, it's not.

Algorithm

• The flag[i] gives priority to turn.
• Process can only enter critical section one time.

Solution

• Solution ensures mutual exclusion
• The create an integer counter that will keep track of the number of full buffers
• The counter is set to zero initially
• The producer produces and item, counter is incremented by 1.
• Consumer consumes item, counter decremented by 1.

Mutual Exclusion, Progress, and Bounded Waiting

• Peterson's solution satisfies the critical section requirements.
• Mutual exclusion is satisfied because Pi can enter if flag[j] is false or turn is i. It can't be both.
• Progress is satisfied due to flag[i] being false in the while(true) loop. Pi can execute any time.
• Bounded waiting is satisfied because of flag[i] being false and the while(true) loop.

Components of the Producer-Consumer Problem

• Producer and consumer are two separate processes writing into and reading out of a bounded buffer.
• Bounded buffer, in pointer, out pointer, and a counter are required.
• The counter, if not handled correctly, can lead to a race condition.

Race Condition

• counter++ could be implemented as register1 = counter, register1 = register1 + 1, counter = register1
• counter-- could be implemented as register2 = counter, register2 = register2 - 1, counter = register2
• If there is interleaving between these blocks there might data inconsistancy.
• Race condition occurs when multiple processes access and manipulate the same data, and the outcome depends on the order of access.

Critical Section Problem

• Involves 'n' processes, each with a critical section segment that can change shared variables, update tables, or write files.
• If a process is in its critical section, no other process should be in theirs.
• The process asks for permission to enter the critical section in the entry section, executes in critical section, exits in exit section, and loops again.
• Rules of critical section problem include the different sections of the process (entry, critical, exit and remainder).
• Solution to critical section problems must satisfy mutual exclusion, progress and bounded waiting

Mutual Exclusion

• If a process is executing in its critical section, no other processes can be in their critical sections.

Progress

• If no process is in a critical section and some processes want to enter, the selection of which process enters next cannot be indefinitely postponed.

Bounded Waiting

• There is a bound on how many times other processes can enter their critical sections after a process has requested entry and before its request is granted.

Synchronization Hardware

• It needs hardware support for critical section code
• Solutions protect critical regions via locks.
• For example, uniprocessors could disable interrupts for the critical section to run without preemption.
• Disabling interupts are inefficient for multiprocessor and not scalable
• Modern machines use atomic hardware instructions.

Atomic Instructions

• Atomic instructions are non-interruptible sequences that either test and set a memory word or swap the contents of two memory words.
• CPU can be taken at any time during an execution.

Types of Locks

Mutex Locks

• Mutex locks provide mutual exclusion, protecting critical sections using a boolean variable.
• Processes acquire() a lock before the critical section and release() it afterward.
• Acquire & release calls are atomic & implemented via atomic hardware instructions
• This solution might require busy waiting (spinlock).

Semaphore

• Semaphores are a more sophisticated way to synchronize process actions.
• Most used solutions
• It has an integer variable S and two atomic operations: wait() and signal().
• Process with try to enter a critical section (CS)
• If S>0 it will be decremented & enter CS; if S<=0 it will wait

Wait() Operation

• Definition of the wait() operation
• wait(S) operation decrements the semaphore (S), and if S becomes negative, the process is blocked.
• The process busy waits or must until S > 0

Signal() Operation

• Definition of signal operation
• The signal(S) operation increments (S) semaphore; which can allow other processes to continue.

Types of Semaphores

• Counting semaphore integer values range is unrestricted domain
• Binary semaphore integer balues range restrict between 0 & 1 (Mutex lock)

Synchronization example

• Suppose P1 and P2 require S1 to happen before S2
• Create a semaphore "synch" initialized to 0.
• P1 will will enter
• P2 will wait until P1 finish
• Solve synchronization problems.

Assumptions

• Assume that processes execute at non-zero speed.
• No assumption to the relative speed of the processes.

Critical Section Handling

• Critical Section Handling in OS depends on whether it's preemptive or non-preemptive.

Preemptive Kernel

• Preemptive kernels allow preemption of processes when running in kernel mode i.e. CPU is taken at any time
• It relinquishes control before using all the available time.

Non-Preemptive Kernel

• Non-preemptive kernels run until they exit, block, or voluntarily yield the CPU.
• CPU cannot be taken from a process running in kernel mode until it completes with no race conditions in kernel mode.

Deadlock & Starvation

Deadlock

• Deadlock occurs when two or more processes are waiting for each other to release resources.

Example Deadlock

• Let S and Q be two semaphores initialized to 1.
• P0 is waiting(S)
• Then P0 tries to acquires Q but it cant be so it waits(S)
• P1 tries to acquire (Q) after acquiring P0.
• Deadlock happens because the operations will not execute and P0 and P1 are deadlocks.

Starvation

• Starvation refers to indefinite blocking, where a process may never be removed from a semaphore queue, possibly due to priorities or scheduling issues.

Priority Inversion

• Priority Inversion is a scheduling issue where a low-priority process holds a lock needed by a high-priority process.

Classical Problems

• Classical Problems if solved then synchronization scheme proposed works can be: Bound-Buffer Problem (Producer-Consumer Problem) Readers-writers problem Dining philosphers problem