Threads

Introduction

Threads: lightweight units of execution within a process. Enable concurrency, parallelism, efficient CPU utilization. Central to modern operating systems, software design. Facilitate multitasking, responsiveness, resource sharing.

"Threads allow multiple sequences of programmed instructions to run concurrently, improving system efficiency and responsiveness." -- Andrew S. Tanenbaum

Thread Concept

Definition

Thread: smallest schedulable unit of CPU execution. Exists within process context. Shares process resources: memory, file descriptors.

Process vs Thread

Process: independent execution environment, own address space. Thread: execution stream within process, shares address space and resources. Threads communicate via shared memory.

Thread Components

Program counter: instruction pointer. Stack: local variables, function calls. Registers: CPU state. Shared data: heap, global variables.

Context

Thread context: CPU registers, stack pointer, program counter. Switching context saves/restores these to change running thread.

Thread Lifecycle

States

New: thread created but not started. Runnable: ready to run. Running: executing instructions. Waiting/Blocked: waiting for event/resource. Terminated: finished execution.

Transitions

New → Runnable: thread started. Runnable → Running: scheduled by CPU. Running → Waiting: waits on I/O or lock. Waiting → Runnable: event occurs. Running → Terminated: completion or killed.

Lifecycle Diagram

New ↓ start()Runnable ↔ Running ↓ wait()/sleep()Waiting ↑ notify()/signal() ↓ exit()Terminated

Types of Threads

User-Level Threads (ULT)

Managed by user-level libraries, invisible to OS. Fast creation, context switch. Limitations: OS unaware, blocking system calls halt entire process.

Kernel-Level Threads (KLT)

Managed by OS kernel. OS schedules threads independently. Overhead higher but more robust. Supports multiprocessor scheduling.

Hybrid Threads

Combination of ULT and KLT. User threads mapped to multiple kernel threads. Balances overhead and concurrency.

Examples

POSIX Threads (pthreads), Windows threads, Java threads.

Thread Models

Many-to-One Model

Multiple user threads mapped to single kernel thread. Simplicity, low overhead. Drawback: one blocked thread blocks all.

One-to-One Model

Each user thread maps to one kernel thread. True concurrency, better parallelism. Higher resource use.

Many-to-Many Model

User threads multiplexed over a smaller or equal number of kernel threads. Combines benefits of both models.

Comparison Table

Thread Creation and Termination

Creation APIs

POSIX pthread_create(): initializes thread, assigns start routine. Java Thread.start(): spawns new thread. Windows CreateThread(): allocates thread resources.

Attributes

Stack size, scheduling policy, priority, detach state.

Termination

Normal exit: thread finishes function. Cancellation: explicit kill. Detached threads: free resources on exit. Joinable threads: require join() to reclaim resources.

Example Code

pthread_t tid;int status = pthread_create(&tid, NULL, function, arg);if(status != 0) { /* handle error */ }pthread_join(tid, NULL);

Thread Synchronization

Need

Threads share data: race conditions, data inconsistency. Synchronization ensures mutual exclusion, ordering.

Mechanisms

Mutexes, semaphores, condition variables, spinlocks, barriers.

Mutex

Mutual exclusion lock. Only one thread holds at a time. Prevents concurrent access to critical sections.

Semaphore

Counting semaphore: controls access to limited resources. Binary semaphore: similar to mutex.

Condition Variables

Allow threads to wait for certain conditions. Used with mutexes to avoid busy waiting.

Deadlock Prevention

Techniques: resource ordering, lock timeout, avoiding circular waits.

Thread Scheduling

Schedulers

Kernel scheduler: manages kernel threads. User-level schedulers: manage user threads.

Scheduling Policies

Preemptive: time slicing, priority-based. Non-preemptive: cooperative multitasking.

Priority

Threads assigned priorities. High priority threads scheduled first. Priority inversion problem addressed via priority inheritance.

Context Switch

Switching CPU from one thread to another. Overhead affects performance.

Load Balancing

In multicore systems, threads distributed across cores for parallelism.

Algorithm: Round Robin SchedulingFor each thread in ready queue: Assign fixed time quantum Run thread until quantum expires or blocks Move thread to end of ready queue if not finishedRepeat

Advantages and Disadvantages

Advantages

Improved responsiveness, resource sharing, faster context switch than processes, better CPU utilization, simplified program structure for concurrent tasks.

Disadvantages

Complex synchronization, risk of deadlocks, debugging difficulty, potential for race conditions, increased overhead with too many threads.

Performance Impact

Optimal thread count depends on CPU cores and workload. Excessive threads cause overhead, context switching delays.

Security

Shared address space risks data leaks, requires careful programming.

Threads vs Processes

Resource Sharing

Threads share memory and resources. Processes have isolated address spaces.

Creation Overhead

Threads created faster with less resource allocation than processes.

Communication

Threads communicate via shared memory easily. Processes require IPC mechanisms: pipes, message queues.

Fault Isolation

Process failure isolated, threads failure can crash entire process.

Common Problems in Multithreading

Race Condition

Multiple threads access shared data without synchronization. Leads to inconsistent or incorrect results.

Deadlock

Two or more threads wait indefinitely for resources held by each other. Conditions: mutual exclusion, hold and wait, no preemption, circular wait.

Starvation

Low priority threads never scheduled due to higher priority threads always running.

Priority Inversion

Lower priority thread holds resource needed by higher priority thread, causing delays.

Debugging Challenges

Non-deterministic behavior, timing-dependent bugs, difficult to reproduce errors.

Applications of Threads

Web Servers

Handle multiple client requests concurrently to improve throughput.

Interactive Applications

Maintain UI responsiveness while performing background tasks.

Parallel Computing

Divide tasks across multiple threads for faster computation on multicore processors.

Real-Time Systems

Use threads with priorities for timely response to events.

Operating Systems

Implement multitasking, background services, device drivers using threads.

References

• A. S. Tanenbaum, Modern Operating Systems, 4th ed., Pearson, 2014, pp. 297-345.
• B. Goetz et al., Java Concurrency in Practice, Addison-Wesley, 2006, pp. 15-63.
• W. Stallings, Operating Systems: Internals and Design Principles, 9th ed., Pearson, 2018, pp. 110-156.
• M. Ben-Ari, Principles of Concurrent and Distributed Programming, 2nd ed., Addison-Wesley, 2006, pp. 40-90.
• R. Love, Linux Kernel Development, 3rd ed., Addison-Wesley, 2010, pp. 230-275.