IT-Programmet, Tema 1 i termin 4:

TTIT61 Processprogrammering och Operativ System

/Concurrent Programming and Operating Systems/

---

Nachos

Throughout all lab assignments in TTIT61 you will use an emulated operating system called Nachos (Not Another Completely Heuristic Operating System).

Instead of running immediately on top of hardware, like normal operating systems, Nachos runs as a single process in a real operating system. In our case, Nachos will be a simple program running on Solaris. Nachos does not manage the real hardware. Instead it emulates a MIPS processor (MIPS is an old processor). The "user programs" that Nachos runs are MIPS binaries. The instructions in the MIPS binaries are interpreted Nachos and executed on the emulated processor.

It is analogous to Java binary code and Java Virtual Machine.

Setup

You can download the code skelleton together with some documentation from here: nachos-3.4.tar.gz. Unpack the archive:
gzip -dc nachos-3.4.tar.gz | tar xf -

During this assignment, you will work in the directory nachos-3.4/code/threads. Change directory to nachos-3.4/code/threads, run gmake depend
gmake
and hopefully you obtain an executable called nachos

Give it a try:
./nachos

Lab description

The purpose of this lab is to give you an understanding of synchronisation mechanisms such as locks, semaphores, condition variables, and monitors.

Semaphores are already implemented. You will have to implement locks and condition variables. The corresponding code has to be written in synch.cc. Read the comments before the function bodies. Also, you may want to read the corresponding sections in the text book (7.4, 7.5.1, 7.7).

As a code writing methodology, I would recommend that you recompile each time you add a function or variable declaration to a header file, and after every 5-10 new lines of code that you add. I strongly discourage the method in which you write all your assignment and compile only once at the end. Even experienced programmers would get tens of errors in these cases.

Recompiling is done by invoking
gmake

Once you implemented the required functionality, you will have to test it. The test application consists of eight concurrent threads that compete for access on a buffer with a capacity of 20 integer elements. Five threads are producers, while three threads are consumers. Initially the buffer is empty.

The functionality of the producer is the following: If the buffer is not full, the producer appends an element (an arbitrary integer, could be given by the function random) to the buffer. Appending the element is done by calling the method put of the bounded buffer object. After the element is put, the producer repeats its operation. If the buffer is full, the producer blocks. After it unblocks, it repeats its operation.

The functionality of the consumer is the following: If the buffer is not empty, the consumer removes the last element in the buffer (which is also the freshest element in the buffer, the most recently produced). The removal is done by calling the method get of the bounded buffer object. After the element is gotten, the consumer repeats its operation. If the buffer is empty, the consumer blocks. After it unblocks, it repeats its operation.

A skelleton for this functionality is given in threadtest.cc. You will have to edit function ThreadTest in order to create the eight threads and start their concurrent execution. You will also have to write the main functions of the producer and consumer threads.

Only the skelletons of put and get methods of the bounded buffer class are implemented. You will have to implement them too. Get inspiration from synchlist.cc.

Running

You will run your program in two variants.

In the first variant, Nachos does not capture the time interrupt and does not preempt threads. Thus, we would have "co-operative multitasking", just that our threads do not co-operate. That means that they run until they are forced to stop (they block), they do not voluntarily relinquish the processor. (They block because of adversary conditions, i.e. the producer blocks because the buffer is full, the consumer blocks because the buffer is empty. Thus, if correctly implemented, your program should not deadlock. At least one thread must be running because the buffer cannot be both empty and full at the same time.) In the case of co-operative multitasking, the buffer occupancy should vary as follows: 0, 1, 2, ..., 19, 20, 19, 18, ..., 1, 0, 1, 2, ..., 19, 20, 19, 18, ...

The first variant is run by executing
./nachos

In the second variant, Nachos captures the time interrupt and preempts the running threads whenever a random time interrupt arrives. Thus, we would have "preemptive multitasking". In this case, the buffer occupancy does not necessarily vary anymore from empty to full, then to back to empty, and so on, but rather oscillates somewhere in between.

The second variant is run by executing
./nachos -rs an_integer_number
rs stands for "random seed", and the integer number given after rs is the random seed. Different random seeds result in different random intervals between successive time interrupts. Consequently, we get different occupancy variation patterns.

Lab 1: Timers, Threads, Interrupts and Synchronization

Goal

In this assignment you are supposed to get acquainted with, probably, the most important mechanisms of operating systems such as timers, threads, interrupts, and, last but not least, synchronization primitives. Proper functioning of any concurrent operating system is simply impossible without them.

Overview

This assignment covers:

• Basic interrupt management.
• A first introduction to threads switching.
• Primitives for synchronization (semaphores, locks and conditions).
• A first simple datatype using synchronization (a bounded buffer).

This lab intends to teach the basics of synchronization, starting from the thread concurrency which is achieved via thread switching triggered by the timer interrupt, through basic synchonization primitives, and, finally, finishing with patterns of thread synchronization.

In the first part you should implement timer_sleep function. Second part is devoted to synchronization.

Pintos uses three synchronization primitives: semaphores, locks and conditions. All of them are already implemented. You should fully understand how they work before you start using 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. You might want to look at the DIGITAL report: An Introduction to Programming with Threads (remark: The report uses the term "mutex" where Pintos 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.

Using synchronization primitives you have to implement BoundedBuffer that is a circular structure with three counters: head, tail, and count. Let X be a buffer size. Initially, all counters are set to 0. As the item is added to the buffer, counters head and count are incremented. As the item is removed from the buffer the counter tail is incremented but count is decremented. Once head or tail reach X, they have to be made equal to 0 (and can be further incremented). If tail == head and count == 0, it means that the buffer is empty. If tail == head and count == X, it means that the buffer is full.

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 Pintos thread and scheduling subsystem. Threads are not very hard to use in Pintos, and a simple scheduling system is already implemented for you to use.

Preparatory questions

Before you begin doing your lab assignment you have to answer on the following set of questions to ensure that you are ready to continue.

• What is "busy waiting"? Why should the programmer avoid busy waiting in a concurrent operating system?
• Explain difference between Yield and Sleep.
• What is the difference between locks and semaphores? (Hint: there are two main differences). What is the deadlock?
• What is the purpose of conditions? Explain how deadlock situations can be avoided with conditions.
• Explain the difference between Signal and Broadcast.

Assignments in detail

Part A: Optional

Task

Your task is to re-implement function timer_sleep() which is located in devices/timer.c. The purpose of this function is make a calling process delay for a given time (sleep). The current implementation uses "busy waiting" strategy: it is calling thread_yield and checking the current time in a loop until enough time has gone by. Obviously, this is not acceptable: processor time is a very valuable resource and must not be wasted in busy waiting.

Preparations

In this lab you will need to modify a set of functions in device/timer.c and use functions from threads/thread.[h|c]. Therefore, before actual implementation you should read and understand at least the source code in device/timer.c and threads/thread.[h|c]. A simple test contained in the file tests/threads/simplethreadtest.c can help you to understand how to create and use threads in Pintos.

Implementation suggestions

In this part of the lab, you need to re-implement timer_sleep(int64_t ticks). If the thread calls timer_sleep() then its execution is suspended for (at least) ticks ticks. In case there are no other running threads (that is, if the system is idle), then the thread should be awaken after exactly ticks ticks. You should not preempt other processes if there are any running after the time has passed by, but rather put our process into the ready-to-run queue and leave the decision when it should be executed to the scheduler.

Hint: Implement a queue for sleeping processes. You can use either original List from Pintos distribution (lib/kernel/list.[c|h]), simplified SList (lib/kernel/slist.[c|h]) or even write your own.

Note, that the argument to timer_sleep is provieded in ticks, not in milliseconds. The macro TIMER_FREQ defines how many ticks there are per second (defined in devices/timer.h).

In your implementation you may modify other functions or add your own code in timer.c and timer.h files. Note, that the functions similar to timer_sleep():

• timer_msleep()
• timer_usleep()
• timer_nsleep()

rely on timer_sleep(), therefore there is no need to modify them.

DO NOT re-program the (hardware) timer itself!

To test your implementation you may run gmake SIMULATOR=--qemu check from the threads/build directory. There is a number of tests:

• alarm-single
• alarm-multiple
• alarm-simultaneous
• alarm-zero
• alarm-negative

which will test timer_sleep() function in different ways. You may run (and debug if necessary) one test at a time, eg.:
pintos --qemu -- run alarm-simultaneous
Note, that these tests will also pass at the very beginning because the current implementation of timer_sleep() is correct, although it is using busy waiting.

Part B

Task

Your task is to write the code for BoundedBuffer data structure that is not included in the distribution (actually, the stub for the structure and the corresponding functions is provided in file threads/boundedbuffer.h and threads/boundedbuffer.c).

In a bounded buffer you must handle two conditions: the case of an empty buffer and a full buffer. If the buffer becomes empty, all the reading processes must wait until something is put into the buffer. If the buffer becomes full, all the writing processes must wait until some place is freed by reading processes.

Preparations

Before you start, you should look at the threads/synch.h and threads/synch.h files. There are three kinds of synchronization primitives which you will use in this and later labs:

• semaphore
• lock
• condition

The next step is to study throughfully an example how locks and conditions are used together. Let us consider a list structure SynchList, which does not allow reading in case of list being empty. Function Append() adds an item into the list and function Remove removes an item from the list. Their pseudocode is shown below:

void Append(SynchList list, Item item)
{
  LockAcquire(list->ListLock); // enforce mutual exclusive access to the list
  AddItemToList(list, item);         // add element to the list
  ConditionSignal(list->ConditionEmpty, list->ListLock);// wake up a waiter, if any
  LockRelease(list->ListLock);       // release the lock
}

Item Remove(SynchList list)
{
  LockAcquire(list->ListLock);         // enforce mutual exclusion
  while(IsEmpty(list)){
    ConditionWait(list->ConditionEmpty, list->ListLock);//wait until list not empty
  }
  item = GetItemFromList(list);    // takes an item from the list
  LockRelease(list->ListLock);         // release the lock
  return item;

}

The condition ConditionEmpty is needed to make a process, which tries to read from the empty list, wait until some other process writes something to the list. ListLock provides mutual exclusion such that only one process can access list at a time.

More implementation details you can find in the files synchlist.h and synchlist.c. These files contain implementation of SynchList, which is a wrapper around original List structure.

Implementation suggestions

Use as an internal data structure for BoundedBuffer a simple array. Create this array upon initialization of BoundedBuffer, passing a buffer size as an argument. Make sure that counters work as expected before implementation of synchronization (a piece of paper and a pencil should help when examining your source code).

Once you have implemented BoundedBuffer, you need to re-compile Pintos by typing gmake from threads directory. Probably, during compilation, you will get information about errors that you have introduced while implementing BoundedBuffer or synchronization primitives. Fix them.

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

Now you can run Pintos from threads/build directory.

Helpful Information

Code directories:	pintos/src/threads, pintos/src/devices
Textbook chapters:	Chapter 1.5.2: Timer Chapter 3.2: Process Scheduling Chapter 6.2: The Critical-Section Problem Chapter 6.5: Semaphores Chapter 6.6.1: The Bounded-Buffer Problem
Documentation:	Pintos documentation, and in particular: Some parts of Project 1 Synchronization Interrupt Handling

Next Laboratory work

Laboratory Assignment 2