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:
A thread ID (identifier).
A program counter (PC).
A register set.
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.

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 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 -efon a Linux system displays kernel threads. The parent of all Linux kernel threads iskthreaddwith .
Benefits of Multithreaded Programming:
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).
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).
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.
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:
Identifying tasks: Partitioning applications into independent, concurrent tasks that can execute in parallel.
Balance: Ensuring identified tasks perform equal work of equal value to justify utilizing a separate core.
Data splitting: Dividing data accessed and manipulated by tasks across separate cores.
Data dependency: Synchronizing execution when one task depends on data generated by another task.
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:
Where is the portion of the application executed serially ().
Where is the number of processing cores.
Convergence Property:
As , the maximum speedup converges to .
If of an application is serial (), the absolute maximum theoretical speedup is , regardless of core count.
Numerical Examples:
An application that is parallel and serial ():
On cores: .
On cores: .
An application that is serial () on cores:
.

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 . Core 0 sums elements , while Core 1 sums elements .
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.

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.

Three Primary Multithreading Models:
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.

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.

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.

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.

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 functionrunnerpassingargv[1]as parameter.pthread_join(tid, NULL);— Blocks parent until threadtidterminates.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);
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 functionSummationpassing&Param.WaitForSingleObject(ThreadHandle, INFINITE);— Blocks parent thread until target thread terminates.WaitForMultipleObjects(N, THandles, TRUE, INFINITE);— Blocks parent until allNthread handles inTHandlesarray 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:
Extend
Threadclass and overriderun().Implement
Runnableinterface definingpublic void run().Use Lambda expressions (Java 1.8+):
java Runnable task = () -> { System.out.println("I am a thread."); }; Thread worker = new Thread(task); worker.start();
Execution:
worker.start()allocates JVM memory, initializes thread, and invokesrun(). Parent callsworker.join()inside atry-catchblock handlingInterruptedException.Java Executor Framework (
java.util.concurrent):Decouples thread creation from task execution using the producer-consumer model.
Executorinterface:void execute(Runnable command);Callable<V>interface: DefinesV call()returning a result value.Future<V>interface: Represents asynchronous result obtained viasubmit(). Results are retrieved usingresult.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:
Servicing requests with existing threads is faster than spawning new threads.
Bounds total active threads, preventing resource exhaustion.
Decouples task execution mechanics from task creation scheduling.
Windows Implementation:
QueueUserWorkItem(&PoolFunction, NULL, 0);Java Implementation (
Executorsfactory 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.

* *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()`).

* *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:
QOS_CLASS_USER_INTERACTIVE: Interactive UI/event handling (requires small processing time).QOS_CLASS_USER_INITIATED: User-requested UI operations requiring longer processing times (e.g., opening a file or URL).QOS_CLASS_UTILITY: Long-running non-immediate operations (e.g., importing data).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()andexec()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 afterfork(), duplicating only the calling thread is ideal becauseexec()overrides the entire process space. Ifexec()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:
Deliver signal to thread to which signal applies.
Deliver signal to every thread in process.
Deliver signal to specific assigned threads.
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:
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.
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/ADeferred: State = Enabled, Type = DeferredAsynchronous: State = Enabled, Type = Asynchronous
Java Thread Cancellation: Uses deferred policy via
worker.interrupt()and checking status usingThread.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>withget()andset()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.

* **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 toKTHREAD.KTHREAD(Kernel Thread Block): Kernel space. Scheduling and synchronization data, kernel stack, pointer toTEB.TEB(Thread Environment Block): User space. Thread identifier, user stack, array for thread-local storage.

Linux Threads:
Linux treats processes and threads generically as tasks.
Represented in kernel space via
struct task_structcontaining 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 tofork()).

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; Results returned to parent via a shared global array where index corresponds to worker setting
1for valid or0for invalid.

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.

Monte Carlo Pi Estimation Method:
Estimates by randomly generating points inside a square bounding a unit circle ().
Calculation formula: