CS 134

Reading Code

We'll mostly be working with the same parts of the kernel we worked with in Homework 4. The main difference is that we'll be looking at the scheduler and timing facilities in more detail.

OS/161 Atomics Library

One thing added to the code for this round was an atomic operations library, <atomic.h>. This library provides a set of functions that can be used to perform atomic operations such as atomic_and_u32, which performs an atomic bitwise AND operation on a 32-bit unsigned integer. These functions are now used in thread.c to update a bitfield that tracks which CPUs are idle.

Retouring thread.c

In our help pages, there is A Tour of thread.c. Give it a read if you haven't already. It's a good overview of the thread.c file, which is where the scheduler lives. You should specifically look at the following functions:

  • thread_switch: Performs a context switch, moving the current thread to a new state and selecting a new thread to run.
  • thread_yield: Yields the CPU to another thread.
  • thread_make_runnable: Called by thread_fork, wchan_wakeone, and wchan_wakeall to make a thread runnable, as well as by thread_switch.

Multi-CPU Scheduling

In addition, the following functions are used for multi-CPU scheduling:

  • thread_consider_migration: Checks if threads should be migrated between CPUs for load balancing.
  • cpu_find_idle: Finds an idle CPU to run a thread on (newly added in this updated version of OS/161). This function is called from thread_make_runnable to determine if there is an idle CPU that can run a newly created or newly woken thread.

Cycle Accounting

Another change in this updated version of OS/161 is the addition of careful tracking of CPU cycles spent in user and kernel mode. The key function for this tracking is cpu_record_cycles in kern/arch/mips/thread/cpu.c, which is called from a few critical places in the kernel to allow the necessary accounting to be done.

Each struct thread now has two additional fields:

  • t_kcycles: The number of kernel cycles the thread has used.
  • t_ucycles: The number of user cycles the thread has used.

In addition, each struct cpu has one additional field:

  • c_cycles: The total number of cycles since boot

Each CPU maintains its own cycle count, but they should be very close to each other; when a CPU wakes from idle, it uses the system clock to reset its cycle count based on the current time.

clock.c, clock.h and the Timer Clock

OS/161 has access to two countdown timers. One is the on-chip MIPS timer, which is used to provide the interrupts used for scheduling (and also for the cycle counting described above). The other is the (LAMEbus) timer clock, which is used to provide the timerclock facility, which currently generates an interrupt every second and is used to provide the clocksleep function that allows a thread to sleep for a specified number of seconds.

The timerclock facility (now) provides a function timerclock_setinterval that allows the interval between timer interrupts to be set.

(When logged in, completion status appears here.)