PT Homework 2

Queue based system

1. Homework’s objective
The objective of the second homework is to design and implement a simulation
application aiming to analyse queuing based systems for determining and minimizing clients’
waiting time.

2. Homework’s description
Queues are commonly used in real life, for example people waiting in a shop queue. The
main objective of a queue is to provide a place for a ‘client’ to wait before receiving a
service. Thus, we are interested in minimizing the time a client spends in a queue before
she/he is served. One way of minimizing is to add more queues in the system, but this
approach increases the costs of the service supplier. When a new queue is added, the waiting
customers will be evenly distributed to all current available queues.
The application should simulate a series of clients arriving for a service, entering the
queue, waiting, being served and then leaving the queue. It tracks the time customers spend
waiting in queues and outputs the average waiting time. The arrival time and service time
depend on the individual clients and are generated randomly. The finish time depends on the
number of queues, the number of clients and their service needs.

Inputs:
 Interval of arriving time between customers
 Simulation interval
 Interval of service time
 Maximum length of a queue

Outputs:
 Average waiting time
 Average service time
 Empty queue time
 Log of events (output file)
 Peak time for simulation

Simulation interval is given as an input by the user, but the time queues are working is to
be extended until all the clients that entered the system are served. The number of queues was
another possible input, but I chose to start with only one queue and add another ones when
needed. The solution should be implemented using multithreading.

Minimal requirements:
 Graphical interface displaying real-time queue evolution
 Documentation
 Random Client Generator
 At least one thread or timer for the simulation
 Log of events (Logger, Output File or TextArea)
 3. Threads. Multithreading. Synchronization
Starting working with threads was a real challenge for learning this new concept. A little
theory and practice were enough to implement a simple queue based system with several
queues working in parallel. In the following part of the documentation I will present briefly
some theoretical aspects about threads, multithreading and synchronization.
It would be nice if we could focus our attention on performing only one task at a time and
doing it well. That’s usually difficult to do in a complex world in which there’s so much
going on at once. Java has many capabilities for developing programs that create and manage
multiple tasks, and this can greatly improve program performance.
When we say that two tasks are operating concurrently, we mean that they’re both
making progress at once. Until recently, most computers had only a single processor.
Operating systems on such computers execute tasks concurrently by rapidly switching
between them, doing a small portion of each before moving on to the next, so that all tasks
keep progressing. For example, it’s common for personal computers to compile a program,
send a file to a printer, receive electronic mail messages over a network and more,
concurrently.
When we say that two tasks are operating in parallel, we mean that they’re executing
simultaneously. In this sense, parallelism is a subset of concurrency. The human body
performs a great variety of operations in parallel. Respiration, blood circulation, digestion,
thinking and walking, for example, can occur in parallel, as can all the senses—sight,
hearing, touch, smell and taste. Today’s multi-core computers have multiple processors that
can perform tasks in parallel. Java programs can have multiple threads of execution, where
each thread has its own method-call stack and program counter, allowing it to execute
concurrently with other threads while sharing with them application-wide resources such as
memory and file handles. This capability is called multithreading.
At any time, a thread is said to be in one of several thread states—illustrated in the UML
state diagram in Fig. 1.

Fig. 1: Thread life-cycle UML state diagram

a. New and Runnable States

A new thread begins its life cycle in the new state. It remains in this state until the
program starts the thread, which places it in the runnable state. A thread in the runnable state
is considered to be executing its task.
 b. Waiting state
Sometimes a runnable thread transitions to the waiting state while it waits for another
thread to perform a task. A waiting thread transitions back to the runnable state only when
another thread notifies it to continue executing.

c. Timed Waiting State

A runnable thread can enter the timed waiting state for a specified interval of time. It
transitions back to the runnable state when that time interval expires or when the event it’s
waiting for occurs. Timed waiting threads and waiting threads cannot use a processor, even if
one is available. A runnable thread can transition to the timed waiting state if it provides an
optional wait interval when it’s waiting for another thread to perform a task. Such a thread
returns to the runnable state when it’s notified by another thread or when the timed interval
expires—whichever comes first. Another way to place a thread in the timed waiting state is to
put a runnable thread to sleep—a sleeping thread remains in the timed waiting state for a
designated period of time (called a sleep interval), after which it returns to the runnable state.

d. Blocked state
A runnable thread transitions to the blocked state when it attempts to perform a task that
cannot be completed immediately and it must temporarily wait until that task completes.

e. Terminated state
A runnable thread enters the terminated state (sometimes called the dead state) when it
successfully completes its task or otherwise terminates, perhaps due to an error.

There are two ways of creating and running a thread (there are more, but these are usually
used):
 Implement the Runnable interface (of package java.lang) to specify a task that can
