Description
Assignment 1: Multi-resource Synchronisation
Introduction
In this assignment you will solve a number of synchronization and locking problems. You will also get experience with data structure and resource management issues.
Please complete the reading exercises for your lecture 8 and 9.
Begin Your Assignment
Configure OS/161 for Assignment 1
Before proceeding further, configure your new sources.
% cd ~/asst1/src
% ./configure –ostree=~/os161/root
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 ~/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 make from compile/ASST0 . In ASST1, you run make from (you guessed it) compile/ASST1 .
% cd ../compile/ASST1
% make depend
% make
% make install
If you are told that the compile/ASST1 directory does not exist, make sure you ran config for ASST1. Run the resulting kernel:
% cd ~/cs161/root % ./sys161 kernel
sys161: System/161 release 2.0.8, compiled Jul 9 2018 11:30:58
OS/161 base system version 2.0.3\
352k 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 lhd0 at lamebus0 lhd1 at lamebus0 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 and the order in which threads run should not change the behaviour of your solution. Of course, your threads may print messages in different orders, but you should be able to easily verify that they follow all of the constraints applied to them and that they do not deadlock.
Built-in thread tests
When you booted OS/161 in ASST0, you may have seen the options to run the thread tests. The thread test code uses the semaphore synchronization primitive. You should trace the execution of one of these thread tests in GDB to see how the scheduler acts, how threads are created, and what exactly happens in a context switch. You should be able to step through a call to mi_switch() and see exactly where the current thread changes.
Thread test 1 ( ” tt1 ” at the prompt or tt1 on the kernel command line) prints the numbers 0 through 7 each time each thread loops. Thread test 2 (” tt2 “) prints only when each thread starts and exits. The latter is intended to show that the scheduler doesn’t cause starvation–the threads should all start together, spin for a while, and then end together.
Reading Exercises
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
- Describe how thread_sleep() and thread_wakeup() are used to implement semaphores. What is the purpose of the argument passed to thread_sleep() ?
- Why does the lock API in OS/161 provide lock_do_i_hold() , but not lock_get_holder() ?
Synchronisation Problems
The following problems are designed to familiarize you with some of the problems that arise in concurrent programming and help you learn to identify and solve them.
Identify Deadlocks
- 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
- 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 Queues
- The thread subsystem in OS/161 uses a queue structure to manage some of its state. This queue structure is not synchronised. Why not? Under what circumstances should you use a synchronised queue structure?
Describe (and give pseudocode for) a synchronised queue data structure based on the queue structure included in the OS/161 codebase. You may use semaphores, locks, and condition variables as you see fit. You must describe (a proof is not necessary) why your algorithm will not deadlock.
Make sure you clearly state your assumptions about the constraints on access to such a structure and how you ensure that these constraints are respected.
Coding Assignment
We know: you’ve been itching to get to the coding. Well, you’ve finally arrived!
Solving Synchronisation Problems
The following problems will give you the opportunity to write one 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). You are responsible for implementing the functions called.
Remember to specify a seed to use in the random number generator by editing your sys161.conf file, and run your tests using sys161 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.
Solving Synchronisation Problems
The following problems will give you the opportunity to write two 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). You are responsible for implementing the functions called.
Remember to specify a seed to use in the random number generator by editing your sys161.conf file, and run your tests using sys161 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.
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.
Paint Shop Synchronisation Problem
You’re in the middle of renovating your apartment and need to purchase some paint. You arrive at your local paint shop to find the shop in complete chaos. Customers are receiving empty cans of paint or paint with weird colors, the staff are fighting over the various tints used to color the paint, orders are getting lost, cans of paint mixed up, some customers are waiting forever for their can of paint, while others seems to get all the service.
Being an operating system expert, you quickly realize that the shop’s problems are related to concurrency issues between the customers and shop staff. You volunteer your services to provide a solution to the shop’s problems, reduce the chaos, and restore order to the store.
The Basic Paint Shop
To provide a solution, you must come to terms with the basic elements of the paint shop that you have to work with. The shop consists of a set of tints (such as RED, GREEN, BLUE) used to color paint. They are mixed with paint by shop staff in various ways according to customer requests. Customers bring their own empty paint can, record the tints they require on the can itself, and give the can to shop staff to mix the paint. The basic elements are defined in kern/asst1/paintshop_driver.h. The actions of customers and shop staff are defined in kern/asst1/paintshop_driver.c. See the file for detailed comments.
- Customers arrive with their paint can, write their requested colour on the can in terms of tints, submit their can as an order to the paint shop staff and wait.
Eventually their can returns with the requested contents (exactly as requested), they paint until the can is empty, take a short break, and do it all again until they have emptied the desired number of cans, then they go home.
- Shop Staff are only slightly more complicated than the customers. They take_orders, and if valid, they fill them and serve them. When all the customers have left, the staff go home.
An invalid order signals that the staff member should go home.
The function runpaintshop() is called via the menu in OS/161 (item 1b). runpaintshop() does the following:
- It initialises all the tint containers to have served zero doses.
- It calls paintshop_open, a routine you will provide to set up the shop.
- It then creates some threads to run as shop staff, 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 staff and customers to finish, after which we print out the tint statistics for the day.
- Finally, it calls paintshop_close, a procedure you provide to clean up when the shop has closed.
The function mix() takes a can and associated tint request and “mixes” the tints into the can such that the content is exactly as requested. The tints are represented by numbers, each number corresponds to the tint container number (and colour). The meaning of the tint numbers are defined in paintshop_driver.h.
You can assume that all the tint containers in the shop are infinite in size and hence will never be empty.
Have a quick look through both paintshop_driver.c and paintshop_driver.h to reinforce your understanding of what is going on (well, at least what is expected to go on).
