ASST1: Synchronisation
Table of Contents
Due Dates and Mark Distribution
Introduction
Setting Up Your Assignment
Obtain the ASST1 distribution with git
Configure OS/161 for Assignment 1
Building ASST1
Check sys161.conf
Run the kernel
Kernel menu commands and arguments to OS/161
Concurrent Programming with OS/161
Debugging concurrent programs
Tutorial Exercises
Code reading
Thread Questions
Scheduler Questions
Synchronisation Questions
Coding the Assignment
Part 1: The Concurrent Counter Problem
Part 2: Simple Deadlock
Part 3: Bounded-buffer producer/consumer problem
The files:
Clarifications
Part 4: The Soup Kitchen
Submitting
Due Dates and Mark Distribution
Due Date & Time: 4pm (16:00), Friday March 10 (Week 4)
Marks: Worth 30 marks (of the class mark component of the course)
The 2% per day bonus for each day early applies, capped at 10%, as per
course outline.
Introduction
In this assignment you will solve a number of synchronisation problems
within the software environment of the OS/161 kernel. By the end of this
assignment you will gain the skills required to write concurrent code within
the OS/161 kernel. While the synchronisation problems themselves are only
indirectly related to the services that OS/161 provides, they solve similar
concurrency problems that you would encounter when writing OS code.
The Week 3 tutorial contains various synchronisation familiarisation
exercises. Please prepare for it. Additionally, feel free to ask any
assignment related questions in the tutorial.
Setting Up Your Assignment
We assume after ASST0 that you now have some familiarity with setting
up for OS/161 development. The following is a brief setup guide. If you
need more detail, refer back to ASST0.
Obtain the ASST1 distribution with git
Clone the ASST1 source repository from gitlab.cse.unsw.edu.au.
% cd ~/cs3231
% git clone
XXXXXX-asst1.git asst1-src
Configure OS/161 for Assignment 1
Configure your new sources as follows.
% cd ~/cs3231/asst1-src
% ./configure && bmake && bmake install
We have provided you with a framework to run your solutions for ASST1.
This framework consists of tester code (found in kern/asst1) and menu
items you can use to execute the code and your solutions from the OS/161
kernel boot menu.
You have to configure your kernel itself 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 kern/compile directory.
Building ASST1
When you built OS/161 for ASST0, you ran bmake in compile/ASST0. In
ASST1, you run bmake from (you guessed it) compile/ASST1.
% cd ../compile/ASST1
% bmake depend
% 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
Check sys161.conf
The sys161.conf should be already be installed in the ~/cs3231/root
directory from assignment 0. If not, follow the instructions below to obtain
another copy. A pre-configured sys161 configuration is available here:
sys161.conf.
% cd ~/cs3231/root
% wget http://cgi.cse.unsw.edu.au/~cs3231/23T1/assignments/asst1/sys
https://cgi.cse.unsw.edu.au/~cs3231/23T1/assignments/asst1/sys161.conf
Run the kernel
Run the previously built kernel:
% cd ~/cs3231/root
% sys161 kernel
sys161: System/161 release 2.0.8, compiled Feb 25 2019 09:34:40
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 #1)
16220k 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 [? for menu]:
Kernel menu commands and arguments to
Your solutions to ASST1 will be tested (and automarked) by running
OS/161 with command line arguments that correspond to the menu
options in the OS/161 boot menu.
Caution! Do not change these menu option strings!
Here are some examples of using command line arguments to select
OS/161 menu items:
sys161 kernel “at;bt;q”
This is the same as starting up with sys161 kernel, then running “at” at
the menu prompt (invoking the array test), then when that finishes running
“bt” (bitmap test), then quitting by typing “q”.
sys161 kernel “q”
This is the simplest example. This will start the kernel up, then quit as
soon as it’s finished booting. Try it yourself with other menu commands.
Remember that the commands must be separated by semicolons (“;”).
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 verify that
they implement the functionality required and that they do not deadlock.
Debugging concurrent programs
thread_yield() is automatically called for you at intervals that vary
randomly. thread_yield() context switches between threads via the
scheduler to provide multi-threading in the OS/161 kernel. While the
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 timing that may expose scenarios that
you had not anticipated.
To reproduce your test cases, you need to run your tests via the command
line arguments to sys161 as described above, otherwise system behaviour
will depend on your precise typing speed (and not be reproducible for
debugging).
Tutorial Exercises
The aim of the week 3 tutorial is to have you implement synchronised data
structures using the supplied OS synchronisation primitives. See the Week
03 Tutorial for details.
It is useful to be prepared to discuss both the questions and the following
assignment in your tutorial.
Code reading
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, though
recommended especially for Extended OS students.
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?
https://cgi.cse.unsw.edu.au/~cs3231/tutorials.php
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
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. What is a wait channel? Describe how wchan_sleep() and
wchan_wakeone() are used to implement semaphores.
10. Why does the lock API in OS/161 provide lock_do_i_hold(), but not
lock_get_holder()?
Coding the Assignment
We know: you’ve been itching to get to the coding. Well, you’ve finally
This is the assessable component of this assignment.
The following problems will give you the opportunity to write some fairly
straightforward concurrent systems and get a practical understanding of
how to use concurrency mechanisms to solve problems. We have provided
you with basic tester 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 other
primitives such as thread_yield(), spinlocks, interrupt disabling (spl),
atomic instructions, and the like are prohibited. Moreover, they usually
result in a poor solution involving busy waiting.
Note: In some instances, the comments within the code also form part of
the specification and give guidance as to what is required. Make sure you
read the provided code carefully.
Check that you have specified a seed to use in the random number
generator by examining your sys161.conf file, and run your tests using
System/161 command line arguments. It is much easier to debug initial
problems when the sequence of execution and context switches are
reproducible.
When you configure your kernel for ASST1, the tester code and extra menu
options for executing the problems (and your solutions) are automatically
compiled in.
Part 1: The Concurrent Counter Problem
For the first problem, we ask you to solve a mutual exclusion problem. The
code in kern/asst1/counter.c is an incomplete implementation of an
interface specified in kern/asst1/counter.h. The interface specifies
functions to initialise (counter_initialise()), increment
(counter_increment()), decrement (counter_decrement()), and read and
cleanup a synchronised counter (counter_read_and_destroy()). The
increment and decrement code can be called concurrently by multiple
threads and is unsynchronised.
The testing code provided in kern/asst1/counter_tester.c exercises a
subset of the counter code and produces an incorrect result similar to the
following. Note that the final count of the incomplete implementation is
dependent on scheduling and hence will vary.
OS/161 kernel [? for menu]: 1a
Starting 10 incrementer threads
The final count value was 5083 (expected 10000)
Your task is to modify kern/asst1/counter.c and kern/asst1/counter.h by
synchronising the code appropriately such that synchronised counters can
be created, destroyed, incremented and decremented correctly.
You can assume that counter_initialise() and
counter_read_and_destroy() are not called concurrently, and
counter_read_and_destroy() is always called sometime after the a call to
counter_initialise(), before any later call to counter_initialise().
counter_increment() and counter_decrement() are only ever called
(multiple times) after a call to counter_initialise() and before the final
call to counter_read_and_destroy().
To test your solution, use the 1a menu choice. Sample output from a
correct solution in included below.
OS/161 kernel [? for menu]: 1a
Starting 10 incrementer threads
The final count value was 10000 (expected 10000)
When we mark your assignment, we will replace the testing code provided
in kern/asst1/counter_tester.c to test your implementation more
extensively than the provided code.
Part 2: Simple Deadlock
This task involves modifying an example such that the example no longer
deadlocks and is able to finish. The example is in twolocks.c.
In the example, bill(), bruce(), bob() and ben() are threads that need to
hold one or two locks at various times to make progress: lock_a and
lock_b. While holding one or two locks, the threads call holds_lockX that
just consumes some CPU. The way the current code is written, the code
deadlocks and triggers OS/161’s deadlock detection code, as shown
OS/161 kernel: 1b
Locking frenzy starting up
Hi, I’m Bill
Hi, I’m Ben
Hi, I’m Bruce
Hi, I’m Bob
hangman: Detected lock cycle!
hangman: in ben thread (0x80031ed8);
hangman: waiting for lock_a (0x80032d04), but:
lockable lock_a (0x80032d04)
held by actor bill thread (0x80031f58)
waiting for lockable lock_b (0x80032cc4)
held by actor ben thread (0x80031ed8)
panic: Deadlock.
sys161: trace: software-requested debugger stop
sys161: Waiting for debugger connection…
You task is to modify the existing code such that:
you apply resource-ordering deadlock prevention such that the code
no longer deadlocks, and runs to completion as shown below (the
ordering may vary);
the modified solution still calls the holds_lockX functions in the same
places, and only the locks indicated are held by the thread at that
point in the code;
your deadlock free solution only uses the existing locks and calls them
the same number of times; and
you document the overall resource order chosen in the comment
indicated in the code.
OS/161 kernel: 1b
Locking frenzy starting up
Hi, I’m Bill
Hi, I’m Bruce
Hi, I’m Ben
Hi, I’m Bob
Bruce says ‘bye’
Bob says ‘bye’
Ben says ‘bye’
Bill says ‘bye’
Locking frenzy finished
Part 3: Bounded-buffer producer/consumer
Your next task in this part is to synchronise a solution to a
producer/consumer problem. In this producer/consumer problem, one or
more producer threads allocate data structures, and call producer_send(),
which copies pointers to the data structures into a fixed-sized buffer,
while one or more consumer threads retrieve those pointers using
consumer_receive(), and inspect and de-allocate the data structures.
The code in kern/asst1/producerconsumer_tester.c starts up a number of
producer and consumer threads. The producer threads attempt to send
pointers to the consumer threads by calling the producer_send() function
with a pointer to the data structure as an argument. In turn, the consumer
threads attempt to receive pointers to the data structure from the
producer threads by calling consumer_receive(). These functions are
currently partially implemented. Your job is to synchronise them.
Here’s what you might 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
Producer started
Consumer started
Producer finished
Consumer started
Producer started
*** Error! Unexpected data -2147287680 and -2147287680
Consumer started
*** Error! Unexpected data -2147287712 and -2147287712
Consumer started
*** Error! Unexpected data -2147287648 and -2147287648
*** Error! Unexpected data -2147287712 and -2147287712
*** Error! Unexpected data -2147287648 and -2147287648
*** Error! Unexpected data -2147287648 and -2147287648
*** Error! Unexpected data -2147287648 and -2147287648
*** Error! Unexpected data -2147287712 and -2147287712
*** Error! Unexpected data -2147287664 and -2147287664
*** Error! Unexpected data -2147287664 and -2147287664
*** Error! Unexpected data -2147287600 and -2147287600
*** Error! Unexpected data -2147287600 and -2147287600
*** Error! Unexpected data -2147287664 and -2147287664
*** Error! Unexpected data -2147287600 and -2147287600
panic: Assertion failed: fl != fl->next, at ../../vm/kmalloc.c:1134
(subpage_kfree)
Note that code will panic (crash) in different ways depending on the
And here’s what you will see with a (possibly) correct solution:
OS/161 kernel: 1c
run_producerconsumer: starting up
Consumer started
Waiting for producer threads to exit…
Producer started
Consumer started
Consumer started
Producer started
Consumer started
Consumer started
Producer finished
Producer finished
All producer threads have exited.
Consumer finished normally
Consumer finished normally
Consumer finished normally
Consumer finished normally
Consumer finished normally
The files:
producerconsumer_tester.c: Starts the producer/consumer simulation
by creating producer and consumer threads that will call
producer_send() and consumer_receive(). You are welcome to modify
this simulation when testing your implementation — in fact, you are
encouraged to — but remember that it will be overwritten when we
test your solution is tested, so you can’t rely on any changes you
make in this file.
producerconsumer.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 (the uninterestingly-named
data_item_t). This file will also be overwritten when your solution is
tested by us.
producerconsumer.c: Contains the implementation of producer_send()
and consumer_receive(). It also contains the functions
producerconsumer_startup() and producerconsumer_shutdown(), which
you can implement to initialise any variables and any synchronisation
primitives you may need.
Clarifications
The provided data structure represents a bounded buffer capable that is
capable of holding BUFFER_ITEMS data_item_t pointers. This means that
calling producer_send() BUFFER_ITEMS times should not block (or overwrite
existing items, of course), but calling producer_send() one more time
should block, until an item has been removed from the buffer using
consumer_receive(). We have provided an unsynchronised skeleton of
circular buffer code, though you will have to use appropriate
synchronisation primitives to ensure that concurrent access is handled
The data structure should function as a circular buffer with first-in, first-
out semantics.
Part 4: The Soup Kitchen
This part simulates a simple soup kitchen with customer threads and a
single soup cooking thread. The customers serve themselves from a large
soup pot that can hold a certain number of servings of soup. The
customers should only attempt to serve themselves soup if the pot is not
empty. When the pot is empty the soup cook should wake up and cook a
whole pot of fresh soup.
The code that drives the system is in kitchen_tester.c. You should review
the code to develop an understanding of the system. You’ll see it starts a
number of customer dining threads and a single cook thread, and then
waits for the customers to consume all their bowls of soup, and the cook
to cook enough pots of soup to serve all the hungry customers.
The functions of particular interest are dining_thread and cooking_thread
which document and show the behaviour of customers and the cook.
A dining thread fills (fill_bowl()) and eats (eats()) their bowl of soup
repeatedly NUM_SERVES times. The cooking thread cooks (do_cooking()) the
appropriate number of pots of soup to satisfy the hunger of the diner. The
dining and cooking threads interact with each other via the skeleton
functions provided in kitchen.c, i.e. fill_bowl() and do_cooking().
At a high level, these ensure a customer only attempts to fill their bowl
when the pot has soup remaining, and the cook only cooks whole pots of
soup when the pot completely empties.
Your task is to implement these functions such that the soup system will
execute correctly.
do_cooking() should only call cook_soup_in_pot() when the pot is
fill_bowl should only call get_serving_from_pot() when there is soup
remaining in the pot.
get_serving_from_pot() should be called mutually exclusively.
Your solution should not busy-wait when a thread can’t make
You should not rely on any changes to code in the kitchen_tester.c
or kitchen.h files. They will be changed for testing purposes after
your final submission. You can vary the code for your own testing
purposes, but we’ll replace them for our own testing of your code.
A sample of how the code can fail follows. Notice a dining customer called
get_serving_from_pot() when the pot was empty.
cpu0: MIPS/161 (System/161 2.x) features 0x0
OS/161 kernel [? for menu]: 1d
Starting 20 dining threads who eat 10 serves each
panic: Attempting to fill bowl from empty pot
A potentially correct solution generates output similar to that below.
cpu0: MIPS/161 (System/161 2.x) features 0x0
OS/161 kernel [? for menu]: 1d
Starting 20 dining threads who eat 10 serves each
Starting cooking thread
The total number of servings served was 200 (expected 200)
Operation took 4.953980040 seconds
This problem is simpler to solve in OS/161 using locks and condition
variables.
If using condition variables, consider whether cv_signal() or
cv_broadcast() is appropriate when required.
Solving this problem involves creating new shared state that tracks
the status of the pot.
For a dining customer, it helps to be able to identify what is the
condition that requires cv_wait to be called. What is the condition that
triggers a cv_signal in the cook.
For the cook, it helps to be able to identify what is the condition that
requires cv_wait to be called. What is the condition that triggers a
cv_signal in a dining customer.
Submitting
The submission instructions are available on the Wiki. Like ASST0, you will
be submitting the git repository bundle via CSE’s give system. For ASST1,
the submission system will do a test build and run a simple test to confirm
your bundle at least compiles. It does not exhaustively test you submission
Warning Don’t ignore the submission system! If your submission
fails the simple test in the submission process, you may
not receive any marks.
To submit your bundle:
% give cs3231 asst1 asst1.bundle
You’re now done.
Even though the generated bundle should represent all the changes you
have made to the supplied code, occasionally students do something
“ingenious”. So always keep your git repository so that you may recover
your assignment should something go wrong. We recommend to git push
it back to gitlab.cse.unsw.edu.au for safe keeping.
https://wiki.cse.unsw.edu.au/cs3231cgi/FrontPage