1. Due Dates and Mark Distribution

Due Date: 8am (08:00), Fri April 17th (Week 6)

Marks: Worth 25 marks (of the 100 available for the class mark component of the course)

The 10% bonus for one week early applies.

2. 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.

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

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:

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

3. Setting Up

Recall from ASST0 that you have to setup up your environment to access to tools in the class account.

% 3231

Your group account

You will do Assignment 1 as part of a two-person group. If you are not yet in a group, and don't have a parnter in mind, post to the appropriate message board on the cs3231 forum (Piazza in the teamates section) to find a partner.

To officially pair up, you must nominate your partner, and he or she must nominate you, via the group nomination form on the class web site (under "Administration" on the left-hand side bar).

You will be notified by email when your group is created, which usually happens 24–48 hours after the partners have nominated each other. 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 account for group work

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 or add the command:

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.

Note: if you forget this step, files you store in your group account will not be accessible to your partner. He will not have permission to access the shared repository you create in the next step.

Obtain the assignment sources

Only one group member should do the following.

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:

% 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:

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

Now make an immediate branch of this import for easy reference when generating your diff:

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

Checkout

The following instructions are now for both partners.

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.

4. 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

Building for ASST1

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

"Physical" Memory

In order to execute the tests in this assignment, you will need more than the 512 KiB of memory configured into System/161 by default. We suggest that you allocate at least 2 MiB of RAM to System/161. This configuration option is passed to the mainboard device with the ramsize parameter in your ~/cs3231/root/sys161.conf file. Make sure the mainboard device line looks like the following:

31 mainboard ramsize=2097152 cpus=1

5. 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.

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.

6. Tutorial Exercises

The following questions 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. However, the main aim of the tutorial is to have you implement synchronised data structures using the supplied OS synchronisation primitives. As such the main focus of the tutorial will be on the Synchronisation Problems below.

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.

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 Lists

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.

Code reading

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

Thread Questions

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

Scheduler Questions

Synchronisation Questions

7. 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 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 or modify).

Remember to specify a seed to use in the random number generator by editing 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.

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.99.04, compiled Mar  6 2010 15:32:32

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

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

1852k 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 r3000
OS/161 kernel: 1a
Starting 10 adder threads
Adder threads performed 10000 adds
Adder 0 performed 1070 increments.
Adder 1 performed 989 increments.
Adder 2 performed 972 increments.
Adder 3 performed 995 increments.
Adder 4 performed 953 increments.
Adder 5 performed 976 increments.
Adder 6 performed 1039 increments.
Adder 7 performed 989 increments.
Adder 8 performed 1030 increments.
Adder 9 performed 987 increments.
The adders performed 10000 increments overall
Operation took 1.920208600 seconds
OS/161 kernel: q
Shutting down.
The system is halted.

Part 2: Bounded-buffer producer/consumer problem

Your second 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 producer 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]: 1b
run_producerconsumer: starting up
Waiting for producer threads to exit...
Consumer started
Consumer started
Producer started
Producer started
Producer finished
Consumer started
Producer finished
Consumer started
Consumer started
All producer threads have exited.
*** Error! Consumer bored, exiting...
*** Error! Consumer bored, exiting...
*** Error! Consumer bored, exiting...
*** Error! Consumer bored, exiting...
*** Error! Consumer bored, exiting...
Operation took 0.402660000 seconds
OS/161 kernel [? for menu]: 

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

OS/161 kernel [? for menu]: 1b
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:

• producerconsumer_driver.c: Starts the producer/consumer simulation by creating appropriate producer and consumer threads that will call producer_produce() and consumer_consume(). You are welcome to (in fact, you are encouraged to) modify this simulation when testing your implementation, but remember that it will be overwritten when your solution is tested.
• producerconsumer_driver.h: Contains prototypes for the functions in producerconsumer.c, as well as the description of the data structure that is passed from producer to consumer (uninterestingly named pc_data). This file will also be overwritten when your solution is tested.
• producerconsumer.c: Contains your implementation of producer_produce() and consumer_consume(). It also contains the functions producerconsumer_startup() and producerconsumer_shutdown(), which you can implement to initialise your data structure and any synchronisation primitives you may need.

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.

You have just moved to a small town in the middle of no where, called Nowhereville. Nowhereville has a town library, which you decide to join, being an avid reader. When joining you notice that the library does not run very efficiently, members have to wait days in line to borrow books, even though there are copies available in the library. It seems the algorithm used to manage the library only allows one borrower at a time in order to not tax the intellectual might of the Nowhereville librarians.

Being an operating systems wizz, you realise they have a synchronisation issue, effectively they give mutually exclusive access to the whole library to one borrower at a time for as long as the borrower takes to read what they borrow. You offer to design a more efficient work-flow based on what you learnt in operating systems.

