Threads

1Learning Outcomes¶

• Define thread, program, and process.

• Differentiate between software thread and hardware threads.

• Explain how (and why!) the OS performs context switches.

A thread (short for a thread of execution) is a single stream of instructions. A process is an instance of a currently running program. A process is composed of a single thread’s execution, or multiple threads, which execute concurrently.

Threads are an easy way to describe/think about parallelism, but their implementation is quite complicated and out of the scope of this course. Nevertheless, we describe some details that will help you understand the thread model of execution.

2Thread model of execution¶

2.1Thread state¶

Each thread maintains state as shown in Figure 1:

• Values of its own registers (including stack pointer)

• Value of its own program counter (PC)

• Shared memory (heap, global variables) with other threads

2.2Fork-Join Model¶

We assume that multi-threaded processes run using the fork-join model in Figure 2:

• The “main thread” executes sequentially until the first parallel task region.

• Fork: When the first parallel task region is encountered, the main thread then creates a team of parallel subthreads, which execute to completion.

• Join: When subthreads complete their parallel task region, they synchronize and terminate, leaving only the main thread. The main thread then executes sequentially until it needs to fork another parallel task region.

3A Warning about Threads¶

From UC Berkeley Professor Emeritus Edward Lee:

As we will see over the next few sections, thread-level programming is hard.

4Executing Threads on Hardware¶

We are so sorry,^[2] but we will introduce one more set of terms to describe how threading works in hardware:

• A software thread is one of the threads that composes a multi-thread process. When we colloquially say “thread,” we are usually referring to a software thread.

• Each core provides one (or more) hardware threads that actively execute instructions.

• An active thread is a software thread that is currently mapped to a hardware thread and executing. All software threads that are not active wait until they are able to execute.

A special program called the Operating System “multiplexes”^[3] multiple software threads onto the available hardware threads. With the OS’s help, a single-core CPU can “concurrently” execute many threads by time-sharing the processor between the threads, as shown in Figure 3.

5The OS: Thread Context Switch¶

On most modern computers, the number of active threads is much larger than the number of available cores, so most (software) threads are idle at any given time. The Operating System, or OS, is responsible for (among other tasks) managing which threads get run on which CPU via a process called context switching.

The OS performs a thread context switch for two main reasons:

• Switch out blocked threads (e.g., cache miss, user input, network access). The OS switches to another thread to avoid stalling the CPU for an extended amount of time.

• Timer (e.g., switch active thread every 1 ms). The OS switches to another thread to allow multiple threads to execute concurrently, even when hardware threads are limited.

To switch to a different thread in the process, the OS does the following:

1. Removes the old software thread from the hardware thread by interrupting its execution. Save the old software thread’s state, e.g., register values (including PC value) and stack pointer to memory. Because threads in the same process share memory, we keep any memory tables.^[4]

2. Start executing a different software thread. Load its state into the hardware thread’s registers (including the thread’s PC value). Then, run the hardware thread by reading the value of the PC (which is the address of the next instruction of the newly active thread).

The OS also performs context switches to multiplex different processes; for now, we won’t discuss this. Most of the details of the operating system are out of scope, but we hope a future version of these course note will go into the operating system in more detail. For those interested, please check out CS 61C Spring 2025.

6Hardware Multithreading¶

Up until now we have maintained that one core has one hardware therad running on it. Some architectures can support hardware multithreading—when we run multiple hardware threads* on the same core.

• Logical CPUs: Effectively, the number of hardware threads.

• Physical CPUs are the true number of hardware cores, where each core could potentially have multiple logical CPUs due to multithreading.

Intel chips use hardware multithreading^[5], whereas many modern Apple chips do not. The below lscpu command run on our course hive machines tells us that we have six physical cores and two threads per core for a total of 12 logical CPUs.

$ lscpu
CPU(s):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) 
                          i7-8700T CPU @ 2.40GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1

Briefly—the hardware multithreading model is in Figure 4. Here, each core can run multiple threads at the same time. The two hardware threads share resources like the cache, the ALU unit, etc., but have separate state (PC, registers, etc.) This design leverages “Moore’s Law” because transistors are aplenty.

Hardware multithreading reduces the overhead of a context switch. When the active hardware thread encounters a cache miss, the other hardware thread can be swapped in quickly and run until the data for the original hardware thread available.