Assignment 1: Synchronisation

1. Due Dates and Mark Distribution

Due Date: 8am (08:00), Thu March 14th

Marks: Worth 30 marks (of the class mark component of the course)

The 10% bonus for 4 days early applies.


2. Introduction

In this assignment you will solve a number of synchronisation problems within the software environment of the OS/161 kernel. By the end of this assignment you will gain the skills required to write concurrent code within the OS/161 kernel, though the synchronisation problems themselves are only indirectly related to the services that OS/161 provides.

This assignment includes familiarisation exercises that will be discussed in your week 3 tutorial. Please prepare for it.


3. Setting Up Your Assignment

We assume after ASST0 that you now have some familiarity with setting up for OS/161 development. The following is a brief setup guide. If you need more detail, refer back to ASST0.

Obtain the ASST1 distribution with git

Clone the ASST1 source repository from gitlab.cse.unsw.edu.au.

% cd ~/cs3231
% git clone gitlab@gitlab.cse.unsw.EDU.AU:zXXXXXXX/19t1-comp3231-asst1.git asst1-src

Configure OS/161 for Assignment 1

Configure your new sources as follows.

% cd ~/cs3231/asst1-src
% ./configure

We have provided you with a framework to run your solutions for ASST1. This framework consists of driver code (found in kern/asst1) and menu items you can use to execute the code and your solutions from the OS/161 kernel boot menu.

You have to configure your kernel itself before you can use this framework. The procedure for configuring a kernel is the same as in ASST0, except you will use the ASST1 configuration file:

% cd ~/cs3231/asst1-src/kern/conf	
% ./config ASST1

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

Building for ASST1

When you built OS/161 for ASST0, you ran bmake in compile/ASST0. In ASST1, you run bmake from (you guessed it) 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.

Tip: Once you start modifying the OS/161 kernel, you can quickly rebuild and re-install with the following command sequence. It will install the kernel if the build succeeds.

% bmake && bmake install

Update sys161.conf

HEADS UP!!!! Make sure you do the following. Failing to do so will potentially lead to subtle problems that will be very difficult to diagnose.

In order to work with this assignment, you need a larger memory configuration for System/161. A pre-configured sys161 configuration is available here: sys161.conf.

The simplest way to install it is as follows:

% cd ~/cs3231/root
% wget http://cgi.cse.unsw.edu.au/~cs3231/19T1/assignments/asst1/sys161.conf -O sys161.conf

Run the kernel

Run the resulting kernel:
% cd ~/cs3231/root
% sys161 kernel
sys161: System/161 release 2.0.8, compiled Feb 19 2017 14:31:53

OS/161 base system version 2.0.3
(with locks&CVs solution)
Copyright (c) 2000, 2001-2005, 2008-2011, 2013, 2014
   President and Fellows of Harvard College.  All rights reserved.

Put-your-group-name-here's system version 0 (ASST1 #29)

16220k physical memory available
Device probe...
lamebus0 (system main bus)
emu0 at lamebus0
ltrace0 at lamebus0
ltimer0 at lamebus0
beep0 at ltimer0
rtclock0 at ltimer0
lrandom0 at lamebus0
random0 at lrandom0
lser0 at lamebus0
con0 at lser0

cpu0: MIPS/161 (System/161 2.x) features 0x0
OS/161 kernel [? for menu]:

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.

IMPORTANT: Please DO NOT change these menu option strings!

Here are some examples of using command line args to select OS/161 menu items:

sys161 kernel "at;bt;q"
This is the same as starting up with sys161 kernel, then running "at" at the menu prompt (invoking the array test), then when that finishes running "bt" (bitmap test), then quitting by typing "q".
sys161 kernel "q"
This is the simplest example. This will start the kernel up, then quit as soon as it's finished booting. Try it yourself with other menu commands. Remember that the commands must be separated by semicolons (";").

4. Concurrent Programming with OS/161

If your code is properly synchronised, the timing of context switches, the location of kprintf() calls, and the order in which threads run should not influence the correctness 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 the constraints required of them and that they do not deadlock.

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 the 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 start the kernel via command line arguments and 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.

To reproduce your test cases, you need to run your tests via the command line arguments to sys161 as described above, otherwise system behaviour will depend on your precise typing speed (and not be reproducible for debugging).


5. Tutorial Exercises

The main aim of the tutorial is to have you implement synchronised data structures using the supplied OS synchronisation primitives. The questions also aim to guide you through OS/161's implementation of threads and synchronisation primitives in the kernel itself for those interested in a deeper understanding of OS/161. A deeper understanding can be useful when debugging, but is not strictly required.

Be prepared to discuss the following questions in your tutorial.

Synchronisation Problems

