Operating Systems: Multithreaded Programming and Concurrency

Overview of Threads and Multithreading

  • Definition of a Thread:

    • A thread is the basic unit of CPU utilization.

    • It comprises four primary components:

      1. A thread ID (identifier).

      2. A program counter (PC).

      3. A register set.

      4. A stack.

  • Process Shared Resources:

    • Threads belonging to the same process share:

      • Code section.

      • Data section.

      • Operating-system resources (e.g., open files, signals).

  • Single-Threaded vs. Multithreaded Processes:

    • A traditional single-threaded process has a single thread of control.

    • A multithreaded process contains multiple threads of control, enabling it to perform more than one task simultaneously.

Single-threaded and multithreaded processes
  • Motivation for Multithreading:

    • Modern software applications run as separate processes containing multiple threads of control.

    • Examples of Multithreaded Applications:

      • Photo Thumbnail Generator: Uses a separate thread to generate a thumbnail for each individual image.

      • Web Browser: One thread displays images/text while another thread retrieves data from the network.

      • Word Processor: One thread displays graphics, a second thread responds to user keypresses, and a third thread performs background spelling and grammar checks.

    • Multithreaded Web Server Architecture:

      • A web server accepts client requests for web pages, images, and audio.

      • Single-threaded approach: Services only one client at a time; other clients experience long wait times.

      • Multi-process approach: Creates a new process for each client request. Process creation is time-consuming, resource-intensive, and wasteful when tasks are identical.

      • Multithreaded approach: A listener thread waits for requests. Upon receiving a request, the server creates a new worker thread to service the client, allowing the listener thread to immediately resume listening for additional client requests.

Multithreaded server architecture
  • Multithreaded Operating System Kernels:

    • OS kernels create multiple threads during boot time (e.g., Linux creates kernel threads for device management, memory management, and interrupt handling).

    • Executing ps -ef on a Linux system displays kernel threads. The parent of all Linux kernel threads is kthreadd with PID=2\text{PID} = 2.

  • Benefits of Multithreaded Programming:

    1. Responsiveness: Interactive applications remain responsive even if part of the program is blocked or performing a lengthy operation (e.g., executing a time-consuming UI action in an asynchronous background thread).

    2. Resource Sharing: Threads share memory and process resources by default within the same address space without requiring explicit IPC setups (such as shared memory or message passing).

    3. Economy: Allocating memory and resources for process creation is expensive. Thread creation and context switching incur significantly lower time and memory overhead compared to process creation.

    4. Scalability: Multithreading leverages multiprocessor and multicore architectures by executing threads in parallel on separate processing cores.

