Description
1. Requirements
Design and implement a simulation application aiming to analyse queuing based systems for determining and minimizing clients’ waiting time.
Queues are commonly used to model real world domains. The main objective of a queue is to provide a place for a “client” to wait before receiving a “service”. The management of queue-based system is interested in minimizing the time amount their “clients” are waiting in queues before they are served. One way to minimize the waiting time is to add more servers, i.e. more queues in the system (each queue is considered as having an associated processor) but this approach increases the costs of the service supplier. When a new server is added the waiting customers will be evenly distributed to all current available queues.
The application should simulate (by defining a simulation time 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛) a series of N clients arriving for service, entering Q queues, waiting, being served and finally leaving the queues. All clients are generated when the simulation is started, and are characterized by three parameters: ID (a number between 1 and N), 𝑡𝑎𝑟𝑟𝑖𝑣𝑎𝑙 (simulation time when they are ready to go to the queue; i.e. time when the client finished shopping) and 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒 (time interval or duration needed to serve the client by the cashier; i.e. waiting time when the client is in front of the queue). The application tracks the total time spend by every customer in the queues and computes the average waiting time. Each client is added to the queue with minimum waiting time when its 𝑡𝑎𝑟𝑟𝑖𝑣𝑎𝑙 time is greater than or equal to the simulation time (𝑡𝑎𝑟𝑟𝑖𝑣𝑎𝑙 ≥ 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛).
The following data should be considered as input data read from a text file for the application:
- – Number of clients (N);
- – Number of queues (Q);
- – Simulation interval (𝑡 𝑀𝐴𝑋 );
𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛
- – Minimum and maximum arrival time (𝑡 𝑀𝐼𝑁 𝑎𝑟𝑟𝑖𝑣𝑎𝑙
- – Minimum and maximum service time (𝑡 𝑀𝐼𝑁 𝑠𝑒𝑟𝑣𝑖𝑐𝑒
≤ 𝑡 𝑎𝑟𝑟𝑖𝑣𝑎𝑙
≤ 𝑡 𝑠𝑒𝑟𝑣𝑖𝑐𝑒
≤ 𝑡 𝑀𝐴𝑋 ); 𝑎𝑟𝑟𝑖𝑣𝑎𝑙
The output of the application is a text file containing a log of the execution of the application and the average waiting time of the clients, as shown in the following example.
In-Test.txt Explanation
≤ 𝑡 𝑀𝐴𝑋 𝑠𝑒𝑟𝑣𝑖𝑐𝑒
);
|
4 |
The application reads from In-Test.txt the simulation parameters: N=4 clients, Q = 2 queues, 𝑡𝑀𝐴𝑋 = 60, a 60 second simulation 𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 interval. It also reads the bounds for the client parameters, respectively a minimum and maximum arrival time 2, 30, meaning that clients will go to the queues from second 2 up to second 30. Furthermore, the bounds for the service time are read from the final line, 2 and 4, meaning that a client has a minimum time to wait in front of the queue 2 seconds and a maximum time of 4 seconds. Using these parameters, a set of 4 clients are generated random, each client i being defined by the following tuple: (𝐼𝐷𝑖, 𝑡𝑖 ,𝑡𝑖 the following constraints: ), with 𝑎𝑟𝑟𝑖𝑣𝑎𝑙 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 |
|
• 1≤𝐼𝐷𝑖≤𝑁
≤ 𝑡𝑖 𝑎𝑟𝑟𝑖𝑣𝑎𝑙 ≤ 𝑡𝑖 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 ≤ 𝑡𝑀𝐴𝑋 𝑎𝑟𝑟𝑖𝑣𝑎𝑙 ≤ 𝑡𝑀𝐴𝑋 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 A number of Q threads will be launched to process in parallel the clients. Another thread will be launched to hold the simulation time 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 and distribute each client i to the queue with the smallest waiting time when 𝑡𝑖 ≥ 𝑡 |
The output of the simulation is a text file containing the status of the pool of waiting clients and the queues as the simulation time 𝑡 goes from 0 to 𝑡𝑀𝐴𝑋 .
𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛
Out-Test.txt Explanation
|
Time 0 |
At time 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 = 0, a number of 4 clients are generated. Client with ID = 1 has an arrival time equal to 2, meaning that it will be ready to go to a queue when 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 ≥ 2. Furthermore, it has a service time equal to 2, meaning that is needs to stay 2 timesteps in the front of the queue. The same rules apply for the next 3 clients. |
|
Time 1 |
At time 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 = 1, none of the clients can be sent to the queues because none of them has the arrival time greater or equal to 2. The two queues are closed since there are not clients available. |
|
Time 2 |
Queue 1 is opened and client with ID =1 is sent to the first queue since 𝑡1 ≥ 𝑡 = 2. 𝑎𝑟𝑟𝑖𝑣𝑎𝑙 𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 Other clients are still waiting. Queue 2 is closed. |
|
Time 3 |
Queue 2 is opened time 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 = 3, client with ID = 2 is sent to it since 𝑡2 ≥ 𝑡 = 3, and the waiting time at the second 𝑎𝑟𝑟𝑖𝑣𝑎𝑙 𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 queue (0) is smaller than the waiting time at the first queue (1), where a client is still processed. Other clients are still waiting. |
|
Time 4 |
At time 𝑡𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 = 4, client with ID = 3 is sent to the first queue since 𝑡3 ≥ 𝑡 = 4. 𝑎𝑟𝑟𝑖𝑣𝑎𝑙 𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 Furthermore, client with ID =1 was eliminated from the queue because its service time has dropped to 0 (it was 1 at the previous iteration and was decreased with one at the simulation step) |
An example of input/output files is the following: In-Test.txt
Out-Test.txt
The final client is still waiting.
…
Average waiting time
2.5
:
The simulation is finished when there are no more clients in the waiting queue or at the service queues or 𝑡 > 𝑡𝑀𝐴𝑋
The average waiting time is computed and appended to the file.
𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛 𝑠𝑖𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛
4
2
60 2,30 2,4
Time 0
Waiting clients: (1,2,2); (2,3,3); (3,4,3); (4,10,2) Queue 1: closed
Queue 2: closed
Time 1
Waiting clients: (1,2,2); (2,3,3); (3,4,3); (4,10,2) Queue 1: closed
Queue 2: closed
Time 2
Waiting clients: (2,3,3); (3,4,3); (4,10,2) Queue 1: (1,2,2);
Queue 2: closed
Time 3
Waiting clients: (3,4,3); (4,10,2) Queue 1: (1,2,1);
Queue 2: (2,3,3);
Time 4
Waiting clients: (4,10,2) Queue 1: (3,4,3);
Queue 2: (2,3,2);
…
Average waiting time: 2.5
1.2 Design considerations
• Use an object-oriented programming design
1.3 Implementation considerations
- Use the Java programming language
- Implement classes with maximum 300 lines
- Implement methods with maximum 30 lines
- Use the Java naming conventions (https://google.github.io/styleguide/javaguide.html)
2. Deliverables
- A solution description document (minimum 2000 words, Times New Roman, 10pt,
Single Spacing) with the structure specified in the Lab Description document.
- Source files – will be uploaded on the personal gitlab account created at the Lab
Resources Gitlab laboratory work, following the steps:
o Create a repository on gitlab named according to the following templatePT2020_Group_FirstName_LastName_Assignment_2
o Push the source code and the documentation (push the code not an archive with the code)
o A PT2020_Group_FirstName_LastName_Assignment_2.jar file containing the project configured to run from the terminal and read 2 parameters: the name of the input file and the name of the output file. The application should permit to be run with the following command:
java -jar PT2020_Group_FirstName_LastName_Assignment_2.jar in.txt out.txt
- Three test files (in-test-1.txt, in-test-2.txt, in-test-3.txt) and their corresponding outputs
(out-test-1.txt, out-test-2.txt, out-test-3.txt) for the following configurations: in-test-1.txt in-test-2.txt in-test-3.txt
- Share the repository with the user utcn_dsrl.
|
4 |
50 |
1000 20 |
3. Evaluation
The assignment will be graded as follows:
Requirement
Grading
Minimum to pass
- Object-oriented programming design
- Classes with maximum 300 lines
- Methods with maximum 30 lines
- Java naming conventions
- Random Client Generator
- Multithreading: one thread per queue
- One test run and saved: in-test-1.txt
- .jar file uploaded and configured to run according to deliverable
requirement
- Appropriate synchronized data structures to assure thread safety (avoid
synchronized keyword as much as possible)
- Queues should open/close dynamically. Initially all queues are closed.
When clients are distributed to the queues, they become open as needed. When a queue becomes empty, it is closed, and the corresponding thread is paused.
•
5 points
Documentation
Other two tests given in requirements (in-test-2.txt, in-test-3.txt)
Quality of documentation
Compute average waiting time
Other tests run when evaluating homework using the compiled code as .jar file uploaded and configured to run according to deliverable requirement
4. Bibliography
1 point 2 points 1 point 1 point
– http://docs.oracle.com/javase/tutorial/essential/concurrency/index.html
– http://www.tutorialspoint.com/java/util/timer_schedule_period.htm
– http://www.javacodegeeks.com/2013/01/java-thread-pool-example-using-executors-and-
threadpoolexecutor.html
