/* 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 #include #include #include 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; }