5
\$\begingroup\$

Recently I completed my first assignment at the university. The assignment is :

Write a CPU scheduling simulator that uses the Shortest Job First and Priority scheduling methods. Both of these should also have a "preemptive" and "non-preemptive" option. Each process information will be read through a text file and to know which algorithm to use you get input through the command line before running your program.

Since it's my first official assignment I would like to know if my code is good and clear enough. Also I would like to hear tips about things I should change, for the program specifically, or my coding in general.

#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdlio.h>

/**
Program that simulates a CPU Scheduler. Uses Shortest Job First and Priority First scheduling methods, on both preemptive and non-preemptive mode
*/

//Enum to hold which algorithm should be called. sjf(shortest job first) or priority(priority scheduling algorithm)
typedef enum
{
    sjf,
    priority
}AlgorithmToCall;

//Struct to hold each procedure's information :
typedef struct Procedure
{
    int procID;
    int arrivalTime;
    int serviceTime;
    int priority;
    int waitTime;
    int finishTime;
    int turnAroundTime;
    int startTime;
    int remainingTime;
    struct Procedure* nextProc;
}Procedure;

//Procedure methods :
Procedure* CreateProc(); // Method to create  dynamically a procedure and return the pointer
void SwapContents(Procedure* proc1, Procedure* proc2); // Method to swap the content of two procedure's by value(everything except nextProc pointer , turnAroundTime and finishTime)

//Struct to hold a Queue :
typedef struct Queue
{
    Procedure* ptrHead;
    Procedure* ptrTail;
}Queue;

//Queue methods :
Queue* CreateQueue(); // Method to create  dynamically a Queue item and return the pointer
void SortQueueByArrival(Queue* const queueToSort, AlgorithmToCall currentState); //Method to sort a queue by arrival time
void AddToQueue(Queue* const queueToAdd, Procedure* const item); // Method to add an element in the queue
void FreeQueue(Queue* const queueToFree); // Method to free the elements(Procedures) of the queue
bool QueueIsEmpty(const Queue* const queueToCheck); // Method to check if a queue is empty


//Input / Output methods :
int ReadFileData(Queue* const dataHolder, FILE* const fileToRead); // Method to read the file's data and store them in the entry queue
void PrintValues(Queue* const outputQueue, int total); // Method to print the values after simulation is complete

//Simulation methods :
void UpdateEntryQueue(Queue* const inputQueue, Queue* const simulationQueue, int currentTime); //Method to update the entry queue
void Tick(Queue* const simulationQueue, Queue* const outputQueue, int currentTime, bool bIsPreemptive, void(*functionToCall)(Queue* const)); //Method to update the simulation queue  
void FindNextSJF(Queue* const simulationQueue); // Method to find next proccess that should run with shortest job first
void FindNextPriority(Queue* const simulationQueue); // Method to find the next proccess that should run with priority scheduling

