Threads and Multithreading Models: short notes (Operating Systems)

Revision mode

Introduction

A thread is a single stream of execution inside a process. A traditional process has one thread; a multithreaded process has several, all running the same program in the same address space. A web server can serve each request in its own thread; a word processor can check spelling in one thread while another reads the keyboard.

Threads exist because processes are expensive to create and switch, and because processes cannot share memory without extra machinery. Threads of one process share code, data, heap and open files, so they communicate through ordinary variables and switch with less work. The price is that shared variables now need synchronization, which is the subject of The Critical-Section Problem.

What threads share and what they own, user-level versus kernel-level threads, the three multithreading models, and the effect of blocking system calls and multiple cores are the distinctions that matter; Amdahl's law bounds the speedup from extra cores.

Prerequisites

Processes, PCB and Process States: PCB, context switch, process states.

Core concepts

Shared and private

Shared by all threads of a process	Private to each thread
Code (text)	Thread ID
Global and static data	Program counter
Heap	Register set
Open files, current directory	Stack (and so local variables)
Signal handlers, user and group IDs	Scheduling state and priority
Address space (page table)	Thread-local storage, if used

Locals are private, globals and heap are shared. A local variable of a thread function lives on that thread's stack. Passing its address to another thread makes it reachable, but it is still memory on the first thread's stack and disappears when that function returns.

A thread control block holds the private part (registers, PC, stack pointer, state); the process's PCB holds the shared part.

Why threads

Responsiveness: one thread can block while others continue.
Resource sharing: no IPC needed for shared data.
Economy: creating a thread and switching between threads of one process is cheaper than for processes, because the address space (page table, and often the TLB contents) does not change.
Scalability: threads of one process can run on different cores at the same time.

Concurrency versus parallelism. Concurrency means several tasks make progress over the same period, possibly by interleaving on one core. Parallelism means several tasks execute at the same instant, which needs several cores. A single-core system can be concurrent but never parallel.

User-level and kernel-level threads

Property	Many-to-one user-level threading (M:1)	One-to-one kernel-scheduled threading (1:1)
Managed by	A thread library in user space	The kernel
Kernel knows about them?	No; it sees one process	Yes; each is scheduled separately
Create and switch cost	Very low: a procedure call, no mode switch	Higher: system call and kernel scheduling
Blocking system call by one thread	Blocks the whole process (all its user threads)	Blocks only that thread
Use of multiple cores	No: the process gets one kernel thread at a time	Yes
Scheduling policy	Application-specific, chosen by the library	Kernel's policy

Multithreading models

The models describe how user threads map onto kernel threads.

Model	Mapping	Blocking call	Parallelism	Examples
Many-to-one	Many user threads on one kernel thread	Blocks all	None	Early Solaris "green threads" library
One-to-one	Each user thread has its own kernel thread	Blocks only the caller	Full	Linux and Windows thread implementations
Many-to-many	$m$ user threads multiplexed on $n \le m$ kernel threads	Another kernel thread can run the rest	Up to $n$ at once	Older Solaris, some research systems

The two-level model is many-to-many that also allows some user threads to be bound to their own kernel thread. One-to-one dominates today because cores are plentiful and kernel threads are cheap enough; its cost is that creating very many threads creates very many kernel objects.

Many-to-one, one-to-one and many-to-many models — Figure 1. Multithreading models: four user threads on one kernel thread (many-to-one), four user threads on four kernel threads (one-to-one), and four user threads on two kernel threads (many-to-many).

How it works: Pthreads

POSIX threads (Pthreads) is a specification, implemented as a library, that may be one-to-one or other.

C11 guarantees long can represent at least -2,147,483,647 to 2,147,483,647; the sums below use long, while thread IDs remain int. Assume the displayed thread creation and join calls succeed.

#include <pthread.h>
long sum[2];                          /* shared: global */
void *worker(void *arg) {
    int id = *(int *)arg;            /* id is local: on this thread's stack */
    for (int i = 0; i < 1000; i++) sum[id] += i;
    return NULL;
}
int main(void) {
    pthread_t t[2]; int ids[2] = {0, 1};
    for (int k = 0; k < 2; k++) pthread_create(&t[k], NULL, worker, &ids[k]);
    for (int k = 0; k < 2; k++) pthread_join(t[k], NULL);
    return sum[0] + sum[1] == 999000L ? 0 : 1;
}

Each thread writes only its own element of sum, so there is no race; each element ends at $0 + 1 + \dots + 999 = 499500$ . pthread_join waits for a thread as wait waits for a child process. Passing &k instead of &ids[k] would be a bug: both threads would read the same changing variable and, if k is declared in the loop, the pointer may outlive k (undefined behaviour).

Threading issues

fork in a multithreaded process. POSIX fork copies only the calling thread into the child. If exec follows at once, this is what is wanted.
Signals. A signal for a process is delivered to one thread that has not blocked it; synchronous signals (such as a segmentation fault) go to the thread that caused them.
Cancellation. Asynchronous cancellation stops the target at once (it may leave shared data inconsistent); deferred cancellation stops it only at cancellation points it checks.
Thread pools. Creating threads in advance and reusing them bounds the number of threads and removes creation time from each request.

Mathematical explanation

