Solutions

1. Thread Cycle

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

A1: Here’s a step-by-step of what context_switch actually does: first, it pushes all registers that need to be saved onto call stack of the thread being taken off of the CPU. Next, it saves the stack pointer in a location that’s easily recovered when it’s this thread’s turn to run once again. After that, it sets the stack pointer to the value saved on some other thread’s stack (itself initialized by a previous call to context_switch or when that thread was initialized). Finally, it then pops all saved registers from the new thread’s stack, and then returns to execute the previously saved instruction pointer.

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?

A2: Besides the main thread, thread two is the first to run, and first to print.

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

A3: It resumes in yield right after the context switch that switched away from the main thread to thread two. It then returns from yield and goes back to main where it prints the next line.

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?

A4: The context_switch function assumes that any thread we switch to was previously freeze-framed; because when it switches stack frames, it immediately proceeds to pop the saved registers off that stack and execute the ret instruction to return to executing the function that called context_switch. This is fine if we are switching back to a thread we previously context-switched away from (since that thread presumably previously called context_switch and saved those registers on the stack), but for a new thread there are no saved registers nor function to return to. Therefore, we must "fake" them so that context_switch runs properly; specifically, we put fake saved registers and a return address that, when ret runs, will take us "back" to the specified function.

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!

A5: Here's a walkthrough of the program:

The main function builds a circular list of threads — the main thread and two others. The main thread is linked to thread #2, which itself is linked to thread #1, which itself links back around to the main one. This circular ordering certainly impacts the order threads get processing time as a result of voluntary context switches.
The main thread executes yield(), which updates the current thread to be thread #2, prints a message about what switch is being performed, and then context switches away from the main thread to begin executing thread #2’s thread_run. That explains the "running thread two for first time." you see.
Thread #2’s call to yield() eventually yields to thread #1 in the same way the main thread just yielded to thread #2. That explains why you see "running thread one for first time." in the output where you do.
Thread #1 calls yield(), which context switches back to the main thread to pick up where it left off. The main thread returns from its yield() and prints "Cool, I'm back in main()!". And that marks the halfway point of the entire program.
The second half is more of the same and allows each of the thread routines to continue. After a second round of context switches, the initial thread returns from main, and that prompts the entire process to exit. Phew!

2. Preemption

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

A6: It resumes in yield right after the context switch that switched away from the main thread to thread two. It then returns from yield and goes back to timer_interrupt_handler, which then returns to main (at which point interrupts are re-enabled).

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

A7: The timer interrupt handler—literally called timer_interrupt_handler here—is invoked with interrupts disabled. In general, interrupt handlers need to be invoked with interrupts being disabled so it itself isn’t interrupted. That would expose the system to a scenario when a chain reaction of interrupts prompt an unbounded number of interrupt handlers to be invoked before any one of them finishes.

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?

A8: The timer handler is invoked with interrupts disabled. However, as a result, the very first time the main thread context switches into thread #2, the thread_run routine is called with interrupts disabled, thereby preventing that call to thread_run from being interrupted unless it explicitly re-enabled interrupts. If that line is removed, the initial thread would run for about 500,000 microseconds and then be preemptively yielded to thread #2 by a timer interrupt, at which point thread #2 would be uninterruptible—what’s to stop it?-and run forever.

Checkoff Questions

Questions are pulled from questions above - see answers above for more information!