path: root/task-2-29994705.c

/*
 * task-2-29994705.c
 * 
 * FIT2100 Assignment 2 for S2/2020
 * 
 * Alexander Occhipinti
 * Student ID: 29994705
 * Created: 18 Oct 2020 
 * Modified: 19 Oct 2020 
 * 
 * This is the source file for Task 2 of Assignment 2.
 * This program simulates a RR (round robin) 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

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


/*
 * Finds the next process from an array of PCBs, which needs is next for the RR scheduler to execute.
 *  This function starts from where the scheduler last left off in the array (the scheduler's cursor) and moves it to
 *  the new PCB's index. It also updates the scheduler's `this_process` pointer which always points to the process the scheduler
 *  is currently working on.
 * 
 * Args:
 *  pcb_array: an array of PCBs (pcb_t) to search through
 *  num_pcbs: the number of PCBs in the array provided
 *  cursor: a pointer to the scheduler's current cursor which indicates which index it last left off from in the array.
 *          It is set to the index of the chosen PCB.
 *  this_process: a pointer to the pointer which refers to the process that is to be processed by the scheduler.
 *                It is set to a reference to the chosen PCB
 * 
 * Returns (int):
 *  0 or positive: the distance that the cursor moved to find the next process, wrapping around the end of the array if needed.
 *  -1: No process is READY, so can't chose one to execute. (i.e. idle)
*/
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;

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

/*
 * Scan through an array of PCBs and given a time, sets those that are due to enter the system to READY.
 *  Intended to simulate processes in the system being started while the scheduler is running.
 * 
 * Args:
 *  pcb_array: an array of PCBs (pcb_t) to search through
 *  num_pcbs: the number of PCBs in the array provided
 *  time: the current unit of time that the scheduler is up to.
*/
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;
}

/*
 * 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
*/
void perform_rr_scheduling(pcb_t *pcb_array, int num_pcbs) {

    /* Initialise values before starting */
    int time = 0, cursor = 0, distance_travelled = 0;
    int procs_left = num_pcbs;
    pcb_t *this_process = NULL;

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

        scan_ready_procs(pcb_array, num_pcbs, time); // Scan and mark processes that are now ready as 'READY'.

        /* If this_process is a null pointer, set it to the next process. (i.e. first run) */
        if (!this_process)
            find_next_process(pcb_array, num_pcbs, &cursor, &this_process);

        /* Simulate a single time cycle if there is a PCB to process */
        if (this_process) {

            /* Run the process for one cycle if it is already running*/
            if (this_process->state == RUNNING) {

                /* Checks if the current process has completed, sets its status to EXIT if so */
                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++;
                    distance_travelled = find_next_process(pcb_array, num_pcbs, &cursor, &this_process);
                    if (procs_left < 0) break;

                /* If this process' time quantum slice is over, switch to the next available process */
                } else if ((this_process->serviceTime-this_process->remainingTime) % TIME_QUANTUM == 0) {
                    this_process->state = READY;
                    cursor++;
                    distance_travelled = 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;
                if (distance_travelled == 0) // Only print a message if the process running has changed.
                    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_rr_scheduling(pcb_array, num_pcbs); // Run the simulation on the read-in PCB array
    return 0;
}