Session 13: Switching processes in Minix

Textbook: None related

Handling a CLOCK interrupt

Step 1: Waking the CLOCK task
Step 2: The CLOCK task responds

Today, we're going to look at exactly what happens in Minix when a quantum expires.

Step 1: Waking the CLOCK task

The business of switching processes when a user process' quantum expires actually occurs in two steps. In the first step, the clock issues an interrupt, and the OS awakens the CLOCK task to respond. In the second step, the CLOCK task responds by modifying the queue and picking the new process to execute.

We're now going to look at the first of these two steps.

  1. First, the clock device issues a hardware interrupt to the CPU. At boot-time (namely, line 6116, using data mentioned at 7802 - but we'll get into that a later day), the OS tells the CPU that a hardware interrupt should be handled by the label hwint00, at line 6164. The CPU pushes the current eip onto the stack and then jumps to line 6164.

  2. The CPU then executes the instructions following line 6164. In this case, we're looking at the code produced by the macro hwint_master(0), define in lines 6143-6060. The first thing this code does is call the save subroutine defined at 6260.

  3. In save, the code pushes all the registers onto the stack in lines 6263-6267. This part works similarly to the system-call handling, except that this time we save all the registers.

  4. Then save starts playing games with the stack, trying to switch to the kernel's stack. We saw this before too. In line 6275, we push _restart to the stack, but now we're pushing onto the kernel's stack, not into the process table. This is to set it up so that when hwint00 returns, it actually jumps to _restart.

  5. The final line of save (77) jumps to the return address saved onto the stack when we called save. It adds the offset RETADR-P_STACKBASE to the old value of esp (pointing into the process table), saved temporarily in eax in line 6271, to determine the address of hwint00 to which to return. This address is stored at the very beginning of the process table entry, and it is the address of line 6145.

  6. We're back in hwint00 at line 6145. The next several lines (6145-6149) tell the CPU that it should no longer accept interrupts from the clock, since it's confusing (and, indeed, potentially catastrophic) for the clock to interrupt the clock interrupt handler. Finally, line 6150 re-enables interrupts, so that from now on we might have another interrupt getting in our way. That's fine, since we've now saved enough about the old process to restore it later on.

  7. Now we look up into the irq_table to see where we need to go to handle interrupt 0. This was set up by the clock task in line 11481 within init_clock(), run when the clock task starts. This line tells the OS that it should remember that clock_handler() is the routine to call when the OS receives a clock interrupt.

  8. So the CPU is now in clock_handler, defined beginning at line 11374. In lines 11441-11444, this routine sets up the local variable rp to point to the entry in the processor table of the current process. Then in lines 11445 to 11451, it does some stuff to update the count of time spent running the process. Ignore the lines 11452-11453 - they're just obscure bits to wake up devices.

  9. Lines 11455-11460 are important, though. Basically, they're there to detect the case that a user process's quantum has expired. (That's the second case of the OR, but it's the more significant case.) Since this is exactly the case we're exploring, we're going to take this branch, going into the interrupt() function and then returning 1.

  10. The interrupt() function begins on line 6938. The point of this is to wake up the I/O task that was waiting for an interrupt to occur. In this case, we want to awaken the CLOCK task. Line 6945 sets rp to point to the row of the process table corresponding to this task.

  11. Lines 6962-6974 are to detect ``dangerous'' conditions where the interrupt-handling process should be held for a while, since it appears that perhaps an interrupt has interrupted the process of handling an earlier interrupt. We'll ignore this piece. We'll also ignore lines 6977-6981, which are to handle the case where the CLOCK task still hasn't completed working with another message.

  12. Lines 6989-6992 save into the CLOCK process structure that CLOCK has received a message from HARDWARE, of type HARD_INT. Lines 6997-7002 place CLOCK at the end of the ready queue. Notice especially 7000, which changes proc_ptr (the pointer to the currently running process), if this task happens to be inserted at the front of the tasks' ready queue.

  13. We return from interrupt(), picking up in clock_handler(), which promptly (line 11460) returns to hwint00 with the value 1.

  14. Now the interrupt handler is ready to return. Since clock_handler() returns 1, the test in 6155-6156 is false. Thus lines 6157-6159, which re-enables the clock interrupt, occur. Then hwint00 returns - and save long ago set up the stack so that when save returns, it actually jumps into restart to start the currently chosen process. Notice that interrupts were disabled in line 7154 so that this switch of processes can proceed safely.

  15. We're now at restart (line 6322), which we saw last time. At this point, we're most likely restoring the CLOCK task awakened by interrupt().

Step 2: The CLOCK task responds

  1. Now the CLOCK task will have blocked within the receive() call on line 11112 within clock_task() in clock.c, awaiting a new message. It just got a message from HARDWARE, with a type of HARD_INT. Lines 11115-11118 are for managing time - you can basically ignore them.

  2. Line 11120 switches on the opcode, which in this case is HARD_INT. So we go into do_clocktick() on line 11140. Within this, ignore 11149-11174, which is for handling processes that have scheduled an alarm. (This isn't the scenario we're considering.) Instead, look at 11178, which tests to see whether the current process has run out of time. Since it has, we'll going to call lock_sched() (from line 11179).

  3. We're now back into Layer 0 at line 7388, trying to schedule our next process. lock_sched(), which simply temporarily sets switching to TRUE to signal to other processes that switching is occurring and so they can't rely on the process table too much.

  4. In sched() (line 7311), the OS rotates the user ready queue, placing the head at the tail. Then it calls pick_proc() (line 7179).

  5. Finally, pick_proc() updates the global variable proc_ptr to point to the next process to execute. Here you can see the policy of choosing first a task, then a server, then a user process, and finally the idle process.

  6. Now pick_proc() returns, and sched() returns, and lock_sched() returns (after resetting switching). Now do_clocktick() (line 11180) updates the global variables sched_ticks and prev_ptr to reflect that we have a new user process.

  7. We return to clock_task() at line 11131. Line 11132 doesn't do anything, since opcode is indeed HARD_INT, so the clock task iterates back to line 1112, where it tries to receive its next message. This will block, since there is no message to receive.

  8. The receive() interrupt will block the CLOCK task and run the process currently pointed to by proc_ptr, which CLOCK updated within pick_proc().