The following problems are designed to familiarise you with some of the problems that arise in concurrent programming and help you learn to identify and solve them.

Critical sections

Q1 The following fragment of code is a single line of code. How might a race condition occur if it is executed concurrently by multiple threads? Can you give an example of how an incorrect result can be computed for x. How would you synchronise this code.

  x = x + 1;

Q2 The following function is called by multiple threads (potentially concurrently) in a multi-threaded program. Identify the critical section(s) that require(s) mutual exclusion. Describe the race condition or why no race condition exists. How would you synchronise the following code.

int i;

void foo()
{
    int j;

    /* random stuff*/

    i = i + 1;
    j = j + 1;

    /* more random stuff */
}

Q3 The following function is called by threads in a multi-thread program. Under what conditions does it need synchronisation or not.

void inc_mem(int *iptr)
{
    *iptr = *iptr + 1;
}

Coordinating activities

Q4 What synchronisation mechanism or approach might one take to have one thread wait for another thread to update some state?

Q5 A particular abstraction only allows a maximum of 10 threads to enter the "room" at any point in time. Further threads attempting to enter the room have to wait at the door for another thread to exit the room. How could one implement a synchronisation approach to enforce the above restriction?

Q6 Multiple threads are waiting for the same thing to happen (e.g. a disk block to arrive from disk). Write pseudo-code for a synchronising and waking the multiple threads waiting for the same event.

Identify Deadlocks

Q7 Here are code samples for two threads that use binary semaphores. Give a sequence of execution and context switches in which these two threads can deadlock.

Propose a change to one or both of them that makes deadlock impossible. What general principle do the original threads violate that causes them to deadlock?

semaphore *mutex, *data;
 
void me() {
	P(mutex);
	/* do something */
	
	P(data);
	/* do something else */
	
	V(mutex);
	
	/* clean up */
	V(data);
}
 
void you() {
	P(data)
	P(mutex);
	
	/* do something */
	
	V(data);
	V(mutex);
}

More Deadlock Identification

Q8 Here are two more threads. Can they deadlock? If so, give a concurrent execution in which they do and propose a change to one or both that makes them deadlock free.

lock *file1, *file2, *mutex;
 
void laurel() {
	lock_acquire(mutex);
	/* do something */
	
	lock_acquire(file1);
    	/* write to file 1 */
 
	lock_acquire(file2);
	/* write to file 2 */
 
	lock_release(file1);
	lock_release(mutex);
 
	/* do something */
	
	lock_acquire(file1);
 
	/* read from file 1 */
	/* write to file 2 */
 
	lock_release(file2);
	lock_release(file1);
}
 
void hardy() {
    	/* do stuff */
	
	lock_acquire(file1);
	/* read from file 1 */
 
	lock_acquire(file2);
	/* write to file 2 */
	
	lock_release(file1);
	lock_release(file2);
 
	lock_acquire(mutex);
	/* do something */
	lock_acquire(file1);
	/* write to file 1 */
	lock_release(file1);
	lock_release(mutex);
}

Synchronised Lists

Q9 Describe (and give pseudocode for) a synchronised linked list structure based on thread list code in the OS/161 codebase (kern/thread/threadlist.c). You may use semaphores, locks, and condition variables as you see fit. You must describe (a proof is not necessary) why your algorithm will not deadlock.

In a general sense, the interface to the synchronised list is as follows.

    init(list_t *);
    add_head(list_t *list, node_t *node);
    add_tail(list_t *list, node_t *node);
    remove_head(list_t *list, node_t **node);
    remove_tail(list_t *list, node_t **node);
    insert_after(node_t *in_list, node_t *new_node);
    insert_before(node_t *in_list, node_t *new_node);
    remove(node_t *in_list);
  

Make sure you clearly state your assumptions about the constraints on access to such a structure and how you ensure that these constraints are respected.

Consider a solution involving a lock per node in the list. The instructive cases are insert_after() and insert_before(), and remove()

The thread subsystem in OS/161 uses a linked list of threads to manage some of its state (kern/thread/threadlist.c). This structure is not synchronised. Why not?

Code reading

For those interested in gaining a deeper understanding of how synchronisation primitives are implemented, it is helpful to understand the operation of the threading system in OS/161. After which, walking through the implementation of the synchronisation primitives themselves should be relatively straightforward.

Thread Questions

1. What happens to a thread when it exits (i.e., calls thread_exit())? What about when it sleeps?
2. What function(s) handle(s) a context switch?
3. How many thread states are there? What are they?
4. 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?
5. What happens when a thread wakes up another thread? How does a sleeping thread get to run again?

Scheduler Questions

6. What function is responsible for choosing the next thread to run?
7. How does that function pick the next thread?
8. What role does the hardware timer play in scheduling? What hardware independent function is called on a timer interrupt?

