Unit 3: Process Synchronization and Threads

1. Introduction to Process Concepts

Concurrent vs. Co-operating Processes

• Concurrent Processes: Processes that execute simultaneously (or virtually simultaneously via time-slicing) on a system. They may or may not interact with each other.
• Independent Processes: Execution of one does not affect the execution of another.
• Co-operating Processes: Processes that can affect or be affected by other executing processes. They share resources (logical or physical).
  • Reasons for Co-operation: Information sharing, computation speedup (parallelism), modularity, and convenience.

Hierarchy of Processes

In most OSs, processes are organized hierarchically.

• Parent/Child: A process creating another process is the parent; the created process is the child.
• Process Tree: This creates a tree structure (e.g., the init process in Unix/Linux is the root).
• Resource Sharing Options:
  1. Parent and child share all resources.
  2. Children share a subset of parent’s resources.
  3. Parent and child share no resources.
• Execution Options:
  1. Parent and child execute concurrently.
  2. Parent waits until children terminate.

Precedence Graph

A directed acyclic graph (DAG) used to represent the dependencies and execution order of concurrent processes.

• Nodes: Represent individual statements or processes ().
• Edges: Represent precedence. An edge from implies must finish before starts.
• Example: If computes and computes , depends on .

2. The Critical Section Problem

Definition

When multiple co-operating processes access shared data, concurrent access can lead to data inconsistency (Race Condition).

• Critical Section (CS): A segment of code in a process where it accesses/modifies shared resources (variables, files, tables).
• The Goal: Protocol design to ensure that when one process is in its CS, no other may be in theirs.

Structure of a Process

do {
    entry section      // Request permission to enter
        critical section
    exit section       // Announce departure
        remainder section
} while (TRUE);

Three Requirements for a Solution

1. Mutual Exclusion: If Process is executing in its critical section, no other processes can be executing in their critical sections.
2. Progress: If no process is executing in its critical section and there exist some processes that wish to enter, only those processes that are not in their remainder sections can participate in the decision, and this selection cannot be postponed indefinitely. (No deadlock).
3. Bounded Waiting: There must be a limit (bound) on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. (No starvation).

3. Solutions to the Critical Section Problem

Classical Two-Process Solution (Peterson’s Algorithm)

A software-based solution for two processes ( and ).

• Variables:
  • int turn: Indicates whose turn it is to enter.
  • boolean flag[2]: Indicates if a process is ready to enter.

Logic for Process (where ):

flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j); // Busy wait

// CRITICAL SECTION

flag[i] = FALSE; // Exit section

• Mutual Exclusion is preserved because enters only if flag[j] == false or turn == i.
• Progress/Bounded Waiting are met because the turn variable prevents strict alternation deadlock.

Hardware Primitives for Synchronization

Software solutions like Peterson’s are not guaranteed to work on modern architectures due to instruction reordering. Hardware support provides atomic (non-interruptible) instructions.

1. TestAndSet

An atomic instruction that returns the old value of a memory location and sets it to TRUE.

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

// Usage:
while (TestAndSet(&lock)); // do nothing
    // critical section
lock = FALSE;

2. CompareAndSwap (CAS)

Takes three operands: a memory location, an expected old value, and a new value.

int CompareAndSwap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

4. Semaphores

Definition

A Semaphore () is a synchronization tool in the form of an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal().

• Historically known as P (Proberen - to test) and V (Verhogen - to increment).

Operations

• wait(S): Decrements . If , the process blocks.
• signal(S): Increments . If there are blocked processes, one is woken up.

Types

1. Binary Semaphore (Mutex Lock): Value can range between 0 and 1. Used for mutual exclusion.
2. Counting Semaphore: Value can range over an unrestricted domain. Used to control access to a given number of resources.

Implementation (No Busy Waiting)

Instead of spinning (busy wait), a process can block itself.

typedef struct {
    int value;
    struct process *list; // Queue of waiting processes
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        block(); // Context switch
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P); // Move to ready queue
    }
}

5. Classical Synchronization Problems

1. The Producer-Consumer Problem (Bounded Buffer)

• Goal: Producer generates data into a buffer; Consumer consumes it. Buffer has fixed size .
• Semaphores:
  • mutex = 1 (Binary semaphore for buffer access).
  • empty = N (Counts empty slots).
  • full = 0 (Counts full slots).

Producer Code:

wait(empty);   // Wait for space
wait(mutex);   // Lock buffer
// Add item to buffer
signal(mutex); // Unlock buffer
signal(full);  // Signal new item available

Consumer Code:

wait(full);    // Wait for item
wait(mutex);   // Lock buffer
// Remove item from buffer
signal(mutex); // Unlock buffer
signal(empty); // Signal space available

2. The Readers-Writers Problem

• Goal: Allow multiple readers to read simultaneously. Only one writer can access shared data at a time (exclusive access). If a writer is writing, no readers may read.
• Semaphores:
  • mutex = 1 (Protects read_count).
  • wrt = 1 (Protects shared file/data).
  • int read_count = 0.

Writer Process:

wait(wrt);
// WRITING
signal(wrt);

Reader Process:

wait(mutex);
read_count++;
if (read_count == 1) wait(wrt); // First reader locks out writers
signal(mutex);

// READING

wait(mutex);
read_count--;
if (read_count == 0) signal(wrt); // Last reader unlocks writers
signal(mutex);

3. The Dining Philosophers Problem

• Scenario: 5 philosophers sit at a round table with 5 chopsticks (forks). A philosopher needs 2 forks (left and right) to eat.
• Constraint: They can only pick up one fork at a time.
• Semaphores: Array semaphore chopstick[5], all initialized to 1.

Naïve Solution (Causes Deadlock):

wait(chopstick[i]);         // Pick left
wait(chopstick[(i+1)%5]);   // Pick right
// EAT
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);

• Deadlock: If all 5 pick up their left fork simultaneously, all wait forever for the right fork.

Deadlock-Free Solutions:

1. Allow only 4 philosophers at the table.
2. Pick up forks only if both are available (inside a critical section).
3. Asymmetric Solution: Odd philosopher picks left then right; Even philosopher picks right then left.

6. Monitors

Definition

A high-level synchronization construct (available in Java, C#) that abstracts away semaphores. It is a class/module/object where only one process can be active within the monitor at any time.

Characteristics

• Automatic Mutual Exclusion: Procedures inside the monitor are mutually exclusive.
• Shared Data: Local to the monitor.

Condition Variables

To allow processes to wait within the monitor, Condition Variables (x, y) are used.

• x.wait(): The process executing this is suspended and placed in a queue for x. The monitor lock is released.
• x.signal(): Resumes exactly one suspended process. If no process is waiting, the signal operation has no effect (unlike semaphores).

7. Threads and Multithreading

Overview

A Thread (Lightweight Process) is a basic unit of CPU utilization.

• Comprises: Thread ID, Program Counter (PC), Register set, Stack.
• Shares (with peer threads): Code section, Data section, OS resources (open files, signals).

Benefits

1. Responsiveness: App continues running even if part of it is blocked (e.g., GUI vs. background calculation).
2. Resource Sharing: Threads share memory naturally (easier than Shared Memory IPC).
3. Economy: Cheaper to create/switch threads than processes (no memory map changes).
4. Scalability: Takes advantage of Multiprocessor architectures.

Multithreading Models

Mapping between User Threads (managed by thread library) and Kernel Threads (managed by OS).

1. Many-to-One Model:

   • Many user threads map to one kernel thread.
   • Pros: Efficient context switching (user space).
   • Cons: Blocking system call blocks the entire process; no true parallelism on multicore.
   • Example: Green Threads (Solaris), GNU Portable Threads.

2. One-to-One Model:

   • Each user thread maps to a distinct kernel thread.
   • Pros: True concurrency; blocking one thread doesn't block others.
   • Cons: Overhead of creating kernel threads.
   • Example: Linux, Windows, XP/2000.

3. Many-to-Many Model:

   • Multiplexes many user threads to a smaller or equal number of kernel threads.
   • Pros: Best of both worlds (concurrency + efficiency).
   • Cons: Complex implementation.

Scheduler Activations

A mechanism for communication between the user-thread library and the kernel.

• Problem: The kernel doesn't know about user threads in Many-to-Many models.
• Solution: The kernel provides a virtual processor (LWP - Light Weight Process) to the application.
• Upcall: The kernel notifies the application (thread library) about events (e.g., "This processor is about to block") via an upcall handler.

Example of Threaded Program (Pseudocode/C-like)

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

int sum = 0; // Shared data

void *runner(void *param) {
    int upper = atoi(param);
    for (int i = 1; i <= upper; i++)
        sum += i;
    pthread_exit(0);
}

int main(int argc, char *argv[]) {
    pthread_t tid; // Thread ID
    pthread_attr_t attr; // Thread attributes

    pthread_attr_init(&attr);
    // Create thread, execute 'runner' function
    pthread_create(&tid, &attr, runner, argv[1]);
    
    // Wait for thread to exit
    pthread_join(tid, NULL); 
    
    printf("Sum = %d\n", sum);
}