Threads & Multithreaded Servers

Middleware and the Operating System

A distributed application runs on many computers at once, and each of those computers may run a different operating system on different hardware. Two layers of software support it. The operating system (OS) on each node looks after that one machine, and middleware spans all the nodes and hides their differences. Knowing which layer does what is the starting point for this Part, because threads are one of the things the OS provides and middleware relies on.

This Part draws on CDK chapter 7 (§7.1, §7.2 and §7.4), lecture L3 and Buyya's chapter on Java threads. The OS layer itself, protection and kernel architectures are covered in Part V. The material matters twice over, because Java threads, locking and threaded socket servers are also the core of Assignment 1, the multi-threaded Subject Enrolment Server.

What each layer does exam

Middleware's services fall into four groups: communication (remote procedure call and remote method invocation, usually shortened to RPC and RMI, plus events and group communication), management, application-specific services, and a runtime environment in which the application runs. RPC and RMI let a program call a procedure or method that lives in another process as if it were local; Part VI covers them in detail.

The OS, by contrast, provides the low- to medium-level core features of one machine:

• process and thread management (creating them, scheduling them on the CPU);
• management of the local hardware: the CPU (central processing unit, the chip that executes instructions), memory and disk;
• security: users, groups and ACLs (access control lists, which say who may use which resource);
• basic networking.

With these features the OS lets a server encapsulate and protect its resources, so that other programs can reach them only through the server's interface, and it provides the mechanisms to access them, including communication and concurrent processing (doing several things at the same time). Middleware then builds remote invocation on top of these local facilities. The diagram below shows the arrangement.

Network OS vs distributed OS exam

An OS can treat a networked collection of machines in one of two ways. A network OS (NOS) leaves each node in charge of itself: every machine runs its own OS, and the user decides where programs run. A distributed OS (DOS) tries to make the whole network look like a single machine, called a single system image, and places processes on nodes by itself. A process here simply means a running program; section 4.2 defines it properly.

Notice the last row: no distributed OS is in general use. CDK (§7.1) gives two reasons why the combination of middleware and network OS won instead.

1. Investment in applications. Users will not adopt an OS that cannot run the applications they already have. One workaround is to emulate existing OSs on new kernels, but such emulation performed poorly, and keeping emulations up to date is a huge job.
2. Autonomy. Users want control over their own machines and predictable performance on them. In CDK's example, Jones does not want Smith's jobs, placed on her machine by a distributed OS, slowing down her editor.

So the two layers divide the work. The network OS provides autonomy and runs standalone applications; middleware adds network-transparent access to distributed services on top of it. Neither a DOS nor a NOS alone is enough: middleware is the "glue" that sits on top of the NOS.

Core OS components exam

Inside one node, CDK's Figure 7.2 divides the core of the OS into five components, each with its own responsibility. Two of them, the process manager and the thread manager, are what the rest of this Part relies on.

Processes and Threads

Before turning to Java, it is worth getting the vocabulary straight. A server wants to do many things at once, and the OS offers two units of concurrency to do it with: processes and threads. They differ in what they share, and that one difference decides how expensive they are and how much they protect you from mistakes.

Multitasking vs multithreading

Both terms describe doing several things at once, but at different levels. Multitasking happens at the OS level and is process-based: several applications run concurrently and the CPU switches between them. It comes in two forms. In cooperative multitasking each application voluntarily gives up the CPU (it yields); in preemptive multitasking a hardware timer ends each timeslice (the short period a task is allowed to run) and the OS performs the switch, whether the task likes it or not.

Multithreading happens at the application level and is thread-based: several activities run concurrently within one process. A word processor, for example, can edit, render its window and print in the background at the same time.

Processes, execution environments and threads exam

A semaphore is an OS counter that threads use to wait for and signal each other, and a socket is an endpoint for network communication (Part III). The program counter is the register that holds the address of the next instruction, and the stack is the memory where a thread keeps the local variables and return addresses of the methods it is currently executing. The figure shows what is shared and what is private.

A context switch is the act of saving one thread's processor registers and loading another's, so that the CPU continues with the other thread. Sometimes it also involves a domain transition, a change of address space and/or of processor mode (between the restricted user mode and the privileged kernel mode in which the OS runs). As the next pictures show, that extra step is what makes some switches expensive.

