PadhaikoAll subjects

Threads and thread scheduling

Operating System (ENCT 254)

Open in the Padhaiko app

2.3 Threads and thread scheduling

A thread—often referred to as a lightweight process (LWP)—is the smallest, basic unit of CPU utilization dispatched by an operating system. A traditional heavyweight process represents a single thread of control executing in an address space; a multithreaded process contains multiple concurrent execution flows sharing a common address space and system resources.

Definition

Thread

A Thread is an independent sequence of execution within the context of a process, possessing its own Program Counter (PC), CPU registers, and private stack, while sharing the process's code segment, data segment, heap, and open file descriptors with other peer threads.

Process vs. Thread: Resource Sharing Architecture

In modern operating systems, resource allocation and execution dispatching are decoupled:

Single-Threaded vs. Multi-Threaded Process ArchitectureText
 [ Single-Threaded Process ]                 [ Multi-Threaded Process ]
 +---------------------------+              +---------------------------+
 | Code | Data | Heap | File |              | Code | Data | Heap | File |  <-- Shared
 +---------------------------+              +---------------------------+
 | Registers | Stack         |              | Regs | Regs | Regs        |  <-- Private
 |                           |              | Stack| Stack| Stack       |
 | (Thread 1)                |              | (Th1)| (Th2)| (Th3)       |
 +---------------------------+              +---------------------------+
Private vs. Shared Thread Resources
Resource ComponentScope Across ProcessWhy it is Shared or Private
Program Counter (PC)Strictly PrivateEach thread tracks its own independent instruction stream position.
CPU Register SetStrictly PrivateStores intermediate values of the thread's active computation.
Stack & Stack PointerStrictly PrivateHolds local automatic variables, function parameters, and return frames.
Thread ID (TID)Strictly PrivateUnique numeric handle used to reference, signal, and join the specific thread.
Text (Code) SegmentSharedAll threads execute functions from the identical program binary.
Data Segment (Globals)SharedGlobal variables and static variables are directly accessible by all threads.
Heap MemorySharedDynamically allocated memory (malloc() / new) is shared across all threads.
Open File DescriptorsSharedIf one thread opens a file socket or pipe, any peer thread can read or write to it.
Signals & Signal HandlersSharedProcess-wide signal actions (such as SIGTERM or SIGINT) apply to the container process.

Motivation and Benefits of Multithreading

The adoption of multithreading in modern application and system architecture is driven by four primary advantages:

  1. High Responsiveness: In interactive desktop and mobile applications, a long-running task (such as downloading a large file or rendering complex 3D graphics) can run in a background worker thread. Meanwhile, the main user interface (UI) thread remains completely responsive to user mouse clicks, keyboard presses, and touch events without freezing.
  2. Resource Sharing: Unlike independent processes that require complex, heavyweight Inter-Process Communication (IPC) techniques—such as shared memory segments (shmget), pipes, or Unix domain sockets—threads within the same process automatically share memory addresses by default.
  3. Economy and Low Overhead:
    • Creation Cost: Creating a process with fork() requires copying or setting up page table hierarchies, file descriptors, and address space maps. Creating a thread requires only allocating a small stack (typically ) and a minimal Thread Control Block (TCB), which is faster than process creation.
    • Context Switching Cost: Thread switching is significantly faster than process switching because the memory mapping does not change. The CPU's Translation Lookaside Buffer (TLB) and hardware cache lines remain intact, avoiding costly cache invalidation.
  4. Multiprocessor and Multicore Scalability: On multicore architectures, distinct threads of a single application execute in true hardware parallelism across multiple physical CPU cores simultaneously.

Thread Implementation Models: User-Level vs. Kernel-Level Threads

Operating systems support multithreading through two fundamental architectural tiers:

AspectUser-Level Threads (ULT)Kernel-Level Threads (KLT)
Management EntityImplemented entirely in user space by a runtime thread library (e.g., POSIX GNU Pth).Managed directly by the operating system kernel (e.g., Linux NPTL, Windows threads).
Kernel AwarenessThe kernel is completely unaware of threads; it sees and schedules only a single monolithic process.The kernel maintains a dedicated Thread Control Block (TCB) for every active thread.
Context Switch SpeedUltra-fast: Context switches occur entirely in user space via local register saves/restores without kernel traps (comparable to a local C function call).Slower: Thread switches require a system call and hardware mode switch from User Mode to Kernel Mode.
Blocking System CallsFatal Flaw: If any one user thread invokes a blocking system call (e.g., disk read), the kernel blocks the entire process, stalling all other threads.Superior Concurrency: If one thread blocks on I/O, the kernel scheduler immediately dispatches another ready thread from the same process.
Multicore Hardware ScalingCannot execute across multiple CPU cores simultaneously; all user threads run on the single core assigned to the parent process.True Parallelism: The kernel can schedule different threads of the same process onto distinct physical CPU cores simultaneously.
PortabilityHighly portable; runs on any standard OS without requiring kernel modification.Platform-dependent; relies on specific OS kernel system calls and scheduling interfaces.

Hybrid Threading Model

The Hybrid (Combined) Model (historically utilized in Solaris and Mach) attempts to combine the best features of both architectures:


Multithreading Models

The mapping between user-level threads and kernel-level threads defines three distinct multithreading architectures:

Architectural Comparison of Multithreading Models
ModelMapping RatioOperational CharacteristicsReal-World Status
Many-to-One ()Many User Threads One Kernel ThreadUser-space thread library manages all execution. Thread switching is fast, but an I/O block in one thread halts the whole process; zero multicore scaling.Used in legacy systems (Green Threads in early Java, GNU Pth). Mostly obsolete.
One-to-One ()One User Thread One Kernel ThreadEvery user thread maps directly to a dedicated kernel thread. Provides true multicore concurrency; blocking threads do not stall peers. Higher kernel resource consumption.The dominant modern standard: Linux (Native POSIX Thread Library - NPTL), Microsoft Windows, macOS.
Many-to-Many ()Many User Threads Fewer/Equal Kernel ThreadsMultiplexes user threads onto kernel threads (). Best theoretical balance of low creation overhead and multicore concurrency. Highly complex to tune.Historically used in Solaris (libthread), IRIX, and HP-UX. Largely replaced by models.
Two-Level ModelCombination of and Operates primarily as Many-to-Many, but allows performance-critical user threads to be permanently bound to dedicated kernel threads.Supported in advanced Unix implementations (HP-UX, early Solaris).

Thread Scheduling

Thread scheduling is categorized into two distinct scheduling scopes based on where competition for processor time occurs:

Scheduling Contention Scopes
Contention ScopeControlling EntityScope of CompetitionAssociated Model
Process-Contention Scope (PCS)User-level thread runtime libraryThreads belonging to the same process compete against one another for available Lightweight Processes (kernel threads). Priority is decided locally without kernel involvement.Many-to-One () and Many-to-Many () models. In Pthreads: PTHREAD_SCOPE_PROCESS.
System-Contention Scope (SCS)Operating system kernel CPU schedulerAll kernel-level threads across the entire operating system compete against one another for physical CPU execution cores.One-to-One () models. In Pthreads: PTHREAD_SCOPE_SYSTEM. Modern Linux and Windows use SCS exclusively.

Multiprocessor and Multicore Thread Scheduling

When an operating system runs on Symmetric Multiprocessing (SMP) and multicore hardware, the thread scheduler must resolve core allocation and memory hierarchy challenges:

1. Processor Affinity (Cache Locality)

When a thread runs on a specific CPU core, its working dataset is fetched into that core's fast private L1 and L2 hardware caches:

AspectSoft Processor AffinityHard Processor Affinity
Policy StrictnessBest-effort heuristicEnforced constraint
Kernel BehaviorThe operating system scheduler prefers to keep a thread on the same CPU core, but will freely migrate it to another core if load balancing demands it.The operating system strictly guarantees that the thread will execute exclusively on the user-specified subset of CPU cores.
System InterfaceDefault behavior in modern kernels.Configured via explicit system calls (e.g., sched_setaffinity() in Linux, SetThreadAffinityMask() in Windows).

2. Multiprocessor Load Balancing