Multicore Programming

  • Multicore vs. Multiprocessor Systems:

    • Multicore architectures place multiple processing cores on a single CPU chip, with each core presented to the operating system as a separate CPU.

  • Concurrency vs. Parallelism:

    • Concurrency: Supports more than one task by allowing all tasks to make progress. On a single-core system, execution of multiple threads is interleaved over time via rapid CPU time-slicing.

    • Parallelism: Performs more than one task simultaneously. Requires hardware with multiple processing cores to assign separate threads to individual cores.

    • Concurrency can exist without parallelism on single-core architectures.

  • Five Key Challenges in Multicore Programming:

    1. Identifying tasks: Partitioning applications into independent, concurrent tasks that can execute in parallel.

    2. Balance: Ensuring identified tasks perform equal work of equal value to justify utilizing a separate core.

    3. Data splitting: Dividing data accessed and manipulated by tasks across separate cores.

    4. Data dependency: Synchronizing execution when one task depends on data generated by another task.

    5. Testing and debugging: Testing and debugging execution paths across multiple parallel cores, which is inherently more complex than single-threaded execution.

  • Amdahl's Law:

    • A mathematical formula that calculates potential performance speedup gains from adding additional computing cores to an application with serial (nonparallel) and parallel portions.

    • Formula:         speedup≤1S+1−SN\text{speedup} \le \frac{1}{S + \frac{1 - S}{N}}

      • Where SS is the portion of the application executed serially (0≤S≤10 \le S \le 1).

      • Where NN is the number of processing cores.

    • Convergence Property:

      • As N→∞N \rightarrow \infty, the maximum speedup converges to 1S\frac{1}{S}.

      • If 50%50\% of an application is serial (S=0.50S = 0.50), the absolute maximum theoretical speedup is 10.50=2.0 times\frac{1}{0.50} = 2.0\text{ times}, regardless of core count.

    • Numerical Examples:

      • An application that is 75%75\% parallel and 25%25\% serial (S=0.25S = 0.25):

        • On N=2N = 2 cores: speedup≤10.25+0.752=10.25+0.375=10.625=1.60 times\text{speedup} \le \frac{1}{0.25 + \frac{0.75}{2}} = \frac{1}{0.25 + 0.375} = \frac{1}{0.625} = 1.60\text{ times}.

        • On N=4N = 4 cores: speedup≤10.25+0.754=10.25+0.1875=10.4375=2.28 times\text{speedup} \le \frac{1}{0.25 + \frac{0.75}{4}} = \frac{1}{0.25 + 0.1875} = \frac{1}{0.4375} = 2.28\text{ times}.

      • An application that is 20%20\% serial (S=0.20S = 0.20) on N=4N = 4 cores:

        • speedup≤10.20+0.804=10.20+0.20=10.40=2.50 times\text{speedup} \le \frac{1}{0.20 + \frac{0.80}{4}} = \frac{1}{0.20 + 0.20} = \frac{1}{0.40} = 2.50\text{ times}.

Amdahl's Law Graph
  • Types of Parallelism:

    • Data Parallelism: Distributes subsets of the same data across multiple computing cores and performs the exact same operation on each core.

      • Example: Summing an array of size NN. Core 0 sums elements 0…[N2−1]0 \dots \left[\frac{N}{2} - 1\right], while Core 1 sums elements [N2]…[N−1]\left[\frac{N}{2}\right] \dots [N - 1].

    • Task Parallelism: Distributes unique tasks (threads) across multiple computing cores. Each thread performs a unique operation on either the same or different data.

      • Example: Running two different statistical analysis algorithms simultaneously on the same array across two cores.

    • Data and task parallelism are not mutually exclusive; applications frequently employ hybrid approaches.

Data and task parallelism

Multithreading Models

  • User Threads vs. Kernel Threads:

    • User Threads: Supported above the kernel and managed without kernel intervention via user-space thread libraries.

    • Kernel Threads: Managed directly by the operating system kernel.

User and kernel threads
  • Three Primary Multithreading Models:

    1. Many-to-One Model:

      • Maps many user-level threads to a single kernel thread.

      • Thread management is performed in user space, making it efficient.

      • Drawbacks: The entire process blocks if a thread makes a blocking system call. Multiple threads cannot run in parallel on multicore systems because only one kernel thread can access the kernel at a time. Obsolete in modern OS design.

Many-to-one model
2.  **One-to-One Model**:
    *   Maps each user thread to a corresponding kernel thread.
    *   Provides high concurrency: a blocking system call in one thread does not block other threads. Allows parallel execution across multiple cores.
    *   *Drawback*: Overhead of creating a kernel thread for every user thread can impact performance if too many threads are created.
    *   *Implementations*: Linux and Windows operating systems.
One-to-one model
3.  **Many-to-Many Model**:
    *   Multiplexes many user-level threads to a smaller or equal number of kernel threads.
    *   Developers can create as many user threads as needed. Corresponding kernel threads execute concurrently on multiprocessor cores.
    *   When a thread performs a blocking system call, the kernel schedules another thread for execution.
Many-to-many model
4.  **Two-Level Model**:
    *   A variation of the Many-to-Many model that multiplexes user threads to kernel threads while also allowing a specific user-level thread to be permanently bound to a dedicated kernel thread.
Two-level model

