Threads and Concurrency

Overview

• Modern applications are multithreaded
• Threads operate within applications, allowing multiple tasks to be implemented separately
• Kernels are multithreaded; kernel threads are created during system boot on Linux systems
  • Kernel threads manage devices, memory, and interrupt handling

Benefits of Threads

• Responsiveness may allow continued execution if part of process is blocked, especially important for user interfaces
• Resource Sharing threads share resources of a process, easier than shared memory or message passing
• Economy cheaper than process creation; thread switching lowers overhead compared to context switching
• Scalability processes can leverage multicore architectures

Thread Execution State

• Main thread states: running, ready, blocked
• Thread operations associated with state changes: spawn, block, unblock, finish

Multicore Programming

• Concurrent execution on a single-core system gives the appearance of parallelism
• Parallelism on a multi-core system truly execute at the same time
• Parallelism allows a system to perform more than one task simultaneously
• Concurrency enables multiple tasks to progress, handled by a scheduler concurrency in a single processor or core

User Threads

• Management of user threads is done by a user-level threads library
• Primary thread libraries include POSIX Pthreads (used in UNIX and Linux), Windows threads, and Java threads

Kernel Threads

• Supported directly by the kernel
• Used by general-purpose operating systems like Windows, Linux, Mac OS X, iOS, and Android

User-Level Threads (ULTs)

• All thread management is handled by the application
• The kernel is unaware of the existence of threads
• Scheduling can be application-specific
• ULTs can run on any OS
• Thread switching does not require kernel mode privileges

Disadvantages of ULTs

• Many OS system calls are blocking
• When a ULT executes a system call, all threads within the process are blocked
• A multithreaded application cannot take advantage of multiprocessing, as a kernel assigns only one processor to one process at a time

Kernel-Level Threads (KLTs)

• Thread management is done by the kernel
• There is no thread management code in the application level, simply an application programming interface (API) to the kernel thread facility
• Windows uses this approach

Advantages of KLTs

• The kernel can simultaneously schedule multiple threads from the same process on multiple processors
• If one thread in a process is blocked, the kernel can schedule another thread of the same process
• Kernel routines themselves can be multithreaded

Disadvantages of KLTs

• Control transfer from one thread to another within the same process requires a mode switch to the kernel

Multithreading Models

• Many-to-One maps many user-level threads to a single kernel thread
• One-to-One maps each user-level thread to a kernel thread
• Many-to-Many maps multiple user-level threads to multiple kernel threads

Many-to-One Model

• Multiple user-level threads are mapped to a single kernel thread
• One thread blocking blocks all threads
• Multiple threads may not run in parallel on multi-core systems, as only one may be in the kernel at a time
• Few systems currently use this model
• Examples: Solaris Green Threads, GNU Portable Threads

One-to-One Model

• Each user-level thread maps to a kernel thread
• Creating a user-level thread creates a kernel thread
• Provides more concurrency than many-to-one
• The number of threads per process may be restricted due to overhead
• Examples: Windows, Linux

Many-to-Many Model

• Permits multiple user-level threads to be mapped to multiple kernel threads
• Allows the operating system to create sufficient kernel threads
• Utilized by Windows with the ThreadFiber package

Two-level Model

• Similar to Many-to-Many, but allows a user thread to be bound (directly linked) to a kernel thread
• Solaris is an example

Thread Libraries

• Provides an API for creating and managing threads
• Can be implemented entirely in user space (user-level library) or supported by the OS (kernel-level library)
• Three primary thread libraries: POSIX Pthreads, Windows threads, and Java threads

Two general strategies for creating multiple threads

• Asynchronous threading: allows the parent thread to resume execution concurrently and independently after creating a child thread
• Synchronous threading: requires the parent thread to wait for all child threads to terminate before resuming

Pthreads

• May be provided as user-level or kernel-level
• Complies with the POSIX standard(IEEE 1003.1c) API for thread creation and synchronization
• API specifies the behavior of the thread library; implementation is up to the library's development
• Common in UNIX operating systems like Linux and Mac OS X

Windows Threads

• Serves as the primary API for Windows applications
• Implements a one-to-one mapping at the kernel level
• Each thread contains a thread ID, register set, separate user and kernel stacks, a program counter, and a private data storage area utilized by run-time and dynamic link libraries (DLLs)
• Context of the thread is the register set, stacks, and private storage area

Windows Threads Data Structures

• 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

Java Threads

• Are managed by the JVM
• Typically implemented using the underlying operating system's threads model
• Creation of Java threads can be done by extending the Thread class or implementing the Runnable interface
• Implementing the Runnable interface is standard practice