In SMP systems, thread workloads must be distributed evenly across all CPU cores to prevent one core from sitting idle while another is overwhelmed:

3. Gang Scheduling

In parallel scientific and multithreaded database applications, threads frequently synchronize with one another via spinlocks or barriers:


POSIX Threads (Pthreads) Programming Overview

POSIX defines standard C library interfaces (<pthread.h>) for portable thread management:

Basic POSIX Multithreading DemonstrationC
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

void *worker_task(void *arg) {
    int id = *(int *)arg;
    printf("Worker thread %d executing concurrently.\n", id);
    pthread_exit(NULL);
}

int main(void) {
    pthread_t thread_handle;
    int thread_arg = 42;

    /* Create a kernel-scheduled thread */
    if (pthread_create(&thread_handle, NULL, worker_task, &thread_arg) != 0) {
        perror("Failed to create thread");
        return 1;
    }

    /* Wait for child thread to finish */
    pthread_join(thread_handle, NULL);
    printf("Child thread joined successfully. Exiting main.\n");
    return 0;
}

Worked Out Examples

Example 2.1

2.1

A computational image processing application is analyzed for multithreaded parallelization. Profiling reveals that of its total execution time is inherently sequential (unparallelizable file I/O and initialization), while the remaining can be parallelized completely across concurrent worker threads.

  1. Apply Amdahl's Law to calculate the theoretical speedup when executing the program on a 4-core processor () and an 8-core processor ().
  2. Determine the theoretical maximum speedup possible on a hypothetical machine with an infinite number of processor cores ().

Formulating Amdahl's Law: Let denote the strictly serial fraction of execution time, and denote the parallelizable fraction ():

Amdahl's Law defines the overall execution speedup achieved using parallel processing cores as:

Evaluating speedup for and cores:

  • For a 4-core CPU ():
  • For an 8-core CPU ():

Evaluating theoretical upper bound (): As the number of cores approaches infinity, the parallel execution term :

No matter how many hundreds of cores are added to the system, the total speedup can never exceed because the serial portion () dominates execution time.

Answer:
  1. With 4 cores, the speedup is ; with 8 cores, the speedup is .
  2. The asymptotic upper limit with infinite cores is ().
Example 2.2

2.2

A high-traffic web server processes client connection requests per second. The engineering team evaluates two concurrency architectures:

  1. Calculate the total CPU time expended purely on concurrency overhead (creation + switching) for requests under both architectures.
  2. Determine the efficiency speedup factor of the multithreaded architecture over the multiprocess architecture.

Calculating concurrency overhead for Architecture A (Multiprocess): Overhead per request under Architecture A:

For client requests:

Calculating concurrency overhead for Architecture B (Multithreaded): Overhead per request under Architecture B:

For client requests:

Evaluating the efficiency gain factor: The speedup in overhead efficiency achieved by multithreading is:

Answer:
  1. Total concurrency overhead for requests: Architecture A requires ; Architecture B requires .
  2. The multithreaded architecture reduces concurrency overhead by a factor of ().
Example 2.3

2.3

Contrast the execution behavior of two multithreaded programs on a dual-core processor: Program 1 utilizes Process-Contention Scope (PCS) under a Many-to-One model, while Program 2 utilizes System-Contention Scope (SCS) under a One-to-One model. Each program spawns two compute-intensive worker threads ( and ).

Analyzing Program 1 under PCS (Many-to-One Model):

  • In PCS under a Many-to-One model, both user threads and map to a single kernel thread (a single process container).
  • The operating system kernel scheduler is completely unaware of and ; it sees only the parent process and allocates it to one single CPU core.
  • The user-space thread library must time-slice and sequentially on that single core.
  • Result: The second CPU core sits completely idle. The program achieves zero hardware parallelism despite running on a dual-core machine.

Analyzing Program 2 under SCS (One-to-One Model):

  • In SCS under a One-to-One model, and map directly to two separate, independent kernel threads.
  • The OS kernel scheduler treats and as first-class scheduling entities and places both into the global system ready pool.
  • The kernel dispatches onto Core 0 and onto Core 1 simultaneously.
  • Result: Both threads execute in true hardware parallelism, completing the computational workload in approximately half the elapsed time.
