Required reading: 7-4 and 7-5, Chapter 8 and 11 of Lion's
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. Example: In v6 on the PDP11, the state is sp, r5, and ka6! (see savu and retu). What is the equivalent on the x86?
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 v6, one switches address spaces by switching segmentation registers (see sureg). Does v6 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 dosn't switch kernel space necessarily.
Process: one address space plus one thread of computation. In v6 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, v6 switches threads (switching from a kernel stack to a user stack) and address spaces (the hardware switches from using the kernel segment registers to the using the user segment registers. When switching from one user program to another, v6 switch both thread and address space.
Sequence coordination. To coordinate the activities between threads explicitly, a thread system supports primimitives for coordination. In v6, the primtives include sleep and wakeup. Sleep releases the processor (by calling swtch); wakeup makes a thread runnuable again, so that swtch might select it to run at some point in the future. Interrupt handlers often call wakeup (e.g., disk I/O completes).
Scheduling. The thread manager needs a method for deciding which thread to run if multiple threads are runnable. The v6 policy is to run the highest priority thread (see swtch), with priorities being dynamically adjusted (see setpri, which is called from the clock interrupt handler).
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 runrun in setpri() and in call (0788)).
Mutual-exclusion coordination. If multiple threads share variables, these variables need to be protected. Otherwise, the values in these variables are the result of the relative scheduling order of the threads, which can lead to disasters (e.g., Therac-25). To indicate that a single thread at a time must proceed through some piece of code, the programmer has to mark these pieces of code as critical sections. It is the programmer's responsibility to mark the sections of code correctly. In v6, only kernel threads share variables (e.g., proc, u, etc.); the user programs contain only one thread, and different user program cannot share variables directly. Because v6 runs on uniprocessors, the only way two threads can enter the same piece of code is if one thread is interrupted in a code path and the interrupt thread enters that code path too; the v6 programmers avoid these problems by temporarily raising the processor priority so that interrupts will be delayed until the priority is lowered again (see bits 5, 6, an 7 of PS, how they are in manipulated in locore.s and spl[0-7]).
| pc (=670)| | r5 (=0) | <- r5 (=usize+64. - 2) | r4 | | r3 | | r2 | <- sp | pc (=1627)| | r5 (=usize+64. -2) | <- r5 | r4 | | r3 | | r2 | <- sp
| pc (=670)| | r5 (=0) | <- r5 (=usize+64. - 2) | r4 | | r3 | | r2 | <- sp | pc (=1638)| | r5 (=usize+64. -2) | <- r5 | r4 | | r3 | | r2 | | pc (=1969)| | r5 (=prev r5) | <- r5 | r4 | | r3 | | r2 | | pc (=2094)| | r5 (=prev r5) | <- r5 | r4 | | r3 | | r2 | <- sp
| pc (=670)| | r5 (=0) | <- r5 (=usize+64. - 2) | r4 | | r3 | | r2 | <- sp | pc (=1627)| | r5 (=usize+64. -2) | <- r5 | r4 | | r3 | | r2 | <- sp
Second, to ensure that certain pieces of kernel code cannot be interrupted, the kernel raises priority of the processor before entering that code and lowwering it when leaving that piece of code. For example, the clock is at interrupt 6; by raising the the priority to 6 after a clock interrupt, no handlers at lower or equal level can interrupt the processor; thus, the clock handler cannot be interrupted until the handler lowers the priority below 6. (Why is the clock at a high interrupt?)
An alternative strategy is to disable interrupts in the kernel (except for clock), as you will do in the lab. What is the advantage of this approach? What is the disadvantage?