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. Modeling the intersection Route-C BC CAAB Route-B Route-A 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-tums 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 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? 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: 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 the intersection, the trucks in a given lane must wait until all cars 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., starvation of the trucks 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. 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. Using other synchronization primitives or resorting to busy waiting is not allowed. This last constraint implies that a vehicle thread which can not make progress in the intersection should not keep continuously checking the condition; instead it should suspend its execution to enable other threads to execute on the processor. It is your task to figure out how to achieve that objective efficiently. 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 approach intersection () 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.