CS 134

Written Component

To implement synchronization primitives in OS/161, you will need to understand what locks and condition variables are and how they are used. These topics are covered in

You also need to understand the operation of the threading system in OS/161. There are some help pages that you can refer to for more information:

These pages will help orient you, but there's no substitute for actually browsing the code to see what really happens.

Other Ways to Explore: The Built-In Thread Tests

When you booted OS/161, you may have seen the options to run the thread tests.

Thread test 1 (tt1 at the prompt or tt1 on the kernel command line) prints the numbers 0 through 7 each time that each thread loops. Thread test 2 (tt2) only prints when each thread starts and exits. tt2 is intended to show that the scheduler doesn't cause starvation—the threads should all start together, spin for a while, and then end together.

The thread-test code uses the semaphore-synchronization primitive, so it won't use the locks and condition variables you'll be implementing. You can trace the execution of one of these thread tests in GDB to see how key functions are called and what exactly happens in a context switch.

A copy of these questions is provided in the handin/written.md file in your repository. Put your answers in that file.

Scheduler Questions

  1. HZ times per second, the hardware timer generates an interrupt. What part of the hardware generates this interrupt and how is it set up? (Hint: Look at kern/arch/sys161/dev/lamebus_machdep.c.)
  2. These frequent timer interrupts end up calling a function in kern/thread/clock.c. What is that function called? And what does it do?
  3. Schedulers need a “run queue” to keep track of the threads that are ready to run. Does OS/161 have one run queue or multiple run queues? Where?
  4. What function is responsible for choosing the next thread to run? How does that function pick the next thread?

Thread Questions

  1. How is a new thread created in OS/161? What steps are involved in setting up its initial state?
  2. What happens to a thread when it exits (i.e., calls thread_exit())? What about when it sleeps?
  3. What function(s) handle(s) a context switch?
  4. How many thread states are there? What are they?
  5. What does it mean to turn interrupts off? How is this accomplished? Why is it important to turn off interrupts in the thread subsystem code?
  6. What happens when a thread wakes up another thread? How does a sleeping thread get to run again?

Synchronization Questions

  1. Briefly describe how wchan_sleep() and wchan_wakeone() are used to implement semaphores.
  2. Why does the lock API in OS/161 provide lock_do_i_hold(), but not lock_get_holder()?
  3. How does the implementation of wchan ensure that a thread never misses a wakeup signal: that another thread cannot attempt to awaken the first thread just as it is preparing to sleep, but before it is actually placed into the sleep queue?

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)