Table of contents
CS 471 Operating Systems Fall 2019
Programming Assignment 1 (PA1): Due date: Friday, October 18, 11:59 pm
1. Introduction
2. Begin your assignment
3. Concurrent Programming with OS/161 4. Written Exercises (25 points)
5. Coding Exercises (75 points)
6. Coding style, submission and grading
1. Introduction
We finished the discussion of threads and general synchronization in class, and you became familiar with the basic OS/161 environment in the first assignment (PA0). In this assignment you will implement synchronization primitives for OS/161 and learn how to use them to solve a synchronization problem. Once you have completed the written and programming exercises you should have a fairly solid grasp of the pitfalls of concurrent programming and synchronization.
To complete this assignment you will need to be familiar with the OS/161 thread code. The thread system provides interrupts, control functions, and semaphores.
Note that in addition to developing non-trivial synchronization code in C, you will need to again do some code reading and directory exploring in OS/161. This is normal. Considering that debugging synchronization programs requires also more time, make sure to allocate sufficient time from the beginning – if you start just a few days before the due date, you are likely to experience significant difficulties.
Working with partner
In this assignment you can – and you are ENCOURAGED to – work with a partner: another CS 471 student from your own section. No team can have more than two members. If you have worked alone in Project 0, you can form a team with another CS 471 student who worked alone in Project 0. You can also continue to work with the same partner you worked with in Project 0 (however, you cannot switch to a new partner). If believe you can finish it without a partner, you are welcome to work alone; but there will not be any bonus points for those working alone, and you should keep in mind that the assignment
1
specification has been developed assuming that two students will actively interact and cooperate in exploring OS/161 and developing a synchronization program.
2. Begin your assignment
Tag your CVS Repository
Before you do any real work on this assignment, tag your CVS repository. The purpose of tagging your repository is to make sure that you have something against which to compare your final tree. Make sure that you do not have any outstanding updates in your tree. Use cvs commit to get your tree committed in the state from which you want to begin this assignment.
% cvs commit -m “End of project-0”
Now, tag your repository as shown below.
% cd ~/os161
% cvs tag asst1-begin os161-1.11
NOTE: If you are working with a partner, you may want to set up the CVS repository so that it may be accessed by both members of your group. The steps to achieve that objective can be found at: https://cs.gmu.edu/~yuecheng/teaching/cs471_fall19/_static/os161/os161_cvs_share.html
Configure OS/161 for ASST1
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 that can be used to execute the 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 ~/os161/os161-1.11/kern/conf
% ./config ASST1
You should now see an ASST1 directory in the compile directory.
Building for ASST1
As in PA0, in order to build kernel, you have two options. You can use the php file provided by the TA or use the alternative method. Before starting any of the methods,make sure to issue the module load command
% module load sys161/1.14
2
IMPORTANT: Youshouldremembertoissuethemoduleloadcommandaboveeverytimeyoulogonto zeus when you intend to work on os161 !
In the first method, you must enter the following:
% wget http://mason.gmu.edu/~aroy6/build-asst1.php
% php build-asst1.php
Or as the second method, you can run make from compile/ASST1.
% cd os161-1.11
% ./configure –ostree=$HOME/os161/root
% cd kern/conf
% ./config ASST1
% cd ~/os161/os161-1.11/kern/compile/ASST1
% make depend
% make
% make install
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!
“Physical” Memory
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 sys161.conf file. Make sure the busctl device line looks like the following:
31 busctl ramsize=2097152 (Note: 2097152 bytes is 2MB).
3. Concurrent Programming with OS/161
If your code is properly synchronized, the timing of context switches and the order in which threads run should not change the behavior of your solution. Of course, your threads may print messages in different orders, but you (and we!) 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
3
thread tests in GDB to see how the scheduler acts, how threads are created, and what exactly happens in a context switch. Y ou 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.
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=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.
4. Written Exercises (25 points)
Please answer the following questions and submit them with your assignment in code-reading.txt.
Code reading
To implement synchronization 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 synchronization problems it will help if you also understand exactly what the OS/161 scheduler does when it dispatches among threads. Place the answers to the following questions in code-reading.txt.
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?
4
3. What does it mean for a thread to be in each of the possible thread states?
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?
Synchronization 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()?
5. Coding Exercises (75 points)
Synchronization Primitives (20/75 Points)
Implement (mutual exclusion) locks for OS/161. The interface for the lock structure is defined in kern/include/synch.h. Stub code is provided in kern/thread/synch.c. Y ou can use the implementation of semaphores as a model, but do NOT build your lock implementation on top of semaphores; your code should not use semaphores in any way. The stub code also contains code templates for condition variables; you should ignore those parts.
Solving the Synchronization Problem (55/75 Points)
The following problem will give you the opportunity to write some fairly straightforward concurrent programs and get a more detailed understanding of how to use threads to solve problems. We have provided you with basic driver code that starts a predefined number of threads. You are responsible for what those threads do. Remember to specify a seed to use in the random number generator by editing your sys161.conf file. 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. For example, you will see an option for “lock variables”; you can choose that option to see if your lock implementation is correct or not. Similarly by invoking the “stoplight.c” option in the menu, you can run an initial test for your driver code stoplight.c implementation (The grader is likely to run additional tests; but you can consider these as initial tests).
5
Synchronization Problem: Traffic Management at Podunk
You must solve this problem using the locks that you implemented above. Other solutions are not acceptable.
Traffic through the main intersection in the town of Podunk, KS has increased over the past few years. Until now the intersection has been a four-way stop but now the impending gridlock has forced the residents of Podunk to admit that they need a more efficient way for traffic to pass through the intersection. Your job is to design and implement a solution using the synchronization primitives (locks) that you have developed in the previous part.
Modeling the intersection
For the purposes of this problem we will model the intersection as shown above, dividing it into quarters and identifying each quarter with which lane enters the intersection through that portion. (Just to clarify: Podunk is in the US, so we’re driving on the right side of the road.) Turns are represented by a progression through one, two, or three portions of the intersection (for simplicity assume that U-turns do not occur in the intersection). So if a car approaches from the North, depending on where it is going, it proceeds through the intersection as follows:
● Right: NW
● Straight: NW-SW
● Left: NW-SW-SE
Before you begin coding, answer the follow questions in exercises.txt:
1. Assume that the residents of Podunk are exceptional and follow the old (and widely ignored) convention that whoever arrives at the intersection first proceeds first. Using the language of synchronization primitives describe the way this intersection is controlled. In what ways is this method suboptimal?
6
2. Now, assume that the residents of Podunk are like most people and do not follow the convention described above. In what one instance can this four-way-stop intersection produce a deadlock? (It will be helpful to think of this in terms of the model we are using instead of trying to visualize an actual intersection).
Implementing your solution
The file you are to work with is in ~/os161/os161-1.11/kern/asst1. Ignore catsem.c and catlock.c. Y ou only need to work with stoplight.c
We have given you the model for the intersection. The following are the requirements for your solution:
● No two cars can be in the same portion of the intersection at the same time. (In Podunk they call this an accident).
● Residents of Podunk do not pass each other going the same way. If two cars both approach from the same direction and head in the same direction, the first car to reach the intersection should be the first to reach the destination.
● Your solution must improve traffic flow without allowing traffic from any direction to starve traffic from any other direction.
● Your solution should maximize concurrency across threads. For example, while a car X is crossing the intersection, it should not unnecessarily delay the entry of another car (whose trajectory does not conflict with that of the car X) to the intersection.
● Each car should print a message as it approaches, enters, and leaves the intersection indicating the car number, approach direction and destination direction. This message is very important and it is your task to make sure that the message is displayed with clarity to allow the grader to follow all the events! (If necessary use synchronization primitives to enforce clear printing). Projects whose car thread execution order cannot be clearly followed will not receive substantial grades.
Your code should be based on the locks that you implemented. Using other synchronization primitives or resorting to busy waiting is not allowed.
The driver for the Podunk Traffic problem is in ~/os161/os161-1.11/kern/asst1/stoplight.c (a not so subtle hint about one possible solution). It consists of createcars() which creates 20 cars and passes them to approachintersection() which assigns each a random direction. We forgot to assign them a random turn direction; please do this in approachintersection() as well. The file stoplight.c also includes routines gostraight(), turnright() and turnleft() that may or may not be helpful in implementing your solution. Use them or discard them as you like.
Please note: The OS-161 menu should not appear on the screen until all the car threads have completed; this is part of the synchronization problem you are solving!
7
6. Coding style, submission and grading
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. Since you will be working in pairs, it will be important for you to be able to read your partner’s code. Also, since you will be working on OS/161 in a future assignment, you may need to read and understand code that you wrote several weeks earlier. Finally, clear, well-commented code makes your TA happy!
Here are some general tips for writing better code:
● 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 an eligible car” is much more informative than one that says “Find the first non-zero element of array.”
You and your partner will probably find it useful to agree on a coding style – for instance, you might want to agree on how variables and functions will be named since your code will have to interoperate.
Working Environment
You will need to develop your code on zeus linux cluster of VSE. Your programs will be tested on zeus (no exceptions!).
Submission
When you are finished create a directory called ‘asst1’, inside the ‘~/os161/’ directory.
% cd ~/os161/
% mkdir asst1
Make sure you commit your latest working copy first:
% cvs commit -m “Completed project-1”
Tag your latest working copy and run a diff:
% cvs tag asst1-end
% cvs diff -r asst1-begin -r asst1-end > asst1/asst1.diff
In the ‘asst1’ directory, you should place the following:
asst1.diff: a diff file listing all the changes you made for this assignment. yoursys161.conf file.
8
code-reading.txt: your answers to the code reading questions. exercises.txt: your answers to the written synchronization exercises.
Next, tar and compress your asst1 directory AND your entire source tree.
% cd ~/os161
% tar -czf uid1_uid2-asst1.tar.gz os161-1.11 asst1
Y ou should replace uid1 and uid2 with you and your partner’s GMU email IDs. If you are working alone, the last line should read tar -czf uid-asst1.tar.gz. Submit the compressed file on Blackboard. All members of a group must submit separately the same compressed file, and before the deadline. Make sure to coordinate.
You can make as many submissions as you like; we will consider ONLY the last submission that you make; so in case you need to re-submit, make sure the compressed file contains all the components listed above.
Questions
Programming – and system-related questions about the project should be directed to the GTA of your own CS 471 section:
Section 001 (Instructor: Prof. Aydin) Section 002 (Instructor: Prof: Cheng) Section 003 (Instructor: Prof. Pathak)
GTA: Jixuan Zhi (jzhi@masonlive.gmu.edu)
GTA: Zhemin An (zan2@masonlive.gmu.edu)
GTA: Adiitya Venkateshwaran (avenkat@masonlive.gmu.edu)
But keep in mind that code-reading and exploring the OS/161 kernel files is a component of the assignment, so you should not expect detailed explanations of how the OS/161 kernel functions work (including the thread functions). Conceptual questions about the Podunk Traffic Synchronization problem specification can be directed to the instructor of your own section.
Grading
This programming assignment accounts for 12% of your final grade. Late penalty for this assignment will be 15% for each day. Projects that are late by 3 or more days (i.e., those submitted on October 21 or later) will not be accepted. Please plan in advance.
Finally, again remember that the debugging multi-threaded programs take time and the zeus server tends to be rather slow on the project due dates. So do not postpone this project to the last week or days.
Good luck!
9