Programming Assignment II

Due on Friday, April 5, 2019 @ 11pm

100 points

Objectives

Develop and implement synchronization primitives. Conceive of and implement unit tests for said primitives.

Introduction

In this assignment you will implement synchronization primitives for OS/161 and learn how to write tests for them. 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.

Write readable code!

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 you will be working in a group, it will be important for you to be able to read each other'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 earlier. Finally, clear, well-commented code makes your grader 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. 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."

Begin Your Assignment

You should have already built a kernel successfully. The following describes the configuration specific to this first project.

Configure OS/161 for ASST1

We have provided an example framework in which you can implement and test your solution for assignment one. This framework consists of driver code, found in kern/test and a menu item that you can use to execute the test from the OS/161 kernel boot menu. You have to configure your kernel before you can use this framework. The procedure is:

% cd kern/conf
% ./config ASST1

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

Building for ASST1

In ASST1, you run bmake from compile/ASST1.

% cd compile/ASST1
% bmake depend
% bmake
% bmake install

If you are told that the compile/ASST1 directory does not exist, make sure you ran config for ASST1.

Command Line Arguments to OS/161

Your solutions to ASST1 will be tested by running OS/161 with command line arguments that correspond to the menu options in the OS/161 boot menu. Please DO NOT change any existing menu option strings, since we will be using them to automate testing.

Concurrent Programming with OS/161

If your code is properly synchronized, the timing of context switches and the order in which threads run should not change the behavior of your solution. Of course, your threads may print messages in different orders, but you should be able to easily verify that they follow all of the constraints applied to them and that they do not deadlock.

Built-in thread tests

When you boot OS/161 you will see the options to run the thread tests (type ? at the menu for a list of commands). The thread test code uses the semaphore synchronization primitive. You should 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" at the prompt or tt1 on the kernel command line) 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.

Debugging concurrent programs

thread_yield() is automatically called for you at intervals that vary randomly. While this randomness is fairly close to reality, it 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 confident that your threads do what they are supposed to do, set the random device to autoseed. This should allow you to test your solutions under varying conditions and may expose scenarios that you had not anticipated.

Code Reading

To implement synchronization primitives, you will have to understand the OS/161 code and the operation of the threading system. It may also help you to look at the provided implementation of semaphores. It will help if you also understand exactly what the OS/161 scheduler does when it dispatches among threads.

The following questions will help orient you to the OS/161 thread system. Answer them and submit them with your assignment. Place the answers in a file called asst1.pdf or asst1.txt in a directory named:

~you/os161/submit/

It will be most helpful to answer the questions before you begin coding.

Questions (20 pts)

Thread Questions (10 pts)

What happens to a thread when it exits (i.e., calls thread_exit())? What about when it sleeps?
What function(s) handle(s) a context switch?
What does it mean for a thread to be in each of the possible thread states?
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?
What happens when a thread wakes up another thread? How does a sleeping thread get to run again?

Scheduler Questions (6 pts)

What function(s) choose(s) the next thread to run?
How does it (do they) pick the next thread?
What role does the hardware timer play in scheduling? What hardware independent function is called on a timer interrupt?

Synchronization Questions (4 pts)

Describe how wchan_sleep() and wchan_wakeone() are used to implement semaphores.
Why does the lock API in OS/161 provide lock_do_i_hold(), but not lock_get_holder()?

Synchronization Primitives

We know: you've been itching to get to the coding on these projects. Well, you've finally arrived!

Locks (30 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/thread/synch.c.

Condition Variables (25 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.

General Guidelines

You may NOT use semaphores for your lock and condition variable implementation; while it is possible to do that, it is likely to lead you astray. Instead, use the various operations defined on wchan.

Unit Testing (25 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. You should decide for yourself what sorts of things you think qualify as "atomic units of functionality" in the context of your lock and CV implementations, and make a case for their sufficiency in the comments of your unit tests.

Unit testing is a bit trickier in the presence of asynchrony, so take care to make sure your tests are reliable—that is, your unit tests should succeed if and only if your primitives are correct. Remember that you have thread routines like thread_yield() at your disposal.

Submitting Your Assignment

Students must submit a tar file named os161.<ProjectName>.<Firstname_LastName>.tgz For example, if your name is John Dow, the sumbission file should be os161.p1.John_Dow.tgz, where p1 means OS/161 project 1. The tar file must contain following directories: root, src, submit and tools. This is the same basic directory organization as in the distributed code except for the addition of the submit subdirectory. Do not use abbreviations. For example, if your name is Jonathan Dow, then use os161.p1.Jonathan_Dow.tgz rather than os161.p1.Jon_Dow.tgz

The submit directory must contain the following:

A project report on design and implementation.
Screen snapshot of the output.
Include diff between the original code and modified source.

Note thatFile diff can be generated in the following way and should be in the submit directory.

cd ~/os161
diff -rw -x "*.[^chsS]" ~cs4411gr/public/baseP1 src > p1.diff
enscript --pretty-print=diff --color=1 -fCourier8 -o diff.ps p1.diff
mv diff.ps p1.diff submit

Note also that you and the grader should be on the same page if you are using the same version of OS/161, sys16 and toolchains. The grader will use the latest versions as follows:

OS/161 -- v2.0.3
sys161 -- v2.0.8

Notes: Unit Testing

A few things to keep in mind for unit tests:

Tests should be runnable from the menu and should be located in a separate file named asst1_tests.c. This file is already in the code base you received in the kern/src/test/ directory.
A single command a1a is available from the menu. It is mapped to a function sst1_tests which is declared in asst1_tests.c. This shoud run all of the tests in your test suite (that is asst1_tests should call in turn each of the functions in your test suite).
Each test should be for an atomic unit of functionality.
You may wish to write your unit tests before implementing your code.
Please provide comments in your test suite (and your code in general) explaining what you are testing and how this particular test ensures that functionality.
Test names should be descriptive.
Tests should have error and success messages.
Do not share your code, however you can share what functionality you are testing for. We reserve the right to use other people test suite on your code and vice versa.

Click here to see how your program will be graded.

Use this page to learn OS/161 debugging.