Unit 5: Multithreading & Synchronization

1. POSIX Thread Creation and Termination

1.1 Overview of Threads

A thread is a basic unit of CPU utilization, consisting of a thread ID, a program counter, a register set, and a stack. It shares the code section, data section, and other operating system resources (such as open files and signals) with other threads belonging to the same process.

• Process vs. Thread: A heavyweight process has a single thread of control. A multithreaded process contains multiple threads of control within the same address space.
• Benefits: Responsiveness, resource sharing, economy (cheaper context switches), and scalability on multiprocessor architectures.

1.2 The Pthreads API

POSIX Threads (Pthreads) is a standard for threading defined by IEEE 1003.1c. In C/C++, headers are found in <pthread.h>. When compiling on Linux, the -pthread flag is typically required (e.g., gcc main.c -pthread).

1.3 Key Functions

1. Thread Creation

To create a new thread, use pthread_create.

int pthread_create(pthread_t *thread, 
                   const pthread_attr_t *attr, 
                   void *(*start_routine) (void *), 
                   void *arg);

• thread: Pointer to a pthread_t variable that will store the unique ID of the new thread.
• attr: Attributes for the thread (stack size, scheduling policy). Pass NULL for default attributes.
• start_routine: The function the thread will execute once created. It must return void* and take a single void* argument.
• arg: The argument passed to start_routine.

2. Thread Termination

A thread terminates when:

1. It returns from its start routine.
2. It calls pthread_exit.
3. It is canceled by another thread (pthread_cancel).

void pthread_exit(void *retval);

• retval: The return value provided to any thread waiting on this thread via pthread_join.

3. Thread Join

The pthread_join function waits for a specific thread to terminate (similar to wait() for processes).

int pthread_join(pthread_t thread, void **retval);

1.4 Code Example: Basic Thread Creation

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

void *print_message(void *ptr) {
    char *message = (char *) ptr;
    printf("%s \n", message);
    pthread_exit(NULL);
}

int main() {
    pthread_t thread1, thread2;
    char *message1 = "Thread 1: Hello";
    char *message2 = "Thread 2: World";

    // Create threads
    pthread_create(&thread1, NULL, print_message, (void*) message1);
    pthread_create(&thread2, NULL, print_message, (void*) message2);

    // Wait for threads to finish
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

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

2. Race Conditions and Critical Sections

2.1 Race Conditions

A Race Condition occurs when two or more threads access shared data concurrently, and at least one of the accesses is a write operation. The final result of the data depends on the precise, non-deterministic timing (interleaving) of the thread execution.

Example Scenario:
Two threads try to increment a shared counter count initialized to 0.

1. Thread A reads count (0).
2. Context Switch occurs.
3. Thread B reads count (0).
4. Thread B increments and writes back (1).
5. Context Switch back to A.
6. Thread A (still thinking count is 0) increments and writes back (1).
   • Result: count is 1, but it should be 2.

2.2 Critical Sections

The segment of code where a thread accesses shared resources (common variables, files, tables) is called a Critical Section.

To prevent race conditions, we must ensure Mutual Exclusion: If one thread is executing in its critical section, no other thread can be executing in their corresponding critical sections.

Requirements for a Solution:

1. Mutual Exclusion: Only one thread in the critical section at a time.
2. Progress: If no thread is in the critical section, and some wish to enter, the selection of who enters next cannot be postponed indefinitely.
3. Bounded Waiting: There must be a limit on how many times other threads can enter the critical section after a thread has requested to enter.

3. Mutex Locks (Mutual Exclusion)

3.1 Concept

A Mutex (Mutual Exclusion Object) is a synchronization primitive that acts like a lock. It protects critical sections by ensuring that only the thread holding the lock can execute the code.

• Acquire (Lock): Before entering the critical section, a thread must acquire the lock. If the lock is already held, the thread blocks (sleeps) until it is released.
• Release (Unlock): After finishing the critical section, the thread releases the lock.

3.2 Pthread Mutex API

1. Initialization:
   
   C

       pthread_mutex_t lock;
       pthread_mutex_init(&lock, NULL);
       // Or statically:
       pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
       

2. Locking:
   
   C

       pthread_mutex_lock(&lock);
       

3. Unlocking:
   
   C

       pthread_mutex_unlock(&lock);
       

4. Destruction:
   
   C

       pthread_mutex_destroy(&lock);
       

3.3 Code Example: Thread-Safe Counter

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

long shared_counter = 0;
pthread_mutex_t lock; // Mutex declaration

void *increment_counter(void *arg) {
    for (int i = 0; i < 100000; i++) {
        // Entry Section
        pthread_mutex_lock(&lock);
        
        // Critical Section
        shared_counter++;
        
        // Exit Section
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

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

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

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

    printf("Final Counter Value: %ld\n", shared_counter);
    pthread_mutex_destroy(&lock); // Clean up
    return 0;
}

4. Semaphores

4.1 Concept

A Semaphore is a more robust synchronization tool than a mutex. It is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal() (historically P and V).

• Wait (sem_wait / P): Decrements the semaphore value. If the value becomes negative, the process/thread blocks.
• Signal (sem_post / V): Increments the semaphore value. If there are blocked processes, one is woken up.

4.2 Types of Semaphores

1. Binary Semaphore: Value ranges between 0 and 1. Functionally equivalent to a Mutex lock.
2. Counting Semaphore: Value can range over an unrestricted domain. Used to control access to a resource that has a finite number of instances (e.g., a pool of 5 connections).

4.3 Pthread Semaphore API

Header: <semaphore.h>

1. Initialization:
   
   C

       // sem: pointer to semaphore variable
       // pshared: 0 = shared between threads, non-zero = shared between processes
       // value: initial value
       int sem_init(sem_t *sem, int pshared, unsigned int value);
       

2. Wait (Decrement/Lock):
   
   C

       int sem_wait(sem_t *sem);
       

3. Signal (Increment/Unlock):
   
   C

       int sem_post(sem_t *sem);
       

4. Destruction:
   
   C

       int sem_destroy(sem_t *sem);
       

4.4 Code Example: Signaling (Strict Order)

Semaphores are excellent for imposing an order on operations (Signal/Wait), not just mutual exclusion. Below, we ensure T1 prints before T2.

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

sem_t sem;

void* t1_func(void* arg) {
    printf("Thread 1: Executing first part...\n");
    // Signal Thread 2 that it can proceed
    sem_post(&sem); 
    return NULL;
}

void* t2_func(void* arg) {
    // Wait for signal from Thread 1
    sem_wait(&sem); 
    printf("Thread 2: Executing second part (after T1 signal)\n");
    return NULL;
}

int main() {
    // Initialize semaphore to 0 (locked initially)
    sem_init(&sem, 0, 0);

    pthread_t t1, t2;
    pthread_create(&t1, NULL, t1_func, NULL);
    pthread_create(&t2, NULL, t2_func, NULL);

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

    sem_destroy(&sem);
    return 0;
}

Summary Comparison