I FOUND THE BUG [C++]

[BuckGup]

So I can't seem to find what's wrong with my program and have spent the last 3 days trying to figure it out. I would normally simply just ask for help but this project is somewhat large and complex so it may be slightly time consuming, hence the monetary reward. I can pay you in any medium you like.

 

The gist of the program is it's a MFQS or Multilevel Feedback Queue Scheduler. It can take a max of 5 queues inclusive of the last being FCFS or First Come First Serve. The rest use a round robin style and ageing is only implemented in the bottom FCFS queue. Aging is when you have sat longer than your time quantum and you get promoted to the next queue above. You can only be promoted out of the bottom queue and the rest demote after your job runs past the time qutnum. Each queue lower is 2 times the time quantum as the queue above it and attached is two test files as it only accepts a tab delimited file for it's testing. The 1K file has 10 entries and the 1M has 1 million. I suggest testing small first and then moving to the 1M. Thank you all so much and have fun!

 

//MFQS Made by Sam Strecker 1/24/21

#include<stdio.h>
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

class Job {
public:
    int PID;
    int burst;
    int arrival;
    Job *nextJob;

    Job *getNextJob() const;

    void setNextJob(Job *nextJob);

    int age;
    int startTime;
    int workRemaining;

    int getAge() const;

    void setAge(int age);

    int getStartTime() const;

    void setStartTime(int startTime);

    int getWorkRemaining() const;

    void setWorkRemaining(int workRemaining);

    void setPid(int pid);

    void setBurst(int burst);

    void setArrival(int arrival);

    void setPriority(int priority);

    int priority;

    int getPid() const {
        return PID;
    }

    int getBurst() const {
        return burst;
    }

    int getArrival() const {
        return arrival;
    }

    int getPriority() const {
        return priority;
    }

    Job() {
        nextJob = NULL;
        age = 0;
    };

    Job(string line) {
        nextJob = NULL;
        char *tok;
        char char_array[99];
        setStartTime(-1);
        setWorkRemaining(-1);
        setAge(0);

        strcpy(char_array, line.c_str());

        tok = strtok(char_array, "\t");
        setPid(stoi(tok));

        tok = strtok(NULL, "\t");
        setBurst(stoi(tok));

        tok = strtok(NULL, "\t");
        setArrival(stoi(tok));

        tok = strtok(NULL, "\t");
        setPriority(stoi(tok));
    }

    void printJob();
};

void Job::printJob() {
    cout << "This is the PID";
    cout << this->PID;
    cout << endl;
}

void Job::setPid(int pid) {
    PID = pid;
}

void Job::setBurst(int burst) {
    Job::burst = burst;
}

void Job::setArrival(int arrival) {
    Job::arrival = arrival;
}

void Job::setPriority(int priority) {
    Job::priority = priority;
}

int Job::getAge() const {
    return age;
}

void Job::setAge(int age) {
    Job::age = age;
}

int Job::getStartTime() const {
    return startTime;
}

void Job::setStartTime(int startTime) {
    Job::startTime = startTime;
}

int Job::getWorkRemaining() const {
    return workRemaining;
}

void Job::setWorkRemaining(int workRemaining) {
    Job::workRemaining = workRemaining;
}

Job *Job::getNextJob() const {
    return nextJob;
}

void Job::setNextJob(Job *nextJob) {
    Job::nextJob = nextJob;
};

string getJob(ifstream &, int);

Job *jobFill(string);

Job *dispatcher(Job *, Job *);

int checkActiveJobs(Job *, int);

void demote(Job *&, Job *&, int);

void deleteJob(Job *&, int, int &, int &, int &);

void promoteJob(Job *&, Job *&, int, int);

