Scheduling and intro to hw3.
Tan., pg. 145-163, needed for hw3, coming
We’ve
already discussed CPU-bound = compute-bound processes. Similarly
i/o-bound. Also preemption and preemptive schedulers.
Scheduling
is about sharing resources appropriately among processes. There are 3
major resources to focus on:
Each process wants some fraction of total resource in each direction, and if these fractions (in some direction) add up to more than 100%, then things slow down, even with good scheduling.
Tanenbaum concentrates on CPU scheduling here. Let’s downplay batch and real-time systems and concentrate on Interactive scheduling.
Interactive systems have users inputting commands and expecting fast response. Response Time, pg. 151.
Round-robin—simplest scheme for
interactive systems. We’ll use this in hw3.
Quantum
= CPU time a process/thread gets before it is preempted, about 50 ms. (pg. 155
20-50 ms)
Often
a thread blocks before it reaches this point.
Quantum
is set at about 50 ms, as compromise between throughput and delay in
responsiveness.
A preemption causes a “process switch” or “context switch”. The second term is too vague, since context just means state. And sometimes it is used for just a mode switch, which happens in a system call. A system call causes execution to go from user mode to kernel mode in the same process. So it’s not a process switch, and in fact is a much lighter-weight action than a process switch. Good thing, since system calls (and mode switches in interrupts) happen much more often.
Process Switch is a mysterious operation. Recall that the CPU is handed over to a process for their 50 ms, then an interrupt occurs (or a system call) and the kernel decides to hand the CPU over to another process. But the kernel is using the CPU to make this decision!
Thread scheduling: In both Solaris and Win2K, threads are the primary scheduling unit. For each thread, the process it belongs to is known, of course.
Look at proc.h in handout. Very simple process entry, since no “current directory” or “open files” to worry about.
Mainly CPU state, saved at process switch, plus process status, and what the process is waiting for, if waiting (blocked). Also the exit code, just for zombies.
Process switch: from process i to process j: a function implemented in assembly language.
Recall idea of C scratch registers: allowed to be overwritten in any called function. Gives us some leeway here. (Note we had no such leeway with interrupt handling.)
Job of asmswtch from process i to process
j:
1. Save CPU non-scratch registers in process entry proctab[i] (here *oldpentryp)
2. Load CPU non-scratch registers from process entry proctab[j] (here *newpentryp)
What about EIP, also known as PC? It is changing as this code is running, so doesn’t have a clear value. But what we really need to know is where this function was called from, the “return PC”. So that’s what’s saved here, and used in the return from here.
Look at asmswtch.s in handout: Here is the actual CPU-state switch. It’s tricky to save and restore the CPU registers while using the CPU to do it, but that’s what’s going on here. The ESP points to the whole stack (with kernel stack built on top of user stack), so the swap of ESP represents a swap of program-execution state. EFLAGS is also swapped, with its important IF flag.
I drew a picture of memory in a horizontal line, with the proctab array showing the four PEntry structs, and inside each, the saved-register area. The CPU was represented as an oval with a set of registers inside. We considered a process switch from process 1 to process 2. Asmswtch copies the actual-CPU-registers out of the CPU and into the saved-register area of process 1's PEntry, and then copies the registers from process 2's saved-register area into the actual CPU. These were shown with big fat arrows up and down. The four process stacks were put on the memory line too. The ESP register in the CPU pointed into process 1's stack before the switch, but into process 2's stack after the switch. This way, the whole execution state is switched off, that is, what the current function should return to, etc.
The “saved PC” (i.e. EIP) is actually asmswtch’s return PC. This trick allows us to start a new process with asmswtch as well as switch processes once we’re going. We can put ustart1 in the “saved-PC” spot in a PEntry, and it will be pushed onto the stack in asmswtch and then used in ret, causing a jump to ustart1.
We see that asmswtch takes two arguments, pointers to the old and new PEntry’s. A first try at using it could be asmswtch(&proctab[0],&proctab[1]), to switch from process 0 to process 1, once kernel execution has turned itself into process 0 and set up proctab[1]. But we need good stuff in proctab[1] to load into the CPU.
We can use asmswtch to start a user process as well as switch processes later. Just set up the processes PEntry with:
“saved” ESP = appropriate stack start (more on this soon)
“saved” PC = code’s start address, for example ustart1
“saved” EFLAGS = 0 except IF = 1, so user code runs with interrupts enabled.
“saved” EBP = 0 for clean debugging backtraces
p_status = RUN.
and it will be started by an asmswtch call with second argument pointing to this PEntry. The very first call will be from process 0, the kernel itself, to user process 1, like this, from C code:
asmswtch(p0,p1)
where
p0 = &proctab[0] = pointer to PEntry for process 0
p1 = &proctab[1] =
pointer to PEntry for process 1
This will switch from process 0 (the kernel initialization turned process) to process 1 (the first user process). It copies the “old” CPU registers to the p_saved_regs array in proctab[0], and gets new values for them from proctab[1].p_saved_regs.
To get started, code it like this and see it actually work, and later morph it into better general purpose code. Note that you don’t need to explicitly set up saved registers for process 0, because they will just be overwritten in this first call anyway.
Note that each process needs its own stack, so you need to decide on where these are, for example, growing down from 0x380000, 0x390000, 0x3a0000, and the original one at 0x3ffff0. For example:
proctab[1].saved_regs[SAVED_ESP]
= 0x380000;
But it’s better to name this constant with #define.
Scheduler setup, kernel global variables:
proctab[], curproc: global, used by tunix.c and sched.c
Recall our discussion of PEntry structs, one for each process in the proctab array. There are 4 spots in the array, one for process 0 and 3 for the user processes 1, 2, and 3.
process 0 derives from the startup execution, i.e., the kernel initialization in tunix.c morphs itself into a process by filling in proctab[0] and curproc. It is always runnable, so the scheduler can always find a process to run.
Scheduler API (not encapsulated: uses global proctab[], as do other functions in the kernel)
sched.c will contain the scheduler code—here are its major functions.
The traditional UNIX names are sleep and wakeup, but we want to use “sleep” for a system call name.