Threads

A thread is the smallest unit of CPU execution within a process. It represents a sequence of instructions that can be scheduled independently and it fully describes program state.

Each thread thus contains the following information:

• Thread Control Block
• Stack Information
• Saved Registers
• Thread Metadata
• Stack (the same stack that maintains function calls with stack frames)

However, the heap, global variables and code are in a shared state which does not belong to a thread.

Threads allow concurrency within a process. Multiple threads can share memory but execute different tasks simultaneously (e.g., a browser rendering a page while downloading files).

This is the idea of multi-threading. For example, in a multi-programmed system, you might run a compiler and a text editor simultaneously. With threads, the text editor itself can run multiple tasks (UI rendering, spell-checking, autosave) concurrently (multi-threading).

Using Threads

Threads are available at the programming layer to communicate to the processor that two tasks that we have don’t need to be executed sequentially, but can be made to run concurrently.

To make a multithreaded process, the process can issue system calls to create new threads.

POSIX provides us an execution model through pthreads which allows us to handle threads directly.

What this does is define a set of C programming types, functions and constants that handle the task of creating system calls that interface with the Kernel to create new threads. Using this, we can implement high level ideas in code such as the Fork-Join pattern.

Here is an example of a C++ code that computes the Parallel Sum of an Array using Fork-Join with pthreads:

#include <iostream>
#include <pthread.h>
#include <vector>

struct ThreadData {
    int start;
    int end;
    const std::vector<int>* arr;
    long long partial_sum;
};

// Worker function for each thread
void* compute_partial_sum(void* arg) {
    ThreadData* data = (ThreadData*)arg;
    data->partial_sum = 0;
    for (int i = data->start; i < data->end; ++i) {
        data->partial_sum += (*(data->arr))[i];
    }
    return nullptr;
}

int main() {
    const int N = 1000000;   // size of array
    const int NUM_THREADS = 4;
    std::vector<int> arr(N, 1); // array filled with 1s

    pthread_t threads[NUM_THREADS];
    ThreadData thread_data[NUM_THREADS];

    int chunk_size = N / NUM_THREADS;

    // Fork: create threads
    for (int i = 0; i < NUM_THREADS; ++i) {
        thread_data[i].start = i * chunk_size;
        thread_data[i].end = (i == NUM_THREADS - 1) ? N : (i + 1) * chunk_size;
        thread_data[i].arr = &arr;
        pthread_create(&threads[i], nullptr, compute_partial_sum, &thread_data[i]);
    }

    // Join: wait for threads and combine results
    long long total_sum = 0;
    for (int i = 0; i < NUM_THREADS; ++i) {
        pthread_join(threads[i], nullptr);
        total_sum += thread_data[i].partial_sum;
    }

    std::cout << "Total sum = " << total_sum << std::endl;
    return 0;
}

• Fork: We split the array into chunks and assign each chunk to a thread.
• Join: After all threads finish, we collect their partial sums into the final result.

This fork-join model is intuitive for tasks like map-reduce, parallel search, or matrix operations.

However, remember that using threads introduces non-determinism because the scheduler can run threads in any order and this makes testing difficult if we don’t prove that our code can work correctly with interleaving. We need good code by design that avoids race conditions.

Dealing with Concrrency

So when dealing with the concurrency afforded by threads, we need to think about:

• Synchronization: Coordination among threads
• Mutual Exclusion: Ensuring only one thread does a particular thing at a time (as a type of syncronisation)
• Critical Section: Code exactly one thread can execute at once (such as code that accesses shared data).
• Lock: An object only one thread can hold at a time, as a way to provide mutual execution.

  Locks have a very simple interface with just two atomic operations: acquire() and release() to allow us to ensure that only one thread can do a particular thing at a time, based on lock possessions.

A mutex is a (type of) lock that enforces mutual exclusion in concurrent programming, making sure shared resources are accessed safely.

Here is an example of how the mutex can be used:

    // Critical section: update global_sum
    pthread_mutex_lock(&mutex);
    global_sum += local_sum;
    pthread_mutex_unlock(&mutex);

Only one thread is not allowed in this critical section at a time. For more, refer to Synchronisation.

Naive Implementation

Early systems had only one thread per process (the process itself). Concurrency was achieved by running multiple processes, each with its own heavy memory footprint.

A thread can be classified into the following 3 states:

• Running - running
• Ready - eligible to run
• Blocked - ineligible to run because it is waiting on something else

A thread is running on a processor when it is resident in that processor’s registers. If it is not there, it is saved in a chunk of memory called a Thread Control Block (TCB). However, it is important to think about how TCBs use memory otherwise there is a risk they will just crowd each other out of memory.

The Thread Control Block (TCB) is a data structure maintained by the operating system to track a thread’s state (program counter, registers, stack pointer, etc.).

When a new thread is created, the OS initializes its TCB and allocates a stack.

Improvements

Threads are lightweight, sharing the same address space and resources. Modern OSs use efficient thread libraries, kernel-level scheduling, and thread pools to reduce overhead.

Beyond Threads

Leads into synchronization (locks, semaphores), scheduling algorithms, and parallel programming models.