MODULE 2

Syllabus:

Concurrency and Synchronization – Basic principles. - Mechanisms: Locks – The basic idea;
Building spin locks with test-and-set; Compare-and-swap; Using queues: sleeping instead of
spinning. - Semaphores – Definition; Binary semaphores; The Producer–Consumer (bounded
buffer) problem and its solution using semaphores-Reader–Writer locks.

Concurrency and Synchronization – Basic principles.

Introduction to Concurrency

Concurrency refers to the execution of multiple processes or threads at the same time within a
computer system. In an operating system, concurrency allows several tasks to make progress
simultaneously by sharing CPU time and system resources.

Concurrency is an essential concept in modern operating systems to improve overall system

performance and responsiveness.

Importance of Concurrency

Concurrency is important because it helps in the following ways:

1. Improves CPU Utilization

The CPU does not remain idle while one process is waiting for input/output
operations. Instead, another process can use the CPU, leading to efficient utilization
of processor time.

2. Increases System Throughput

By executing multiple processes concurrently, the system can complete more tasks
in a given amount of time, thereby increasing overall throughput.

3. Supports Multitasking and Multi-User Systems

Concurrency allows multiple applications to run at the same time and supports
multiple users accessing the system simultaneously without performance
degradation.
Types of Concurrency
Concurrency can occur in the following systems:

1. Single-Core Systems

In single-core systems, concurrency is achieved through context switching. The CPU switches
rapidly between multiple processes, giving the illusion that they are running simultaneously,
even though only one process executes at a time.

2. Multi-Core Systems

In multi-core systems, true parallel execution is possible. Multiple processes or threads can
execute at the same time on different CPU cores, resulting in better performance and faster
execution.

Concurrent Processes and Threads

A process is a program in execution, whereas a thread is the smallest unit of execution within
a process.

Concurrent processes or threads are those that execute simultaneously and may run
independently or cooperate with each other. Threads within the same process share the
same address space, making communication faster, while processes usually have separate
memory spaces. Concurrency among processes and threads helps in faster execution and
better CPU utilization
Shared Resources and Data Consistency
In a concurrent system, multiple processes or threads may share common resources such as
variables, memory, files, or devices. When shared resources are accessed simultaneously
without control, it can lead to inconsistent or incorrect data.

Data consistency ensures that shared data remains correct and predictable even when
accessed by multiple processes concurrently. To maintain data consistency, proper
synchronization mechanisms are required.

Process synchronization:
Process Synchronization means sharing system resources by processes in such a way that,
Concurrent access to shared data is handled thereby minimizing the chance of inconsistent
data. Maintaining data consistency demands mechanisms to ensure synchronized execution
of cooperating processes They can share

 Variable
 Memory
 Code
 Resources

Why Concurrency is Challenging

 When multiple processes access shared resources (variables, files, memory),

uncontrolled access can lead to:
o Incorrect results
o Data inconsistency
o System instability
 This leads to the need for process synchronization.

Consider value is a shared variable accessed by two concurrent processes P1 and P2.

Process P1 Process P2
x = value; y = value;
x++; y--;
sleep(1); sleep(1);
value = x; value = y;
  Process P1 reads the shared variable value into local variable x, increments it by 1,
waits for some time using sleep(1), and then writes the updated value back to value.
 Process P2 reads the same shared variable value into local variable y, decrements it
by 1, waits using sleep(1), and then writes the updated value back to value.

Problem Without Process Synchronization

Since both P1 and P2 execute concurrently, the following situation may occur:

1. P1 reads value into x

2. Context switch occurs

3. P2 reads the same value into y

4. Both processes modify their local copies independently

5. The last process to write updates value

Final value depends on execution order, not on logic.

Why Process Synchronization Is Needed

Process synchronization is required to:

 Prevent simultaneous access to shared variable value

 Ensure only one process updates value at a time
 Maintain data consistency
 Avoid race conditions

The statements accessing value form a critical section, which must be protected.

Race Conditions
A race condition occurs when two or more processes or threads access and modify shared
data concurrently, and the final result depends on the order of execution. Since the execution
order is unpredictable, the output may vary each time the program runs. Race conditions can
cause incorrect results and system instability. Synchronization techniques are used to prevent
race conditions by controlling access to shared resources.
Critical Section Problem
A critical section is a part of a program where shared resources are accessed or modified. The
critical section problem arises when multiple processes attempt to enter their critical sections
simultaneously, leading to race conditions.

The objective of the critical section problem is to design a protocol that ensures only one
process can execute in its critical section at a time, thereby maintaining data consistency.

For every critical section in the program, a synchronization mechanism adds:

 An entry section before the critical section

 An exit section after the critical section

Entry Section

 It acts as a gateway for a process to enter inside the critical section.

 It ensures that only one process is present inside the critical section at any time.
 It does not allow any other process to enter inside the critical section if one process is
already present inside it.

Exit Section

 It acts as an exit gate for a process to leave the critical section.

 When a process takes exit from the critical section, some changes are made so that
other processes can enter inside the critical section.
Requirements for Critical Section Solution

Any correct solution to the critical section problem must satisfy the following conditions:

1. Mutual Exclusion

Mutual exclusion ensures that only one process is allowed to enter the critical section at any
given time. If one process is executing in the critical section, no other process should be
allowed to enter it.

2. Progress

Progress means that if no process is executing in the critical section, and some processes wish
to enter it, the selection of the next process to enter the critical section should not be
postponed indefinitely. Processes that do not want to enter the critical section should not
block others.
3. Bounded Waiting

Bounded waiting ensures that there is a limit on the number of times other processes can
enter the critical section after a process has made a request to enter. This prevents starvation
and guarantees that every process gets a fair chance to execute.

4. Architectural Neutral

Our mechanism must be architectural natural. It means that if our solution is working fine on
one architecture then it should also run on the other ones as well.

Synchronization Mechanism
A synchronization mechanism is a technique used in operating systems to control the access
of multiple processes or threads to shared resources, ensuring data consistency and
preventing race conditions. Synchronization mechanisms are fundamental tools in concurrent
programming, used to manage shared resources and prevent race conditions. They
coordinate access to critical sections of code where shared data is modified.

Solutions to Process Synchronization Problems

In a multiprogramming environment, multiple processes often compete for shared resources

like memory, CPU, or files. If not managed properly, this leads to race conditions where the
final output depends on the order of execution. To avoid such issues, process synchronization
techniques are used.

The three major approaches are:

1. Interrupt Disable

2. Lock (Software-based & Hardware-based)

3. Operating System (OS)-based Solutions

1. Interrupt Disable

 This method allows a process to disable all hardware interrupts before entering its
critical section.

 Since no interrupts can occur, the running process cannot be preempted. It executes
its critical section without interference.

2. Lock(Software-based & Hardware-based)

Locks ensure that only one process at a time can enter the critical section. A process must
“acquire” the lock before entering, and “release” it after exiting. If another process tries to
enter while the lock is held, it must wait.

Locks can be implemented in two ways:

(a) Software-Based Locks

Software-based locks are implemented using algorithms that rely on shared variables
(like flags, turn variables, or ticket numbers) to coordinate access to the critical
section. These solutions try to ensure mutual exclusion without depending on
hardware instructions.

Eg: Peterson’s Algorithm, Dekker’s Algorithm, Bakery Algorithm

(b) Hardware-Based Locks

Modern CPUs provide special atomic instructions that make lock implementation
easier and faster. Atomic means indivisible operation. Once an atomic instruction
starts, it finishes completely before anything else (like another process or interrupt)
can occur. This ensures that no two processes can modify the same lock at the same
time.
  Test-and-Set (TSL): Tests the lock’s old value and sets it to “locked” in one
unbreakable step.
 Compare-and-Swap (CAS): Compares a memory value with an expected value
and, if equal, swaps it with a new value atomically.
 Spinlocks: Built using TSL or CAS; processes “spin” (busy wait) until the lock
becomes free. Very fast for short waits but wastes CPU cycles for long waits.
 Mutex (Mutual Exclusion Lock)

A mutex is a higher-level lock abstraction often built on top of hardware primitives

like spinlocks. Unlike raw locks, a mutex doesn’t always require busy waiting:

 If the mutex is unavailable, the process is blocked and put to sleep until
the lock is released. This avoids wasting CPU cycles compared to spinlocks.

3. Operating System (OS)-based Solutions

Operating Systems introduced more powerful synchronization tools: Semaphores and

Monitors. These are built on top of lock-based mechanisms but provide extra control, safety
and ease of use.

(a) Semaphores

 A semaphore is an integer variable accessed with two atomic operations:

 wait() (decrement, block if < 0)

 signal() (increment, wake one waiting process)

 Removes busy waiting by blocking processes when resources are unavailable.

(b) Monitors

 A monitor is a higher-level construct that combines mutual exclusion and condition

variables.

 Only one process can execute in a monitor at a time, ensuring safety automatically.

 Condition variables (wait, signal) simplify coordination between processes.

Test-and-Set Instruction (Hardware Solution for Synchronization)
Test-and-Set is a hardware solution for process synchronization that uses a special atomic
instruction to ensure mutual exclusion.A shared boolean variable lock is used.

 lock = false → critical section is free

 lock = true → critical section is busy

Working of Test-and-Set

To enter the critical section:

 The process checks the lock.

 If the lock is true, the process waits (busy waiting).

 If the lock is false, the process sets the lock to true and enters the critical section.

 After executing the critical section, the process sets lock = false.

Test-and-Set Function (Atomic)

boolean test_and_set(boolean *L)

boolean prev = *L;

*L = true;

return prev;

Critical Section Code Using Test-and-Set

while (true)

