CS161 Day 2 In-Class Exercise

After completing this exercise, you should be able to:

Configuring and Compiling OS/161

If you happened to not check the web site, then you probably have not installed the CS161 tools on your own VM. Please do so right now! You can find the instructions on the two web page: Setting up the Coures Appliance and Using Code.Seas.

At this point you've created the working copy of the os161 repository and it's time to configure and build your own operating system. We will do this in two parts. First we will configure and build user level utilties, and then we'll configure and build the actual kernel (operating system).

Fire up your virtual machine and cd into the top level of the os161 directory:

% cd cs161/os161
The configure script in this directory indicates where to place the things it builds. By default, the configure script will put the kernel and its support files in $HOME/cs161/root. Run ./configure --help to see the options available. Next, run configure with an option that tells you where to place your root directory:

% ./configure --ostree=$HOME/cs161/root

Now let's build and install the user level utilities. Note that we are not yet building the kernel; these are user-level programs that will run in our operating system. Also note that we are using BSD make (bmake) and not the usual Linux GNU make. Complicated build systems like OS/161's are easier to write in BSD make.

% bmake
% bmake install
Let's make sure this wasn't all black magic. Traditionally operating systems place the files and utilities they need directly on file systems that the operating system itself provides. As might be apparent, there is a bit of a startup problem there. While you will not be undertaking any file system development until assignment 4, OS/161 comes with an emulated filesystem that passes requests from OS/161 to the file system on the computer on which we're running our simulated hardware (System/161) and our operating system (OS/161). In this case, OS/161 can retrieve files that reside on your virtual machine. Thus, files in your installation root (again, $HOME/cs161/root by default) will be available in this manner from inside OS/161. After you've built and installed your user level utilities, look in $HOME/cs161/root and see what's there.

Now that you have some utilities built, let's build a kernel! The first thing you will need to do is configure the kernel. Kernel configuration files live in kern/conf, (from now on all path names will be relative to your os161 directory, which should be ~/cs161/os161). If you look in that directory, you will see one configuration file per assignment. These configuration files describe which device drivers to include and various other sundry options. When the config script is run on them, a corresponding directory under kern/compile is created. So for now, do:

% cd ~/cs161/os161/kern/conf
% ./config ASST1

This will create and populate the directory kern/compile/ASST1 in which you will be able to compile your kernel as configured by the ASST1 configuration file from kern/conf. Note that you should specify the complete pathname ./config when you configure OS/161. If you omit the ./, you may end up running the configuration command for the system on which you are building OS/161, and that is almost guaranteed to produce rather strange results!

So, last but not least: compile the kernel!

% cd ../compile/ASST1
% bmake depend
% bmake
% bmake install
You have now built your first OS/161 kernel and put it in the right place. Congratulations!

So, when you want to build a kernel, you have to do four things:

  1. Configure the kernel you want to build by running config on a config file in kern/conf. This creates a kernel build directory in ../compile with the name of the config file you used.
  2. Create dependencies for the kernel you wish to build (by running bmake depend in your kernel build dirctory.
  3. Build your kernel using bmake.
  4. Install your kernel using bmake install.


The astute observer might be wondering where, exactly, the computer is that you're supposed to be running this new operating system on. That is, after all, the point of an operating system, right?

The answer is that the computer is simulated. You will run your operating system on a virtual machine known as System/161, which simulates a MIPS-like hardware architecture. System/161 reads in a binary operating system kernel image and then takes responsibility for simulating what would happen if real hardware with a real processor were to try to run it.

Ultimately, you do not need to understand the details of System/161's design or operation; you need only understand how to use it. You can view the full guide to its use here.

Before you can run System/161, however, you need to provide it with a configuration file. A sample can be found here. Save this in your OS/161 installation root directory with the name sys161.conf.

To run your compiled kernel in System/161, type:

% cd ~/cs161/root
% sys161 kernel

You can play around with the current kernel, check out what commands it supports and simply experiment. You can't do anything bad, so just play with it for a minute!

Playing with Synchronization

Warming up

The video introduced you to several HW instructions that provide the building blocks for synchronization. The first one introduced was a test-and-set (TAS).

Question 1: Let's say that you had a TAS instruction with the following usage: TAS ret, dest that sets dest to 1 and places the original value of dest into ret. How would you rewrite the spinlock_data_testandset code to use that instruction? (You can use the variable names, x, y, and sd, instead of the asm syntax to describe this.)

While the Intel architecture has no instruction called TAS, it does have a similar instruction called xchg. It works as follows:

	xchg dest, src
Exchanges the values in dest and src atomically.

Question 2: How would you use xchg to act like a TAS?

Question 3: How would you use cmpxchg to implement TAS?

The video also introduced the LL/SC instructions and transactional memory.

Question 4: Discuss with your partners how a LL/SC is like a simple HW transaction

Do you really understand spinlocks?

The synchronization video introduced the os161 implementation of a spinlock. Although we provide it for you, the following exercise will ensure that you really understand how we build simple, low-level primitives from even simpler hardware instructions.

Question 5: The code in spinlock.h bridges between the C and assembly, but doesn't quite implement a full spinlock. How would you use the primitive spinlock_data_testandset to build a function that actually spins until you are successful in your attempt to acquire the lock?

Once you think you know how, go to the file kern/thread/spinlock.c and go to line 110 to see if you got it right.

You will notice a bunch of code that checks and manipulates hangman structures. You may safely ignore those for now. We have added a deadlock detector to os161 that will greatly simplify your debugging later in the course. The hangman structures are used to provide this service.

You will also notice calls to splraise and spllower (in spinlock_release). These are discussed in more detail in the Assignment 1 code walkthrough -- they are slightly more functional versions of turning interrupts on and off.

Question 6: Why do we turn interrupts off when we acquire a spinlock?

In addition to spinlocks, OS161 comes equipped with semaphores as well. Here is a bit of a scavenger hunt -- find the semaphore code! (Think about some of the directories we've already examined ... you should be able to deduce where the semaphore implementation lives!)

Question 7: Where does the semaphore code live?

Question 8: Where will your implementation of locks and condition variables go?

The video that accompanies Assignment 1 provides a code walkthrough of the semaphore (and wait channel) code.

From Spinlocks to Locks

Question 9: In assignment 1, we're going to ask you to implement locks. What functionality to locks provide that spinlocks do not?

As you build out OS161, synchronization will be a critical issue. Part of the challenge in designing data structures and algorithms lies in selecting the right synchronization primitive. Question 10: Given what you have learned so far, come up with some guidelines for when you will use spinlocks, locks (with or without condition variables), and semaphores in your kernel.

After you've made an honest attempt at all the questions, you can check your answers here.