Threads and multithreading models

Why it exists

A process bundles two things: a private address space and resources (memory, open files), and a thread of control that executes in it. Many programs want several activities at once that work on the same data: a web server serving many clients, a word processor that checks spelling while you type. Creating a process for each activity is expensive and makes sharing data awkward. A thread separates the two ideas: one process can have several threads, each with its own execution state but sharing the process's memory and resources. Threads are cheaper to create and switch and communicate through shared memory. GATE asks what is shared and private, the thread models and what blocks, and the speedup from threads.

Prerequisites

You need the process, its address space and its PCB from the process model.

Precise definitions

Thread (lightweight process). A basic unit of CPU utilisation: a thread has its own thread id, program counter, set of registers, stack and state, and shares with the other threads of its process the code, the global (static) data, the heap, the open files and other resources, and (usually) the signal handlers. A traditional process is a process with one thread.

The kernel or the thread library keeps a thread control block (TCB) per thread: the registers, the stack pointer and the state; the PCB holds the shared resources.

Benefits. Responsiveness (one thread can continue while another blocks); resource sharing (the threads share memory without the kernel's help); economy (creating and switching a thread costs much less than for a process: no new address space, and no TLB flush on a switch between the threads of one process); scalability (threads can run in parallel on several cores).

Costs. Threads share data without protection from each other, so one buggy thread can corrupt the others and updating shared data needs synchronization (critical sections). A crash in one thread usually kills the whole process.

User-level and kernel-level threads.

• User-level threads are created and scheduled by a library in user space; the kernel sees only one process. Creating and switching them needs no system call and is very fast, and the library can use its own scheduling policy. But if one thread makes a blocking system call, the whole process blocks (all its threads), and the threads cannot run in parallel on several processors, since the kernel schedules the process as one.
• Kernel-level threads are created and scheduled by the kernel, which keeps a TCB for each. A blocking call blocks only that thread, and the threads can run on different processors at the same time. Creation and switching cost more (a system call and a kernel switch), though still less than for processes.

Multithreading models (how user threads map to kernel threads):

A variant, the two-level model, allows binding a user thread to a kernel thread as well.

Thread libraries. POSIX threads (pthread_create, pthread_join), Java threads and Windows threads. pthread_create starts a new thread running a given function; pthread_join waits for it to finish.

Multicore speedup. If a fraction $f$ of the work can be done in parallel by $T$ threads on $T$ cores, the speedup is bounded by Amdahl's law, $1/((1 - f) + f/T)$ (Amdahl's law). The serial part limits it however many threads are used.

How it works

The animation shows a switch between two threads of the same process. Each thread has a TCB (rows 100 to 103 and 110 to 113); the data they share, a counter at address 300, has just one copy. Only the PC, SP and one register are saved and loaded. The page table base register keeps the same value, so neither the TLB nor the cache contents are disturbed.

Worked examples

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
 
static int shared[2];               /* global data: one copy, seen by every thread */
static void *shared_seen[2];        /* the address of `shared` as each thread sees it */
static void *local_addr[2];         /* the address of each thread's own local variable */
 
static void *worker(void *arg) {
    int id = *(int *)arg;
    int local = 10 * (id + 1);      /* lives on this thread's own stack */
    shared_seen[id] = (void *)shared;
    local_addr[id] = (void *)&local;
    shared[id] = local;
    return NULL;
}
 
int main(void) {
    pthread_t t[2];
    int ids[2] = {0, 1};
    for (int i = 0; i < 2; i++) pthread_create(&t[i], NULL, worker, &ids[i]);
    for (int i = 0; i < 2; i++) pthread_join(t[i], NULL);
    printf("global array after both threads: %d %d\n", shared[0], shared[1]);
    printf("both threads saw the same global array: %d\n", shared_seen[0] == shared_seen[1]);
    printf("their local variables are at different addresses: %d\n", local_addr[0] != local_addr[1]);
    return 0;
}

global array after both threads: 10 20
both threads saw the same global array: 1
their local variables are at different addresses: 1

Cheat box

Traps and GATE patterns

Connections

A thread is a lighter unit than the process and the cost difference appears in the context switch: no change of address space. A fork copies an address space; creating a thread does not. Threads that update shared data need critical sections, and the speedup they give is limited by the serial fraction.

PYQs

Which of the following statements about threads
is/are TRUE?

Which one or more of the following need to be
saved on a context switch from one thread (T1) of
a process to another thread (T2) of the same process
?

Consider the following multi-threaded code
segment (in a mix of C and pseudocode), invoked
by two processes P1 and P2, and each of the
processes spawns two threads T1 and T2:

int x = 0;   // global

Lock L1;    // global

main() {

create a thread to execute foo();  // Thread T1

create a thread to execute foo();  // Thread T2

wait for the two threads to finish execution;

print (x);}

foo () {

 int y = 0;

Acquire L1;

x = x + 1;

 y = y + 1;

Release L1;

print (y);}

Which of the following statement(s) is / are correct?

Threads of a process share

Which of the following is/are shared by all the threads
in a process?

I. Program counter

II. Stack

III. Address space

IV. Registers

Which one of the following is FALSE?

A thread is usually defined as a "light weight
process" because an operating system (OS)
maintains smaller data structures for a thread than
for a process. In relation to this, which of the
following is TRUE?

Consider the following statements about user level
threads and kernel level threads. Which one of the
following statements is FALSE?

Self-check

Revision card

References