Threads in Operating Systems

Threads

• Threads are a fundamental unit of CPU utilization in multithreaded computer systems.
• The use of threads simplifies code and increases efficiency.
• Kernels are generally multithreaded

Objectives of Thread

• Introduce the concept of a thread
• Discuss the APIs for Pthreads, Windows, and Java thread libraries.
• Explore strategies for implicit threading.
• Examine issues related to multithreaded programming.
• Cover operating system support for threads in Windows and Linux.

Motivation

• Most modern applications are multithreaded.
• Threads run within an application to implement multiple tasks.
• Process creation is heavy-weight while thread creation is light-weight.

Multithreaded Server Architecture

• A client sends a request to the server
• The server creates a new thread to handle the request.
• The server resumes listening for additional client requests.

Benefits of Threads

• Responsiveness: Continued execution if part of the process is blocked.
• Resource Sharing: Threads share resources, easier than shared memory or message passing.
• Economy: Thread creation is cheaper than process creation.
• Scalability: Processes can take advantage of multiprocessor architectures.

Multicore Programming

• Multicore or multiprocessor systems put pressure on programmers to utilize resources in optimal way.
• Challenges of multicore programming include dividing activities, balancing workloads, splitting data, handling data dependencies, and testing/debugging.
• Parallelism: A system performs more than one task simultaneously.
• Concurrency: More than one task makes progress.
• Concurrency can be achieved via a single processor/core or scheduler.
• Data parallelism distributes subsets of the same data across multiple cores, applying the same operation on each.
• Task parallelism distributes threads across cores, each performing a unique operation.
• CPUs have cores as well as hardware threads.
• Oracle SPARC T4 has 8 cores and 8 hardware threads per core.

Amdahl’s Law

• Amdahl's Law identifies performance gains from adding cores to an application with serial and parallel components.
• Performance is limited by serial sections of code
• The formula for speedup is: speedup ≤ 1 / (S + (1-S)/N), where S is the serial portion and N is the number of cores.

User Threads vs Kernel Threads

• User threads are managed by a user-level threads library.
• Three primary thread libraries are POSIX Pthreads, Windows threads, and Java threads
• Kernel threads are supported by the Kernel.
• Examples of systems that use kernel threads are Windows, Solaris, and Linux.

Multithreading Models

• Many-to-One: Many user-level threads mapped to a single kernel thread.
• One-to-One: Each user-level thread maps to a kernel thread.
• Many-to-Many: Allows many user-level threads to be mapped to many kernel threads.
• Two-Level: Similar to Many-to-Many model, but allows a user thread to be bound to kernel thread

Thread Libraries

• A thread library provides an API for creating and managing threads.
• Libraries can be entirely in user space or supported by the OS kernel.

Pthreads

• Pthreads is a POSIX standard (IEEE 1003.1c) API for thread creation and synchronization.
• It specifies the behavior of the thread library, while the implementation is up to the library developer.
• Pthreads is common in UNIX operating systems like Solaris, Linux, and Mac OS X.

Implicit Threading

• The number of threads increase, program correctness becomes more difficult with explicit threads.
• Creation and management of threads is done by compilers and run-time libraries rather than programmers.
• Methods: Thread Pools, OpenMP and Grand Central Dispatch.
• Other options include Microsoft Threading Building Blocks (TBB), java.util.concurrent package.

Thread Pools

• Thread pools create a number of threads that await work.
• The advantages of using thread pools are that it is usually slightly faster and limit the number of threads.
• Task scheduling becomes more flexible and tasks can be scheduled to run periodically.
• Windows API supports thread pools.

OpenMP

• OpenMP provides support for parallel programming in shared-memory environments.
• It identifies parallel regions, which are blocks of code that can run in parallel.
• Directives are used to create as many threads as there are cores, and code can direct loops to run in parallel.

Grand Central Dispatch

