Assignment 1

Assignment 1: Readers and Writers: Concurrent Prime Number Generator

Due Date: 8am, Monday morning, 6th of September

Worth 25 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, also applies

See course intro for exact details. The notional release time is midnight, Monday, 16th August



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

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

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

Setting up your account

You will need to set up various environment variables for you to access the tools needed for the course. You may have already done so for the week 3 tutorial. If not you'll need either do the following if you know what you're doing, or simply run 3231 in each new shell. Note: You must not have "." (or equivalent) prior to "/bin" in your PATH. The build will fail later if you do. Note: doing this is generally a bad idea for security reasons anyway.

Obtaining and setting up the distribution

The OS/161 distribution can be copied from the class account into your home direcory. Assuming you've set up your account as above, use this command:
% cp -r ~cs3231/assigns/asst1/src ~/cs3231
You should now have a src directory to work on.

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
You should now see an ASST1 directory in the compile directory.

Building for ASST1

When you built OS/161 for the tutorial in week 3, 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]: 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]:
The prime command runs a very simple test. You may also pass in the number of readers and the number of writers.

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!

"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.
There is an example conf file

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 the week 3 tutorial, 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.

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() {
	/* do something */
	/* do something else */
	/* clean up */
void you() {
	/* do something */

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() {
	/* do something */
    	/* write to file 1 */
	/* write to file 2 */
	/* do something */
	/* read from file 1 */
	/* write to file 2 */
void hardy() {
    	/* do stuff */
	/* read from file 1 */
	/* write to file 2 */
	/* do something */
	/* write to file 1 */

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 25 marks of the 100 available for the class mark component of the course.

Solving Synchronisation Problems

The following problem will give you the opportunity to write a fairly straightforward concurrent program 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.

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

The Problem

This is a variant of a consumer/producer problem combined with a concurrent sequence merge: A number generator produces numbers and inserts them in a circular buffer. An unknown number of worker threads take a number from the circular buffer, check whether the number is prime. If so, they insert it in a shared list in a way that the resulting list is always sorted. The worker threads have to be able to insert elements into the list concurrently, so it is not possible to lock the whole list while inserting, or while searching for the right spot for the insertion. However, you first might want to try and implement it locking the complete list. A solution which works this way achieves at most 70% of the possible marks.

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!!!!

You should have a very good idea of what you are 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. Now is also a good time to design the data-structures you will need to implement the assignment.

Your Job

Read the comments in kern/asst1/prime.h. Once you understand what each function does, finish the implementation in kern/asst1/prime.c. If you need to write extra functions in prime.c, you should, of course, declare them in prime.h.

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:

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

Your solution will be judged in terms of its correctness, conciseness, clarity, and performance. We will be auto-testing your code, so make sure your print functions work exactly as specified, and that you don't have any extra print statements.

Performance will be judged in at least the following areas.

When testing your assignment, we may write driver code that is significantly different to prime_driver.c. In particular, we may vary at least the following: In summary, if your code conforms to the API in kern/asst1/prime_driver.h you should be fine.

Submitting Your Assignment

You will be submitting only your prime.c and prime.h files. Use the following commands to do so:
$ cd ~/cs3231/src/kern/asst1
$ give cs3231 asst1 prime.h prime.c
You're now done.