Department of Computer and Information Science (IDA)

NACHOS Laboratory Assignment 1: Threads and Synchronization

Overview

This assignment covers:

• Primitives for synchronization (semaphores, locks and conditions).
• A first simple datatype using synchronization (a bounded buffer).
• A first introduction to threads and scheduling in NACHOS.

NACHOS uses three synchronization primitives; semaphores, locks and conditions. The semaphore is the most basic primitive and you find it already implemented in NACHOS. Completing the other two primitives is part of this assignment. You should fully understand their function before you start implementing them.

The course book provides only little information about Locks and Conditions. However, Locks and Conditions together form the same functionality as monitors and you can find some information about that in the book. But you might want to look at the DIGITAL report: An Introduction to Programming with Threads (remark: The report uses the term "mutex" where NACHOS uses "lock").

To test your implementation of the primitives you will construct your own synchronized datatype - a bounded buffer. This gives you valuable insight into constructing such datatypes, which you will benefit from in the following labs. You will use primarily locks and conditions, the primitives you have implemented.

To run the test, you need to have more than one thread, so this is a good time to have a first look at the NACHOS thread and scheduling subsystem. Threads are not very hard to use in NACHOS, and the scheduling system is already implemented for you to use.

Preparation

• Examine the source code for the class Semaphore (in threads/synch.cc)
• Read and understand the code in threadtest.cc that starts up two threads.
• Read the code for the class SynchList (in threads/synchlist.cc)

Answer these questions before starting with the assignment:

1. Explain the difference between the primitives lock, semaphore and condition. Can one be implemented using the others? How?
2. Show how the condition primitive can be used in an example (you can use the bounded buffer example).
3. Why is there a while loop around the Wait statement in the part of the SynchList class shown below?
   
   void * SynchList::Remove()
   {
       void *item;
       lock->Acquire();                    // enforce mutual exclusion
       while (list->IsEmpty())
           listEmpty->Wait(lock);          // wait until list isn't empty
       item = list->Remove();
       ASSERT(item != NULL);
       lock->Release();
       return item;
   }

The NACHOS framework

NACHOS is a relatively complex simulator. It simulates three things:

• A simulation of the MIPS processor
• A simulation of hardware usually found in a system
• An OS, handling this computer system

For this assignment you don't have to deal with the full complexity of NACHOS, but rather test some of the subsystems of the NACHOS OS kernel (synchronization, threads and scheduling).

Also, you will not use the MIPS emulator, but rather have some threads running in the NACHOS OS kernel. Usually an OS would run on the processor of the system. This is however NOT the case in NACHOS, the OS kernel does NOT run on the emulated MIPS processor, but rather as "ordinary" code in the NACHOS program. This might be confusing at times, but this is because you want to use a debugger to see that your code works properly.

NACHOS has a scheduler in place, using a fixed-priority pseudo-preemptive scheme. The first thread on the run queue is run until the thread yields control voluntarily. Later on you will do real preemptive multitasking, but for now the multitasking thus will be non-preemptive (like Microsoft Windows 3.x). However, which thread is taken from the run queue can be randomized (see below).

Files

The working directory for this lab is the /code/threads directory.

The following files are the central files for this lab:

• main.cc
  Holds the main()-function, the first function to run on execution of nachos.
• threadtest.cc
  Test program for testing the thread synchronization you have implemented.
• synch.h, synch.cc
  Synchronization routines, some of which you are supposed to implement.
• boundedbuffer.h, boundedbuffer.cc
  This is a skeleton for your bounded buffer implementation.

Read the following files to understand how to work with threads and scheduling of threads:

• thread.h, thread.cc
  Data structures and methods for handling threads.
• scheduler.h, scheduler.cc
  Scheduler for the threads that keeps lists of threads to run, etc. Study the code and examine how threads can be controlled.

You can find an example of a data structure that uses synchronization:

• list.h, list.cc
  An implementation of a linked list (should be used in the methods in Lock and Condition).
• synchlist.h, synchlist.cc
  An implementation of lists, using locks and condition variables for synchronization.

The following files are central files of NACHOS in general, read them to understand how NACHOS works internally:

• system.h, system.cc
  Functions to start and to end NACHOS.
• switch.h, switch.s
  Assembler code for switching between threads.
• interrupt.h, interrupt.cc
  The interrupt handler.
• timer.h, timer.cc
  Simulates a clock, generating interrupts with a given interval.
• stats.h
  Gathers statistics.

Assignments in detail

• In threads/synch.cc are the classes Semaphore, Lock and Condition. The only one implemented is the Semaphore class. You will write the code for the other two classes for this assignment. These shall follow the MESA semantics.

Before you start, you should look at the semaphore class. You are free to use semaphores when implementing the lock and condition classes.

In threads/synch.h you shouldn't change any member function definitions, but you are free to add member variables to the classes.

• Write the class BoundedBuffer that is not included in the distribution. Define the following files: threads/boundedbuffer.h and implement the class in threads/boundedbuffer.cc

The files threads/synchlist.h and threads/synchlist.cc contain an example of this, implementing a synchronized list, using a lock and a condition if the list is empty. Remember that you must handle both, the case of an empty buffer and a full buffer.

• Test your implementation of the boundedbuffer with the multithreaded threadtest.cc program. See details below.
• Update the threads/Makefile by expanding the macros:
  HFILES = $(THREAD_H)
  CFILES = $(THREAD_C)
  C_OFILES = $(THREAD_O)
  by adding the bounded buffer header file, C-file, and object file as follows:
  HFILES = $(THREAD_H) boundedbuffer.h
  CFILES = $(THREAD_C) boundedbuffer.cc
  C_OFILES = $(THREAD_O) boundedbuffer.o
• Do not forget to run gmake depend before issuing gmake nachos

The code already contains an example of how to start up two threads, so read and understand this first.

Running and debugging

For instructions on compiling and running nachos, please have a look at NACHOS: Introduction and installation.

To test the synchronization primitives under more realistic conditions, NACHOS can be started with the command:

       nachos -rs 17

This will give the number 17 as a seed to the random generator, which will then switch between the threads more randomly. Giving the same number in two different executions of the program, will cause NACHOS to switch in the same places both times.

To see in detail what your threads do, you may also use the flag -d:

       nachos -rs 17 -d

For the following assignments it will be necessary to use a debugger. So take this lab assignment as a good opportunity to get familiar with the use of a debugger. The GNU debugger ("gdb") works fine with NACHOS. There is a graphical interface to the debugger called "ddd".

You execute it by:

       ddd ./nachos

The SWITCH function (switches between threads; part of the scheduling subsystem) is written in assembler. You don't have to understand it fully, it is sufficient to know what it does in general. Observe that when running NACHOS in a debugger, the SWITCH call will probably confuse the debugger.

Test program

A test program for testing your bounded buffer code (replace your threadtest.cc) : threadtest.cc. Uses

• BoundedBuffer::BoundedBuffer(int size)
• int BoundedBuffer::read()
• void BoundedBuffer::write(int value)

Helpful Information

Next Laboratory work

Laboratory Assignment 2