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.

This project has two parts with two distinct deadlines: Part 1 is due by March 10 and it consists ofyour answers to code reading questions, declaration of your project partner (if any), and a short progress report. Part 2 is due by March 29 and it consists of your coding solutions (the programming part) and a design     document.

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/571   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/571 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 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

Copy necessary files

For this assignment, you need to replace three ofyour existing files as follows:

The updated versions of these files can be found in the /usr/local/shared/cs471/PA1 directory on Zeus.

1. cd ~/os161/os161-1.11/kern

2. cp /usr/local/shared/cs471/PA1/menu.c main/

3. cp /usr/local/shared/cs471/PA1/test.h include/

4. cp /usr/local/shared/cs471/PA1/stoplight.c asst1/

You must replace these three files accurately before you start coding the solution.

Tag your Git Repository

Before you do any real work on this assignment, tag your Git 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 git commit to get your tree committed in the state from which you want to begin this assignment.

% git commit -am "End of project-0"

% git push

Now, tag your repository as shown below.

% cd ~/os161/os161-1.11

% git tag asst1-begin

NOTE 1: Tags are not pushed to remote GitLab repo by default. This means if you work in a group on this project, you and your partner both need to run “git tag asst1-begin”  separately.

NOTE 2: If you are working with a partner, you may want to set up the GitLab repository so that it may be accessed by both members ofyour group. In case you have not setup GitLab, the instructions for the initial setup can be found here:

https://mason.gmu.edu/~zan2/gitlab_setup.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/stoplight.c) 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/2.0.8

IMPORTANT:  You should remember to issue the module load command above every time you logon to zeus when you intend to work on os161!  (the command will only work on zeus.vse.gmu.edu).

First method: This is based on running a script provided by the TA. Give the following command to get the script file.  The scripts folder should exist after following the steps for PA0.  If not, you can create it.

% cd ~/os161

% cd scripts

% cp /usr/local/shared/cs471/scripts/build-asst1.php .

Then run this php file in your scripts directory by typing

% php build-asst1.php

Warnings and Errors in the build will be output to ~/os161/scripts/os161_errors.txt 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: DO NOT change the 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 (located under ~/os161/root/) . 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    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.

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

OS/161 uses this random number generator to randomly vary the timing of the context switches, to allow for some randomness in the scheduling.  Even with the same seed, the time you spend in the menu will

make a very large number of calls to the random number generator, which means if you run the system normally, your seed will not appear to give you the same results every time you run your stoplight

program.

To address this, if you are using a fixed seed, you will need to run the OS/161 by launching your stoplight program immediately, bypassing the menu.  To do this, simply execute the following from your                ~/os161/root directory:

% sys161 kernel 1c

This command will run the stoplight program (test 1c) without spending any time in the menu, giving you a deterministic set of random selections using your fixed seed.  This also implies that if you wish to run    your stoplight program again with the same seed, you will need to quit OS/161 and re-launch it with this  command.

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. Part 1 (15 points)

Code reading

Please answer the following questions and save your answers in a file named “code-reading.txt” .

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 ifyou 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?

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()? Once you finish the code reading questions, create a second file named “progress-report.txt”

In that file, first give the full names and G numbers of the team members who decided to collaborate in   project PA1 (see the “Working with a partner” paragraph in Section 1 of the hand-out for the rules governing partner selection).  Then, in the same file, give a short (around one-page) summary of the        progress you made on the design and coding part of your project. Do not provide any code; just summarize your efforts. While you are not required to submit any code in Part 1, you are expected to     begin thinking about overall design and also start coding – implementation of the locks could be a good  target. In the progress report, you should summarize your efforts towards that goal (for example, you can describe your efforts towards implementing/testing locks.)

Finally, briefly explain the responsibilities of the team members in Part 2 of the project (the coding part). Failure to submit the progress report may result in deduction of points.

You can work with a partner in Part 2 (Coding Part) below only if that student’s name is explicitly stated in Part 1 submission in a timely manner.

Submission of Part 1:

Create a directory called ‘asst1-part1’, inside the ‘~/os161/’ directory.

% cd ~/os161/

% mkdir asst1-part1

When both code-reading.txt andprogress-report.txt files are ready, put these two files in it. Next, tar and compress your asst1-part1 directory.

% cd ~/os161

% tar -czf uid1_uid2-asst1-part1.tar.gz asst1-part1

