![[UNSW]](/~cs3231/images/unsw_0.png)
ASST1: Synchronisation
Table of Contents
Due Dates and Mark Distribution
Due Date & Time: 2pm (14:00), June 26 (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 synchronisation problems themselves are 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 https://zXXXXXXX@gitlab.cse.unsw.edu.au/COMP3231/20T2/zXXXXXXX-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 driver 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 % 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/20T2/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]:
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 required of them 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 conditions and 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.
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
- What happens to a thread when it exits (i.e., calls thread_exit())? What about when it sleeps?
- What function(s) handle(s) a context switch?
- How many thread states are there? What are they?
- 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?
- What happens when a thread wakes up another thread? How does a sleeping thread get to run again?
Scheduler Questions
- What function is responsible for choosing the next thread to run?
- How does that function pick the next thread?
- What role does the hardware timer play in scheduling? What hardware independent function is called on a timer interrupt?
Synchronisation Questions
- What is a wait channel? Describe how wchan_sleep() and wchan_wakeone() are used to implement semaphores.
- 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 arrived!
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 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 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 driver code and extra menu options for executing the problems (and your solutions) are automatically compiled in.
Part 1: Concurrent Mathematics Problem
Marks: 5
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. An incorrect run is shown below.
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.
OS/161 kernel: 1a Starting 10 adder threads In thread 6, 777 + 1 == 782? In thread 1, 1053 + 1 == 783? In thread 5, 782 + 1 == 1073? In thread 0, 1040 + 1 == 784? In thread 8, 1443 + 1 == 1455? In thread 4, 1511 + 1 == 1522? In thread 9, 1562 + 1 == 1568? In thread 2, 1657 + 1 == 1666? In thread 7, 1665 + 1 == 1667? In thread 6, 4341 + 1 == 4344? In thread 3, 6499 + 1 == 6505? In thread 1, 7877 + 1 == 7894? In thread 5, 7893 + 1 == 7895? In thread 0, 9783 + 1 == 9834? Adder threads performed 10000 adds Adder 0 performed 1924 increments. Adder 1 performed 1403 increments. Adder 2 performed 95 increments. Adder 3 performed 4822 increments. Adder 4 performed 658 increments. Adder 5 performed 264 increments. Adder 6 performed 219 increments. Adder 7 performed 9 increments. Adder 8 performed 590 increments. Adder 9 performed 92 increments. The adders performed 10076 increments overall (expected 10000)
Your Task
Your task is to modify adder() in math.c by placing synchronisation primitives appropriately such that incrementing the counter works correctly, and the sanity-check code involving a and b no longer prints. The statistics printed at the end should also be consistent with the overall count. Note: The critical section should not extend beyond that specified in the code itself.
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.
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
Part 2: Simple Deadlock
Marks: 5
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(), 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 below.
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:
- 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.
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 problem
Marks: 10
Your next task in this part is to implement a solution to a producer/consumer problem. In this producer/consumer problem, one or more producer threads allocate data structures and copy the pointers to the data structures into a fixed-sized buffer, while one or more consumer threads retrieve those pointers, inspect and de-allocate the data structures.
The code in kern/asst1/producerconsumer_driver.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 unimplemented. Your job is to implement them.
Here's what you will see before you have implemented any code:
OS/161 kernel: 1c run_producerconsumer: starting up Consumer started panic: Assertion failed: item != NULL, at ../../asst1/producerconsumer_driver.c:108 (consumer_thread)
And here's what you will see with a (possibly partially) 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_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 data_item_t). 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 buffer structure and any synchronisation primitives you may need.
Suggestions on how to implement your solution
You must implement a data structure representing a buffer capable holds BUFFER_SIZE data_item_t pointers. 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 an item has been removed from the buffer using consumer_receive(). A simple way to implement this data structure is to use an array of pointers as provided, 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: The Ticket System
Marks: 10
This part simulates a ticket system where multiple ticket holder threads put their tickets into a single queue where validator threads dequeue the tickets, validate them, and return the tickets to the holder so the holder can continue.
Holders are in a loop that validate a number of tickets one after another. The code that drives the system is in ticket_system_driver.c. You should review the code to develop an understanding of the system. You'll see it starts a number of holder and validator threads and the waits for the holders to validate all their tickets. It then signals the validators to exit, waits, and completes. Ticket validation is simulated by updating a check field based on the ticket ID.
The holder and validator threads interact via the functions implemented in ticket_system.c. At a high level, these functions will queue tickets, and block and wake holders and validators based on when they can make progress. A more detailed specification of the each function is provided in the comments in the code itself.
Your task is to implement the functions such that the tick system will always execute correctly with all the tickets validated.
- Your solution should not busy-wait when a thread can't make progress.
- You should not rely on any changes to code in the ticket_system_driver.c or tick_system_driver.h files. It will be changed for testing. You can vary the code for your own testing purposes, but we'll replace them for our own testing.
The code as supplied fails as follows.
OS/161 kernel [? for menu]: 1d run_ticket_system: starting up Ticket holder 0 started panic: My ticket is corrupt or invalid
A potentially correct solution generates output similar to that below. Note: The order of starting and finishing, and the number of tickets validated by each validator will vary on each execution run. The total number of tickets validated will be 300 in the supplied code.
OS/161 kernel [? for menu]: 1d run_ticket_system: starting up Ticket holder 3 started Ticket holder 4 started Ticket holder 0 started Waiting for ticket holder threads to exit... Validator 1 started Ticket holder 6 started Ticket holder 8 started Ticket holder 1 started Ticket holder 7 started Ticket holder 2 started Ticket holder 5 started Validator 0 started Validator 2 started Ticket holder 9 started Ticket holder 3 finished Ticket holder 0 finished Ticket holder 4 finished Ticket holder 6 finished Ticket holder 8 finished Ticket holder 7 finished Ticket holder 1 finished Ticket holder 2 finished Ticket holder 5 finished Ticket holder 9 finished All 10 ticket holder threads have exited. Validator 2 finished validating 91 tickets Validator 0 finished validating 91 tickets Validator 1 finished validating 118 tickets All 3 validator threads have exited.
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 tests in the submission process, you may not receive any marks.
To submit your bundle:
% cd ~ % 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.