Process vs thread exam

Setting the two side by side shows the trade-off: threads are much cheaper to create and to switch between, but they give up protection from one another.

CDK sums up the comparison in four points, which are worth quoting as they stand in an exam answer:

1. Creating a thread is cheaper than creating a process.
2. More importantly, switching between threads of the same process is cheaper than switching between processes.
3. Threads share data and resources conveniently and efficiently.
4. By the same token, threads are not protected from one another.

Why a process switch costs more: the aliasing problem

Programs use virtual addresses, which the MMU translates to physical addresses in RAM. To make that fast, the CPU keeps a TLB (translation lookaside buffer), a small cache of recent translations, and often a cache of memory contents indexed by virtual address. The trouble is aliasing: the same virtual address means different data in different address spaces. So when the CPU switches to another address space, any untagged TLB entries and virtually addressed cache lines are now wrong and must be flushed. The new process then suffers cache misses and page faults while they refill.

Address spaces and creating a process (brief)

CDK §7.4.1–7.4.2 covers these only briefly. An address space is a set of non-overlapping regions, such as the program text (its code), the heap, one stack per thread, and mapped files. Each region has an extent (start and size), permissions (read, write, execute) and a direction in which it can grow. Shared regions are used for libraries, for the kernel (which is mapped into every process) and for sharing data between processes.

Creating a process in a distributed system has two parts. The first is choosing a host: a transfer policy decides whether to create the process locally or remotely, and a location policy decides which node it goes to. The second is creating the execution environment. The UNIX fork call, for example, creates a child process whose environment is a copy of its parent's. Copying everything up front would be slow and often wasted, so copy-on-write is used: the inherited regions share the same page frames (fixed-size blocks of physical memory), which are write-protected, and a page is physically copied only when one of the processes writes to it. Step through it below.

What threads are used for

Threads are used in six common situations. The first is easiest to picture: several independent calculations run side by side and the main thread waits for all of them with join(), which blocks until a thread finishes.

Creating Java Threads

With the concepts in place, we turn to how Java exposes threads. Every Java program already has one thread, the one that runs main. To do two things at once you create more, and Java gives you two ways to say what a new thread should run. In both cases the code the thread executes goes in a method called run(), and in both cases nothing happens until you call start().

Two ways to create a thread exam

In the first way you extend Thread and override run(), so the object itself is a thread. In the second you implement Runnable, an interface with the single method run(), so the object is only a task, and a separate Thread object runs it. The example shows both.

// Way 1: extend Thread and override run(). The object IS a thread.
class A extends Thread {
    public void run() {
        for (int i = 1; i <= 5; i++) System.out.println("\t From ThreadA: i= " + i);
        System.out.println("Exit from A");
    }
}

// Way 2: implement Runnable. The object is a task that a Thread runs.
class Task implements Runnable {
    public void run() { System.out.println("in " + Thread.currentThread().getName()); }
}

public class ThreadEx {
    public static void main(String[] args) throws InterruptedException {
        A a = new A();                         // NEW: no thread running yet
        Thread t = new Thread(new Task());     // wrap the Runnable
        a.start();                             // JVM creates a thread that calls run()
        t.start();
        a.join(); t.join();                    // main waits for both to terminate
    }
}

Reading it line by line:

• class A extends Thread with its own run(): the body is what the new thread will execute, here a loop printing five lines and then "Exit from A".
• class Task implements Runnable: its run() prints the name of whichever thread is executing it, found with the static method Thread.currentThread().
• A a = new A(); creates a Thread object in the New state. It is just an object; no thread is running yet.
• new Thread(new Task()) wraps the task in a Thread object, which will call the task's run() when started.
• a.start() asks the JVM (the Java Virtual Machine, the runtime that executes Java programs) to create a real thread, which will later call a.run(). start() returns immediately, so main carries straight on to t.start().
• a.join(); t.join(); make main wait until each thread has terminated. join() can throw InterruptedException (if another thread interrupts the waiting one), which is why main declares throws InterruptedException.

The two approaches differ in what the object is and in what they cost you in inheritance. Java allows a class to extend only one superclass, so extending Thread uses up that one chance. Runnable is usually the better choice.

A lambda is Java's short syntax for an object with one method, so new Thread(() -> work()) is the same as passing a Runnable whose run() calls work(). A thread pool (section 4.8) is a fixed set of threads that run many submitted Runnable tasks, which is one reason the task-only style is so useful.

