1. Due Dates and Mark Distribution

Due Date: 8am (08:00), Mon April 2nd

Extension: 8am (08:00), Mon April 9th

Marks: Worth 30 marks (of 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.
• The code you write will be reviewed, debugged, and modified by your partner. You will work more efficiently with your partner if they can understand your code.
• 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 the warm-up exercise that you have to set up up your environment to access 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 partner in mind, post to the appropriate message board on the cs3231 forum (Piazza in the teammates 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 website (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 the warm-up exercise, you used a version control system (VCS) to keep track of changes and to produce a file that you could submit. For this assignment, you will also use a VCS. 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 can 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. They 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. However, it would be beneficial if a group sets up the repo together to understand the process.

For this assignment, you will set up a repository in your group account directory (/home/osprjXXX). You may remember the repo directory you created for the warm-up exercise. For assignment 1, you will be creating this repository in your group account directory. Initialise this repository now.

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

You should now see an ASST1 directory in the compile directory.

Building for ASST1

When you built OS/161 for ASST0, you ran bmake from compile/ASST0. In ASST1, you run bmake from (you guessed it) compile/ASST1.

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

If you are told that the compile/ASST1 directory does not exist, make sure you ran config for ASST1.

Tip: Once you start modifying the OS/161 kernel, you can quickly rebuild and re-install with the following command sequence. It will install the kernel if the build succeeds.

% bmake && bmake install

"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 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, the location of kprintf() calls, and the order in which threads run should not influence the correctness 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 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 the 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 start the kernel via command line arguments and 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 need to run your tests via command line args to sys161 as described above, otherwise system behaviour will depend on your precise typing speed (and not be reproducible).

6. Tutorial Exercises

The main aim of the tutorial is to have you implement synchronised data structures using the supplied OS synchronisation primitives. The questions also 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.

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.

Critical sections

Q1 The following fragment of code is a single line of code. How might a race condition occur if it is executed concurrently by multiple threads? Can you give an example of how an incorrect result can be computed for x. How would you synchronise this code.

  x = x + 1;

Q2 The following function is called by multiple threads (potentially concurrently) in a multi-threaded program. Identify the critical section(s) that require(s) mutual exclusion. Describe the race condition or why no race condition exists. How would you synchronise the following code.

int i;

void foo()
{
    int j;

    /* random stuff*/

    i = i + 1;
    j = j + 1;

    /* more random stuff */
}

Q3 The following function is called by threads in a multi-thread program. Under what conditions does it need synchronisation or not.

void inc_mem(int *iptr)
{
    *iptr = *iptr + 1;
}

Coordinating activities

Q4 What synchronisation mechanism or approach might one take to have one thread wait for another thread to update some state?

Q5 A particular abstraction only allows a maximum of 10 threads to enter the "room" at any point in time. Further threads attempting to enter the room have to wait at the door for another thread to exit the room. How could one implement a synchronisation approach to enforce the above restriction?

Q6 Multiple threads are waiting for the same thing to happen (e.g. a disk block to arrive from disk). Write pseudo-code for a synchronising and waking the multiple threads waiting for the same event.

Identify Deadlocks

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

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

Q8 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 Lists

Q9 Describe (and give pseudocode for) a synchronised linked list structure based on thread list code in the OS/161 codebase (kern/thread/threadlist.c). 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.

In a general sense, the interface to the synchronised list is as follows.

    init();
    add_head(list_t *list, node_t *node);
    add_tail(list_t *list, node_t *node);
    remove_head(list_t *list, node_t *node);
    remove_tail(list_t *list, node_t *node);
    insert_after(node_t *in_list, node_t *new_node);
    insert_before(node_t *in_list, node_t *new_node);
    remove(node_t *in_list);
  

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.

Consider a solution involving a lock per node in the list. The instructive cases are insert_after() and insert_before(), and remove()

The thread subsystem in OS/161 uses a linked list of threads to manage some of its state (kern/thread/threadlist.c). This structure is not synchronised. Why not?

Code reading

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

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

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

Note: In this assignment, you are restricted to the lock, semaphore, and condition variable primitives provided in OS/161. The use of primitives such as thread_yield, atomic ops, and the like are discouraged. Moreover, they usually result in a poor solution involving busy waiting.

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.

When you configure your kernel for ASST1, the driver code and extra menu options for executing your solutions are automatically compiled in.

Part 1: 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"
ys161: System/161 release 2.0.2, compiled Feb 26 2015 18:41:37

OS/161 base system version 2.0.2
(with locks&CVs solution)
Copyright (c) 2000, 2001-2005, 2008-2011, 2013, 2014
   President and Fellows of Harvard College.  All rights reserved.

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

1804k 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/161 (System/161 2.x) features 0x0
OS/161 kernel: 1a
Starting 10 adder threads
Adder threads performed 10000 adds
Adder 0 performed 919 increments.
Adder 1 performed 1037 increments.
Adder 2 performed 867 increments.
Adder 3 performed 1087 increments.
Adder 4 performed 1059 increments.
Adder 5 performed 905 increments.
Adder 6 performed 1132 increments.
Adder 7 performed 997 increments.
Adder 8 performed 958 increments.
Adder 9 performed 1039 increments.
The adders performed 10000 increments overall
Operation took 4.268131880 seconds
OS/161 kernel: q
Shutting down.
The system is halted.
sys161: 138026250 cycles (138026250 run, 0 global-idle)
sys161:   cpu0: 94167964 kern, 0 user, 0 idle; 146194 ll, 146194/0 sc, 312241 sync
sys161: 36389 irqs 0 exns 0r/0w disk 0r/1084w console 0r/0w/1m emufs 0r/0w net
sys161: Elapsed real time: 4.128787 seconds (33.4302 mhz)
sys161: Elapsed virtual time: 5.525339383 seconds (25 mhz)

Part 2: Simple Deadlock

This task involves modifying a simple example such that the example no longer deadlocks and is able to finish. The example is in twolocks.c.

In the example, bill() and ben() are two threads that both need to hold two locks at the same time to make progress: lock_a and lock_b. While holding both locks, bill() and ben() do "something" that is omitted from the code. The way the current code is written, the code deadlocks and trigger's OS/161's deadlock detection code, as shown below.

% sys161 kernel "1b;q"
sys161: System/161 release 2.0.8, compiled Feb 19 2017 14:31:53

OS/161 base system version 2.0.3
(with locks&CVs solution)
Copyright (c) 2000, 2001-2005, 2008-2011, 2013, 2014
   President and Fellows of Harvard College.  All rights reserved.

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

348k 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/161 (System/161 2.x) features 0x0
OS/161 kernel: 1b
Locking frenzy starting up
Hi, I'm Bill
Hi, I'm Ben
hangman: Detected lock cycle!
hangman: in ben thread (0x8002ded8);
hangman: waiting for lock_a (0x8002ed04), but:
   lockable lock_a (0x8002ed04)
   held by actor bill thread (0x8002df58)
   waiting for lockable lock_b (0x8002ecc4)
   held by actor ben thread (0x8002ded8)
panic: Deadlock.
sys161: trace: software-requested debugger stop
sys161: Waiting for debugger connection...

You task is to modify the existing code such that:

1. The example runs to completion.
2. The solution still involves both locks being held at the point where "something" happens.

Part 3: Bounded-buffer producer/consumer problem

Your next 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_send() function with a data structure. In turn, the consumer threads attempt to receive information from the producer threads by calling consumer_receive(). 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
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]: 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:

• producerconsumer_driver.c: Starts the producer/consumer simulation by creating appropriate producer and consumer threads that will call producer_send() and consumer_receive(). 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_send() and consumer_receive(). 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_send() BUFFER_SIZE times should not block (or overwrite existing items, of course), but calling producer_send one more time should block, until data has been removed from the buffer using consumer_receive(). 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.

Part 4: Bar synchronisation

It's Monday night, you have finished your lecture, and you decide to unwind, relax, and head to the bar for a drink. When you arrive, you find the bar in complete chaos. Customers are receiving empty glasses, bartenders are fighting over drink supplies, orders are getting lost, drinks are being mixed up, some customers are waiting forever for their first drink, while others have already passed out on the floor.

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

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

System Details

To provide a solution, you must come to terms with the basic elements of the bar that you have to work with. The bar consists of a set of bottles containing various drinks such as BEER, GIN, and VODKA, that are used to pour drinks for customers.

Customers arrive at the bar and give their order to a bartender, who then pours their drink using one or more bottles.

The basic elements are defined in kern/asst1/bar_driver.h and barglass.h

The behaviour of customers and bartenders are defined in kern/asst1/bar_driver.c. See the file for detailed comments.

• Customers (threads) arrive and give their order to a bartender, then wait for their drink.

  Eventually they get their drink, drink it, then give another order to the bartender until they've had enough and go home.

• Bartenders are only slightly more complicated than the customers. They take orders, they fill them and serve them. When all the customers have left, the bartenders go home.

  A flag in the order is used to signal that the bartender should go home.

The function run_bar() is called via the menu in OS/161 (item 1d). run_bar() does the following:

• It initialises all the bottles to have served zero doses.
• It calls bar_open(), a routine you will provide to set up the bar.
• It then creates some threads to run as bartenders, 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 bartenders and customers to finish, after which we print out the bottle statistics for the evening.
• Finally, it calls bar_close(), a procedure you provide to clean up when the bar has closed.

The function mix() takes up to three basic ingredients (from a customer) and mixes a drink from each of the appropriate bottles into a glass. The ingredients are represented by numbers, each number corresponds to the selected bottle number. Note the contents of the glass is also represented by an array of numbers (ingredients). The meaning of the bottle numbers are defined in barglass.h.

You can assume that all bottles in the bar are infinite in size and hence will never be empty. You may similarly assume that there is never any danger of running out of fresh glasses for customers.

Have a quick look through both bar_driver.c and bar_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 bar.c that perform most of the work (and potentially modify bar.h). Each function is described in bar.c.

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

• The bar being prepared for opening.
• All customers having their orders served with the correct drinks in a glass. "Correct" means that each corresponding entry in the contents array contains what was originally requested in the requested_bottles array.
• The bartenders all going home after all the customers are finished.
• The bar being suitably cleaned up afterwards (allocated memory or locks, semaphores, etc. being freed).
• Statistics kept on bottle usage are consistent with the orders made.

You can modify bar_driver.c and bar_driver.h to test different scenarios (e.g. vary the number and type of drinks ordered), but your solution must preserve the existing overall model of behaviour. Your solution should continue to work with an unmodified version of the bar_driver.c file, and any variation we choose that validly exercises the model of the bar.

Behaviour within the overall model includes:

• Customers ordering different requests (e.g. random bottles).
• Bars initialised with different numbers of bartenders and/or customers.
• Bars that start with more or fewer bottles in their stores

You will have to modify bar.c to implement your solution. However, your modifications have the constraint that they must still work within the original bar_driver.c model.

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

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

% sys161 kernel '1d;q'
sys161: System/161 release 2.0.8, compiled Feb 25 2017 06:18:37

OS/161 base system version 2.0.3
(with locks&CVs solution)
Copyright (c) 2000, 2001-2005, 2008-2011, 2013, 2014
   President and Fellows of Harvard College.  All rights reserved.

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

1884k 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/161 (System/161 2.x) features 0x0
OS/161 kernel: 1d
Bottle 1 used for 100 doses
Bottle 2 used for 0 doses
Bottle 3 used for 0 doses
Bottle 4 used for 0 doses
Bottle 5 used for 0 doses
Bottle 6 used for 0 doses
Bottle 7 used for 0 doses
Bottle 8 used for 0 doses
Bottle 9 used for 0 doses
Bottle 10 used for 0 doses
The bar is closed, bye!!!
Operation took 5.391906280 seconds
OS/161 kernel: q
Shutting down.
The system is halted.
sys161: 197892889 cycles (166326605 run, 31566284 global-idle)
sys161:   cpu0: 134760321 kern, 0 user, 0 idle; 477753 ll, 477753/0 sc, 1011533 sync
sys161: 49906 irqs 0 exns 0r/0w disk 0r/921w console 0r/0w/1m emufs 0r/0w net
sys161: Elapsed real time: 3.684926 seconds (53.7034 mhz)
sys161: Elapsed virtual time: 6.657353583 seconds (25 mhz)

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.

• What are the shared resources (e.g. bottles)?
• Who shares what resources?
• Who produces what and who consumes what (e.g. customers produce orders consumed by bartenders)?
• What states can the various resources be in?
• How does your solution prevent deadlock or starvation (in this case, dehydration)?

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.

It is reasonable to assume co-operative subsystems within an OS. It is difficult (impossible) to defend against malicious code within the operating system itself. However, one can still program defensively in the interests of detecting invalid behaviour early for debugging purposes. Such behaviour usually signals an internal error, with a reasonable response being to panic(). In the case of this assignment, one can assume customers and bartenders follow the overall interaction model.

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.

• Do all the bartenders participate?
• Can bartenders mix in parallel if they do not require the same bottle at the same time?
• 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 to minimise the chance of memory exhaustion.
• You should always test for success of functions you use to and not assume memory allocation will always work (good programming practice anyway). It is unlikely that you will trigger the pathological situation that results in memory exhaustion.
• You should avoid solutions that dynamically allocate memory on every small step of your solution - e.g. dynamically allocating a fresh drink order for each order.

Documenting your solutions

This is a compulsory component of this assignment. You must write a small design document identifying the basic issues in all 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 result 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 the warm-up exercise, you again will be submitting a diff of your changes to the original tree.

You should first commit your changes back to the repository. 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. Refer to the appropriate wiki page for instructions.