Unit 4: Process Synchronization & Threads

Pseudocode
do {
    /* ENTRY SECTION — request permission to enter */

    CRITICAL SECTION
    /* Access shared resource here */

    /* EXIT SECTION — release the lock */

    REMAINDER SECTION
    /* Non-critical code */

} while (TRUE);

Pseudocode
// Shared variables
bool flag[2] = {false, false};  // flag[i] = true means process i wants to enter
int turn;                        // whose turn it is (tie-breaker)

// Process P_i (i = 0 or 1, j = 1 - i)
do {
    flag[i] = true;             // I want to enter
    turn = j;                    // But I give you the chance first
    while (flag[j] && turn == j)
        ;                        // Busy wait — spin until it's my turn

    /* CRITICAL SECTION */

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

    /* REMAINDER SECTION */
} while (TRUE);

Pseudocode
// Shared variables
bool choosing[n];     // choosing[i] = true means process i is picking a number
int number[n];        // number[i] = ticket number of process i (0 = not interested)

// Process P_i
do {
    choosing[i] = true;
    number[i] = 1 + max(number[0], ..., number[n-1]);  // Take next ticket
    choosing[i] = false;

    for (j = 0; j < n; j++) {
        while (choosing[j])
            ;   // Wait if process j is choosing
        while (number[j] != 0 &&
               (number[j], j) < (number[i], i))
            ;   // Wait if j has a smaller ticket (or same ticket but smaller ID)
    }

    /* CRITICAL SECTION */

    number[i] = 0;    // Done — release ticket

    /* REMAINDER SECTION */
} while (TRUE);

C-style Pseudocode
// This ENTIRE function executes atomically (hardware guarantee)
bool test_and_set(bool *target) {
    bool rv = *target;   // Save old value
    *target = true;      // Set to true
    return rv;            // Return old value
}

// Usage — mutual exclusion for any number of processes
bool lock = false;    // Shared lock variable

do {
    while (test_and_set(&lock))
        ;                // Spin until lock is acquired

    /* CRITICAL SECTION */

    lock = false;        // Release lock

    /* REMAINDER SECTION */
} while (TRUE);

How it works: If lock is false (free), TAS returns false (loop exits) and sets lock = true atomically. If lock is true (held), TAS returns true (keeps spinning).

C-style Pseudocode
// Executes atomically
int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

// Usage
int lock = 0;

do {
    while (compare_and_swap(&lock, 0, 1) != 0)
        ;                // Spin until lock acquired

    /* CRITICAL SECTION */

    lock = 0;

    /* REMAINDER SECTION */
} while (TRUE);

Advantage of CAS over TAS: CAS only modifies the value if it matches the expected value, making it more flexible. It's the foundation of lock-free data structures used in high-performance systems like Zerodha's trading engine.

Pseudocode
// P() operation — also called wait() or down()
P(S) {
    while (S <= 0)
        ;           // Wait (in practice: block/sleep)
    S--;
}

// V() operation — also called signal() or up()
V(S) {
    S++;
}

Key rule: Both P() and V() are atomic — they execute without interruption.

Pseudocode
monitor MonitorName {
    // Shared data — private to monitor
    int shared_var;

    // Condition variables
    condition x, y;

    // Procedures — only one can execute at a time
    procedure P1() {
        // ... access shared_var safely ...
        if (need_to_wait)
            x.wait();     // Suspend and release monitor
    }

    procedure P2() {
        // ... modify shared_var ...
        x.signal();          // Wake up one waiting process
    }

    // Initialization code
    init() { shared_var = 0; }
}

Pseudocode
// Shared
semaphore mutex = 1;       // Mutual exclusion for buffer access
semaphore empty = N;       // Count of empty slots (initially N)
semaphore full  = 0;       // Count of filled slots (initially 0)

// PRODUCER
do {
    // ... produce an item ...

    P(empty);      // Wait for an empty slot
    P(mutex);      // Lock the buffer

    // ... add item to buffer ...

    V(mutex);      // Unlock the buffer
    V(full);       // Signal that a filled slot is available
} while (TRUE);

// CONSUMER
do {
    P(full);       // Wait for a filled slot
    P(mutex);      // Lock the buffer

    // ... remove item from buffer ...

    V(mutex);      // Unlock the buffer
    V(empty);      // Signal that an empty slot is available

    // ... consume the item ...
} while (TRUE);

Pseudocode
// Shared
semaphore rw_mutex = 1;   // Exclusive access for writers
semaphore mutex = 1;      // Protect read_count
int read_count = 0;       // Number of active readers

// WRITER
do {
    P(rw_mutex);       // Get exclusive access

    // ... write data ...

    V(rw_mutex);       // Release
} while (TRUE);

// READER
do {
    P(mutex);
    read_count++;
    if (read_count == 1)
        P(rw_mutex);   // First reader locks out writers
    V(mutex);

    // ... read data ...

    P(mutex);
    read_count--;
    if (read_count == 0)
        V(rw_mutex);   // Last reader unlocks for writers
    V(mutex);
} while (TRUE);

Problem: If readers keep arriving, writers may starve (never get access). This is called reader preference.

Writer Preference: Add another semaphore so that once a writer is waiting, no new readers are admitted. This prevents writer starvation but may starve readers.

Pseudocode
semaphore chopstick[5];  // All initialized to 1

// Philosopher i (0 to 4)
do {
    // THINKING ...

    P(chopstick[i]);          // Pick up LEFT chopstick
    P(chopstick[(i+1)%5]);    // Pick up RIGHT chopstick

    // EATING ...

    V(chopstick[i]);          // Put down LEFT
    V(chopstick[(i+1)%5]);    // Put down RIGHT
} while (TRUE);

