How PV Operations Solve Concurrency: Semaphores, Mutex & Producer-Consumer

What Is a Semaphore?

A semaphore is an integer combined with two atomic operations, proposed by Dijkstra in 1972. The names P and V come from Dutch: Prolaag (try to decrease) and Verhoog (increase). A semaphore represents the "resource count".

Semaphore Types

1. Binary semaphore
   - Value only 0 or 1
   - Equivalent to a mutex lock

2. Counting semaphore
   - Value can be any non-negative integer
   - Represents resource quantity

P Operation (wait)

Definition

void P(Semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // Resource insufficient, block process
        add_to_blocked_queue(S, current_process);
        block(); // Block current process
    }
}

Intuitive Understanding

P operation = attempt to "take" one resource.

Resource count = 3, currently 3 available

After P:
Resource count = 2, still 2 available ✓

Another P:
Resource count = 1, still 1 available ✓

Another P:
Resource count = 0, no resources left
Another P:
Resource count = -1, someone is blocked!

P Operation Illustration

Semaphore S = 3;

Time 1: S = 3 → P → S = 2 [process continues]
Time 2: S = 2 → P → S = 1 [process continues]
Time 3: S = 1 → P → S = 0 [process continues]
Time 4: S = 0 → P → S = -1 [process blocked!]

When resource released, S may return to 0
Blocked process will be awakened

V Operation (signal)

Definition

void V(Semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // Process waiting, wake one up
        Process *p = remove_from_blocked_queue(S);
        wake_up(p); // Wake process
    }
}

Intuitive Understanding

V operation = "return" one resource.

Current S = -1 (someone waiting)

After V:
S = 0, wake one waiting process
Process moves from blocked queue to ready queue

V Operation Illustration

Current S = -2 (2 processes blocked)

After V:
S = -1
Wake one process, 1 still blocked

Another V:
S = 0
Wake last process

Another V:
S = 1
No process waiting, resource count +1

Practical Applications of PV Operations

Application 1: Mutual Exclusion

Semaphore mutex = 1; // Mutex semaphore, initial 1

// Process P1
P(&mutex);
// Critical section (only one process can enter)
V(&mutex);

// Process P2
P(&mutex);
// Critical section
V(&mutex);

Working principle:
1. Initial: mutex = 1
2. P1 executes P, mutex = 0, P1 enters critical section
3. P2 executes P, mutex = -1, P2 blocks
4. P1 executes V, mutex = 0, wakes P2
5. P2 enters critical section
6. P2 executes V, mutex = 1, restores initial

Application 2: Sequential Synchronization

Semaphore S = 0; // Initial 0, means "not done"

void process_A() {
    // Step 1
    // ...
    V(&S); // Notify B can continue
}

void process_B() {
    P(&S); // Wait for A's notification
    // Step 2
}

Scenario: Process B must wait for Process A to complete something

1. Initial S = 0
2. B executes P, S = -1, B blocks!
3. A executes V, S = 0, wakes B
4. B continues execution

Application 3: Resource Counting (Producer-Consumer)

Semaphore empty = 10; // 10 empty slots
Semaphore full = 0;   // 0 full slots
Semaphore mutex = 1;  // Mutual exclusion

void producer() {
    int item;
    while (TRUE) {
        item = produce();
        P(&empty);        // Wait for empty slot
        P(&mutex);        // Mutex access
        put_item(item);   // Put into buffer
        V(&mutex);
        V(&full);         // Increase full slot count
    }
}

void consumer() {
    int item;
    while (TRUE) {
        P(&full);         // Wait for full slot
        P(&mutex);
        item = get_item(); // Take out
        V(&mutex);
        V(&empty);        // Increase empty slot count
        consume(item);
    }
}

Producer-Consumer Problem Detailed

Problem Description

Producer: produces items, puts into buffer
Consumer: takes items, consumes

Constraints:
- Buffer full: producer cannot put
- Buffer empty: consumer cannot take
- Mutex access to buffer

Complete Code

#define N 5
Semaphore empty = N;  // Empty slots
Semaphore full = 0;   // Full slots
Semaphore mutex = 1;  // Mutex access

int buffer[N];
int in = 0, out = 0;

void producer() {
    while (TRUE) {
        int item = produce_item();

        P(&empty);              // Wait for empty
        P(&mutex);              // Enter critical section
        buffer[in] = item;
        in = (in + 1) % N;
        V(&mutex);              // Leave critical section
        V(&full);               // One more product

        sleep(random() % 3);
    }
}

void consumer() {
    while (TRUE) {
        P(&full);               // Wait for product
        P(&mutex);
        int item = buffer[out];
        out = (out + 1) % N;
        V(&mutex);
        V(&empty);              // One more empty
        consume_item(item);

        sleep(random() % 3);
    }
}

Execution Timeline

Timeline:
T1: Producer P(empty) → empty = 4
T2: Producer P(mutex) → mutex = 0
T3: Producer puts product
T4: Producer V(mutex) → mutex = 1
T5: Producer V(full) → full = 1

T6: Consumer P(full) → full = 0
T7: Consumer P(mutex) → mutex = 0
T8: Consumer takes product
T9: Consumer V(mutex) → mutex = 1
T10: Consumer V(empty) → empty = 5

PV Operation Caveats

1. P and V Must Be Paired

// Correct
P(&mutex);
// Critical section
V(&mutex);

// Wrong: P and V not paired
P(&mutex);
// Critical section
// Forgot V, resource never released!

2. P Order Matters

// Mutex and resource semaphore
Semaphore mutex = 1;
Semaphore empty = N;

// Good order: resource first, then mutex
P(&empty);
P(&mutex);

// Bad order: mutex first, then resource
P(&mutex);
P(&empty);
// May cause deadlock!

3. Cannot Block Inside Critical Section

// Wrong example
P(&mutex);
// Inside critical section, P another semaphore?
// If blocks, other processes also cannot enter mutex
V(&mutex);

PV Operations vs Monitors

What Is a Monitor?

Monitor = Encapsulated synchronization abstraction

Encapsulates shared variables and operations together
Automatically guarantees mutual exclusion

Equivalent to high-level language's "auto-lock"

monitor BankAccount {
    int balance = 0;

    procedure deposit(amount) {
        balance = balance + amount;
    }

    procedure withdraw(amount) {
        if (balance >= amount) {
            balance = balance - amount;
        }
    }
}

PV vs Monitor Comparison

PV:
- Requires programmer to manually lock/unlock
- High flexibility
- Error-prone

Monitor:
- Compiler automatically locks
- High safety
- Limited expressiveness

Summary: Two Core PV Operations

P operation (wait):
- Request resource
- Decrement resource count
- Block if insufficient

V operation (signal):
- Release resource
- Increment resource count
- Wake waiter if any

Semaphore types:
- Binary semaphore: mutex lock
- Counting semaphore: resource counting

Typical applications:
- Mutual exclusion: mutex = 1
- Synchronization: semaphore initial 0 or N

Remember : P is "take", V is "give back". Can't take? Wait. Gave back and someone waiting? Wake them! That's the essence of PV operations!

Key Points :

P operation = wait = request resource, value--, block if < 0

V operation = signal = release resource, value++, wake if <= 0

Binary semaphore can be used for mutual exclusion

Counting semaphore can be used for resource management

PV operations must be used in pairs