Operating System Chapter 4: Threads

Chapter 4: Threads

• Threads: a fundamental unit of CPU utilization that forms the basis of multithreaded computer systems

Motivation

• Most modern applications are multithreaded, where multiple tasks within an application can be implemented by separate threads
• Examples of tasks: update display, fetch data, spell checking, answer a network request
• Process creation is heavy-weight, while thread creation is light-weight
• Kernels are generally multithreaded

Multithreaded Server Architecture

• Benefits:
  • Responsiveness: allows continued execution if part of process is blocked, especially important for user interfaces
  • Resource Sharing: threads share resources of process, easier than shared memory or message passing
  • Economy: cheaper than process creation, thread switching lower overhead than context switching
  • Scalability: process can take advantage of multiprocessor architectures

Multicore Programming

• Challenges:
  • Dividing activities
  • Balance
  • Data splitting
  • Data dependency
  • Testing and debugging
• Parallelism: a system can perform more than one task simultaneously
• Concurrency: supports more than one task making progress, single processor/core, scheduler providing concurrency

Multicore Programming (Cont.)

• Types of parallelism:
  • Data parallelism: distributes subsets of the same data across multiple cores, same operation on each
  • Task parallelism: distributing threads across cores, each thread performing unique operation
• Architectural support for threading:
  • CPUs have cores as well as hardware threads
  • Consider Oracle SPARC T4 with 8 cores, and 8 hardware threads per core

Concurrency vs. Parallelism

• Concurrent execution: on a single-core system
• Parallelism: on a multi-core system

Single and Multithreaded Processes

• Single-threaded process: only one thread of execution
• Multithreaded process: multiple threads of execution

Amdahl's Law

• Identifies performance gains: from adding additional cores to an application that has both serial and parallel components
• S is serial portion: N processing cores
• Formula: Speedup = (1 - S) / (1 - S + S/N)
• Serial portion: has a disproportionate effect on performance gained by adding additional cores

User Threads and Kernel Threads

• User threads: management done by user-level threads library
• Three primary thread libraries:
  • POSIX Pthreads
  • Windows threads
  • Java threads
• Kernel threads: supported by the Kernel
• Examples:
  • Windows
  • Solaris
  • Linux
  • Tru64 UNIX
  • Mac OS X

Multithreading Models

• Many-to-One: many user-level threads mapped to single kernel thread
• One-to-One: each user-level thread maps to kernel thread
• Many-to-Many: many user-level threads mapped to many kernel threads
• Two-level Model: similar to many-to-many, except that it allows a user thread to be bound to kernel thread

Thread Libraries

• Provides programmer with API: for creating and managing threads
• Two primary ways of implementing:
  • Library entirely in user space
  • Kernel-level library supported by the OS

Pthreads

• May be provided: either as user-level or kernel-level
• A POSIX standard: API for thread creation and synchronization
• Specification, not implementation: API specifies behavior of the thread library, implementation is up to development of the library
• Common in UNIX operating systems: Solaris, Linux, Mac OS X

Windows Multithreaded C Program

• Example of creating threads: using Windows API

Java Threads

• Managed by the JVM: typically implemented using the threads model provided by underlying OS
• Java threads may be created by:
  • Extending Thread class
  • Implementing the Runnable interface

Implicit Threading

• Growing in popularity: as numbers of threads increase, program correctness more difficult with explicit threads
• Creation and management of threads: done by compilers and run-time libraries rather than programmers
• Three methods explored:
  • Thread Pools
  • OpenMP
  • Grand Central Dispatch
• Other methods: Microsoft Threading Building Blocks (TBB), java.util.concurrent package

Thread Pools

• Create a number of threads: in a pool where they await work
• Advantages:
  • Usually slightly faster to service a request with an existing thread than create a new thread
  • Allows the number of threads in the application(s) to be bound to the size of the pool
  • Separating task to be performed from mechanics of creating task allows different strategies for running task

OpenMP

• Set of compiler directives: and an API for C, C++, FORTRAN
• Provides support for parallel programming: in shared-memory environments
• Identifies parallel regions: blocks of code that can run in parallel
• Examples: #pragma omp parallel, #pragma omp parallel for