int main() {
    char *tok;
    Job *currentJob = nullptr;
    Job *topJob = nullptr;
    Job *myJob = nullptr;
    Job *Q1 = nullptr;
    Job *Q2 = nullptr;
    Job *Q3 = nullptr;
    Job *Q4 = nullptr;
    Job *QF = nullptr;
    char fileDirectory[99];
    int numQ = 0;
    int timeQuantum = 0;
    //int ageInterval = 0;
    char tempArray[99];
    int clockCycle = 0;
    int totalWaitTime = 0;
    int totalTurnaroundTime = 0;
    int totalProcesses = 0;
    int workToDo = 0;
    int quantumClock = 0;
    int myAge = 0;

    printf("\nEnter the test file directory:\t");
    scanf("%s", fileDirectory);

    printf("Enter the number of queues:\t");
    scanf("%d", &numQ);

    printf("Enter time quantum for top queue:\t");
    scanf("%d", &timeQuantum);

    printf("Enter ageing interval:\t");
    scanf("%d", &myAge);

    //printf("Enter ageing interval:\t");
    // scanf("%d", &TEST);


    sprintf(tempArray, "sort -g -k 3,3 %s > 1M.sorted", fileDirectory);

    system(tempArray); // execute the UNIX command "sort"

    string line;
    ifstream myfile("1M.sorted");

    //Check top newJob.next pointer = current
    //Previous job = new job if current job is greater than previous
    //If current is smaller than newJob and next job is NULL then add on end


    quantumClock = timeQuantum;
    while (true) {

        string tempJob;

        tempJob = getJob(myfile, clockCycle);
        //Read in scheduled jobs from file
        while (!tempJob.empty()) {
            myJob = new Job(tempJob);
            Q1 = dispatcher(Q1, myJob);
            if (!myfile.eof()) {
                tempJob = getJob(myfile, clockCycle);
            }
        }

        if (QF != NULL || QF != nullptr) {
            //Call the function to check if the age is past the interval and traverse across all elements in FCFS
            if (numQ == 2) {
              //  promoteJob(QF, Q1, clockCycle, myAge);
            } else if (numQ == 3) {
             //   promoteJob(QF, Q2, clockCycle, myAge);

            } else if (numQ == 4) {
            //    promoteJob(QF, Q3, clockCycle, myAge);

            } else if (numQ == 5) {
              //  promoteJob(QF, Q4, clockCycle, myAge);

            } else {
                cerr << "Queue out of bounds" << endl;
            }


        }

        //Check status of jobs
        if (Q1 != nullptr || Q1 != NULL) {
            workToDo = checkActiveJobs(Q1, clockCycle);
            quantumClock--;

            if (workToDo == 0) {
                deleteJob(Q1, clockCycle, totalProcesses, totalWaitTime, totalTurnaroundTime);
                quantumClock = timeQuantum;

            } else {
                if (quantumClock == 0) {
                    if (numQ == 2) {
                        demote(Q1, QF, clockCycle);
                    } else {
                        demote(Q1, Q2, clockCycle);
                    }
                    //demote2(Q1, Q1, Q2, Q3, Q4, QF, clockCycle, numQ);
                    quantumClock = timeQuantum;
                }
            }
        } else if (Q2 != nullptr || Q2 != NULL) {
            workToDo = checkActiveJobs(Q2, clockCycle);
            quantumClock--;
            if (workToDo == 0) {
                deleteJob(Q2, clockCycle, totalProcesses, totalWaitTime, totalTurnaroundTime);
                quantumClock = timeQuantum * 2;

            } else {
                if (quantumClock == 0) {
                    if (numQ == 3) {
                        demote(Q2, QF, clockCycle);
                    } else {
                        demote(Q2, Q3, clockCycle);
                    }
                    // demote(Q1, Q2, clockCycle);
                    // demote2(Q2, Q1, Q2, Q3, Q4, QF, clockCycle, numQ);
                    quantumClock = timeQuantum;
                }
            }

        } else if (Q3 != nullptr || Q3 != NULL) {
            workToDo = checkActiveJobs(Q3, clockCycle);
            quantumClock--;
            if (workToDo == 0) {
                deleteJob(Q3, clockCycle, totalProcesses, totalWaitTime, totalTurnaroundTime);
                quantumClock = timeQuantum * 4;

            } else {
                if (quantumClock == 0) {
                    if (numQ == 3) {
                        demote(Q3, QF, clockCycle);
                    } else {
                        demote(Q3, Q4, clockCycle);
                    }
                    quantumClock = timeQuantum;
                }
            }

        } else if (Q4 != nullptr || Q4 != NULL) {
            workToDo = checkActiveJobs(Q4, clockCycle);
            quantumClock--;
            if (workToDo == 0) {
                deleteJob(Q4, clockCycle, totalProcesses, totalWaitTime, totalTurnaroundTime);
                quantumClock = timeQuantum * 8;

            } else {
                if (quantumClock == 0) {
                    if (numQ == 4) {
                        demote(Q4, QF, clockCycle);
                    }
                    quantumClock = timeQuantum;
                }
            }

        } else if (QF != nullptr || QF != NULL) {
            workToDo = checkActiveJobs(QF, clockCycle);
            quantumClock = timeQuantum;
            if (workToDo == 0) {
                deleteJob(QF, clockCycle, totalProcesses, totalWaitTime, totalTurnaroundTime);

            }

        } else {

            cout << "Ave. wait time= " << totalWaitTime / totalProcesses << " Ave. turnaround time = "
                 << totalTurnaroundTime
                 << " Total processes scheduled = " << totalProcesses << endl;

            myfile.close();
            remove("1M.sorted");
            exit(0);
        }
        clockCycle++;

    }


}