Thread Libraries and APIs

  • Implementation Approaches:

    • User-Space Library: Code and data structures reside entirely in user space. Function calls result in local user-space calls, not system calls.

    • Kernel-Level Library: Code and data structures reside in kernel space. Library API function calls invoke system calls.

  • Global Data Sharing:

    • In POSIX Pthreads and Windows threading, any variables declared globally outside function blocks are shared among all threads in the process.

    • In Java, access to shared data must be explicitly arranged because Java lacks global variables.

  • Threading Strategies:

    • Asynchronous Threading: Parent spawns a child thread and immediately resumes execution. Parent and child run concurrently and independently. Little data sharing occurs.

    • Synchronous Threading: Parent spawns child threads and blocks waiting for all children to terminate before resuming ("fork-join"). High data sharing occurs.

  • POSIX Pthreads:

    • Pthreads (IEEE 1003.1c) is a specification defining standards for thread creation and synchronization (not a implementation).

    • Header file: #include <pthread.h>.

    • Core Functions & Code Structure:

      • pthread_t tid; — Thread identifier.

      • pthread_attr_t attr; — Thread attributes.

      • pthread_attr_init(&attr); — Initializes default attributes.

      • pthread_create(&tid, &attr, runner, argv[1]); — Spawns new thread running function runner passing argv[1] as parameter.

      • pthread_join(tid, NULL); — Blocks parent until thread tid terminates.

      • pthread_exit(0); — Terminates execution of calling thread.

    • Joining Multiple Threads: c #define NUM_THREADS 10 pthread_t workers[NUM_THREADS]; for (int i = 0; i < NUM_THREADS; i++) pthread_join(workers[i], NULL); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

  • Windows Threads:

    • Header file: #include <windows.h>.

    • Data Types: DWORD (unsigned 32-bit int), HANDLE, LPVOID (void pointer).

    • Core Functions & Code Structure:

      • CreateThread(NULL, 0, Summation, &Param, 0, &ThreadId); — Spawns thread running function Summation passing &Param.

      • WaitForSingleObject(ThreadHandle, INFINITE); — Blocks parent thread until target thread terminates.

      • WaitForMultipleObjects(N, THandles, TRUE, INFINITE); — Blocks parent until all N thread handles in THandles array complete.

      • CloseHandle(ThreadHandle); — Reclaims memory associated with thread handle.

  • Java Threads:

    • Supported on all platforms with a JVM (maps to host OS library, e.g., Windows API or Pthreads).

    • Creation Methods:

      1. Extend Thread class and override run().

      2. Implement Runnable interface defining public void run().

      3. Use Lambda expressions (Java 1.8+): java Runnable task = () -> { System.out.println("I am a thread."); }; Thread worker = new Thread(task); worker.start(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

    • Execution: worker.start() allocates JVM memory, initializes thread, and invokes run(). Parent calls worker.join() inside a try-catch block handling InterruptedException.

    • Java Executor Framework (java.util.concurrent):

      • Decouples thread creation from task execution using the producer-consumer model.

      • Executor interface: void execute(Runnable command);

      • Callable<V> interface: Defines V call() returning a result value.

      • Future<V> interface: Represents asynchronous result obtained via submit(). Results are retrieved using result.get().

Implicit Threading

  • Concept: Shifts thread creation and management responsibilities from developers to compilers and runtime libraries. Programmers define tasks (written as functions) which libraries map to threads, usually via Many-to-Many models.

  • Thread Pools:

    • Pre-creates a designated pool of threads at startup that wait for tasks in a sleep state.

    • When a request arrives, it is assigned to an available thread from the pool. Upon completing the task, the thread returns to the pool.

    • Benefits:

      1. Servicing requests with existing threads is faster than spawning new threads.

      2. Bounds total active threads, preventing resource exhaustion.

      3. Decouples task execution mechanics from task creation scheduling.

    • Windows Implementation: QueueUserWorkItem(&PoolFunction, NULL, 0);

    • Java Implementation (Executors factory methods):

      • Executors.newSingleThreadExecutor(): Pool size 1.

      • Executors.newFixedThreadPool(int size): Fixed number of threads.

      • Executors.newCachedThreadPool(): Unbounded pool that reuses threads.

      • pool.shutdown(): Rejects new tasks and shuts down pool after active tasks finish.

  • Fork-Join Framework:

    • Synchronous implicit model used for recursive divide-and-conquer algorithms.

Fork-join parallelism
*   *Java Fork-Join Implementation (Java 1.7+)*:
    *   Tasks inherit from `ForkJoinTask` base class and run inside a `ForkJoinPool` via `pool.invoke(task)`.
    *   `RecursiveTask<V>`: Abstract class for tasks returning results (overrides `V compute()`).
    *   `RecursiveAction`: Abstract class for non-result returning tasks (overrides `void compute()`).
UML class diagram for Java's fork-join
    *   *Work Stealing Algorithm*: Each thread in a `ForkJoinPool` maintains its own double-ended task queue. If its queue becomes empty, it steals a task from another thread's queue to balance workload.
  • OpenMP:

    • Compiler directives and API for C, C++, and FORTRAN supporting parallel execution in shared-memory environments.

    • #pragma omp parallel: Spawns threads equal to processing core count to execute parallel code regions.

    • #pragma omp parallel for: Divides loop iteration spaces among spawned worker threads.

  • Grand Central Dispatch (GCD):

    • Apple technology (macOS/iOS runtime library libdispatch).

    • Dispatch Queues:

      • Serial Queues (Private): Tasks execute sequentially in FIFO order. Each process has its main serial queue.

      • Concurrent Queues (Global): Tasks are removed in FIFO order but execute concurrently across multiple threads.

    • Quality-of-Service (QoS) Classes for Concurrent Queues:

      1. QOS_CLASS_USER_INTERACTIVE: Interactive UI/event handling (requires small processing time).

      2. QOS_CLASS_USER_INITIATED: User-requested UI operations requiring longer processing times (e.g., opening a file or URL).

      3. QOS_CLASS_UTILITY: Long-running non-immediate operations (e.g., importing data).

      4. QOS_CLASS_BACKGROUND: User-invisible, non-time-sensitive background operations (e.g., mail indexing, system backups).

    • Syntax: Blocks in C/C++ (^{ ... }) or Closures in Swift (dispatch_async(queue, { ... })).

  • Intel Threading Building Blocks (TBB):

    • C++ template library enabling parallel programming without specialized compiler support.

    • parallel_for(range, body) template divides an iteration space into chunks and assigns them to worker threads.

    • Provides thread-safe concurrent data structures (e.g., concurrent_hash_map, concurrent_queue, concurrent_vector).

Threading Issues and System Design

  • The fork() and exec() System Calls:

    • If a thread calls fork(), UNIX systems offer two options: (1) duplicate all threads in the new process, or (2) duplicate only the calling thread.

    • If exec() is called immediately after fork(), duplicating only the calling thread is ideal because exec() overrides the entire process space. If exec() is not called, all threads should be duplicated.

  • Signal Handling:

    • Signals notify UNIX processes that a specific event has occurred.

    • Synchronous Signals: Generated by internal process events (e.g., division by zero, illegal memory access). Delivered directly to the thread causing the event.

    • Asynchronous Signals: Generated by external events (e.g., <control><C> keystrokes, timer expiration). Delivered to the target process.

    • Signal Delivery Options in Multithreaded Processes:

      1. Deliver signal to thread to which signal applies.

      2. Deliver signal to every thread in process.

      3. Deliver signal to specific assigned threads.

      4. Assign dedicated signal-handling thread for the entire process.

    • Functions: kill(pid_t pid, int signal) sends signal to process; pthread_kill(pthread_t tid, int signal) sends signal to specific thread.

    • Windows Asynchronous Procedure Calls (APCs): Emulates signals directly to specific target threads.

  • Thread Cancellation:

    • Terminating a target thread before it completes.

    • Two Approaches:

      1. Asynchronous Cancellation: One thread immediately terminates the target thread.

        • Risk: May leave shared data in an inconsistent state or fail to free allocated system resources.

      2. Deferred Cancellation: Target thread checks whether it should terminate at predefined Cancellation Points.

        • Pthreads checking function: pthread_testcancel().

        • Default cancellation type in Pthreads is deferred.

    • Pthreads Cancellation Modes:

      • Off: State = Disabled, Type = N/A

      • Deferred: State = Enabled, Type = Deferred

      • Asynchronous: State = Enabled, Type = Asynchronous

    • Java Thread Cancellation: Uses deferred policy via worker.interrupt() and checking status using Thread.currentThread().isInterrupted().

  • Thread-Local Storage (TLS):

    • Data unique to each individual thread across function invocations.

    • Differs from local variables (visible only within function execution) and static/global variables (shared across all threads).

    • Syntax Support:

      • gcc compiler: static _thread int threadID;

      • C#: [ThreadStatic]

      • Java: ThreadLocal<T> with get() and set() methods.

      • Pthreads: pthread_key_t.

  • Scheduler Activations and Lightweight Processes (LWPs):

    • Lightweight Process (LWP): Intermediate virtual processor structure positioned between user threads and kernel threads in Many-to-Many and Two-Level models.

Lightweight process (LWP)
*   **Upcalls**: Communication mechanism where the kernel informs the user-thread library about blocking events (e.g., thread blocking on I/O).
*   **Upcall Handlers**: Code executed on a virtual processor to save blocking thread states, relinquish virtual processors, and schedule new eligible threads.

Operating System Implementations

  • Windows Threads:

    • Uses One-to-One mapping model.

    • Thread Context Components: Register set, user stack, kernel stack, private storage area for DLLs.

    • Kernel and User Data Structures:

      • ETHREAD (Executive Thread Block): Kernel space. Pointer to parent process, start address, and pointer to KTHREAD.

      • KTHREAD (Kernel Thread Block): Kernel space. Scheduling and synchronization data, kernel stack, pointer to TEB.

      • TEB (Thread Environment Block): User space. Thread identifier, user stack, array for thread-local storage.

Data structures of a Windows thread
  • Linux Threads:

    • Linux treats processes and threads generically as tasks.

    • Represented in kernel space via struct task_struct containing pointers to shared data structures.

    • Created via clone() system call using custom sharing flags:

      • CLONE_FS: Shared file-system info (e.g., current working directory).

      • CLONE_VM: Shared virtual memory address space.

      • CLONE_SIGHAND: Shared signal handlers.

      • CLONE_FILES: Shared open files table.

    • Process vs. Thread behavior: Passing all flags to clone() creates thread-like sharing. Passing no flags creates independent process-like tasks (identical to fork()).

Some of the flags passed when clone() is invoked

Practice Problems, Exercises, and Projects Summary

  • Sudoku Solution Validator Project:

    • Validates a 9x9 Sudoku grid using 11 separate worker threads (1 thread for rows, 1 thread for columns, and 9 threads for individual 3x3 subgrids).

    • Parameters passed to threads using a structure: c typedef struct { int row; int column; } parameters; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

    • Results returned to parent via a shared global array where index ii corresponds to worker ii setting 1 for valid or 0 for invalid.

Solution to a 9x9 Sudoku puzzle
  • Multithreaded Sorting Application Project:

    • Divides an unsorted array into two equal sublists.

    • Spawns two sorting threads to sort sublists concurrently, then a third merging thread joins sorted sublists into a final sorted array.

Multithreaded sorting
  • Monte Carlo Pi Estimation Method:

    • Estimates π\pi by randomly generating (x,y)(x, y) points inside a square bounding a unit circle (radius=1\text{radius} = 1).

    • Calculation formula:         π≈4×number of points in circletotal number of random points\pi \approx 4 \times \frac{\text{number of points in circle}}{\text{total number of random points}}