while (test_and_set(&lock)) ; // busy waiting

/* critical section */

lock = false;

/* remainder section */

}
Compare-and-Swap

Compare-and-Swap is an atomic hardware instruction that compares the value of a memory

location with an expected value and, if they are equal, updates the memory location with a
new value in a single indivisible operation, thereby ensuring mutual exclusion.

lock = 0 → free

lock = 1 → busy

Working of Compare and Swap

1. A shared variable (lock) is used.

lock = 0 → free

lock = 1 → busy

2. A process calls the compare-and-swap instruction with:

 memory address of lock

 expected value (0)

 new value (1)

3. The instruction compares the current value of lock with the expected value.

4. If both values are equal:

 lock is updated to 1

 process enters the critical section

5. If both values are not equal:

 no change is made to lock

 process keeps waiting (busy waiting)

6. After executing the critical section:

 process resets lock to 0

 other waiting processes may enter

Compare-and-Swap Function

int compare_and_swap(int *value, int expected,int new_value)

int old = *value;

if (*value == expected)

*value = new_value;

return old;

Critical Section Using CAS

while (true)

while (compare_and_swap(&lock, 0, 1) != 0) ;

/* critical section */

lock = 0;

/* remainder section */

}
Using queues: Sleeping instead of Spinning – Mutex Lock
Mutex Lock
A mutex lock is a synchronization mechanism that ensures only one process or thread enters
the critical section at a time. A mutex lock is a mutual exclusion mechanism that blocks
processes and uses a waiting queue to allow only one process to enter the critical section at
a time.

Working of Mutex Lock

1. A process requests the mutex.

2. If the mutex is free → the process acquires it and enters the critical section.

3. If the mutex is busy → the process is blocked (put to sleep) and placed in a waiting
queue.

4. When the mutex is released:

o One waiting process is woken up

o It acquires the mutex and enters the critical section.

Key Characteristics

 No busy waiting (unlike spinlocks)

 Uses a queue for waiting processes
 Saves CPU cycles
 Provides fairness (often FIFO order)
 Suitable for long critical sections

Mutex Lock (Mutual Exclusion Lock)

do
 The process runs in an infinite loop.
{
 Before entering the critical section, it calls acquire(&lock).
acquire(&lock);  After finishing the critical section, it calls release(&lock).
 This ensures mutual exclusion.
/* Critical Section */

release(&lock);

} while (true);
Acquire lock Function
 *lock = 0 → lock is free
acquire(*lock)  *lock = 1 → lock is busy
 while (*lock != 0);
{ o If lock is busy, the process keeps waiting
(busy waiting).
while (*lock != 0) ;  When lock becomes free (0),
o the process sets *lock = 1
*lock = 1; o and enters the critical section.

Release Lock Function

release(*lock)  After leaving the critical section,

 the process sets *lock = 0
{  This releases the lock so another process can enter.
*lock = 0;

}
SEMAPHORE
A semaphore is a synchronization tool used to control access to a shared resource by multiple
processes in a concurrent system (such as a multitasking operating system).

 It can be thought of as a special variable that controls how many processes can access
a resource at the same time.
 Semaphores help prevent problems like race conditions by controlling when and how
processes access shared data.
 A semaphore works by maintaining a counter that controls access to a specific
resource, ensuring that no more than the allowed number of processes access the
resource simultaneously.

Example 1: Traffic Signal

 Consider a one-lane bridge that allows only one car at a time.

 A binary semaphore ensures that only one car passes at a time.

Example 2: Printer

 Only one person/process can use the printer at a time.

 This is controlled using a binary semaphore.

Working of Semaphores
Semaphores operate using two main operations:

1. Wait Operation (P operation)

 Decreases the semaphore value by 1.

 If the value becomes less than 0, the process waits (is blocked).

 Wait operation checks whether a resource is available. If not, the process must wait.

2. Signal Operation (V operation)

 Increases the semaphore value by 1.

 If the value is greater than or equal to 0, a waiting process can enter.

 Signal operation releases the resource and wakes up waiting processes.

Pseudo Code for Semaphore Operations

wait(S)

while (S <= 0);

S = S - 1;

signal(S)

S = S + 1;

Types of Semaphores

1. Binary Semaphore

 Value is either 0 or 1.

 Works like a lock/unlock mechanism.

 Example: Only one process can use a printer at a time.

 Used to solve critical section problems where only one process is allowed access.

Example: Binary Semaphore (S = 1)

while (true)

wait(S);

// Critical Section

signal(S);

Only one process can execute the critical section at any time.
2. Counting Semaphore

 Value can be greater than 1.

 Controls access to a resource with multiple instances.

 Example: If a parking lot has 5 spaces, up to 5 cars can enter.

 Used when multiple identical resources are available.

Example: Counting Semaphore (S = 3)

semaphore S = 3;

wait(S);

// use resource

signal(S);

Up to three processes can access the resource concurrently.