Synchronisation Questions

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

6. Coding Assignment

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

This is the assessable component of this assignment.

The following problems will give you the opportunity to write some fairly straightforward concurrent systems and get a practical understanding of how to use concurrency mechanisms to solve problems. We have provided you with basic driver code that starts a predefined number of threads that execute a predefined activity (in the form of calling functions that you must implement or modify).

Note: In this assignment, you are restricted to the lock, semaphore, and condition variable primitives provided in OS/161. The use of primitives such as thread_yield, atomic ops, and the like are discouraged. Moreover, they usually result in a poor solution involving busy waiting.

Note: In some instances, the comments within the code also form part of the specification and give guidance as to what is required.

Check that you have specified a seed to use in the random number generator by examining your sys161.conf file, and run your tests using Sys/161 command line args. It is much easier to debug initial problems when the sequence of execution and context switches is reproducible.

When you configure your kernel for ASST1, the driver code and extra menu options for executing your solutions are automatically compiled in.

Part 1: Concurrent Mathematics Problem

For the first problem, we ask you to solve a very simple mutual exclusion problem. The code in kern/asst1/math.c counts from 0 to 10000 by starting several threads that increment a common counter.

You will notice that as supplied, the code operates incorrectly and produces results like 345 + 1 = 352. An incorrect run is shown below in red.

Once the count of 10000 is reached, each thread signals the main thread that it is finished and then exits. Once all adder() threads exit, the main (math()) thread cleans up and exits.

OS/161 kernel: 1a
Starting 10 adder threads
In thread 6, 777 + 1 == 782?
In thread 1, 1053 + 1 == 783?
In thread 5, 782 + 1 == 1073?
In thread 0, 1040 + 1 == 784?
In thread 8, 1443 + 1 == 1455?
In thread 4, 1511 + 1 == 1522?
In thread 9, 1562 + 1 == 1568?
In thread 2, 1657 + 1 == 1666?
In thread 7, 1665 + 1 == 1667?
In thread 6, 4341 + 1 == 4344?
In thread 3, 6499 + 1 == 6505?
In thread 1, 7877 + 1 == 7894?
In thread 5, 7893 + 1 == 7895?
In thread 0, 9783 + 1 == 9834?
Adder threads performed 10000 adds
Adder 0 performed 1924 increments.
Adder 1 performed 1403 increments.
Adder 2 performed 95 increments.
Adder 3 performed 4822 increments.
Adder 4 performed 658 increments.
Adder 5 performed 264 increments.
Adder 6 performed 219 increments.
Adder 7 performed 9 increments.
Adder 8 performed 590 increments.
Adder 9 performed 92 increments.
The adders performed 10076 increments overall (expected 10000)

Your Task

Your task is to modify math.c by placing synchronisation primitives appropriately such that incrementing the counter works correctly. The statistics printed should also be consistent with the overall count.

Note that the number of increments each thread performs is dependent on scheduling and hence will vary. However, the total should equal the final count.

To test your solution, use the "1a" menu choice. Sample output from a correct solution in included below.

OS/161 kernel: 1a
Starting 10 adder threads
Adder threads performed 10000 adds
Adder 0 performed 919 increments.
Adder 1 performed 1037 increments.
Adder 2 performed 867 increments.
Adder 3 performed 1087 increments.
Adder 4 performed 1059 increments.
Adder 5 performed 905 increments.
Adder 6 performed 1132 increments.
Adder 7 performed 997 increments.
Adder 8 performed 958 increments.
Adder 9 performed 1039 increments.
The adders performed 10000 increments overall

Part 2: Simple Deadlock

This task involves modifying a simple example such that the example no longer deadlocks and is able to finish. The example is in twolocks.c.

In the example, bill() and ben() are two threads that both need to hold two locks at various times to make progress: lock_a and lock_b. While holding both locks, bill() and ben() calls "holds_lockX" that just consumes some CPU. The way the current code is written, the code deadlocks and trigger's OS/161's deadlock detection code, as shown below.

OS/161 kernel: 1b
Locking frenzy starting up
Hi, I'm Bill
Hi, I'm Ben
hangman: Detected lock cycle!
hangman: in ben thread (0x80031ed8);
hangman: waiting for lock_a (0x80032d04), but:
   lockable lock_a (0x80032d04)
   held by actor bill thread (0x80031f58)
   waiting for lockable lock_b (0x80032cc4)
   held by actor ben thread (0x80031ed8)
panic: Deadlock.
sys161: trace: software-requested debugger stop
sys161: Waiting for debugger connection...

You task is to modify the existing code such that:

  1. The example runs to completion as shown below.
  2. The solution still involves the locks being held at the three different points in the code as indicated by the "holds_lockX" function calls.

