Assignment 1

Assignment 1: Synchronisation

Due Date: 8am, Monday morning, 28th of April

Worth 40 marks (of the 100 available for the class mark component of the course)

The 10% bonus for one week early applies

The extra 5% bonus for a submitted, working assignment within 48 hours of release applies. This "48 hour" bonus expires on Tuesday at 11:59pm due to the weekend release.

See course intro for exact details.

Contents

Introduction

In this assignment you will solve a number of synchronisation and locking problems. You will also get experience with data structure and resource management issues.

Please complete the reading exercises for your week 5 tutorial.

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. Code that is understandable to others is a requirement for any real-world programmer, not to mention the fact that after enough time, you will be in the shoes of one of the others when attempting to understand what you wrote in the past. Finally, clear, concise, well-commented code makes it easier for the assignment marker to award you marks! (This is especially important if you can't get the assignment running. If you can't figure out what is going on, how do you expect us to).

There is no single right way to organise 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 to read other people's code, for example OS/161. 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:

Setting Up Assignment 1

Your group account

You will do Assignment 1 as part of a two-person group. If you are not yet in a group, post to the appropriate message board on the cs3231 forum to find a partner. You must nominate your partner, and he or she must nominate you, via the group nomination form (under "Administration" on the left-hand side).

You will be notified by email when your group is created. Check the group nomination page for your group number. A group account will have been created for you in /home/osprjXXX, where XXX is your three-digit group number. For example, if you are a member of group 103, your group account is /home/osprj103.

Set up your group account

For assignment 0, you used the Subversion (SVN) revision control system to keep track of changes and to produce a file that you could submit. For this assignment, you will also use SVN. However, you have to do some extra set-up because you will be collaborating with another person on the assignment.

Before you start, both you and your partner will need to modify your umask so you and your partner to share the assignment files (if you're interested, see man umask for details). Do this by modifying your .profile in your home directory. Change the umask command to be the following.

umask 007

Now, whenever you log in, your umask will be set appropriately. Either log out and log back in again now or run the command source .profile to ensure your umask is set.

Obtain the assignment sources

For this assignment, you will set up an SVN repository in your group account directory (/home/osprjXXX). You may remember the repo directory you created for assignment 0. For assignment 1, you will be creating this repository in your group account directory. Initialise this repository now (only one group member needs to do this): 

% cd /home/osprjXXX
% svnadmin create repo

Once again, this repository directory will be completely maintained for you by SVN. Now import the sources into your new repository in a similar way to assignment 0 (once again, only one group member should do this step):

% cd /home/cs3231/assigns
% svn import asst1/src file:///home/osprjXXX/repo/asst1/trunk -m "Initial import"

As in assignment 0, make an immediate branch of this import for easy reference when you generate your diff (only one group member should do this step):

% svn copy -m "Tag initial import" file:///home/osprjXXX/repo/asst1/trunk
file:///home/osprjXXX/repo/asst1/initial

You have now set up your repository. Both you and your partner should now check out a working copy:

% cd ~/cs3231
% svn checkout file:///home/osprjXXX/repo/asst1/trunk asst1-src

You are now ready to start the assignment.

Begin Your Assignment

Configure OS/161 for Assignment 1

Before proceeding further, configure your new sources. 

% 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 your solutions from the OS/161 kernel boot menu.

You have to reconfigure your kernel 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 make from compile/ASST0 . In ASST1, you run make from (you guessed it) compile/ASST1 . 
% cd ../compile/ASST1
% make depend
% make
% make install
If you are told that the compile/ASST1 directory does not exist, make sure you ran config for ASST1. Run the resulting kernel: 
% cd ~/cs3231/root
% sys161 kernel 
sys161: System/161 release 1.1, compiled Jul 28 2003 17:28:51

OS/161 base system version 1.08
Copyright (c) 2000, 2001, 2002, 2003
   President and Fellows of Harvard College.  All rights reserved.

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

Cpu is MIPS r2000/r3000
1876k physical memory available
Device probe...
lamebus0 (system main bus)
emu0 at lamebus0
ltrace0 at lamebus0
ltimer0 at lamebus0
hardclock on ltimer0 (10000 hz)
beep0 at ltimer0
rtclock0 at ltimer0
lrandom0 at lamebus0
random0 at lrandom0
lser0 at lamebus0
con0 at lser0
pseudorand0 (virtual)

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 (";").

"Physical" Memory

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 execute the tests in this assignment, you will need more than the 512 KB of memory configured into System/161 by default. We suggest that you allocate at least 2MB of RAM to System/161. This configuration option is passed to the busctl device with the ramsize parameter in your ~/cs3231/root/sys161.conf file. Make sure the busctl device line looks like the following: 

31 busctl ramsize=2097152
Note: 2097152 bytes is 2MB.

Concurrent Programming with OS/161

If your code is properly synchronised, the timing of context switches and the order in which threads run should not change the behaviour 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 booted OS/161 in ASST0, you may have seen the options to run the thread tests. The thread test code uses the semaphore synchronisation 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 mi_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. To reproduce your test cases, you additionally need to run your tests via command line args to sys161 as described above.

Tutorial Exercises

Please answer the following questions and bring them to your tutorial in week 5.

Code reading

To implement synchronisation primitives, you will have to understand the operation of the threading system in OS/161. It may also help you to look at the provided implementation of semaphores. When you are writing solution code for the synchronisation problems it will help if you also understand exactly what the OS/161 scheduler does when it dispatches among threads.

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. Describe how thread_sleep() and thread_wakeup() are used to implement semaphores. What is the purpose of the argument passed to thread_sleep() ?
10. Why does the lock API in OS/161 provide lock_do_i_hold() , but not lock_get_holder() ?

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.

Identify Deadlocks

11. 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.
12. 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

13. 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 Queues

14. The thread subsystem in OS/161 uses a queue structure to manage some of its state. This queue structure is not synchronised. Why not? Under what circumstances should you use a synchronised queue structure?

Describe (and give pseudocode for) a synchronised queue data structure based on the queue structure included in the OS/161 codebase. 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.

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.

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. It is worth 40 marks of the 100 available for the class mark component of the course.

Solving Synchronisation Problems

The following problems will give you the opportunity to write three fairly straightforward concurrent programs and get a more detailed 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). You are responsible for implementing the functions called.

