Threads and Concurrency

Learning Objectives

By the end of this reading, you will be able to:

• Understand the concept of threads and how they differ from processes
• Explain the benefits and challenges of multithreading
• Describe different multithreading models (user-level, kernel-level, hybrid)
• Create and manage threads using POSIX threads (pthreads) and Python threading
• Identify and understand race conditions and data hazards
• Implement basic thread synchronization techniques
• Understand thread lifecycle and states

Table of Contents

1. Introduction to Threads
2. Threads vs Processes
3. Benefits of Multithreading
4. Thread Models
5. Thread Libraries and Creation
6. Thread States and Lifecycle
7. Concurrency Issues
8. Race Conditions
9. Exercises
10. Summary

Introduction to Threads

A thread is the smallest unit of execution within a process. While a process can be thought of as a heavyweight unit with its own memory space, a thread is a lightweight unit that shares the process's resources.

What is a Thread?

A thread is sometimes called a lightweight process because it has:

• Its own program counter
• Its own register set
• Its own stack

But it shares with other threads in the same process:

• Code section
• Data section
• Operating system resources (open files, signals)

Single-Threaded vs Multi-Threaded Process

SINGLE-THREADED PROCESS           MULTI-THREADED PROCESS
+------------------+              +------------------+
|    Process       |              |    Process       |
|                  |              |                  |
|  Code            |              |  Code  (shared)  |
|  Data            |              |  Data  (shared)  |
|  Files           |              |  Files (shared)  |
|                  |              |                  |
|  +------------+  |              |  Thread 1  Thread 2  Thread 3
|  |  Thread    |  |              |  +------+  +------+  +------+
|  |            |  |              |  |  PC  |  |  PC  |  |  PC  |
|  |  Stack     |  |              |  | Regs |  | Regs |  | Regs |
|  |  Registers |  |              |  |Stack |  |Stack |  |Stack |
|  |  PC        |  |              |  +------+  +------+  +------+
|  +------------+  |              |                  |
+------------------+              +------------------+

Threads vs Processes

Understanding the distinction between threads and processes is crucial for effective concurrent programming.

Comparison Table

Memory Layout Comparison

TWO PROCESSES                    ONE PROCESS WITH TWO THREADS

Process A        Process B       Process C
+----------+     +----------+    +----------+
| Code     |     | Code     |    | Code     | <-- Shared
+----------+     +----------+    +----------+
| Data     |     | Data     |    | Data     | <-- Shared
+----------+     +----------+    +----------+
| Heap     |     | Heap     |    | Heap     | <-- Shared
+----------+     +----------+    +----------+
| Stack A  |     | Stack B  |    | Stack T1 |
+----------+     +----------+    +----------+
                                 | Stack T2 |
                                 +----------+

Separate Memory               Shared Memory (except stacks)

When to Use Threads vs Processes

Use Threads When:

• Tasks need to share data frequently
• Need faster creation and context switching
• Working on parts of the same problem
• Building responsive user interfaces

Use Processes When:

• Need strong isolation for security/stability
• Running completely independent programs
• Want to avoid shared state complexity
• Need to run on multiple machines (distributed systems)

Benefits of Multithreading

1. Responsiveness

Multi-threaded applications remain responsive even when part of the program is blocked.

Example: Web Browser
Thread 1: Downloads image (blocked on I/O)
Thread 2: Renders already-loaded content (responsive!)
Thread 3: Handles user input (responsive!)

2. Resource Sharing

Threads automatically share memory and resources, making communication easier and more efficient.

# Threads can easily share data
shared_list = []

def worker_thread():
    # Can directly access and modify shared_list
    shared_list.append(data)

3. Economy

Creating and managing threads is cheaper than processes.

Process Creation: ~10,000 microseconds
Thread Creation:  ~100 microseconds
100x faster!

4. Scalability

Threads can run on different processors, using multi-core CPUs effectively.

Single-threaded:        Multi-threaded (4 cores):
CPU1: ████████████      CPU1: ████
CPU2: idle              CPU2: ████
CPU3: idle              CPU3: ████
CPU4: idle              CPU4: ████

Thread Models

Operating systems can implement threads in different ways, leading to various threading models.

1. User-Level Threads (Many-to-One Model)

All thread management is done in user space by a thread library. The kernel sees only one process.

User Space
+----------------------------------+
| Thread 1 | Thread 2 | Thread 3  |
+----------------------------------+
            |
      Thread Library
            |
+----------------------------------+
Kernel Space
+----------------------------------+
|        Single Kernel Thread     |
+----------------------------------+

Advantages:

• Fast thread creation and management
• No kernel involvement needed
• Portable across different operating systems

Disadvantages:

• If one thread blocks, entire process blocks
• Cannot use multiple CPUs
• Thread scheduling controlled by library, not OS

Example: GNU Portable Threads

2. Kernel-Level Threads (One-to-One Model)

Each user thread maps to a kernel thread. The kernel manages threads directly.

User Space
+----------------------------------+
| Thread 1 | Thread 2 | Thread 3  |
+----------------------------------+
      |          |          |
      v          v          v
+----------------------------------+
Kernel Space
+----------------------------------+
| Kernel   | Kernel   | Kernel    |
| Thread 1 | Thread 2 | Thread 3  |
+----------------------------------+

Advantages:

• Can run threads in parallel on multiple CPUs
• If one thread blocks, others can continue
• Better system integration

Disadvantages:

• Thread creation involves kernel calls (slower)
• More overhead per thread
• Limited number of threads (kernel resource constraints)

Example: Windows threads, Linux NPTL (Native POSIX Thread Library)

3. Hybrid Model (Many-to-Many Model)

Multiple user threads map to multiple kernel threads. Best of both worlds.

User Space
+----------------------------------------+
| Thread 1 | Thread 2 | Thread 3 | ... |
+----------------------------------------+
      \        |        /        /
       \       |       /        /
        v      v      v        v
+----------------------------------+
Kernel Space
+----------------------------------+
| Kernel Thread 1 | Kernel Thread 2|
+----------------------------------+

Advantages:

• Can create many user threads
• Kernel threads can run in parallel
• Flexible scheduling

Disadvantages:

• Complex to implement
• Can be difficult to program

Example: Solaris threads (prior to Solaris 9)

Thread Libraries and Creation

POSIX Threads (pthreads)

The POSIX thread library is a standard for Unix-like systems.

Basic Thread Creation in C

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

// Thread function - takes void* argument, returns void*
void *thread_function(void *arg) {
    int thread_id = *((int *)arg);
    printf("Thread %d: Hello from thread!\n", thread_id);
    sleep(1);
    printf("Thread %d: Exiting\n", thread_id);
    return NULL;
}