You 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-part1.tar.gz. Submit the compressed     Part 1 file on Blackboard. All members of a group must submit separately the same compressed file, and before the Part 1 deadline 3/10 11:59 PM . Make sure to coordinate.  Make sure to double check that you are submitting the correct file  -- if you submit wrong, corrupt, or empty file you are likely to get zero.

Late penalty for Part 1 will be 15% for each day. Submissions made on March 13 or later will not get credit. Please plan in advance.

You can make multiple submissions; 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.

Note: The contents of Part 1 should be submitted separately from Part 2, and in a timely manner.

5.  Part 2 - Coding  Solution and Design Document (85 points)

Synchronization Primitives (20/85 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. You 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 (or condition variables) in any way (i.e., do not call    any semaphore or cv functions in your lock implementation). The stub code also contains code templates for condition variables; you should ignore those parts.

Solving the Synchronization Problem (55/85 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.

Please note: Since the kernel calls the lock functions during boot-up, if you have a partial implementation, or have an error in your lock implementation, the kernel may either hang or terminate early without menu input options.  This is probably happening because ofyour lock implementation.  You need to complete/fix your lock implementation first.

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 (typing “1c”) 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).  Note: typing '?t' on the kernel command line will show the full test list in os161 and then use 'sy2' on the kernel command line to test your lock implementation. You can ignore the ‘elapsed time’ information displayed by those tests.

If your lock implementation is correct, the ‘sy2’ command will print ‘lock test done’ along with the elapsed time, but without any garbled characters.  If you see garbled characters in the output of ‘sy2’, that means there is an error in your lock implementation.

Synchronization Problem: Traffic Management at Podunk

You must solve this problem using the locks that you implemented above along with

thread_sleep() and thread_wakeup ()functions.

Other solutions (condition variables, semaphores, etc.) are not acceptable.

Your solution shouldn’t use busy waiting either.

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 three-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 purpose of this problem we will model the intersection as shown above, dividing it into three         portions (AB, BC, CA) and identifying each portion with the names of the lanes entering/leaving the         intersection through that section. (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 or two portions of the intersection (for         simplicity assume that U-turns do not occur in the intersection). So if a car approaches from Route-A,       depending on where it is going, it proceeds through the intersection as follows:

●    Right: AB

●    Left: AB-BC

In addition to “Cars”, there are also “Trucks” in Podunk. Trucks have a lower priority than cars when        entering the intersection. If a lane in a given route has both cars and trucks in it, then the cars should cross the intersection before the trucks in that route. When no more cars are waiting, then the trucks on that lane can cross the intersection. It is fine if some trucks suffer starvation (i.e., cross last). Note that, cars have    higher priority than trucks approaching the intersection through the same route (Route-A, Route-B, or       Route-C). For example, if there are six vehicles (four cars and two trucks) approaching the intersection     through Route-A, the two trucks should not start to cross before any of the four cars.

Before you begin coding, answer the follow questions in a file named exercises.txt (to be submitted in Part 2, along with your code):

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?

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 three-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. You only need to work with stoplight.c

We have given you the model for the intersection. The following are the requirements for your solution:

●    Each vehicle “approaches” the intersection when the corresponding thread is created,  it “enters” the intersection when the conditions are right for it to proceed (see below),  and after crossing the intersection, it  “leaves” . No two vehicles can be in the same portion of the intersection at the     same time. (In Podunk they call this an accident).

●     Cars have a higher priority than trucks. Before proceeding to (entering) the intersection, the        trucks in a given lane must wait until all cars (which have already approached) on that lane have entered the intersection.

●    Your solution must improve traffic flow without allowing traffic from any direction to starve       traffic from any other direction. However, as per the spec, the trucks are supposed to proceed last in a given lane and that is how you should implement (i.e., extended waiting experienced by the  trucks in the presence of cars is not a problem).

●     For full credit, your solution should maximize concurrency across threads and should not impose  unnecessary delays not imposed by the constraints given above. For example, while a vehicle X is crossing the intersection, it should not unnecessarily delay the entry of another vehicle                  (approaching from the same route or different route) to the intersection if the other constraints of the problem are not violated. Similarly, having the vehicles cross the intersection one by one is not acceptable.

●    A truck must not wait for cars which have not approached yet (because this will incur                    unnecessary delay.) A truck can (and should) enter the intersection if its path does not cause a car to get delayed. A truck should not wait for any “future” cars which have not yet approached the   intersection. In other words, generating all the vehicles approaching a given lane first, putting      them in priority order (cars first), and only then allowing the vehicles to proceed to the                  intersection is not acceptable.

●     Each vehicle should print a message as it approaches, enters, and leaves the intersection                indicating the vehicle number, vehicle type (car or truck), approach direction and destination        direction. You should also print messages to clearly show when a vehicle is in a specific portion  (AB, BC, CA) of the intersection.  The messages should unambiguously describe all the events in the intersection with proper ordering. 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 vehicle thread execution order cannot be clearly followed will not receive substantial scores.

Your code should be based on the locks that you implemented, along with the thread_sleep() and thread_wakeup () functions.   Using other synchronization primitives or resorting to busy waiting is not allowed.  This last constraint implies that a vehicle thread that cannot make progress in the                 intersection should not keep continuously checking the condition; instead, it should suspend its execution (using thread_sleep()) to enable other threads to execute on the processor. Later, it should be      awakened by calling thread_wakeup (). The thread may need to re-check the condition when it is   awakened before proceeding; that is acceptable.  Of course you are allowed to call other thread functions to create and terminate threads in your program.

The driver for the Podunk Traffic problem is in (the version that you updated from Blackboard)           ~/os161/os161-1.11/kern/asst1/stoplight.c (a not so subtle hint about one possible solution). It consists of createvehicles() which creates 20 vehicles and passes them to               approachintersection() which assigns each a random direction. It also assigns each vehicle a random type as ‘car’ or ‘truck’ . We assigned them a random turn direction as well. The file                  stoplight.c also includes routines 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 (and truck) threads have completed; this is part of the synchronization problem you are solving!

Design document (10/85 points):

A component of your PA1 submission will be a design document, that will provide an overview of your synchronization problem solution that you implement. Put your design answers in a separate file named design.txt, and submit as part of your Part 2 submission (you can also submit a pdf design             document file, ifyou want to). A 2-page design document should be sufficient to convey the main         features of your approach.

In your design document, after giving a high-level overview of your solution, explain:

i.)  How many locks you used in your program and for what purpose(s),

ii.) How you achieved the objective of giving high-priority to cars (compared to trucks); explain what type of data structures and synchronization primitives you used for that purpose