start() vs run() exam

This is the classic trap. Calling start() creates a new thread, which the scheduler later dispatches to execute run(); start() itself returns immediately. Calling run() directly is just an ordinary method call in the current thread, so nothing runs concurrently.

A thread can also be started only once. Calling start() a second time throws IllegalThreadStateException, and a thread that has finished (is dead) cannot be restarted; you must create a new Thread object.

Thread Life Cycle, Control and Scheduling

Once a thread exists, you need to know what it is doing at any moment: is it running, waiting for its turn, asleep, or finished? The answer is its state, and the methods you call on a thread are mostly ways of moving it between states. This section draws the life cycle, lists the control methods (and the dangerous ones you must not use), and explains why you can never predict the order in which threads run.

The thread life cycle exam

The slides model a thread's life as seven states, with the method calls and events that move it from one to another. Read the diagram from the black dot (the start) to the ringed dot (the end).

In words: a thread starts New (the object exists, no thread yet). start() makes it Ready (able to run, waiting for a CPU). The scheduler dispatches it, making it Running; yield() or the end of its timeslice sends it back to Ready. From Running it can go Sleeping (sleep(ms)), Waiting (wait(), until notified) or Blocked (waiting for I/O, or suspended). When run() finishes (or, in old code, on stop()) it is Dead.

Java's own Thread.State enum uses different names, and the exam may use either set:

Sleeping, waiting and blocked threads are all still alive (isAlive() returns true). When they wake, they return to Ready, not straight to Running.

Thread methods exam

These are the main methods for controlling a thread. "Static" means you call it on the class, Thread.sleep(100), and it acts on whichever thread is executing the call.

Why stop, suspend and resume are deprecated exam

The reason comes down to locks, which section 4.5 introduces properly; for now, a lock is a token that only one thread can hold at a time, used to stop other threads touching an object while it is being changed.

stop() kills a thread at an arbitrary point and releases all its locks, so any objects it was halfway through updating are left inconsistent and visible to other threads. suspend() has the opposite problem: it freezes a thread while it still holds its locks, so if the thread that would call resume() needs one of those locks, the result is deadlock (threads waiting for each other for ever; section 4.7). resume() exists only to pair with suspend(), so it goes too.

class Worker extends Thread {
    private volatile boolean running = true;   // volatile: other threads see changes at once
    public void shutdown() { running = false; interrupt(); }
    public void run() {
        while (running) { /* do one unit of work, then re-check the flag */ }
    }
}

The sketch above is one way to code the flag; the keyword volatile makes every thread read the field's latest value rather than a cached copy. CDK also describes thread groups: every thread belongs to a group, and groups serve two purposes. One is security, since a thread cannot manage threads in another group. The other is priority control, since a group's maximum priority caps the priorities of its members; this is used for applets and servlets (small programs hosted inside a browser or a web server).

Start order is not run order exam

This example shows why you cannot predict the order in which threads run. main starts three threads, each of which prints five lines and then "Exit from X".

// class A is as in section 4.3; B and C are identical but print "ThreadB" / "ThreadC"
public class ThreadTest {
    public static void main(String[] args) {
        new A().start();
        new B().start();
        new C().start();
    }
}

The output varies because start() only makes a thread Ready. When the thread actually runs, and when it is preempted (taken off the CPU), is up to the JVM/OS scheduler. That timing depends on timeslices, the other load on the machine, JIT compilation and garbage collection activity (both done by the JVM in the background), and the number of cores, so it changes from run to run.

Priorities and scheduling

