Sections Wed Nov 08 to Fri Nov 10

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 different kinds of scheduling algorithms and compare their performance

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

In lecture, we saw different possible scheduling algorithms for deciding which thread gets to run next, and their different tradeoffs. Let's say we have the following threads with the following times until they block or terminate, and no other threads running on the system:

A (12ms)    B (18ms)    C (10ms)    D (24ms)

Q6: Which scheduling algorithm will finish task B first? Which algorithm finishes task B last?

1. FIFO
2. Round Robin with a time slice of 6ms
3. SRPT