Assignment 1
Assignment 1: Synchronisation
Due Date: 8am, Monday morning, 5th of September
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 applies if you submit it before Friday, midnight.
See course intro for exact details.Contents
- Introduction
- Groups
- 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."
Groups
By default, we assume both group partners have done similar amount of coding, and we distribute the marks equally between both group members. However, if both of you agree, you can split the work (and the marks) differently (e.g., 40/60 instead of 50/50). In this case, you have to hand in a signed note to your tutor (or both tutors if you attend different tutes) stating how you want to split the marks before the end of the late submission deadline. If you can't agree on a fair split, contact your tutor. We will consult CVS logs to determine the distribution. If CVS hasn't been used, the split will be 50/50 (one more reason to use CVS). Please understand that we can't consider any complaints about group members after the deadline for the late submission has passed.Setting Up Assignment 1
Some more practice with CVS
At the end of the previous assignment, you would have committed the changes you made to the CVS repository and tagged as asst0-final.
You may have made some changes to the sources since then. To check this you can use the following command
% cd ~/cs3231/asst0-src % cvs -q -n update M kern/main/main.c %
A short note on the arguments to cvs:
- -q means "be quiet". Don't show the directories cvs traverses while it works.
- -n means "no action". It means go through the motions of performing the command, but don't actually change anything. -n is a great way to test something you might want to do, but that you are not sure of the consequences of.
- update requests cvs to update your version of the sources with the latest version in your repository.
Note that in our example, we have modified (M) the kern/main/main.c file since the last commit. The output above might be different for you. It may be empty, in which case you have not made any changes since asst0 finished.
If you have made changes, decide whether you wish to keep them to play around with later, or whether you simply wish to throw them away. If you wish to keep them, you should commit your changes back to the repository using cvs commit.
Now remove your asst0-src tree to prepare for this assignment (yes really).
% cd ~/cs3231 % rm -rf asst0-srcNote you can get your original tree back at anytime by running cvs checkout asst0-src. Feel free to test this if you wish, but make sure you remove it again before proceeding further. Never delete (or cvs init) your repository in /home/osprj000/cvsroot, as you will not be able to retrieve your past work.
We assume that the remainder of the ~/cs3231 directory is in place from the previous assignment, and that your umask, PATH and CVSROOT are still set appropriately.
Obtaining and setting up ASST1 in CVS
In this section, you will be setting up the cvs repository that will contain your code. Only one of you needs to do the following. We suggest your partner sit in on this part of the assignment.- Check your umask is still set appropriately.
% umask 0007 %
If not, you have done something wrong with your umask setup and need to fix it. - Check your CVSROOT environment variable as below.
% echo $CVSROOT /home/osprj000/cvsroot %
If your CVSROOT is not an appropriately modified version of the above, then you will need to fix it. - Now import the OS/161 sources into your repository as follows
% cd /home/cs3231/assigns/asst1/src % cvs import -m "Initial import of asst1 OS/161 sources" asst1-src os161 asst1-base
- We'll assume from your cs3231 directory is intact
from the previous assignment. Change to your directory.
% cd ~/cs3231
- Now checkout a copy of the os161 sources to work on from your
shared repository.
% cvs checkout asst1-src
- You should now have a asst1-src directory to work on.
You are now ready to start the assignment.
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.
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.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.
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 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=1We 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
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
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?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!This is the assessable component of this assignment. It is worth 25 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.
Implementing Pipes
Your task is to implement thread communication channels inspired by (but not the same as) Unix pipes as discussed in the lecture. You have to implement the following five functions:- Create a new pipe, return a handle to the in-pipe and
out-pipe.
int pipe_create (pipe_in **p_in, pipe_out **p_out);
The pipe has a capacity of MAX_PIPE_SIZE (defined in pipe_def.h) bytes it can buffer at any point in time. However, it should be possible to write messages of arbitrary size into the pipe (see below). - Destroy in-pipe, and free all memory associated with it.
int pipe_destroy_in (pipe_in *p);
Any attempt to read from the pipe or write to the corresponding in-pipe may lead to undefined behaviour. - Destroy out-pipe, and free all memory associated with it.
int pipe_destroy_out (pipe_out *p);
Any attempt to read from the pipe or write to the corresponding in-pipe may lead to undefined behaviour. - Write n bytes from src to in-pipe:
int pipe_write (pipe_in *p, void *src, int n);
If the message size exceeds the available space in the buffer, the writer thread blocks until space is available again. You have to make sure that no other writer thread gets access to the pipe until the current writer thread finished writing the message. - Write n bytes from in-pipe to dst to
int pipe_read (pipe_out *p, void *dst, int n);
In case of an underflow (less than n bytes in the buffer), the reader thread blocks until another writer thread has successfully written to the pipe. No other reader should get access to the pipe until the first reader finished reading the message.
You will have to modify pipes.c and pipe_def.h to implement your solution. However, you may not change the prototypes in pipes.h.
For testing, we will replace pipes_driver.c This is a variant of the consumer/producer problem discussed in the lecture. You might want to start by implementing a simplified version of pipes which behaves exactly like the circular buffer in the consumer/producer problem.
% sys161 kernel "1b;q" sys161: System/161 release 1.12, compiled Mar 8 2005 21:30:24 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 #32) Cpu is MIPS r2000/r3000 1880k 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]: 1 creating pipe pipe created Writing to pipe Done Read "What's in the pipe?" from pipe All done, bye!!! Operation took 0.021304320 seconds OS/161 kernel [? for menu]:
Before Coding!!!!
You should have a very good idea of what your 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?
- Who shares what resources?
- Who produces what and who consumes what?
- What states can the various resources be in?
- How does your solution prevent deadlock or starvation?
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 tour operators participate?
- Can tourists from different operators eat in parallel if they do not require the same tables?
- 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 in cvs as follows.
% cd ~/cs3231/asst1-src % cvs 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 again will be submitting a diff of your changes to the original tree.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 % cvs commitIf the above fails, you may need to run cvs update to bring your source tree up to date with commits made by your partner. If you do this, you should double check and test your assignment prior to submission.
Now tag the repository so that you can always retrieve your current version in the future.
% cd ~/cs3231/asst1-src % cvs tag asst1-finish
Now generate a file containing the diff.
% cvs -q rdiff -r asst1-base -r asst1-finish -u asst1-src > ~/asst1.diff
Submitting Your Assignment
Now submit the diff as your assignment.% cd ~ % give cs3231 asst1 asst1.diffYou're now done.
Note: If for some reason you need to change and re-submit your assignment after you have tagged it asst0-final, you will need to either delete the asst0-final tag, commit the new changes, re-tag, and re-diff your assignment, or choose a different final tag name and commit the new changes, tag with the new tag, and re-diff with the new tag. To delete a cvs tag, use
% cvs rtag -d asst0-final asst0-src