Critical Resources and Mutual Exclusion

Resources that require processes to access them in a mutually exclusive manner are termed critical resources.

Principles of Synchronization Mechanisms

• Wait if idle: Allow entry when the resource is free.
• Busy then wait: Block entry while the resource is occupied.
• Bounded waiting: Guarantee that no process waits indefinitely.
• Yield while waiting: A waiting process should release the CPU rather than busy-looping.

Hardware-Based Synchronization: Disabling Interrupts

By turning off interrupts, a process can guarantee that its critical section will not be preempted.

Drawbacks:

• Increases system risk; a malicious or erroneous process could monopolize the CPU.
• Only applicable in uniprocessor environments.

Hardware-Based Synchronization: Test-and-Set (TSL)

This atomic instruction records the current lock state, sets the lock to occupied, and returns the previous state.

bool test_and_set(bool *mutex_flag) {
    bool previous_state = *mutex_flag;
    *mutex_flag = true;
    return previous_state;
}

Usage in a spinlock pattern:

while (true) {
    // Other operations...
    while (test_and_set(&mutex_flag)) {
        // Spin until the lock is released
    }
    // Critical section entry
    // Execute mutually exclusive operations
    mutex_flag = false;
    // Critical section exit
    // Remainder section
}

Hardware-Based Synchronization: Swap

The Swap instruction atomically exchanges the values of two memory words.

void exchange_state(bool *ptr1, bool *ptr2) {
    bool temp_val = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp_val;
}

Usage for mutual exclusion:

while (true) {
    bool intent_flag = true;
    do {
        exchange_state(&mutex_flag, &intent_flag);
    } while (intent_flag != false);
    // Critical section entry
    // Execute mutually exclusive operations
    mutex_flag = false;
    // Remainder section
}

Semaphore Mechanisms

A semaphore represents the quantity of available instances of a specific system resource.

• Integer semaphore: Tracks resource count, supporting only initialization, wait (P), and signal (V) operations.
• Structured (Record-type) semaphore: Utilizes a data structure combining a counter and a process waiting queue.
• Semaphore sets: Allows requesting multiple units across various resource categories simultaneously.

Integer Semaphore

Initialized to a non-negative integer. The P and V operations are defined as:

void acquire(int &sem) {
    while (sem <= 0) { /* busy wait */ }
    sem--;
}

void release(int &sem) {
    sem++;
}

Structured Semaphore

Defined using a record structure to handle both the resource count and blocked processes.

typedef struct {
    int resource_count;
    ProcessControlBlock *blocked_queue;
} SyncSemaphore;

The resource_count reflects available resources when positive, or the count of waiting processes when negative. The blocked_queue links to the PCBs of suspended processes.

void acquire(SyncSemaphore *sem) {
    sem->resource_count--;
    if (sem->resource_count < 0) {
        suspend_process(sem->blocked_queue);
    }
}

void release(SyncSemaphore *sem) {
    sem->resource_count++;
    if (sem->resource_count <= 0) {
        resume_process(sem->blocked_queue);
    }
}

AND Semaphores

Used when a process requires simultaneous allocation of multiple resource types to proceed.

void acquire_all(SyncSemaphore *sem_array[], int count) {
    while (true) {
        bool all_available = true;
        for (int i = 0; i < count; i++) {
            if (sem_array[i]->resource_count < 1) {
                all_available = false;
                suspend_process(sem_array[i]->blocked_queue);
                // Restart acquisition attempt upon wakeup
                break;
            }
        }
        if (all_available) {
            for (int i = 0; i < count; i++) {
                sem_array[i]->resource_count--;
            }
            break;
        }
    }
}

Semaphore Sets

Processes can request multiple units of multiple resource types. acquire_set(S1, t1, d1, ..., Sn, tn, dn) allocates d1 units of S1 only if S1 has at least t1 units available.

Special cases:

• acquire_set(S, d, d): Requests d units; fails if fewer than d are available.
• acquire_set(S, 1, 1): Behaves as a standard mutex if S=1, or a counting semaphore if S>1.
• acquire_set(S1, 1, 1, S2, 1, 1): Equivalent to an AND semaphore.
• acquire_set(S, 1, 0): Functions as a conditional switch (checking availability without consuming it).

Applying Semaphores for Mutual Exclusion

Define a mutex semaphore initialized to 1. Wrap critical sections with acquire(mutex) and release(mutex).

Applying Semaphores for Precedence Relations

To enforce execution order P1 -> P2, introduce a semaphore sync_var initialized to 0. P1 calls release(sync_var) after its task, and P2 calls acquire(sync_var) before its task.

SyncSemaphore sync_var = 0;

void task1() {
    execute_step1();
    release(sync_var);
}

void task2() {
    acquire(sync_var);
    execute_step2();
}

void main() {
    parallel_begin(task1(), task2());
    parallel_end();
}

The parallel_begin and parallel_end constructs allow concurrent execution, while the semaphore enforces the required sequence.

Classic Synchronization Problems

Producer-Consumer Problem

Producer logic:

void producer() {
    while (true) {
        Data item = generate_item();
        acquire(empty_slots);
        acquire(access_mutex);
        storage[insert_idx] = item;
        insert_idx = (insert_idx + 1) % capacity;
        release(access_mutex);
        release(filled_slots);
    }
}

Consumer logic:

void consumer() {
    while (true) {
        acquire(filled_slots);
        acquire(access_mutex);
        Data item = storage[extract_idx];
        extract_idx = (extract_idx + 1) % capacity;
        release(access_mutex);
        release(empty_slots);
        process_item(item);
    }
}

Dining Philosophers Problem

SyncSemaphore utensils[5] = {1, 1, 1, 1, 1};

void philosopher(int idx) {
    while (true) {
        acquire(utensils[idx]);
        acquire(utensils[(idx + 1) % 5]);
        eat();
        release(utensils[idx]);
        release(utensils[(idx + 1) % 5]);
        think();
    }
}

Readers-Writers Problem

Basic solution with a single mutex allows concurrent reads but risks writer starvation.

SyncSemaphore entry_mutex = 1;

void reader() {
    acquire(entry_mutex);
    read_data();
    release(entry_mutex);
}

void writer() {
    acquire(entry_mutex);
    write_data();
    release(entry_mutex);
}

Introducing a reader count allows multiple readers but still requires a mutex to modify the count safely.

SyncSemaphore entry_mutex = 1;
SyncSemaphore count_mutex = 1;
int active_readers = 0;

void reader() {
    acquire(count_mutex);
    active_readers++;
    if (active_readers == 1) acquire(entry_mutex);
    release(count_mutex);

    read_data();

    acquire(count_mutex);
    active_readers--;
    if (active_readers == 0) release(entry_mutex);
    release(count_mutex);
}

void writer() {
    acquire(entry_mutex);
    write_data();
    release(entry_mutex);
}

Monitors as Synchronization Tools

A monitor is an abstract data type encapsulating shared data and the operations permitted on it, ensuring mutual exclusion.

monitor ResourceController {
    shared data declarations;
    condition variables;

    public void operation1() { /* ... */ }
    public void operation2() { /* ... */ }

    initialization_code() { /* ... */ }
}

Characteristics: Modular, abstract, inherently mutually exclusive (only one process active inside at a time).

Handling concurrent entry:

• Hoare: The awakening process yields immediately to the waiting process.
• Mesa: The waiting process must re-evaluate conditions upon waking.
• Hansen: The signal operation must be the final step in a monitor procedure.

Producer-Consumer using a monitor:

monitor BufferManager {
    Data queue[SIZE];
    int head, tail, count;
    condition not_full, not_empty;

    public void insert(Data val) {
        if (count >= SIZE) cwait(not_full);
        queue[tail] = val;
        tail = (tail + 1) % SIZE;
        count++;
        csignal(not_empty);
    }

    public Data extract() {
        if (count <= 0) cwait(not_empty);
        Data val = queue[head];
        head = (head + 1) % SIZE;
        count--;
        csignal(not_full);
        return val;
    }

    initialization_code() {
        head = 0; tail = 0; count = 0;
    }
} buffer_instance;

void producer() {
    while (true) {
        Data item = generate_item();
        buffer_instance.insert(item);
    }
}

void consumer() {
    while (true) {
        Data item = buffer_instance.extract();
        process_item(item);
    }
}

Inter-Process Communication (IPC)

IPC enables information exchange between processes.

• Low-level: Restricted to control signals, inefficient for bulk data.
• High-level: Supports substantial data transfers efficiently and transparently.

Message Passing Systems

Direct communication uses explicit naming:

• send(destination, message)
• receive(source, message)

Synchronization variants: Blocking send/blocking receive, Non-blocking send/blocking receive, Non-blocking both.

Message buffer queue implementation:

typedef struct {
    int origin_id;
    int length;
    char *payload;
    struct MsgBuffer *next;
} MsgBuffer;

Send primitive:

void dispatch_message(int target, MessageEnvelope env) {
    MsgBuffer *node = allocate_buffer(env.length);
    node->origin_id = env.origin_id;
    node->length = env.length;
    copy_payload(node->payload, env.payload);
    node->next = null;

    ProcessControlBlock *dest_pcb = find_pcb(target);
    acquire(dest_pcb->queue_mutex);
    append_buffer(dest_pcb->msg_queue, node);
    release(dest_pcb->queue_mutex);
    release(dest_pcb->msg_semaphore);
}

Receive primitive:

void fetch_message(MessageEnvelope env) {
    ProcessControlBlock *self_pcb = current_pcb();
    acquire(self_pcb->msg_semaphore);
    acquire(self_pcb->queue_mutex);
    MsgBuffer *node = remove_first(self_pcb->msg_queue);
    release(self_pcb->queue_mutex);

    env.origin_id = node->origin_id;
    env.length = node->length;
    copy_payload(env.payload, node->payload);
    free_buffer(node);
}

Indirect Communication (Mailboxes)

Processes communicate via shared intermediary entities known as mailboxes or ports.

Client-Server Systems

• Sockets: File-based (local) or network-based endpoints for bidirectional data streams.
• Remote Procedure Calls (RPC): Enables a client to invoke a procedure on a remote server host as if it were local.