int main(int argc, char *argv[])
{
    //Enum to hold the state the user chooses(sjf or priority)
    AlgorithmToCall whichOne;

    //bool to hold if the sim is ran on preemptive mode
    bool bisPreemptive;

    //File pointer to open the input file the user chooses
    FILE* ptrProcsFile;

    if (argc != 4) //First we check if the arguments from the command line are 4(including this program's name)
    {
        printf("Error! Invalid number of arguments!");
        exit(0);
    }

    if (strcmp(argv[1], "sjf") == 0 || strcmp(argv[1], "SJF") == 0) //Then we check if the first argument is correct(should be "sjf" or "priority") and store the input in the enum
        whichOne = sjf;
    else if (strcmp(argv[1], "priority") == 0 || strcmp(argv[1], "PRIORITY") == 0)
        whichOne = priority;
    else
    {
        printf("Error! Invalid algorithm call!");
        exit(1);
    }

    if (strcmp(argv[2], "p") == 0 || strcmp(argv[2], "P") == 0) //Then we check if the is-preemptive argument is correct(should be 'p' or 'np') and store the input in the bIsPreemptive bool
        bisPreemptive = true;
    else if (strcmp(argv[2], "np") == 0 || strcmp(argv[2], "NP") == 0)
        bisPreemptive = false;
    else
    {
        printf("Error! Invalid pre-emptiveness");
        exit(2);
    }

    ptrProcsFile = fopen(argv[3], "r");
    if (ptrProcsFile == NULL) //And last , we check if the holding each procedures information is correctly opened
    {
        printf("Error! File %s could not be opened!", argv[3]);
        exit(3);
    }

    Queue* entryQueue = CreateQueue(); //Then we create a dynamic Queue to hold the text's data

    int totalProcs = ReadFileData(entryQueue, ptrProcsFile); //And we read the data from the text file , storing them to the entryQueue
    fclose(ptrProcsFile); //After we're done , we close the file

    SortQueueByArrival(entryQueue, whichOne); //Then we call the sort queue on the entry queue

    //Check which state we are in(sjf or priority)
    if (whichOne == sjf)
    {
        Queue* simulationQueue = CreateQueue(); //Create a simulation queue to hold procedure's leaving the entry queue
        Queue* outputQueue = CreateQueue(); //And an output queue to hold procedure's leaving the simulation queue
        int currentTime = 0; //Initialise the time to 0
        UpdateEntryQueue(entryQueue, simulationQueue, currentTime); //Move the first procedure in the simulation queue
        while (true)
        {
            if (QueueIsEmpty(entryQueue) && QueueIsEmpty(simulationQueue)) //Loop until both entry and simulation queues are empty
                break;
            //On each time step , increment the time by 1 , and update both queues(entry and simulation)
            currentTime++;
            UpdateEntryQueue(entryQueue, simulationQueue, currentTime);
            Tick(simulationQueue, outputQueue, currentTime, bisPreemptive, &FindNextSJF);
        }
        //After the sim is complete , free entry and simulation queues
        free(entryQueue);
        free(simulationQueue);
        //Then , print the output queue on the screen , free each output queue procedure seperately and finally free the output queue
        printf("\n\t\t\t\t---/ Shortest Job First Output \\---\n\n");
        PrintValues(outputQueue, totalProcs);
        FreeQueue(outputQueue);
        free(outputQueue);
    }
    else
    {
        //Same as sjf procedure , only difference we call the Tick function with FindNextPriority method pointer
        Queue* simulationQueue = CreateQueue();
        Queue* outputQueue = CreateQueue();
        int currentTime = 0;
        UpdateEntryQueue(entryQueue, simulationQueue, currentTime);
        while (true)
        {
            if (QueueIsEmpty(entryQueue) && QueueIsEmpty(simulationQueue))
                break;
            currentTime++;
            UpdateEntryQueue(entryQueue, simulationQueue, currentTime);
            Tick(simulationQueue, outputQueue, currentTime, bisPreemptive, &FindNextPriority);
        }
        free(entryQueue);
        free(simulationQueue);
        printf("\n\t\t\t\t---/ Priority Scheduling Output \\--- \n\n");
        PrintValues(outputQueue, totalProcs);
        FreeQueue(outputQueue);
        free(outputQueue);
    }
    return 0;
}

//Creates a procedure item dynamically , checks if the creation was successfull and returns the address of the item
Procedure* CreateProc()
{
    Procedure* temp = (Procedure*)malloc(sizeof(Procedure));
    if (temp == NULL)
    {
        printf("Error! Malloc failed at procedure creation!");
        exit(5);
    }
    temp->nextProc = NULL;
    return temp;
}

//Method to swap two procedures contents by value
void SwapContents(Procedure* proc1, Procedure* proc2)
{
    Procedure temp = *proc1;

    proc1->arrivalTime = proc2->arrivalTime;
    proc1->priority = proc2->priority;
    proc1->serviceTime = proc2->serviceTime;
    proc1->procID = proc2->procID;
    proc1->startTime = proc2->startTime;
    proc1->waitTime = proc2->waitTime;
    proc1->remainingTime = proc2->remainingTime;

    proc2->arrivalTime = temp.arrivalTime;
    proc2->priority = temp.priority;
    proc2->serviceTime = temp.serviceTime;
    proc2->procID = temp.procID;
    proc2->startTime = temp.startTime;
    proc2->waitTime = temp.waitTime;
    proc2->remainingTime = temp.remainingTime;
}

//Creates a Queue item dynamically , checks if the creation was successfull and returns the address of the item
Queue* CreateQueue()
{
    Queue* temp = (Queue*)malloc(sizeof(Queue));
    if (temp == NULL)
    {
        printf("Error! Malloc failed at queue creation");
        exit(4);
    }
    temp->ptrHead = temp->ptrTail = NULL;
    return temp;
}

//Method to sort a queue by arrival time , uses selection sort algorithm
void SortQueueByArrival(Queue* const queueToSort, AlgorithmToCall currentState)
{
    if (!QueueIsEmpty(queueToSort))
    {
        for (Procedure* firstIterator = queueToSort->ptrHead; firstIterator != queueToSort->ptrTail; firstIterator = firstIterator->nextProc)
        {
            for (Procedure* secondIterator = firstIterator->nextProc; secondIterator != NULL; secondIterator = secondIterator->nextProc)
            {
                if (firstIterator->arrivalTime > secondIterator->arrivalTime)
                    SwapContents(firstIterator, secondIterator); //If the first iterator's arrival time is higher than the second's we call SwapContents with first and second iterator as parameters
                else if (firstIterator->arrivalTime == secondIterator->arrivalTime) //Else we check if both iterator's arrival time is the same
                {
                    if (currentState == sjf) //If yes , we check the current state we are in (sjf or priority)
                        if (firstIterator->serviceTime > secondIterator->serviceTime) //For sjf we check if first iterator's service time is higher than second's. If yes we call swap contents
                            SwapContents(firstIterator, secondIterator);
                        else
                            if (firstIterator->priority < secondIterator->priority) //For priority we check if first iterator's priority is lower than second's. If yes we call swap contents
                                SwapContents(firstIterator, secondIterator);
                }
            }
        }
    }
    else
    {
        printf("Error! Queue is empty! \n");
        exit(6);
    }
}

//Adds a Procedure item in a queue , gets the item and the queue that the item should be added as a parameter
void AddToQueue(Queue* const queueToAdd, Procedure* const item)
{
    if (QueueIsEmpty(queueToAdd)) //First we check if the queue is empty and add the item to the front(head)
    {
        queueToAdd->ptrHead = queueToAdd->ptrTail = item;
        item->nextProc = NULL;
    }
    else //Else we add the item to the back(tail) of the queue and initialise it's nextProc pointer to NULL
    {
        queueToAdd->ptrTail->nextProc = item;
        queueToAdd->ptrTail = item;
        item->nextProc = NULL;
    }
}

//Method to free allocated memory after simulation is complete
void FreeQueue(Queue* const queueToFree)
{
    //Create 2 pointers , one to iterate through the elements and one to delete an element , iterator is always deleter->nextitem
    Procedure* iterator = queueToFree->ptrHead;
    Procedure* deleter;
    while (iterator != NULL)
    {
        deleter = iterator;
        iterator = iterator->nextProc;
        free(deleter);
    }
}

//Method to check if a queue is empty , takes as a parameter the queue we want to check and returns if the head is null
bool QueueIsEmpty(const Queue* const queueToCheck)
{
    return (queueToCheck->ptrHead == NULL);
}

//Method to read and store file's data into queue , takes the queue and the file to be read as parameters , returns how many procedures were added
int ReadFileData(Queue* const dataHolder, FILE* const fileToRead)
{
    int arrivalTime, serviceTime, priority; //Ints to hold the data to be stored
    int numOfProcs = 0; //Counter to hold how many procedures are added , used to save each procedure's id as well
    while (fscanf(fileToRead, "%d %d %d", &arrivalTime, &serviceTime, &priority) == 3) //First we check if fscan's return is 3(meaning we haven't reached a blank line)
    {
        //Then we dynamically allocate a procedure , store the input data and initialise the remaining values(ones we don't get through the text file)
        Procedure* temp = CreateProc();
        temp->arrivalTime = arrivalTime;
        temp->serviceTime = serviceTime;
        temp->priority = priority;
        temp->procID = numOfProcs;
        temp->waitTime = 0;
        temp->startTime = 0;
        temp->remainingTime = temp->serviceTime;
        //Then we add the created procedure in the entry queue and increment the number of procedures
        AddToQueue(dataHolder, temp);
        numOfProcs++;
    }
    return numOfProcs; //After we are done , we return the number of procedures added
}

//Method to print the data after the simulation is complete , gets the outputQueue and the total number of procedures as parameters
void PrintValues(Queue* const outputQueue, int total)
{
    int serviceTimeSum = 0;
    int totalWaitTime = 0;
    int totalTurnaroundTime = 0;
    float averageServiceTime, averageWaitTime, averageTurnaroundTime;
    printf("ProcID\tArrivalTime\tServiceTime\tPriority\tWaitTime\tStartTime\tFinishTime\tTurnaroundTime\n");
    for (Procedure* iterator = outputQueue->ptrHead; iterator != NULL; iterator = iterator->nextProc)
    {
        serviceTimeSum += iterator->serviceTime;
        totalWaitTime += iterator->waitTime;
        totalTurnaroundTime += iterator->turnAroundTime;
        printf("%d    \t%d    \t        %d    \t        %d    \t        %d         \t%d    \t        %d    \t        %d\n", iterator->procID, iterator->arrivalTime, iterator->serviceTime,
            iterator->priority, iterator->waitTime, iterator->startTime, iterator->finishTime, iterator->turnAroundTime);
    }
    averageServiceTime = (float)serviceTimeSum / total;
    averageWaitTime = (float)totalWaitTime / total;
    averageTurnaroundTime = (float)totalTurnaroundTime / total;
    printf("\nAverage Service Time: %f \n", averageServiceTime);
    printf("Average Wait Time: %f \n", averageWaitTime);
    printf("Average Turnaround Time: %f \n", averageTurnaroundTime);
}

//Method to update the entry queue , takes the entry and simulations queue's as parameters as well as the current simulation time
void UpdateEntryQueue(Queue* const inputQueue, Queue* const simulationQueue, int currentTime)
{
    if (!QueueIsEmpty(inputQueue))
    {
        if (inputQueue->ptrHead->arrivalTime == currentTime) //If the head's arrival time is equal to the current simulation time
        {
            //Create a temp procedure and point it to the head procedure
            Procedure* toRemove = inputQueue->ptrHead;
            //Change the head to point to the next procedure in the queue
            inputQueue->ptrHead = inputQueue->ptrHead->nextProc;
            //Add the item to the back of the simulation queue
            AddToQueue(simulationQueue, toRemove);
        }
    }
}


//Method to update the simulation on each clock tick , takes the sim queue , output queue , current simulation time , bool to check if the sim is preemptive and a pointer-to-function
//(for priority or sjf procedure swaping)
void Tick(Queue* const simulationQueue, Queue* const outputQueue, int currentTime, bool bIsPreemptive, void(*functionToCall)(Queue* const))
{
    if (!QueueIsEmpty(simulationQueue))
    {
        Procedure* head = simulationQueue->ptrHead; //First we decrement the current running procedure's remaining time
        head->remainingTime--;
        if (head->remainingTime == 0) //Then we check if it has reached 0 (procedure has finished runing)
        {
            //If yes , we move the head of the queue to the next procedure and add the finished procedure to the output queue
            head->finishTime = currentTime;
            head->turnAroundTime = head->finishTime - head->arrivalTime;
            simulationQueue->ptrHead = simulationQueue->ptrHead->nextProc;
            AddToQueue(outputQueue, head);
            //Then we call the function to find the next procedure that should run(might be sjf sorting or priority sorting)
            if (!QueueIsEmpty(simulationQueue))
            {
                (*functionToCall)(simulationQueue);
                //Then, if the queue is not empty we check if the procedure to-be-ran has ran again before(remaining time == service time)
                if (simulationQueue->ptrHead->remainingTime == simulationQueue->ptrHead->serviceTime)
                    simulationQueue->ptrHead->startTime = currentTime; //If not we initialise it's start time to the current time
            }
            else //If the queue is empty (simulation has finished) we return
                return;
        }
        else //If the procedure hasn't finished runing
            if (bIsPreemptive) //We check if we are on preemptive mode
            {
                (*functionToCall)(simulationQueue); //If yes , we check if a procedure should be ran instead of this one with sjf or priority sorting(same as before)
                if (simulationQueue->ptrHead->remainingTime == simulationQueue->ptrHead->serviceTime)
                    simulationQueue->ptrHead->startTime = currentTime;
            }
        //Finally , we increment each procedure's(except the head's) remaining time by 1
        for (Procedure* iterator = simulationQueue->ptrHead->nextProc; iterator != NULL; iterator = iterator->nextProc)
            iterator->waitTime++;
    }
}

//Method to find the next procedure that should be ran with Shortest Job First sorting , takes the simulation queue as a parameter
void FindNextSJF(Queue* const simulationQueue)
{
    //Create a temp procedure to find the minimum remaining time
    Procedure* min = simulationQueue->ptrHead;
    for (Procedure* iterator = min->nextProc; iterator != NULL; iterator = iterator->nextProc)
        if (min->remainingTime > iterator->remainingTime)
            min = iterator;
    if (min == simulationQueue->ptrHead) //If the minimum remaining time is that of the head's , we return
        return;
    else //Else we call the swap contents Method 
        SwapContents(min, simulationQueue->ptrHead);
}

//Method to find the next procedure that should be ran with priority sorting , takes the simulation queue as a parameter
void FindNextPriority(Queue* const simulationQueue)
{
    //Create a temp procedure to find the highest priority 
    Procedure* high = simulationQueue->ptrHead;
    for (Procedure* iterator = high->nextProc; iterator != NULL; iterator = iterator->nextProc)
        if (high->priority < iterator->priority)
            high = iterator;
    if (high == simulationQueue->ptrHead) //If the priority is that of the head's , we return
        return;
    else
        SwapContents(high, simulationQueue->ptrHead); //Else we call the swap contents Method 
\$\endgroup\$
  • 1
    \$\begingroup\$ It looks like there's a missing closing bracket on the last function. You might want to add it in, lest someone complain that this code doesn't compile. \$\endgroup\$ – user1118321 Nov 8 '17 at 4:57
  • 1
    \$\begingroup\$ the posted code does not compile, Beyond what @user1118321 commented upon, this statement: #include <stdlio.h> does not compile because there is no header file named: stdlio.h Perhaps you meant: #include <stdio.h> \$\endgroup\$ – user3629249 Nov 10 '17 at 16:50
  • \$\begingroup\$ Yep , thanks a lot , made a typo when writing the post here . Sorry for the inconvenience ! \$\endgroup\$ – Erotokritos Vallianatos Nov 11 '17 at 0:02
4
\$\begingroup\$

Τικανεσ! (That's all the Greek I know!) For a first program, this is good! You've already done the main things that we tell beginners, namely, improve your naming, use the proper data types, and write more readable code. Here are some things I would do differently:

Comments

It's good to have comments, but I think you've added more than you need. Your function names are quite good, so you don't need to add a comment to tell what the function does since your code is self-documenting. Likewise with the comments in the code. In general, add comments when the code has to do something that's not obvious. Strive to write the code as clearly as possible, and when it's not possible, then add comments explaining it.

Simplify

I would simplify the program argument handling by converting the arguments to either all lowercase or all uppercase using the tolower() or toupper() function. Then you only need a single comparison.

In SortQueueByArrival(), you don't need to check if the Queue is empty. Your condition to terminate the for loop will handle the empty queue case.

Related to this, you've made it so that the Procedure structure is also the node type in the queue. If you had a separate node type, you could simplify the code in some places (though it's a trade-off in other places). For example, you could define a QueueNode like this:

typedef struct QueueNode
{
    Procedure* proc;
    struct QueueNode* next;
} QueueNode;

Then your Queue could be defined like this:

typedef struct Queue
{
    QueueNode* ptrHead;
    QueueNode* ptrTail;
} Queue;

What this would allow you to do is avoid ever having to swap the contents of 2 Procedures. Instead, you could simply swap the pointers in the QueueNodes that point to them.

On the other hand, it would make allocation, and deletion a little bit more complicated as you'd have to allocate both the node and the Procedure.

Use More Functions

You've done a fairly good job of creating functions for most of the things that need functions and for separating out the functionality. It's very readable. But I think that you could go a little bit further and make the argument handling in main() into its own function, for example. I would also put the code that does the actual processing in its own functions. For example the stuff in main() in the 2 branches of the if (whichOne == sjf) could go into 2 functions to make it a little cleaner.

Naming

OK, one small thing about naming. Usually a scheduler is scheduling "Processes" not "Procedures". I think of procedures as being functions in an application, whereas the running application itself is a process.

Infinite Loops

In general, I avoid writing infinite loops, at least in cases where there's a very clear stopping criteria. In main() you have 2 of them. You write:

while (true)
{
    if (QueueIsEmpty(entryQueue) && QueueIsEmpty(simulationQueue)) //Loop until both entry and simulation queues are empty
        break;

This is a verbose way of saying:

while (!QueueIsEmpty(entryQueue) || !QueueIsEmpty(simulationQueue))
{
    //... rest of the body

It's easier to read and clearer when the exit condition for the loop is part of the loop construct rather than a sneaky exit in the middle of the loop.

Don't exit() on Failure!

Unless you've been told to do so for this assignment, you shouldn't just call exit() whenever something unexpected happens. It's important to write code that returns errors, and code that handles errors. This code contains a lot of things that could easily be turned into a handy library for re-use elsewhere. But nobody's going to be able to use it if their application can suddenly exit at the first sign of problems. What about unsaved data a user might have in memory? If you just exit, that gets deleted! So I'd err on the side of returning error codes or NULL pointers where appropriate, and having the calling code handle it appropriately. For this simulation it's not a huge problem to quit, but as your code does more complex things, it quickly will become a problem.

Potential Errors

It looks like there may be an error in your SortQueueByArrival() function. Deep inside the inner for loop, you have this code:

                if (currentState == sjf) //If yes , we check the current state we are in (sjf or priority)
                    if (firstIterator->serviceTime > secondIterator->serviceTime) //For sjf we check if first iterator's service time is higher than second's. If yes we call swap contents
                        SwapContents(firstIterator, secondIterator);
                    else
                        if (firstIterator->priority < secondIterator->priority) //For priority we check if first iterator's priority is lower than second's. If yes we call swap contents
                            SwapContents(firstIterator, secondIterator);

According to the comments, this should do one thing if currentState is sjf and another if it's not. But that's not what the code actually does. If currentState is priority, nothing will ever be swapped. That else if clause is going with the inner if, not the outer one. This is why you should always use braces in your if statements, even if they're only a single line long. You should write it like this:

                if (currentState == sjf) //If yes , we check the current state we are in (sjf or priority)
                {
                    if (firstIterator->serviceTime > secondIterator->serviceTime) //For sjf we check if first iterator's service time is higher than second's. If yes we call swap contents
                    {
                        SwapContents(firstIterator, secondIterator);
                    }
                 }
                 else 
                 {
                     if (firstIterator->priority < secondIterator->priority) //For priority we check if first iterator's priority is lower than second's. If yes we call swap contents
                     {
                         SwapContents(firstIterator, secondIterator);
                     }
                 }
\$\endgroup\$
  • \$\begingroup\$ Hello and thanks for your reply! For the last part (potential errors) I had already noticed and fixed it. Apart from that though , your tips are really helpful and will keep them in mind for my next project/assignment. Especially the part on how to handle the struct/queue nodes/queue is really clever and saves a lot of code. Thanks again! \$\endgroup\$ – Erotokritos Vallianatos Nov 8 '17 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.