CS 161: Operating Systems (Spring 2017)

Tuesday/Thursday 1:00pm-2:30pm

Pierce 301

James Mickens

Assignment 1: An Introduction to OS/161 and Synchronization

Due Thursday, February 2, 2017 at 5:00 PM

By the time you complete this assignment and the related in-class work, you should be able to:

• Discover important design aspects of OS/161 by examining its code base
• Use GDB to manipulate OS/161
• Understand how OS/161 implements semaphores
• Develop and implement synchronization primitives
• Conceive of and implement unit tests for said primitives
• Be able to select the appropriate primitive(s) for a given specification
• Use synchronization primitives appropriately to solve synchronization problems.

The purpose of this assignment is to introduce you to the code you will be using throughout the rest of the course. You have already completed significant portions of this assignment in class and in your web work -- setting up your virtual machine, cloning the code repository, learning how to configure and build kernels -- these are all different aspects of becoming familiar with the system you'll be using.

In this assignment you will also implement synchronization primitives for OS/161 and learn how to write tests for them. Once you have completed the written and programming exercises, you should have a fairly solid grasp of the pitfalls of concurrent programming and, more importantly, how to avoid those pitfalls in the code you will write later this semester.

To complete this assignment you'll need to become familiar with the OS/161 thread code. The thread system provides interrupts, control functions, and semaphores. You will implement locks and condition variables.

For this assignment, you will hand in an individual problem set. You may speak to other students about the probems, but you may communicate only in a spoken language, not in C or any other programming language. You may not search the web for solutions. All the work you turn in should be your own.

First, "tag" your Git repository. The purpose of tagging your repository is to make sure that you have something against which to compare your final tree.

Make sure that you do not have any uncommitted updates in your repo. Now, tag your repository as shown here:

  % git tag asst1-start

Now, push that new tag:

  % git push origin master --tags

Configure OS/161 for ASST1

We have provided an example framework in which you can implement and test your solutions for ASST1. This framework consists of driver code, found in kern/synchprobs, and menu items that you can use to execute tests from the OS/161 kernel boot menu. You have to reconfigure your kernel before you can use this framework:

  % cd kern/conf
  % ./config ASST1

You should now see an ASST1 directory in the compile directory.

OS/161 is a simplified skeleton of a modern operating system. It comes with a configurable build system, code for some useful user-level utilities that can be run from within OS/161, and of course code for the operating system itself. To complete the assignments of this course, you will need to get your hands deep in the guts of the OS/161 codebase, and the sooner you become familiar with it, the better. To that end, you should look through the files and begin to internalize how the code is structured, what goes where, and how things work. This applies both to the build system and the codebase itself.

To guide you in this process please write up and hand in answers to the questions found below in this section. Put them in a text file asst1-answers.txt in the submit/ subdirectory of your OS/161 repository.

