path: root/task-2-29994705.c

/*
 * task-1-29994705.c
 * 
 * FIT2100 Assignment 2 for S2/2020
 * 
 * Alexander Occhipinti
 * Student ID: 29994705
 * Created: 14 Oct 2020 
 * Modified: 15 Oct 2020 
 * 
 * This is the source file for Task 1 of Assignment 2.
 * This program simulates a FCFS (first-come-first-serve) scheduler with at most 10 simulated processes.
 * These processes are read from file, simulated, then results are exported to "process-data.txt".
 * These results include wait time, turnaround time and whether the deadline was met for each process.
 * The purpose of this is to compare various scheduling algorithms.
 *  
*/

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "task-2-29994705.h"

// NOTE: the structs provided in the assignment document are in the header file

/*
 * Compares two pcb_t structs to determine the order between the two in a FCFS system.
 *  This function is designed to interface with C's qsort function.
 * 
 * Args:
 *  pcb_a: any given process' PCB as a pcb_t
 *  pcb_b: any given process' PCB as a pcb_t
 * 
 * Returns (int):
 *  -1 if pcb_a comes before b
 *  0 if both equal
 *  1 if pcb_a comes after b
 * 
*/
int fcfs_compare(const void *pcb_a, const void *pcb_b) {
    pcb_t *pcb_x = (pcb_t *) pcb_a;
    pcb_t *pcb_y = (pcb_t *) pcb_b;
    return pcb_x->entryTime - pcb_y->entryTime;
}

/*
 * Reads and interprets a file containing process PCBs to simulate in the given format:
 *  [Process Name] [Arrival Time] [Service Time] [Deadline]
 *  separated by spaces.
 * Writes these PCBs to a given array via a pointer to be simulated later.
 * 
 * Args:
 *  file_path: the path to the input file
 *  pcb_array: an array to write PCBs into
 *  array_size: the size of the given PCB array
 * 
 * Returns (int):
 *  The number of PCBs actually read from the file. (May be less than the maximum array size)
 * 
*/
int pcbs_from_file(char* file_path, pcb_t *pcb_array, int array_size) {
    FILE *fp;
    fp = fopen(file_path, "r");
    int i;

    /* Read PCBs in from file until array is full or the file ends */
    for (i = 0; i<array_size && !feof(fp); i++){
        pcb_t process;
        fscanf(fp, "%s %d %d %d", process.process_name, &process.entryTime, &process.serviceTime, &process.deadline);
        /* Initialise values in the struct */
        process.state = UNENTERED;
        process.remainingTime = process.serviceTime;
        pcb_array[i] = process;
    }
    fclose(fp);
    return i;
}

/* 
 * Calculates and exports results to the default file path after a simulation, provided a list of PCBs.
 *  Writes to a file information in the following format:
 *  [Process Name] [Wait Time] [Turnaround Time] [Deadline Met]
 *  separated by spaces.
 * 
 * Args:
 *  pcb_array: an array of process PCBs after a simulation (i.e. experimental data filled into each struct)
 *  num_pcbs: the number of PCBs in the array provided
 * 
 * Returns void
 * 
*/
void export_results(pcb_t *pcb_array, int num_pcbs) {
    FILE *fp;
    fp = fopen(RESULT_FILE_PATH, "w");
    for (int i = 0; i < num_pcbs; i++) {
        int wait_time, turnaround_time, met_deadline;
        wait_time = pcb_array[i].timeStarted - pcb_array[i].entryTime;
        turnaround_time = pcb_array[i].timeFinished - pcb_array[i].entryTime;
        met_deadline = turnaround_time <= pcb_array[i].deadline;
        fprintf(fp, "%s %d %d %d\n", pcb_array[i].process_name, wait_time, turnaround_time, met_deadline);
    }
    fclose(fp);
}

/*
 * The function that runs the main FCFS scheduling simulation loop, provided an array of process PCBs to simulate.
 *  Each loop represents a single unit of time, where processes may either be become ready, start running or finish.
 *  For each unit of time, the following happens (in order):
 *   Each process is checked to see if it is ready (i.e. simulating the user or system starting a new process)
 *   The current running process is checked to see if it has finished executing
 *   The next process in the array (determined by FCFS) is checked to see if it is able to be run (i.e. no other process running)
 *   The scheduler sleeps for a short amount of time (one second by default) and the simulated time is incremeneted by one unit
 *  The simulation terminates once every process has been completed, then the results are exported. 
 * 
 * Args:
 *  pcb_array: An array of process PCB structs to run the simulation on
 *  num_pcbs: the number of PCBs in the provided array
 * 
 * Returns void
*/