string getJob(ifstream &myfile, int currentTime) {
    char char_array[99];
    char *PID;
    char *Burst;
    char *Arrival;
    string line;
    streampos oldpos;

    if (myfile.is_open()) {

        do {
            oldpos = myfile.tellg();   // get back to the position
            getline(myfile, line);
            if (myfile.eof() || line.empty()) {
                return "";
            }
            strcpy(char_array, line.c_str());
            if (strchr(char_array, '-') != NULL || strchr(char_array, 'i')) {
                continue;
            }
            PID = strtok(char_array, "\t");
            Burst = strtok(NULL, "\t");
            Arrival = strtok(NULL, "\t");
            if (stoi(Arrival) == currentTime) {
                return line;
            } else {
                myfile.seekg(oldpos);
                return "";
            }
        } while (!myfile.eof() && !line.empty());
    }
    //return "";
}

Job *dispatcher(Job *myQ, Job *myJob) {
    Job *tempPointer = myQ;

    //Check for if Que is empty
    if (myQ == NULL) {
        myQ = myJob;
        myQ->nextJob = myQ;
        cout << "Process " << myJob->getPid() << ":" << " arrives @ " << myJob->getArrival() << endl;

    } else {
        while (tempPointer->nextJob != myQ) {
            tempPointer = tempPointer->nextJob;
        }
        tempPointer->nextJob = myJob;
        myJob->nextJob = myQ;
        cout << "Process " << myJob->getPid() << ":" << " arrives @ " << myJob->getArrival() << endl;
    }
    return myQ;
}

int checkActiveJobs(Job *Qa, int clockCycle) {

    if (Qa == nullptr || Qa == NULL) {
        return 0;
    } else {
        if (Qa->getStartTime() == -1) {
            Qa->setWorkRemaining(Qa->getBurst());
            //start job
            Qa->setStartTime(clockCycle);
            return Qa->getBurst();
        } else {
            Qa->setWorkRemaining(Qa->getWorkRemaining() - 1);
            return Qa->getWorkRemaining();
        }
    }

    return 0;
}

void demote(Job *&Qa, Job *&Qb, int clockCycle) {
    Job *tempPtrQa = nullptr;
    tempPtrQa = Qa;
    Job *tempPtrQb = nullptr;
    tempPtrQb = Qb;

    while (tempPtrQa->nextJob != Qa) {
        tempPtrQa = tempPtrQa->nextJob;
    }
    if (Qb == nullptr || Qb == NULL) {
        Qb = Qa;
        Qb->nextJob = Qb;

        if (tempPtrQa->nextJob == Qa) {
            Qa = NULL;
        } else {
            Qa = Qa->nextJob;
        }

    } else {
        //if last element in Q1
        while (tempPtrQb->nextJob != Qb) {
            tempPtrQb = tempPtrQb->nextJob;
        }
        tempPtrQa->nextJob = Qa->nextJob;
        tempPtrQb->nextJob = Qa;
        Qa->nextJob = Qb;

        if (tempPtrQa->nextJob == Qa) {
            Qa = nullptr;

        } else {
            Qa = tempPtrQa->nextJob;
        }
        Qb->nextJob = Qb->nextJob;

    }
    cout << tempPtrQa->getPid() << " switched @ " << clockCycle << endl;

}

void deleteJob(Job *&Qa, int clockCycle, int &totalProcess, int &totalWaitTime, int &totalTurnaroundTime) {
    Job *tempPtr = nullptr;
    tempPtr = Qa;
    while (tempPtr->nextJob != Qa) {
        tempPtr = tempPtr->nextJob;
    }
    totalTurnaroundTime += (clockCycle - Qa->getStartTime());
    totalWaitTime += (Qa->getStartTime() - Qa->getArrival());
    totalProcess++;
    cout << Qa->getPid() << " finished @ " << clockCycle << endl;

    //checks if last element and delete itself
    if (Qa->nextJob == Qa) {
        Qa = nullptr;
    } else {
        tempPtr->nextJob = Qa->nextJob;
        Qa = Qa->nextJob;
    }

}


