University of Arkansas
Department of Computer Science and Computer Engineering
CSCE 3613 – Operating Systems Spring 2019
Due: March 29 (Friday) 3:05PM Homework #5
The objective of this assignment is to provide some hands-on experience on multithreaded program-
ming and thread synchronization. You will design and implement a multithreaded program to control
southbound and northbound traffic on an imaginary na
ow
idge.
Traffic Patterns: Traffic will consist of cars and trucks. A vehicle (car or truck) may be traveling south
or north: the direction of each vehicle will be determined according to a probability distribution at the
time of its a
ival. Each ca
truck will take 2 seconds to cross the
idge.
Bridge Restrictions: The following restrictions are to be enforced.
R1. Since the
idge has only one lane, the traffic may cross the
idge in one direction at a time.
R2. Due to construction constraints, the
idge can accommodate at most 3 cars at a time.
R3. While a truck is crossing the
idge, no other vehicle (car or truck) should be on the
idge.
Violating the restriction R1 will cause collisions, while violating R2 or R3 will result in the collapse
of
idge. Your program should prevent collisions, deadlocks and the collapse of the
idge.
Traffic Control Policies: Traffic flow will be controlled according to the following rules.
P1. Trucks will have absolute priority over cars. That is, no car should be allowed to start to cross
the
idge if there is any waiting truck at either end of the
idge. In case there are waiting
trucks in both directions, then the traffic direction must be switched after each truck, to provide
a fair waiting time to trucks in each direction.
P2. If there are no waiting trucks, then the cars (if any) can start to cross the
idge. If there are
waiting cars at both ends of the
idge, then you are free to choose the direction of the first car to
cross the
idge (initially, or following a group of trucks). However, once a car C starts crossing
the
idge in one direction, the cars heading in the same direction as C will have priority ove
any car that may be waiting/a
iving at the other end of the
idge. Clearly, policy P1 will be
effective again as soon as a southbound or northbound truck a
ives. But observe that before
allowing any truck, your program must wait until all the cars that are already on the
idge
have left (otherwise the
idge will collapse).
P3. Subject to restrictions R1-R3 and policies P1-P2, no vehicle should incur a delay if there is
no opposite traffic crossing the
idge when it a
ives. If there is sufficient traffic, the
idge
capacity must be fully used (in other words, having cars cross the
idge one by one is not
acceptable).
P4. Any waiting vehicle can be selected to cross the
idge as long as restrictions R1-R3 and policies
P1-P2 are followed.
Representing Vehicles as Threads: You will represent each vehicle by one thread, which executes the
procedure Vehicle-Routine upon a
ival at the
idge:
Vehicle-Routine(parameter-list)
{
A
ive(...)
Cross(...)
Leave(...)
}
The parameter-list in Vehicle-Routine above should contain at least vehicle-id (an integer uniquely
identifying the vehicle), vehicle-type (car or truck) and direction (southbound or northbound). You are
free to use additional parameters and to determine the parameter lists of procedures A
ive, Cross
and Leave.
The A
ive procedure must check all the traffic
idge restrictions and it must not return until it is
safe for the vehicle to cross the
idge. The Cross procedure will just delay for 2 seconds for each
vehicle. Finally, the Leave procedure must take additional steps to let the traffic control mechanism
update its internal state and to let additional vehicles to cross the
idge, if any. These procedures must
print all the information necessary to follow the a
ival and departure patterns as well as the list
of waiting queues and crossing vehicles. The format shown in the following example should be adopted:
Car #5 (northbound) a
ived.
Car #7 (northbound) a
ived.
Truck #3 (southbound) a
ived.
.......
Car # 5 is now crossing the
idge.
Vehicles on the
idge (northbound): [Car #3, Car #4, Car #5]
Waiting vehicles (northbound): [Car #7, Car #8, Truck #2]
Waiting vehicles (southbound): [Car #10, Car #12]
.......
Car #5 exited the
idge.
Vehicles on the
idge (northbound): [Car #3, Car #4]
Waiting vehicles (northbound): [Car #7, Car #8, Truck #2]
Waiting vehicles (southbound): [Car #10, Car #12]
.......
Once a vehicle a
ives, the type, the id, the direction of the vehicle have to be printed. Once the status
of a vehicle changes (i.e., start crossing and exit the
idge), the information of the vehicles on the
idge
and the waiting vehicles have to be reported as above.
Programming Language, Thread Li
aries: For this assignment, you need to use C as the program-
ming language. You can use any multithreaded programming li
ary; however, you are encouraged to use
Pthreads, since you are likely to find a large number of references for Pthreads. Pthreads are also available
on the Turing.
Synchronization Primitives: You will write the procedures A
ive, Cross and Leave using mutex
locks and condition variables. Your solution must not employ busy waiting. For full credit, you should
only use pthread_cond_signal() for signalling any threads blocked on a condition variable. In othe
words, avoid using pthread_cond_
oadcast() function. Because of thread scheduling mechanism
of the li
ary you are using, you may occasionally observe that vehicles do not leave the
idge in the
same order they entered: a vehicle may overtake another vehicle traveling in the same direction. You do
not have to fix this problem.
Running Your Program with Specific Schedules: In this assignment, you have to run your program
for six vehicle a
ival schedules given below:
1) 10 : DELAY (10) : 10
ca
truck probability: [1.0, 0.0]
2) 10 : DELAY (10) : 10
ca
truck probability: [0.0, 1.0]
3) 20
ca
truck probability: [0.65, 0.35]
4) 10 : DELAY(25) : 10 : DELAY(25) : 10
ca
truck probability: [0.5, 0.5]
5) 10 : DELAY(3) : 10 : DELAY (10): 10
ca
truck probability: [0.65, 0.35]
6) 20 : DELAY(15) : 10
ca
truck probability: [0.75, 0.25]
Here the numbers indicate the number of a group of vehicles a
iving simultaneously at the
idge,
while the numbers in parentheses indicate the delay before the next a
ival(s). For example, under schedule
(4) 10 vehicles a
ive simultaneously at the
idge at the start of the experiment, 10 more vehicles a
ive
simultaneously 25 seconds after the a
ival of the first ten vehicles and so on. Under schedule (4), 30
vehicles a
ive at the
idge during the course of the experiment.
When multiple vehicles a
ive simultaneously, no vehicle in a group is allowed to cross the
idge until
all vehicles in the same group a
ive.
When multiple vehicles a
ive simultaneously, the direction and type of each vehicle will be determined
andomly. During all experiments, assume that the probabilities of having a southbound or north-
ound vehicle are equal (i.e. both are XXXXXXXXXXThe type of each vehicle (that is, whether it is a ca
or truck) will be determined according to the probabilities given at the end of each schedule in
pair [car=X, truck=Y]. For example, the schedule (3) is to be executed with pair (car=0.65, truck=0.35),
meaning that the probability that an a
iving vehicle is a car is 0.65, while the probability that an a
iving
vehicle is a truck is 0.35. For each a
iving vehicle, first determine its direction and then its type according
to these distributions. Observe that schedules (1) and (2) represent car-only and truck-only traffic patterns,
espectively. If you are using C, you can use the rand() to generate a random number. The random
number generator can be initialized by calling srand() with the desired seed.
Input and output of the program: The six specific schedules are required to given as command-
line arguments to the program, one schedule each time. For example, if you run Schedule #1, type in
.
idge_crossing 1.
idge_crossing is the executable. All the output of the program are
printed to the screen.
Submission: Please create a tar file using the name hw5
.tar including the following
items.
1) The source code of your programs.
Your code should include meaningful comments and variable names.
Name your executable as
idge_crossing.
2) Makefile, and/or any other information necessary to compile and run your program if you are using
additional facilities/li
aries.
Please note that I will use Turing to compile and verify your code.
3) A
ief report consisting of the following contents:
• A write-up describing the data structures you use.
• The pseudocode for your solution (please note that source code augmented with comments is
not pseudocode).
• The output of runs for the schedules given above.
4) A README file specifies the names of the above files.
Resources: You are strongly encouraged to refer to parallel programming links available at
http:
hthreads.csce.uark.edu/wiki/Howtos.
Suggestions: First, you will have to study the basics of multithreaded programming in C (see Resources
above). It is strongly suggested that you solve the problem with pen and paper before starting to code. An
incremental implementation where you first address the simpler cases of car-only and truck-only traffic
may be helpful. Then you can focus on the case of mixed traffic. It is important not to postpone the
assignment to the very last days unless you have prior experience in multithreaded programming.
Grading: The relative weights of grading components will be approximately as follows:
• Write-up and pseudo-code: 15 points
The output of six schedules are necessary for grading
• Co
ect Design and Implementation: 85 points
– Bridge Restrictions: 25 points
– Control Policy for Truck-Only Traffic: 10 points
– Control Policy for Car-Only Traffic: 10 points
– Control Policy for Mixed Traffic: 40 points
• Total Points: 100
Co
ect implementation of
idge restrictions is a necessary condition for traffic control policy imple-
mentation.
Late Penalty: No late submission will be accepted unless you consult with the instructor in advance.