int main() {
    pthread_t thread1, thread2;
    int id1 = 1, id2 = 2;

    // Create threads
    pthread_create(&thread1, NULL, thread_function, &id1);
    pthread_create(&thread2, NULL, thread_function, &id2);

    printf("Main: Created threads\n");

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

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

Compile and run:

gcc -pthread thread_example.c -o thread_example
./thread_example

Thread Attributes

#include <pthread.h>

int main() {
    pthread_t thread;
    pthread_attr_t attr;

    // Initialize attributes
    pthread_attr_init(&attr);

    // Set detached state
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

    // Set stack size
    pthread_attr_setstacksize(&attr, 1024 * 1024); // 1MB

    // Create thread with attributes
    pthread_create(&thread, &attr, thread_function, NULL);

    // Destroy attribute object
    pthread_attr_destroy(&attr);

    return 0;
}

Python Threading

Python provides a high-level threading interface that's easier to use.

Basic Thread Creation in Python

import threading
import time

def thread_function(name, delay):
    """Function that will run in a separate thread"""
    print(f"Thread {name}: Starting")
    time.sleep(delay)
    print(f"Thread {name}: Finishing after {delay} seconds")

# Create threads
thread1 = threading.Thread(target=thread_function, args=("One", 2))
thread2 = threading.Thread(target=thread_function, args=("Two", 1))

# Start threads
thread1.start()
thread2.start()

print("Main: Waiting for threads to complete")

# Wait for threads to complete
thread1.join()
thread2.join()

print("Main: All threads completed")

Thread with Class

import threading
import time

class WorkerThread(threading.Thread):
    def __init__(self, name, count):
        threading.Thread.__init__(self)
        self.name = name
        self.count = count

    def run(self):
        """Code to run when thread starts"""
        print(f"{self.name}: Starting")
        for i in range(self.count):
            print(f"{self.name}: Count {i+1}")
            time.sleep(0.5)
        print(f"{self.name}: Finishing")

# Create and start threads
thread1 = WorkerThread("Worker-1", 3)
thread2 = WorkerThread("Worker-2", 5)

thread1.start()
thread2.start()

thread1.join()
thread2.join()

print("Main: All workers completed")

Getting Thread Information

import threading
import time

def worker():
    current = threading.current_thread()
    print(f"Thread Name: {current.name}")
    print(f"Thread ID: {current.ident}")
    print(f"Is Alive: {current.is_alive()}")
    print(f"Is Daemon: {current.daemon}")
    time.sleep(1)

thread = threading.Thread(target=worker, name="MyWorker")
thread.start()

# Get all active threads
print(f"\nActive threads: {threading.active_count()}")
print(f"Thread list: {threading.enumerate()}")

thread.join()

Thread States and Lifecycle

Threads, like processes, transition through different states during their lifetime.

Thread State Diagram

                 +--------+
      Create --> |  New   |
                 +--------+
                      |
                      | Start
                      v
                 +----------+      Yield/      +---------+
                 |          | <--------------- |         |
                 | Runnable |                  | Running |
                 |          | ---------------> |         |
                 +----------+    Scheduled     +---------+
                   ^    ^                           |
                   |    |                           |
                   |    |  Notify/                  | Wait/Sleep/
                   |    |  Timeout                  | Block
                   |    |                           |
                   |    |                           v
                 +----------+                 +---------+
                 |          |                 |         |
                 | Blocked/ |                 | Waiting |
                 | Sleeping |                 |         |
                 +----------+                 +---------+
                      |
                      | Exit/Terminate
                      v
                 +----------+
                 |   Dead   |
                 +----------+

Thread State Descriptions

1. New: Thread created but not started
2. Runnable: Thread ready to run, waiting for CPU
3. Running: Thread currently executing
4. Waiting: Thread waiting for event/condition
5. Blocked: Thread waiting for resource (I/O, lock)
6. Dead: Thread completed execution

Thread Lifecycle Example

import threading
import time

def demonstrate_states():
    # NEW state
    thread = threading.Thread(target=worker)
    print(f"NEW: Thread created, alive={thread.is_alive()}")

    # RUNNABLE state
    thread.start()
    print(f"RUNNABLE/RUNNING: Thread started, alive={thread.is_alive()}")

    # Let it run
    time.sleep(0.1)

    # DEAD state
    thread.join()
    print(f"DEAD: Thread finished, alive={thread.is_alive()}")

def worker():
    print("Worker: Executing")
    time.sleep(1)  # WAITING/BLOCKED state during sleep
    print("Worker: Done")

demonstrate_states()

Concurrency Issues

When multiple threads access shared resources, several problems can arise.

Shared Resource Problem

Thread 1                Thread 2
Read balance (100)      Read balance (100)
Add 50                  Add 30
Write 150               Write 130
balance = 130 (WRONG! Should be 180)

Types of Concurrency Issues

1. Race Conditions: Outcome depends on thread scheduling
2. Deadlock: Threads wait for each other indefinitely
3. Starvation: Thread never gets CPU time
4. Priority Inversion: Low-priority thread holds resource needed by high-priority thread

Race Conditions

A race condition occurs when the correctness of a program depends on the relative timing of threads.

Classic Example: Bank Account

import threading
import time

class BankAccount:
    def __init__(self):
        self.balance = 0

    def deposit(self, amount):
        # Read current balance
        current = self.balance
        # Simulate some processing
        time.sleep(0.0001)
        # Write new balance
        self.balance = current + amount

account = BankAccount()

def make_deposits():
    for _ in range(1000):
        account.deposit(1)

# Create two threads
thread1 = threading.Thread(target=make_deposits)
thread2 = threading.Thread(target=make_deposits)

thread1.start()
thread2.start()

thread1.join()
thread2.join()

print(f"Final balance: {account.balance}")
print(f"Expected: 2000")
# Output might be less than 2000 due to race condition!

Race Condition Visualization

Time  Thread 1              Thread 2              balance
----  --------              --------              -------
t0                                                0
t1    read balance (0)                            0
t2                          read balance (0)      0
t3    add 1 (temp = 1)                            0
t4                          add 1 (temp = 1)      0
t5    write 1                                     1
t6                          write 1               1
Result: Only 1 added instead of 2!

Critical Section

The critical section is the part of code where shared resources are accessed.

def deposit(self, amount):
    # --- CRITICAL SECTION START ---
    current = self.balance
    time.sleep(0.0001)
    self.balance = current + amount
    # --- CRITICAL SECTION END ---

Requirements for Critical Section Solution

1. Mutual Exclusion: Only one thread in critical section at a time
2. Progress: If no thread is in critical section, selection of next thread must not be postponed indefinitely
3. Bounded Waiting: Limit on how long thread waits to enter critical section

Simple Lock Solution

import threading

class BankAccount:
    def __init__(self):
        self.balance = 0
        self.lock = threading.Lock()

    def deposit(self, amount):
        self.lock.acquire()
        try:
            current = self.balance
            time.sleep(0.0001)
            self.balance = current + amount
        finally:
            self.lock.release()

# Better: Use context manager
    def deposit_better(self, amount):
        with self.lock:
            current = self.balance
            time.sleep(0.0001)
            self.balance = current + amount

pthread Mutex Example

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

int counter = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

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

int main() {
    pthread_t t1, t2;

    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);  // Should be 200000
    pthread_mutex_destroy(&mutex);
    return 0;
}

