Sections Thu Nov 10 to Fri Nov 11

This section handout is based on problems by David Mazières and Jerry Cain, with modifications by Nick Troccoli. Edits by Sumer Kohli.

Learning Goals

During this section, you will:

1. get practice understanding context switches between threads
2. trace through thread execution and how threads are resumed
3. review interrupts and how we enable/disable them as needed to implement preemptive scheduling

Get Started

Clone the section starter code by using the command below. This command creates a section5 directory containing the project files.

git clone /afs/ir/class/cs111/repos/lab5/shared section5

Next, pull up the online section checkoff and have it open in a browser so you can jot things down as you go.

1. Thread Cycle

The thread-cycle.cc program is a gesture to the type of coding you’ll do for assign5. By working through it, you’ll advance your understanding of thread stacks and the context_switch function mentioned in lecture, and you’ll also see a simulated example of threads linked together such that they all get some execution time and run to completion.

Note that on the assignment you'll implement a full Thread class, and you'll keep track of threads in a ready queue; in this smaller example, we have a struct Thread with fewer capabilities, and each thread stores a pointer to the next thread it yields to.

Open thread-cycle.cc - this program is an expanded version of the context-switch.cc program from lecture. In that program, we switched manually between two threads; now we are creating a "thread cycle" of 3 threads that cycle around and give each time to run.

A Thread has a stack and stack pointer (both same as before), but now also a name and a pointer to the next thread that it will yield to. Yielding means voluntarily giving up the CPU to let another thread run:

typedef struct Thread {
    char stack[8192];
    char *saved_rsp;
    string name;
    Thread *next;
} Thread;

There is one global variable current which is a pointer to the current running thread. We initialize it in main to the main thread, and then create two other threads.

int main(int argc, char *argv[]) {
    // Make a Thread variable to represent this main thread, which is currently running
    Thread main_thread("main");
    current = &main_thread;

    // Make two more threads, and link them such that main yields to two,
    // two yields to one, and one yields to main
    Thread one(thread_run, "one", &main_thread);
    Thread two(thread_run, "two", &one);
    main_thread.next = &two;

    cout << "Hello, world!  I am the main thread" << endl;
    yield();
    cout << "Cool, I'm back in main()!" << endl;
    yield();
    cout << "Exiting main" << endl;
    return 0;
}

Each non-main-thread runs the following function:

void thread_run() {
    cout << "Running thread " << current->name << " for the first time." << endl;
    yield();
    cout << "Running thread " << current->name << " after allowing peers to run." << endl;
    yield();
}

yield updates the current variable to point to the next thread that will run, and then performs a context switch to start running the new thread:

void yield() {
    Thread *prev = current;
    current = current->next;
    cout << "Going from thread " << prev->name << " to thread " << current->name << endl;
    context_switch(*prev, *current);
    cout << "Back in thread " << prev->name << endl;
}

context_switch is the same assembly function from lecture.

Compile and run the program, and trace through the code to answer the following questions:

Q1: Describe the implementation of context_switch and how it switches from one thread to another.

Q2: The main function sets up a circular list of threads. What’s the name of the thread besides the main thread that gets to execute code first? What’s the name of the thread besides the main thread that prints something first?

Q3: When the program switches back to executing the main thread the first time, where does it resume?

Q4: The provided Thread struct initializes the thread's stack with "fake" saved registers and a fake layout that makes it look as though it was freeze-framed right before executing the specified function. Why must we initialize the stack in this way, rather than just starting with an empty stack?

Q5: Trace through the program output to match the output with the code. Pay careful attention to the context switches and where each thread is freeze-framed and resumed!

2. Preemption

thread-cycle-preemption.cc is the same program as problem 1, but using preemptive scheduling - meaning that every 0.5 seconds, it automatically yields the current thread to run the next one every time the timer fires, instead of the threads manually calling yield. The code has been updated so that all threads print forever, and are switched between whenever the timer fires. The main thread now does the following:

// Fire the timer every 500,000 microseconds to context switch
timer_init(500000, timer_interrupt_handler);

while (true) {
    cout << "Hello, I am the main thread" << endl;
}

The other threads now do the following:

void thread_run() {
    intr_enable(true);
    while (true) {
        cout << "Hello, I am thread " << current->name << endl;
    }
}

And the interrupt handler just calls yield:

void timer_interrupt_handler() {
    yield();
}

All other code is the same as from problem 1. Compile and run the program, and trace through the code to answer the following questions:

Q6: When the program switches back to executing the main thread the first time, where does it resume?

The timer implementation we provide disables interrupts before calling your handler, and re-enables them after. You can imagine that the code within the timer that calls your handler looks something like the following:

intr_enable(false);
timer_handler();
intr_enable(true);

Q7: Why is it important that interrupts be disabled when the handler is run?

Q8: The program calls intr_enable(true) at the start of the other thread functions to re-enable interrupts. Why is that needed? What happens if that line is removed? Why?