Roadmap 3: Interrupts

In this part, we study the following issues associated with interrupts:

• Data Structures of the Interrupt
• Hardware timer emulator.
• Interface between system (software) and timer (hardware).
• How are interrupts Scheduled?
• What happens when a timer interrupt occurs?

Let us first start by looking at the file main.cc (in threads/main.cc) and note the call to the function Initialize() as shown below:

threads/main.cc

int
main(int argc, char **argv)
{
    int argCount;                       // the number of arguments
                                        // for a particular command

    DEBUG('t', "Entering main");
    (void) Initialize(argc, argv);
...

Main calls Initialize() before any other function (Debug () is just for logging purposes). Its purposes are to initialize the global data structures and construct the interrupt, the scheduler, and the machine timer objects. Let's take a look at a few lines of code from this function.

threads/system.*

void
Initialize(int argc, char **argv)
{
...
......Code to take care of options (e.g. debug, random yields, etc )....
...

    DebugInit(debugArgs);                  // initialize DEBUG messages
    stats = new Statistics();                   // collect statistics
    interrupt = new Interrupt;               // start up interrupt handling
    scheduler = new Scheduler();                // initialize the ready queue
    if (randomYield)                            // start the timer (if needed)
        timer = new Timer(TimerInterruptHandler, 0, randomYield);

    threadToBeDestroyed = NULL;
...

    currentThread = new Thread("main");
    currentThread->setStatus(RUNNING);

    interrupt->Enable();
    CallOnUserAbort(Cleanup);                  // if user hits ctl-C
...

To understand the above code, you should first study the Interrupt and Scheduler classes in machine/interrupt.* and threads/scheduler.* respectively. You can see that Initialize first constructs an Interrupt , the Scheduler, and the Timer objects. It then uses the command currentThread = new Thread("main") to create the first formal thread known to the scheduler, indicates it as "running", and enables interrupts by calling Enable().

First, we take a look at Scheduler.

// The following class defines the scheduler/dispatcher abstraction --
// the data structures and operations needed to keep track of which
// thread is running, and which threads are ready but not running.

class Scheduler {
  public:
    Scheduler();                        // Initialize list of ready threads
    ~Scheduler();                       // De-allocate ready list

    void ReadyToRun(Thread* thread);    // Thread can be dispatched.
    Thread* FindNextToRun();            // Dequeue first thread on the ready
                                        // list, if any, and return thread.
    void Run(Thread* nextThread);       // Cause nextThread to start running
    void Print();                       // Print contents of ready list

  private:
    List *readyList;            // queue of threads that are ready to run,
                                // but not running
};

The Scheduler (Dispatcher) has a list of ready threads. When the Scheduler object is constructed, a ready queue is initialized along with the member functions such as ReadyToRun(), FindNextToRun(), and Run().

Then, we look at Interrupt.

// The following class defines the data structures for the simulation
// of hardware interrupts.  We record whether interrupts are enabled
// or disabled, and any hardware interrupts that are scheduled to occur
// in the future.

class Interrupt {
  public:

    ...

  private:
    IntStatus level;            // are interrupts enabled or disabled?
    List *pending;              // the list of interrupts scheduled
                                // to occur in the future
    bool inHandler;             // TRUE if we are running an interrupt handler
    bool yieldOnReturn;         // TRUE if we are to context switch
                                // on return from the interrupt handler
    MachineStatus status;       // idle, kernel mode, user mode

};

The data structures of the interrupts class are as follows:

        |------------------|
        |     level        |    - interrupt level
        |------------------|
        |    pending -->   |    - pointer to list of pending interrupts
        |------------------|
        |    inHandler     |    - boolean to identify if running
        |------------------|      an interrup handler
        |  yieldOnReturn   |    - boolean to identify if the interrupted
        |------------------|      thread should yield
        |    status        |    - MachineStatus: idle, kernel, user mode
        |------------------|

Note

This is a generic interrupt data structure. It is used by a hardware device (timer, consoles, disk, network). Do not change it.

During the system intitialization, the interrupt object is constructed as follows.

//----------------------------------------------------------------------
// Interrupt::Interrupt
//      Initialize the simulation of hardware device interrupts.
//
//      Interrupts start disabled, with no interrupts pending, etc.
//----------------------------------------------------------------------

Interrupt::Interrupt()
{
    level = IntOff;
    pending = new List();
    inHandler = FALSE;
    yieldOnReturn = FALSE;
    status = SystemMode;
}

So, after the construction of interrupt and scheduler, there are two queues in the system: the pending interrupt list and the ready queue. Recall that a list has a list of items along with sorting keys. In the pending list, the items are PendingInterrupt.

// The following class defines an interrupt that is scheduled
// to occur in the future.  The internal data structures are
// left public to make it simpler to manipulate.

class PendingInterrupt {
public:
    PendingInterrupt(VoidFunctionPtr func, int param, int time, IntType kind);
                                // initialize an interrupt that will
                                // occur in the future

    VoidFunctionPtr handler;    // The function (in the hardware device
                                // emulator) to call when the interrupt occurs
    int arg;                    // The argument to the function.
    int when;                   // When the interrupt is supposed to fire
    IntType type;               // for debugging
};

Its data structures are as follows:

        |------------------|
        |    Handler       |    - pointer to the Interrupt
        |------------------|      Handler Function
        |      Arg         |    - argument of type integer
        |------------------|      to interrupt Handler
        |      when        |    - time when this interrupt
        |------------------|      is suppose to occur
        |      type        |    - the device that generated the
        |------------------|      interrupt for debugging purposes

Note

Again, this is the interface defined by an interrupt device (hardware). Do not change it.

Thus, the pending list looks like:

           ---------   ---------
pending -->| next -|-->| next -|--> ... 
           |-------|   |-------|
           |  key  |   |  key  |
           |-------|   |-------|
           | item  |   | item  |
           ----|----   ----|----
               |           |
               |           |
     PendingInterrupt   PendingInterrupt

In the following, we study the timer hardware device and find out:

How the timer schedules timer interrupts;

When and how timer interrupts occur;

What happens when a timer interrupt occurs.

//
//      A hardware timer generates a CPU interrupt every X milliseconds.
//      This means it can be used for implementing time-slicing, or for
//      having a thread go to sleep for a specific period of time.
//
//      We emulate a hardware timer by scheduling an interrupt to occur
//      every time stats->totalTicks has increased by TimerTicks.
//
//      In order to introduce some randomness into time-slicing, if "doRandom"
//      is set, then the interrupt comes after a random number of ticks.
//
//  DO NOT CHANGE -- part of the machine emulation
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation
// of liability and disclaimer of warranty provisions.

#ifndef TIMER_H
#define TIMER_H

#include "copyright.h"
#include "utility.h"

// The following class defines a hardware timer.
class Timer {
  public:
    Timer(VoidFunctionPtr timerHandler, int callArg, bool doRandom);
                                // Initialize the timer, to call the interrupt
                                // handler "timerHandler" every time slice.
    ~Timer() {}

// Internal routines to the timer emulation -- DO NOT call these

    void TimerExpired();        // called internally when the hardware
                                // timer generates an interrupt

    int TimeOfNextInterrupt();  // figure out when the timer will generate
                                // its next interrupt

  private:
    bool randomize;             // set if we need to use a random timeout delay
    VoidFunctionPtr handler;    // timer interrupt handler
    int arg;                    // argument to pass to interrupt handler

};

 

 

//----------------------------------------------------------------------
// Timer::Timer
//      Initialize a hardware timer device.  Save the place to call
//      on each interrupt, and then arrange for the timer to start
//      generating interrupts.
//
//      "timerHandler" is the interrupt handler for the timer device.
//              It is called with interrupts disabled every time the
//              the timer expires.
//      "callArg" is the parameter to be passed to the interrupt handler.
//      "doRandom" -- if true, arrange for the interrupts to occur
//              at random, instead of fixed, intervals.
//----------------------------------------------------------------------

Timer::Timer(VoidFunctionPtr timerHandler, int callArg, bool doRandom)
{
    randomize = doRandom;
    handler = timerHandler;
    arg = callArg;

    // schedule the first interrupt from the timer device
    interrupt->Schedule(TimerHandler, (int) this, TimeOfNextInterrupt(),
                TimerInt);
}

From the above code, we can see that when the timer is constructed during the system initialization TimerInterruptHandler is passed to the Timer as the first argument, then the interrupt is called to schedule the first interrupt by calling interrupt->Schedule(). Make sure you understand the arguments being passed to this constructor, especially the pointer to the function TimerHandler(). Note that this routine can only be called by a hardware device such as timer and should not be called by the NACHOS kernel directly.

//----------------------------------------------------------------------
// Interrupt::Schedule
//      Arrange for the CPU to be interrupted when simulated time
//      reaches "now + when".
//
//      Implementation: just put it on a sorted list.
//
//      NOTE: the Nachos kernel should not call this routine directly.
//      Instead, it is only called by the hardware device simulators.
//
//      "handler" is the procedure to call when the interrupt occurs
//      "arg" is the argument to pass to the procedure
//      "fromNow" is how far in the future (in simulated time) the
//               interrupt is to occur
//      "type" is the hardware device that generated the interrupt
//----------------------------------------------------------------------
void
Interrupt::Schedule(VoidFunctionPtr handler, int arg, int fromNow, IntType type)
{
    int when = stats->totalTicks + fromNow;
    PendingInterrupt *toOccur = new PendingInterrupt(handler, arg, when, type);

    DEBUG('i', "Scheduling interrupt handler the %s at time = %d\n",
                                        intTypeNames[type], when);
    ASSERT(fromNow > 0);

    pending->SortedInsert(toOccur, when);
}

As shown in the above code, this function first calculates the time when the interrupt is scheduled to occur, then it constructs a PendingInterrupt and inserts it on the pending interrupt list (sorted by times).

As mentioned before, this routine is only called by a hardware device, it requires a pointer to an interrupt handler (function). In the case of the timer, this function is TimerHandler() provided by the timer constructor.

// dummy function because C++ does not allow pointers to member functions
static void TimerHandler(int arg)
{ Timer *p = (Timer *)arg; p->TimerExpired(); }

Note

This is a dummy function. It is really TimerExpired().

//----------------------------------------------------------------------
// Timer::TimerExpired
//      Routine to simulate the interrupt generated by the hardware
//      timer device.  Schedule the next interrupt, and invoke the
//      interrupt handler.
//----------------------------------------------------------------------
void
Timer::TimerExpired()
{
    // schedule the next timer device interrupt
    interrupt->Schedule(TimerHandler, (int) this, TimeOfNextInterrupt(),
                TimerInt);

    // invoke the Nachos interrupt handler for this device
    (*handler)(arg);
}

Note

This function schedules the next timer interrupt and runs handler(), which is TimerInterruptHandler() passed by the system during the construction of the timer.

//----------------------------------------------------------------------
// TimerInterruptHandler
//      Interrupt handler for the timer device.  The timer device is
//      set up to interrupt the CPU periodically (once every TimerTicks).
//      This routine is called each time there is a timer interrupt,
//      with interrupts disabled.
//
//      Note that instead of calling Yield() directly (which would
//      suspend the interrupt handler, not the interrupted thread
//      which is what we wanted to context switch), we set a flag
//      so that once the interrupt handler is done, it will appear as
//      if the interrupted thread called Yield at the point it is
//      was interrupted.
//
//      "dummy" is because every interrupt handler takes one argument,
//              whether it needs it or not.
//----------------------------------------------------------------------
static void
TimerInterruptHandler(int dummy)
{
    if (interrupt->getStatus() != IdleMode)
        interrupt->YieldOnReturn();
}

Note the call toYieldOnReturn() in the above code. Read the comments carefully to understand why this call to YieldOnReturn() is made instead of just Yield(). Why is YieldOnReturn() called only if the machine is not in idle mode? What happens if the machine is in idle mode?

//----------------------------------------------------------------------
// Interrupt::YieldOnReturn
//      Called from within an interrupt handler, to cause a context switch
//      (for example, on a time slice) in the interrupted thread,
//      when the handler returns.
//
//      We can't do the context switch here, because that would switch
//      out the interrupt handler, and we want to switch out the
//      interrupted thread.
//----------------------------------------------------------------------

void
Interrupt::YieldOnReturn()
{
    ASSERT(inHandler == TRUE);
    yieldOnReturn = TRUE;
}

What is the effect of setting the flag yieldOnReturn to TRUE?

At this point, you should understand:

How the timer schedules timer interrupts;

What happens when a timer interrupt occurs.

The function of the (simulated) machine clock Timer is to generate timer interrupts. There are several types of interrupts (see machine/interrupt.h for interrupt types). A timer interrupt forces the running thread to execute the function TimerInterruptHandler, which is defined by the system. Thus the hardware timer schedules timer interrupts, whereas the system determines what to do when a timer interupt occurs. For now, a timer interrupt causes the current thread to yield if the machine is not idle. This is how a time-slice can be introduced in a time-sharing system.

How interrupts occur? In other words, how a pending interrupt is removed from the pending list and its handler gets run?

//----------------------------------------------------------------------
// Interrupt::CheckIfDue
//      Check if an interrupt is scheduled to occur, and if so, fire it off.
//
// Returns:
//      TRUE, if we fired off any interrupt handlers
// Params:
//      "advanceClock" -- if TRUE, there is nothing in the ready queue
,
//              so we should simply advance the clock to when the next
//              pending interrupt would occur (if any).  If the pending
//              interrupt is just the time-slice daemon, however, then
//              we're done!
//----------------------------------------------------------------------
bool
Interrupt::CheckIfDue(bool advanceClock)
{
    MachineStatus old = status;
    int when;

    ASSERT(level == IntOff);            // interrupts need to be disabled,
                                        // to invoke an interrupt handler
    if (DebugIsEnabled('i'))
        DumpState();
    PendingInterrupt *toOccur =
                (PendingInterrupt *)pending->SortedRemove(&when);

    if (toOccur == NULL)                // no pending interrupts
        return FALSE;

    if (advanceClock && when > stats->totalTicks) {       // advance the clock
        stats->idleTicks += (when - stats->totalTicks);
        stats->totalTicks = when;
    } else if (when > stats->totalTicks) {        // not time yet, put it back
        pending->SortedInsert(toOccur, when);
        return FALSE;
    }

// Check if there is nothing more to do, and if so, quit
    if ((status == IdleMode) && (toOccur->type == TimerInt)
                                && pending->IsEmpty()) {
         pending->SortedInsert(toOccur, when);
         return FALSE;
    }

    DEBUG('i', "Invoking interrupt handler for the %s at time %d\n",
                        intTypeNames[toOccur->type], toOccur->when);
#ifdef USER_PROGRAM
    if (machine != NULL)
        machine->DelayedLoad(0, 0);
#endif
    inHandler = TRUE;
    status = SystemMode;                        // whatever we were doing,
                                                // we are now going to be
                                                // running in the kernel
    (*(toOccur->handler))(toOccur->arg);  // call the interrupt handler
    status = old;                               // restore the machine status
    inHandler = FALSE;
    delete toOccur;
    return TRUE;
}

What does the argument advanceClock mean?

This function does the following:

When do interrupts occur? In other words, when is CheckIfDue() called?

This function is called by OneTick(), which is called after the execution of a user instruction or when interrupts are turned back on from off. It is also called by Idle() when the ready queue is empty.

//----------------------------------------------------------------------
// Interrupt::Idle
//      Routine called when there is nothing in the ready queue.
//
//      Since something has to be running in order to put a thread
//      on the ready queue, the only thing to do is to advance
//      simulated time until the next scheduled hardware interrupt.
//
//      If there are no pending interrupts, stop.  There's nothing
//      more for us to do.
//----------------------------------------------------------------------
void
Interrupt::Idle()
{
    DEBUG('i', "Machine idling; checking for interrupts.\n");
    status = IdleMode;
    if (CheckIfDue(TRUE)) {             // check for any pending interrupts
        while (CheckIfDue(FALSE))       // check for any other pending
            ;                           // interrupts
        yieldOnReturn = FALSE;          // since there's nothing in the
                                        // ready queue, the yield is automatic
        status = SystemMode;
        return;                         // return in case there's now
                                        // a runnable thread
    }

    // if there are no pending interrupts, and nothing is on the ready
    // queue, it is time to stop.   If the console or the network is
    // operating, there are *always* pending interrupts, so this code
    // is not reached.  Instead, the halt must be invoked by the user program.

    DEBUG('i', "Machine idle.  No interrupts to do.\n");
    printf("No threads ready or runnable, and no pending interrupts.\n"
;);
    printf("Assuming the program completed.\n");
    Halt();
}

When both the ready queue and the pending interrupt list are empty, the system Halt().

//----------------------------------------------------------------------
// Interrupt::Halt
//      Shut down Nachos cleanly, printing out performance statistics.
//----------------------------------------------------------------------
void
Interrupt::Halt()
{
    printf("Machine halting!\n\n");
    stats->Print();
    Cleanup();     // Never returns.
}

//----------------------------------------------------------------------
// Interrupt::OneTick
//      Advance simulated time and check if there are any pending
//      interrupts to be called.
//
//      Two things can cause OneTick to be called:
//              interrupts are re-enabled
//              a user instruction is executed
//----------------------------------------------------------------------
void
Interrupt::OneTick()
{
    MachineStatus old = status;

// advance simulated time
    if (status == SystemMode) {
        stats->totalTicks += SystemTick;
        stats->systemTicks += SystemTick;
    } else {                                    // USER_PROGRAM
        stats->totalTicks += UserTick;
        stats->userTicks += UserTick;
    }
    DEBUG('i', "\n== Tick %d ==\n", stats->totalTicks);

// check any pending interrupts are now ready to fire
    ChangeLevel(IntOn, IntOff);         // first, turn off interrupts
                                        // (interrupt handlers run with
                                        // interrupts disabled)
    while (CheckIfDue(FALSE))           // check for pending interrupts
        ;
    ChangeLevel(IntOff, IntOn);         // re-enable interrupts
    if (yieldOnReturn) {                // if the timer device handler asked
                                        // for a context switch, ok to do it now
        yieldOnReturn = FALSE;
        status = SystemMode;            // yield is a kernel routine
        currentThread->Yield();
        status = old;
    }
}

This function first advances the time, then checks if any pending interrupts due by calling CheckIfDue(). Finally, if the yieldOnReturn flag is TRUE, it resets the flag and the interrupted thread yields.

When is OneTick() called?

//----------------------------------------------------------------------
// Interrupt::SetLevel
//      Change interrupts to be enabled or disabled, and if interrupts
//      are being enabled, advance simulated time by calling OneTick().
//
// Returns:
//      The old interrupt status.
// Parameters:
//      "now" -- the new interrupt status
//----------------------------------------------------------------------

IntStatus
Interrupt::SetLevel(IntStatus now)
{
    IntStatus old = level;

    ASSERT((now == IntOff) || (inHandler == FALSE));// interrupt handlers are
                                                // prohibited from enabling
                                                // interrupts

    ChangeLevel(old, now);                      // change to new state
    if ((now == IntOn) && (old == IntOff))
        OneTick();                              // advance simulated time
    return old;
}

This function can be called when interrupts are enabled.

//----------------------------------------------------------------------
// Interrupt::Enable
//      Turn interrupts on.  Who cares what they used to be?
//      Used in ThreadRoot, to turn interrupts on when first starting up
//      a thread.
//----------------------------------------------------------------------
void
Interrupt::Enable()
{
    (void) SetLevel(IntOn);
}

When interrupts are enabled, this function calls SetLevel() which in turn calls OneTick() to advance the time if the old level is off.

//----------------------------------------------------------------------
// Machine::Run
//      Simulate the execution of a user-level program on Nachos.
//      Called by the kernel when the program starts up; never returns.
//
//      This routine is re-entrant, in that it can be called multiple
//      times concurrently -- one for each thread executing user code.
//----------------------------------------------------------------------

void
Machine::Run()
{
    Instruction *instr = new Instruction;  // storage for decoded instruction

    if(DebugIsEnabled('m'))
        printf("Starting thread \"%s\" at time %d\n",
               currentThread->getName(), stats->totalTicks);
    interrupt->setStatus(UserMode);
    for (;;) {
        OneInstruction(instr);
        interrupt->OneTick();
        if (singleStep && (runUntilTime <= stats->totalTicks))
          Debugger();
    }
}
....
....

As shown above, it repeatedly executes a user instruction and advances the time using OneTick().

Big Picture

When a Nachos system is booted up (initialize() in threads/system.*), an interrupt object including a list for pending interrupts is set up, a ready queue is created, and then a hardware device timer simulator is constructed. The system passes the pointer to the TimerInterruptHandler() function to the timer. For now, this function just turns on yieldOnReturn if the ready queue is not empty. The timer device starts with scheduling the first timer interrupt (Timer::Timer, machine/timer.*). When a timer interrupt is fired, TimerHandler() gets run, which schedules the next timer interrupt and runs TimerInterruptHandler(). Interrupts occur when CheckIfDue() is called in the following situations: