Modern operating systems execute multiple processes and threads concurrently. These concurrent execution units often share:

• Memory

• Files

• Devices

• Buffers

• Data structures

When multiple threads or processes access shared resources simultaneously, serious problems may occur:

• Race conditions

• Data corruption

• Inconsistent states

• Deadlocks

To prevent these issues, operating systems use:

Synchronization mechanisms

One of the most important synchronization mechanisms is:

Semaphore

Semaphores are fundamental to:

• Operating systems

• Concurrent programming

• Multithreading

• Distributed systems

• Process synchronization

Understanding semaphores is extremely important because they provide the foundation for:

• Mutual exclusion

• Resource coordination

• Process synchronization

• Critical section protection

What is a Semaphore?

A semaphore is a synchronization variable used to control access to shared resources in concurrent systems.

A semaphore maintains:

• Integer value

• Queue of waiting processes/threads

Semaphores coordinate execution among concurrent entities safely.

Core Idea

Semaphores synchronize concurrent processes and threads using signaling operations

Important Insight

Semaphores prevent simultaneous unsafe access to shared resources

Why Semaphores are Necessary

Suppose two threads execute:

counter++;

Simultaneously.

Without synchronization:

• Both may read same old value

• Updates lost

Result:

• Incorrect final value

This problem called:

Race Condition

Semaphores solve this by:

• Controlling access order

Critical Section Problem

Very important OS concept.

Critical Section

Code segment accessing:

• Shared resources

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

Example

balance = balance - amount;

Banking systems require:

• Safe concurrent access

Requirements of Critical Section Solution

1. Mutual Exclusion

Only one process enters critical section.

2. Progress

Processes should not wait forever unnecessarily.

3. Bounded Waiting

No starvation.

Semaphore Structure

A semaphore contains:

• Integer counter

• Waiting queue

Counter Meaning

Represents:

• Available resources
  or

• Synchronization state

Semaphore Operations

Semaphores mainly support two atomic operations:

1. wait() Operation

Also called:

• P()

• down()

Function

Attempts to acquire resource.

Operation

S = S - 1

If result negative:

• Process/thread blocked

Pseudocode

wait(S):
    S = S - 1
    if S < 0:
        block process

2. signal() Operation

Also called:

• V()

• up()

Function

Releases resource.

Operation

S = S + 1

If waiting processes exist:

• Wake one process

Pseudocode

signal(S):
    S = S + 1
    if S <= 0:
        wake waiting process

Important Insight

Semaphore operations must execute atomically to avoid synchronization errors

Atomic Operations

Semaphore operations cannot be interrupted midway.

Reason:

• Concurrent updates would break correctness

OS ensures:

• Atomic execution

using:

• Hardware instructions

• Interrupt disabling

• Spinlocks

Binary Semaphore

Binary semaphore values:

• 0

• 1

Works similarly to:

Mutex lock

Example

1 → resource available
0 → resource occupied

Workflow

Step 1

Thread executes:

• wait()

Semaphore becomes:

• 0

Step 2

Other threads attempting wait():

• Blocked

Step 3

Thread executes:

• signal()

Semaphore returns:

• 1

Advantages

• Simple mutual exclusion

Counting Semaphore

Counting semaphore:

• Can hold values greater than 1

Used when:

• Multiple identical resources available

Example

Suppose:

• 5 printers

Semaphore initialized to:

5

Each printer request:

• wait()

Printer release:

• signal()

Important Insight

Counting semaphores manage pools of multiple shared resources

Busy Waiting vs Blocking Semaphores

Busy Waiting

Process repeatedly checks semaphore.

Example:

while(S <= 0);

Problems:

• Wastes CPU cycles

Spinlocks

Busy-wait synchronization primitive.

Useful for:

• Very short waiting times

Blocking Semaphores

Waiting processes:

• Put to sleep

Advantages:

• Better CPU efficiency

Modern operating systems usually prefer:

• Blocking synchronization

Producer-Consumer Problem

Classic semaphore synchronization problem.

Scenario

Producer

Adds items to shared buffer.

Consumer

Removes items.

Problems

Need synchronization to prevent:

• Buffer overflow

• Buffer underflow

• Concurrent corruption

Solution Uses Three Semaphores

mutex

Protects critical section.

empty

Tracks empty slots.

full

Tracks filled slots.

Workflow

Producer:

1. wait(empty)

2. wait(mutex)

3. Add item

4. signal(mutex)

5. signal(full)

Consumer:

1. wait(full)

2. wait(mutex)

3. Remove item

4. signal(mutex)

5. signal(empty)

Readers-Writers Problem

Another classic synchronization problem.

Readers

Only read shared data.

Writers

Modify shared data.

Goals:

• Multiple readers allowed simultaneously

• Writers require exclusive access

Semaphores coordinate:

• Access ordering

Dining Philosophers Problem

Famous synchronization problem.

Illustrates:

• Deadlocks

• Resource allocation issues

Philosophers need:

• Two forks

Incorrect semaphore usage may cause:

• Circular waiting

Semaphores and Deadlocks

Improper semaphore ordering may cause:

Deadlock

Example

Thread A:

• Holds Resource 1

• Waits for Resource 2

Thread B:

• Holds Resource 2

• Waits for Resource 1

Both blocked forever.

Important Insight

Incorrect semaphore usage can introduce deadlocks and starvation

Starvation Problem

Some threads may:

• Wait indefinitely

if scheduler repeatedly favors others.

Priority Inversion

Important scheduling issue.

Low-priority thread holds semaphore.
High-priority thread waits.

Medium-priority thread keeps running.

Result:

• High-priority thread indirectly blocked.

Solution

Priority inheritance protocols.

Semaphore Implementation in Operating Systems

OS maintains:

• Semaphore value

• Waiting queue

Kernel handles:

• Blocking

• Wakeup

• Scheduling

Linux Semaphores

Linux supports:

• Kernel semaphores

• POSIX semaphores

POSIX Semaphore APIs

sem_init()

Initialize semaphore.

sem_wait()

Acquire semaphore.

sem_post()

Release semaphore.

Example

sem_wait(&sem);
/* critical section */
sem_post(&sem);

Semaphores vs Mutexes

Students commonly confuse these.

Mutex

Typically:

• Lock/unlock by same thread

Semaphore

Can signal between:

• Different threads/processes

Important Insight

Semaphores are more general synchronization mechanisms than mutexes

Real-World Example

Suppose database server handles:

• Thousands of concurrent transactions

Semaphores coordinate:

• Shared buffers

• Connection pools

• Disk access

• Transaction synchronization

Without semaphores:

• Data corruption likely

Advantages of Semaphores

1. Synchronization

Coordinates concurrent execution.

2. Resource Management

Controls limited resources.

3. Mutual Exclusion

Protects critical sections.

4. Process Coordination

Supports producer-consumer workflows.

Problems with Semaphores

1. Deadlocks

Incorrect ordering dangerous.

2. Starvation

Some threads may wait indefinitely.

3. Debugging Complexity

Concurrency bugs difficult.

4. Priority Inversion

Scheduling complications.