Java lets you influence the scheduler through priorities. The constants are MIN_PRIORITY = 1, NORM_PRIORITY = 5 and MAX_PRIORITY = 10. NORM_PRIORITY is the default, and a new thread inherits its priority from the thread that created it. According to the slides, equal-priority threads are served first-come-first-served and higher priority runs first. Both the slides and Buyya describe the garbage collector (the JVM's background memory recycler) as a low-priority thread.

A threadA = new A();  B threadB = new B();  C threadC = new C();
threadC.setPriority(Thread.MAX_PRIORITY);           // 10
threadB.setPriority(threadA.getPriority() + 1);     // A is still NORM (5), so B gets 6
threadA.setPriority(Thread.MIN_PRIORITY);           // 1
threadA.start(); threadB.start(); threadC.start();  // typical output: C first, A last

In the slides' priority example above, a typical output runs C first and A last. But priorities are only hints to the OS scheduler, so use them to favour work, never for correctness. A server, for example, can give a class of premium customers higher-priority threads.

Preemptive vs non-preemptive scheduling exam

CDK distinguishes two ways a thread scheduler can behave, and the difference decides whether you need synchronisation at all.

Race Conditions and synchronized

Threads share their process's data, and a preemptive scheduler can switch between them at any instruction. Put those two facts together and two threads can trip over each other while updating the same field. This section shows exactly how that goes wrong, step by step, and then how Java's synchronized keyword prevents it.

The problem: a race condition exam

Access to a shared resource must be coordinated. A printer cannot print two jobs at once, and the calls deposit(), withdraw() and enquire() on one bank account must not interleave. When accesses do interleave, the result can be a race condition: the outcome depends on the unpredictable interleaving of the threads that access the shared data.

The key insight is that balance += amt looks like one step but is really three: read the field into a register, add, and write the result back. A thread can be preempted between any two of them. In the stepper, the account starts with 100; thread 1 deposits 30 while thread 2 withdraws 50, so the right answer is 80.

The same thing happens on the server side. CDK's example is an I/O thread and several worker threads manipulating a shared queue of requests: without coordination, requests can be lost or handed to two workers.

To work out what is shared, use the picture from section 4.2: local variables live on each thread's private stack, whereas instance and static fields live in shared objects and are shared. In the example, r is private and balance is shared.

The course example is Internet banking, where deposit and withdraw threads share one Account. With synchronized methods the balances are consistent. Without it, Buyya's run printed "balance is 60.0" after every operation, which is plainly a wrong result.

The fix: synchronized, monitors and intrinsic locks exam

Java's basic tool for mutual exclusion is the keyword synchronized. Every Java object has an intrinsic lock (also called its monitor lock), and synchronized uses it to implement the monitor construct: at most one thread executes inside an object's synchronized code at a time. Any other thread that tries to enter is BLOCKED until the lock is free.

There are two forms. A synchronized method locks this, the object it is called on; a static synchronized method locks the Class object instead (one per class). A synchronized block, written synchronized (obj) { … }, locks a chosen object around a smaller critical section.

class Account {
    private double balance;
    public synchronized void deposit(double amt) { balance += amt; }   // locks this

    public void withdraw(double amt) {
        // ... work that needs no lock can go here ...
        synchronized (this) { balance -= amt; }                       // block: locks this, briefly
    }
    public static synchronized void audit() { /* locks Account.class */ }
}

Two properties make these locks easy to use. They are reentrant: the thread holding the lock can call other synchronized methods on the same object without blocking on itself. And the lock is released automatically when the method or block exits, even if it exits by throwing an exception.

The example below puts this together. Two threads increment one shared Counter 100,000 times each; synchronising increment() makes its read-modify-write atomic (indivisible), so no update can be lost.

class Counter {                                       // the "monitor"
    private int count = 0;
    public synchronized void increment() { count++; } // read-modify-write is now atomic
    public synchronized int get() { return count; }
}

public class RaceDemo {
    public static void main(String[] args) throws InterruptedException {
        Counter c = new Counter();
        Runnable task = () -> { for (int i = 0; i < 100_000; i++) c.increment(); };
        Thread t1 = new Thread(task), t2 = new Thread(task);   // both share ONE Counter
        t1.start(); t2.start();
        t1.join();  t2.join();
        System.out.println(c.get());   // always 200000; without synchronized, usually less
    }
}

• count++ is read-modify-write, exactly like balance += amt, so without the lock two threads can lose increments.
• The lambda task is a Runnable; both threads run the same task on the same Counter c, which is what makes count shared.
• get() is synchronized too, so it reads a consistent value.
• join() makes main wait for both threads before printing. Remove synchronized and the total is usually less than 200,000.

Here is the same deposit/withdraw race again, this time with both methods synchronized.

Locks belong to objects

A synchronized instance method locks its own object. Two threads calling the same synchronized method on different objects do not block each other at all, because they take different locks.

wait, notify and Producer–Consumer

Mutual exclusion stops two threads changing data at the same time, but it is not enough when a thread must wait for a condition, such as "the queue is non-empty". A consumer that finds an empty queue cannot just loop and check again while holding the lock, because then no producer could ever get in to add an item. It needs a way to sleep, give up the lock, and be woken when things change. In Java, any object can play that role, acting as a condition variable.

How wait and notify work exam

1. A thread calls wait() on an object while holding that object's lock (inside synchronized code).
2. wait() releases the lock and blocks the thread in the object's wait set until it is notified, interrupted or (with wait(ms)) timed out.
3. Another thread, holding the same lock, calls notify() to wake one waiting thread, or notifyAll() to wake all of them. Woken threads then compete for the lock.
4. The woken thread reacquires the lock before wait() returns, and carries on inside the synchronized code.

Calling wait, notify or notifyAll without holding the object's lock throws IllegalMonitorStateException. Look back at the monitor figure in section 4.5: wait() moves the owner into the wait set, and notification moves a waiter back to the entry set.

CDK also notes that a Java monitor has only one implicit condition variable per object. Producers waiting for "not full" and consumers waiting for "not empty" therefore sit in the same wait set, and notify() might wake a thread of the wrong kind. That is why notifyAll() is used when producers and consumers wait on the same object.

The producer–consumer (bounded-buffer) problem

The classic use of these methods is the producer–consumer problem. Producers add items to a fixed-size buffer and consumers remove them. A producer must wait while the buffer is full, and a consumer must wait while it is empty. Buyya's version is a MessageQueue with three producers and three consumers. CDK's worker-pool server (section 4.8) uses the same pattern: worker threads wait on an empty request queue, and the I/O thread notifies them when it adds a request.

import java.util.LinkedList;
import java.util.Queue;

class BoundedBuffer {
    private final Queue<String> items = new LinkedList<>();
    private final int capacity;
    BoundedBuffer(int capacity) { this.capacity = capacity; }

    public synchronized void put(String msg) throws InterruptedException {
        while (items.size() == capacity) wait();   // full: release lock until a consumer takes
        items.add(msg);
        notifyAll();                               // wake consumers waiting on "empty"
    }

    public synchronized String take() throws InterruptedException {
        while (items.isEmpty()) wait();            // empty: release lock until a producer puts
        String msg = items.remove();
        notifyAll();                               // wake producers waiting on "full"
        return msg;
    }
}
// Usage: new Thread(() -> { ... buf.put("MSG#" + i) ... }).start();   // producer
//        new Thread(() -> { ... buf.take() ... }).start();             // consumer

• items is the shared queue and capacity its fixed size. Both methods are synchronized, so the buffer object is the monitor and only one thread at a time touches items.
• put: while the buffer is full, wait() releases the lock so a consumer can get in and take something. Once there is room it adds the message and calls notifyAll() to wake any consumer waiting for "not empty".
• take is the mirror image: wait while empty, remove an item, notifyAll() to wake any producer waiting for "not full", and return the item.
• Both methods declare throws InterruptedException because wait() can be interrupted.
• The usage lines show producer and consumer threads written as lambdas sharing one buf.

The stepper runs this buffer with one producer and two consumers, and shows why the while loop matters.

sleep vs wait exam

These two are easy to confuse because both make a thread stop for a while. The difference is all about the lock.

Read–Write Locks, Granularity and Deadlock

Plain synchronized is correct but blunt. Assignment 1, the multi-threaded Subject Enrolment Server, raises three issues that go beyond it: letting readers share access, deciding how many locks to use, and making a check and its update atomic. Using several locks then brings a new danger, deadlock. This section covers all four, ending with the code that solves them together.

Readers and writers exam

Many readers can safely run together, because reading does not change anything; only a writer needs exclusive access. But synchronized lets in one thread at a time, so it serialises readers needlessly. This is the readers–writers problem. The class java.util.concurrent.locks.ReentrantReadWriteLock solves it: it allows either many holders of the read lock or one holder of the write lock, never both.

Lock granularity exam

Granularity means how much data each lock protects. A single global lock over the whole server is simple and cannot deadlock, but every operation is serialised, so operations on different subjects block one another. One lock per resource (per subject, or per bank account) lets independent operations run in parallel.

In general, finer granularity gives more concurrency, but it means more locks to manage and brings a deadlock risk whenever one operation needs several locks, such as a transfer between two subjects.

The check-then-act race exam

Consider if (enrolled < capacity) enrolled++;. It looks safe because it checks first. But with one seat left, two threads can both pass the check before either increments, and both enrol, oversubscribing the subject. The check and the update must therefore happen inside one critical section, under the write lock.

Putting it together: the EnrolmentService

The code below applies all three ideas, with one read–write lock per subject. query takes the read lock, enrol does its check and update under the write lock, and transfer takes two write locks in a fixed global order, which is the deadlock fix explained next.

import java.util.concurrent.locks.ReentrantReadWriteLock;

class Subject {
    final String code; final int capacity; int enrolled;
    final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();   // one lock PER subject
    Subject(String code, int capacity) { this.code = code; this.capacity = capacity; }
}

class EnrolmentService {
    int query(Subject s) {
        s.rw.readLock().lock();                 // shared: concurrent queries allowed
        try { return s.enrolled; }
        finally { s.rw.readLock().unlock(); }   // always released, even on exception
    }

    boolean enrol(Subject s) {
        s.rw.writeLock().lock();                // exclusive: no readers or writers
        try {
            if (s.enrolled >= s.capacity) return false;   // check ...
            s.enrolled++;                                  // ... and act atomically
            return true;
        } finally { s.rw.writeLock().unlock(); }
    }

    boolean transfer(Subject from, Subject to) {
        // Global lock order (ascending code), whatever the transfer direction
        Subject first  = from.code.compareTo(to.code) < 0 ? from : to;
        Subject second = (first == from) ? to : from;
        first.rw.writeLock().lock();
        try {
            second.rw.writeLock().lock();
            try {
                if (to.enrolled >= to.capacity) return false;
                from.enrolled--; to.enrolled++;
                return true;
            } finally { second.rw.writeLock().unlock(); }
        } finally { first.rw.writeLock().unlock(); }
    }
}

• Subject holds the data plus its own ReentrantReadWriteLock rw: fine granularity, one lock per subject.
• query only reads, so it takes the read lock; many queries on one subject can run at once. The return inside try still runs the finally, so the lock is always released.
• enrol takes the write lock and does both the capacity check and the increment inside it, which closes the check-then-act race. Returning false early is safe because finally still unlocks.
• transfer needs two subjects. It works out which code is smaller with compareTo and always locks that subject first, regardless of which is the source. Two nested try/finally blocks release the two locks in reverse order.

Deadlock exam

Deadlock occurs when each thread in a set waits for ever for a lock held by another thread in the set. Suppose client 1 runs TRANSFER(X→Y) and client 2, at the same time, runs TRANSFER(Y→X), and each locks in request order, source then destination. Step through it.

Coffman identified four necessary conditions for deadlock. All four must hold at once for a deadlock to happen, so you can avoid deadlock by breaking any one of them.

Two more habits help: hold locks only briefly, and never block on I/O or call remote code while holding a lock. And avoid suspend(), which freezes a thread while it still holds its locks (section 4.4).

Two related liveness problems are worth naming. In starvation, a thread never gets the lock because others keep getting it first. In livelock, threads keep reacting to each other (for example, both backing off and retrying in step) without making progress, so they are not blocked but get nowhere.

Multithreaded Server Architectures

A server's job is to answer as many requests as possible, as quickly as possible. A single-threaded server handles one request at a time: while it waits for the disk, the CPU sits idle and every new request waits in the queue at the server's port. Threads fix that, and there are four standard ways to organise them. This section explains why threads help, measures how much, and then compares the four designs, which is one of the most examined topics in the subject.

Why multithread a server? exam

Multithreading lets a server maximise throughput, measured as requests processed per second, in two ways: by overlapping computation with I/O (one thread computes while another waits for the disk), and by using multiple processors. It also lets the server give requests different priorities. A single-threaded server, by contrast, makes every new request wait in the port queue until the current one finishes.

Worked example: how much faster? (CDK §7.4.3) exam

CDK's worked example puts numbers on it. Each request needs 2 ms of CPU plus 8 ms of disk I/O, and there is one disk, so disk accesses happen one at a time. First compare one thread with two on a single CPU.

Every row of CDK's table follows the same three-step method:

1. For each resource, work out its capacity as 1000 ÷ (ms of that resource per request), in requests per second.
2. With overlap (several threads), throughput is the minimum of these capacities, because the bottleneck resource sets the pace.
3. With a single thread nothing overlaps, so add the times instead: throughput = 1000 ÷ (total ms per request).

Now add one improvement at a time and watch which resource becomes the bottleneck. A cache here is a copy of recently used disk data kept in memory; a 75% hit rate means three requests in four find their data there and skip the disk.

The four architectures exam

CDK, following Schmidt, describes four ways to organise a server's threads (CDK Figs 7.5–7.6). They differ in when threads are created, where requests queue, and what has to be synchronised, so those are the three points to cover whenever you compare them. Each tab draws its architecture in the same frame, so you can flip between them: clients on the left, the server process in the dashed box, remote objects (the server's shared data) on the right. The amber thread is the I/O thread, which receives requests; green threads are workers, which process them.

