Introduction

In this assignment you will implement a simple concurrent prime number generator. You will solve a number of synchronisation and locking problems and 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

Follow these directions carefully. Make sure you have plenty of disk quota available before you start.

Setting up your account

• You will need to add /home/cs3231/bin, and /home/cs3231/bin-${ARCH}, to your PATH.
• You will need to add /home/cs3231/man to your MANPATH.
• In your home directory, create a directory in which you will do all your cs3231 work. We'll assume from here on that it's called cs3231. The following command will acheive this:

  $ mkdir ~/cs3231

Obtaining and setting up the distribution

% cp -r ~cs3231/assigns/asst1/src ~/cs3231

Begin Your Assignment

Configure OS/161 for Assignment 1

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 the week 3 tutorial except you will use the ASST1 configuration file:

% cd ~/cs3231/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]: prime
circ_buffer_create: not yet implemented!circ_buffer_create failed.
Operation took 0.011444560 seconds
Menu command failed: Unimplemented feature
OS/161 kernel [? for menu]:

Command Line Arguments to OS/161

IMPORTANT: Please DO NOT change these menu option strings!

"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 25 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.

When you configure your kernel for ASST1, menu options for executing your solutions are automatically compiled in.

The Problem

Don't worry about finding an efficient way to check if a number is prime or not: this is not the point of the assignment.

Before Coding!!!!

The following questions may help you develop your solution.

• What information do you need to keep track of the content of the buffer?
• What data can be accessed concurrently (i.e. what do you need to protect)?

Your Job

We have provided you with a function called is_prime in prime_driver.c (declared in prime_driver.h) to test for prime-ness.
You must use this function for your prime checking.
Do not waste your time trying to optimise this function, as it and all the other functions in prime_driver.c may be modified for testing.

You may use any combination of locks, semaphores, and condition variables to implement your solution. Do NOT use splx() (or any other functions which manipulate the interrupt status directly).

While you may do the assignment in any way you see fit, the following strategy may help:

• To start out, implement only a single worker thread.
• Extend your implementation to multiple workers, locking the complete prime buffer.
• Finally, finish the assignment by allowing the worker threads to concurrently access the prime buffer.

We have provided a very simple test in kern/asst1/prime_driver.c. We expect you to test your code, so you may modify this file as you see fit. However, your solution must conform to the API in prime_driver.h and should not rely on the contents of prime_driver.c. We will use our own version of prime_driver.h and prime_driver.c to run tests; any changes you make to this file will be lost.

Evaluating your solution

Performance will be judged in at least the following areas.

• How efficient is your solution?
• Can multiple multiple workers access the buffer at the same time? Or, alternatively, does your implementation block threads unnecessarily?
• Does your implementation clean up resources when they are no longer required?

• Size of a buffers;
• Number of threads;
• Relative speed of threads (slow generator, slow workers, etc.); and
• Behaviour of threads;

Submitting Your Assignment

$ cd ~/cs3231/src/kern/asst1
$ give cs3231 asst1 prime.h prime.c