Chapter 4

Chapter 4: Threads

Objectives

  • Introduction of Threads: Introduce the notion of a thread as a fundamental unit of CPU utilization that forms the basis of multithreaded computer systems.

  • APIs Discussion: Discuss the APIs for the Pthreads, Windows, and Java thread libraries.

  • Implicit Threading Strategies: Explore several strategies that provide implicit threading.

  • Multithreaded Programming Issues: Examine issues related to multithreaded programming.

  • Operating System Support for Threads: Cover operating system support for threads in Windows and Linux.

Single and Multithreaded Processes

  • Components of Processes: Diagrammatically represented components: text, code, data, files, registers, stack, and heap.

  • Single-threaded Process: A process that has only one execution thread.

  • Multithreaded Process: A process that contains multiple threads of execution. Each thread operates within the same address space, meaning they can share resources more efficiently.

Motivation for Multithreading

  • Prevalence of Multithreaded Applications: Many modern applications are multithreaded to facilitate the concurrent execution of tasks.

  • Functionality of Threads: Individual tasks within applications can be handled by separate threads (e.g., updating the display, fetching data, spell checking, answering network requests).

  • Lightweight Thread Creation: Thread creation is significantly lighter in weight compared to process creation.

  • Code Simplification and Efficiency: Multithreading can simplify code and improve overall efficiency, leading to increased responsiveness in applications.

  • Multithreaded Kernels: Modern operating systems often feature multithreading at the kernel level.

Multithreaded Server Architecture

  • Client-Server Interaction: Server creates new threads to service client requests while continuing to listen for additional requests. This architecture supports concurrent client handling.

Benefits of Multithreading

  • Responsiveness: Continues execution in one part of the process while another part is blocked; crucial for user interfaces.

  • Resource Sharing: Threads share resources of the process, making it easier to manage memory than through shared memory or message passing.

  • Economy: Cheaper to create threads than processes; thread switching incurs lower overhead compared to context switching.

  • Scalability: Multithreading allows processes to effectively utilize multiprocessor architectures, enhancing performance.

Multicore Programming

  • Challenges in Multicore Systems: Programmers face challenges in dividing activities, balancing load, and managing data dependencies while debugging.

  • Definitions of Parallelism and Concurrency:

    • Parallelism: Ability of a system to perform multiple tasks simultaneously.

    • Concurrency: More than one task making progress within overlapping time periods.

  • Single-Core Scheduler: On single-core systems, the scheduler provides concurrency through context switches.

Types of Parallelism in Multicore Systems

  • Data Parallelism: Distributes subsets of the same data across multiple cores, applying the same operation on each subset.

  • Task Parallelism: Distributes different threads across cores, with each thread performing a unique operation.

  • Core and Hardware Threading: As the number of threads increases, CPUs also include hardware-level threads to better support threading.

Concurrency vs. Parallelism

  • Concurrent Execution: Achieved on a single-core system, where tasks are interleaved.

  • Parallel Execution: True simultaneous execution on a multi-core system.

User Threads vs. Kernel Threads

  • User Threads: Managed by user-level thread libraries, including:

    • POSIX Pthreads

    • Windows threads

    • Java threads

  • Kernel Threads: Supported directly by the kernel in most general-purpose operating systems, including:

    • Windows

    • Solaris

    • Linux

    • Tru64 UNIX

    • Mac OS X

Multithreading Models

  • Many-to-One Model:

    • Many user-level threads mapped to a single kernel thread.

    • If one thread blocks, all threads block; limited parallelism as only one may access kernel resources at a time.

    • Examples: Solaris Green Threads, GNU Portable Threads.

  • One-to-One Model:

    • Each user-level thread corresponds to a kernel thread.

    • Increased concurrency over many-to-one.

    • Examples: Windows, Linux, Solaris 9 and later.

  • Many-to-Many Model:

    • Supports multiple user threads mapped to multiple kernel threads.

    • Enables the OS to create a sufficient number of kernel threads.

    • Examples: Solaris before version 9, Windows with ThreadFiber package.

  • Two-level Model:

    • Combines features of many-to-many; allows user threads to be bound to kernel threads.

    • Examples: IRIX, HP-UX, Tru64 UNIX, Solaris 8 and earlier.

