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 threads/main.cc and note the construction of the kernel and the call to the kernel function Initialize() as shown below:

threads/main.cc

int
main(int argc, char **argv)
{
    ...
    DEBUG(dbgThread, "Entering main");

    kernel = new ThreadedKernel(argc, argv);
    kernel->Initialize();
    ...

}

Let's take a look at the code of the function Initialize().

threads/kernel.*

void
ThreadedKernel::Initialize()
{
    stats = new Statistics();             // collect statistics

    interrupt = new Interrupt;            // start up interrupt handling
    scheduler = new Scheduler();          // initialize the ready queue
    alarm = new Alarm(randomSlice);       // start up timer slicing


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

    interrupt->Enable();
}

To understand the above code, we first study machine/interrupt.*, threads/scheduler.*, and machine/timer.*. You can see that Initialize() first constructs an interrupt, the scheduler, and the alarm 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, bool finishing);
                                      // Cause nextThread to start running
    void CheckToBeDestroyed();        // check if thread that had been
                                      // running needs to be deleted
    void Print();                     // Print contents of ready list

  private:
    List<Thread *> *readyList;        // queue of threads that are ready to run,
                                     // but not running
    Thread *toBeDestroyed;           // finishing thread to be destroyed
                                     // by the next thread that runs
};

                        --------------------
                        |   readyList ->   |
                        --------------------
                        | toBeDestroyed -> |
                        --------------------

NOTE

The Scheduler (Dispatcher) has a list of ready threads and a thread to be destroyed. 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?
    SortedList<PendingInterrupt *> *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
};

NOTE

The data structures of the interrupt 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 and user modes
        |------------------|

Note

This is a generic interrupt data structure. It is used by a hardware devices (timer, console input, console output, disk, network input, network output). 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 SortedList<PendingInterrupt *>(PendingCompare);
    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. In the ready queue, the items are threads.

// 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(CallBackObj *callOnInt, int time, IntType kind);
                                // initialize an interrupt that will
                                // occur in the future

    CallBackObj *callOnInterrupt;
                                // The object (in the hardware device
                                // emulator) to call when the interrupt occurs
    int when;                   // When the interrupt is supposed to fire
    IntType type;               // for debugging
};

NOTE

The PendingInterrupt data structures are as follows:

        |---------------------|
        |  callOnInterrupt -> |    - pointer to CallBackObj
        |---------------------|
        |      when           |    - time when this interrupt
        |---------------------|      is supposed to occur
        |      type           |    - the type of the device that generated
        |---------------------|      the interrupt

CallBackObj is a base class defined in machine/callback.h.

// Abstract base class for objects that register callbacks

class CallBackObj {
   public:
     virtual void CallBack() = 0;
   Protected
     CallBackObj() {};         // to prevent anyone from creating
                               // an instance of this class. Only
                               // allow creation of instances of
                               // classes derived from this class.
     virtual ~CallBackObj() {};
};

Note

Again, the structure of PendingInterrupt is the interface provided 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.

// The following class defines a hardware timer.
class Timer : public CallBackObj {
  public:
    ...
  private:
    ...
    CallBackObj *callPeriodically;
                                // call this every TimerTicks time units
    ...
    CallBack();
    ...
};

The hardware device timer is a class derived from the base class CallBackObj. It has an implementation of member function CallBack().

//----------------------------------------------------------------------------
// 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.
//
//      "doRandom" -- if true, arrange for the interrupts to occur
//              at random, instead of fixed, intervals.
//      "toCall->CallBack()" is the interrupt handler to call when
//              the timer expires.
//----------------------------------------------------------------------------

Timer::Timer(bool doRandom, CallBackObj *toCall)
{
    randomize = doRandom;
    callPeriodically = toCall;
    disable = FALSE;
    SetInterrupt();
}

Keep in mind that callPeriodically is the pointer to CallBackObj, which is passed to the timer constructor. The constructor then calls SetInterrupt().

Timer::SetInterrupt

//---------------------------------------------------------------------------
// Timer::SetInterrupt
//      Cause a timer interrupt to occur in the future, unless
//      future interrupts have been disabled. The delay is either
//      fixed or random.
//---------------------------------------------------------------------------

void
Timer::SetInterrupt()
{
    if (!disable) {
       int delay = TimerTicks;

       if (randomize) {
             delay = 1 + (RandomNumber() % (TimerTicks * 2));
       }
       // schedule the next timer device interrupt
       kernel->interrupt->Schedule(this, delay, TimerInt);
    }
}

Thus, when the timer is constructed, after calculating the time delay, SetInterrupt() calls Nachos kernel to schedule the first timer interrupt by inserting a PendingInterrupt into the pending queue as shown below. In this case, the object of class CallBackObj in the PendingInterrupt structure is the timer, which is an object of a class derived from the base class CallBackObj.

machine/interrupt.*

//----------------------------------------------------------------------
// 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.
//
//      "toCall" is the object to call when the interrupt occurs
//      "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(CallBackObj *toCall, int fromNow, IntType type)
{
    int when = stats->totalTicks + fromNow;
    PendingInterrupt *toOccur = new PendingInterrupt(toCall, when, type);
    ...
    pending->Insert(toOccur);
}

Now we know that when the timer is constructed, it schedules the first timer interrupt. But

when is the timer constructed?

What is the object toCall passed to the timer constructor? In particular, what does callPeriodically->CallBack() do? Note that inside timer, callPeriodically is toCall.

The timer is constructed by the alarm, which is constructed when the Nachos kernel is initialized in threads/main.cc.