Answer:

Under PCS (), threads compete locally inside a single process and are constrained to run on a single CPU core. Under SCS (), threads compete globally at the kernel level and are dispatched simultaneously across separate physical cores, achieving true hardware parallelism.


Exercises

Threads and Thread Scheduling Review

Question 1

What is a thread? Enumerate the resources that are shared among peer threads of the same process, and enumerate the resources that are strictly private to each individual thread. [2078, 2075]

Definition of a thread: A thread is the basic unit of CPU execution within a process. It is an independent execution path with its own program counter, register values, and call stack, operating inside the shared environment of a parent process.

Resources shared among threads: All threads within the same process share:

  1. Text (Code) Segment: The compiled machine instructions.
  2. Data Segment: Global variables and static memory.
  3. Heap Segment: Dynamically allocated memory (malloc / new).
  4. Open Files and Sockets: File descriptor table and network connections.
  5. Signals and System Permissions: Process ID (PID), user credentials, and signal dispositions.

Resources private to each thread: Every thread possesses private copies of:

  1. Thread ID (TID): Unique numeric identifier.
  2. Program Counter (PC): Current instruction execution address.
  3. CPU Register State: General-purpose registers, condition flags, and floating-point registers.
  4. Call Stack: Local automatic variables, function arguments, and return pointers.
  5. Thread-Specific Storage (TLS): Dedicated per-thread static memory buffers.
Answer:

A thread is the fundamental unit of CPU execution. Peer threads share code, global data, the heap, open files, and signals, while maintaining strictly private Program Counters, CPU registers, execution stacks, and Thread IDs.

Question 2

Compare User-Level Threads (ULT) and Kernel-Level Threads (KLT) in terms of creation overhead, context switch latency, blocking behavior on I/O, and multicore scalability. [2078, 2070]

Creation overhead and context switch latency:

  • User-Level Threads (ULT): Managed purely by a user-space thread library without kernel assistance. Thread creation allocates only a local user stack. Context switches occur via local register swapping without trapping into the kernel, taking only tens of nanoseconds.
  • Kernel-Level Threads (KLT): Managed directly by the OS kernel. Creation requires a kernel system call and memory allocation for a kernel TCB. Context switches require hardware mode switches (User Kernel User), taking several microseconds.

Blocking behavior and multicore scalability:

  • Blocking on I/O: In ULT, the kernel is unaware of individual threads; if one user thread executes a blocking system call (e.g., waiting for disk data), the kernel blocks the entire process, stopping all other threads. In KLT, if one thread blocks, the kernel scheduler immediately dispatches another ready thread from the same process.
  • Multicore Scalability: ULTs cannot achieve hardware parallelism; all user threads run on the single core assigned to the process. KLTs scale across all available physical CPU cores concurrently.
Answer:

ULTs feature ultra-fast context switches and low creation overhead, but a single blocking I/O call blocks the entire process, and they cannot scale across multiple CPU cores. KLTs incur higher context switch overhead via system calls, but provide true multicore parallelism and allow peer threads to execute while one is blocked on I/O.

Question 3

Describe the Many-to-One, One-to-One, and Many-to-Many multithreading models. Why has the One-to-One model become the dominant architecture in modern operating systems such as Linux and Windows?

Descriptions of the three multithreading models:

  • Many-to-One (): Maps many user-level threads to a single kernel thread. Thread management is fast and efficient in user space, but lacks multicore execution and blocks entirely if any thread performs blocking I/O.
  • One-to-One (): Maps each user-level thread directly to an independent kernel-level thread. Provides high concurrency; if one thread blocks, others continue running. Can run simultaneously across multiple processor cores.
  • Many-to-Many (): Multiplexes user threads onto kernel threads (). Enables applications to spawn hundreds of user threads while the kernel schedules them across physical cores.