OS/161 kernel: 1b
Locking frenzy starting up
Hi, I'm Bill
Hi, I'm Ben
Ben says 'bye'
Bill says 'bye'
Locking frenzy finished

Part 3: Bounded-buffer producer/consumer problem

Your next task in this assignment is to implement a solution to a producer/consumer problem. In this producer/consumer problem one or more producer threads allocate data structures and copy the pointers into a fixed-sized buffer, while one or more consumer threads retrieve those pointers and de-allocate the data structures.

The code in kern/asst1/producerconsumer_driver.c starts up a number of producer and consumer threads. The producer threads attempt to send pointers to the data structures to the consumer threads by calling the producer_send() function with a pointer to the data structure. In turn, the consumer threads attempt to receive pointers to the allocated data structure from the producer threads by calling consumer_receive(). Unfortunately, these functions are currently unimplemented. Your job is to implement them.

Here's what you will see before you have implemented any code:

OS/161 kernel: 1c
run_producerconsumer: starting up
Consumer started
panic: Assertion failed: item != NULL, at ../../asst1/producerconsumer_driver.c:108 (consumer_thread)

And here's what you will see with a (possibly partially) correct solution:

OS/161 kernel: 1c
run_producerconsumer: starting up
Consumer started
Waiting for producer threads to exit...
Producer started
Consumer started
Consumer started
Producer started
Consumer started
Consumer started
Producer finished
Producer finished
All producer threads have exited.
Consumer finished normally
Consumer finished normally
Consumer finished normally
Consumer finished normally
Consumer finished normally

The files:

How to implement your solution

You must implement a data structure representing a buffer capable of holding at least BUFFER_SIZE data_item_t pointers. This means that calling producer_send() BUFFER_SIZE times should not block (or overwrite existing items, of course), but calling producer_send one more time should block, until an item has been removed from the buffer using consumer_receive(). A simple way to implement this data structure is to use an array of pointers as provided, though you will of course have to use appropriate synchronisation primitives to ensure that concurrent access is handled safely.

Your data structure should function as a circular buffer with first-in, first-out semantics.

Part 4: Dining Philosophers

No OS course is complete without having to solve the dining philosopher's problem. Now is your chance!

System Details

The system consists of the following files:

The structure of the system follows the typical dining philosopher structure where each philosopher thread does the following in a loop that eventually finishes.

think();
take_forks(); 
eat();   
put_forks();  

The supplied code has the addition of a fork-use count that is incremented during each eat(). If you have correctly synchronised the problem, eat() should have mutually exclusive access to the count for the left and right fork, and thus the count should accurately reflect the number of times the fork has been used. The supplied code is not synchronised, thus count is inaccurate and varies to race conditions on updates, as shown below.

Starting 5 philosopher threads
Philosopher 3 started
Philosopher 0 started
Philosopher 1 started
Philosopher 2 started
Philosopher 4 started
Philosopher 3 finished
Philosopher 0 finished
Philosopher 1 finished
Philosopher 2 finished
Philosopher 4 finished
Fork 0 used 1940 times.
Fork 1 used 1893 times.
Fork 2 used 1866 times.
Fork 3 used 2000 times.
Fork 4 used 2000 times.

Your Task

You task is to synchronise the philosophers such that they have mutually exclusive access to their forks. You do this by implementing the functions in dining.c, including declaring any types for data structures that you need.

Better solutions allow multiple philosophers to eat in parallel when they don't share forks in common.

You can't assume the constants in dining_driver.h remain the same in our testing. You can assume there will be at least 2 philosophers configured in the system.

To test your solution, use sys161 kernel "1d;q". Sample output from a potential working solution is included below.

OS/161 kernel: 1d
Starting 5 philosopher threads
Philosopher 3 started
Philosopher 4 started
Philosopher 2 started
Philosopher 1 started
Philosopher 0 started
Philosopher 3 finished
Philosopher 2 finished
Philosopher 1 finished
Philosopher 4 finished
Philosopher 0 finished
Fork 0 used 2000 times.
Fork 1 used 2000 times.
Fork 2 used 2000 times.
Fork 3 used 2000 times.
Fork 4 used 2000 times.

7. Submitting

The submission instructions are available on the Wiki. Like ASST0, you will be submitting the git repository bundle via CSE's give system. For ASST1, the submission system will do a test build and run a simple test to confirm your bundle at least compiles.

Warning! Don't ignore the submission system! If your submission fails the submission process, you may not receive any marks.

To submit your bundle:

% cd ~
% give cs3231 asst1 asst1.bundle

You're now done.

Even though the generated bundle should represent all the changes you have made to the supplied code, occasionally students do something "ingenious". So always keep your git repository so that you may recover your assignment should something go wrong.