[OS Concepts] 06. Process Synchronization Tools

// Race condition example: Two threads incrementing shared variable count
// Initial value of count is 5

// Thread A: count++
// Internally:
//   register_A = count        (register_A = 5)
//   register_A = register_A + 1  (register_A = 6)
//   count = register_A        (count = 6)

// Thread B: count++
// Internally:
//   register_B = count        (register_B = 5)
//   register_B = register_B + 1  (register_B = 6)
//   count = register_B        (count = 6)

// Interleaved execution scenario:
// T0: A sets register_A = count         (register_A = 5)
// T1: A sets register_A = register_A + 1 (register_A = 6)
// T2: B sets register_B = count         (register_B = 5)  <-- still 5!
// T3: B sets register_B = register_B + 1 (register_B = 6)
// T4: A sets count = register_A         (count = 6)
// T5: B sets count = register_B         (count = 6)
// Result: count = 6 (not the expected 7!)

[Process Structure]

do {
    [Entry Section]
        -- Request permission to enter critical section --

    [Critical Section]
        -- Access shared data --

    [Exit Section]
        -- Notify completion of critical section usage --

    [Remainder Section]
} while (true);

// Peterson's Solution (two processes i, j)
int turn;           // Whose turn it is
bool flag[2];       // Intent to enter critical section

// Code for process i
void process_i() {
    while (true) {
        flag[i] = true;     // I (i) want to enter
        turn = j;           // Yield to the other (j)
        while (flag[j] && turn == j)
            ;               // Wait if the other wants it and it's their turn

        // Critical section
        // ... access shared data ...

        flag[i] = false;    // I'm done

        // Remainder section
    }
}

// Memory barrier usage example
// Thread 1
while (!flag)
    memory_barrier();  // Ensures flag read is not reordered before this point
print(x);

// Thread 2
x = 100;
memory_barrier();      // Ensures x write completes before flag write
flag = true;

// CAS logic (actually a single atomic instruction)
bool compare_and_swap(int *value, int expected, int new_value) {
    if (*value == expected) {
        *value = new_value;
        return true;
    }
    return false;
}

// Atomic increment using CAS
void atomic_increment(int *counter) {
    int old_val;
    do {
        old_val = *counter;
    } while (!compare_and_swap(counter, old_val, old_val + 1));
    // Retry until successful
}

// Mutual exclusion using CAS
int lock = 0;

void acquire() {
    while (!compare_and_swap(&lock, 0, 1))
        ;  // Change lock from 0 (available) to 1 (in use)
}

void release() {
    lock = 0;
}

// C11 atomic variables
#include <stdatomic.h>

atomic_int counter = 0;

void increment() {
    atomic_fetch_add(&counter, 1);  // Atomic increment
}

// Java atomic variables
// import java.util.concurrent.atomic.AtomicInteger;
// AtomicInteger counter = new AtomicInteger(0);
// counter.incrementAndGet();  // Atomic increment

// Mutex usage pattern
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void critical_section() {
    pthread_mutex_lock(&mutex);     // Acquire lock

    // Critical section
    // Access shared data

    pthread_mutex_unlock(&mutex);   // Release lock
}

[Mutex Operation]

Thread A                   Thread B
   |                          |
   |-- lock() success --      |
   |   (enter critical)       |-- lock() attempt
   |   access shared data     |   (waiting/blocked)
   |                          |   ...
   |-- unlock() ---------     |
   |                    ----->|-- lock() success
   |                          |   (enter critical)
   |                          |   access shared data
   |                          |-- unlock()

// Spinlock implementation (CAS-based)
typedef struct {
    atomic_flag flag;
} spinlock_t;

void spin_lock(spinlock_t *lock) {
    while (atomic_flag_test_and_set(&lock->flag))
        ;  // Repeat until locked (busy waiting)
}

void spin_unlock(spinlock_t *lock) {
    atomic_flag_clear(&lock->flag);
}

// Basic semaphore operations (atomic)
wait(S) {          // P operation or acquire
    while (S <= 0)
        ;          // Wait
    S--;
}

signal(S) {        // V operation or release
    S++;
}

// Counting semaphore usage: Maximum 5 concurrent connections
#include <semaphore.h>

