Description
Introduction
In this homework, you are asked to write a multithreaded C++ program that simulates a
queue of customers waiting in a store to pay their groceries. There are two (2) cashiers and a queue in
the store, shared by these cashiers. One of the cashier always serves to the customers, while the other
cashier serves when the current number of customers waiting in the queue passes a threshold value.
When arrived, customers need to go to the rear of the queue and wait in that queue until their turn
comes to be served by a cashier. Whenever a cashier is available, the customer at the front of the queue
begins the checkout process with that cashier. In this homework, you will simulate the customer’s
arrivals and their transactions with the cashiers via a dynamic queue data structure and multithreading
techniques.
The time between arrivals of two customers is probabilistic. Moreover, the time for a cashier to
finish a checkout process is also probabilistic. Thus, the inter-arrival time between two customers and
the checkout durations of cashiers are random values. The parameters of these random values will be
input (see Section “Details of Simulation” for details).
In the scope of this homework, simulation means to employ a queue which customers arrive at
random intervals and cashiers get the next customer to process. Simulation starts after taking the inputs
from the keyboard, and continues until all of the customers arrive and complete checkout. During the
simulation, you are going to display some verbose output about the actions of customers and cashiers
(see Section “Details of Simulation” for details).
Using Threads
There will be three threads (other than the main thread) in your program. One thread is for the
arrival of the customers. Other two threads are for the cashiers; one for each. In the customer thread,
the customers will arrive one by one at random intervals and enqueued to the queue. On the other
hand, while one cashier always dequeues a customer from the queue, other cashier only dequeues
when queue’s size passes a pre-determined threshold value, which is also an input. Then the cashier
starts the checkout process, which also takes a random time period.
Please use the HW8DynIntQueue class given in this homework package as the queue data
structure. Moreover, do not forget that each cashier and its thread uses same HW8DynIntQueue
object for dequeuing. Also, enqueuing customers to this queue will be done in a single customer
thread. Such a structure may cause some special cases to deal with in a multithreaded application. For
example, there might be a synchronization conflict during enqueuing and dequeuing customers to/from
the queue. Some other special cases and conflicts may occur; therefore, you have to take some
precautions in the threads to avoid such situations. Please refer to lecture and lab materials which
include methods for dealing with these cases using mutex.
At the end, your threads must be joined properly and your program must terminate without any
complications/crashes.
Details of Simulation
Before the simulation begins, some inputs (total 6 of them) are entered via keyboard. First,
total_customer_count is entered. total_customer_count is the total number of customers who are going
to arrive to the store and served during the simulation. In other words, the simulation will finish when
total_customer_count customers complete their transactions. Moreover, you should not allow more
than total_customer_count customers to arrive. Thus, at the end of simulation, all customers should be
processed by the cashiers and the queue must be empty.
Second input is cashier2_threshold that determines when second cashier starts and stops to
serve customers according to the current queue size. More specifically, as long as the current queue
size is greater or equal to cashier2_threshold, second cashier serves by getting the next customer in the
queue. When the queue size becomes less than cashier2_threshold, second cashier stops serving. Here
remark that if queue size gets greater than or equal to the cashier2_threshold again at a later time,
second cashier starts to serve again, and so on.
Then, the parameters of the random customer inter-arrival time and random cashier checkout
duration must be entered via keyboard. The time period between two customer arrivals is a random
value in seconds. This random value is between two integer parameters: min_arrival and max_arrival
(min and max values are included in the range). The cashiers’ checkout time is also determined
similarly; it is a random integer value between and including min_checkout_time and
max_checkout_time. Of course, the random checkout time will be picked for each customer separately.
You do not need to make any input checks for these parameters. You can assume that min values are
always less than or equal to the corresponding max values and min values are greater than or equal to 1
second. To generate random numbers for arrival and checkout time, do not use the RandGen class
from CS201 for random integer generation in multithreaded applications because it is not thread-safe.
Instead, you must use the following thread-safe function, random_range, for generating
random waiting times inside the threads. This function returns a random number between (and
including) min and max parameters. In the threads, you can call it by passing minimum and maximum
waiting times of the corresponding thread as arguments.
#include
#include
int random_range(const int & min, const int & max) {
static mt19937 generator(time(0));
uniform_int_distribution distribution(min, max);
return distribution(generator);
}
Simulation starts when the user enters all the inputs through keyboard. During the simulation,
customers will arrive and cashiers will process customers in corresponding threads as explained before.
Here we want to give a hint about second cashier’s thread. Since the second cashier works in on/off
manner due to the threshold logic explained above, you may think of starting and stopping its thread
for the implementation of this logic. However, this would be too complicated and we are not expecting
such a solution; it would be sufficient if you start the second cashier’s thread at the beginning of the
program (after getting the inputs) and implement the logic of threshold within the thread’s entry point
function.
Each new customer must be associated with a consecutive ID number starting with 1. You may
simulate inter-arrival time of customers and checkout time of a customer by a cashier by sleeping the
threads using the this_thread::sleep_for(chrono::seconds(time_in_seconds))
command of thread (for this_thread::sleep_for) and chrono (for
chrono::seconds) libraries. Moreover, you have to sleep the cashier threads just after starting the
thread functions as well.
At the beginning of the program (after getting the inputs and just before the beginning of the
simulation), you have to display a message saying that the simulation is starting at the current time.
During the simulation, customer thread should display the details of each customer’s arrival. These
details contain the ID of the customer, the queue size after enqueue operation and the time of arrival.
Similarly, each cashier thread should display the details of the checkouts. At the beginning and at the
end of a transaction, the tag of the cashier (1 or 2), the ID of the customer and the time of the operation
should be displayed. Additionally, for the beginning of transaction, the size of the queue (after
dequeuing) should be displayed as well. At the end of the simulation, a message saying that the
simulation is ended must be displayed together with the current time. Please see the sample run section
for some examples.
Two important rules about the simulation details and use of threads:
Here please remark that a single line of output from a particular thread may be interleaved by
the output of another thread if you do not take appropriate precautions. If this happens, the
outputs mix up and become messy. You have to code appropriately, with the help of a
dedicated mutex, in order not to end up with such an undesirable situation. Here by “dedicated”
we mean this; the mutex that you use for tidy output should not be the one that you use for
accessing the shared queue object. These two critical sections are different concepts and must
be handled via different mutexes.
Do not sleep a thread while a mutex is locked. We use sleeping to simulate the arrival duration
or checkout duration. We do not access shared resources while doing so. Thus, sleeping a
thread while a mutex is locked is totally nonsense.
Any violation to these rules will be penalized severely (50 points or more).
HW8DynIntQueue class and use of global variables
We provide a header file (HW8DynIntQueue.h) and its implementation
(HW8DynIntQueue.cpp) together with this homework. You have to use this queue class without any
change. In order to use it, include both the header and the .cpp to your project. Of course, you have to
copy these files to appropriate folders in your project.
Finally a good news; you may use global variables in this homework. Actually, it would be
miserable not to use them in a program that has several threads. However, we kindly request you not to
exaggerate the global usage since after a certain point you may lose control over your program (as the
famous Turkish proverb says “azı karar, coğu zarar”).
Sample Runs
Some sample runs are given below, but these are not comprehensive, therefore you have to consider all
cases, to get full mark.
Due to the probabilistic nature of the homework and due to scheduling of threads, same inputs may
yield different outputs for your code. However, the order of the events must be consistent with the
homework requirements and the given inputs. Nevertheless, occasional (i.e. rare) inconsistencies in the
display order of the events occurred at the same time are acceptable.
The inputs from the keyboard are written in boldface and italic.
Sample Run 1:
Please enter the total number of customers: 15
Please enter the number of customers waiting in the queue to open the second cashier:
2
Please enter the inter-arrival time range between two customers:
Min: 1
Max: 1
Please enter the checkout time range of cashiers:
Min: 1
Max: 1
Simulation starts 11:09:30
New customer with ID 1 has arrived (queue size is 1): 11:09:30
New customer with ID 2 has arrived (queue size is 2): 11:09:31
Cashier 1 started transaction with customer 1 (queue size is 1): 11:09:31
New customer with ID 3 has arrived (queue size is 2): 11:09:32
Cashier 2 started transaction with customer 2 (queue size is 1): 11:09:32
Cashier 1 finished transaction with customer 1 11:09:32
Cashier 1 started transaction with customer 3 (queue size is 0): 11:09:32
New customer with ID 4 has arrived (queue size is 1): 11:09:33
Cashier 2 finished transaction with customer 2 11:09:33
Cashier 1 finished transaction with customer 3 11:09:33
Cashier 1 started transaction with customer 4 (queue size is 0): 11:09:33
New customer with ID 5 has arrived (queue size is 1): 11:09:34
Cashier 1 finished transaction with customer 4 11:09:34
Cashier 1 started transaction with customer 5 (queue size is 0): 11:09:34
New customer with ID 6 has arrived (queue size is 1): 11:09:35
Cashier 1 finished transaction with customer 5 11:09:35
Cashier 1 started transaction with customer 6 (queue size is 0): 11:09:35
New customer with ID 7 has arrived (queue size is 1): 11:09:36
Cashier 1 finished transaction with customer 6 11:09:36
Cashier 1 started transaction with customer 7 (queue size is 0): 11:09:36
New customer with ID 8 has arrived (queue size is 1): 11:09:37
Cashier 1 finished transaction with customer 7 11:09:37
Cashier 1 started transaction with customer 8 (queue size is 0): 11:09:37
New customer with ID 9 has arrived (queue size is 1): 11:09:38
Cashier 1 finished transaction with customer 8 11:09:38
Cashier 1 started transaction with customer 9 (queue size is 0): 11:09:38
New customer with ID 10 has arrived (queue size is 1): 11:09:39
Cashier 1 finished transaction with customer 9 11:09:39
Cashier 1 started transaction with customer 10 (queue size is 0): 11:09:39
New customer with ID 11 has arrived (queue size is 1): 11:09:40
Cashier 1 finished transaction with customer 10 11:09:40
Cashier 1 started transaction with customer 11 (queue size is 0): 11:09:40
New customer with ID 12 has arrived (queue size is 1): 11:09:41
Cashier 1 finished transaction with customer 11 11:09:41
Cashier 1 started transaction with customer 12 (queue size is 0): 11:09:41
New customer with ID 13 has arrived (queue size is 1): 11:09:42
Cashier 1 finished transaction with customer 12 11:09:42
Cashier 1 started transaction with customer 13 (queue size is 0): 11:09:42
New customer with ID 14 has arrived (queue size is 1): 11:09:43
Cashier 1 finished transaction with customer 13 11:09:43
Cashier 1 started transaction with customer 14 (queue size is 0): 11:09:43
New customer with ID 15 has arrived (queue size is 1): 11:09:44
Cashier 1 finished transaction with customer 14 11:09:44
Cashier 1 started transaction with customer 15 (queue size is 0): 11:09:44
Cashier 1 finished transaction with customer 15 11:09:45
End of the simulation ends: 11:09:45
Press any key to continue . . .
Sample Run 2:
Please enter the total number of customers: 15
Please enter the number of customers waiting in the queue to open the second cashier:
5
Please enter the inter-arrival time range between two customers:
Min: 1
Max: 3
Please enter the checkout time range of cashiers:
Min: 1
Max: 8
Simulation starts 11:14:28
New customer with ID 1 has arrived (queue size is 1): 11:14:28
New customer with ID 2 has arrived (queue size is 2): 11:14:31
Cashier 1 started transaction with customer 1 (queue size is 1): 11:14:32
New customer with ID 3 has arrived (queue size is 2): 11:14:32
New customer with ID 4 has arrived (queue size is 3): 11:14:35
New customer with ID 5 has arrived (queue size is 4): 11:14:36
Cashier 1 finished transaction with customer 1 11:14:37
Cashier 1 started transaction with customer 2 (queue size is 3): 11:14:37
New customer with ID 6 has arrived (queue size is 4): 11:14:37
New customer with ID 7 has arrived (queue size is 5): 11:14:40
Cashier 2 started transaction with customer 3 (queue size is 4): 11:14:40
New customer with ID 8 has arrived (queue size is 5): 11:14:43
New customer with ID 9 has arrived (queue size is 6): 11:14:44
Cashier 1 finished transaction with customer 2 11:14:45
Cashier 1 started transaction with customer 4 (queue size is 5): 11:14:45
Cashier 2 finished transaction with customer 3 11:14:46
Cashier 2 started transaction with customer 5 (queue size is 4): 11:14:46
Cashier 1 finished transaction with customer 4 11:14:47
Cashier 1 started transaction with customer 6 (queue size is 3): 11:14:47
New customer with ID 10 has arrived (queue size is 4): 11:14:47
New customer with ID 11 has arrived (queue size is 5): 11:14:49
Cashier 1 finished transaction with customer 6 11:14:52
Cashier 1 started transaction with customer 7 (queue size is 4): 11:14:52
New customer with ID 12 has arrived (queue size is 5): 11:14:52
Cashier 1 finished transaction with customer 7 11:14:53
Cashier 1 started transaction with customer 8 (queue size is 4): 11:14:53
Cashier 2 finished transaction with customer 5 11:14:53
New customer with ID 13 has arrived (queue size is 5): 11:14:54
Cashier 2 started transaction with customer 9 (queue size is 4): 11:14:54
Cashier 1 finished transaction with customer 8 11:14:56
Cashier 1 started transaction with customer 10 (queue size is 3): 11:14:56
New customer with ID 14 has arrived (queue size is 4): 11:14:56
New customer with ID 15 has arrived (queue size is 5): 11:14:58
Cashier 2 finished transaction with customer 9 11:15:00
Cashier 2 started transaction with customer 11 (queue size is 4): 11:15:00
Cashier 2 finished transaction with customer 11 11:15:03
Cashier 1 finished transaction with customer 10 11:15:04
Cashier 1 started transaction with customer 12 (queue size is 3): 11:15:04
Cashier 1 finished transaction with customer 12 11:15:11
Cashier 1 started transaction with customer 13 (queue size is 2): 11:15:11
Cashier 1 finished transaction with customer 13 11:15:18
Cashier 1 started transaction with customer 14 (queue size is 1): 11:15:18
Cashier 1 finished transaction with customer 14 11:15:19
Cashier 1 started transaction with customer 15 (queue size is 0): 11:15:19
Cashier 1 finished transaction with customer 15 11:15:22
End of the simulation ends: 11:15:22
Press any key to continue . . .
Sample Run 3:
Please enter the total number of customers: 1
Please enter the number of customers waiting in the queue to open the second cashier:
1
Please enter the inter-arrival time range between two customers:
Min: 1
Max: 1
Please enter the checkout time range of cashiers:
Min: 1
Max: 1
Simulation starts 11:18:41
New customer with ID 1 has arrived (queue size is 1): 11:18:41
Cashier 1 started transaction with customer 1 (queue size is 0): 11:18:42
Cashier 1 finished transaction with customer 1 11:18:43
End of the simulation ends: 11:18:43
Press any key to continue . . .
Sample Run 4:
Please enter the total number of customers: 1
Please enter the number of customers waiting in the queue to open the second cashier:
1
Please enter the inter-arrival time range between two customers:
Min: 1
Max: 1
Please enter the checkout time range of cashiers:
Min: 1
Max: 1
Simulation starts 11:19:05
New customer with ID 1 has arrived (queue size is 1): 11:19:05
Cashier 2 started transaction with customer 1 (queue size is 0): 11:19:06
Cashier 2 finished transaction with customer 1 11:19:07
End of the simulation ends: 11:19:07
Press any key to continue . . .
Sample Run 5:
Please enter the total number of customers: 15
Please enter the number of customers waiting in the queue to open the second cashier:
1
Please enter the inter-arrival time range between two customers:
Min: 2
Max: 3
Please enter the checkout time range of cashiers:
Min: 1
Max: 1
Simulation starts 12:09:46
New customer with ID 1 has arrived (queue size is 1): 12:09:46
Cashier 2 started transaction with customer 1 (queue size is 0): 12:09:47
New customer with ID 2 has arrived (queue size is 1): 12:09:48
Cashier 1 started transaction with customer 2 (queue size is 0): 12:09:48
Cashier 2 finished transaction with customer 1 12:09:48
Cashier 1 finished transaction with customer 2 12:09:49
New customer with ID 3 has arrived (queue size is 1): 12:09:51
Cashier 1 started transaction with customer 3 (queue size is 0): 12:09:51
Cashier 1 finished transaction with customer 3 12:09:52
Cashier 2 started transaction with customer 4 (queue size is 0): 12:09:53
New customer with ID 4 has arrived (queue size is 1): 12:09:53
Cashier 2 finished transaction with customer 4 12:09:54
New customer with ID 5 has arrived (queue size is 1): 12:09:56
Cashier 2 started transaction with customer 5 (queue size is 0): 12:09:56
Cashier 2 finished transaction with customer 5 12:09:57
New customer with ID 6 has arrived (queue size is 1): 12:09:58
Cashier 2 started transaction with customer 6 (queue size is 0): 12:09:58
Cashier 2 finished transaction with customer 6 12:09:59
New customer with ID 7 has arrived (queue size is 1): 12:37:37
Cashier 1 started transaction with customer 7 (queue size is 0): 12:37:37
Cashier 1 finished transaction with customer 7 12:37:38
New customer with ID 8 has arrived (queue size is 1): 12:37:39
Cashier 1 started transaction with customer 8 (queue size is 0): 12:37:39
Cashier 1 finished transaction with customer 8 12:37:40
New customer with ID 9 has arrived (queue size is 1): 12:37:42
Cashier 1 started transaction with customer 9 (queue size is 0): 12:37:42
Cashier 1 finished transaction with customer 9 12:37:43
Cashier 1 started transaction with customer 10 (queue size is 0): 12:37:44
New customer with ID 10 has arrived (queue size is 1): 12:37:44
Cashier 1 finished transaction with customer 10 12:37:45
New customer with ID 11 has arrived (queue size is 1): 12:37:46
Cashier 1 started transaction with customer 11 (queue size is 0): 12:37:46
Cashier 1 finished transaction with customer 11 12:37:47
New customer with ID 12 has arrived (queue size is 1): 12:37:49
Cashier 2 started transaction with customer 12 (queue size is 0): 12:37:49
Cashier 2 finished transaction with customer 12 12:37:50
New customer with ID 13 has arrived (queue size is 1): 12:37:52
Cashier 1 started transaction with customer 13 (queue size is 0): 12:37:52
Cashier 1 finished transaction with customer 13 12:37:53
New customer with ID 14 has arrived (queue size is 1): 12:37:55
Cashier 2 started transaction with customer 14 (queue size is 0): 12:37:55
Cashier 2 finished transaction with customer 14 12:37:56
New customer with ID 15 has arrived (queue size is 1): 12:37:58
Cashier 2 started transaction with customer 15 (queue size is 0): 12:37:58
Cashier 2 finished transaction with customer 15 12:37:59
End of the simulation ends: 12:38:00
Press any key to continue . . .
Please see the previous homework specifications for the other important rules and
the submission guidelines
Last, but not the least, you are highly recommended to use Windows for this
homework. In multithreaded applications, there are several dependencies to the
underlying operating system. Thus the behavior that you see while running in a
Windows computer could be totally different than MacOS. Your code will be
tested in Windows and if it does not work, even if it works using Mac, we may not
re-evaluate your code due to hectic grading period at the end of the semester. To
sum up, use Mac at your own risk.
Good Luck!
Albert Levi, Vedat Peran
As you can see,
there are
inconsistencies
here in the display
order of the events
occurred at the
same time. As
mentioned before,
such occasional
inconsistencies
are acceptable.
