Hi all,
Below is a program that continues to give me multiple errors when I ran it. I kept getting error which I don't know how to fix and where/or what I did wrong. I need your help.
Please bear with me as you read through this because it is long I wanted to explain my intention. The program will create a multithreaded and thread synchronization to enable multiple thread accessing data structure without data corruption. Analogious to when multiple vehicles accessing narrow bridge. I used threads as vehicles and narrow bridge as buffer. I was thinking of using data structure instead of buffer but I don't know the difference...???
Traffic will consist of East and West for the vehicles (threads). There will be three types of vehicles: cars, vans and trucks. The direction and the type of each vehicle
will be determined according to given probability distributions at the time of its arrival. The
weight of a vehicle is determined by its type: Vehicles of type car, van and truck will weigh
100, 150 and 300 units each, respectively. Each vehicle will take 2 seconds to cross the bridge.
Bridge Rules:
R1. Since the bridge has only one lane, the traffic may cross the bridge in one direction at a
time.
R2. Due to construction constraints, the total weight of vehicles on the bridge cannot exceed
500 units, at any time.
Violating the restriction R1 will cause collisions, while violating R2 will result in the collapse
of bridge. Your program should prevent collisions, deadlocks and the collapse of
the bridge.
Traffic Control Policies: Traffic flow will be controlled according to the following rules.
P1. Once the traffic starts crossing the bridge in one direction, any other vehicles (threads) arriving at the bridge in the direction of current traffic will have priority over any vehicle that may be waiting/arriving at the other end of the bridge, subject to the fairness condition
P2 below.
P2. If there are vehicles waiting at one end of the bridge in one direction, then at most 6
consecutive vehicles may cross the bridge from the other end (in other direction). In
other words, a vehicle which is (or, arrives) at the “head” of the queue at one side of
the bridge should never wait for more than 6 vehicles crossing the bridge in the other
direction1.
P3. When admitting the vehicles to the bridge in a given direction, First-Come-First-
Served (FCFS) rule will be applied. In other words, both East bound and West bound
waiting queues should reflect the vehicle arrival orders. Note that this rule should be
enforced even when it results in unused bridge (buffer) capacity. For example, when a West bound truck is crossing the bridge, multiple west bound cars may have to wait behind another truck at the head of the westbound waiting queue.
P4. Subject to restrictions R1-R2 and policies P1-P3, the bridge (buffer) capacity (500) must be fully used when there is sufficient traffic. In other words, no vehicle should incur unnecessary delay (for example, having all the vehicles cross the bridge one by one regardless of their types is not acceptable).
Note: The number of vehicles crossing the bridge in the opposite direction when a given vehicle V arrives to the head of the waiting queue will also count towards the limit of six that must be adhered to for this vehicle V.
Like I said, each vehicle is represented by one thread, which executes the procedure Vehicle-Routine upon arrival at the bridge: Vehicle-Routine(parameter-list)
{
Arrive(. . .)
Cross(. . .)
Leave(. . .)
}
The parameter-list in Vehicle-Routine above should contain at least vehicle-id (an integer
uniquely identifying the vehicle), vehicle-type (1: Car, 2: Van or 3: Truck) and direction
(southbound or northbound). 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 traffic/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 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
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. This program print the list of the threads (vehicles) that have arrived but not started to cross the bridge (that is, waiting vehicles) in a clear way. The total weight of the vehicles on the bridge must be also printed whenever a vehicle enters/leaves the bridge. I adopted this format in the following order:
Vehicle #5 (Eastbound, Type: Car) arrived.
Vehicle #6 (Eastbound, Type: Truck) arrived.
Vehicle #7 (Westbound, Type: Van) arrived.
.......
Vehicle #5 is now crossing the bridge.
Vehicles on the bridge: [#3 (Type: Van), #4 (Type: Car) , #5 (Type: Car)]. Total Weight:
350
Waiting vehicles (Eastbound): [#6 (Type: Truck), #8 (Type: Car), #11 (Type: Van)]
Waiting vehicles (Westbound): [#10 (Type: Van), # 12 (Type: Car)]
.......
Vehicle #5 exited the bridge. Total Weight: .......
.......
I tried to avoid busy waiting.
Synchronization Primitives: My intention is to use Arrive, Cross and Leave using mutex locks and condition variables. I want to use thread synchronization facilities (wait() and notify()) but not notifyall() to avoid releasing all the blocked threads at once. Also I intend not to employ busy waiting. Because of the thread scheduling mechanism of the library you are using, the order in which cars leave or enter does not matter.
The goal is to run the program with Specific Schedules for six vehicle arrival schedules given below:
1. 20 : DELAY (10) : 10
Vehicle Type Probability Distribution : [1.0, 0.0, 0.0]
2. 10 : DELAY (10) : 5
Vehicle Type Probability Distribution : [0.0, 0.0, 1.0]
3. 30
Vehicle Type Probability Distribution : [0.5, 0.3, 0.2]
4. 20 : DELAY(45) : 10 : DELAY(45) : 5
Vehicle Type Probability Distribution: [0.5, 0.25, 0.25]
5. 20 : DELAY(5) : 10 : DELAY (5): 5
Vehicle Type Probability Distribution : [0.5, 0.25, 0.25]
6. 20 : DELAY(15) : 10
Vehicle Type Probability Distribution : [0.3, 0.3, 0.4]
Here the numbers indicate the number of vehicles arriving at the bridge, while the numbers
in parantheses indicate the delay before the next arrival(s). For example, under schedule (4) 20 vehicles arrive at the bridge at the start of the experiment, 10 more vehicles arrive 45 seconds after the arrival of the first 20 vehicles and so on. Under schedule (4), 35 vehicles arrive at the bridge during the course of the experiment. The direction and type of each vehicle will is determined randomly. I am assuming that the probabilities of having a Eastbound or Westbound vehicle are equal (i.e. both are 0.50). The type of each vehicle will is determined according to the probabilities given at the end of each schedule in the triple [X,Y, Z], where X, Y, Z represent the probability of having a vehicle of type car, van and truck, respectively. For example, the schedule (3) is to be executed with the probability distribution [0.5, 0.3, 0.2], meaning that the probability of having a vehicle of type car, van and truck, is 0.5, 0.3 and 0.2, respectively. For each arriving vehicle, I first determined its direction and then its type according to these distributions. I tried to use system library functions to generate random numbers, but not possible for me. Simply multiplying the total number of vehicles (threads) by the car probability did NOT give the number of cars in that group: I should generate a random number when determining each vehicle’s type but it is not working right. The same consideration applies to the step of determining the direction of each vehicle: if there are 10 vehicles in a group, this does not
mean that you can immediately set the number of Eastbound and Westbound vehicles to 5.
Observe that schedules (1) and (2) represent Car-Only and Truck-Only traffic patterns,
respectively. The incoming vehicles must be generated one after the other without any delay, unless the schedule calls for an explicit delay through DELAY statement.
PROGRAM:
My goal is to use this program below to accomplish my objective, but I am not getting a good result. Rather than providing you with my modified program to confuse you more, I decided to give you this sample program which is akin to my goal. I believe this will give you vivid idea of what I am looking to accomplish. Thanks for reading and your help.
/**
This program shows how to avoid data corruption
when multiple threads access a data structure
*/
public class SynchBankTest
{
public static void main (String [] args)
{
Bank b = new Bank (NACCOUNTS, INITIAL_BALANCE);
int i;
for (i = 0; i < NACCOUNTS; i++)
{
TransferThread t = new TransferThread (b, i,
INITIAL_BALANCE);
t.setPriority (Thread.NORM_PRIORITY + i % 2);
t.start ();
}
}
public static final int NACCOUNTS = 10;
public static final int INITIAL_BALANCE = 10000;
}
/**
A bank with a number of bank accounts.
*/
class Bank
{
/**
Constructs the bank.
@param n the number of accounts
@param initialBalance the initial balance
for each account
*/
public Bank (int n, int initialBalance)
{
accounts = new int[n];
int i;
for (i = 0; i < accounts.length; i++)
accounts[i] = initialBalance;
ntransacts = 0;
}
/**
Transfers money from one account to another.
@param from the account to transfer from
@param to the account to transfer to
@param amount the amount to transfer
*/
public synchronized void transfer (int from, int to, int amount)
throws InterruptedException
{
while (accounts[from] < amount)
wait ();
accounts[from] -= amount;
accounts[to] += amount;
ntransacts++;
notifyAll ();
if (ntransacts % NTEST == 0) test ();
}
/**
Prints a test message to check the integrity
of this bank object.
*/
public synchronized void test ()
{
int sum = 0;
for (int i = 0; i < accounts.length; i++)
sum += accounts[i];
System.out.println ("Transactions:" + ntransacts
+ " Sum: " + sum);
}
/**
Gets the number of accounts in the bank.
@return the number of accounts
*/
public int size ()
{
return accounts.length;
}
public static final int NTEST = 10000;
private final int[] accounts;
private long ntransacts = 0;
}
/**
A thread that transfers money from an account to other
accounts in a bank.
*/
class TransferThread extends Thread
{
/**
Constructs a transfer thread.
@param b the bank between whose account money is transferred
@param from the account to transfer money from
@param max the maximum amount of money in each transfer
*/
public TransferThread (Bank b, int from, int max)
{
bank = b;
fromAccount = from;
maxAmount = max;
}
public void run ()
{
try
{
while (!interrupted ())
{
int toAccount = (int)(bank.size () * Math.random ());
int amount = (int)(maxAmount * Math.random ());
bank.transfer (fromAccount, toAccount, amount);
sleep (1);
}
}
catch (InterruptedException e) {}
}
private Bank bank;
private int fromAccount;
private int maxAmount;
}