CS 161: Operating Systems Spring 2016

Tuesday/Thursday 1:00-2:30

Pierce 301


Home Syllabus Assignments Resources Piazza

Assignment 1: An Introduction to OS/161 and Synchronization

Due Thursday, February 4, 2016 at 11:59 PM

Objectives

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

Introduction

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.

Begin Your Assignment

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.

Part 1. General Code Reading Questions (22 points)

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:


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

Now that you've perused the source tree, here are two last questions.

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.

Part 2. Synchronization

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

Synchronization Code Reading Questions (14 points)

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()?

Writing Readable Code (Nothing to turn in)

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:

Synchronization Primitives (40 points)

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!)

Submitting Your Assignment

By 11:59 PM on Thursday, 2/4/2016, you should push the following to your code.seas repo:

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.