For the assignment, this means completing missing components of a software model of the library with appropriate data structures and synchronisation. A detailed description of the behaviour of the model is contained in the code itself in library.c, library_driver.c and the corresponding header files.

System Details

The following describes how the library system is modelled in OS/161 using its thread support in the kernel.

Members

Each member of the library is represented by a thread in OS/161 that runs the member() function, which borrows, reads, and returns books in accordance with the rules of the library.

• Each member has a library card which they use to borrow and return books.
• Only MAX_BORROWED books can be borrowed at a time.
• All previously borrowed books must be returned prior to borrowing more books.
• Any number of borrowed books can be returned in any order.
• Members will not attempt to borrow more copies of a book than the library possesses (NCATBOOKS), nor will they attempt to return books they did not borrow.

You can assume members of the library are good citizens and do not violate the rules of the library.

Librarians

As with library members, each librarian is represented by a thread in OS/161. Staff of Nowhereville library are pretty simple folk and behave as follows.

• Librarians either sit at the loans desk or the returns desk. Librarians wait for members to hand over their library cards with a list of books.
• If the member wishes to borrow books (i.e., he has approached the loans desk), the loans_librarian() fetches the book from the shelf if there is an available copy. If there is not a copy available, the librarian simply waits (potentially a very long time) for the book to return before fetching another book for the borrower. The librarian continues fetching books until he/she has all the requested books, at which point the librarian returns the card to the member so they can read the books.
• If the member wishes to return books (i.e., he has approached the returns desk), the returns_librarian() simply makes available the books the borrower returned and returns the card back to the member.
• The library keeps track of the number of members. Whenever a member permanently gives their card back to the library, the number of members is decremented. If the number of members reaches zero, all the librarians leave their jobs to find something else to do for a living, and the library shuts down.

Carefully examine the driver file library_driver.c and the header file library_driver.h. They contain a sample behaviour for librarians and members, and also constants in the header file that define the size of the library etc. You can change the files for testing purposes, but you cannot rely on any changes you make—we will use modified versions of them for testing which will remove any changes you make.

You will notice the librarian and member behaviour depend on the implementation of several support functions and data structures in library.c and library.h. These functions hand library cards between threads, wait for books, return books, etc. Your job is to implement these functions in the files such that the library functions.

Before Coding!!!!

The following questions may help you develop your solution.

• What are the shared resources (e.g. heads of queues?)?
• Who shares what resources?
• Who produces what and who consumes what (e.g. members produce cards consumed by librarians)?
• What states can the various resources be in?
• What do you need to keep a count of (e.g. number of members of the library)?
• How does your solution prevent deadlock or starvation?

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

sys161: System/161 release 1.99.04, compiled Mar 11 2010 15:44:07

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

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

1844k 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 r3000
OS/161 kernel: 1c
Initialising the library
M 0 going home after 10 loans
M 5 going home after 10 loans
M 4 going home after 10 loans
M 9 going home after 10 loans
M 1 going home after 10 loans
M 7 going home after 10 loans
M 2 going home after 10 loans
M 6 going home after 10 loans
M 3 going home after 10 loans
M 8 going home after 10 loans
L 1 going home after serving 34 borrow requests
L 2 going home after serving 32 borrow requests
L 0 going home after serving 34 borrow requests
R 0 going home after serving 100 returns requests
The library is closed, bye!!!
Operation took 0.441744520 seconds
OS/161 kernel: q
Shutting down.
The system is halted.
sys161: 15110771 cycles (15110771 run, 0 global-idle)
sys161:   cpu0: 15110771 kern, 0 user, 0 idle)
sys161: 6044 irqs 0 exns 0r/0w disk 0r/1138w console 0r/0w/1m emufs 0r/0w net
sys161: Elapsed real time: 0.581357 seconds (25.9922 mhz)
sys161: Elapsed virtual time: 0.604430840 seconds (25 mhz)

Evaluating your solutions

Performance will be judged in at least the following areas.

• Do all the librarians participate?
• Can library members read in parallel if they do not require the same copies of a book?
• Do you define critical sections larger than needed?

Note: OS/161 for ASST1 has a memory leak by design. OS/161 in-kernel uses kmalloc() and kfree() to allocate memory. kfree() is only partially implemented. This means two things:

• We will test your assignment by booting OS/161 and only running a single test per boot. We'll boot afresh for each subsequent test.
• You should avoid solutions that dynamically allocate memory on every small step of your solution - e.g. dynamically allocating a fresh library card for each loan.

Documenting your solutions

This is a compulsory component of this assignment. You must write a small design document identifying the basic issues in both 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 be 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.

Place your design document in design.txt (which we have created for you) at the top of the source tree to OS/161 (i.e. in ~/cs3231/asst1-src/design.txt).

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.

8. 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

Once your solution is committed, generate a diff.

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

Testing Your Submission