Assignment 1
Assignment 1: Synchronisation
Due Date: 8am, Monday morning, 16th of April
Worth 25 marks (of the 100 available for the class mark component of the course)
The 10% bonus for one week early applies
The extra 5% bonus for a submitted, working assignment within 48 hours of release, also applies
Hard deadline is 7 days late, beyond which, submissions will not be accepted
See course intro for exact details. The notional release time is Midnight, Thursday, 22nd MarchContents
- Introduction
- Setting Up
- Begin Your Assignment
- Concurrent Programming with OS/161
- Tutorial Exercises
- Coding Assignment
- Generating Your Assignment Submission
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.
Please complete the reading exercises for your week 5 tutorial.
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."
Setting Up Assignment 1
Your group account
You will do Assignment 1 as part of a two-person group. If you are not yet in a group, post to the appropriate message board on the cs3231 forum to find a partner. You must nominate your partner, and he or she must nominate you, via the group nomination form (under "Administration" on the left-hand side).
After you and your partner have nominated each other, you will receive a group number via email. 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 group account
For assignment 0, you used the Darcs revision control system to keep track of changes and to produce a file that you could submit. For this assignment, you will also use Darcs. 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.
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.
Obtain the assignment sources
For this assignment, you will set up a Darcs repository in your group account directory (/home/osprjXXX). Start by getting a copy of the repository (remember to replace XXX with your group number!) Only one member of your group needs to do this:
% cd /home/osprjXXX % darcs get /home/cs3231/assigns/asst1/src asst1-src
Warning! Darcs sometimes takes a while to finish the checkout. Do not cancel it mid-way (by hitting CTRL-C or otherwise). If you do, your copy may be in an undefined state and you will get weird errors later!
Now you have a copy of the assignment. Unlike assignment 0, you won't use this copy directly. Instead you will check out your own working copy. Both you and your partner should do this:
% cd ~/cs3231 % darcs get /home/osprjXXX/asst1-src
You now have a working copy in your cs3231 directory, and are ready to start the assignment.
What you just did illustrates Darcs' decentralised nature. Any checkout is in fact a full working repository -- you can run darcs get from any checkout.
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 ASST1You 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 installIf you are told that the compile/ASST1 directory does not exist, make sure you ran config for ASST1. Run the resulting kernel:
% cd ~/cs3231/root % sys161 kernel sys161: System/161 release 1.1, compiled Jul 28 2003 17:28:51 OS/161 base system version 1.08 Copyright (c) 2000, 2001, 2002, 2003 President and Fellows of Harvard College. All rights reserved. Put-your-group-name-here's system version 0 (ASST1 #6) Cpu is MIPS r2000/r3000 1876k physical memory available Device probe... lamebus0 (system main bus) emu0 at lamebus0 ltrace0 at lamebus0 ltimer0 at lamebus0 hardclock on ltimer0 (10000 hz) beep0 at ltimer0 rtclock0 at ltimer0 lrandom0 at lamebus0 random0 at lrandom0 lser0 at lamebus0 con0 at lser0 pseudorand0 (virtual) OS/161 kernel [? for menu]:
Command Line Arguments to OS/161
Your solutions to ASST1 will be tested by running OS/161 with command line arguments that correspond to the menu options in the OS/161 boot menu.IMPORTANT: Please DO NOT change these menu option strings!
Here are some examples of using command line args 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 (";").
"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 KB of memory configured into System/161 by default. We suggest that you allocate at least 2MB of RAM to System/161. This configuration option is passed to the busctl device with the ramsize parameter in your ~/cs3231/root/sys161.conf file. Make sure the busctl device line looks like the following:
31 busctl ramsize=2097152Note: 2097152 bytes is 2MB.
If you don't have a sys161.conf from assignment 0 to modify (what
happened to it?) you can download an appropriate assignment 1 sys161.conf here.
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 awhile,
and then end together.
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:
1. What happens to a thread when it exits (i.e., calls thread_exit()
)? What about when it sleeps?
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.
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
synchronisation 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.
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.
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.
Tutorial Exercises
Please answer the following questions and bring them to your tutorial
in week 5.
Code reading
To implement synchronisation primitives, you will have to understand
the operation of the threading system in OS/161. It may also help you
to look at the provided implementation of semaphores. When you are
writing solution code for the synchronisation problems it will help if
you also understand exactly what the OS/161 scheduler does when it
dispatches among threads.
Thread Questions
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
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. Describe how thread_sleep() and thread_wakeup() are used to
implement semaphores. What is the purpose of the argument passed to
thread_sleep() ?
10. 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 familiarise you with some of
the problems that arise in concurrent programming and help you learn
to identify and solve them.
Identify Deadlocks
11. 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.
12. 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
13. 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
14. 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?
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. It is worth 30 marks of the 100 available for the class mark component of the course.
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.
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.1, compiled Feb 24 2003 21:57:51 OS/161 base system version 1.08 Copyright (c) 2000, 2001, 2002, 2003 President and Fellows of Harvard College. All rights reserved. Put-your-group-name-here's system version 0 (ASST1 #28) Cpu is MIPS r2000/r3000 848k physical memory available Device probe... lamebus0 (system main bus) emu0 at lamebus0 ltrace0 at lamebus0 ltimer0 at lamebus0 hardclock on ltimer0 (10000 hz) beep0 at ltimer0 rtclock0 at ltimer0 lrandom0 at lamebus0 random0 at lrandom0 lser0 at lamebus0 con0 at lser0 pseudorand0 (virtual) OS/161 kernel: 1a Starting 10 adder threads Adder threads performed 10000 adds Adder 0 performed 1008 increments. Adder 1 performed 1032 increments. Adder 2 performed 998 increments. Adder 3 performed 1017 increments. Adder 4 performed 1012 increments. Adder 5 performed 988 increments. Adder 6 performed 971 increments. Adder 7 performed 975 increments. Adder 8 performed 1027 increments. Adder 9 performed 972 increments. The adders performed 10000 increments overall Operation took 3.665222400 seconds OS/161 kernel: q Shutting down. The system is halted.
Library Synchronisation
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 and 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!!!!
You should have a very good idea of what you're 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. 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 "1b;q". Sample output from a working solution is included below.
sys161: System/161 release 1.12, compiled Mar 1 2006 21:58:56 OS/161 base system version 1.10 Copyright (c) 2000, 2001, 2002, 2003 President and Fellows of Harvard College. All rights reserved. Put-your-group-name-here's system version 0 (ASST1 #18) Cpu is MIPS r2000/r3000 1876k physical memory available Device probe... lamebus0 (system main bus) emu0 at lamebus0 ltrace0 at lamebus0 ltimer0 at lamebus0 hardclock on ltimer0 (10000 hz) beep0 at ltimer0 rtclock0 at ltimer0 lrandom0 at lamebus0 random0 at lrandom0 lser0 at lamebus0 con0 at lser0 pseudorand0 (virtual) OS/161 kernel: 1b Initialising the library M 6 going home after 10 loans M 2 going home after 10 loans M 1 going home after 10 loans M 5 going home after 10 loans M 8 going home after 10 loans M 9 going home after 10 loans M 3 going home after 10 loans M 4 going home after 10 loans M 0 going home after 10 loans M 7 going home after 10 loans L 1 going home after serving 33 borrow requests L 2 going home after serving 34 borrow requests L 0 going home after serving 33 borrow requests R 0 going home after serving 100 returns requests The library is closed, bye!!! Operation took 0.692078120 seconds OS/161 kernel: q Shutting down. The system is halted. sys161: 20927955 cycles (20912216k, 0u, 15739i) sys161: 8078 irqs 0 exns 0r/0w disk 0r/1172w console 0r/0w/1m emufs 0r/0w net sys161: Elapsed real time: 2.055073 seconds (10.1836 mhz) sys161: Elapsed virtual time: 0.837118200 seconds (25 mhz)
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 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?
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 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.
Create your design document to the top of the source tree to OS/161 (~/cs3231/asst1-src), and include it as follows.
% cd ~/cs3231/asst1-src % darcs add design.txt
When you later commit your changes into your repository, your design doc will be included in the commit, and later in your submission.
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.
Generating Your Assignment Submission
As with assignment 0, you will be submitting a Darcs .patches file.
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 % darcs push /home/osprjXXX/asst1-src
The above command will "push" any changes you have made using darcs record to your shared repository. Before pushing changes, it's a good idea to make sure your local copy is up-to-date by checking for changes made by your partner:
% cd ~/cs3231/asst1-src % darcs pull /home/osprjXXX/asst1-src
Darcs will find any changes made by your partner and incorporate them into your tree.
Now generate a .patches file.
% darcs send -o ~/asst1.patches /home/cs3231/assigns/asst1/src
Submitting Your Assignment
Now submit your assignment.% cd ~ % give cs3231 asst1 asst1.patchesYou're now done.