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

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

A6: FCFS will finish task B soonest, because it runs tasks in order until completion (it will finish after 30ms). Round Robin will finish task B last, as it will only finish it after 9 time slices (52ms, since C doesn't use all of its last time slice). Here's how each scheduling algorithm would run the threads:
FIFO: ABCD
Round Robin: ABCDABCDBDD (runs each task for at most 6ms)

Checkoff Questions

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