C++ program which uses queues and heaps for discrete event simulation to model t
ID: 3750807 • Letter: C
Question
C++ program which uses queues and heaps for discrete event simulation to model the queuing and service of a set of requests. Store all the event times on a heap and have a secondary array telling which server is doing what. Make sure to add appropreate comments to make the code more readable.
Input consists of the following data (given in the sample file below):
- The number of primary servers in the system.
- The number of secondary servers in the system.
- A set of service requests each consisting of an arrival time and two service times in the order primary followed by secondary. This set is terminated by a dummy record with arrival time and service times all equal to 0.
(Note: the arrival times are sorted in ascending order).
Your program should read the name of the data file from standard input and then read the data in the named file into the simulation as needed.
The simulation is to be of a system with two sets of servers, primary and secondary, each set of servers associated with a queue. Customers arrive in the system and are served first by a primary server and, on completion of this service, by a secondary server. If all servers of a particular type are busy, the customer will enter either the primary or secondary queue as appropriate.
The simulation should be run until the last customer has left the system.
Important Notes:
- Standard libraries of data structures and algorithms such as STL may not be used.
- The simulation starts at time = 0, not when the first customer arrives.
- You may assume that there are no more than 10 servers of each type, 20 total.
Output, to standard output will consist of the following data:
- Number of people served.
- Time last service request is completed.
- Average total service time.
- Average total time in queue(s). Both overall and separate.
- Average length of queue. For each queue and overall.
- Maximum Length of queue. For each queue and overall.
- Total idle time for each server.
The format of the output should look like this:
Number of people served: xxx
Time last service request completed: xxx.xxx
Avg total service time: x.xxx
Avg total time spent in primary servers: xx.xx
Avg total time spent in secondary servers: xx.xx
Avg total time spent in queues: xx.xx
Avg length of the primary servers: xx.xx
Avg length of the secondary servers: xx.xx
Avg length of the queues: xx.xx
Max length of primary servers: xx
Max length of secondary servers: xx
Max length of queues: xx
Idle times of servers:
Total idle time for each server in primary servers
0: xx.xx
1: xx.xx
2: xx.xx
Total idle time for each server in secondary servers
0: xx.xx
1: xx.xx
Please use this sample file to test this program:
3
2
0.490986897 1.385112773 3.590034257
1.241028335 1.794862289 1.360290065
1.767694437 3.508872586 2.528623235
2.108350758 1.697700393 1.24499551
2.171760494 4.453241905 3.352559789
2.63033819 3.074279642 3.506584411
3.501143903 3.197945668 3.69322067
3.919179966 1.587555336 1.554331602
4.285220927 2.462347587 3.712313223
4.903813035 1.601535549 1.476412114
5.880221024 1.711730329 2.620081524
6.332875975 2.593645279 2.283626938
7.21734923 1.02771052 1.126456304
8.151866418 1.123773959 2.715130524
8.665921869 4.476768016 3.039874078
9.160499093 1.726910146 2.63001837
9.43795821 3.055150814 1.074536682
9.740793279 1.371899802 2.147988246
10.18671208 3.377224803 1.517646447
10.54220008 3.175974072 2.767316669
11.29937684 3.304307858 2.503408972
11.39185977 3.378386574 2.551986442
Explanation / Answer
EventQueue.cpp
#include <iostream>
#include "EventQueue.h"
void swap(Event *A, Event *B);
EventQueue::EventQueue(int size) : _capacity(size), _n_events(0)
{
_q = new Event[_capacity];
}
void EventQueue::min_heapify(int i)
{
int smallest = i;
if (LEFT(i) <= _n_events && _q[LEFT(i)].ev_time < _q[i].ev_time)
smallest = LEFT(i);
if (RIGHT(i) <= _n_events && _q[RIGHT(i)].ev_time < _q[smallest].ev_time)
smallest = RIGHT(i);
if (smallest != i) {
swap(&_q[i], &_q[smallest]);
min_heapify(smallest);
}
}
void EventQueue::add_event(EventType ev_type, double ev_time, Customer &cust)
{
if (_n_events == _capacity - 1) {
std::cout << "Event queue overflow." << std::endl;
return;
}
int i = _n_events++;
Event new_event = { ev_type, ev_time, cust };
_q[i] = new_event;
// Fix min-heap property
while (i != 0 && _q[PARENT(i)].ev_time > _q[i].ev_time) {
swap(&_q[i], &_q[PARENT(i)]);
i = PARENT(i);
}
}
Event EventQueue::extract_next_event()
{
if (_n_events <= 0)
std::cout << "Event Queue underflow."<< std::endl;
if (_n_events == 1) {
_n_events--;
return _q[0];
}
Event next = _q[0];
_q[0] = _q[_n_events - 1];
_n_events--;
min_heapify(0);
return next;
}
bool EventQueue::more_events() { return _n_events > 0; }
void swap(Event *A, Event *B)
{
Event temp = *A;
*A = *B;
*B = temp;
}
EventQueue.h
#ifndef ASSIGNMENT02_C_VERSION_EVENTQUEUE_H
#define ASSIGNMENT02_C_VERSION_EVENTQUEUE_H
#define MAX(a,b) ( ((a) > (b)) ? (a) : (b) )
#define PARENT(i) ( (i-1) / 2 )
#define LEFT(i) ( (i * 2) + 1 )
#define RIGHT(i) ( (i * 2) + 2 )
enum EventType { eCustomerArrived = 0, eCustPrimaryFinished = 1, eCustSecondaryFinished = 2 };
struct Customer {
double arrival_time, p_service_duration, s_service_duration;
double wait_duration, cust_queued_time;
int server_idx;
};
struct Event {
EventType type; // type of event
double ev_time; // snapshot time of event to process
Customer cust; // customer for event
};
typedef Event Event;
typedef Customer Customer;
class EventQueue {
public:
explicit EventQueue(int size); // initialiser
void add_event(EventType ev_type, double ev_time, Customer &cust);
Event extract_next_event();
bool more_events();
private:
void min_heapify(int i);
int _n_events, _capacity;
Event *_q;
};
#endif //ASSIGNMENT02_C_VERSION_EVENTQUEUE_H
ServerQueue.cpp
#include <iostream>
#include "ServerQueue.h"
ServerQueue::ServerQueue(int size, char *name) : _capacity(size), _head(-1), _tail(-1), _n_customers(0), _name(name)
{
_max_q_len = 0;
_sum_q_len = _sum_q_len_time = _prev_q_len_change_time = 0;
_q = new Customer[_capacity];
}
void ServerQueue::add_waiting_customer(Customer &c, double ev_time)
{
calculate_average_queue_len(ev_time);
enqueue(c);
_max_q_len = MAX(_max_q_len, _n_customers);
}
void ServerQueue::calculate_average_queue_len(double ev_time)
{
// current_time - previous time length
double q_len_delta_time = ev_time - _prev_q_len_change_time; // last time the queue was changed
_sum_q_len += q_len_delta_time * _n_customers;
_sum_q_len_time += q_len_delta_time;
_prev_q_len_change_time = ev_time; // save the snapshot change time before enqueue/dequeue called
}
void ServerQueue::enqueue(Customer &c)
{
if (_n_customers == _capacity - 1)
std::cout << "Enqueue: " << _name << "Server_Q is full." << std::endl;
else {
if (_head == -1)
_head = 0;
_tail++;
_q[_tail] = c;
_n_customers++;
}
}
Customer ServerQueue::next_waiting_customer(double ev_time)
{
calculate_average_queue_len(ev_time);
return dequeue();
}
Customer ServerQueue::dequeue()
{
Customer cust;
if (_head == -1) {
std::cout << "Dequeue: " << _name << "_Server_Q is empty." << std::endl;
} else {
cust = _q[_head];
_head++;
if (_head > _tail)
_head = _tail = -1;
_n_customers--;
return cust;
}
}
int ServerQueue::get_max_q_len() const { return _max_q_len; }
double ServerQueue::get_avg_queue_len() const { return _sum_q_len / _sum_q_len_time; }
double ServerQueue::get_sum_q_len() const { return _sum_q_len; }
double ServerQueue::get_sum_q_len_time() const { return _sum_q_len_time; }
bool ServerQueue::is_empty() { return _head == -1; }
ServerQueue.h
#ifndef ASSIGNMENT02_C_VERSION_SERVERQUEUE_H
#define ASSIGNMENT02_C_VERSION_SERVERQUEUE_H
#include "EventQueue.h"
class ServerQueue {
public:
explicit ServerQueue(int size, char *name);
void add_waiting_customer(Customer &c, double ev_time);
void enqueue(Customer &c);
Customer dequeue();
Customer next_waiting_customer(double ev_time);
void calculate_average_queue_len(double ev_time);
bool is_empty();
int get_max_q_len() const;
double get_avg_queue_len() const;
double get_sum_q_len() const;
double get_sum_q_len_time() const;
private:
int _head, _tail, _capacity, _n_customers, _max_q_len;
double _sum_q_len, _sum_q_len_time, _prev_q_len_change_time;
Customer *_q;
char *_name;
};
#endif //ASSIGNMENT02_C_VERSION_SERVERQUEUE_H
Servers.cpp
#include <iostream>
#include <iomanip>
#include "Servers.h"
using namespace std;
// Constructor to create an _idle[] array of int index for idle servers
// and a Server[] array to store each server.
Servers::Servers(unsigned int size, char *name) : _capacity(size), _name(name), _n_idle_servers(0)
{
_head = _tail = -1;
_servers = new Server[_capacity];
_idle = new int[_capacity];
// loop through and initialise each server to _server[] array and
// enqueue their index int to the _idle[] FIFO queue
int i;
for (i = 0; i < _capacity; i++) {
Server new_server;
new_server.idx = i;
new_server.count = 0;
new_server.finish_time = new_server.total_idle_time = 0;
enqueue(new_server.idx);
_servers[i] = new_server;
}
}
// dequeue a server from the next available server from _idle[] queue
// and add the customer to the Server struct from the _server[]
void Servers::add_customer(Customer &c, double start_time, double finish_time)
{
// calculate_idle_times(start_time);
int next_avail_idx = dequeue();
if (next_avail_idx != -1) {
c.server_idx = next_avail_idx;
// stats for each server
// this service time accumulated
_servers[next_avail_idx].total_service_time += (finish_time - start_time);
// last time they served someone minus starting time for this event
_servers[next_avail_idx].total_idle_time += start_time - _servers[next_avail_idx].finish_time;
_servers[next_avail_idx].finish_time = finish_time;
_servers[next_avail_idx].count++;
}
}
// implementation for the dequeue of an index int from the _idle[] queue
int Servers::dequeue()
{
int s_id;
if (_head == -1) {
cout << "No Servers Available" << endl;
return -1;
} else {
s_id = _idle[_head];
_head++;
if (_head > _tail)
_head = _tail = -1;
_n_idle_servers--;
return s_id;
}
}
// add the server index int back to the _idle[] FIFO queue
void Servers::remove_customer(int s_idx)
{
enqueue(s_idx); // add server to idle queue
}
// FIFO enqueue implementation for an _idle[] int array of server indexes
void Servers::enqueue(int s_idx)
{
if (_n_idle_servers == _capacity)
cout << "Too many servers. ";
else {
if (_head == -1)
_head = 0;
_tail++;
_idle[_tail] = s_idx;
_n_idle_servers++;
}
}
// returns whether _idle[] queue is not empty
bool Servers::is_available() { return _n_idle_servers != 0; }
void Servers::display_server_statistics(double last_service_time)
{
int i;
cout << "Statistics for " << _name << " servers:" << endl;
cout << "|--------|-----------------|--------------------|" << endl;
cout << left << setw(10) << "| Server |"
<< setw(18) << " Total Idle Time |"
<< setw(21) << " Total Service Time |" << endl;
cout << "|--------|-----------------|--------------------|" << endl;
for (i = 0; i < _capacity; i++) {
// Final update
_servers[i].total_idle_time += last_service_time - _servers[i].finish_time;
cout << left << fixed << setprecision(4) << "| " << setw(3) << _servers[i].idx + 1 << " |"
<< right << setw(16) << _servers[i].total_idle_time << " |"
<< setw(19) << _servers[i].total_service_time << " |" << endl;
}
cout << "|--------|-----------------|--------------------|" << endl;
cout << endl;
}
Servers.h
#ifndef ASSIGNMENT02_C_VERSION_SERVERS_H
#define ASSIGNMENT02_C_VERSION_SERVERS_H
#define MIN(a,b) ( ((a) < (b)) ? (a) : (b) )
#include "EventQueue.h"
struct Server {
int idx;
// stats
int count;
double finish_time, total_idle_time, total_service_time;
};
typedef Server Server;
class Servers {
public:
explicit Servers(unsigned int size, char *name); // main initialiser
void add_customer(Customer &c, double start_time, double finish_time);
void remove_customer(int s_idx); // enqueue server
void enqueue(int s_idx);
int dequeue(); // dequeue server
bool is_available();
void display_server_statistics(double last_service_time);
private:
Server *_servers;
int *_idle;
char *_name;
int _head, _tail;
unsigned int _capacity, _n_idle_servers;
};
#endif //ASSIGNMENT02_C_VERSION_SERVERS_H
ass2.cpp
#include <cstring>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <iomanip>
#include "EventQueue.h"
#include "ServerQueue.h"
#include "Servers.h"
using namespace std;
/*====================| MACRO DEFINITIONS |====================*/
#define BUFFER_SZ 50
/*====================| STRUCT AND ENUM DEFINITIONS |====================*/
/*====================| FUNCTION PROTOTYPES |====================*/
void print_statistics(Servers, Servers, ServerQueue, ServerQueue, EventQueue);
/*====================| CLASS DEFINITIONS |====================*/
/*====================| GLOBAL VARIABLE DEFINITIONS |====================*/
int n_total_cust;
double last_service_completed, total_service_time, p_server_q_wait_times, s_server_q_wait_times;
int p_server_n_cust, s_server_n_cust;
int main(int argc, const char* argv[])
{
cout<<"|===============| CSCI203 Assignment 02 |===============| Author: Dinh Che (codeninja55 | dbac496)"<<endl;
char filename[BUFFER_SZ];
ifstream fin;
// Check for any args passed or prompt for filename to be read from
if (argc == 2) // arg passed
strncpy(filename, argv[1], BUFFER_SZ);
else { // no arg passed, prompt for filename
cout << "Input file name >> ";
cin.getline(filename, BUFFER_SZ);
}
// open file to read and check if correctly opened
fin.open(filename);
if (!fin.good()) {
cout << "[!!] Error: Failed to open file " << filename << " Exiting... ";
return -1;
}
// Initialise servers from read in file parameters
unsigned int n_p_servers, n_s_servers;
fin >> n_p_servers >> n_s_servers;
char p_name[] = "Primary";
char s_name[] = "Secondary";
Servers p_servers = Servers(n_p_servers, p_name); // wrapper class for array of primary server structs
Servers s_servers = Servers(n_s_servers, s_name); // wrapper class for array of secondary server structs
// Initialise queues
ServerQueue p_server_q = ServerQueue(1000, p_name); // FIFO queue - waiting to be served by a p server
ServerQueue s_server_q = ServerQueue(1000, s_name); // FIFO queue - waiting to be served by a s server
EventQueue event_q = EventQueue(1000); // Priority queue implemented as a heap with an array - main event queue
// Statistic counters initialisers
n_total_cust = 0;
last_service_completed = total_service_time = p_server_q_wait_times = s_server_q_wait_times = 0;
p_server_n_cust = s_server_n_cust = 0;
bool cust_arrival_flag = true; // flag to be changed if no other events to read from file
// Read first customer from file
Customer first_cust;
first_cust.wait_duration = 0;
fin >> first_cust.arrival_time
>> first_cust.p_service_duration
>> first_cust.s_service_duration;
// add the first customer to the event_q
event_q.add_event(eCustomerArrived, first_cust.arrival_time, first_cust);
// main simulation event loop
while (event_q.more_events()) { // check if there are any more events waiting to be processed
// the top priority event based on (min) event_time when added
Event ev = event_q.extract_next_event();
switch (ev.type) {
case eCustomerArrived:
// read next customer from file and put them in event_q on arrival_time
if (cust_arrival_flag) {
Customer next_read_cust;
fin >> next_read_cust.arrival_time
>> next_read_cust.p_service_duration
>> next_read_cust.s_service_duration;
// break loop if 0, 0, 0 reached in txt file and close file
if (next_read_cust.arrival_time == 0.0 && next_read_cust.p_service_duration == 0.0) {
cust_arrival_flag = false;
fin.close();
} else {
next_read_cust.wait_duration = 0;
event_q.add_event(eCustomerArrived, next_read_cust.arrival_time, next_read_cust);
}
}
if (p_servers.is_available()) { // p server in array to be dequeue'd
double p_service_finish_time = ev.cust.arrival_time + ev.cust.p_service_duration;
p_servers.add_customer(ev.cust, ev.ev_time, p_service_finish_time);
event_q.add_event(eCustPrimaryFinished, p_service_finish_time, ev.cust);
} else {
ev.cust.cust_queued_time = ev.ev_time;
p_server_q.add_waiting_customer(ev.cust, ev.ev_time);
p_server_n_cust++;
}
break;
case eCustPrimaryFinished:
// free up a server in primary server array
p_servers.remove_customer(ev.cust.server_idx);
total_service_time += (ev.cust.p_service_duration + ev.cust.wait_duration); // wait_duration only for p
if (s_servers.is_available()) {
double s_service_finish_time = ev.ev_time + ev.cust.s_service_duration;
s_servers.add_customer(ev.cust, ev.ev_time, s_service_finish_time);
event_q.add_event(eCustSecondaryFinished, s_service_finish_time, ev.cust );
} else {
ev.cust.cust_queued_time = ev.ev_time;
s_server_q.add_waiting_customer(ev.cust, ev.ev_time);
s_server_n_cust++;
}
break;
case eCustSecondaryFinished:
// free up a server in secondary server array
s_servers.remove_customer(ev.cust.server_idx);
n_total_cust++;
total_service_time += (ev.cust.s_service_duration + ev.cust.wait_duration);
if (!event_q.more_events()) {
last_service_completed = ev.ev_time;
// p_server_q.calculate_average_queue_len(last_service_completed);
// s_server_q.calculate_average_queue_len(last_service_completed);
}
break;
}
// Check if there are any secondary servers available to process
// someone in queue if there is a queue
if (!s_server_q.is_empty() && s_servers.is_available()) {
Customer waiting_cust = s_server_q.next_waiting_customer(ev.ev_time);
waiting_cust.wait_duration = ev.ev_time - waiting_cust.cust_queued_time;
double s_server_finish_time = ev.ev_time + waiting_cust.s_service_duration;
s_servers.add_customer(waiting_cust, ev.ev_time, s_server_finish_time);
event_q.add_event(eCustSecondaryFinished, s_server_finish_time, waiting_cust);
s_server_q_wait_times += waiting_cust.wait_duration; // accumulate waiting time stats
}
// Check if there are any primary servers available to process
// someone in queue if there is a queue
if (!p_server_q.is_empty() && p_servers.is_available()) {
Customer waiting_cust = p_server_q.next_waiting_customer(ev.ev_time);
waiting_cust.wait_duration = ev.ev_time - waiting_cust.cust_queued_time;
double p_server_finish_time = ev.ev_time + waiting_cust.p_service_duration;
p_servers.add_customer(waiting_cust, ev.ev_time, p_server_finish_time);
event_q.add_event(eCustPrimaryFinished, p_server_finish_time, waiting_cust);
p_server_q_wait_times += waiting_cust.wait_duration; // accumulate waiting time stats
}
}
print_statistics(p_servers, s_servers, p_server_q, s_server_q, event_q);
cout << "|=======| Assignment 02 -- Simulation Complete |=======|" << endl << endl;
return 0;
}
void print_statistics(Servers p_servers, Servers s_servers, ServerQueue p_server_q, ServerQueue s_server_q, EventQueue event_q)
{
cout << " |=======| Assignment 02 -- Simulation Statistics |=======|" << endl << endl;
cout << fixed << setprecision(3) << left << setfill('.') << setw(50) << "Number of People Served:" << " "
<< n_total_cust << endl;
cout << left << setw(50) << "Time Last Service Request Completed:" << " "
<< last_service_completed << endl;
cout << left << setw(50) << "Total Service Time:" << " "
<< total_service_time << endl;
cout << left << setw(50) << "Average Total Service Time:" << " "
<< total_service_time / n_total_cust << endl << endl;
cout << left << setw(50) << "Total Time in Queues:" << " "
<< ((p_server_q_wait_times + s_server_q_wait_times) / (p_server_n_cust + s_server_n_cust))
* (p_server_n_cust + s_server_n_cust) << endl;
cout << left << setw(50) << "Average Time Spent in Primary Server Queue:" << " "
<< p_server_q_wait_times / p_server_n_cust << endl;
cout << left << setw(50) << "Average Time Spent in Secondary Server Queue:" << " "
<< s_server_q_wait_times / s_server_n_cust << endl;
cout << left << setw(50) << "Average Total Time in Queues:" << " "
<< (p_server_q_wait_times + s_server_q_wait_times) / (p_server_n_cust + s_server_n_cust)
<< endl << endl;
// TODO
cout << left << setw(50) << "Average Length of the Primary Server Queue:" << " "
<< p_server_q.get_avg_queue_len() << endl;
cout << left << setw(50) << "Average Length of the Secondary Server Queue:" << " "
<< s_server_q.get_avg_queue_len() << endl;
cout << left << setw(50) << "Average Length of the Queues:" << " "
<< (p_server_q.get_sum_q_len() + s_server_q.get_sum_q_len()) /
(p_server_q.get_sum_q_len_time() + s_server_q.get_sum_q_len_time())
<< endl << endl;
cout << left << setw(50) << "Max Length of Primary Server Queue:" << " "
<< p_server_q.get_max_q_len() << endl;
cout << left << setw(50) << "Max Length of Secondary Server Queue:" << " "
<< s_server_q.get_max_q_len() << endl;
cout << left << setw(50) << "Max Length of Queues:" << " "
<< MAX(p_server_q.get_max_q_len(), s_server_q.get_max_q_len())
<< endl << endl << setfill(' ');
p_servers.display_server_statistics(last_service_completed);
s_servers.display_server_statistics(last_service_completed);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.