Gas Station Simulation: How to simulate Cars coming at random intervals?

Question

The assignment is as follows:

The gas station consists of 2 pumps. Each pump has a certain amount of fuel it can distribute. Cars arrive at random intervals and attempt to use one of two pumps:

- If a pump is available and has fuel, the car is immediately allowed to use it. Each car requires a certain amount of fuel (random number), and has to wait for a time proportional to that amount of fuel. For example, a car may need 6 gallons and will use the pump for 3sec, another car may need 10 gallons and will use the pump 5 seconds, etc. When the car is fueled up, it leaves and the another car can use the pump. After fueling a car, the amount of fuel in the pump is adjusted accordingly.
- If both pumps are currently being used, then an arriving car waits until one of the two pumps becomes available.
- If a pump runs out of fuel, it must wait for a tanker to provide more fuel. The tanker arrives periodically (but not too often), and fills both pumps to capacity. While a tanker is servicing the pumps, no cars can use the pumps. forgot to add this

Part I: you must submit a detailed design that matches the above specifications. Your design must use Java threads. You must specify how many and what type of threads you will be using, and how these threads will be synchronized. You can write this stage of the project in pseudo-code. This is to help you understand how the various pieces will together.

Part II: you must submit a complete implementation of your design using Java threads and appropriate synchronization methods. Your implementation must be carefully tested against the above specifications.

I want to know. How can I use a Java Thread to simulate the cars coming in at random intervals?
I am very lost and appreciate your help in advance.

Answer 1

Firstly, as there is nothing in either your OP nor the extra bit of the problem statement which states that the system is operating against the wall clock, don't assume it does. Anything based on Sleeping for ten seconds between creating cars will drive you crazy while you're testing it. Create a simple interface to provide time for the simulation and work against that; if you need to tie it to the wall clock then you can, but you can also run your tests as fast as your machine will go.

Secondly, it's usually better to run simulations as events - car arrives at station, cars transitions from queue to pump, car leaves pump, tanker arrives. Usually a priority queue of events based on their times works; when a car starts filling, you add the event for it completing its task to the event queue with a timestamp in the future. It's much, much easier to write logic not to process cars if there is a tanker at a given time than to mess around with threading priorities.

Since your task requires that you demonstrate some synchronisation between threads, you might want to run the processes of cars waiting, cars filling/tankers unloading as separate threads ( in real software you wouldn't, but more likely use futures and an executor if you wanted parallel execution, but I'm assuming this is a pedagogic task and you need to show some design of threads, rather than letting the library sort it all out for you ).

So for each time slice, you process the events from the queue, wait for all event processing to complete, and then ask the clock for the next tick. The fast clock will immediately return a timestamp for the next second, or a wall clock clock would wait until the next second of the system time.

Since you're required to use threads for each task, you need to synchronise these tasks at the start and end of each time slice, and you need to synchronise or otherwise ensure that enqueued events are safely enqueued and visible before a time slice finishes.

So the tasks are something like:

• incoming cars

  • every second, determine the number of car arrivals. this will be a Poisson distribution.
  • for each arrival, post a car arrived event ( or post an event with the number of cars) (alternatively, use some other random mechanism; most of the other approaches will only cause one car to arrive at a time, which is not often a useful restriction to place on a model)

• incoming tankers

  • every (tanker arrival period) post a tanker arrived event per pump

• waiting cars

  • increment the number of cars waiting on car arrival event

• pumps

  • if a tanker has arrived, set the tanker waiting flag
  • if the pump is free, then
    • if a tanker is waiting, reset the tanker waiting flag, fill pump, post pump free event for time-to-fill-pumps in future
    • if the pump has fuel and any car is waiting, decrement the cars waiting count, post pump free event for time-to-fill-car in future

The problem statement isn't clear whether the tanker has to wait for both pumps to be free before it can start filling them, in which case you would need to add another 'tanker ready' state.

If the tasks are in different threads, you would need to synchronise the various counters, either 'manually' or by using the atomic values in java.util.concurrent.atomic.

Answer 2

Don't Use a Poisson Distribution. Poission will give you "Number arrivals in next X minutes." It will not give you "Time until next arrival".