Scheduler Activations

  • Necessary for many-to-many and two-level models to maintain the correct number of kernel threads allocated to applications.

  • Involves a lightweight process (LWP) concept, which acts as a virtual processor allowing scheduled user threads.

  • Upcalls Mechanism: Scheduler activations provide upcalls, a communication mechanism from the kernel to the thread library, assisting in thread management.

Thread Libraries

  • Function of Thread Libraries: Provide APIs for programmers to create and manage threads.

  • Implementation Methods: 1. Libraries entirely in user space.

  1. Kernel-level libraries supported by the OS.

Pthreads

  • Pthreads Standard: A POSIX standard (IEEE 1003.1c) that acts as both a specification and an implementation guideline for threading.

  • Common in UNIX operating systems, including Solaris, Linux, and Mac OS X.

Implicit Threading

  • Context of Growth: Gaining popularity as the number of threads increases and program complexity grows.

  • Role of Programmers: Programmers focus on identifying tasks instead of managing threads explicitly.

  • Methods for Implicit Threading: 1. Thread Pools

    1. OpenMP

    2. Grand Central Dispatch

    • Other methods include Microsoft Threading Building Blocks (TBB) and java.util.concurrent package.

Thread Pools

  • Concept: Create a pool of threads waiting for tasks.

  • Advantages:

    • Enhanced efficiency as existing threads are reused instead of creating new ones.

    • Limits number of threads to the pool size, optimizing resource usage.

    • Separates task performance logic from thread management.

Fork-Join Parallelism

  • Synchronous Strategy: A library manages thread creation and joining.

  • Application: Useful for divide-and-conquer strategies where tasks are forked and then joined back together.

OpenMP

  • Description: A set of compiler directives that supports parallel programming within shared-memory environments.

  • Usage Example:

    • #pragma omp parallel to create threads.

    • #pragma omp parallel for for parallel for loop execution (example provided in C).

Grand Central Dispatch (GCD)

  • Overview: Technology from Apple for managing concurrency in macOS and iOS, with a corresponding API.

  • Thread Management: Automatically allocates blocks of code for available threads in a dispatch queue.

  • Queue Types: 1. Serial - FIFO order with single processing per task.

    1. Concurrent - FIFO order but allows multiple simultaneous executions.

Intel Threading Building Blocks (TBB)

  • Utility: A template library for parallel programming in C++, managing tasks and balancing loads while being cache-aware.

  • Example of Parallel Loop: A specific example of using the parallel_for statement to run loops in parallel is included.

Threading Issues

  • Critical Topics:

    • Semantics of fork() and exec() system calls.

    • Signal handling (synchronous and asynchronous).

    • Thread cancellation mechanisms (asynchronous vs. deferred).

    • Thread-local storage relevant for managing data across thread executions.

fork() and exec()

  • fork(): Used to create a duplicate process from the calling process, affecting only the calling thread in some systems.

  • exec(): Replaces the existing process with a new program, including its threads.

Signal Handling

  • Signal Functionality: Signals notify processes of events. Each signal has

    • Default and user-defined handlers, overriding the default behavior.

  • Signal Delivery in Multithreading: Needs decisions on whether the signal applies to specific threads, all threads, or a designated thread.

Thread Cancellation

  • Definition: The termination of a thread before completion proposed either through:

    • Asynchronous cancellation terminating immediately.

    • Deferred cancellation allowing periodic checks before execution.

  • Pthread Implementation: Example code provided for creating and canceling threads.

  • Cancellation Mechanism: Default cancellation is deferred; only occurs at designated points or when enabled explicitly by the thread.

Thread-Local Storage

  • Concept: Allows threads to maintain their own unique copies of data, which persists across function invocations. Distinct from local variables but similar to static data.

Operating System Examples

Windows Threads

  • Implementation: Utilizes the Windows API (for various Windows versions) with a one-to-one kernel-level threading model.

  • Thread Components:

    • Thread ID, register set, stacks, private storage area (context of the thread).

  • Primary Data Structures: Includes ETHREAD, KTHREAD, and TEB, defining processes, scheduling info, and thread environment properties.

Linux Threads

  • Terminology: Referred to as tasks and created via the clone() system call.

  • Structure: Uses a struct task_struct to provide comprehensive references to processes and controls behavior regarding address space sharing.

End of Chapter 4

  • Conclusion reflected in threading principles, design patterns, and their implications for operating system support and performance management.

Scanning for accuracy and completeness within your operating systems studies, especially around threading, enhances your understanding of fundamental concepts crucial to modern computing.