Assignment 2: Synchronization

• Points 8
•
Overview
For this assignment, we're going back to the realm of user mode programming. In this
assignment, you will work with synchronization primitives to implement a guidance system for
traffic simulation.
Autonomous (Self-driving) cars are increasingly becoming more reliable, as development of
smart technologies help better guide the vehicle through its environment safely. Autonomous
cars depend on several sensors and complex logic to coordinate with other vehicles in a safe
manner. At an intersection for example, cars must have a policy to coordinate crossing the
intersection in order to avoid crashes and to ensure that everyone goes through the intersection
eventually.
Your job is to implement synchronization in a traffic system that coordinates cars moving
through two types of intersections: stop signs and traffic lights, by enforcing ordering between
car arrivals in the same lane, avoiding potential crashes, and avoiding deadlocks.
Details
Each car is implemented as a separate thread, so synchronization is needed to prevent collisions
and data structure corruption and race conditions as it passes through an intersection. A car is
defined by two parameters:
• position or the direction from which is starts (NORTH, SOUTH, EAST, WEST)
• action or how it passes through the intersection (STRAIGHT, RIGHT_TURN,
LEFT_TURN)
Because both the stop sign algorithm and the traffic light algorithm share many common
functions, we have implemented both in a single program. Your task is to complete the
implementation of safeStopSign.c and safeTrafficLight.c by adding the
appropriate synchronization. You should use locks and condition variables (not semaphores).
Stop Sign
There are four entrance lanes and four exits to the intersection, each corresponding to a cardinal
direction: North (N), South (S), East (E) and West (W). Each entrance into the intersection is
referred to as a lane and the intersection itself is broken into four quadrants. Depending on the
action, a car may pass through between one (right turn) and three (left turn) quadrants. A car may
enter and perform its action provided that the quadrants it would pass through are completely
clear of other cars (assume that a car occupies all quadrants required by the action until finishes
moving through the intersection), including any from the same direction.
In the stop sign simulation, each car thread follows 3 steps: (see runStopSignCar() in
safeStopSign.c)
1. Enter the proper entry lane. (See enterLane in intersection.c)
2. Move through the intersection. (See goThroughStopSign in stopSign.c)
3. Formally exit the simulation area (having already moved through the quadrants where
collisions can happen); ensure that cars from the same entry lane exit the simulation area
in the same order they entered their entry lane. (See exitIntersection in
intersection.c)
Traffic Light
In the traffic light scenario, there are twelve entrance and exit lanes: one for each possible
combination of direction and action. For example, depending on the action, a car entering from
East may enter a left-turn lane, straight lane or right-turn lane. Unlike in stop sign, the only
requirements for a car to enter the intersection is that it be in a lane and that the traffic light is
green for its direction. Likewise, due to the arrangement of the lanes, the only danger of collision
comes from left-turns. A vehicle wanting to make a left-turn first enters the intersection and then
when there are no cars starting from the opposite direction going straight in the intersection,
makes its left turn.
To simplify things, the traffic light has just three states: green for N-S (red for E-W), green for EW (red for N-S) and red all-ways. (There is only one traffic light. ) After a variable number of
cars enter the intersection, the signal immediately turns red (there's no yellow light). Once red,
and once all the cars that entered while it was green have moved through, the light turns green
for either N-S or E-W. Note that you are not allowed to assume that the light will turn green for
the opposite orientation as before (you could see Green N-S - Red - Green N-S).
In the traffic light simulation, each car thread follows 5 steps: (see runTrafficLightCar()
in safeTrafficLight.c)
1. Enter the proper lane. (See enterLane() in intersection.c)
2. Enter the intersection when safe. (See enterTrafficLight() in
trafficLight.c)
3. While inside the traffic light intersection: confirm it is safe to make the desired move.
(See actTrafficLight() in trafficLight.c)
4. Move through the intersection. (See actTrafficLight() in trafficLight.c)
5. Formally exit the simulation area (having already moved through the main part of the
intersection, where collisions can happen); ensure that cars from the same entry lane exit
the simulation area in the same order they entered their entry lane. (See
exitIntersection in intersection.c)
Implementation
Your task is to add synchronization to the functions, runStopSignCar() and
runTrafficLightCar() in SafeStopSign.c and SafeTrafficLight.c
respectively. You should also add members to the SafeStopSign and SafeTrafficLight
structs defined in SafeStopSign.h and SafeTrafficLight.h respectively as needed.
You can also add more structs if you need to, but you should not change any other starter code
files.
The code you write is part of a larger simulator framework. Starting in carsim.c, the program
runs test cases defined in testing.c. These in turn will run your logic from
SafeStopSign.c and SafeTrafficLight.c. The simulator is designed in a way that
will help detect synchronization problems. When a car performs actions such as moving through
intersections, its thread will sleep to simulate the time taken by the action. This also provides an
opportunity to detect collisions, etc. Also, when a car performs some actions, the framework will
provide it with a token. These are validated later to detect corruption or incorrect usage.
As mentioned above, you must also ensure proper lane ordering. If two cars that enter in the
same lane, A and B, call enterLane() in that order, even if B wakes up and finishes going
through the intersection before A, you must ensure that A and B call exitIntersection()
in the same order.
In the traffic light scenario, entering (enterTrafficLight()) and actually moving through
it (actTrafficLight()) are two separate operations. Also, actTrafficLight()
accepts two callbacks (function pointers) that you can use to specify your own custom logic
before and after the car physically moves through the intersection.
• carsim.c: Defines main() for the program. You can specify which simulations to run.
• car: Defines a car and a few related enumerations and helper functions.
• common.h: Defines a few helper functions that can be useful to you.
• intersection.c: Defines logic common to the two scenarios, such as lanes.
• testing.c: Defines the simulation test cases. You can add your own test cases for better
coverage.
• mutexAccessValidator: Defines a tool used to check for collisions in the stop sign
scenario.
• SafeStopSign, SafeTrafficLight: Defines the functions each thread runs for each scenario.
• StopSign, TrafficLight: Defines the two scenarios. Check the headers for useful helper
functions.
Notes:
• Unlike in real life, there are no limits on the number of cars allowed to enter the traffic
light intersection and waiting to make a left turn.
• To simplify things in the traffic light intersection, you only need to check that there are
no cars going straight inside the intersection (see getStraightCount() in
trafficLight.c) from the opposite direction immediately before making a left-turn.
You do not have to check that there are no left-turners when going straight.
• Rules:
◦ Your code is run as part of a simulator framework with files that may be
overwritten when we run your submission. Don’t put any custom logic you may
need in any of the other files!
◦ You may not directly access members in the following structs (all interactions
with them must be done through the functions given):
▪ TrafficLight
▪ StopSign
▪ Lane
▪ CarToken, IntersectionQuad, MutexAccessValidator
• To earn full marks:
◦ Your code should not be overly restrictive. E.g., if two cars can pass through an
intersection at the same time, your code should not force one of them to wait.
◦ Use condition variables to notify other threads when an event occurs – don’t use a
while loop with polling (i.e., constantly checking to see if the event occurred).
▪ Don't use pthread_cond_timedwait(), we will treat it similarly to polling,
and you won't get full marks.
▪ Don't use spinlocks or spin-lock semantics either.
◦ Properly destruct and free any objects and allocations you make.
◦ Perform error checking.
◦ Use good code style (more on that below).
Testing
The purpose of toos like the mutexAccessValidator is to print messages to help you debug your
code when the synchronization is not quite right. You can test your programs on relatively small
numbers of cars (e.g. 16) and still expect to see some problems. As you become more confident
that your synchronization is correct, you can try it out on larger numbers of cars and a higher
number of experiments (say 80). Don't go crazy though, especially on wolf.teach.cs.toronto.edu.
You will eventually hit a limit of the number of threads you can create. Note that when we
mark, we will also test with cases that have different distributions of cars than what you were
given, along with tests that confirm whether or not your code is too restrictive.
Testing programs that involve synchronization primitives is difficult. Data races, deadlocks, and
other synchronization problems may occur during one run but not the next, which makes
detection of synchronization-related bugs a tedious (and frustrating) task. As computer scientists,
solving frustrating bugs is your bread and butter though, right? Well, it doesn't have to be.
Luckily, many share the same frustration of having to deal with complicated synchronization
bugs for days at a time. As a result, automated tools for detecting possible synchronization
problems are being developed and perfected, in order to assist programmers with developing
parallel code.
One such tool is valgrind, which you may have used before in checking other problems in
your code (e.g., memory leaks). Valgrind's instrumentation framework contains a set of tools
which performs various debugging, profiling, and other tasks to help developers improve their
code.
One of valgrind's tools is called helgrind, a synchronization error checker (for the lack of
a better word), which is tasked with helping developers identify synchronization bugs in
programs that use POSIX pthreads primitives. You are encouraged to read through the
Documentation (Links to an external site.)Links to an external site. for helgrind, in order to
understand the kinds of synchronization errors it can detect and how each of these are reported.
The simplest example of how to use helgrind is as follows:
valgrind --tool=helgrind ./carsim stop 1 16
However, before you start testing your assignment code, you might want to consider trying it out
on much simpler code, like the samples provided in lecture. For example, try testing helgrind
on the producer-consumer solution with condition variables: pc_cond.c. As you can see, no
synchronization errors are reported, and you should get a report that ends similarly to the one
below:
==9395==
==9395== For counts of detected and suppressed errors, rerun
with: -v
==9395== Use --history-level=approx or =none to gain increased
speed, at
==9395== the cost of reduced accuracy of conflicting-access
information
==9395== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 94
from 25)
For the most part, you can ignore most suppressed errors, but you might find it useful to enable
the verbose flag (-v) to enable more detailed reports. Please consider reading the documentation
for more information on this.
Although the documentation examples should be reasonably easy to follow, in order to practice
your understanding of what is being reported for various synchronization bugs, you might want
to consider trying to intentionally introduce various synchronization errors in the producerconsumer code and understanding the resulting helgrind report. For example, comment out in
the producer function the line which acquires the region_mutex. What does the
helgrind report tell you?
Warning: do not rely solely on this tool for writing correct code! Assistance from tools like
helgrind should not be a substitute for carefully thinking through what your code is doing and
what problems may arise. Although in this assignment the helgrind tool is probably sufficient
for detecting most mistakes you could run into, it is not a "catch-all" solution for synchronization
bugs and it is constantly being enhanced with more features. Once again, for the types of errors
detected by helgrind, please read the Documentation (Links to an external site.)Links to an
external site. carefully.
Submission
First of all, please do not manually create an a2 directory in your repo. An empty directory
called 'a2' should be created for you automatically when you log into MarkUs and go on your a2
link. Next, you should see the newly-created 'a2' directory in your repository. It will include all
of the starter code. Please make sure in advance that you can access your a2 directory, to avoid
last-minute surprises.
Your modifications to the starter code should be in 4 files:
• safeStopSign.c
• safeStopSign.h
• safeTrafficLight.c
• safeTrafficLight.h
You can also create additional helper files and modify the makefile. All submitted files should
be in the a2 directory, not a subdirectory. Do not submit executables or object files!
Additionally, you may submit an INFO.txt file which contains a discussion of your
implementation and any problems you encountered. If your program is partially working, this is
a great place to let the TAs know what is and isn't working. This file is not required.
Finally, whether you work individually or in pairs with a partner, you must submit a
plagiarism.txt file, with the following statement:
"All members of this group reviewed all the code being submitted and have a good
understanding of it. All members of this group declare that no code other than their own has been
submitted. We both acknowledge that not understanding our own work will result in a zero on
this assignment, and that if the code is detected to be plagiarised, academic penalties will be
applied when the case is brought forward to the Dean of Arts and Science."
Any missing code files or Makefile will result in a 0 on this assignment! Please reserve
enough time before the deadline to ensure correct submission of your files. No remark requests
will be addressed due to an incomplete or incorrect submission!
Again, make sure your code compiles without any errors or warnings. Your code will be tested
on the teach.cs lab machines.
Code that does not compile will receive zero marks!
Marking scheme
We will be marking based on correctness (90%), and coding style (10%). Make sure to write
legible code, properly indented, and to include comments where appropriate (excessive
comments are just as bad as not providing enough comments). Code structure and clarity will be
marked strictly!
Once again: code that does not compile will receive 0 marks! More details on the marking
scheme:
• stop sign: 30% (correctness and efficiency of the synchronization)
• traffic light: 60% (correctness and efficiency of the synchronization)
• Code style and organization: 10% - code design/organization (modularity, code
readability, reasonable variable names, avoid code duplication, appropriate comments
where necessary, proper indentation and spacing, use of constant variables, etc.)
• Negative deductions (please be careful about these!):
◦ Code does not compile -100% for *any* mistake, for example: missing source file
necessary for building your code (including Makefile, provided source files, etc.),
typos, any compilation error, etc.
◦ No plagiarism.txt file: -100% (we will assume that your code is
plagiarized, if this file is missing) Please contact the instructor in this case.
◦ Warnings: -10%
◦ Extra output (other than the printf statement indicated in the comments): -20%
◦ Code placed in subdirectories: -20% (only place your code directly under your a2
directory)