iii.) Specific rules you implemented to admit, suspend, and wake up a vehicle thread, approaching  the intersection from a specific lane: you may want to list separate cases you considered.

In the design document, you should not “copy” your C code: someone reading the document should be able to understand the main logic without having to inspect your C code if they are familiar with locks, and thread sleep/wakeup functionalities.

6. Recommendations

If this is your first multi-threaded programming project (likely to be the case for most students) make sure to allocate sufficient time, in particular for testing and debugging. It’s not uncommon to spend very          significant time on debugging first multi-threaded programs, because it takes time to adjust to thinking     with multiple threads executing the same program. That is why you are given several weeks to complete  this project.

It is our strong recommendation that you develop the solution to the traffic management problem             incrementally to make debugging a tractable task; for example,  by developing and testing the locks, then modeling the intersection by allowing the vehicles to cross in any order, ignoring the “accidents”, and     printing the events properly. While that is not an acceptable solution to the project, it will give you good know-how about creating threads and displaying their progress at run-time, so that you can proceed with confidence.

In the next phase, you can update your solution to prevent accidents, and when successful, you can add     high priority to cars.  Finally, you can make sure that your solution maximizes concurrency across threads and doesn’t impose any unnecessary delay.

All these phases require good planning and working according to a timetable through several weeks. Last- minute scrambles are known to be not very helpful in multithreaded projects.

7. 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 server.  Your programs will be tested on zeus.vse.gmu.edu (no exceptions!).

Submission  for Part 2:

When you are finished, creating a directory called ‘asst1-part2’, inside the ‘~/os161/’ directory.

% cd ~/os161/

% mkdir asst1-part2

Make sure you commit your latest working copy first:

% cd ~/os161/os161-1.11/

% git commit -am "Completed project-1"

Tag your latest working copy and run a diff:

% git tag asst1-end

% git diff asst1-begin asst1-end > ../asst1-part2/asst1.diff In the ‘asst1-part2’ directory, you should place the following:

asst1.diff: a diff file listing all the changes you made for this assignment.

your sys161.conf file.

exercises.txt: your answers to the written synchronization exercises (do NOT include code- reading.txt)

design.txt: your 2-page design document.

Next, tar and compress your asst1-part2 directory AND your entire source tree.

% cd ~/os161