Which creates how many threads? exam

Exam multiple-choice questions like to ask how many threads each architecture creates. The answer always follows from the name: what is a thread created per? Here is one illustrative scenario counted four ways.

Java: a thread-per-connection server

In Java, a thread-per-connection server takes only a few lines. The main thread listens on a TCP port and loops, accepting each connection and starting a new thread for it. Each handler thread then reads and answers its client's requests in order until the client closes the connection. TCP (Transmission Control Protocol) gives a reliable, ordered byte stream between two sockets (Part III); a ServerSocket waits for clients to connect, and accept() returns a new Socket for each one.

import java.io.*;
import java.net.*;

public class ThreadPerConnectionServer {
    public static void main(String[] args) throws IOException {
        try (ServerSocket listener = new ServerSocket(4444)) {     // 1. listen on a TCP port
            while (true) {
                Socket client = listener.accept();                 // 2. wait for a connection
                new Thread(new ConnectionHandler(client)).start(); // 3. one thread per connection
            }
        }
    }
}

class ConnectionHandler implements Runnable {
    private final Socket socket;
    ConnectionHandler(Socket socket) { this.socket = socket; }

    public void run() {
        try (Socket s = socket;
             BufferedReader in = new BufferedReader(new InputStreamReader(s.getInputStream(), "UTF-8"));
             PrintWriter out = new PrintWriter(new OutputStreamWriter(s.getOutputStream(), "UTF-8"), true)) {
            String request;
            while ((request = in.readLine()) != null) {   // 4. many requests, handled in order
                out.println("ECHO " + request);            // 5. process (lock shared state!) and reply
            }
        } catch (IOException e) {
            System.err.println("Client error: " + e.getMessage());
        }                                                  // 6. client closed: thread ends
    }
}

1. new ServerSocket(4444) listens on TCP port 4444. The try (…) form ("try-with-resources") closes it automatically at the end.
2. listener.accept() blocks until a client connects, then returns a Socket for that one connection.
3. The main thread wraps the socket in a ConnectionHandler (a Runnable) and starts a new thread for it, then loops straight back to accept() for the next client. This is the "per connection" moment.
4. In the handler's run(), the streams are wrapped for text: BufferedReader reads lines, PrintWriter with true flushes after each println. readLine() returns each request in order, and returns null when the client closes the connection.
5. Each request is processed and answered (here, just echoed). In a real server, any shared state touched here must be locked, because other handler threads run the same code at the same time.
6. When the loop ends, try-with-resources closes the socket and streams, run() returns, and the thread dies.

Buyya also calls socket.setSoTimeout(...), so that an idle client cannot hold a thread for ever: a read that waits longer than the timeout throws an exception and the handler can close the connection.

Thread pools with ExecutorService

For a practical worker pool, Java provides ExecutorService. Create ExecutorService pool = Executors.newFixedThreadPool(8);, replace step 3 with pool.execute(new ConnectionHandler(client));, and call pool.shutdown() at exit. The executor's internal queue and threads correspond to CDK's request queue and workers. There are variations: newCachedThreadPool() creates threads on demand and reuses idle ones, and submit() returns a Future, an object through which you can later collect the task's result.

ExecutorService pool = Executors.newFixedThreadPool(8);
// ... inside the accept loop, instead of new Thread(...).start():
pool.execute(new ConnectionHandler(client));
// ... at exit:
pool.shutdown();

Java 21 virtual threads (Executors.newVirtualThreadPerTaskExecutor()) are cheap user-level threads, which makes thread-per-request affordable (compare section 4.10).

Threads in Clients; Threads vs Processes

Threads help clients as well as servers. A remote invocation (a call to a method on another machine) normally blocks the caller until the reply arrives, which can take many milliseconds. A client that has other useful work to do should not sit idle for that long.

A two-thread client

CDK (Fig. 7.5) gives the client two threads. Thread 1 computes results and puts them into buffers; Thread 2 takes them out and performs the blocking remote invocations. Thread 1 then blocks only when the buffers are full. It is the producer–consumer pattern of section 4.6, used inside a client.

Web browsers use the same idea, fetching several pages or images concurrently to hide latency (the delay before a reply starts to arrive). Part V covers concurrent invocations further.

Threads vs multiple processes exam

Several single-threaded processes could also overlap computation and I/O, so why use threads? Threads are preferred for two reasons:

1. They are cheaper to create and manage (section 4.2).
2. They share resources more efficiently, because they live in one execution environment. For example, threads of one server can share one file cache in memory, which separate processes could not do directly.

If components need protection from one another, though, use processes, or a type-safe language (one, like Java, that stops code from accessing memory it should not).

Kernel-Level vs User-Level Threads

Who actually implements threads? Either the OS kernel does, or a library running inside the process does, and the kernel never knows. The choice affects how cheap threads are, how flexibly they can be scheduled, and, crucially, what happens when one thread blocks.

The strengths of one are largely the weaknesses of the other. A trap here means switching into the kernel via a system call, which costs time; a page fault happens when a thread touches memory that is not currently in RAM, so the kernel must fetch it, blocking the caller.

Hybrid schemes

Hybrid schemes try to combine the two. In Mach, user-level code gives scheduling hints to the kernel. In Solaris 2, a user-level scheduler maps user threads onto kernel threads, called lightweight processes (LWPs). This uses multiprocessors and switches cheaply, but if a kernel thread blocks, all the user threads assigned to it are stuck.

Scheduler activations

Scheduler activations, from Anderson et al., go further. The insight is that a user-level scheduler needs more than kernel threads to map onto: the kernel must also tell it about scheduling events, such as one of its threads blocking. The labour is divided like this: the kernel allocates virtual processors (VPs) to each process, and their number can change over time; the process's user-level scheduler assigns its READY threads to them. A scheduler activation (SA) is an upcall from the kernel to the user-level scheduler, that is, a call made by the kernel into user code (the reverse of a system call).

Events flow in both directions. The process tells the kernel when a virtual processor is idle and when a virtual processor is needed. The kernel, in turn, notifies the process of four events:

1. Virtual processor allocated: the user-level scheduler runs a READY thread on it.
2. SA blocked: the scheduler marks that thread BLOCKED and runs another thread on the notifying SA.
3. SA unblocked: the scheduler returns the thread to READY.
4. SA preempted: the scheduler puts the preempted thread back to READY and re-evaluates.

The result is both flexible, since any scheduling policy can be built on these events, and efficient, since no thread stays READY while a virtual processor is available.

Self-Test and Tutorial 3 Answers

This section collects the guide's self-test questions not already placed after their topics, then the official Tutorial 3 answers and the Week 4 Ed practice quiz. Try each question before opening the answer. Questions answered earlier in the Part are listed at the end so you can find them.

Self-test

The other self-test questions sit with their topics: Q2 (processes vs threads) in 4.9; Q7 (wait/notifyAll) in 4.6; Q8 and Q9 (enrolment races, deadlock) in 4.7; Q10 (the 2016 past-exam question), Q11 and Q12 (architectures and throughput) in 4.8; Q13 (user-level vs kernel-level threads) in 4.10.

Tutorial 3 model answers (Week 4) official

These are the tutors' official answers from Ed, Tutorial 03 (Week 4), plus the Week 5 thread demos. Staff have confirmed that tutorial content is examinable.

Code demos (Weeks 4–5). The demos covered sleep, join and synchronisation; a multithreaded socket server and client; threads created by extending Thread and by implementing Runnable; and resource locking with ReentrantReadWriteLock, which allows many readers or one writer (section 4.7).

Ed practice quiz (Week 4), with answers