Posted by raghvr
on February 17, 2013 at 10:48 AM PST
I need to design and implement a a multithreaded program to control traﬃc on an imaginary bridge with one lane in each direction.
The two lanes are labeled as Lane 1 and Lane 2.
R1. Vehicles cannot change lanes while on the bridge, and a given lane should never be opened
to traﬃc in opposite directions at the same time (otherwise a collision will occur).
R2. The total length of the vehicles in Lane 1 cannot exceed the total length of the bridge,
which is 44 feet. Similarly, the total length of the vehicles in Lane 2 cannot exceed 44
Traﬃc Control Policies: The traﬃc ﬂow will be controlled according to the following rules.
P1. As long as there is incoming traﬃc in both directions, exactly one lane will be allocated
to southbound and northbound vehicles in each traﬃc direction.
P2. If there are no waiting/crossing vehicles in one direction, then both lanes will be used
by the vehicles coming from the other direction (if any), to improve the traﬃc ﬂow.
While both lanes are being used in one direction, the policy P1 will be eﬀective again
as soon as vehicles from the other direction arrive at the other end of the bridge. But
before changing the traﬃc direction in a given lane, your program must wait until all the
vehicles which are already in that lane have left (otherwise a crash will occur).
P3. Subject to restrictions R1-R2 and policies P1-P2, no vehicle should incur a delay. If there
is suﬃcient traﬃc, the bridge capacity must be used fully (for example, having vehicles
cross the bridge one by one is not acceptable). The deadlocks should be also prevented.
Representing Vehicles as Threads:
You will represent each vehicle by one thread,
which executes the procedure Vehicle-Routine upon arrival at the bridge:
}The parameter-list in Vehicle-Routine above should contain at least vehicle-id (an integer
uniquely identifying the vehicle), vehicle-type (car or van), and vehicle-direction (northbound
or southbound). You are free to use additional parameters and to determine the parameter lists
of procedures Arrive, Cross and Leave. The Arrive procedure must check all the traﬃc/bridge
restrictions and it must not return until it is safe for the vehicle to cross the bridge. The
Cross procedure will just delay for 3 seconds for each vehicle. Finally, the Leave procedure
must take additional steps to let the traﬃc control mechanism update its internal state and
to let additional vehicles to cross the bridge, if any. These procedures must print all the
information necessary to follow the arrival and departure patterns as well as the
list of waiting queues and crossing vehicles. Your program should print the list of the
vehicles that have arrived but not started to cross the bridge (that is, waiting vehicles) in a
clear way. In addition, the total length of vehicles in each lane should be printed in a clear
way. The format shown in the following example can be adopted:
Car #6 (northbound) arrived.
Van #7 (northbound) arrived.
Van #8 (southbound) arrived.
Car #6 (northbound) is now crossing the bridge in Lane 1.
Van #7 (northbound) is now crossing the bridge in Lane 1.
Van #8 (southbound) is now crossing the bridge in Lane 2.
Bridge Status: Lane 1 - Northbound: [Car #3, Car #6, Van #7] Total Vehicle Length: 35
Lane 2 - Southbound: [Van #5, Van #8] Total Vehicle Length: 30
Waiting Queue (Northbound): [Car #9, Van #10, Car #12]
Waiting Queue (Southbound): [Van #4]
Car #6 (northbound) exited the bridge in Lane 1.
The incoming vehicles must be generated one after the other without
any delay, unless the schedule calls for an explicit delay through DELAY statement. You
should determine the directions of all the vehicles arriving simultaneously in a
group, before deciding on the next traﬃc ﬂow pattern (one lane for each direction
or both lanes for one-way traﬃc). As an example, in the schedule (4), your program
should generate the directions of all 20 vehicles in the ﬁrst group before determining the ﬁrst
traﬃc ﬂow pattern: unless all the 20 vehicles are bound for the same direction, initially a
separate lane should be allocated to the traﬃc in each direction.
You should design a simple user-interface to allow the grader to
enter any of the above schedules (or, another schedule). For example, your program may ﬁrst
prompt about the number of groups in the schedule. Then it may get information from the
user about the number of vehicles in each group, the Northbound/Southbound probability for
that group, followed by the DELAY before the next one (when applicable). The Car/Van
probability can be set to 0.6/0.4 statically. Alternatively, your program may read the schedule
information from a ﬁle, according to a format of your preference. The bottom-line is that the
grader should not have to modify your source program and that he should be able to easily
enter the information about the schedule of his preference. Your program should allow
the user to enter a schedule other than the schedules shown above.