• Grand Central Dispatch (GCD) is an Apple technology for Mac OS X and iOS operating systems.
• GCD includes extensions to C, C++, an API, and a run-time library.
• It allows identification of parallel sections and manages threading details.
• Blocks, which contain code, are placed in dispatch queues and assigned to available threads from a thread pool when they are removed from the queue.

Types of Grand Central Dispatch

• Serial – blocks removed in FIFO order, queue is per process, called main queue
• Programmer can create queues within program
• Concurrent – removed in FIFO order but several may be removed at the same time
• 3 System wide queues with priorities low, default, high

Threading Issues

• Semantics of fork() and exec() system calls.
• Signal handling is the delivery of signals to threads.
• Thread cancellation is terminating a thread before it completes, achieved through asynchronous or deferred cancellation.
• Thread-local storage allows each thread to have its own copy of data and is different from local variables
• Scheduler Activations.

Semantics of Fork and Exec

• Fork duplicates only the calling thread or all threads in the program.
• Some UNIX systems have two version of fork
• Exec usually works as normal - replace the running process including all threads

Signal Handling

• Signals are used in UNIX systems to notify a process that a particular event has occurred.
• A signal handler is used to process signals.
• A signal is generated by an event and delivered to a process.
• The signal is be handled by default (kernel-defined) or user-defined logic.
• Every signal has a default handler that the kernel runs when handling the signal
• A user-defined signal handler can override default
• For single-threaded processes, the signal is generally delivered to the process.

Where Signals are Delivered

• Multi-threaded signal delivery options:
• To the thread to which it applies
• To every thread in the process
• To certain threads in the process
• Assigning a specific thread to receive all signals for the process

Thread Cancellation

• Terminating of a thread before it has finished
• Asynchronous cancellation terminates the target thread immediately.
• Deferred cancellation allows the thread to periodically check if it should be cancelled.

Thread Cancellation requests

• Involves invoking a thread cancellation, actual cancellation depends on the thread state.
• If thread has cancellation disabled, cancellation remains pending until the thread enables it.
• Default type is deferred
• Cancellation only occurs when the thread reaches cancellation point.

On Linux systems

• Thread cancellation is handled through signals

Thread Local Storage

• Thread-local storage (TLS) allows each thread to have its own copy of data.
• Useful when there is no control over the thread creation process (i.e., when using a thread pool)
• It is different from local variables, which are visible only during single function invocation. TLS is visible across functions invocations
• TLS is unique to each thread

Scheduler Activations

• Both M:M and Two-level models require communication to maintain the appropriate number of kernel threads allocated to the application
• Typically use an intermediate data structure between user and kernel threads - lightweight process(LWP)
• Appears to be a virtual processor on which process can schedule user thread to run
• Each LWP attached to kernel thread
• Scheduler activations provide upcalls - a communication mechanism from the kernel to the upcall handler in the thread library
• This communication allows an application to maintain the correct number kernel threads

Operating System Examples

• Windows Threads and Linux Threads

Windows Threads

• Windows implements the Windows API – primary API for Win 98, Win NT, Win 2000, Win XP, and Win 7
• Implements the one-to-one mapping, kernel-level.
• Each thread contains: a thread ID, a register set representing the state of the processor, separate user and kernel stacks, and a private data storage.
• Thread-Local Storage (TLS) is used by run-time and dynamic-link libraries (DLLs).
• The register set, stacks, and private storage area are known as the context of the thread. The primary data structures of a thread include:
• ETHREAD (executive thread block) includes pointer to process to which thread belongs and to KTHREAD, in kernel space
• KTHREAD (kernel thread block) scheduling and synchronization info, kernel-mode stack, pointer to TEB, in kernel space
• TEB (thread environment block) thread id, user-mode stack, thread-local storage, in user space

Linux Threads

• Linux refers to them as tasks rather than threads.
• Thread creation is done through clone() system call
• clone() allows a child task to share the address space of the parent task (process).
• Used flags control behavior.
• struct task_struct points to process data structures (shared or unique).