Operating Systems #3 — Processes and Threads

What a process actually is

A process is the data structure holding everything a program needs in order to run. Inside it:

• text — the program code.
• stack — everything to do with function calls: parameters, the return address to come back to, the callee's local variables.
• data — static and global variables, reachable regardless of which part of the program is executing.
• heap — data stored through dynamic allocation.
• control information — the state this process needs to keep running, mostly PC and register values.

Why a stack, specifically? Think about nested calls. A calls B, B calls C — the return address that takes C back to B sits on top, so you just pop it. Then the address that takes B back to A is on top.

The control information lives inside the process because of multiprogramming and multitasking. Programs take turns running, so state has to be saved each time.

The address space

The region a process occupies in memory is its address space, from 0 to MAX. It's logically contiguous, but where it lives in physical memory is unknown — it may not be contiguous there at all, and memory management decides. From the process's point of view it just logically owns 0 through MAX.

The regions split into fixed and variable size.

• Fixed — text (code) and data (statics and globals don't get created anew or change size).
• Variable — heap (allocation and free) and stack (calls and returns).

So the fixed parts go at the bottom and the variable parts sit at either end, growing and shrinking toward each other. Since address space size is a logical thing, MAX is set very large, and the two are unlikely to ever meet.

The five states

A process has a state, and the OS manages it.

• new — just created, contents filled in, loaded into memory. Not yet eligible for CPU scheduling. On ordinary operating systems you can treat new as essentially nonexistent — a process goes straight into the eligible set. Real time systems differ: if a new process cuts in among processes running to deadlines, the deadlines may be missed. So it stays in new, out of the scheduling set, until an existing process finishes and admitting it looks safe.
• running — holding the CPU and doing work. With one core there is exactly one running process.
• waiting — waiting for an event, mostly an I/O event. Effectively, the I/O hasn't finished so it must not hold the CPU. It leaves this state at the moment it learns the I/O is done (an interrupt arrives), and goes to ready.
• ready — ready to work but no CPU assigned yet. Like waiting, it isn't doing work, but unlike waiting it can be given the CPU at any moment.
• terminated — finished its last instruction. No longer eligible for scheduling, and the OS frees it. That is: last instruction done, not yet destroyed.

Transitions

A newly created process enters new. In a real time system, when admission control decides it may join the scheduling set, it's admitted to ready. From ready, getting the CPU makes it running — that step is the scheduler dispatch.

There are three ways out of running:

1. Finishing the last instruction and becoming terminated.
2. Issuing I/O and waiting for it. Holding the CPU is pointless, so it releases the CPU and goes to waiting. When the completion interrupt arrives it goes to ready.
3. Running out of its allotted time. Multitasking exists for time sharing, so when the time is up the CPU is handed over. No I/O was issued, so it goes to ready, not waiting. It isn't only I/O devices that send interrupts — the timer device does too.

The PCB

The structure that gives a process concrete form is the PCB (Process Control Block). Every OS builds it differently; Linux declares it as task_struct. That struct is one process.

A PCB holds the current state, PC, CPU registers, CPU scheduling information (priority and so on), memory management information (where it's loaded, how far the stack and heap have grown), accounting information (how long since it started, how much memory it uses, how much CPU it has consumed), and I/O status (which I/O it has requested, which files it has open). It's genuinely complicated — everything about the process is in there.

Queues and schedulers

Since there's more than one process in any given state, they're kept in queues.

• Job queue — all processes (pointers to PCBs).
• Ready queue — processes waiting for the CPU, i.e. in the ready state.
• Device queue — the set of processes waiting on that device's I/O, i.e. in the waiting state.

A state change moves a process between queues. Waiting for I/O in a device queue and receiving the interrupt sends it to the ready queue; being granted the CPU takes it out of the ready queue. (It stays in the job queue throughout.)

There are three schedulers.

• Long term scheduler (job scheduler) — moves processes from new to ready. Relatively infrequent, since it only decides whether to admit when a new process is created and one of the running ones finishes. The number of processes eligible for CPU scheduling is the degree of multiprogramming (running, waiting, and ready), and the long term scheduler controls it.
• Short term scheduler — picks which of the ready processes runs. This is what people mean by "the CPU scheduler." Time quanta are very short, so it runs very often.
• Medium term scheduler — when memory runs short, picks a process to push out to disk (swap out) and fills the space with a new one (swap in). When the swapped-out process is due to run again it's brought back and put on the ready queue. The prime candidates for swapping out are suspended processes.

Processes carry one piece of information that matters enormously to the scheduler: is this a process that issues a lot of I/O (editors, messengers — short CPU usage but frequent; many short CPU bursts), or one that just computes (once it starts it keeps computing; few very long CPU bursts)?

Context switching

Within one program the context holds, but moving to another program means the CPU works in a completely different context. Hence context switch. It comes with saving the outgoing process's state and loading the incoming one's — overhead you accept in exchange for multiprogramming.

There's a second cost beyond the switch itself: cache misses. Whatever the CPU read from memory is sitting in cache, and when a completely different program runs that cache is meaningless. So it's flushed, and misses spike immediately after.

A CPU switch happens on a timer interrupt or a system call. The system call side confused me for a while. The user process and whatever handles the system call it invoked are the same process. So why does a context switch occur?

Normally the system call is handled in the same process. But if handling it requires other work inside the kernel, the kernel may end up running a different process, and that's a context switch. It isn't a separate program running — the kernel temporarily loads a different PCB at the current process's request. (Threads appear to have PCBs too, one each, and what's loaded here seems to be a kernel thread's PCB for handling the call.) For now I've filed it as: in some cases, invoking a system call can cause a context switch.

Creating processes — fork and exec

It's easy to think a double-click creates a process, but really the process that receives the click event calls fork() to create a child. That is, a process creates another process. So processes have a family tree, and every process descends from a root process — a shell, say. Every process has a pid.

Parent and child have no relationship beyond "the parent made the child." In terms of context they're unrelated. The reason the relationship still has to be managed is that when a child dies, some process has to receive its return value. The parent does that.

The child's address space is an exact copy of the parent's. Immediately after fork() they're identical: PC, registers, memory, open files. Since PC matches too, the child starts at the same point the parent is at — which is why the return value differs.

• The parent gets the pid of the child it created.
• The child gets 0.
• A negative value means fork() failed.

wait(NULL) blocks until a child you created finishes.

fork() only duplicates the address space. It's exec() that fills the address space with the program passed as its argument, at which point the two become completely independent processes.

From the lab — one question asked for a one-line difference between fork and exec. fork creates a child that's a copy of the calling process; exec replaces the calling process with the program given as an argument. Another gave source code and asked for the process tree. Tracing by hand which branch gets which parent through nested forks is what makes the differing return values click.

Termination and zombies — exit and wait in xv6

Tracing process termination in the xv6 lab helped. With a parent chain A → B → C, when C calls exit():

• C closes all the files it opened.
• If C had children, their parent is reassigned to initproc.
• If any of them are zombies, initproc is woken to deal with them.
• And C itself becomes a zombie.

Then C's parent calls wait() and reclaims C's resources. If the parent already exited so the parent became initproc, initproc reclaims them. wait() reclaims a zombie child and returns its pid; it returns -1 if there's no child or if it's killed while waiting.

The parent exiting first follows the same rules. When A calls exit(), all its children get initproc as parent. If the user then calls kill() to set C's killed to 1, C calls exit() the next time the scheduler gives it the CPU and it goes through interrupt handling. C's parent is initproc by then, so initproc reclaims the resources on its wait().

Threads

Threads inside one process aren't processes, so they don't have code of their own. Having been created inside one process, they run the same code. Code is shared; the data section (globals) is shared no matter where in the program a thread is executing; open files are shared.

So what has to differ? One thread might be running function A while another runs function B. The calls differ, so the return addresses, parameters, and locals on the stack differ. Hence each thread has its own stack. State information and register values obviously differ too.

In short: a thread is a dynamic entity inside a single process, with its own register state and its own stack.

Why use threads

A thread is called a lightweight process. It's the basic unit of work, and it's light because it shares more with its siblings than processes do (data, code, files).

• Responsiveness. A single-threaded process has no choice but to go to waiting when it issues I/O or makes a blocking system call. Split into threads running at different points, one thread entering waiting leaves the others working — the program as a whole keeps making progress.
• Resource efficiency. Why not just create several processes? You could, but a process has its own address space. Even processes doing identical work get their code and data sections copied into memory separately, which wastes resources. Threads keep one copy.
• Economy. Creating processes is expensive. fork() copies the context and address space, so it's slow. A thread shares what it can and creates only what it must, so creation and destruction are cheap.
• Scalability. On a multicore machine one process can never run on several cores at once. Composed of several threads, a single process can have each thread running on a different core simultaneously.

Kernel threads and user threads

Kernel threads are supported at the kernel level — the kernel creates them. The kernel can manage them, and CPU scheduling can happen per thread.

User threads are invisible to the kernel. They're created at user level through a thread library, which just makes thread objects inside the process. The kernel sees one process and knows nothing of the threads inside, so it can only schedule per process.

Does that make kernel threads strictly better? Not quite. User threads are created and destroyed without the kernel's help, so they're light and fast; kernel threads have to go through the kernel and are slower. That said, most kernels support threads these days, so kernel-level threads are the norm.