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

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:

• Split large functions. If a function spans multiple pages, it is probably too long.
• Group related items together, whether they are variable declarations, lines of code, or functions.
• Use descriptive names for variables and procedures. Be consistent with this throughout the program.
• Comments should describe the programmer's intent, not the actual mechanics of the code. A comment which says "Find a free disk block" is much more informative than one that says "Find first non-zero element of array."

Setting Up Assignment 1

Some more practice with CVS

At the end of the previous assignment, you would have committed the changes you made to the CVS repository and tagged as asst0-final.

You may have made some changes to the sources since then. To check this you can use the following command

% cd ~/cs3231/asst0-src
% cvs -q -n update
M kern/main/main.c
%

A short note on the arguments to cvs:

• -q means "be quiet". Don't show the directories cvs traverses while it works.
• -n means "no action". It means go through the motions of performing the command, but don't actually change anything. -n is a great way to test something you might want to do, but that you are not sure of the consequences of.
• update requests cvs to update your version of the sources with the latest version in your repository.

Note that in our example, we have modified (M) the kern/main/main.c file since the last commit. The output above might be different for you. It may be empty, in which case you have not made any changes since asst0 finished.

If you have made changes, decide whether you wish to keep them to play around with later, or whether you simply wish to throw them away. If you wish to keep them, you should commit your changes back to the repository using cvs commit.

Now remove your asst0-src tree to prepare for this assignment (yes really).

% cd ~/cs3231
% rm -rf asst0-src

We assume that the remainder of the ~/cs3231 directory is in place from the previous assignment, and that your umask, PATH and CVSROOT are still set appropriately.

Obtaining and setting up ASST1 in CVS

• Check your umask is still set appropriately.

  % umask
  0007
  % 
  

  If not, you have done something wrong with your umask setup and need to fix it.
• Check your CVSROOT environment variable as below.

  % echo $CVSROOT
  /home/osprj000/cvsroot
  % 
  

  If your CVSROOT is not an appropriately modified version of the above, then you will need to fix it.
• Now import the OS/161 sources into your repository as follows

  % cd /home/cs3231/assigns/asst1/src
  % cvs import -m "Initial import of asst1 OS/161 sources" asst1-src os161 asst1-base
  

• We'll assume from your cs3231 directory is intact from the previous assignment. Change to your directory.

  % cd ~/cs3231
  

• Now checkout a copy of the os161 sources to work on from your shared repository.

  % cvs checkout asst1-src
  

• You should now have a asst1-src directory to work on.

Configure OS/161 for Assignment 1

Before proceeding further, configure your new sources.

% cd ~/cs3231/asst1-src
% ./configure --ostree=~/cs3231/root

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

Building for ASST1

% cd ../compile/ASST1
% make depend
% make
% make install

% 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

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"

sys161 kernel "q"

"Physical" Memory

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 

Concurrent Programming with OS/161

Built-in thread tests

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

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 

Tutorial Exercises

Code reading

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

Synchronisation Questions

Synchronisation Problems

Identify Deadlocks

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

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

This is the assessable component of this assignment. It is worth 30 marks of the 100 available for the class mark component of the course.

Solving Synchronisation 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

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.

Paint Shop Synchronisation Problem

Being an operating system expert, you quickly realise that the shop's problems are related to concurrency issues between the customers and shop staff. You volunteer your services to provide a solution to the shop's problems, reduce the chaos, and restore order to the store.

The Basic Paint Shop

• Customers arrive with their paint can, write their requested colour on the can in terms of tints, submit their can as an order to the paint shop staff and wait.

  Eventually their can returns with the requested contents (exactly as requested), they paint until the can is empty, take a short break, and do it all again until they have emptied the desired number of cans, then they go home.

• Shop Staff are only slightly more complicated than the customers. They take_orders, and if valid, they fill them and serve them. When all the customers have left, the staff go home.

  An invalid order signals that the staff member should go home.

• It initialises all the tint containers to have served zero doses.
• It calls paintshop_open, a routine you will provide to set up the shop.
• It then creates some threads to run as shop staff, and some more threads to run as customers. Note these threads obviously run concurrently.
• The driver thread then waits on a semaphore for all the staff and customers to finish, after which we print out the tint statistics for the day.
• Finally, it calls paintshop_close, a procedure you provide to clean up when the shop has closed.

You can assume that all the tint containers in the shop are infinite in size and hence will never be empty.

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

Your Job

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

• The shop being prepared for opening.
• All customers having their orders served with the correctly tinted paint in a can. "Correct" means that each corresponding entry in the contents array contains what was originally requested in the requested_colours array.
• The shop staff all going home after all the customers are finished.
• The shop being suitably cleaned up afterwards (allocated memory or locks, semaphores, etc being freed).
• Statistics kept on tint usage are consistent with the orders made.

You can modify paintshop_driver.c and paintshop_driver.h to test different scenarios (e.g vary the number and colour of paint cans ordered), but your solution must also work with an unmodified version of the paintshop_driver.c file.

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

For testing, we will replace paintshop_driver.c and .h with logically equivalent versions that may vary the numbers of participants, and the colours 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.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 #3)

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: 1b
S 0 going home after mixing 34 orders
S 1 going home after mixing 33 orders
S 2 going home after mixing 33 orders
Tint 1 used for 0 doses
Tint 2 used for 0 doses
Tint 3 used for 0 doses
Tint 4 used for 0 doses
Tint 5 used for 0 doses
Tint 6 used for 0 doses
Tint 7 used for 0 doses
Tint 8 used for 100 doses
Tint 9 used for 0 doses
Tint 10 used for 0 doses
The paint shop is closed, bye!!!
Operation took 0.529411720 seconds
OS/161 kernel: q
Shutting down.
The system is halted.

Before Coding!!!!

The following questions may help you develop your solution.

• What are the shared resources (e.g. tint containers)?
• Who shares what resources?
• Who produces what and who consumes what (e.g. customers produce orders consumed by staff)?
• What states can the various resources be in?
• What do you need to keep a count of (e.g. number of customers in the shop)?
• How does your solution prevent deadlock or starvation?

Evaluating your solutions

Performance will be judged in at least the following areas.

• Do all the staff members participate?
• Can staff mix in parallel if they do not require the same tints?
• Do you define critical sections larger than needed?

Documenting your solutions

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 cvs as follows.

% cd ~/cs3231/asst1-src
% cvs 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.

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
% cvs commit

Now tag the repository so that you can always retrieve your current version in the future.

% cd ~/cs3231/asst1-src
% cvs tag asst1-finish

Now generate a file containing the diff.

% cvs -q rdiff -r asst1-base -r asst1-finish -u asst1-src > ~/asst1.diff

Submitting Your Assignment

% cd ~
% give cs3231 asst1 asst1.diff

Note: If for some reason you need to change and re-submit your assignment after you have tagged it asst0-final, you will need to either delete the asst0-final tag, commit the new changes, re-tag, and re-diff your assignment, or choose a different final tag name and commit the new changes, tag with the new tag, and re-diff with the new tag. To delete a cvs tag, use

% cvs rtag -d asst1-final asst1-src