The questions are designed to encourage code exploration. (We've tried to avoid questions that can be answered simply using grep.) The goal is to help you understand key parts of the system. That said, you are not yet expected to understand everything you see; that's what the rest of the course is for. But you should get the "gist," and your answers should reflect that. Please be as detailed as possible, giving function names and full pathnames in the source tree where appropriate. You don't need to explain what every last line of a function does, but your answers should be conceptually complete. Note that some questions may require longer answers than others.

Note: in these questions, and throughout the course of the semester, we will refer to the terms "trap", "interrupt", "exception", and "system call". Although these terms might take on different meanings in different classes, in CS 161, they mean the following:

• We use "trap" as a generic term of transferring control into the kernel.
• We use "exception" for events that are synchronous with respect to user processes and cause a trap into the kernel: these include things like divide-by-0 or NULL pointer dereference exceptions and the trap caused by the syscall instruction in MIPS.
• We use "interrupt" for asynchronous events that cause a trap into the kernel: this includes things like interrupts from the serial console hardware, the timer hardware, etc.
• We use "system call" for synchronous requests user processes make to request service from the OS: system calls are invoked using traps -- specifically using the syscall instruction on MIPS.

• Question 1 In section 3.1 of the text, you are introduced to the mechanisms used to transfer control between user processes and the operating system. Tell us where we can find the first line of OS/161 code that is executed when a trap occurs. Then tell us where control gets transferred to from that point (i.e. what function services the trap). Be sure to describe the control flow for each type of trap that may occur: system calls, VM faults, and hardware interrupts.
• Question 2 Making a system call, such as write, ultimately leads to a trap. Find where in OS/161 this trap is triggered.
• Question 3 Why do you suppose there are libc functions in the "common" part of the source tree (common/libc) as well as in userland/lib/libc?

Below is a brief overview of the organization of the source tree, and a description of what goes where.

• configure -- top-level configuration script; configures the OS/161 distribution and build system. It does not configure the operating system kernel, which is a slightly different kind of configuration.

  Question 4: Name two things that configure configures. What might invalidate that configuration and make you need/want to rerun it?

• Makefile -- top-level makefile; builds the OS/161 userland distribution, including all the provided utilities, but does not build the operating system kernel.

• common/ -- code used both by the kernel and user-level programs, mostly standard C library functions.

• kern/ -- the kernel source code.

  • kern/Makefile -- Once again, there is a Makefile. This Makefile installs header files but does not build anything.

  • kern/arch/ -- This is where architecture-specific code goes. By architecture-specific, we mean the code that differs depending on the CPU type or hardware platform on which you're running. There are two directories here: mips which contains code specific to the MIPS processor and sys161 which contains code specific to the System/161 simulator.

    • kern/arch/mips/conf/conf.arch -- This tells the kernel config script where to find the machine-specific, low-level files it needs (throughout kern/arch/mips/*).

    • kern/arch/mips/include/ -- This folder and its subdirectories include files for the machine-specific constants and functions.

      Question 5: What are some of the details which would make a function "machine dependent"? Why might it be important to maintain a separation between machine independent and machine dependent code, instead of just putting all of the code in one function?

    • kern/arch/mips/* -- The other directories contain source files for the machine-dependent code that the kernel needs to run. A lot of this code is in assembler and will seem very low level, but understanding how it all fits together will help you immensely on Assignment 2.

      Question 6: Where is the first line of code for constructing a trapframe? Describe at a high level what the code is doing here.

    • kern/arch/sys161/conf/conf.arch -- Similar to mips/conf/conf.arch.

    • kern/arch/sys161/include -- These files are include files for the System161-specific hardware, constants, and functions. machine-specific constants and functions.

  • kern/compile -- This is where you build kernels. See below.

    Question 7: For each scenario, state which of the following actions (a, b, c, d) you must take to compile your kernel (a scenario might require more than one action or none at all).

    1. Edit kern/conf/conf.kern
    2. Run kern/conf/config
    3. Run bmake depend
    4. Run bmake and bmake install.

    Scenario 1. You just finished assignment 1 and are ready to start assignment 2.

    Scenario 2. You added #include <cpu.h> at the top of kern/thread/synch.c.

    Scenario 3. You added a new file foo.c with a corresponding foo.h.

    Scenario 4. You added code in kern/thread/synch.c to implement locks and condition variables.

    Scenario 5. You edited sys161.conf to change the size of physical memory for System/161.

  • kern/dev -- This is where all the low level device management code is stored. Unless you are really interested, you can safely ignore this directory.

  • kern/fs -- This is where the actual file system implementations go. The subdirectory sfs contains a simple default file system. You will augment this file system as part of Assignment 4, so we'll ask you more questions about it then. The subdirectory semfs contains a special-purpose file system that provides semaphores to user-level programs. We may ask you more questions about this later on, after we discuss in class what semaphores are.

  • kern/include -- These are the include files that the kernel needs. The kern/include/kern directory contains include files that are visible not only to the operating system itself, but also to user-level programs. (Think about why it's named "kern" and where the files end up when installed.)

    Question 8: What does the preprocessor hackery in array.h accomplish (vs. just having the plain "struct array")? When might you use array.h?

  • kern/lib -- These are library routines used throughout the kernel, e.g., arrays, kernel printf, etc. Note: You can use these data structures as you implement your assignments in CS161. We strongly encourage you to look around and see what we've provided for you.

  • kern/main -- This is where the kernel is initialized and where the kernel main function is implemented.

  • kern/proc -- This is where process support lives. You will write most of the code that goes here during Assignment 2.

  • kern/synchprobs -- This is the directory that contains solution code to toy synchronization problems similar to the ones you completed in assignment 5 for CS 61 (if you took it this past fall). You are welcome to test your lock/CV implementation using these examples, but they don't count as unit tests.

  • kern/syscall -- This is where you will add code to create and manage user level processes. As it stands now, OS/161 runs only kernel threads; there is no support for user level code. In Assignment 2, you'll implement this support.

  • kern/thread -- Threads are the fundamental abstraction on which the kernel is built (do not forget to look back at header files in kern/include!)

  • kern/vfs -- The vfs is the "virtual file system." It is an abstraction for a file system and its existence in the kernel allows you to implement multiple file systems, while sharing as much code as possible. The VFS layer is the file-system independent layer. You will want to go look at vfs.h and vnode.h before looking at this directory.

  • kern/vm -- This directory is fairly vacant. In Assignment 3, you'll implement virtual memory and most of your code will go in here.

• man/ -- the OS/161 manual ("man pages") appear here. The man pages document (or specify) every program, every function in the C library, and every system call. You will use the system call man pages for reference in the course of assignment 2. The man pages are HTML and can be read with any browser.

• mk/ -- fragments of makefiles used to build the system.

• userland/ -- user-level libraries and program code

  • userland/bin/ -- all the utilities that are typically found in /bin, e.g., cat, cp, ls, etc. The things in bin are considered "fundamental" utilities that the system needs to run.

    Note: we need to have the source for these utilities and can't just use the the host system's standard utilities since they are not compiled for the correct architecture (MIPS) or operating system ABI (OS/161). (ABI stands for Application Binary Interface.)

  • userland/include/ -- these are the include files that you would typically find in /usr/include (in our case, a subset of them). These are user level include files; not kernel include files.

  • userland/lib/ -- library code lives here. We have only two libraries: libc, the C standard library, and hostcompat, which is for recompiling OS/161 programs for the host UNIX system. There is also a crt0 directory, which contains the startup code for user programs.

    Question 9: When a user program returns from its main function, what is done with the value it returns?

  • userland/sbin/ -- this is the source code for the utilities typically found in /sbin on a typical UNIX installation. In our case, there are some utilities that let you halt the machine, power it off and reboot it, among other things.

  • userland/testbin/ -- this is the source code for the test programs found in /testbin in the installed OS/161 tree. You will want to examine this directory closely and be aware of what's available here, as many of these test programs will be useful during the course of the semester.

Question 10: Imagine that you wanted to add a new system call. List all the places that you would need to modify/add code. Then review your answers to question 7 and note which of those actions you need to take in order to test the new system call.

Question 11: Refer to the document Using GDB and run gdb on your kernel. Experiment a bit and follow the execution from the start.S file through kmain and then to the code that executes some of the commands. Explain the control flow from start.S through to the menu. There is no need to trace functions called by functions that kmain calls, but you might need to look at those functions to be able to describe what the function kmain calls does at a high level. For example, if kmain called foo and foo called bar, you would have to list foo in your description of the control flow and describe what it does, but you do not need to list bar, although you might need to know what it does to be able to describe what foo does.

In the next part of the assignment, you will implement locks and condition variables. System/161 allows real parallelism by simulating a multicore processor. But even on a single core machine, OS/161 can provide the illusion of concurrency using timer interrupts and context switching. The kernel keeps track of threads via a thread object, defined in kern/include/thread.h, which stores information like the location of the stack, the saved value of registers, and the thread state (i.e. running, ready, sleeping, or zombie).

To help you get introduced to the guts of thread synchronization, we have provided this video that goes over Interrupt Protection Level (IPL), semaphores, and wait channels in OS/161. Please take some time to watch this video now before diving into the questions below and especially before you start to work on your implementation of locks and condition variables.

When you booted OS/161, you may have seen the options to run thread tests (type ? at the menu for a list of commands). The thread test code uses the semaphore synchronization primitive. First, trace the execution of one of these thread tests in GDB to see how the scheduler acts, how threads are created, and what exactly happens in a context switch. You should be able to step through a call to thread_switch() and see exactly where the current thread changes.

Thread test 1 (tt1) prints the numbers 0 through 7 each time each thread loops. Thread test 2 (tt2) prints only when each thread starts and exits. The latter is intended to show that the scheduler doesn't cause starvation—the threads should all start together, spin for awhile, and then end together.

Now, take a careful look at the code in kern/thread/thread.c, and answer the following questions.

Question 12: What happens to a thread when it sleeps?

Question 13: What function(s) handle(s) a context switch?

Question 14: 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?

Question 15: What happens when a thread wakes up another thread? How does a sleeping thread get to run again?

Question 16: What role does the hardware timer play in scheduling? What hardware independent function is called on a timer interrupt?

Question 17: Describe how wchan_sleep() and wchan_wakeone() are used to implement semaphores.

Question 18: Why does the lock API in OS/161 provide lock_do_i_hold(), but not lock_get_holder()?

In your programming assignments, you are expected to write well-documented, readable code. There are a variety of reasons to strive for clear and readable code. Since in the future you will be working in pairs, it will be important for you to be able to read your partner's code. Also, since you will be working on OS/161 for the entire semester, you may need to read and understand code that you wrote several months earlier. Finally, clear, well-commented code makes your TFs happy!

There is no single right way to organize and document your code; it is not our intent to dictate a particular coding style for this class. The best way to learn about writing readable code is simply to read a lot of code. Read the OS/161 code, or the source of code of some other freely available operating system. Read your partner's code, too (once you start coding together; that is, from ASST2 onwards). When you read someone else's code, note what you like and what you don't like. Pay close attention to the lines of comments which most clearly and efficiently explain what is going on. When you write code yourself, keep these observations in mind.

Here are some general tips for writing better code:

• Group related items together, whether they are variable declarations, lines of code, or functions.
• Use descriptive names for variables and procedures. Be consistent with this throughout the program.
• Comments should describe the programmer's intent, not the actual mechanics of the code. A comment which says "Find a free disk block" is much more informative than one that says "Find first non-zero element of array."

We know: you've been itching to get to the coding. Well, you've finally arrived! You can implement these synchronization primitives in terms of any other primitive(s), but you should put some thought into choosing the right implementation.

Locks (10 points)

Implement locks for OS/161. The interface for the lock struct is defined in kern/include/synch.h. Stub code is provided in kern/threads/synch.c.

Condition Variables (10 points)

Implement condition variables with Mesa semantics for OS/161. The interface for the cv struct is also defined in synch.h and stub code is provided in synch.c.

Unit Testing (10 + 10 points)

It's important to get in the habit of writing your own tests. The tests we provide, while ideally useful to you, do not necessarily ensure robust coverage and correctness of your code. After all, you know your code better than we do! It's also important to be able to communicate your testing needs (and other coding needs) to others. In this section, you will exercise all of these skills.

In order to verify the correctness of your synchronization primitives, we ask that you write some unit tests for your lock and CV implementations. Unit tests are small, modular pieces of test code intended to verify a single, atomic unit of functionality (hence the name).

First, in asst1-answers.txt (the file you used for code reading answers), enumerate 5 correctness or incorrectness criteria for each of the primitives you just implemented (i.e., locks and condition variables). These criteria should read somewhat like "A properly implemented lock will guarantee..." or "A properly implemented CV will prevent...". For example, an appropriately scoped criterion for struct semaphore would be "A properly implemented semaphore would always have a nonnegative number of holders."

Now, implement 5 unit tests, each of which tests one of the criteria you listed in the "Correctness Criteria" exercise above. Each unit test you write should be runnable from the OS/161 menu that appears when you run the system (the options that are displayed when the user types ? into the prompt). You should have at least one unit test per primitive.

Examples of unit tests for semaphores, along with what they test, are in kern/test/semunit.c. The example criterion above is tested in semu4.

Note: You might have noticed when tracing threads in GDB that to facilitate concurrency, thread_yield() is automatically called at intervals that vary randomly. This complicates the process of debugging your concurrent programs.

The random number generator used to vary the time between these thread_yield() calls uses the same seed as the random device in System/161. This means that you can reproduce a specific execution sequence by using a fixed seed for the random number generator. You can pass an explicit seed into random device by editing the "random" line in your sys161.conf file. For example, to set the seed to 1, you would edit the line to look like:

  28 random seed=1

We recommend that while you are writing and debugging your solutions you pick a seed and use it consistently. Once you are done with initial debugging/testing, remember to set the random device back to autoseed. This should allow you to test your solutions under varying conditions and may expose scenarios that you had not anticipated, which is central to effective testing.

Additional Testing (0 points, but can be very helpful!)

Normally you would implement unit tests for everything you do. However, unit testing synchronization is tricky. So, to help you test your synch primitives in the ~*real world*~, we provided the solutions to synchronization problems from last year, which rely on your primitives.

Source code and problem statements are located in the following:
kern/synchprobs/elves.c
kern/synchprobs/airballoon.c

To run, compile and start your kernel, and type:
sp1 to run elves
sp2 to run airballoon

Unfortunately, to check if your output is actually correct, you'll have to read and understand the problem statement in the source files, and then manually inspect the output to see if everything looks reasonable. (Hey, at least you don't have to do the problems anymore!)

By 5:00 PM on Thursday, 2/2/2017, you should push the following to your Github Classroom repo:

• The file asst1-answers.txt in the submit/ directory containing answers to the 18 questions and your 10 correctness/incorrectness criteria for the synch primitives.
• Completed implementations of locks and condition variables.
• 5 unit tests demonstrating that your primitives work properly.

See the handout How to Submit Assignments for preparing your assignment. Be sure to tag your repository to tell us that you have finished the assignment.

% git tag asst1-submit
% git push origin master --tags

You do not need to print out anything for this assignment.