int find_next_process(pcb_t *pcb_array, int num_pcbs, int *cursor, pcb_t **this_process) {
    int i;
    int started_from = *cursor;
    for (i = 0; i<num_pcbs; i++) {
        *cursor = (started_from + i) % num_pcbs;
        // printf("(%d,%d)", *cursor, num_pcbs);
        // printf("[%d]", pcb_array[*cursor].state);
        // printf("{%d}", i);

        if (pcb_array[*cursor].state == READY) {
            *this_process = &pcb_array[*cursor];
            return 1;
        }
    }
    return 0;
}


int scan_ready_procs(pcb_t *pcb_array, int num_pcbs, int time){
    int total_ready = 0;
    for (int i = 0; i < num_pcbs; i++) {
        if (pcb_array[i].entryTime <= time && pcb_array[i].state == UNENTERED) {
            pcb_array[i].state = READY;
            total_ready++;
            printf("Time %d: Process %s entered the system.\n", time, pcb_array[i].process_name);
        }
    }
    return total_ready;
}

void perform_fcfs_scheduling(pcb_t *pcb_array, int num_pcbs) {

    qsort(pcb_array, num_pcbs, sizeof(pcb_t), fcfs_compare); // Sort the PCB array in the order determined by the FCFS algorithm (via comparison function)
    int time = 0;
    int cursor = 0;
    int procs_left = num_pcbs;
    pcb_t *this_process = NULL;

    // for (int i = 0; i < num_pcbs; i++) {
    //     if (pcb_array[i].entryTime <= time && pcb_array[i].state == UNENTERED) {
    //         pcb_array[i].state = READY;
    //         printf("Time %d: Process %s entered the system.\n", time, pcb_array[i].process_name);
    //     }
    // }

    // this_process = find_next_process(pcb_array, num_pcbs, &cursor, &finished_flag);

    while (procs_left > 0) { // Loop until all processes are finished

        
        int num_procs_ready = scan_ready_procs(pcb_array, num_pcbs, time);

        if (!this_process)
            find_next_process(pcb_array, num_pcbs, &cursor, &this_process);

        if (this_process) {
            /* Checks if the current process has completed, sets its status to EXIT if so */
            if (this_process->state == RUNNING) {
                // printf("Time %d: Process %s is running.\n", time, this_process->process_name);
                if (--this_process->remainingTime == 0) { // Is there no remaining time left?
                    this_process->state = EXIT;
                    this_process->timeFinished = time;
                    printf("Time %d: Process %s has finished executing.\n", time, this_process->process_name);
                    procs_left--;
                    cursor++;
                    find_next_process(pcb_array, num_pcbs, &cursor, &this_process);
                    if (procs_left < 0) break;
                } else if ((this_process->serviceTime-this_process->remainingTime) % 2 == 0) {
                    this_process->state = READY;
                    cursor++;
                    find_next_process(pcb_array, num_pcbs, &cursor, &this_process);
                }
            }

            /* Checks if the current process ready for execution and sets its status to RUNNING */
            if (this_process->state == READY) {
                this_process->state = RUNNING;
                this_process->timeStarted = time;
                printf("Time %d: Process %s is now running.\n", time, this_process->process_name);
            }

        } else {
            printf("Time %d: CPU is idle.\n", time);
        }

        // Sleep and continue to the next unit of time
        sleep(WAIT_PER_CYCLE);
        time++;
    }

    export_results(pcb_array, num_pcbs);
}


/*
 * The Main function, called when the program is started
 * Reads PCBs from file, simulates the scheduler on them, then exports the results.
 * 
 * Interprets the following program arguments:
 *  0 args: runs with the DEFAULT_INPUT_PATH as the input file
 *  1 arg: (a path to a text file): exports the results to the given path 
*/
int main(int argc, char *argv[]) {
    char in_path[MAX_PATH_SIZE] = DEFAULT_INPUT_PATH; // Initialise the PCB input file path to the default one
    if (argc > 1) strncpy(in_path, argv[1], MAX_PATH_SIZE); // Set the input path to the first argument if it was provided

    pcb_t pcb_array[MAX_NUM_PROCS]; // Init the array that will hold the PCBs
    int num_pcbs = pcbs_from_file(in_path, pcb_array, MAX_NUM_PROCS); // Read the PCBs from the provided file path, into the PCB array
    perform_fcfs_scheduling(pcb_array, num_pcbs); // Run the simulation on the read-in PCB array
    return 0;
}