OPERATING SYSTEMS
Module-3 Part1: Process Synchronization
Anuradha Pai
Assistant Prof
BTI College of Engineering
• Synchronization:
• The critical section problem
Table Of • Peterson’s solution
Contents • Synchronization hardware
• Semaphores
• Classical problems of synchronization
1. Objectives
• To develop a description of deadlocks, which prevent sets of concurrent processes
from completing their tasks
• To present a number of different methods for preventing or avoiding deadlocks in
a computer system
2. Concurrency vs. Parallelism
Concurrent Execution: Parallel Execution:
• Processes run by rapidly switching between them, • Different processes execute simultaneously on
managed by the CPU scheduler. separate processing cores.
• A single CPU executes instructions from multiple • Enables actual simultaneous execution of
processes in quick succession, giving the illusion of multiple instruction streams.
simultaneous execution.
• Processes may not complete execution fully before
being preempted.
The Role of Scheduling
• The CPU scheduler ensures processes share CPU time effectively.
• A process can be interrupted at any point in its execution stream to allow another process to use the CPU.
• This chapter delves into how concurrent and parallel execution can affect the integrity of data shared among
processes
3. Example: Producer-Consumer
Problem
• Overview:
• A classic example of cooperating processes sharing resources.
• The producer generates items and places them in a buffer. The consumer retrieves and processes items from the buffer.
• Initial Bounded Buffer Model:
• The buffer has a fixed size (BUFFER_SIZE).
• At most, BUFFER_SIZE - 1 items can be in the buffer simultaneously.
• Note: The term bounded buffer emphasizes that the buffer has a fixed, predefined size (or bound), meaning it can hold
only a limited number of items at a time.
Producer:
Consumer:
Item nextProduced;
while (true) { item nextConsumed;
/* Produce an item */ while (true) {
while (((in + 1) % BUFFER_SIZE) == out); while (in == out)
/* do nothing -- no free buffers */
; // do nothing -- nothing to consume
buffer[in] = item;
item = buffer[out];
in = (in + 1) % BUFFER SIZE;
out = (out + 1) % BUFFER SIZE;
}
4. Producer/Consumer Problem:
With Counter Variable
To improve the model, a variable counter is introduced:
• Tracks the current number of items in the buffer.
• Incremented when the producer adds an item.
• Decremented when the consumer removes an item.
• Initialized to 0
Modified Produce Code: Modified Consumer Code:
• Checks for available space in the buffer before • Checks if the buffer contains items before
adding an item. removing one.
• Updates the buffer and increments counter: • Updates the buffer and decrements counter:
4. Producer/Consumer Problem:
Concurrent Execution
If the producer and consumer execute concurrently, they may simultaneously modify counter.
• Example:
• counter starts at 5.
• The producer executes counter++ while the consumer executes counter--.
• The final value of counter could be 4, 5, or 6 instead of the expected 5.
• Machine-Level Operations for Increment and Decrement
• High-level statements like counter++ and counter-- are broken into several low-level instructions:
• These operations involve reading the value of counter into a CPU register, modifying it, and writing it back to
memory.
Counter++; Counter--;
4. Producer/Consumer Problem:
Example of Interleaved Execution
Concurrent execution of counter++ and • Multiple processes access and modify shared data
counter-- can result in incorrect interleaving: concurrently, resulting in unpredictable outcomes based
on execution order, is known as a race condition.
• To prevent such issues, processes must be synchronized
to ensure only one process manipulates shared data at a
time. This chapter focuses on synchronization
mechanisms to maintain orderly execution and ensure
data consistency among cooperating processes.
• To address this problem, we need synchronization
mechanisms that enforce mutual exclusion, ensuring
only one process modifies the shared variable at a time.
Synchronization is particularly critical in systems with
multiple cores and multithreaded applications, where
Result: The final value of counter is 4 threads often share data and operate in parallel.
instead of 5.
5. Critical Section
The critical-section problem addresses how processes can synchronize their actions to safely share
resources or data. It arises in systems with multiple processes, such as n processes denoted by P0,P1…,Pn−1.
Each process has a portion of code, called the critical section, where it performs actions that could affect
shared resources, like updating variables, modifying tables, or writing files.
• Key Characteristics of the Problem
• Only one process can execute its critical section at any given
time.
• If a process is in its critical section, all other processes must
wait.
• To address this, processes need a protocol for coordination. Before
entering the critical section, a process must:
1. Request permission (in the entry section).
2. Leave the critical section after finishing (in the exit section).
The remaining portion of the process’s code is called the
remainder section.
5.1 Critical Section Problem Solution
Any solution to the critical-section problem must satisfy the following:
[Link] Exclusion:
If one process is in its critical section, no other process can enter its critical
section simultaneously.
[Link]:
If no process is in its critical section, and some processes want to enter, the
system must decide which process can enter next. The decision must involve only
the processes requesting access and cannot be indefinitely postponed.
[Link] Waiting:
A process that requests entry to its critical section must be allowed to enter within
a finite time, ensuring no process is starved.
5.2 Critical Sections in Operating System
Challenges in Kernel Design
• Operating system kernels often face critical-section problems due to shared
data structures, such as:
• Open file lists
• Memory allocation tables
• Process lists
• Interrupt handling mechanisms
• Race conditions may occur if multiple processes modify shared data
simultaneously. Developers must ensure the kernel is designed to avoid
such conflicts.
5.3 Critical Sections in Operating
System
Two approaches to handle critical sections in operating system
[Link] Kernels:
• Allow processes to be interrupted while running in kernel mode.
• Offer better responsiveness and are suitable for real-time systems.
• Require careful design to avoid race conditions, especially on systems with multiple
processors.
[Link] Kernels:
• Do not interrupt processes running in kernel mode until they voluntarily yield
control, block, or complete.
• Easier to design and naturally free from race conditions because only one process
operates in the kernel at a time.
While preemptive kernels are more challenging to design, they are preferred for
applications requiring responsiveness or real-time capabilities. Nonpreemptive kernels,
though simpler, are less flexible in such scenarios.
6. Peterson’s Solution
• Peterson’s solution is a classic
software-based approach to solving
the critical-section problem,
particularly for two processes.
• Though it may not work correctly on
modern computer architectures due to
how basic machine instructions (like
load and store) are executed, it
remains an important algorithmic
illustration.
• It helps demonstrate the complexities
of designing software that meets the
critical-section requirements of
mutual exclusion, progress, and
bounded waiting.
6. Peterson’s Solution
• In this solution, two processes, P0and P1, • How It Works:
alternate between their critical sections and • When process Pi wants to enter the
remainder sections. critical section, it sets flag[i] =
• The two processes share two variables: true and turn = j, signaling that if
• int turn; process Pj also wants to enter, it
• Boolean flag[2] can proceed.
• The variable turn indicates whose turn it is to
• If both processes attempt to enter
enter the critical section at the same time, the value of turn
will get set to both i and j almost
• The flag array is used to indicate if a process simultaneously. However, the
is ready to enter the critical section. flag[i] = value of turn that persists will
true implies that process Pi is ready! determine which process enters its
critical section first.
6.1 Peterson’s Solution Steps
6.2 Peterson’s Solution Example
Process P0 Process P1
6.2 Peterson’s Solution Example
6.2 Peterson’s Solution Example
6.2 Peterson’s Solution Example
6.3 Peterson’s Solution: Simple Terms
6.4 Peterson’s Solution: Illustration
with timeline
6.5 Petersons Solution: Correctness
Proof
We must demonstrate that Peterson’s solution satisfies the following conditions:
• Mutual Exclusion: • Bounded Waiting:
• A process enters its critical section only if • A process Pi will not wait indefinitely to
flag[j] == false or turn == i. enter the critical section.
• If both processes attempt to enter their critical • If Pj enters the critical section first, it will
sections simultaneously, they will not both eventually exit and set flag[j] = false,
succeed at the same time, as turn can only allowing Pito enter.
have one valid value (either 0 or 1). • Even if Pj resets flag[j] to true, it must also
• Progress: set turn = i, ensuring Pi will eventually
• A process can enter its critical section unless it enter the critical section.
is blocked in the while loop (waiting for the • Thus, Peterson’s solution successfully
other process to finish). guarantees mutual exclusion, progress, and
• If process Pj is not trying to enter, flag[j] == bounded waiting for two processes.
false, allowing Pito enter immediately.
• If Pj is trying to enter, then either turn == i or
turn == j will allow one of the processes to
7. Synchronization Hardware
• We’ve previously explored a software-based solution to the critical-section problem. However, software
solutions like Peterson’s are not always reliable on modern computer architectures. In this section, we’ll
examine several alternative solutions to the critical-section problem, using both hardware and software-based
APIs available to kernel developers and application programmers. These solutions rely on the concept of
locking, which involves protecting critical sections with locks. As we’ll see, the design of these locks can be
quite intricate.
• We begin by discussing simple hardware instructions available in many systems and demonstrating how they
can be effectively used to solve the critical-section problem. Hardware features can significantly simplify
programming tasks and enhance system performance.
• In a single-processor environment, the critical-section problem could be resolved by disabling interrupts while
modifying a shared variable. This approach ensures that the current sequence of instructions is executed without
interruption, preventing any other instructions from modifying the shared variable. This method is often used by
nonpreemptive kernels.
• Challenges in Multiprocessor Environments
• In a multiprocessor environment, disabling interrupts is less practical. Sending interrupt-disable signals to
all processors can be time-consuming and inefficient, as it delays entry into the critical section and impacts
system performance. Moreover, if the system’s clock is maintained by interrupts, disabling them could
disrupt its functionality.
7. Synchronization Hardware
• Modern computer systems use special hardware instructions to address the critical-section problem,
ensuring safe access to shared resources in a concurrent environment. These instructions operate
atomically, meaning they execute without interruption, even if multiple CPUs try to use them
simultaneously.
• Example: TestAndSet() and Swap() instruction
7.1 TestAndSet() Instruction
• This instruction checks the value of a variable and
sets it to a specific value (typically true) in one
atomic operation.
• If two processes execute TestAndSet() at the same
time, one will succeed first, ensuring mutual
exclusion.
• Purpose of Returning the Old Value
1. Detect Contention:
• If the old value is TRUE, it means the
lock was already set by another process,
and you need to wait or try again.
• If the old value is FALSE, it means the
lock was not set, and you successfully
acquired it.
2. Atomic Lock Acquisition:
• By returning the old value, TestAndSet()
allows a process to determine
immediately if it succeeded in acquiring
the lock without needing additional
checks.
7.1 TestAndSet() Instruction
• The three steps explicitly show:
• Step 1: The old value of *target is saved.
• Step 2: The value of *target is updated to TRUE.
• Step 3: The old value is returned to the caller.
• This breakdown helps clarify the atomic nature of the operation, even though it
is implemented as a single machine-level instruction.
• Atomic Nature:
Even though the pseudocode shows three steps, the actual hardware
implementation performs these operations atomically as a single instruction.
This ensures no other process can interfere during execution.
7.1 Mutual Exclusion implementation
with TestAndSet() Instruction
• First Process:
When the first process calls
TestAndSet(&lock), the old value is FALSE,
so it proceeds to the critical section and sets
the lock to TRUE.
• Second Process:
When the second process calls
TestAndSet(&lock), the old value is TRUE,
meaning the lock is already held. It will loop
or block until the lock is released.
7.2 Swap() Instruction
• The Swap instruction works by atomically exchanging the values of two memory
locations. This operation ensures that the swap is completed as a single, uninterrupted
action, even in multiprocessor systems, where multiple processes might try to access
shared data simultaneously.
• *a and *b are pointers to two Boolean variables.
• The instruction swaps the values stored at the memory locations pointed to by a and b.
7.2 Mutual Exclusion with Swap()
Instruction
The Swap instruction can implement The structure of a process using Swap():
mutual exclusion by using a shared lock
variable (lock) and a local key variable
(key) for each process:
Algorithm
• Shared variable: lock (initial value
FALSE).
• Local variable: key (local to each
process).
7.2 Mutual Exclusion with Swap()
Instruction
7.3 Swap() Instruction
Properties of Algorithms
1. Mutual Exclusion:
• Only one process can enter the critical section at a time.
• Controlled using locks and flags like waiting[].
2. Progress:
• A process waiting to enter its critical section eventually proceeds when
another process exits.
3. Bounded Waiting:
• Waiting time for any process is bounded by n-1 turns.
8. Semaphore
•Hardware-based solutions to the critical- Atomic Operations
section problem are complex for application • Semaphore modifications via wait() and
developers. To simplify synchronization, signal() are indivisible, ensuring no other
semaphores are used as a powerful tool. process modifies the semaphore during
these operations.
• A semaphore, denoted by S, is an integer
• In wait(), both testing (S≤0) and
variable accessed via two atomic operations:
decrementing (S--) are performed without
wait() and signal(). interruption.
• wait() (originally termed P from the Dutch
proberen, meaning "to test") decrements
the semaphore.
• signal() (originally called V from
verhogen, meaning "to increment")
increments the semaphore.
8.1 Types of Semaphore
1. Counting Semaphore:
• Can hold values over an unrestricted domain.
• Used for managing a finite number of identical resources.
2. Binary Semaphore:
• Restricts values to 0 or 1.
• Commonly used for mutual exclusion and is often referred to as a mutex lock.
8.2 Semaphore Usage
• Critical-Section Problem: Binary Resource Management: Counting
semaphores (initialized to 1) can semaphores control access to limited
manage mutual exclusion for multiple resources.
processes. Each process performs:
• Semaphore initialized to resource
count.
• Processes decrement semaphore via
wait() when accessing a resource.
• Semaphore incremented via signal()
when resource is released.
8.3 Synchronization Between Processes
Process P1 Process P2
• Consider two concurrently running processes: P1 with a statement S1 and P2 with a statement S2.
• Suppose we require that S2 be executed only after S1 has completed. We can implement this
scheme readily by letting P1 and P2 share a common semaphore synch, initialized to 0.
• Because synch is initialized to 0, P2 will execute 52 only after P1 has invoked signal (synch),
which is after statement 51 has been executed.
8.4 Semaphore Implementation
• To implement semaphores under this definition, we define a semaphore as a "C'
struct:
• Each semaphore has an integer value and a list of processes list. When a process
must wait on a semaphore, it is added to the list of processes. A signal() operation
removes one process from the list of waiting processes and awakens that process.
8.5 Semaphore Implementation
Wait() Implementation Signal() Implementation
The block() operation suspends the process that invokes it. The wakeup(P) operation resumes the execution of a
blocked process P. These two operations are provided by the operating system as basic system calls.
8.6 Challenges and Problems:
Deadlocks
8.6 Challenges and Problems:
Indefinite Blocking and Priority Inversion