Remember to specify a seed to use in the random number generator by editing your sys161.conf file, and run your tests using sys161 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.

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 .

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.

Your Job
Your job 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. 

% sys161 kernel "1a;q"
sys161: System/161 release 1.1, compiled Feb 24 2003 21:57:51

OS/161 base system version 1.08
Copyright (c) 2000, 2001, 2002, 2003
   President and Fellows of Harvard College.  All rights reserved.

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

Cpu is MIPS r2000/r3000
848k physical memory available
Device probe...
lamebus0 (system main bus)
emu0 at lamebus0
ltrace0 at lamebus0
ltimer0 at lamebus0
hardclock on ltimer0 (10000 hz)
beep0 at ltimer0
rtclock0 at ltimer0
lrandom0 at lamebus0
random0 at lrandom0
lser0 at lamebus0
con0 at lser0
pseudorand0 (virtual)

OS/161 kernel: 1a
Starting 10 adder threads
Adder threads performed 10000 adds
Adder 0 performed 1008 increments.
Adder 1 performed 1032 increments.
Adder 2 performed 998 increments.
Adder 3 performed 1017 increments.
Adder 4 performed 1012 increments.
Adder 5 performed 988 increments.
Adder 6 performed 971 increments.
Adder 7 performed 975 increments.
Adder 8 performed 1027 increments.
Adder 9 performed 972 increments.
The adders performed 10000 increments overall
Operation took 3.665222400 seconds
OS/161 kernel: q
Shutting down.
The system is halted.

Restaurant Synchronisation Problem

You're working your way through university and decide to take a job in a restaurant seating customers. The restaurant is next to the famous "tourist trap" monument, and the main clientele are tourist buses who are managed by the various tour operators. You start your first day and find complete chaos. Customers are not being seated, or being seated at the wrong tables, some customers are fighting over tables, requests for tables are getting lost, some customers are waiting forever for their table, while others seems to get all the service.