sem_t connection_pool;

void init() {
    sem_init(&connection_pool, 0, 5);  // Initial value 5
}

void handle_request() {
    sem_wait(&connection_pool);    // Acquire connection (decrease count)

    // Perform database operation
    // ...

    sem_post(&connection_pool);    // Return connection (increase count)
}

// Guarantee S1 executes before S2
sem_t sync_sem;
sem_init(&sync_sem, 0, 0);  // Initial value 0

// Process 1
void process1() {
    S1;                     // Statement to execute first
    sem_post(&sync_sem);    // signal
}

// Process 2
void process2() {
    sem_wait(&sync_sem);    // wait (wait until S1 completes)
    S2;                     // Execute after S1
}

typedef struct {
    int value;
    struct list_head waiting_list;  // List of waiting processes
} semaphore;

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // Add current process to waiting list
        add_to_list(&S->waiting_list, current_process);
        block();  // Switch process to waiting state
    }
}

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // Wake up one process from the waiting list
        process *P = remove_from_list(&S->waiting_list);
        wakeup(P);  // Switch P to ready state
    }
}

[Monitor Structure]

+------------------------------------+
|           monitor                  |
|                                    |
|  Shared Data                       |
|  +-----------+                     |
|  | Variables  |                     |
|  +-----------+                     |
|                                    |
|  Condition Variables               |
|  condition x, y;                   |
|                                    |
|  procedure P1() { ... }           |
|  procedure P2() { ... }           |
|  procedure P3() { ... }           |
|                                    |
|  Initialization code               |
|                                    |
+------------------------------------+
      ^          ^          ^
      |          |          |
   Thread1    Thread2    Thread3
   (only one at a time inside the monitor)

// Monitor pattern in Java (synchronized keyword)
public class BoundedBuffer {
    private final Object[] buffer;
    private int count = 0;
    private int in = 0;
    private int out = 0;

    public BoundedBuffer(int size) {
        buffer = new Object[size];
    }

    // synchronized: Only one thread can execute at a time
    public synchronized void produce(Object item)
            throws InterruptedException {
        while (count == buffer.length) {
            wait();  // Wait if buffer is full
        }

        buffer[in] = item;
        in = (in + 1) % buffer.length;
        count++;

        notifyAll();  // Wake up waiting consumers
    }

    public synchronized Object consume()
            throws InterruptedException {
        while (count == 0) {
            wait();  // Wait if buffer is empty
        }

        Object item = buffer[out];
        out = (out + 1) % buffer.length;
        count--;

        notifyAll();  // Wake up waiting producers
        return item;
    }
}

// Pthreads condition variable usage
#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int ready = 0;

// Waiting thread
void *waiter(void *arg) {
    pthread_mutex_lock(&mutex);

    while (!ready) {
        // Wait until condition is met
        // Releases mutex while waiting, reacquires on wakeup
        pthread_cond_wait(&cond, &mutex);
    }

    printf("Condition met! Proceeding.\n");
    pthread_mutex_unlock(&mutex);
    return NULL;
}

// Signaling thread
void *signaler(void *arg) {
    pthread_mutex_lock(&mutex);

    ready = 1;
    pthread_cond_signal(&cond);  // Wake up waiting thread

    pthread_mutex_unlock(&mutex);
    return NULL;
}

[Deadlock Example]

Thread A                    Thread B
lock(mutex1);              lock(mutex2);
  // holds mutex1              // holds mutex2
lock(mutex2);              lock(mutex1);
  // waits for mutex2!         // waits for mutex1!
  // Each waits for the other's resource -> deadlock

Solution: Always acquire resources in the same order
Thread A                    Thread B
lock(mutex1);              lock(mutex1);  // Same order
lock(mutex2);              lock(mutex2);

[Priority Inversion Scenario]

Priority: H > M > L

1. L acquires resource R and is running
2. H arrives, requests R -> waits because L holds R
3. M arrives, preempts L -> M runs
4. H needs L to release R, but L is preempted by M
5. Result: M runs before H! (priority inversion)

Solution: Priority inheritance protocol
L inherits H's priority while holding R
-> L is not preempted by M -> L releases R quickly