Note that Alarm is incomplete. For example, the member function WaitUntil() is not impletemented.

threads/alarm.*

// The following class defines a software alarm clock.
class Alarm : public CallBackObj {
  public:
    ...
  private:
    Timer *timer;                   // the hardware timer device

    void CallBack();                // called when the hardware
                                    // timer generates an interrupt
};



//---------------------------------------------------------------------------
// Alarm::Alarm
//      Initialize a software alarm clock. Start up a timer device
//
//      "doRandom" -- if true, arrange for the hardware interrupts to
//              occur at random, instead of fixed, intervals.
//----------------------------------------------------------------------------

Alarm::Alarm(bool doRandom)
{
    timer = new Timer(doRandom, this)
}

Now, we see that alarm constructs the timer and passes the alarm object to the timer constructor. So, we find out alarm CallBack():

void
Alarm::CallBack()
{
    ...
    if (status == IdleMode) {
        ...
    } else {
        interrupt->YieldOnReturn();
    }
}

If the machine is not in idle mode, it calls YieldOnReturn(). Read the comments carefully to understand

why this call to YieldOnReturn() is made instead of calling Yield() (in threads/thread.*) directly?

Why is YieldOnReturn() called only if the machine is not in idle mode? What happens if the machine is in idle mode?

machine/interrupt.*

//----------------------------------------------------------------------
// 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;
}

NOTE

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

Putting all things together, we can see how timer interrupts work. When the Nachos starts, an alarm is constructed, in turn, the timer is constructed, and the alarm object is passed to the timer, this is the interface between the system software alarm and the hardware device timer. The alarm CallBack() function is the timer interrupt handler, which causes a context switch in the interrupted thread when the interrupt handler returns. Recall that when a timer interrupt is scheduled in SetInterrupt(), the timer object is passed into PendingInterrupt. Thus, when a timer interrupt occurs, the timer CallBack() gets run.

Timer::CallBack()

void
Timer::CallBack()
{
    // invoke the Nachos interrupt handler for this device
    callPeriodically->CallBack();

    SetInterrupt();
}

There are several types of interrupts (see machine/interrupt.h for interrupt types). We only discuss timer interrupts, which introduce time slicing. The other types of interrupts are similar to the timer interrupts.

Next, we find when interrupts occur. In other words, how a pending interrupt is removed from the pending list and its handler gets run.

The following function CheckIfDue() in machine/interrupt.* fires off due interrupts.

machine/interrupt.*

//----------------------------------------------------------------------
// Interrupt::CheckIfDue
//      Check if an interrupts are scheduled to occur, and if so,
//      fire them 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).
//----------------------------------------------------------------------
bool
Interrupt::CheckIfDue(bool advanceClock)
{
    PendingInterrupt *next;
    ...
    ASSERT(level == IntOff):               // interrupts need to be disabled
    ...
    next = pending->Front();
    if (next->when > stats->totalTicks) {
        if (!advanceClock} {               // not time yet
            ...
        } else {                           // advance the clock
            ...
        }
    }
    ...
#ifdef USER_PROGRAM
    if (kernel->machine != NULL) {
        kernel->machine->DelayedLoad(0, 0);
    }
#endif
    inHandler = TRUE;
    do {
        next = pending->RemoveFront();   // pull interrupt off list
        next->callOnInterrupt->CallBack();
                                            // call the interrupt handler
        delete next;
    } while (!pending->IsEmpy()
             && (pending->Front()->when <= stats->totalTicks));
    inHandler = FALSE;
    return TRUE;
}

This function does the following:

When is CheckIfDue() called?

It 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.

machine/interrupt.*

//----------------------------------------------------------------------
// 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(dbgInt, "Machine idling; checking for interrupts.\n");
    status = SystemMode;
    if (CheckIfDue(TRUE)) {             // check for any pending interrupts
        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.

    ...
    Halt();
}

NOTE

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

machine/interrupt.*

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

machine/interrupt.*

//----------------------------------------------------------------------
// 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 oldStatus = status;

// advance simulated time
    ...

// check any pending interrupts are now ready to fire
    ChangeLevel(IntOn, IntOff);         // first, turn off interrupts
                                        // (interrupt handlers run with
                                        // interrupts disabled)
    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
        kernel->currentThread->Yield();
        status = oldStatus;
    }
}

NOTE

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?

machine/interrupt.*

//----------------------------------------------------------------------
// 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;

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

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

This function is also called when interrupts are enabled.

machine/interrupt.*

//----------------------------------------------------------------------
// 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);
}

NOTE

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

machine/mpssim.*

//----------------------------------------------------------------------
// 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(debug->IsEnabled('m')) {
        ...
    }
    kernel->interrupt->setStatus(UserMode);
    for (;;) {
        OneInstruction(instr);
        kernel->interrupt->OneTick();
        if (singleStep && (runUntilTime <= kernel->stats->totalTicks))
          Debugger();
    }
}

NOTE

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/kernel.*), it constructs an interrupt object including a list for pending interrupts, creates a ready queue, and then starts up an alarm, which constructs a hardware device timer. The system passes the alarm object to the timer. The Alarm::CallBack() function in the alarm turns on yieldOnReturn if the ready queue is not empty. The timer device starts with scheduling the first timer interrupt. When a timer interrupt is fired, the Timer::CallBack() gets run, which runs the Alarm::CallBack() and then schedules the next timer interrupt. Interrupts occur when CheckIfDue() is called in the following situations: