Strategy for tackling Nachos projects

Here are some suggestions for getting started on the project. This reflects my style of programming, but I would recommend implementing project features one at a time and testing each feature first before moving on to the next. One example of this is part 1 of project 1 -- first, ignore condition variables for a moment and concentrate on implementing the Lock class just by itself. Don't let how CVs work confuse you about Locks. I would implement Acquire and Release, and then write a couple of test programs to test basics of the Lock: have one thread acquire the lock, force a context switch with Yield, have another thread try to acquire the lock to make sure it sleeps, etc.

One you finish the Lock and finish testing the Lock, then move on to CVs, etc. And with Join, I would first implement the case where Join is called on a thread that still exists (the easier case), and then write a test program to make sure that it works as expected. And then I would implement the part of Join where Join is called on a thread that has already finished. And so on. It may seem like it would take longer to make progress, but in the long run it is faster because you don't have to debug lots of code at one time.

Locks

We need to implement its two operations, Acquire and Release. We know that (1) we need to make them atomic, and (2) they are going to block threads. So what we will do is look at the implementation of the Semaphore class to see how it does these things.

Implementing the methods

Let's start with Acquire. We need to make Acquire atomic. If we look at the implementation of synch.cc:Semaphore::P(), we see that it disables interrupts for atomicity. So we will do the same for Lock::Acquire. P() has to worry about keeping track of a counter before it blocks, but for the Lock we don't. All we need to do is check whether some other thread holds the Lock and block if so.

So pseudo code for Lock::Acquire is going to look something like:

Lock::Acquire()
{
  disable interrupts;

  while (the lock is held) {
     put this thread (the current thread) on the wait Q for the lock;
     block this thread (make the current thread go to sleep);
  }

  do some bookkeeping;

  enable interrupts;
}

Each of these actions is implemented in Semaphore::P(), so you should be able to look at the code for Semaphore::P() and do essentially the same thing.

We can do the same thing for Lock::Release:

Lock::Release()
{
  disable interrupts;

  remove a blocked thread from the Q, if there is one;
  unblock the removed thread;

  do some bookkeeping;

  enable interrupts;
}

Again, each of these operations is used in the implementation of Semaphore::V(), so we can essentially just copy them into the implementation of Lock::Release().

NOTE: I did not check for error conditions in this pseudo code, but you will want to in your project solutions.

Compiling

We are going to put the code for Lock::Acquire and Lock::Release in synch.cc. So we put our code there where the skeleton functions are defined. Now we need to recompile Nachos. To do this, all we need to do is rerun "gmake" in the threads directory.

Testing

Ok, now we have an implementations of the Lock class and we compiled it, removing all compilation errors.

So how do we test it? This is where threadtest.cc comes in. If we look in threadtest.cc, we see the function ThreadTest(). We know that ThreadTest() is called from main() in main.cc. So what we will do is implement a new function in threadtest.cc, call it LockTest(), and change the ThreadTest function in threadtest.cc to invoke that function.

Here is a modified version of threadtest.cc that does this. Note that, in this test, two threads are created, the first thread runs, acquires the lock, yields to the second thread, which runs, tries to acquire the lock but blocks, gives up the CPU to the first thread, and the first thread continues, etc. This behavior is highlighted by the output below.

You can use the command line argument "-q" to invoke different test functions you have implemented in threadtest.cc. To invoke LockTest, do the following:

% ./nachos -q 2
L1:0
L1:1
L2:0
L1:2
L1:3
L2:1
L2:2
L2:3
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!

Ticks: total 110, idle 0, system 110, user 0
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

Cleaning up...

We used printf's to see how the threads were executing. We can also use Nachos' debug facility to trace context switches and threads moving around on queues. Try running the following:

% ./nachos -d t -q 2

Ok, we've written an implementation of the Lock class and written one test program for it. Now you should implement other test programs for Lock, in particular test programs that test various kinds of error conditions. Once you're confident that your Lock class works, you can move on to implementing the Condition class. Go about implementing Condition in the same way. Write down its pseudo code, look at the implementation of Semaphore and Lock to see how each step should be implemented in Nachos, compile, and then write test cases that validates its implementation. Implement and test one behavior at a time so that you do not try to juggle too much.



jwanderson@cs.ucsd.edu