⚠️ DEADLOCK: If all 5 philosophers pick up their left chopstick simultaneously, all are holding one and waiting for the other — circular wait!

Pseudocode
semaphore chopstick[5];  // All initialized to 1

// Philosopher i
do {
    // THINKING ...

    if (i % 2 == 0) {       // Even: pick left first
        P(chopstick[i]);
        P(chopstick[(i+1)%5]);
    } else {                // Odd: pick right first
        P(chopstick[(i+1)%5]);
        P(chopstick[i]);
    }

    // EATING ...

    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
} while (TRUE);

Why it works: By making at least one philosopher pick up chopsticks in opposite order, we break the circular wait condition.

Given statements: S1, S2, S3, S4, S5, S6

Constraints: S1 → S2, S1 → S3, S2 → S4, S3 → S4, S4 → S5, S4 → S6

Diagram
        S1
       /  \
      S2    S3
       \  /
        S4
       /  \
      S5    S6

Meaning: S2 and S3 can run in parallel (both only depend on S1). S4 must wait for BOTH S2 and S3. S5 and S6 can run in parallel after S4.

Implementation with semaphores:

Pseudocode
semaphore a=0, b=0, c=0, d=0, e=0, f=0;

P1: S1; V(a); V(b);
P2: P(a); S2; V(c);
P3: P(b); S3; V(d);
P4: P(c); P(d); S4; V(e); V(f);
P5: P(e); S5;
P6: P(f); S6;

C
#include <stdio.h>
#include <pthread.h>

void* print_hello(void* arg) {
    int id = *((int*)arg);
    printf("Hello from thread %d\n", id);
    pthread_exit(NULL);
}

int main() {
    pthread_t threads[3];
    int ids[3] = {1, 2, 3};

    for (int i = 0; i < 3; i++)
        pthread_create(&threads[i], NULL, print_hello, &ids[i]);

    for (int i = 0; i < 3; i++)
        pthread_join(threads[i], NULL);

    printf("All threads completed.\n");
    return 0;
}

Compile: gcc -o threads threads.c -lpthread

C
#include <stdio.h>
#include <pthread.h>

int counter = 0;
pthread_mutex_t lock;

void* increment(void* arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&lock);
        counter++;              // Critical section
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;
    pthread_mutex_init(&lock, NULL);

    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Counter = %d\n", counter); // Always 200000 with mutex!
    pthread_mutex_destroy(&lock);
    return 0;
}

Without mutex: Counter would be less than 200000 due to race condition!

Answer:

1. Mutual Exclusion: Only one process can be in its critical section at a time. Analogy: Only one person can use the ATM booth — the door locks from inside.

2. Progress: If no process is in the critical section and some want to enter, the decision of who enters cannot be postponed indefinitely. Only processes not in their remainder section participate in the decision. Analogy: If the ATM is free and people are waiting, one of them must be allowed in — you can't keep the booth empty.

3. Bounded Waiting: There must be a bound on the number of times other processes can enter before a waiting process gets its turn. Analogy: In a bank queue with token numbers, you're guaranteed to be served after a finite number of customers — nobody can keep cutting the line.

Answer:

Binary Semaphore (Mutex): Takes values 0 or 1 only. Used for mutual exclusion — ensuring one process at a time. Example: A single-key bathroom — key is either with someone (0) or hanging on the hook (1).

Counting Semaphore: Takes values from 0 to N. Used to control access to a resource with multiple instances. Example: A parking lot with 50 spaces — semaphore starts at 50, each car entering decrements it, each car leaving increments it. When 0, new cars must wait.

Key difference: Binary semaphore = one resource. Counting semaphore = N identical resources.

Answer:

Deadlock cause: Each philosopher picks up their left chopstick first. If all 5 do this simultaneously, each holds one chopstick and waits for the other — creating a circular wait. All four conditions for deadlock are met: mutual exclusion (chopstick is exclusive), hold and wait (holding left, waiting for right), no preemption (can't force a philosopher to release), and circular wait (P0→P1→P2→P3→P4→P0).

Solutions:

• Asymmetric ordering: Even-numbered philosophers pick left first, odd pick right first — breaks circular wait
• Limit to 4: Allow at most 4 philosophers to sit simultaneously (counting semaphore = 4)
• All-or-nothing: Pick up both chopsticks only if both are available, inside a critical section

Answer:

User-Level Threads: Managed by a thread library in user space. Faster context switching (no kernel involvement), portable across OSes. BUT: if one thread blocks, all block; cannot use multiple CPUs.

Kernel-Level Threads: Managed by the OS kernel. Can exploit multiple CPUs, one blocking thread doesn't block others. BUT: slower creation and context switching due to system calls.

Choose ULT when: You need many lightweight threads with fast switching and the application is CPU-bound (no blocking I/O). Example: cooperative multitasking in game engines.

Choose KLT when: You need true parallelism on multicore CPUs, or your application does blocking I/O (network servers, file processing). Example: Web servers handling concurrent HTTP requests.

Answer:

A precedence graph is a DAG (Directed Acyclic Graph) showing execution order constraints between statements. An edge from S_i to S_j means S_i must complete before S_j begins.

Graph
       S1
      /  \
    S2    S3
      \  /
       S4

S2 and S3 can execute in parallel (both depend only on S1). S4 must wait for both S2 and S3.

Semaphore implementation:

Pseudocode
semaphore a=0, b=0, c=0, d=0;
P1: S1; V(a); V(b);
P2: P(a); S2; V(c);
P3: P(b); S3; V(d);
P4: P(c); P(d); S4;