void promoteJob(Job *&QF, Job *&Qb, int clockCycle, int myAge) {

    Job *tempPtrQF = nullptr;
    tempPtrQF = QF;
    Job *tempPtrQb = nullptr;
    tempPtrQb = Qb;
    Job *tempPtrQprev = nullptr;
    tempPtrQprev = QF;

    //age increased by 1
    do {
        tempPtrQF->setAge(tempPtrQF->getAge() + 1);
        cout << tempPtrQF->getPid() << " age: " << tempPtrQF->getAge() << endl;
        tempPtrQF = tempPtrQF->nextJob;
    } while (tempPtrQF->nextJob != QF);

    if (Qb == NULL || Qb == nullptr) {
        tempPtrQF = QF;
        while (tempPtrQF->nextJob != QF) {
            if (tempPtrQF->getAge() > myAge) {
                tempPtrQprev = QF;

                while (tempPtrQprev->nextJob != tempPtrQF) {
                    tempPtrQprev = tempPtrQprev->nextJob;
                }
                Qb = tempPtrQF;
                tempPtrQprev->nextJob = tempPtrQF->nextJob;
                cout << tempPtrQF->getPid() << " promoted1 @ " << clockCycle << endl;
            }
            tempPtrQF = tempPtrQF->nextJob;
        }
    } else {
        while (tempPtrQb->nextJob != Qb) {
            tempPtrQb = tempPtrQb->nextJob;
            //end of Que above F
        }
        tempPtrQF = QF;

        while (tempPtrQF->nextJob != QF) {
            if (tempPtrQF->getAge() > myAge) {
                tempPtrQprev = QF;

                while (tempPtrQprev->nextJob != tempPtrQF) {
                    tempPtrQprev = tempPtrQprev->nextJob;
                }
                tempPtrQprev->nextJob = tempPtrQF->nextJob;
                tempPtrQb->nextJob = tempPtrQF;
                tempPtrQF->nextJob = Qb;
                tempPtrQF = tempPtrQprev->nextJob;
                cout << tempPtrQF->getPid() << " promoted2 @ " << clockCycle << endl;
            }
            else {
                tempPtrQF = tempPtrQF->nextJob;
            }
        }

    }
}

 

 

1M.txt 1S.txt

[FakeFBI]

holy moly ill try to help but its gonna be time consuming

[BuckGup]

10 minutes ago, ComputerBuilder said:

holy moly ill try to help but its gonna be time consuming

I might beat you to it lol.

[FakeFBI]

1 minute ago, BuckGup said:

I might beat you to it lol.

head start

[gabrielcarvfer]

Just looked at the code and have a few questions:

 

1. Why mix C and C++? Raw pointers within classes look very weird.

2. If you're using C++, why not make your life easier and use a priority queue?

3. If it is part of an assignment, why not use standard containers instead of pointers? Less error prone than dealing with raw pointers, no NULL/nullptr checks and code gets a bit simpler.

4. Why can you change the PID? It would break a ton of optimizations in a real OS.

[gabrielcarvfer]

Another question, is this correct? You're making the job become a queue and then pointing to it as the next job?

Why does that sound you will eventually call a destructor and have an invalid pointer? Not saying this is actually the case, but that it can happen.

Job *dispatcher(Job *myQ, Job *myJob) {
    Job *tempPointer = myQ;

    //Check for if Que is empty
    if (myQ == NULL) {
        myQ = myJob;
        myQ->nextJob = myQ;

 

[Unimportant]

@BuckGupWhat exactly is the problem. How exactly to replicate ?

 

Have you compiled with all warnings enabled. It spits out quite a few things. Quick look also shows there's a memory leak.

[Eigenvektor]

1 hour ago, gabrielcarvfer said:

4. Why can you change the PID? It would break a ton of optimizations in a real OS.

I agree that the PID should most likely not be mutable. In fact for concurrent systems it is often preferable if objects are immutable (i.e. no setters at all). To modify anything you need to create a new instance instead. This can avoid errors that can occur when objects are modified concurrently.

 

In the same vein, why are any of the fields public? It looks like you have getters/setters already, so why not make them private?

[BuckGup]

GOT IT