You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
725 lines
22 KiB
725 lines
22 KiB
/* License: AGPLv3 or later. https://www.gnu.org/licenses/licenses.html |
|
* |
|
* Assignment 2 - Discrete Simulation |
|
* Manish |
|
* Student Login: ***** |
|
* |
|
* Compile it as: |
|
* gcc -Wall -std=c11 -o ass2 ass2.c |
|
*/ |
|
|
|
#include <stdbool.h> |
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <string.h> |
|
|
|
enum category |
|
{ |
|
TOURIST = 0, |
|
BUSINESS = 1, |
|
}; |
|
|
|
typedef struct event |
|
{ |
|
// 0 for arrival 1+ for unique server ids |
|
int id; |
|
double time; |
|
int class; // 0 for tourist and 1 for business |
|
// service time for customer arrival and busy time for servers |
|
double duration; |
|
} event; |
|
|
|
// customers_queue is dynamically scaled |
|
typedef struct customers_queue |
|
{ |
|
int first; |
|
int next; |
|
int size; // memory in use |
|
int capacity; // memory allocated to queue |
|
event* queue; |
|
} customers_queue; |
|
|
|
typedef struct id_busy |
|
{ |
|
int id; // unique server ID |
|
double busy; // time server was busy |
|
} id_busy; |
|
|
|
// servers_queue are dynamically infantilized than not re-scaled |
|
typedef struct servers_queue |
|
{ |
|
int first; |
|
int next; |
|
int available; |
|
int capacity; |
|
id_busy* queue; |
|
} servers_queue; |
|
|
|
// Used as temporary storages for processing |
|
event arrival; |
|
event customer_in_queue; |
|
id_busy server; |
|
|
|
// Dynamically initialized than not re-scaled |
|
event* heap; |
|
int heap_size = 0; |
|
|
|
customers_queue business_q; |
|
customers_queue tourist_q; |
|
|
|
servers_queue business_servers; |
|
servers_queue tourist_servers; |
|
|
|
bool dummy_arrival(const event* arrival); |
|
int read_next_arrival(FILE* file, event* e); |
|
void read_back_next_arrival(FILE* file, event* e); |
|
void read_front_next_arrival(FILE* file, event* e); |
|
void shiftdown(int i); |
|
void shiftup(int i); |
|
void swap(event* i, event* j); |
|
|
|
event dequeue_customers(customers_queue* q); |
|
void enqueue_customers(customers_queue* q, const event* e); |
|
/* Used for sorting servers by id before printing output |
|
* Heap sort is used since we do not need stable sorting as all ids are unique |
|
* and heap sort sorts in place therefore require less memory than merge sort |
|
*/ |
|
void server_shiftdown(servers_queue* heap, int i); |
|
void server_makeheap(servers_queue* q); |
|
void server_sort(servers_queue* q); |
|
void server_swap(id_busy* i, id_busy* j); |
|
|
|
id_busy dequeue_servers(servers_queue* q); |
|
void enqueue_servers(servers_queue* q, const id_busy* s); |
|
void free_server(servers_queue* q); |
|
|
|
int max(int i, int j); |
|
|
|
int main(void) |
|
{ |
|
printf("Enter file name: "); |
|
char filename[257]; |
|
// Assuming filename/file path won't be longer than 256 characters |
|
scanf("%256s", filename); |
|
|
|
FILE* file = fopen(filename, "r"); |
|
if (!file) |
|
{ |
|
perror(filename); |
|
exit(EXIT_FAILURE); |
|
} |
|
|
|
for (int pass = 1; pass <= 2; pass++) |
|
{ |
|
rewind(file); // move file pointer back to beginning |
|
|
|
// Read no. of business and & tourist servers |
|
fscanf( |
|
file, |
|
"%d %d", |
|
&business_servers.available, |
|
&tourist_servers.available); |
|
|
|
arrival.id = 0; |
|
if (read_next_arrival(file, &arrival) == EOF) |
|
{ |
|
fprintf(stderr, "Error in reading 1st arrival. Exiting\n"); |
|
return 1; |
|
} |
|
|
|
// INITIALIZE/RESET VARIABLES |
|
heap = malloc( |
|
sizeof(event) |
|
* (1 + business_servers.available + tourist_servers.available)); |
|
|
|
business_servers.first = 0; |
|
business_servers.next = 0; |
|
business_servers.capacity = business_servers.available; |
|
business_servers.queue = malloc( |
|
sizeof(event) * business_servers.capacity); |
|
|
|
tourist_servers.first = 0; |
|
tourist_servers.next = 0; |
|
tourist_servers.capacity = tourist_servers.available; |
|
tourist_servers.queue = malloc( |
|
sizeof(event) * tourist_servers.capacity); |
|
|
|
if (heap == NULL |
|
|| business_servers.queue == NULL |
|
|| tourist_servers.queue == NULL) |
|
{ |
|
fprintf( |
|
stderr, |
|
"Failed to allocate memory for all data structures\n"); |
|
return 1; |
|
} |
|
|
|
business_q.first = 0; |
|
business_q.next = 0; |
|
business_q.size = 0; |
|
business_q.capacity = 0; |
|
// Memory is allocated only if needed |
|
business_q.queue = NULL; |
|
tourist_q.first = 0; |
|
tourist_q.next = 0; |
|
tourist_q.size = 0; |
|
tourist_q.capacity = 0; |
|
// Memory is allocated only if needed |
|
tourist_q.queue = NULL; |
|
|
|
for (int i = 0; i < business_servers.capacity; i++) |
|
{ |
|
business_servers.queue[i].id = i + 1; |
|
business_servers.queue[i].busy = 0; |
|
} |
|
for (int i = 0; i < tourist_servers.capacity; i++) |
|
{ |
|
tourist_servers.queue[i].id = i + business_servers.capacity + 1; |
|
tourist_servers.queue[i].busy = 0; |
|
} |
|
|
|
heap[heap_size++] = arrival; |
|
|
|
// Statistics Variables |
|
double time = 0; |
|
|
|
int max_q_length = 0; |
|
|
|
int no_of_business_customers = 0; |
|
double business_service_time = 0; |
|
double business_q_time = 0; |
|
int max_business_q_length = 0; |
|
|
|
int no_of_tourist_customers = 0; |
|
double tourist_service_time = 0; |
|
double tourist_q_time = 0; |
|
int max_tourist_q_length = 0; |
|
|
|
// MAIN LOOP |
|
while (heap_size > 0) |
|
{ |
|
time = heap[0].time; |
|
if (heap[0].id == 0) // Arrival |
|
{ |
|
if (heap[0].class == TOURIST) |
|
{ |
|
no_of_tourist_customers++; |
|
tourist_service_time += heap[0].duration; |
|
if (tourist_servers.available) |
|
{ |
|
// Time when server will finish serving |
|
heap[0].time += heap[0].duration; |
|
server = dequeue_servers(&tourist_servers); |
|
heap[0].id = server.id; |
|
// Total busy time of server |
|
heap[0].duration += server.busy; |
|
shiftdown(0); |
|
read_back_next_arrival(file, &arrival); |
|
} |
|
/* Available/free business servers will serve tourist |
|
* customer in 2nd pass if no business customer in q |
|
* NOTE: free server implies business_q is empty |
|
*/ |
|
else if (pass == 2 && business_servers.available) |
|
{ |
|
// Time when server will finish serving |
|
heap[0].time += heap[0].duration; |
|
server = dequeue_servers(&business_servers); |
|
heap[0].id = server.id; |
|
// Total busy time of server |
|
heap[0].duration += server.busy; |
|
shiftdown(0); |
|
read_back_next_arrival(file, &arrival); |
|
} |
|
// All relevant servers busy, add to tourist customers queue |
|
else |
|
{ |
|
enqueue_customers(&tourist_q, &heap[0]); |
|
max_tourist_q_length = max( |
|
max_tourist_q_length, tourist_q.size); |
|
max_q_length = max( |
|
max_q_length, tourist_q.size + business_q.size); |
|
read_front_next_arrival(file, &arrival); |
|
} |
|
} |
|
else if (heap[0].class == BUSINESS) |
|
{ |
|
no_of_business_customers++; |
|
business_service_time += heap[0].duration; |
|
if (business_servers.available) |
|
{ |
|
// Time when server will finish serving |
|
heap[0].time += heap[0].duration; |
|
server = dequeue_servers(&business_servers); |
|
heap[0].id = server.id; |
|
// Total busy time of server |
|
heap[0].duration += server.busy; |
|
shiftdown(0); |
|
read_back_next_arrival(file, &arrival); |
|
} |
|
// All relevant servers busy, add to tourist customers queue |
|
else |
|
{ |
|
enqueue_customers(&business_q, &heap[0]); |
|
max_business_q_length = max( |
|
max_business_q_length, business_q.size); |
|
max_q_length = max( |
|
max_q_length, tourist_q.size + business_q.size); |
|
read_front_next_arrival(file, &arrival); |
|
} |
|
} |
|
else |
|
{ |
|
fprintf( |
|
stderr, |
|
"Impossible scenario: Event = Arrival but Class = %d", |
|
heap[0].class); |
|
exit(1); |
|
} |
|
} |
|
else if ( // Business server finished serving |
|
heap[0].id >= 1 && heap[0].id <= business_servers.capacity) |
|
{ |
|
if (business_q.size > 0) // Customers waiting in queue |
|
{ |
|
customer_in_queue = dequeue_customers(&business_q); |
|
business_q_time += time - customer_in_queue.time; |
|
// Time when server will finish serving |
|
heap[0].time += customer_in_queue.duration; |
|
// Total busy time of server |
|
heap[0].duration += customer_in_queue.duration; |
|
shiftdown(0); |
|
} |
|
/* Freed business servers will serve tourist customer |
|
* 2nd pass if no business customer in q |
|
*/ |
|
else if (pass == 2 && tourist_q.size > 0) |
|
{ |
|
customer_in_queue = dequeue_customers(&tourist_q); |
|
// Time when server will finish serving |
|
tourist_q_time += time - customer_in_queue.time; |
|
heap[0].time += customer_in_queue.duration; |
|
// Total busy time of server |
|
heap[0].duration += customer_in_queue.duration; |
|
shiftdown(0); |
|
} |
|
else // free server at heap[0] and enqueue to business_servers |
|
free_server(&business_servers); |
|
} |
|
else if ( |
|
heap[0].id > business_servers.capacity |
|
&& heap[0].id <= (business_servers.capacity |
|
+ tourist_servers.capacity)) |
|
{ |
|
if (tourist_q.size > 0) // Customers waiting in queue |
|
{ |
|
customer_in_queue = dequeue_customers(&tourist_q); |
|
// Time when server will finish serving |
|
tourist_q_time += time - customer_in_queue.time; |
|
heap[0].time += customer_in_queue.duration; |
|
// Total busy time of server |
|
heap[0].duration += customer_in_queue.duration; |
|
shiftdown(0); |
|
} |
|
else // free server at heap[0] and enqueue to tourist_servers |
|
free_server(&tourist_servers); |
|
} |
|
else |
|
{ |
|
fprintf( |
|
stderr, |
|
"Impossible scenario Heap[0].id = %d is out of range\n", |
|
heap[0].id); |
|
exit(1); |
|
} |
|
} |
|
|
|
// COMPUTE REMAINING STATISTICS FROM TRACKED STATISTICS |
|
int total_customers = ( |
|
no_of_business_customers + no_of_tourist_customers); |
|
double avg_q_time = ( |
|
(business_q_time + tourist_q_time) / total_customers); |
|
double avg_q_length = ((business_q_time + tourist_q_time) / time); |
|
double avg_service_time = ( |
|
(business_service_time |
|
+ business_q_time |
|
+ tourist_q_time |
|
+ tourist_service_time) |
|
/ total_customers); |
|
|
|
double avg_business_q_time = ( |
|
business_q_time / no_of_business_customers); |
|
double avg_business_q_length = (business_q_time / time); |
|
double avg_business_service_time = ( |
|
(business_service_time + business_q_time) |
|
/ no_of_business_customers); |
|
|
|
double avg_tourist_q_time = (tourist_q_time / no_of_tourist_customers); |
|
double avg_tourist_q_length = (tourist_q_time / time); |
|
double avg_tourist_service_time = ( |
|
(tourist_service_time + tourist_q_time) / no_of_tourist_customers); |
|
|
|
// SIMULATION OUTPUT/PRINT SIMULATION STATISTICS |
|
char pass_title[80]; |
|
if (pass == 1) |
|
strncpy( |
|
pass_title, |
|
"Pass 1: Business servers exclusively serve business class", |
|
80); |
|
else if (pass == 2) |
|
strncpy( |
|
pass_title, |
|
"Pass 2: Idle business servers may serve tourist class", |
|
80); |
|
|
|
printf( |
|
"%s\n\n" |
|
"%-50s % 5d\n" |
|
"%-50s % 8.2lf\n\n" |
|
"%s\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 5d\n\n" |
|
"%s\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 5d\n\n" |
|
"%s\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 8.2lf\n" |
|
"%-50s % 5d\n" |
|
"\n", |
|
pass_title, |
|
"Number of people served: ", |
|
total_customers, |
|
"Time last service is completed: ", |
|
time, |
|
"Business class customers: ", |
|
"Average total service time: ", |
|
avg_business_service_time, |
|
"Average total time in queue: ", |
|
avg_business_q_time, |
|
"Ave length of queue: ", |
|
avg_business_q_length, |
|
"Maximum number queued: ", |
|
max_business_q_length, |
|
"Tourist class customers:", |
|
"Average total service time: ", |
|
avg_tourist_service_time, |
|
"Average total time in queue: ", |
|
avg_tourist_q_time, |
|
"Ave length of queue: ", |
|
avg_tourist_q_length, |
|
"Maximum number queued: ", |
|
max_tourist_q_length, |
|
"All customers:", |
|
"Average total service time: ", |
|
avg_service_time, |
|
"Average total time in queue: ", |
|
avg_q_time, |
|
"Ave length of queue: ", |
|
avg_q_length, |
|
"Maximum number queued: ", |
|
max_q_length); |
|
|
|
// Sort servers by ID before printing |
|
server_sort(&business_servers); |
|
printf("Business class servers:\n"); |
|
for (int i = 0; i < business_servers.capacity; i++) |
|
printf( |
|
"Total idle time for business class server %3d: %13.2lf\n", |
|
business_servers.queue[i].id, |
|
time - business_servers.queue[i].busy); |
|
|
|
// Sort servers by ID before printing |
|
server_sort(&tourist_servers); |
|
printf("\nTourist class servers:\n"); |
|
for (int i = 0; i < tourist_servers.capacity; i++) |
|
printf( |
|
"Total idle time for tourist class server %3d: %14.2lf\n", |
|
tourist_servers.queue[i].id - business_servers.capacity, |
|
time - tourist_servers.queue[i].busy); |
|
|
|
printf("\n\n\n"); |
|
|
|
// FREE DYNAMICALLY ALLOCATED MEMORY |
|
free(heap); |
|
free(business_servers.queue); |
|
free(tourist_servers.queue); |
|
free(business_q.queue); |
|
free(tourist_q.queue); |
|
} |
|
|
|
fclose(file); |
|
return 0; |
|
} |
|
|
|
bool dummy_arrival(const event* arrival) |
|
{ |
|
return ( |
|
arrival->time == 0 && arrival->duration == 0); |
|
} |
|
|
|
int read_next_arrival(FILE* file, event* e) |
|
{ |
|
return fscanf(file, "%lf %d %lf", &e->time, &e->class, &e->duration); |
|
} |
|
|
|
void read_back_next_arrival(FILE* file, event* e) |
|
{ |
|
// WARNING: Potential BUG: dummy_arrival(e) gets old arrival or new? |
|
if (fscanf(file, "%lf %d %lf", &e->time, &e->class, &e->duration) != EOF |
|
&& dummy_arrival(e) == false) |
|
{ |
|
heap[heap_size++] = *e; |
|
shiftup(heap_size - 1); |
|
} |
|
} |
|
|
|
void read_front_next_arrival(FILE* file, event* e) |
|
{ |
|
if (fscanf(file, "%lf %d %lf", &e->time, &e->class, &e->duration) != EOF |
|
&& dummy_arrival(e) == false) |
|
{ |
|
heap[0] = *e; |
|
} |
|
else |
|
{ // Since dummy arrival or EOF reached, pop heap[0] |
|
swap(&heap[0], &heap[--heap_size]); |
|
} |
|
shiftdown(0); |
|
} |
|
|
|
void shiftdown(int i) |
|
{ |
|
int child = (i * 2) + 1; // left child |
|
if (child < heap_size) // has at least one child |
|
{ |
|
if (child < heap_size - 1) // has both children |
|
{ |
|
// if right child smaller |
|
if (heap[child].time > heap[child + 1].time) |
|
child++; // pick right child |
|
} |
|
if (heap[i].time > heap[child].time) |
|
{ |
|
swap(&heap[i], &heap[child]); |
|
shiftdown(child); |
|
} |
|
} |
|
} |
|
|
|
void shiftup(int i) |
|
{ |
|
if (i == 0) |
|
return; |
|
int parent = (i - 1) / 2; |
|
if (heap[parent].time > heap[i].time) |
|
{ |
|
swap(&heap[parent], &heap[i]); |
|
shiftup(parent); |
|
} |
|
} |
|
|
|
void swap(event* i, event* j) |
|
{ |
|
event tmp = *i; |
|
*i = *j; |
|
*j = tmp; |
|
} |
|
|
|
event dequeue_customers(customers_queue* q) |
|
{ |
|
if (q->size-- == 0) |
|
{ |
|
fprintf( |
|
stderr, |
|
"Impossible scenario: dequeue_customers when queue empty"); |
|
exit(1); |
|
} |
|
event customer = q->queue[q->first++]; |
|
q->first %= q->capacity; |
|
if (q->size < q->capacity / 4) |
|
{ |
|
int new_capacity = (q->capacity / 2) + (q->capacity % 2); |
|
if (q->size != 0 |
|
&& (q->first >= new_capacity || q->next >= new_capacity)) |
|
{ |
|
/* Original queue: |
|
* XX--------|-------XXX |
|
* OR |
|
* --------XX|XXX------- |
|
* OR |
|
* -----------|-XXXXX---- |
|
* Where X has some number, - is empty place & | is new_capacity |
|
* Than, copy queue to next location and free old space |
|
*/ |
|
event* new_q = malloc(sizeof(event) * new_capacity); |
|
if (new_q == NULL) |
|
{ |
|
fprintf( |
|
stderr, |
|
"Failed to reallocate memory for customer_queue\n"); |
|
exit(1); |
|
} |
|
int j = 0; |
|
for (int i = q->first; i != q->next; i = (i + 1) % q->capacity) |
|
{ |
|
new_q[j++] = q->queue[i]; |
|
} |
|
free(q->queue); |
|
q->queue = new_q; |
|
q->first = 0; |
|
q->next = j; |
|
} |
|
else |
|
{ |
|
q->queue = realloc(q->queue, sizeof(event) * new_capacity); |
|
if (q->queue == NULL) // Probably unnecessary since shrinking |
|
{ |
|
fprintf( |
|
stderr, "Failed to reallocate memory for customer_queue\n"); |
|
exit(1); |
|
} |
|
if (q->size == 0) |
|
{ |
|
q->first = 0; |
|
q->next = 0; |
|
} |
|
} |
|
q->capacity = new_capacity; |
|
} |
|
return customer; |
|
} |
|
|
|
void enqueue_customers(customers_queue* q, const event* e) |
|
{ |
|
if (q->size == q->capacity) // Queue full |
|
{ |
|
// Double queue and adjust pointers |
|
// max() for when no space allocated previously i.e. capacity == 0 |
|
int new_capacity = max(q->capacity * 2, 1); |
|
q->queue = realloc(q->queue, sizeof(event) * new_capacity); |
|
if (q->queue == NULL) |
|
{ |
|
fprintf( |
|
stderr, "Failed to reallocate memory for customer_queue\n"); |
|
exit(1); |
|
} |
|
if (q->first != 0) |
|
{ |
|
/* Original queue: |
|
* XXX|XXXXXXX |
|
* After realloc: |
|
* XX|XXXXXXXX---------- |
|
* After this loop: |
|
* XX----------|XXXXXXXX |
|
* Where X has some number, - is empty place |
|
* and | is q->first pointer |
|
*/ |
|
for (int i = q->first; i < q->capacity; i++) |
|
{ |
|
q->queue[i + q->capacity] = q->queue[i]; |
|
} |
|
q->first += q->capacity; |
|
} |
|
/// MISSING THIS CORNER CASE WAS CAUSE OF A MAJOR BUG |
|
else |
|
q->next = q->size; |
|
|
|
q->capacity = new_capacity; |
|
} |
|
q->size++; |
|
q->queue[q->next++] = *e; |
|
q->next %= q->capacity; |
|
} |
|
|
|
id_busy dequeue_servers(servers_queue* q) |
|
{ |
|
if (q->available-- == 0) |
|
{ |
|
fprintf( |
|
stderr, |
|
"Impossible scenario: dequeue_servers when queue empty"); |
|
exit(1); |
|
} |
|
server = q->queue[q->first++]; |
|
q->first %= q->capacity; |
|
return server; |
|
} |
|
|
|
void enqueue_servers(servers_queue* q, const id_busy* s) |
|
{ |
|
if (q->available++ == q->capacity) |
|
{ |
|
fprintf( |
|
stderr, "Impossible scenario: enqueue_servers when queue full"); |
|
exit(1); |
|
} |
|
q->queue[q->next++] = *s; |
|
q->next %= q->capacity; |
|
} |
|
|
|
void free_server(servers_queue* q) |
|
{ |
|
server.id = heap[0].id; |
|
server.busy = heap[0].duration; |
|
enqueue_servers(q, &server); |
|
heap[0] = heap[--heap_size]; |
|
shiftdown(0); |
|
} |
|
|
|
int max(int i, int j) |
|
{ |
|
return (i > j) ? i : j; |
|
} |
|
|
|
void server_shiftdown(servers_queue* heap, int i) |
|
{ |
|
int child = (i * 2) + 1; // left child |
|
if (child < heap->available) // has at least one child |
|
{ |
|
if (child < heap->available - 1) // has both children |
|
{ |
|
// if right child smaller |
|
if (heap->queue[child].id < heap->queue[child + 1].id) |
|
child++; // pick right child |
|
} |
|
if (heap->queue[i].id < heap->queue[child].id) |
|
{ |
|
server_swap(&heap->queue[child], &heap->queue[i]); |
|
server_shiftdown(heap, child); |
|
} |
|
} |
|
} |
|
|
|
void server_makeheap(servers_queue* q) |
|
{ |
|
// Shiftdown Method |
|
int shiftdowns_required = (q->capacity / 2)-1; |
|
for (int i = shiftdowns_required; i >= 0; i--) |
|
{ |
|
server_shiftdown(q, i); |
|
} |
|
} |
|
|
|
void server_sort(servers_queue* q) |
|
{ |
|
server_makeheap(q); |
|
while(q->available > 0) |
|
{ |
|
server_swap(q->queue, &q->queue[--q->available]); |
|
server_shiftdown(q, 0); |
|
} |
|
q->available = q->capacity; |
|
} |
|
|
|
void server_swap(id_busy* i, id_busy* j) |
|
{ |
|
id_busy tmp = *i; |
|
*i = *j; |
|
*j = tmp; |
|
}
|
|
|