Wite a small while loop like so ::

  public int getTimeTillNextCar() {
    PROBABILITY = .001;
    int timeTillNextCar = 0;
    while(rand.nextDouble() > PROBABILITY) {
      timeTillNextCar++;
    }
  }

Obviously, I just assumed you are using discreet time. However, it is possible (and some would argue better) to use a single draw from an exponential. This will be more efficent. However, using that approach makes the code "mathy" which some people might not like/understand.

Remeber, the Poisson distribution arrives from counting how many bernoulli draws were succesful given n draws when p is very small and n is moderately big. If n is "too" big then the Possion distribution will converge to the Normal distribution.

As for the rest of the design...

Thread_A should add cars to a Queue (be sure to use a thread safe queue class)

Thread_A shoule do this:
add car,
sleep(getTimeTillNextCar()),
add car,
sleep(getTimeTillNextCar()),
add car,
sleep(getTimeTillNextCar()),
etc....

Thread_B and Thread_C should take cars off the queue:
Thread_B (and C) should do this:
get_car_off_queue,
sleep(car.getFuelingTime(),
get_car_off_queue,
sleep(car.getFuelingTime(), etc...

Answer 3

You can use the thread-safe PriorityBlockingQueue to create an event queue.

Basically, car arrivals, tanker arrivals, car entering pump, and car exiting a pump are all events. Each of these have an order of occurrence, you insert an "Event" object for each of these events, with a timestamp. You can arrange so that the timestamp is used by the PriorityBlockingQueue to sort the events.

Initially, you start a thread for the car arrival producer thread and tanker arrival producer thread. The car arrival thread will put() a CarArrivalEvent to the queue, and then sleep for an random amount of time. The tanker thread also does the same, but put() TankerArrivalEvent instead.

The gas station has two pumps, each represented by consumer threads. Each pump thread will take() a CarArrivalEvent, then sleep for the amount of time needed to fill the car. You do similarly for TankerArrivalEvent.

Answer 4

Create a Car factory class that spits out a Car to be added to a dequeue and goes to sleep for a random period of time.

Like all students, you're probably finding this problem to be a little overwhelming. It is if you don't start breaking it down into smaller chunks that you can handle. Think of an overall design and start implementing small pieces of it.

For example, this is a queuing theory problem. They could be cars, people in bank lines, or anything interacting with a queue. Don't worry about the cars or the gas station details. Here's your issue:

1. You've got a line that adds new entries at one end and takes them off at the other. It's called a dequeue data structure. Read up on that. See if you can write (or reuse) a Java Dequeue class. Understand it completely. Write a small driver to add to one end and remove from the other.
2. Once you have that, you need to write classes that create new entries to add to the dequeue and another to remove them. Start simply by writing adders/removers that work at a fixed interval. What you should see is that if the adder and remover have exactly the same interface, the number of entries waiting in line will not change. If the adder works faster than the remover, the line should fill up. If the remover works faster than the adder, you'll never have a backup. Make sure that your simple classes exhibit this kind of behavior.
3. Add in the random bits and start your simulation. You'll want to see how the number of entries in line changes over time.
4. Now add more than one line. You want to see how adding more lines changes the dynamics.

Answer 5

If you have fixed intervals the number of cars arriving in that interval is Poisson distributed.

The time between two cars has a probabilitydensity proportional to exp(-t/tau) where tau describes the frequency of cars arriving. So you need to figure out how to create exponentially distributed random numbers.

From a probability density of p(t)=c*exp(-t/tau) we integrate a cumulative probability distribution of P(t)=1-exp(-t/tau). So inverting that function you get t=-tau*ln(1-P(t)). So if you generate a number u uniformly distributed between 0 and 1 you can get a correctly distributed t as t=-tau*ln(1-u)

Answer 6

I can see where you're going with a thread, but you don't really need one unless this is a graphic simulation in which you wish people to see it run in real time. Otherwise, simply keep track of a timeline. Know at any given point in time what event is going to happen next between: A) Truck arrives. B) Car arrives. C) Car leaves.

I imagine you're keeping track of how long these things take, so simply simulate the event to happen sooner. And everytime a car arrives, the time it takes for a new car to arrive will be a random amount of time decided by you.

Trust me, it'll make life a lot easier for you to simply things.

Answer 7

You can use same kind of cars source. You can establish some time interval for example with random deviation.