Why the One-to-One model dominates modern operating systems:

  1. Multicore Hardware Proliferation: Modern computing environments feature multi-gigahertz processors with physical cores. The model natively exposes every application thread to the kernel scheduler, extracting maximum hardware parallel performance.
  2. Hardware Acceleration of Kernel Primitives: Kernel context switching and synchronization primitives have become extremely fast, shrinking the overhead gap between user and kernel thread switches.
  3. Simplicity and Reliability: The complex coordination required by models (e.g., scheduler activations, upcalls from kernel to user space) proved fragile and difficult to tune across diverse software workloads.
Answer:

The Many-to-One model maps multiple user threads to one kernel thread; One-to-One maps each user thread to a dedicated kernel thread; Many-to-Many multiplexes user threads onto a pool of kernel threads. The model dominates modern systems (Linux NPTL, Windows) because multi-core hardware requires direct kernel scheduling to achieve true parallelism, and optimized kernel schedulers have minimized context switch overhead.

Question 4

Explain the distinction between Process-Contention Scope (PCS) and System-Contention Scope (SCS) in thread scheduling. How does the choice of contention scope impact thread priority arbitration?

Process-Contention Scope (PCS): Under PCS, thread scheduling competition is local to the process:

  • The user-level thread library schedules user threads onto available kernel LWPs based on thread priorities assigned within that specific application.
  • Priorities are strictly relative: a high-priority thread in Process A only competes against other threads in Process A; it has zero priority standing against threads in Process B.

System-Contention Scope (SCS): Under SCS, thread scheduling competition is system-wide:

  • The OS kernel scheduler arbitrates between all kernel threads belonging to all active processes on the computer.
  • Thread priorities are global: a high-priority thread in Process A will preempt a lower-priority thread in Process B.
Answer:

PCS arbitrates competition locally among threads of the same process via user-space thread libraries; SCS arbitrates competition globally across all threads in the operating system via the kernel scheduler. SCS ensures that high-priority real-time threads take precedence system-wide across all running applications.

Question 5

A software application has a workload where of execution time is fully parallelizable using multithreading, while the remaining is strictly serial.

  1. Use Amdahl's Law to determine the speedup on and processor cores.
  2. What is the maximum theoretical speedup achievable even if thousands of CPU cores are provided?

Applying Amdahl's Law: Serial fraction ; parallel fraction . Amdahl's Law states:

Calculating speedup for cores:

  • For :
  • For :
  • For :
  • For :

Calculating asymptotic maximum speedup ():

Answer:
  1. Theoretical speedups: ( cores), ( cores), ( cores), and ( cores).
  2. The maximum theoretical speedup with infinite cores is ().
Question 6

Define Processor Affinity in multiprocessor scheduling. Distinguish between Soft Affinity and Hard Affinity, and explain why maintaining cache affinity significantly improves multithreaded performance.

Definition of Processor Affinity: Processor Affinity is the preference of an operating system scheduler to bind and execute a thread on the same physical CPU core on which it ran previously.

Soft Affinity vs. Hard Affinity:

  • Soft Affinity: A scheduler policy where the kernel attempts to keep a thread on the same CPU core to preserve cache state, but is permitted to migrate the thread to another core if workload balancing demands it.
  • Hard Affinity: An explicit programmatic binding (via system calls like sched_setaffinity()) that strictly confines a thread to execute only on a designated subset of CPU cores, forbidding the scheduler from migrating it elsewhere.

Why cache affinity improves performance: When a thread runs on a core, its instructions and memory data fill that core's private L1 and L2 high-speed hardware caches. If the thread is migrated to a different core, that core's cache contains none of its data ("cold cache"). The thread incurs hundreds of clock cycles of latency fetching cache lines from shared L3 cache or off-chip main memory. Maintaining processor affinity minimizes cache misses, optimizing memory access throughput.

Answer:

Processor Affinity binds threads to specific CPU cores. Soft affinity is a best-effort heuristic allowing migration during load imbalance; hard affinity strictly forbids migration via system calls. Affinity dramatically improves multithreaded performance by keeping data inside fast private L1/L2 caches, avoiding costly cache misses and main memory access latency.

Past exam questions for Operating System

← Process description, states and control · Scheduling algorithmsPrinciples of concurrency, race condition, critical region · Mutual… →