diff options
| -rw-r--r-- | .gitignore | 5 | ||||
| -rw-r--r-- | Makefile | 10 | ||||
| -rw-r--r-- | task-2-29994705.c | 233 | ||||
| -rw-r--r-- | task-2-29994705.h | 52 |
4 files changed, 296 insertions, 4 deletions
@@ -1,3 +1,6 @@ process-data.txt scheduler-result.txt -task-1-29994705
\ No newline at end of file +task-1-29994705 +vgcore* +task-*-29994705 +.vscode
\ No newline at end of file @@ -1,11 +1,15 @@ CC = gcc -CFLAGS = -Wall +CFLAGS = -Wall -g -ALL: task1 +ALL: task1 task2 task1: task-1-29994705.c $(CC) $(CFLAGS) task-1-29994705.c -o task-1-29994705 chmod +x task-1-29994705 +task2: task-2-29994705.c + $(CC) $(CFLAGS) task-2-29994705.c -o task-2-29994705 + chmod +x task-2-29994705 + clean: - rm task-1-29994705 + rm task-1-29994705 task-2-29994705 diff --git a/task-2-29994705.c b/task-2-29994705.c new file mode 100644 index 0000000..9e946bb --- /dev/null +++ b/task-2-29994705.c @@ -0,0 +1,233 @@ +/* + * 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; +} diff --git a/task-2-29994705.h b/task-2-29994705.h new file mode 100644 index 0000000..0675a74 --- /dev/null +++ b/task-2-29994705.h @@ -0,0 +1,52 @@ +/* + * task-1-29994705.h + * + * Alexander Occhipinti + * Student ID: 29994705 + * Created: 15 Oct 2020 + * Modified: 15 Oct 2020 + * + * The header file for task-1-29994705.c + * See task-1-29994705.c for documentation + * +*/ + +#ifndef _TASK2_H +#define _TASK2_H + +#define DEFAULT_INPUT_PATH "process-data.txt" // Default file path to read the process PCBs from before simulation +#define RESULT_FILE_PATH "scheduler-result.txt" // Default file path for the results after simulation +#define MAX_PATH_SIZE 256 +#define MAX_QUEUE_SIZE 10 +#define MAX_NUM_PROCS 10 +#define WAIT_PER_CYCLE 1 + + +/* Special enumerated data type for process state */ +typedef enum { + UNENTERED, READY, RUNNING, PAUSED, EXIT +} process_state_t; + + +/* C data structure used as process control block. + * The scheduler should create one instance + * per running process in the system +*/ +typedef struct { + char process_name[11]; // a string that identifies the process + + /* Times measured in seconds */ + int entryTime; // time process entered system + int serviceTime; // the total CPU time required by the process + int deadline; // The deadline of the process (for analysis) + + int remainingTime; // remaining service time until completion + int timeStarted; // the time the process entered the RUNNING state + int timeFinished; // the time the process entered the EXIT state (i.e. it completed) + + process_state_t state; // current process state (e.g. READY) + +} pcb_t; + + +#endif
\ No newline at end of file |