Threads and Concurrency

A thread is a lightweight unit of execution within a process. Threads of the same process SHARE: code/text, data (globals), heap, and open files/signals. Each thread has PRIVATE: program counter, registers, and its own stack. Memory aid: 'Stack and Registers are Selfish; Code, Data, Heap, Files are Shared' (SR-private, CDHF-shared). Thread creation and context switching are cheaper than process creation because the address space is shared (no page-table switch, no TLB flush in many cases). Benefits: responsiveness, resource sharing, economy, scalability on multiprocessors. Risk: lack of isolation; one thread's bad pointer can corrupt the whole process.

Modern processors give you multiple cores, but only the kernel decides which thread actually runs on which core. So how user-level threads are mapped to kernel-level threads decides whether your program is truly parallel, whether one blocking I/O call freezes everything, and how heavy the per-thread cost is. GATE loves this topic because a single line of code (pthread_create) behaves very differently under each model.

Definition: A user-level thread (ULT) is a thread managed entirely by a library in user space; the kernel is unaware of it.

Definition: A kernel-level thread (KLT) is a thread the kernel itself schedules; it is the unit the OS scheduler sees.

Definition: A multithreading model is the rule that maps many user threads onto some number of kernel threads.

The three classical models

There are exactly three mapping models you must memorise: Many-to-One, One-to-One, and Many-to-Many. Each is a trade-off between speed of thread management and true concurrency / parallelism.

Many-to-One

Many user threads are mapped to one kernel thread. The thread library (in user space) does its own scheduling among the user threads, but to the kernel the whole process looks like a single schedulable entity.

The good: thread creation, context switch, and destruction are all done in user space — extremely cheap, no system call needed.

The bad: if any user thread makes a blocking system call (say, a disk read), the entire process is blocked because the kernel only sees one thread. And on a multi-core CPU, only one user thread can run at any instant — no true parallelism, ever. Classic implementations: early Solaris green threads, GNU Portable Threads.

One-to-One

Every user thread maps to its own kernel thread. Now the kernel sees and schedules every thread independently, so blocking one does not block others, and the OS can place different threads on different cores for genuine parallelism.

The cost: every thread creation requires a system call and a kernel data structure, which is much heavier. There is also usually a system-imposed cap on the number of kernel threads per process.

This is the model used by Linux (NPTL) and Windows. So when you write pthread_create on a typical Linux machine today, you are using a One-to-One implementation.

Many-to-Many

m user threads multiplex onto n kernel threads, with n typically less than or equal to m and tuneable. The library can keep many lightweight user threads while ensuring there are always some kernel threads available so that a blocked thread does not stall the others.

This combines the flexibility of user threads with the parallelism of kernel threads. It is conceptually elegant but harder to implement, which is why most mainstream OSes have moved to One-to-One. A close variant is the two-level model, where most user threads are many-to-many but a few are "bound" to a dedicated kernel thread.

Why thread libraries are not models

Definition: A thread library is the API a programmer uses to create and manage threads.

The three libraries you should know are POSIX Pthreads, Windows threads, and Java threads. A library is a specification; the model it uses depends on the implementation. POSIX Pthreads on Linux is One-to-One; an older Pthreads implementation on a different OS could have been Many-to-One. Java threads on the JVM usually delegate to the underlying OS, so on Linux/Windows they too are One-to-One.

Why it matters: an exam question that says "POSIX Pthreads is which model?" is a trap — the correct answer is that Pthreads is a specification, not a model. The model depends on the implementation.

Real-world example

Consider a typical Indian web service like an IRCTC ticket booking backend running on Linux. When a request arrives, a worker thread (a Pthread, which on Linux is a One-to-One kernel thread) does a database call. The thread blocks on I/O — but because the model is One-to-One, the other worker threads continue serving other passengers on other cores. If IRCTC were running on Many-to-One, every passenger's request would queue behind whichever one was waiting on the database. That is why production servers have used kernel threads for two decades.

Common misconception

