Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Multi-queue simulation theory

  1. #1
    Member
    Join Date
    Oct 2011
    Posts
    40
    My Mood
    Stressed
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Multi-queue simulation theory

    I am currenty working on a program involving queues for my data structures class.

    The premise is very common among college assignments I'm told, but I am having trouble puzzling it out. Here are the basics:

    Code needs to handle 1-9 tellers based on input.
    Customers come in and join the shortest line, so there are as many lines as tellers, not a single queue.
    Event based - customer arrival time is random, time spent at teller is random.

    So, I have my teller queues set up, and am handling the random arrival of customers by predermining arrival times and placing them into an array. This may not be the best way to do it, but it's where I am right now. What I am not sure how to do is to keep track of all the teller queues, with their random customer service times, and continue moving the clock forward without missing anyone. Not sure if I am explaining that right...

    Lets say, customers arrive every 2-3 seconds while concurrently tellers take 3-8 seconds to service each customer.

    If there are 3 tellers, how to I make sure that I am processing arrival and departure events in the right order for all of them without missing anything?
    Should I predermine customer service times like I did arrivals?

    Maybe this is simple, I just can't figure out priority. I don't want code, just help with understanding.


  2. #2
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Multi-queue simulation theory

    If I understand your assignment, I would say a multi-threaded set of tellers with a shared database. Each teller can operate on its own, and all share the sama data set.

  3. #3
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Multi-queue simulation theory

    I might set it up something like this:


    Time-based simulation considerations for a multiple-queue, multiple-server system:

    There is a simulation timer variable, t. Start with t = 0, and there is a big loop that increments t at the end of the loop. (For convenience, assume t is an integer, and represents seconds from the time the bank opened.)

    There is a variable, arrivalTime, that keeps track of the next scheduled customer arrival time. When current simulation time becomes greater than arrivalTime, an entry is made into the shortest teller queue with current time as the arrival time.

    Then a new customer arrival is scheduled at current time plus some value from a random number generator.

    There are as many customer queues as there are tellers.

    Each teller queue has entries that show arrival times of customers.
    (So that statistics such as average wait time can be calculated.)

    Each teller has a variable, endTime, that keeps track of whether that teller is busy. If the teller is not busy, endTime = 0 for that teller. It stays at that value until the teller sees another entry in its queue.

    When a teller begins with a new customer (removes an entry from its queue), the teller schedules a new value of endTime according to some random number generator.


    For each teller, create an empty queue and set each teller's
    endTime to zero.
     
    Set arrivalTime equal to zero.
     
    for (t = 0; t < timeLimit; t++)
    BIG LOOP
        IF t is greater than or equal to arrivalTime
        THEN
           Find shortest teller queue
     
           Put an entry in that teller queue with arrival time = t
     
           Schedule a new arrivalTime equal to t + some random number
        END IF
     
        Make a loop that looks at all teller queues
        LOOP THROUGH TELLERS
           IF t is greater than this teller's endTime
           THEN
              IF this queue is empty
              THEN
                 Set this teller's endTime equal to zero
              ELSE
                 Remove that queue entry.  Wait time for this
                 customer was current time, t, minus arrival time
                 as shown in the queue entry.  Use this however
                 you have it set up to keep statistics.
     
                 Set this teller's endTime equal to current time, t,
                 plus some random number
              END IF
           END IF
        END LOOP THROUGH TELLERS
    END BIG LOOP

    Implementation details might re-arrange some of the logic (slightly) to attempt to get better performance, but the important part is to understand the problem in some context and get something to work. Implement first, optimize later (if appropriate).

    Random functions:
    1. Exponential distribution random number generator with 1/lambda = average interval between customer arrivals. Since the exponential distribution is continuous, for discrete time simulations, sometimes a Poisson distribution is assumed, where the value is the number of customers arriving in a given interval.

    2. Uniform distribution random number generator with mu = average time for service by a teller. (Could be some other distribution)


    If you want to calculate arrival times and service times ahead of time and put them in arrays instead of generating random deviates on the fly, that would work too, I guess.



    Alternative simulation implementation: Have an event list (sorted according according to time, smallest time value is at the top of the list). There are two types of events: Arrivals and Service. New arrivals are generated the same way as above, and new Service events are scheduled whenever a teller begins service. (Arrival events have an arrival time; service events have a server number as well as an arrival time.) Now, you don' t actually have a timer variable that is incremented each time through a loop.

    Your loop simply sets simulation time to the event at the top of the event list and it services all events that have that time. Then after removing the event or events with that time, you just go back to the top of the loop and you advance simulation time to the next event.

    This would be a "real" event-driven (rather than time-driven) simulator.

    It's only a little more complicated to handle different event types, but it's probably not worth it for small-potatoes stuff like a bank with nine tellers and events happening on one-second boundaries.

    On the other hand, simulating systems with thousands or hundreds of thousands (or even millions) of components with nanosecond or picosecond time resolution, you wouldn't want to spend a lot of time spinning through loops where nothing was happening...


    Cheers!


    Z
    Last edited by Zaphod_b; July 23rd, 2012 at 08:04 AM.

  4. #4
    Member
    Join Date
    Apr 2013
    Posts
    40
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Multi-queue simulation theory

    Hi im working on something similar just to ask how did you implement the 3-8 seconds to service each customer. For that I just used System.out.print and used sleep method. How did you do it ?

  5. #5
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Multi-queue simulation theory

    Quote Originally Posted by spiderd View Post
    ...how did you implement the 3-8 seconds to service each customer...
    This is a very general skeleton of implementation of a single-thread simulation program. The pseudo-code for my little time-driven example has a BIG LOOP whose counter value is the number of seconds from the start of the simulation.

    Each teller, when presented with a new customer, generates, and keeps track of, a "random" end time that allows the server to check at each successive pass through the loop, to see whether that much time has elapsed since service started.

    There is nothing in the loop that blocks execution, and, for text output, the simulation does not run in real time (so there is no sleeping); it runs as fast as it can and reports changes that are encountered as a result of the simulated time elapsed since scheduling each new event.


    If you want to create some kind of "real-time" animation based on this, then just put a statement at the end of the BIG LOOP that makes the program sleep for a second (or whatever time granularity you are simulating). Then, for each elapsed (real-time) second the program makes a trip through the BIG LOOP.

    A more sophisticated time-based program like this might have a different thread for each server and a dispatcher thread that puts each new arrival into one of the servers' queues. Then each server could sleep for a number of seconds when it encounters a new customer at the head of its queue while the others merrily keep doing their things. For some people that is conceptually simpler. It is, for some people, easier to visualize actual servers taking different times to process their customers and relate this to a multi-threaded simulation. Implementing the details could have significant educational value.

    I mean, learning about interaction and communication among several threads in a program, and, particularly debugging such a beast, can be a sobering experience, but might be interesting enough to make such exploration worthwhile to you. It might serve you well in your future development. (A little queuing theory pun here. Get it? Serve you. No? Oh, well...)

    Anyhow...

    Since the servers are not actually doing anything except removing things from queues, and seeing if time is up, there is no particular operational advantage (performance or otherwise) to multi-threading the simulation, even if you have a lot of cores in your processor that can take advantage of multi-threading.


    On the other hand...

    A simple, single BIG LOOP like my example (no sleeping or other program blocking by individual servers) illustrates a method that many embedded systems use to implement real-time programs without benefit of multi-threading and without multi-tasking operating systems. The clock keeps on ticking, relentlessly, and at each tick of the clock the program determines whether some event needs processing.

    There are, of course, other ways...



    Cheers!

    Z

Similar Threads

  1. create a simulation
    By aecosis in forum Java IDEs
    Replies: 3
    Last Post: June 12th, 2012, 08:55 AM
  2. 2D Fluid water simulation
    By JamEngulfer221 in forum Java Theory & Questions
    Replies: 0
    Last Post: December 11th, 2011, 07:27 AM
  3. board of galton,simulation.
    By robingeldolf in forum What's Wrong With My Code?
    Replies: 7
    Last Post: November 19th, 2011, 08:36 AM
  4. Checkout line Simulation
    By BuhRock in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 7th, 2011, 10:38 PM
  5. Keypress simulation problems
    By ummix in forum What's Wrong With My Code?
    Replies: 0
    Last Post: February 6th, 2010, 07:31 AM