Module 5

Synchronization Tools

1. Why Synchronization is Needed

When multiple processes or threads access shared data simultaneously, incorrect results may occur.

Synchronization ensures data consistency.

2. Race Condition

A race condition occurs when multiple processes access shared data at the same time and the final result depends on the timing of execution.

Example:
Two processes update the same variable simultaneously.

Result:
Data becomes incorrect.

3. Critical Section

A critical section is the part of a program where shared resources are accessed.

Example:

  • updating a shared variable

  • writing to a file.

Only one process should execute a critical section at a time.

4. Requirements of a Correct Critical Section Solution

Mutual Exclusion

Only one process can enter the critical section.

Progress

If no process is in the critical section, one waiting process should be allowed to enter.

Bounded Waiting

A process should not wait forever.

There must be a limit on waiting time.

5. Peterson’s Solution

Peterson’s algorithm solves the critical section problem for two processes.

It uses:

  • a turn variable

  • flag variables

Purpose:
Control which process enters the critical section.

However, this solution may not work correctly on modern processors due to instruction reordering.

6. Memory Barrier

A memory barrier ensures that memory operations occur in the correct order.

It prevents processors from reordering instructions.

This ensures correct synchronization.

7. Hardware Support for Synchronization

Modern systems use special hardware instructions.

Examples:

Test-and-Set

Checks a variable and sets it simultaneously.

Used for locking.

Compare-and-Swap

Compares a value with an expected value and replaces it if they match.

This operation is atomic.

8. Atomic Variables

Atomic variables allow operations that cannot be interrupted.

Example:
Atomic increment operation.

This ensures data is updated safely.

9. Mutex Locks

A mutex (mutual exclusion) lock ensures that only one process enters the critical section.

Steps:

  1. Acquire the lock

  2. Execute critical section

  3. Release the lock

Problem:
May cause busy waiting (process repeatedly checks lock).

10. Semaphores

A semaphore is a synchronization tool represented by an integer variable.

It supports two operations:

wait()

Decreases the semaphore value.

signal()

Increases the semaphore value.

Types of Semaphores

Binary Semaphore

  • values: 0 or 1

  • similar to a mutex lock.

Counting Semaphore

  • can have multiple values

  • used when multiple resources exist.

11. Monitors

A monitor is a high-level synchronization construct.

Characteristics:

  • shared variables are inside the monitor

  • only one process can execute inside it at a time.

This simplifies synchronization.

12. Condition Variables

Condition variables allow processes to wait for certain conditions.

Operations:

wait()

Process goes to sleep.

signal()

Wake up a waiting process.

13. Liveness Problems

Liveness refers to whether processes continue making progress.

Problems include:

Deadlock

Processes wait forever for each other.

Starvation

A process never receives resources.

Priority Inversion

A low-priority process blocks a high-priority process.