Being an operating system expert, you quickly realise that the restaurant's problems are related to concurrency issues between the requesting of tables by tour operators for their buses, and the allocation of tables. You volunteer your services to provide a solution to the restaurant's problems, reduce the chaos, and restore order.

The Basic Restaurant
To provide a solution, you must come to terms with the basic elements of the restaurant that you have to work with. The restaurant consists of a set of tables labelled 1 to N (where N is the maximum table number of the day). Some tables have better views than others, so the restaurant allows the tour operators to request the set of tables they would like for each of their bus loads of tourists. Each bus load requests their tables, are seated when the tables become available, eat, and leave. The basic elements are defined in kern/asst1/restaurant_driver.h. The actions of the tour operators are defined in kern/asst1/restaurant_driver.c. See the file for detailed comments. For each tour bus a tour operator manages, he: The function run_restaurant() is called via the menu in OS/161 (item 1b). run_restaurant() does the following:

Have a quick look through both restaurant_driver.c and restaurant_driver.h to reinforce your understanding of what is going on (well, at least what is expected to go on).

Your Job
Your job is to write the functions outlined in restaurant.c that perform most of the work. Each function is described in restaurant.c.

Generally, your solution must result in the following when run_restaurant() is called during testing.

You can modify restaurant_driver.c and restaurant_driver.h to test different scenarios (e.g vary the number of tour operators or tables requested), but your solution must not rely on any changes you make to the restaurant_driver.c file.

You will have to modify restaurant.c to implement your solution. However, your modifications have the constraint that they must still work with an original restaurant_driver.c.

For testing, we will replace restaurant_driver.c and .h with logically equivalent versions that may vary the numbers of participants, and the tables requested. We may also vary the timing of various functions. A correct solution will work for all variations we test. Sample output from a correct solution is included below. 

% sys161 kernel "1b;q"
sys161: System/161 release 1.12, compiled Mar  8 2005 21:30:24

OS/161 base system version 1.10
Copyright (c) 2000, 2001, 2002, 2003
   President and Fellows of Harvard College.  All rights reserved.

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

Cpu is MIPS r2000/r3000
1880k physical memory available
Device probe...
lamebus0 (system main bus)
emu0 at lamebus0
ltrace0 at lamebus0
ltimer0 at lamebus0
hardclock on ltimer0 (10000 hz)
beep0 at ltimer0
rtclock0 at ltimer0
lrandom0 at lamebus0
random0 at lrandom0
lser0 at lamebus0
con0 at lser0
pseudorand0 (virtual)

OS/161 kernel: 1b
Opening the restaurant
The tour operators are starting
OP 0 starting
OP 1 starting
OP 2 starting
OP 3 starting
Op 0 going home after seating 200 tables
OP 4 starting
Op 1 going home after seating 200 tables
Op 2 going home after seating 200 tables
Op 3 going home after seating 200 tables
Op 4 going home after seating 200 tables
The restaurant is closing
Table 1 reserved 1000 times
Table 2 reserved 0 times
Table 3 reserved 0 times
Table 4 reserved 0 times
Table 5 reserved 0 times
Table 6 reserved 0 times
Table 7 reserved 0 times
Table 8 reserved 0 times
Table 9 reserved 0 times
Table 10 reserved 0 times
Table 11 reserved 0 times
Table 12 reserved 0 times
Table 13 reserved 0 times
Table 14 reserved 0 times
Table 15 reserved 0 times
Table 16 reserved 0 times
Table 17 reserved 0 times
Table 18 reserved 0 times
Table 19 reserved 0 times
Table 20 reserved 0 times
Total reservations 1000
The restaurant is closed, bye!!!
Operation took 0.555521080 seconds
OS/161 kernel: q
Shutting down.
The system is halted.
Before Coding!!!!
You should have a very good idea of what your attempting to do before you start. Concurrency problems are very difficult to debug, so it's in your best interest that you convince yourself you have a correct solution before you start.

The following questions may help you develop your solution.

Try to frame the problem in terms of resources requiring concurrency control, and producer-consumer problems. A diagram may help you to understand the problem.

Bounded-buffer producer / consumer problem

Your final task in this assignment is to implement a solution to a standard producer / consumer problem. In the producer / consumer problem one or more producer threads put data into a fixed-sized buffer while one or more consumer threads process information from the same buffer.

The code in kern/asst1/producerconsumer_driver.c starts up a number of producer and consumer threads. The producer threads attempt to communicate with the consumer threads by calling the producer_produce() function with a data structure. In turn, the consumer threads attempt to receive information from the consumer threads by calling consumer_consume(). 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 [? for menu]: 1c
run_producerconsumer: starting up
Consumer started
Consumer started
Consumer started
Consumer started
Consumer started
*** Error! Consumer bored, exiting...
Producer started
Producer finished
Producer started
Waiting for producer threads to exit...
Producer finished
All producer threads have exited.
*** Error! Consumer bored, exiting...
*** Error! Consumer bored, exiting...
*** Error! Consumer bored, exiting...
*** Error! Consumer bored, exiting...
Operation took 0.637168200 seconds
OS/161 kernel [? for menu]:

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

OS/161 kernel [? for menu]: 1c
run_producerconsumer: starting up
Consumer started
Consumer started
Consumer started
Waiting for producer threads to exit...
Producer started
Consumer started
Producer started
Producer finished
Consumer started
Producer finished
All producer threads have exited.
Consumer finished normally
Consumer finished normally
Consumer finished normally
Consumer finished normally
Consumer finished normally
Operation took 0.232509280 seconds
OS/161 kernel [? for menu]:
The files:

How to implement your solution

You must implement a data structure representing a buffer capable of holding at least BUFFER_SIZE struct pc_data items. This means that calling producer_produce() BUFFER_SIZE times should not block (or overwrite existing items, of course), but calling producer_produce one more time should block, until data has been removed from the buffer using consumer_consume(). A simple way to implement this data structure is to use an array, 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.

Evaluating your solutions

Your solutions will be judged in terms of its correctness, conciseness, clarity, and performance.

Performance will be judged in at least the following areas.

Documenting your solutions

This is a compulsory component of this assignment. You must write a small design document identifying the basic issues in all three of the concurrency problems in this assignment, and then describe your solution to the problems you have identified. For example, detail which data structures are shared, and what code forms a critical section. The document must be plain ASCII text. We expect such a document to roughly 200 - 1000 words, i.e. clear and to the point.

The document will be used to guide our markers in their evaluation of your solution to the assignment. In the case of a poor results in the functional testing combined with a poor design document, we will base our assessment on these components alone. If you can't describe your own solution clearly, you can't expect us to reverse engineer the code to a poor and complex solution to the assignment.

Create your design document to the top of the source tree to OS/161 (~/cs3231/asst1-src), and include it in svn as follows. 

% cd ~/cs3231/asst1-src
% svn add design.txt

When you later commit your changes into your repository, your design doc will be included in the commit, and later in your submission.

Also, please word wrap you design doc if your have not already done so. You can use the unix fmt command to achieve this if your editor cannot.

Generating Your Assignment Submission

As with assignment 0, you again will be submitting a diff of your changes to the original tree.

You should first commit your changes back to the repository using the following command. Note: You will have to supply a comment on your changes. You also need to coordinate with your partner that the changes you have (or potentially both have) made are committed consistently by you and your partner, such that the repository contains the work you want from both partners. 

% cd ~/cs3231/asst1-src
% svn commit
If the above fails, you may need to run svn update to bring your source tree up to date with commits made by your partner. If you do this, you should double check and test your assignment prior to submission.

Once your solution is committed, generate a diff.

% svn diff file:///home/osprjXXX/repo/asst1/initial
file:///home/osprjXXX/repo/asst1/trunk >~/asst1.diff

Submitting Your Assignment

Now submit the diff as your assignment. 
% cd ~
% give cs3231 asst1 asst1.diff
You're now done.