execute concurrently with other tasks. The Runnable interface declares the single
method run, which contains the code that defines the task that a Runnable object
should perform.
 Extend Thread. The Thread class itself implements Runnable, though its run method
does nothing. An application can extend Thread, providing its own implementation of
run.
In both cases, Thread.start is invoked in order to start the new thread. But which of these
options are to be used? The first one, which employs a Runnable object, is more general,
because the Runnable object can subclass a class other than Thread. The second is easier to
use in simple applications, but is limited by the fact that your task class must be a descendant
of Thread. In this project we will use the second way, as our system is not that complex.
When a Java program starts up, one thread begins running immediately. This is usually
called the main thread of your program, because it is the one that is executed when your
program begins. The main thread is important for two reasons:
 It is the thread from which other ‘child’ threads will be born.
 It must be the last thread to finish execution. When the main thread stops, your
program terminates.
The join method allows one thread to wait for the completion of another. If t is a Thread
object whose thread is currently executing, t.join(); causes the current thread to pause its
execution until t’s thread terminates.
 3.1.Thread Synchronization

In this sub-chapter I will discuss only about methods and concepts that are used for
developing this project. Because we are dealing with a Logic(Shop) thread that creates(has)
other Queues, we have to synchronize them. This was done using wait and notifyAll methods
on a token.
wait() tells the calling thread to give up the lock and go to sleep until some other thread
enters the same monitor and calls notify(). The wait() method releases the lock prior to
waiting and reacquires the lock prior to returning from the wait() method.
notify() wakes up one single thread that called wait() on the same object. It should be
noted that calling notify() does not actually give up a lock on a resource. It tells a waiting
thread that that thread can wake up. However, the lock is not actually given up until the
notifier’s synchronized block has completed. So, if a notifier calls notify() on a resource but
the notifier still needs to perform 10 seconds of actions on the resource within its
synchronized block, the thread that had been waiting will need to wait at least another
additional 10 seconds for the notifier to release the lock on the object, even
though notify() had been called.
notifyAll() wakes up all the threads that called wait() on the same object. The highest
priority thread will run first in most of the situation, though not guaranteed. Other things are
same as notify() method above.

4. Problem analysis. Modeling. Use cases

The very first questions to be asked when starting to develop a solution to a real
problem are: Which are the objects involved? What classes do they belong to? Which
attributes describe the objects? What actions can they perform, and how do they interact with
each other? In fact, creating a good model of the reality was the first concern. Better the
model, less complex the algorithms to be used.
We were required to develop a queue based management system for minimizing the
waiting time at a queue shop, for example. Until now, we identify 2 objects: queues and
clients that are waiting in a queue. These two object have specific attributes that describe
them, as we will see shortly. Another class for the Logic was needed. It can represent the
shop itself, that has control over the queues. The logic creates the queues when needed, starts
them, notify the queues when to run, collects and process information from all of them. The
queues are running in parallel while the logic is sleeping. Then the logic does some other
stuff and again notifies the queues to do their job for that currentTime.
For generating the clients and the queues, I implemented a ClientFactory and a
QueueFactory respectively. These classes have each one a method that returns a numbers of
clients/queues and fill their attributes with certain random values.
As we work with many intervals, an Interval object was needed to simplify our job.
The user can interact with the system through a Graphical User Interface (GUI). He
should introduce valid inputs first, and then the process will start. He can see the evolution of
queues in real time in the user interface window or read a more detailed outputFile that is
generated with all the events that occurs in each second of the simulation time.
 5. Project design and implementation

Fig. 2: UML Diagram

Logic has a list of clients and a list of queues. A queue has a list of clients (aggregation).

5.1. Factories

ClientFactory and QueueFactory were designed to provide our system with clients and
queues. Clients are generated with a random name, a random service time(that is in serviceI),
and a random arrivalTime(that is less than the simInterval.getB()). Clients are supposed to
come at an arrival time between them generated also randomly, in a range introduced by the
user. No clients is generated so to arrive after the simulation ends.
First time only one queue is generated. We open the shop and there is only one queue
where you can pay. If needed, we will open other queues on the way. But we avoided to let
the number of queues to be introduced by the user, in order to avoid a big emptyQueueTime.
Queues have a random name and they are given a maximum amount of clients they can hold.
The token is used for synchronization with the Logic.

5.2. Client

Clients are described by a name, arrivalTime and serviceTime. We have getters for all
these attributes. The serviceTime can be decremented with decrServiceTime(), method used
to know when a client is supposed to leave a queue.

5.3.Queue