A very common error is to say "user-level threads are always faster." They are faster to create and switch, but if any one of them blocks on I/O, the entire process stalls — making throughput much worse. So user-level threads are fast only for CPU-bound, cooperative workloads where blocking is rare. For real workloads with disk and network I/O, kernel-level threads win.

Another misconception: students think Many-to-Many is the most popular model. In practice, the simpler One-to-One model won because modern OS schedulers and stacks are cheap enough that the overhead is acceptable.

Worked example

Question: A program has 4 user-level threads under a Many-to-One model on a quad-core machine. One thread issues a blocking read() system call. What happens to the other three threads?
Solution:
Step 1: Recall that under Many-to-One the kernel sees only one schedulable entity for the entire process.
Step 2: The blocking system call traps to the kernel. The kernel marks the (single) kernel thread as blocked.
Step 3: With the only kernel thread blocked, no user thread of this process can be scheduled — the library has nothing to switch to from the kernel's perspective.
Conclusion: All four user threads are effectively blocked, even though three of them have no reason to wait. This is the canonical "Many-to-One blocks all" failure.

fork() creates a child process duplicating the parent's address space (copy-on-write). It returns the child PID to the parent and 0 to the child. Counting trick: n consecutive fork() calls create 2^n - 1 child processes (total 2^n processes including the original). Example: code with three fork() calls in sequence yields 2^3 = 8 total processes, hence 7 children. With branching/conditionals, draw the process tree. After fork(), parent and child have separate copies of variables; changes in one do not affect the other. exec() replaces the process image; wait() lets a parent block until a child terminates, reaping zombies.

Cover the answer, recall, then check. 11 cards on threads and concurrency for GATE OS.

Q1. What do threads of the same process share, and what is private per thread?
A1. Shared: code (text), data/heap, open files and signals. Private per thread: program counter, register set, and its own stack. This is why thread creation is cheaper than process creation.

Q2. User-level vs kernel-level threads — key difference?
A2. User threads are managed by a user library, invisible to the kernel (fast switching, but one blocking call blocks the whole process). Kernel threads are scheduled by the OS (a block affects only that thread, but switching is costlier).

Q3. In the many-to-one threading model, what happens if one thread makes a blocking system call?
A3. The entire process blocks, because the kernel sees only one schedulable entity. Also, no true parallelism on multicore.

Q4. What is the advantage of the one-to-one model over many-to-one?
A4. Each user thread maps to a kernel thread, so threads can run in parallel on multiple CPUs and one blocking call doesn't block the others. Cost: more kernel threads to manage.

Q5. Why are context switches cheaper between threads than between processes?
A5. Threads of one process share the address space, so the memory map / page tables (and TLB, in the same address space) need not change — only registers, PC and stack pointer are switched.

Q6. Concurrency vs parallelism — the distinction?
A6. Concurrency: multiple tasks make progress in overlapping time (possible on one core via interleaving). Parallelism: tasks literally execute at the same instant (requires multiple cores).

Q7. What is a thread pool and why use one?
A7. A set of pre-created worker threads that pick up tasks from a queue. It avoids per-task thread-creation cost and bounds the number of concurrent threads.

Q8. Does creating more threads always speed up a program?
A8. No. Beyond the available cores and past the parallelisable fraction (Amdahl's law), extra threads add scheduling and synchronization overhead without speedup.

Q9. What is the primary correctness challenge introduced by threads sharing memory?
A9. Race conditions on shared data — requiring synchronization (locks, semaphores). This is the cost of the cheap sharing that makes threads attractive.

Q10. How does a multithreaded process behave on fork()?
A10. Some systems duplicate only the calling thread, others all threads — hence exec() is usually called right after fork() in multithreaded programs to avoid ambiguity.

Q11. Where is the Thread Control Block (TCB) relative to the PCB?
A11. Each thread has a TCB (its PC, registers, stack pointer, state); all TCBs of a process are associated with the single shared PCB holding process-wide resources.