Threads, processes, and context switching

Required reading: proc.c (focus on scheduler() and sched()), setjmp.S, and sys_fork (in sysproc.c)

Overview

Big picture: more programs than processors. How to share the limited number of processors among the programs?

Observation: most programs don't need the processor continuously, because they frequently have to wait for input (from user, disk, network, etc.)

Idea: when one program must wait, it releases the processor, and gives it to another program.

Mechanism: thread of computation, an active active computation. A thread is an abstraction that contains the minimal state that is necessary to stop an active and an resume it at some point later. What that state is depends on the processor. On x86, it is the processor registers (see setjmp.S).

Address spaces and threads: address spaces and threads are in principle independent concepts. One can switch from one thread to another thread in the same address space, or one can switch from one thread to another thread in another address space. Example: in xv6, one switches address spaces by switching segmentation registers (see setupsegs). Does xv6 ever switch from one thread to another in the same address space? (Answer: yes, v6 switches, for example, from the scheduler, proc[0], to the kernel part of init, proc[1].) In the JOS kernel we switch from the kernel thread to a user thread, but we don't switch kernel space necessarily.

Process: one address space plus one or more threads of computation. In xv6 all user programs contain one thread of computation and one address space, and the concepts of address space and threads of computation are not separated but bundled together in the concept of a process. When switching from the kernel program (which has multiple threads) to a user program, xv6 switches threads (switching from a kernel stack to a user stack) and address spaces (the hardware uses the kernel segment registers and the user segment registers).

xv6 supports the following operations on processes:

This interfaces doesn't separate threads and address spaces. For example, with this interface one cannot create additional threads in the same threads. Modern Unixes provides additional primitives (called pthreads, POSIX threads) to create additional threads in a process and coordinate their activities.

Scheduling. The thread manager needs a method for deciding which thread to run if multiple threads are runnable. The xv6 policy is to run the processes round robin. Why round robin? What other methods can you imagine?

Preemptive scheduling. To force a thread to release the processor periodically (in case the thread never calls sleep), a thread manager can use preemptive scheduling. The thread manager uses the clock chip to generate periodically a hardware interrupt, which will cause control to transfer to the thread manager, which then can decide to run another thread (e.g., see trap.c).

xv6 code examples

Thread switching is implemented in xv6 using setjmp and longjmp, which take a jumpbuf as an argument. setjmp saves its context in a jumpbuf for later use by longjmp. longjmp restores the context saved by the last setjmp. It then causes execution to continue as if the call of setjmp has just returned 1.

Example of thread switching: proc[0] switches to scheduler:

Why switch from proc[0] to the processor stack, and then to proc[0]'s stack? Why not instead run the scheduler on the kernel stack of the last process that run on that cpu?

How is preemptive scheduling implemented in xv6? Answer see trap.c line 2905 through 2917, and the implementation of yield() on sheet 22.

How long is a timeslice for a user process? (possibly very short; very important lock is held across context switch!)