Amdahl's law

If a fraction $S$ of a program's running time is inherently serial and the rest can be spread perfectly over $N$ cores, the speedup is

\text{speedup}(N) = \frac{1}{S + \dfrac{1 - S}{N}},

where $0\le S\le1$ , $N\ge1$ . For $S>0$ , this approaches $1/S$ as $N\to\infty$ ; for $S=0$ , ideal speedup is $N$ with no finite asymptotic bound. It is an upper bound: it ignores the cost of creating and synchronizing threads.

Worked examples

Amdahl's law

With $S = 0.25$ and $N = 4$ : speedup $= 1/(0.25 + 0.75/4) = 1/0.4375 \approx 2.29$ . With $N = 8$ : $1/(0.25 + 0.09375) \approx 2.91$ . No number of cores gives more than $1/0.25 = 4$ .

Blocking system calls and models

A process has 4 threads. Each needs 10 ms of CPU and then issues a blocking read that takes 10 ms, after which it finishes. Threads are started in order T1 to T4, and a free CPU always takes the next ready thread.

Model and machine	Completion time	Why
Many-to-one, 1 core	80 ms	Each read blocks the only kernel thread, so nothing overlaps: $4 \times (10 + 10)$
Many-to-one, 2 cores	80 ms	Still one kernel thread; the second core is useless
One-to-one, 1 core	50 ms	T1 computes 0 to 10 and reads 10 to 20 while T2 computes 10 to 20, and so on; T4 computes 30 to 40 and reads 40 to 50
Many-to-many, 2 kernel threads, 2 cores	40 ms	T1 and T2 compute 0 to 10, then their reads hold both kernel threads from 10 to 20; T3 and T4 compute 20 to 30 and read 30 to 40
One-to-one, 2 cores	30 ms	T1 and T2 compute 0 to 10; T3 and T4 compute 10 to 20 while T1 and T2 read; T3 and T4 read 20 to 30

The example shows both weaknesses of many-to-one: no overlap of I/O with computation and no use of extra cores. Many-to-many sits in between: a blocked kernel thread is unavailable to every user thread until its call returns.

Important properties and observations

Threads of one process are not protected from each other: one thread can overwrite any memory of another.
A crash (for example a segmentation fault) in one thread normally kills the whole process.
Switching between threads of the same process skips the address-space switch; switching between threads of different processes costs the same as a process switch.
With M:1 user-level threads and equal per-process kernel scheduling the kernel schedules the process, so a process with 100 user threads gets the same CPU share as a process with one.

Common misconceptions.

"Threads have separate heaps." The heap is shared; only stacks are private.
"User-level threads run in parallel on a multicore machine." Not under many-to-one.
"Kernel-level threads are always better." They cost more to create and switch; user-level threads win when there are many short-lived threads and few blocking calls.

GATE examination perspective

Shared versus private. Stack, registers and PC are private; code, globals, heap and open files are shared. Expect "which of these is not shared".
Blocking behaviour. In many-to-one, a blocking system call by any thread blocks all; in one-to-one, only the caller blocks.
Switch cost ordering. User-thread switch (no kernel entry) is cheapest; kernel-thread switch within one process is next; process switch (address space change) is most expensive.
Multicore. Multicore parallelism requires multiple kernel-schedulable execution contexts. M:N can run at most as many threads at once as the smallest of three counts (runnable user threads, available kernel threads, cores), even though the kernel does not know the user-thread identities.
Amdahl's law. Compute $1/(S + (1-S)/N)$ ; for $0\le S\le1,N\ge1$ , the limit is $1/S$ when $S>0$ ; if $S=0$ , speedup is $N$ .
fork and threads. POSIX fork duplicates only the calling thread.

Summary

A thread is an execution stream inside a process with its own PC, registers and stack.
Threads share code, globals, heap and files, so they communicate cheaply and need synchronization.
M:1 user-level threads are cheap but share one kernel execution context, so a blocking call blocks the mapping and there is no multicore parallelism. 1:1 threads can block independently; M:N can also run in parallel over multiple kernel contexts.
Many-to-one: blocking call blocks all, no parallelism. One-to-one: full concurrency, more kernel objects. Many-to-many: $m$ user threads on $n$ kernel threads.
Concurrency is interleaving; parallelism needs several cores.
Amdahl's law bounds speedup by $1/S$ when $0<S\le1$ ; for $S=0$ , ideal speedup is $N$ , $N\ge1$ , without a finite asymptotic bound.
POSIX fork copies only the calling thread.

Sources

A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley: Chapter 4 (4.1 Overview, 4.2 Multicore Programming, 4.3 Multithreading Models, 4.4 Thread Libraries, 4.6 Threading Issues).
A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4th ed., Pearson: Section 2.2 (2.2.2 The Classical Thread Model, 2.2.3 POSIX Threads, 2.2.4 Implementing Threads in User Space, 2.2.5 Implementing Threads in the Kernel, 2.2.6 Hybrid Implementations).

Introduction

Prerequisites

Core concepts

Shared and private

Why threads

User-level and kernel-level threads

Multithreading models

How it works: Pthreads

Threading issues

Mathematical explanation

Amdahl's law

Worked examples

Amdahl's law

Blocking system calls and models

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps