Synchronization Primitives (10Points)
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. The stub code also contains code templates for condition variables; you should ignore those parts.
Solving the Synchronization Problem (20 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 (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.
Synchronization Problem: Traffic Management at Podunk
You must solve this problem using the locks that you implemented above. Other solutions (condition variables, semaphores, etc.) 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 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.
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