Threads and Multithreading

# Threads and Multithreading

4.1 Why Threads: Motivation and Definition

The previous session covered the difference between a process and a thread. This session dives into threads alone. The roadmap: the multithreading models available, the thread APIs (pthreads, Windows threads, Java threads), implicit threading, the issues that come with multithreaded programs, and finally the operating system support for threads in Linux and Windows. The next session returns to processes alone, with process scheduling and process synchronization.

Why create threads at all? Real applications have many small jobs that can run at the same time, and each job can be handed to its own thread.

The idea is not new. In the older process-based design, an application that wanted many concurrent conversations had to create a whole new process for each one — copying the code, the data, and all the memory. That is why, before threads became popular, the "one process per request" style of concurrency was known to be slow and memory-hungry. Threads give the same concurrency without that copying bill. The two examples below are the professor's way of making this concrete.

4.1.1 The Word Processor Example

Take a word processing application. While I type some information, I also paste an image, and at the same time the spellcheck runs. Everything happens in parallel, so each of these jobs can be treated as a thread of its own. The threads live inside the same application, and the user cannot see them — from the outside it looks like one program quietly doing everything at once. Inside, the threads do the jobs one by one.

The mapping is explicit: the typing keystrokes get thread T1, the image paste gets thread T2, the spellcheck gets thread T3. All three threads share the same document in memory — the same code (the editor's program text) and the same data (the document buffer). If T3 finds a misspelled word, it can mark it directly in the document that T1 is editing, because both see the same buffer. The user never sees three programs; they see one editor window. The threads are invisible workers inside one application.

4.1.2 The Browser Example

Real-world: a browser on a shopping site. You type a query and the first page loads. You select an item; images and multimedia start playing on the page. Meanwhile you click the submit button to add the item to the cart. These are all separate tasks, and the application does them in parallel with the help of threads. It becomes very easy when they share the code and the data. Only in very few cases does a thread need data of its own — that case comes up later in this session.

Notice what makes the browser example feel so natural: page loading, media playback, and cart operations all work on the same page object, the same session, the same cookies. If they were separate processes, they would need explicitly arranged shared memory or message passing just to agree on what is in the cart. As threads of one process, they read and write the same data by default, with no extra machinery. The professor's aside — "only in very few cases does a thread need data of its own" — is a preview of thread-local storage, which we meet in section 4.11.

4.1.3 What a Thread Is

A thread — a lightweight process — is a program in action, or a task in execution. If an application has multiple small tasks to perform, it can create a thread for each, and each thread runs in parallel. From the user's point of view it is as if the same application (the same process) is doing all the work; what really happens is that multiple threads are created and each one does its part.

The definition in plain words: a thread is one running task inside a program. The professor's phrase "a program in action" is deliberate — a static file on disk is not a thread; a thread exists only while the program is being executed. When the application decides it has three small tasks, it creates three threads; the scheduler then decides which thread actually gets a processor at any moment. The user's view ("one application doing everything") and the system's view ("several threads, each doing its part") are both correct — they describe the same situation from the outside and from the inside.

4.1.4 Threads vs Processes: Heavyweight vs Lightweight

Process creation is heavy. When you create a process, you must give it its own address space — the code has to be separate, the data has to be separate, everything is allocated separately for the parent P1 and for the child P2. Threads do not do this. Threads share the address space, and they share the data and the code. That sharing is what makes them light, and it increases efficiency.

To see the difference in concrete terms, think of what a process table entry must describe: memory map, open file table, signal handlers, security context, plus the execution context. Creating process P2 means building a whole new instance of all of that. Creating a thread inside P1 means adding one new execution context — registers and a stack — that points back at the already-existing code and data. That is why thread creation is measured in roughly tens of microseconds while process creation costs an order of magnitude or more. Measured on one Unix-like system, creating a thread takes about ten times less time than creating a process, and switching between two threads of one process takes about five times less time than switching between processes.

The takeaway from the table: threads are light precisely because they own only what execution needs (registers, stack) and borrow everything else. This is the professor's core contrast of the session, and it returns in section 4.5 when we look at the layout of a threaded process in detail.

4.1.5 Multithreaded Servers

Real-world: most web servers are multithreaded. When a client makes a request, the server does not sit idle waiting for only that one client. It listens and services requests from many clients at once. When the first request arrives, it creates a new thread and hands the request to that thread; when the next request arrives, it goes to the next thread, and so on. This is how the server processes many clients with the help of multithreading.

That example brings out the main benefits of multithreaded programming, which we now take one by one: responsiveness, resource sharing, economy, context switching, and scalability.

In the broader field, multithreading is the default structure of nearly every interactive and server-side system you will meet: web servers and database servers (a thread per request or per connection), GUI frameworks (a UI thread plus worker threads), media players (a decode thread, a render thread, a network thread), and even operating-system kernels themselves, which run kernel threads for device and interrupt management. When you later meet process scheduling and synchronization in the next sessions, keep this section's picture in mind: scheduling decides which thread runs next, and synchronization exists precisely because threads share data so freely.

4.2 Benefits of Multithreaded Programming

The web server trace in section 4.1 delivered the payoff list. The professor takes the five benefits one by one: responsiveness, resource sharing, economy, context switching, and scalability. Keep the web server in mind while reading them — each benefit is exactly the property that server relies on.

4.2.1 Responsiveness

Responsiveness means nothing gets blocked. Suppose a program has four threads. Even if one thread is blocked, the others continue, because each thread is in execution and each is independent — one thread does not affect the other.

A thread becomes blocked when it waits for something — an I/O operation, a network reply, a lock. In a single-threaded program, a blocked program is a frozen program: the user clicks and nothing happens. In a four-thread program, the thread that is waiting is the only one that stops; the other three keep running. This is what a browser uses when an image is loading slowly: the image-loading thread blocks, but the thread that reads your clicks continues, so the page stays responsive. Responsiveness is the user-visible benefit — the application never appears to freeze.

4.2.2 Resource Sharing

Threads share the resources of their process: messages, information, data, and memory. Sharing is far easier between threads of one process than between separate processes, which need their own address spaces.

This is the default behaviour, and that default is the point. Two processes can share data only through machinery the programmer must explicitly build: shared memory regions or message passing, both of which pass through the kernel. Two threads of one process simply use the same memory — if T1 updates a variable, T2 sees the update when it reads that location. The shopping-cart example from section 4.1 works exactly this way: the media thread and the cart thread read and write the same session data without any IPC machinery. The word "messages" in the professor's list refers to the message-based communication that threads can also use within a process — but with shared memory available by default, it is rarely needed between sibling threads.

4.2.3 Economy

Creating threads is cheap. The overhead of creating a thread is much smaller than the overhead of creating a process, so multithreading brings an economy of creation and management.

The cost difference is not symbolic. Because a thread needs only a new execution context (registers and a stack) while a process needs a duplicated address space, thread creation costs a small fraction of process creation: on one Unix-like system, thread creation is about ten times faster than process creation, and thread context switching about five times faster. There is also an economy of management: terminating a thread is as cheap as creating it, and the operating system has less state to maintain for a thread than for a full process. For workloads that create and destroy execution units constantly — a web server handling thousands of short requests — that difference is the difference between an overloaded machine and a responsive one.

4.2.4 Context Switching

When the operating system switches between processes, it has to save the state of the previous process, load the next process into memory, and only then start executing — that sequence creates overhead. In the case of context switching between threads, the overhead is much smaller, because everything the threads need lives in the same address space.

A context switch is the operating system's act of pausing one execution unit and starting another: save the outgoing unit's registers and program counter, load the incoming unit's, and continue. Switching between two processes also requires switching address spaces — the memory maps and page tables that describe where each process's code and data live. Switching between two threads of the same process skips that part entirely: both threads use the same address space, so the switch is just register-and-stack bookkeeping. The professor's sequence — save state, load next, start executing — still happens, but the expensive middle step (loading a new address space) disappears.

4.2.5 Scalability

In multiprocessor architectures, multithreaded programs scale well: with more than one processor available, each processor can take a thread and run it, so the work spreads across the hardware.

Scalability means the application gets faster as you add hardware. A single-threaded process can run on only one processor at a time, no matter how many the machine has. A multithreaded process with enough threads can put a different thread on each processor, so adding processors adds throughput — up to the limit imposed by Amdahl's law (section 4.6). This is the benefit that connects threads to the hardware trend of the last two decades: as chips moved from one core to many cores, only multithreaded software could use the new cores at all.

In the broader field, these five benefits are the standard evaluation checklist for threading: when engineers debate whether to make a server, a game engine, or a database multithreaded, they weigh responsiveness against synchronization risk, economy against correctness. The database world, for example, runs each connection on its own thread and each query planner as a parallel worker — pure resource sharing plus scalability — and the games industry reports that coarse-grained threading (one module per core) reliably raises performance while fine-grained threading is much harder to get right.

4.3 Multiprocessor and Multi-Core Systems

The previous section ended with scalability — the one benefit that needs multiple processors. Now the lecture looks at the hardware itself: what a multiprocessor system is, why using many cores well is hard, and the two execution styles the hardware enables.

4.3.1 What a Multiprocessor System Is

A multiprocessor system is a system with multiple processors. Today this usually means a single chip that carries multiple cores, and each core is capable of executing work. Each core can run its own process, and the system as a whole gains raw computing power.

Historically, a multiprocessor meant several separate CPU chips wired together. Today the same idea lives inside one chip: a multi-core processor is a single die containing several complete processing units (cores), each with its own execution pipeline and its own cache, sharing the chip. To the operating system each core looks like an independent processor: it can run its own process, and the machine's total computing power is roughly the sum of the cores. A four-core chip can genuinely execute four instructions at the same instant — one per core.

4.3.2 Challenges of Multi-Core Systems

Using many cores well raises challenges that must be handled:

• Divide the activities. An application such as a word processor has many jobs; they must be split up and handed to each core.
• Keep cores balanced. If there are two cores C1 and C2, one must not be overloaded while the other idles. Both should take more or less the same execution time for a given task.
• Split the data properly.
• Avoid data dependency. If C1 has to wait for C2 to update something, the task stops there and has to be suspended. That should not happen.
• Keep testing and debugging easy. When multiple cores run different tasks, tracing a fault should not become a nightmare.

From a multi-core or multiprocessor system you can get either parallelism or concurrency.

4.3.3 Parallelism vs Concurrency

Parallelism means the system performs multiple tasks at the same instant — simultaneously. That requires more than one core, because everything happens at the same time. Concurrency also handles more than one task, but to the user it only seems that many things happen in parallel; inside, the tasks take turns. Concurrency can be provided by a single processor or a single core: the scheduler runs multiple tasks one after another, in a time-sliced manner or however it is arranged, so even with one core you can operate several tasks. Parallelism is the stronger claim — the tasks genuinely overlap in time — and concurrency is the weaker one: interleaving on one core. With multiple cores, both are available; with a single core, only concurrency is.

The distinction is the lecture's key vocabulary pair of this session, and the professor's phrasing gives the crisp rule: concurrency is about dealing with many things at once; parallelism is about doing many things at once. A single core can be concurrent but never parallel; multiple cores can deliver both.

In the broader field, the parallelism-versus-concurrency vocabulary is the foundation of all parallel computing: chip vendors (Intel, AMD, ARM, NVIDIA) scale core counts to tens and hundreds, and every performance claim about "parallel" software is really a claim about how well the five challenges were solved. Database servers, video encoders, and game engines all report near-linear scaling on carefully balanced workloads — and mediocre scaling when balance or dependency dominates.

4.4 Data Parallelism and Task Parallelism

Section 4.3 established that multiple cores can run tasks in parallel — but where does the parallelism come from? The professor splits the answer in two: parallelism in the data, and parallelism in the tasks.

4.4.1 Data Parallelism

In data parallelism, a subset of the same information is spread across different cores, and the same operation is performed on all of them. For example, take a loop that performs a sum:

$$\text{for }(i=1;i<10;i++):\text{sum}\leftarrow \text{sum}+i$$

This is an operation repeated on the same set of data, so the iteration can be distributed across different cores: each core runs the same operation on its subset of the data. That is data parallelism.

The defining pattern: one operation, many pieces of data. The loop body sum ← sum + i is identical for every i; only the value of i changes. The loop's 9 iterations can be carved up — say core C1 takes i = 1, 2, 3; core C2 takes i = 4, 5, 6; core C3 takes i = 7, 8, 9 — and each core executes the same instruction on its own subset. Image processing, matrix multiplication, and video encoding are data-parallel workloads for exactly this reason: thousands of pixels or matrix entries, one operation.

4.4.2 Task Parallelism

In task parallelism, the work itself is different. We distribute threads across the different cores, and each thread performs a unique operation. The word processor and browser examples from the start of this session are task parallelism: typing, pasting an image, and spellchecking are different operations, each given to its own thread.

The defining pattern: many different operations, possibly on different data. Each thread runs its own code — the keystroke handler, the image renderer, the spellchecker. Nothing is duplicated across cores; instead the application's tasks are handed to different threads, and the threads to different cores.

Real programs combine both: a browser's spellcheck thread (task parallelism) may itself run a dictionary lookup over many words in parallel (data parallelism). When to pick which: if the work is one uniform operation over lots of data, choose data parallelism — it is the easiest to balance; if the application naturally consists of distinct responsibilities, choose task parallelism — but expect balance to be harder to achieve, since different tasks take different times.

4.4.3 Threads and Cores: Oracle SPARC T4

The number of threads you can run depends on the number of CPUs in the machine. Based on the number of CPUs you can create that many threads, and let each thread execute on one CPU. Real-world: Oracle's SPARC T4 processor has 8 cores with 8 hardware threads per core. With 4 such cores, 4 cores × 8 threads per core = 32 threads can be created. The number is not fixed at 8 or 10 anymore — vendors keep adding cores: chips with 16 cores exist, and NVIDIA and AMD ship up to 64 cores. So the number of threads that can be created multiplies accordingly, across Intel, ARM, AMD, and other architectures.

4.4.4 Concurrent vs Parallel Execution

The two execution styles line up with concurrency and parallelism. On a single core, execution is concurrent: start with T1, then T2 continues, then T3, T4. Even if T1 has not finished, in a time-sliced manner it has to come out after its slice — say two seconds — and wait for its next turn; T2 gets the same time, whether it finishes or not. On multiple cores, execution can be parallel: run two threads on one core and another two on another core — T1 and T3 on one, T2 and T4 alternating on the other, working at the same time. When the number of cores grows, the operating system has to provide the support that lets the parallelism grow with it.

This is the lecture's execution diagram, and it is worth drawing in words. One core: the timeline is a single line; at time 0–2s T1 runs, at 2–4s T2 runs, at 4–6s T3 runs, at 6–8s T4 runs, then back to T1 — each thread gets a fixed slice (say two seconds) and leaves the core when its slice ends, whether its work is finished or not. Two cores: the timeline splits into two lines; T1 and T3 share core C1 (interleaved in slices), while T2 and T4 share core C2 — at any instant two threads are genuinely executing, one per core. Adding cores adds lines to the timeline, and the operating system's scheduler is what draws the lines: it must keep enough threads ready to fill every core. That is what the professor means by "the operating system has to provide the support that lets the parallelism grow" — scheduling, load balancing, and the hardware-awareness of section 4.3.

In the broader field, this split is the vocabulary of every parallel framework you will meet later: OpenMP's parallel for is data parallelism, GCD dispatch queues are task parallelism, and GPU programming (NVIDIA CUDA, AMD ROCm) is almost pure data parallelism — thousands of cores, one instruction stream per data element.

4.5 Single-Threaded and Multithreaded Processes

4.5.1 The Layout of a Threaded Process

In a single-threaded process there is only one thread, and that thread uses the process's code, data, files, registers, and stack. In a multithreaded process, the code, the data, and the files are shared by all threads, but the registers and the stack are separate for each thread. The registers are limited by hardware: if the number of CPUs is larger, there are more registers available; otherwise, when multiple threads outnumber the registers per CPU, the registers have to be split, and the same holds for the stack. So the rule to remember: code, data, and files are shared; registers and stack are per-thread.

This layout is exactly what operating systems implement in practice: Solaris keeps a process control block with one thread-control-block per lightweight process, Linux's clone() system call takes flags such as CLONE_VM and CLONE_FILES to decide which pieces the new task shares, and Windows XP threads carry a thread ID, register set, user and kernel stacks, and a thread-local storage array — all wrapped in the thread environment block.

4.6 Amdahl's Law

4.6.1 The Speedup Formula

When you add cores to an application, how much faster does it get? Amdahl's law answers that. Let $S$ be the serial portion of the application — the fraction that must run one task after another, sequentially — and let $N$ be the number of cores. Serial means sequential, one task followed by the next; parallel means everything happens at once. The speedup of the performance gain is:

$$\text{Speedup}(N)=\frac{1}{S+\frac{1-S}{N}}$$

Here $S\in [0,1]$ is the serial fraction of the application, and $N$ is the number of cores that work on the parallel portion $1-S$.

Why the formula has this shape — the derivation. Speedup is defined as the ratio of two running times:

$$\text{Speedup}(N)=\frac{\text{time on 1 processor}}{\text{time on }N\text{ processors}}$$

Call the total single-processor time $T$. Of that time, a fraction $S$ is serial: it can only run on one core, so it still takes $T\cdot S$ no matter how many cores exist. The remaining fraction $1-S$ is perfectly parallelizable: spread over $N$ cores, it takes $T\cdot \frac{1-S}{N}$. The new total time is so

$$T_{\text{new}}=T\cdot S+T\cdot \frac{1-S}{N}=T\left(S+\frac{1-S}{N}\right)$$

and the speedup is the old time $T$ divided by the new time:

$$\text{Speedup}(N)=\frac{T}{T\left(S+\frac{1-S}{N}\right)}=\frac{1}{S+\frac{1-S}{N}}$$

which is exactly the professor's formula. The denominator is the average time per unit of work — the serial part at full cost plus the parallel part discounted by $N$.

4.6.2 Worked Example: Two Cores with 25% Serial Code

Take $N=2$ cores and a serial portion $S=25\%$, which is $0.25$. Substitute step by step:

$$1-S=1-0.25=0.75$$

$$\frac{1-S}{N}=\frac{0.75}{2}=0.375$$

$$S+\frac{1-S}{N}=0.25+0.375=0.625$$

$$\text{Speedup}(2)=\frac{1}{0.625}=1.6$$

So with two cores and 25% serial code, the speedup is 1.6 times. If $N$ increases to 4, the speedup grows again — it increases with the number of cores.

4.6.3 The Limit as N Grows

What happens if we keep adding cores? When $N$ approaches infinity, the term $(1-S)/N$ becomes zero, and the formula collapses to:

$$\underset{N\to \infty }{\lim }\text{Speedup}(N)=\frac{1}{S}$$

The serial portion of the application has a disproportionate — not proportionate — effect on the performance gained by adding cores. If the serial portion were 100%, the whole application would be serial and the formula gives $1/S=1$: no gain at all, no matter how many cores. That is why the serial part is the bottleneck.

The limit is the punchline: $\frac{1-S}{N}\to 0$ as $N\to \infty$, leaving the denominator $S+0=S$, so the speedup can never exceed $1/S$. For the 25%-serial program, that ceiling is $1/0.25=4\times$ — no amount of cores can make that program more than four times faster. Only shrinking $S$ raises the ceiling.

Visual intuition. Draw the speedup curve with the number of cores $N$ on the horizontal axis and $\text{Speedup}(N)$ on the vertical axis. The curve starts at (1, 1) and rises steeply at first — for the 25% case, 1.6 at $N=2$, 2.29 at $N=4$ — then flattens as it approaches the horizontal asymptote $y=1/S=4$. Every doubling of cores adds a smaller increment, and the curve never touches the asymptote. The takeaway in one line: the curve climbs toward $1/S$ and stops; the serial fraction draws the ceiling.

4.6.4 Student Questions: Amdahl's Law and Contemporary Multi-Core Systems

In the broader field, Amdahl's law is the standard argument in every performance engineering discussion — chip vendors use it to justify core counts, cloud providers use it to price CPU hours, and database and game-engine teams use it to decide where optimization effort goes: attacking the serial fraction pays off permanently, while adding cores pays off only up to the $1/S$ ceiling.

4.7 User Threads and Kernel Threads

4.7.1 Kernel Threads

A kernel thread is a thread that is executed in the kernel space, and it is supported by the kernel. Real-world: essentially all major operating systems support kernel threads in one way or another — Windows, Solaris, Linux, Unix, and Mac OS.

4.7.2 User Threads

A user thread is a thread that is executed in the user space. It is managed by the user-level thread library, not directly by the kernel.

4.7.3 Thread Libraries

The thread libraries in common use are POSIX pthreads, Windows threads, and Java threads. Pthreads threads and their libraries are examined in detail in section 4.9.

The two spaces. Every modern machine runs with two execution spaces: kernel space, where the operating system itself executes privileged code, and user space, where applications run. A kernel thread lives in kernel space: the kernel creates it, keeps its data structures inside the kernel, schedules it, and switches between kernel threads — Windows, Solaris, Linux, Unix, and Mac OS all support them. A user thread lives in user space: it is created and managed by a user-level thread library (a package of routines for creating, destroying, scheduling, and context-switching threads) and the kernel may not even know it exists. The kernel schedules the process that hosts the user threads; the library decides which user thread runs inside the process.

The comparison. The professor's two definitions sit on two axes: where the thread executes (kernel vs user space) and who manages it (kernel vs user-level library). The trade-off table:

When to pick which: user threads win when you need very cheap threads within one process and do not need true multi-core parallelism; kernel threads win whenever a blocked thread must not stall the process or when the threads must run in parallel across cores. Most modern systems combine them — user threads mapped onto kernel threads — which is exactly what section 4.8 formalizes as the multithreading models.

In practice, this distinction drives how languages and operating systems are built: the Java Virtual Machine maps its threads onto the host's threads (Win32 API on Windows, Pthreads on Linux and Mac OS X), and Solaris historically ran its JVM on green threads — a user-level library — before moving to one-to-one kernel mapping. When you see a framework advertise "lightweight threads" (goroutines, fibers), you are seeing the user-thread idea reappear on top of kernel threads.

4.8 Multithreading Models

Three classic models describe how user threads map onto kernel threads: many-to-one, one-to-one, and many-to-many, plus a variation called the two-level model.

Think of user threads as customers and kernel threads as checkout counters that can actually reach the hardware. The model decides how the customers line up against the counters. With one counter, only one customer is served at a time; with one counter per customer, every customer has a dedicated server; with several counters shared by all customers, service happens in parallel up to the counter count. Keep this picture while the four models are defined.

4.8.1 Many-to-One

The name says it: many user threads are mapped to only one kernel thread. The advantage is simplicity; the disadvantage is that not all threads can run in parallel — even on a multi-core system. Every action needs the kernel: a user thread request must reach the kernel, and from there the hardware. With only one kernel thread, the second user thread, the third, the fourth — all of them have to wait and take turns. So despite owning a multi-core system, true multithreading cannot be achieved. Real-world: Solaris green threads and GNU Portable Threads use this model.

4.8.2 One-to-One

Here each user thread maps to one kernel thread. The advantage is that more than one task can run at a time, because every user thread has its own kernel thread underneath. The disadvantage is the overhead of creating as many kernel threads as user threads: if I have 10 threads, I have to create 10 kernel threads. Real-world: Windows, Linux, and Solaris 9 and later use the one-to-one model.

4.8.3 Many-to-Many

Many user threads are mapped to many kernel threads, and the numbers need not match. Five user threads with three or four kernel threads are enough to achieve multithreading on a multi-core system. Real-world: earlier versions of Solaris used this model, and Windows uses it with the thread fiber package.

4.8.4 Two-Level Model

The two-level model is a variation of many-to-many. It works like many-to-many, but a user thread is always bound to a particular kernel thread. The number of user threads is still larger than the number of kernel threads, yet each user thread gets the opportunity to be bound to one kernel thread. There is some overhead — one thread or another will be waiting. Real-world: IRIX, HP-UX, Tru64, and Solaris 8 and earlier use the two-level model; Solaris 9 and later switched to one-to-one.

The comparison. All four models side by side:

The professor's exam-intel version of this table: Solaris moved from two-level to one-to-one at version 9; Windows pairs one-to-one with a fiber package for many-to-many; green threads give Solaris its many-to-one heritage.

Visual intuition. Draw the models as two rows of circles — user threads on top, kernel threads below — with arrows between them. Many-to-one: a fan of many arrows from above converging into one circle below. One-to-one: identical vertical arrows, 1:1. Many-to-many: a dense web of arrows between unequal rows. Two-level: the same dense web, but one top circle has a single bold arrow locked to one bottom circle. The takeaway: the arrow pattern is the model — count how many bottoms each top can reach, and you know the parallelism.

In practice this vocabulary explains the threading behavior you observe daily: a JVM on Windows maps each Java thread to a kernel thread (one-to-one), while the same JVM on an older Solaris ran on green threads (many-to-one). Modern Linux NPTL threads are one-to-one kernel threads, and lightweight "goroutine" schedulers in languages like Go are many-to-many arrangements of user-level tasks over a small kernel-thread pool.

4.9 Thread Libraries and Thread APIs

4.9.1 What a Thread Library Does

A thread library is a collection of APIs — application programming interfaces — that help you create and manage threads. There are two ways such a library can work: the library can live entirely in the user space, or a kernel-level library can support the threads that are present in the user level. Either way, the library is what implements thread creation, synchronization, and joining.

4.9.2 POSIX Threads (pthreads)

pthreads — POSIX threads — is a standard created by the IEEE. Its first part is the API for thread creation and synchronization. It is a specification, not an implementation: it tells you how to create a thread, how to create a thread library, and how to join — run threads in parallel, then join them. Real-world: most Unix-family operating systems — Solaris, Linux, and Mac OS — use pthreads. pthreads can be implemented at the user level or at the kernel level.

4.9.3 A Worked pthreads Program (Sum of Integers)

The classic example is a C program that sums the non-negative integers given on the command line:

1. Include the pthread.h header file.
2. Write a runner function; its prototype is given. The data it works on is shared among the threads.
3. Declare a thread identifier and an attribute for the thread, both of the types defined in the header — no need to manage that data by hand.
4. Get the argument from the command line. If the number of arguments is less than two, print an error and exit. The count of arguments must be two: the name of the program, and the value we supply as the data for the program.
5. Get the default attributes for the thread.
6. Create the thread. When a thread is created, an ID is given to it and the attributes are supplied; we pass the runner function, and we pass the argument — the data supplied through the command line.
7. Once the threads are created, everything runs in parallel. Later the threads are joined, and the join prints the result.

The thread's work: take the parameter supplied on the command line, convert it to an integer, and run a loop that performs the sum of the non-negative integers. When the summation is over, the thread exits and goes to the join, where the sum is displayed.

This program has two threads in total: the main thread, which is the parent, and the created thread, the child. The parent creates the child, then waits for the child to complete, then joins and exits.

4.9.4 Handling Many Threads with an Array

For 10 threads or more, use an array of threads. Each element of the array takes care of one thread, and each thread does its own work separately — the data slots W1, W2, and so on, each handled by its own thread. Later the threads are checked and joined.

4.9.5 Windows Threads

The same addition example, in Windows syntax. Include windows.h; create a variable sum with the data type DWORD, and a summation function that takes care of the adding. The syntax differs, but the multithreading structure is what matters:

1. Create the thread with CreateThread, passing the security attributes (none as of now), the stack size (nothing), the thread start function, the parameter to pass, a default flag of zero — meaning the thread is not yet started — and the identifier for the thread.
2. If the created thread is not null, it does its work; otherwise print an error and exit.
3. If the thread was created successfully, a handle is returned; the return value is checked.
4. Once the handle is valid, the child thread has been created and performs its work. Then WaitForSingleObject does the same job as pthread_join: it waits for the child to complete. It can wait for any number of threads until everything completes.
5. Close the handle, print the sum, and finish.

4.9.6 Java Threads

Java provides multithreading through an interface called Runnable. We implement this interface — in effect, we extend the thread class by implementing the Runnable interface. There is an abstract method, run(), which we implement in the summation case, because the summation performs the sum of the integers. The sum value is supplied and read with setSum and getSum. The key point: run() is never called directly. It is called with the help of the function start() — whenever start() executes, it calls run(), which executes the task. Later we get the sum of the object with getSum.

The comparison. Three libraries, one structure:

When to pick which: pthreads for Unix-family portability (Solaris, Linux, Mac OS), the Windows API for Windows-native performance, Java for cross-platform, managed-memory applications. All three implement the same conceptual structure: write the task, create the thread, run, join, read the result.

In practice, pthreads underlies nearly every Unix service (Apache, PostgreSQL, and Nginx worker models), the Windows thread API is what .NET and native Windows services build on, and Java threads power application servers such as Tomcat and WebSphere. Knowing the one shared structure — create, run, join — transfers across all of them.

4.10 Implicit Threading

4.10.1 Why Implicit Threading

As a process does more things, the number of threads grows. With explicit threads, everything is manual: create the threads, manage them, later join them. When the thread count climbs, that becomes difficult to handle. Implicit threading hands the work to the compiler and runtime instead of the programmer. Real-world: thread pools, OpenMP, and Grand Central Dispatch (GCD) are the examples; Java also supports implicit threading.

The contrast is the professor's: with explicit threads the programmer does everything manually — create the threads, manage them, later join them — which becomes difficult to handle as the thread count climbs. With implicit threading the programmer just describes what should run in parallel, and the compiler and runtime decide how many threads to create, when, and how to schedule them. The lecture's examples are thread pools, OpenMP, and Grand Central Dispatch; Java's own concurrency utilities support the same idea.

4.10.2 Thread Pools

A thread pool keeps a pool of threads ready instead of creating threads on demand. Not every thread is assigned work at the same time: the first thread is taken and assigned a task; when the next task arrives, it is assigned to the next thread, and so on, depending on how many tasks arrive. This is faster than creating a new thread for each task — the pool already exists, so picking a thread and assigning a task is easy. The number of threads in the pool varies with the application. Real-world: Windows 8 supports thread pools with pool functions — a pool function gets a thread from the pool and performs the task on it.

4.10.3 OpenMP

OpenMP is a set of compiler directives — like preprocessor directives — available in C, C++, and Fortran. It provides parallel programming by identifying parallel regions so that the code inside them runs in parallel. The identification is done with #pragma omp. Example: add the values of two arrays in parallel and store them into a third array; write it as #pragma omp parallel for. As soon as the directive line is reached, a particular thread starts and executes the work — as many threads as there are cores — and the block of code executes on each core in parallel.

#pragma omp parallel for
for (i = 0; i < n; i++) {
    C[i] = A[i] + B[i];
}

4.10.4 Grand Central Dispatch (GCD)

Grand Central Dispatch is the technology used in Mac OS and iOS. Libraries help identify the parallel sections. First we identify the blocks — in C, C++, or Objective-C a block starts with { and ends with }, and it is marked with the caret symbol ^ in front of it. Each block is placed in a queue; if a thread is available in the pool, the block is removed from the queue and assigned to that thread. There are two types of queues: a serial queue, which works in FIFO (first in, first out) order — the block that comes first is executed first, and only one block is removed and given to an available thread at a time; and a concurrent queue, which is also FIFO but can remove several blocks in parallel and work on them at once. The serial-versus-concurrent distinction is the same as the synchronized-versus-asynchronous distinction in dispatch.

4.10.5 Student Question: Thread Pool Dependencies

In practice, implicit threading is the modern default: web frameworks and database drivers submit tasks to thread pools rather than creating threads; C++'s standard parallelism, Java's executors, and Python's ThreadPoolExecutor are the same idea; and on Apple platforms GCD queues are the idiomatic way to keep the UI responsive while background work runs.

4.11 Issues in Multithreaded Programming

4.11.1 fork and exec in Multithreaded Programs

fork creates a child process. If the fork is successful it creates the child and returns zero; if it fails it returns a non-zero value, and the child gets its own separate ID. In a multithreaded program, fork raises a question: should it duplicate only the thread that called it, or all the threads present in the process? In Unix there are two versions. One duplicates all the threads — if there are 10 threads, all 10 are duplicated. The other duplicates only the thread that invoked the fork call. Then we can run exec — the exec function replaces the current program with a new program: whatever is specified as the parameter inside the exec call is what gets executed, and only that is replaced. If exec is called immediately after fork, there is no need to duplicate all the threads, because exec will throw them away and load the new program anyway; it is enough to duplicate only the thread that invoked it. But that is not right for every application — if a process forks and never calls exec, all the threads may need to be duplicated. Which version to use depends on the application.

In a single-threaded program, fork creates a child process: on success it returns zero to the child and the child's ID to the parent; on failure it returns a non-zero value. In a multithreaded program the question is what the child contains: only the calling thread, or every thread of the process? Unix answers with two fork versions, and the professor's rule picks between them:

The key fact about exec is that it replaces the current program: whatever is named in the exec call is what gets executed, and nothing else survives. So the two versions exist because the two futures of the child differ. "Which version to use depends on the application" — the professor's summary is the decision rule itself: look at what the child will do next.

4.11.2 Signal Handling

A signal is information sent to the operating system to notify it that an event has occurred. When a process is running and an interruption takes place — a hardware interrupt or a software interrupt — that event is notified with the help of a signal. The signal handler takes care of processing signals, whether the signal is generated by an event or delivered to a process. There are two handlers: a default handler, which every signal has and which runs when the signal is generated, and a user-defined handler, which can always overwrite the default handler. In a multithreaded program, the question is where the signal should be delivered: to T1, T2, T3, or T4? The options: deliver it to the thread to which the signal applies — for a hardware event, the signal goes to the corresponding thread, not to all threads; or deliver it to each and every thread; or assign a specific thread, say T1, to receive all the signals. So signal delivery is one of the threading issues to decide.

A signal is a notification — "information sent to the operating system to notify it that an event has occurred." A running process may be interrupted by a hardware interrupt or a software interrupt, and the event is announced with a signal. A signal handler is the code that processes a delivered signal, and every signal has a default handler (run by the kernel) which a user-defined handler can always overwrite. In a single-threaded process, "deliver the signal to the process" is unambiguous; in a multithreaded process the question is which thread: T1, T2, T3, or T4?

4.11.3 Thread Cancellation

A thread can be cancelled — terminated — as soon as its work is finished. The thread that is going to be cancelled is called the target thread. There are two approaches: asynchronous cancellation ends the target thread immediately; deferred cancellation checks periodically whether the thread has to be cancelled. In pthreads, cancelling a thread takes just its ID: pthread_cancel(target_thread_id). Whether the cancellation is possible depends on the state and the mode of the thread. If the mode is not present, the state is disabled, and no cancellation of any type is possible — the state has to be enabled to cancel a thread. If the state is enabled and the mode is deferred, deferred cancellation is available; deferred is also the default. A deferred cancellation takes effect at a cancellation point — for example, the function pthread_testcancel — which performs the cleanup operation so that the thread cancellation is handled. In Java, cancellation is handled through signals. If the mode is asynchronous and enabled, the thread is cancelled immediately by calling the particular function.

Thread cancellation means terminating a thread before its work is complete — for example, when several threads search a database and one finds the answer, or when the user presses Stop while a browser loads a page with one thread per image. The thread to be cancelled is the target thread. Two approaches exist, and the professor's state-and-mode framework decides which applies.

4.11.4 Thread-Local Storage (TLS)

Threads usually share the data, the code, and the files of the process. But certain threads need their own data; that is called thread-local storage (TLS). TLS is useful exactly when we do not have control over thread creation — for instance, when we are using a pool of threads, we do not create a thread for every task, so the pool's threads need a place to keep their own values. TLS lasts for the entire execution of the thread, and it stays visible across different invocations of the same function: if a local variable is set, it ceases to exist when we come out of the function, but if the same function is called multiple times by a particular thread, the TLS value remains visible across those invocations. Think of TLS as static data that is unique for each and every thread.

These four issues are everyday engineering decisions: web servers choose their fork-and-exec strategy when spawning helper processes, browsers cancel page-loading threads asynchronously when you press Stop, database connection pools keep per-connection state in thread-local storage, and signal-driven servers designate dedicated signal threads so that Ctrl+C handling never races with request processing.

4.12 Scheduler Activations: Lightweight Processes and Upcalls

4.12.1 The Lightweight Process (LWP)

The scheduler takes care of the activation of threads. In the many-to-many and two-level models, we need to maintain the number of kernel threads relative to the number of user threads. For this we have an intermediate data structure called the lightweight process (LWP). The LWP is like a virtual processor: it schedules which thread is going to run. In the two-level model we have many user threads and the same number of — or fewer — kernel threads, and we assign a user thread to a particular kernel thread with the help of this virtual processor. Each kernel thread has a lightweight process of its own, so we have to decide how many lightweight processes (virtual processors) to create: if there are four kernel threads, there will be four lightweight processes.

4.12.2 Upcalls and the Upcall Handler

Each lightweight process provides an upcall — a communication mechanism from the kernel to the thread library — and that communication is done with the help of the upcall handler. The upcall handler runs inside the lightweight process and provides an interface between the user thread and the kernel thread. If something blocks — if a user thread gets suspended or blocked because of some other activity — the next user thread is immediately assigned, through the lightweight process, to the kernel thread. Later, when the previous user thread resumes, the LWP switches back over to it, and it communicates again with the kernel thread. This is how the activation of the scheduler takes place with the help of upcalls in the many-to-many and two-level models.

In practice, this is the machinery behind Solaris's historical threading architecture (processes → user threads → LWPs → kernel threads) and the ancestor of modern user-level scheduling: Go's runtime, Java's virtual threads, and Windows user-mode scheduling all implement variants of the same idea — lightweight user-managed executions activated over a smaller number of kernel threads.

Exam Guidance Summary

• Quiz 1: Runs between February 12 and 18 through an announcement on the portal. Expect about 20 questions to answer within 25 to 30 minutes, with a weight of 5 percent. Quiz 1 covers everything up to the fifth contact session — that includes process scheduling, whose problems will be worked out in the next session. The scheduling problems in the quiz will differ from the ones solved in class, so review the notes to prepare.
• Quiz 2: Comes after the mid-semester exam.
• Assignment: It takes the form of a lab simulation, with a demo shown after the mid-semester exam, around the tenth contact session. It can be done individually or in a group, but a group may not have more than three members.
• Mid-semester: Covers the material up to process synchronization. Process synchronization is a very big topic that will take at least two sessions to cover.
• Amdahl's law (section 4.6): Expect a numerical: given a serial portion $S$ (often as a percentage) and a number of cores $N$, compute the speedup with $\text{Speedup}(N)=\frac{1}{S+\frac{1-S}{N}}$. The two-core, 25%-serial case gives 1.6. Work in four steps: convert the percentage to a decimal, compute $1-S$, divide by $N$, and take the reciprocal — and remember the limit $1/S$ as the ceiling.
• Threading models (section 4.8): Know which operating system uses which model, including Solaris's switch from two-level to one-to-one at version 9, and the Windows fiber package.
• Threading issues (section 4.11): Be ready for the two fork versions and when each applies, the signal delivery options, and the state/mode rules of thread cancellation.
• Threading basics (sections 4.1–4.5): The recurring exam-ready definitions are the thread-vs-process contrast (heavyweight vs lightweight), the shared/per-thread layout rule (code, data, files shared; registers and stack per-thread), and the parallelism-vs-concurrency distinction — all three are short-definition candidates.

Key Industry Applications

• Real-world: multithreaded web servers create a thread per client request instead of serving clients one at a time.
• Real-world: browsers and online shops run page loading, media playback, and cart operations in parallel threads.
• Real-world: Oracle SPARC T4 — 8 cores with 8 hardware threads per core; 4 cores give 32 threads. Chips with 16 cores are common, and NVIDIA and AMD ship up to 64 cores, so thread counts multiply with core counts.
• Real-world: POSIX pthreads on Solaris, Linux, and Mac OS; Windows threads; Java threads via the Runnable interface and start().
• Real-world: implicit threading in production systems — Windows 8 thread pools and pool functions, OpenMP directives in C/C++/Fortran, and Grand Central Dispatch on Mac OS and iOS with serial and concurrent queues.
• Real-world: threading models in actual operating systems — many-to-one in Solaris green threads and GNU Portable Threads; one-to-one in Windows, Linux, and Solaris 9 and later; many-to-many in older Solaris versions and the Windows thread fiber package; two-level in IRIX, HP-UX, Tru64, and Solaris 8 and earlier.
• Real-world: Amdahl's law as the industry planning tool — companies use it to decide how many cores a workload can profitably use, since the serial fraction $S$ caps the gain at $1/S$ even on today's 64-core chips.