Queue class extends Thread class, thus queues are runnable objects(threads). These are
described by qName, simInterval, maxQSize, waitingTime, emptyQueueTime and a token for
synchronization. In the run method, overridden from Thread class, the queue waits until it
gets the token from logic. When it does, it does some operations that a queue should do in a
second of simulation: re-compute the emptyQueueTime and waitingTime, decrement the
service time of the client being served(if there is one) dequeue a client when needed. After
that, the queue waits for another notification from Logic, so that it can perform the same
operations for the next second of execution. This is done until the simulation time is over or
there are still some clients in the queue.
One can obtain the fields of the queue with the provided getters. Also you can check if the
queue is full or you can obtain the last client in the queue (i.e. the client being served).
Enqueue/Dequeue operations are also done on a queue.

5.4.Logic

The name of this class is not very suggestive. A better name would be ‘Shop’, or
‘ShopLogic’. This class also extends Thread class, and is the place where queue threads are
created and started. I will describe below the ‘run’ method of this class, as it performs lots of
things.
First, the outputFile with the events is cleaned. Then avgServiceTime is computed
(because the clients that are supposed to enter the system during the following simulation is
already known, and after simulation end their service time will be 0) and the queues are
started. Actually there is only one queue started at the beginning, but I leave that ‘for each’ as
it is, because one may modify the solution in the future to start with more queues. Then a
while begins until the simulation times up or there are still clients in queues, so we wait for
them to be served and after that we close the shop. During the running of the thread, several
things are written in the output file: current time, events like adding or removing a client from
a queue, or the content of each queue. In the GUI will be written in real time the state of the
queue. The logic checks if there is a client that should enter the system(i.e. its arrivalTime
equal the currentTime of simulation). If so, the logic places the new clients in the emptiest
queue available. If all queues are full, a new queue is created, the client is place there and all
other clients are evenly distributed among queues. This way, we simulate a real situation:
when a new shop queue opens, some clients from the other queues change their place so that
its more convenient for them. After enqueuing process, the queues are notified they can do
their job while Logic sleeps for one second, so that the two kinds of threads do not bother
each other. We also compute, at each second, the peak time.
When simulation ends, statistics are displayed on the screen: average waiting time,
average service time, how much time the queues were empty, and peak time of the
simulation.
 6. Graphical User Interface
The Graphical User Interface (a visual way of interacting with a computer) for this
project was done with the MVC design – Model, View, Controller. The model represents data
and the rules that govern access to and updates of this data. In enterprise software, a model
often serves as a software approximation of a real-world process. The view renders the
contents of a model. It specifies exactly how the model data should be presented. If the model
data changes, the view must update its presentation as needed. The Controller translates the
user’s interactions with the view into actions that the model will perform. There is a clear
separation between those three parts of the design.
In our case, we are modeling the Logic(Shop).

6.1. The View

The View extends JFrame class. It contains labels, text fields, text areas and buttons. The
user introduces the simulation time, the maximum size of the queues, the service interval and
the arrival time between clients. The simulation start when the user hits the start button. The
result appears in the boxes below: in the text area ‘Real Time Queue Evolution’ the real time
status of the queues, then the statistics. One can clear all the fields of the view by pressing the
clear button.

Fig. 3.: GUI of the system

 In View’s constructor the output text field components are initialized with an empty
string and set to be non-editable. After that, the components are arranged on panels. All
panels are grouped then in a vertical panel. It is set visible and can be exited on close.
The View contains methods that are related to reading the user’s input and displaying the
results of the operations/events. There is a listener for each button. Listeners in java are
responsible to handles events. If a button is pressed, some actions are to be taken. The
controller describes what actions are taken for each event.

6.2. The Controller

The Controller takes the View and the Model as instance variables. The Model is
made of two polynomials. In Controller’s constructor the listeners are placed on the view, one
for each button.
A class for each listener that implements ActionListener is written, and then a method
that describes what each listener should do when it “hears” something.

7. Results

The result is an interactive way of simulating a real queue based system. The user
specifies the input conditions and then he can see the outcome displayed on the screen.

8. Conclusions and further work

During the development of this project I learned the basic concepts regarding threads and
I had the chance to see how they really work.
As a further work, the design can be structured better, the synchronization may be
improved(I am not sure if it is good practice to make the token static in a separate class,
instead of placing it as parameter) and the model strengthen.
The Graphical User Interface may be improved to give the user a better experience with
the system. The validation of the user input is another important aspect to be done further.

https://en.wikipedia.org/wiki/One-to-many_(data_model) [1]
https://en.wikipedia.org/wiki/Singleton_pattern [2]
http://tutorials.jenkov.com/java-reflection

https://docs.oracle.com/javase/tutorial/java/generics/types.html
https://www.tutorialspoint.com/java/java_generics.htm [3]