Producer-Consumer Problem

A classic concurrency problem demonstrating race conditions.

import threading
import time
import random
from collections import deque

class Buffer:
    def __init__(self, size):
        self.buffer = deque(maxlen=size)
        self.lock = threading.Lock()

    def produce(self, item):
        with self.lock:
            if len(self.buffer) < self.buffer.maxlen:
                self.buffer.append(item)
                return True
            return False

    def consume(self):
        with self.lock:
            if len(self.buffer) > 0:
                return self.buffer.popleft()
            return None

buffer = Buffer(10)

def producer(name):
    for i in range(5):
        item = f"{name}-{i}"
        while not buffer.produce(item):
            time.sleep(0.1)
        print(f"Producer {name}: Produced {item}")
        time.sleep(random.uniform(0.1, 0.3))

def consumer(name):
    for _ in range(5):
        item = None
        while item is None:
            item = buffer.consume()
            time.sleep(0.1)
        print(f"Consumer {name}: Consumed {item}")
        time.sleep(random.uniform(0.1, 0.3))

# Create threads
producers = [threading.Thread(target=producer, args=(f"P{i}",)) for i in range(2)]
consumers = [threading.Thread(target=consumer, args=(f"C{i}",)) for i in range(2)]

# Start all threads
for t in producers + consumers:
    t.start()

# Wait for completion
for t in producers + consumers:
    t.join()

Exercises

Basic Exercises

1. Thread Creation

   • Write a C program that creates 5 threads, each printing its thread ID
   • Write a Python program that creates 3 threads, each sleeping for different durations
   • Measure and compare thread creation time vs process creation time

2. Threads vs Processes

   • List 3 scenarios where threads are better than processes
   • List 3 scenarios where processes are better than threads
   • Explain why threads share memory while processes don't

3. Thread States

   • Draw and label the thread state transition diagram
   • For each transition, give an example of what causes it
   • Write code that demonstrates each thread state

Intermediate Exercises

4. Race Condition Detection

   counter = 0
   
   def increment():
       global counter
       for _ in range(100000):
           counter += 1
   
   t1 = threading.Thread(target=increment)
   t2 = threading.Thread(target=increment)
   # What is the expected vs actual result? Why?
   

5. Critical Section Protection

   • Modify the bank account example to use locks correctly
   • Implement a thread-safe counter class
   • Create a thread-safe queue with enqueue/dequeue operations

6. Multi-threaded File Processing Write a program that:

   • Divides a large file into chunks
   • Uses multiple threads to process each chunk
   • Combines results from all threads
   • Measures speedup compared to single-threaded version

Advanced Exercises

7. Reader-Writer Problem Implement a solution where:

   • Multiple readers can read simultaneously
   • Only one writer can write at a time
   • Writers have exclusive access
   • Use appropriate synchronization primitives

8. Thread Pool Implementation Create a thread pool that:

   • Maintains a fixed number of worker threads
   • Accepts tasks and queues them
   • Worker threads process tasks from queue
   • Properly handles shutdown

9. Performance Analysis

   • Create a CPU-bound task and measure performance with 1, 2, 4, 8 threads
   • Create an I/O-bound task and measure performance with varying thread counts
   • Graph the results and explain the differences
   • Identify the optimal thread count for each scenario

10. Parallel Matrix Multiplication

    • Implement matrix multiplication using multiple threads
    • Divide work among threads (row-wise or block-wise)
    • Compare performance with single-threaded version
    • Measure speedup with different thread counts

Challenge Exercises

11. Dining Philosophers Problem Implement a solution to the dining philosophers problem:

    • 5 philosophers sit at a round table
    • Each needs two forks to eat
    • Prevent deadlock
    • Prevent starvation
    • Use mutexes or semaphores

12. Parallel Web Scraper Build a multi-threaded web scraper that:

    • Downloads multiple web pages concurrently
    • Extracts links from pages
    • Follows links up to a certain depth
    • Avoids visiting same URL twice (thread-safe set)
    • Handles errors gracefully

Summary

In this reading, we explored threads and concurrency in depth:

Key Takeaways

1. Threads are Lightweight: Threads share memory and resources within a process, making them faster to create and switch than processes.

2. Thread Models: Operating systems implement threads using different models:

   • User-level (Many-to-One): Fast but limited
   • Kernel-level (One-to-One): Parallel but expensive
   • Hybrid (Many-to-Many): Flexible but complex

3. Benefits of Multithreading:

   • Responsiveness in applications
   • Resource sharing within process
   • Economy in creation and management
   • Scalability across multiple CPUs

4. Thread Creation: Multiple libraries exist:

   • POSIX threads (pthreads) for C/C++
   • Threading module for Python
   • Each provides creation, joining, and synchronization

5. Thread States: Threads transition through states (New, Runnable, Running, Waiting, Blocked, Dead) similar to processes.

6. Concurrency Issues: Shared memory access creates problems:

   • Race conditions when threads interfere
   • Need for synchronization mechanisms
   • Critical sections must be protected

7. Race Conditions: When program correctness depends on thread timing, unpredictable bugs occur.

Important Concepts to Remember

• Threads share code, data, and files but have separate stacks and registers
• Context switching between threads is cheaper than between processes
• Race conditions are bugs that may occur intermittently depending on timing
• Critical sections must be protected with synchronization primitives
• Not all programs benefit from multithreading (overhead vs speedup)

Best Practices

1. Minimize Shared State: Reduce shared data between threads
2. Protect Critical Sections: Always use proper synchronization
3. Avoid Nested Locks: Can lead to deadlocks
4. Use High-Level Abstractions: Thread pools, concurrent queues
5. Test Thoroughly: Concurrency bugs are hard to reproduce

Looking Ahead

In the next reading, we'll dive into Memory Management, exploring how operating systems allocate and manage memory for processes and threads, including virtual memory, paging, segmentation, and the Translation Lookaside Buffer (TLB).

Understanding threads and concurrency is essential for modern programming, especially with multi-core processors. The synchronization techniques we briefly introduced here will be covered in much greater detail in the Synchronization and Deadlocks reading.

Previous Reading: 01-processes.md - OS Overview and Processes

Next Reading: 03-memory-management.md - Memory Management