Almost finished with Round Robin algorithm

Hey again.

Well, I got all the kinks out of it from before, but now I'm at a block again. My Round Robin algorithm seems to be stuck in an infinite loop. :(

I can't figure out where it's looping forever, and I'm not so good at debugging on Linux. Can anyone help me out?

What it's supposed to do it take a list of processes (sorted by time arrived, and also containing the required burst time), process them, and output the average wait time and average turnaround time. I still have to implement checking to see if a process has arrived at a time or not, but I will leave that until this is working.

The data file is located here.

Edit: I almost forgot, this program takes two numerical arguments for the time quanta and context switch time, eg. rr 5 5.

Here is what I have so far:

Code:

---

#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

/* Process Data Structure */
struct process {
    int arrive;            /* Process Arrival Time */
    int burst;              /* CPU Burst Time */
    float working;            /* Working time*/
    float waiting;            /* Waiting time*/
    struct process *next;
};

struct process *init_process (int pid, int burst);
void rr (process *proc, int burst, float cswitch);

int  main(int argc, char* argv[]) {

        process *plist,*ptmp;

        int init = 0;
        int quanta = static_cast<int>(std::strtol(argv[1], NULL, 0));
        int context_switch = static_cast<int>(std::strtol(argv[2], NULL, 0));
        float cswitch = context_switch/1000;

        ifstream input;
        input.open("rrdata.txt");
        if (input.fail()) {
        cerr << "unable to open file rrdata.txt for reading" << endl;
        exit(1);
        }

        //Initialize  the list of processes
        int arrive,burst;
        input>>arrive>>burst;
        plist = init_process(arrive,burst);
        init++;
        input>>arrive>>burst;
        plist -> next = init_process(arrive,burst);ptmp = plist->next;
        init++;
        for (int i = 0; i < 98; i++) {
                input>>arrive>>burst;
                ptmp -> next = init_process(arrive,burst);ptmp = ptmp->next;
                init++;
        }
        input>>arrive>>burst;
        ptmp -> next = init_process(arrive,burst);         
        init++;

  rr(plist,quanta,cswitch);

  input.close();
        return 0;
}

struct process *init_process (int arrive, int burst) {
        struct process *proc;
        proc = new process;
    if (proc == NULL) {
        printf("Fatal error: memory allocation failure.\nTerminating.\n");
        exit(1);
    };
    proc->arrive = arrive;
    proc->burst = burst;
    proc->working = 0;
    proc->waiting = 0;
    proc->next = NULL;
    return(proc);
};

void rr (process *proc, int quanta, float cswitch){
        float burst = 0;
        float wait = 0;
        float switches = 0;
        float time = 0;
        process *head = proc; /*Used to keep a pointer to the top node.*/
        process *trail = proc; /*Used to keep a pointer to the previous node in the event that a node must be removed.*/
        int processesleft = 100;
  int i = 0;

  ofstream output;
        output.open("output.txt");
        if (output.fail()) {
        cerr << "unable to open file output.txt" << endl;
        exit(1);
        }
 
  while(processesleft != 0){

        /*If there is more then quanta burst time left and there is another process in the queue, do this:*/
    if(proc->burst > quanta && proc->next != NULL)
    {
      proc->working += quanta;
      proc->waiting = time - proc->waiting;
      proc->burst -= quanta;
      trail = proc;
      proc = proc->next;
      time += quanta;
      switches++;
      output<<"time removed, new process"<<endl;
    } 

  /*If there is less then or equal to the quanta burst time left and there is another process in the queue, do this:*/
    else if(proc->burst <= quanta && proc->next != NULL)
    {
      proc->working += proc->burst;
      proc->waiting += time-proc->waiting;
      proc->burst = 0;
      time += proc->burst;
      burst = proc->working;
      wait = proc->waiting;
      proc = proc->next;
      trail->next = proc;
      switches++;
      processesleft--;
      output<<"time reomved, process removed, new process"<<endl;
    }

  /*If there is more then quanta burst time left and there is not another process in the queue, do this:*/
    else if(proc->burst > quanta && proc->next != NULL)
    {
      proc->working += quanta;
      proc->waiting = time - proc->waiting;
      proc->burst -= quanta;
      time += quanta;
      output<<"time removed, no new process"<<endl;
    }

  /*If there is less then or equal to the quanta burst time left and there is not another process in the queue, do this:*/
          else if(proc->burst <= quanta && proc->next != NULL)
    {
      proc->working += proc->burst;
      proc->waiting += time-proc->waiting;
      time += proc->burst;
      proc->burst = 0;
      burst = proc->working;
      wait = proc->waiting;
      processesleft--;
      output<<"time removed,process removed"<<endl;
    }
  }

  switches *= cswitch;
  burst += switches;

  output<<wait/100<<" "<<burst/100;
  output.close();       
};

---

Your code is not working for me at all. I'll fix it up and repost, but until then I am already noticing your intialization loop is kinda fishy. You should let the end of the file dictate when the loop stops, not a hard-coded number of lines. also:

Code:

---

        int arrive,burst;
        input>>arrive>>burst;
        plist = init_process(arrive,burst);
        init++;
        input>>arrive>>burst;
        plist -> next = init_process(arrive,burst);ptmp = plist->next;
        init++;

---

why do you do this?

Ok I'm didn't go too deep into this since it seemed evident to me that your program was just hitting a seg fault so fast you probably just didn't even know what was going on. That said, I added some fixes to your code that should help you get back on track. But by no means does this mean I finished your program for you.

Code:

---

#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

/* Process Data Structure */
struct process {
    int arrive;            /* Process Arrival Time */
    int burst;              /* CPU Burst Time */
    float working;            /* Working time*/
    float waiting;            /* Waiting time*/
    struct process *next;
};

struct process *init_process (int pid, int burst);
void rr (process *proc, int burst, float cswitch, int processesleft);

int  main(int argc, char* argv[]) {

  process *plist,*ptmp;

  /* This is a biggy man...when I first ran your code it crashed due to insufficient parameters */
  if(argc < 3) {
    cerr << "Invalid number of parameters." << endl;
    return EXIT_FAILURE;
  }

  int init = 0;
  int quanta = static_cast<int>(std::strtol(argv[1], NULL, 0));
  int context_switch = static_cast<int>(std::strtol(argv[2], NULL, 0));
        float cswitch = context_switch/1000;

  ifstream input;
  input.open("rrdata.txt");
  if (input.fail()) {
    cerr << "unable to open file rrdata.txt for reading" << endl;
    return EXIT_FAILURE;
  }

  //Initialize  the list of processes
  int arrive,burst;

  input >> arrive >> burst;

  if((plist = init_process(arrive, burst))) {
    ptmp = plist;
    init++;

    while(!input.eof() && ptmp) {
      input >> arrive >> burst;
      ptmp->next = init_process(arrive,burst);
      ptmp = ptmp->next;
      init++;
    }
  }

  rr(plist, quanta, cswitch, init);

  input.close();
  return EXIT_SUCCESS;
}

struct process *init_process (int arrive, int burst) {
  struct process *proc;
  proc = new process;
    if (proc == NULL) {
        printf("Fatal error: memory allocation failure.\nTerminating.\n");
        exit(1);
    };
    proc->arrive = arrive;
    proc->burst = burst;
    proc->working = 0;
    proc->waiting = 0;
    proc->next = NULL;
    return(proc);
};

void rr (process *proc, int quanta, float cswitch, int processesleft){
        float burst = 0;
        float wait = 0;
        float switches = 0;
        float time = 0;
  process *head = proc; /*Used to keep a pointer to the top node.*/
  process *trail = proc; /*Used to keep a pointer to the previous node in the event that a node must be removed.*/
  int i = 0;

  ofstream output;
  output.open("output.txt");
  if (output.fail()) {
    cerr << "unable to open file output.txt" << endl;
    exit(1);
  }
 
  while(processesleft != 0){

    /*If there is more then quanta burst time left and there is another process in the queue, do this:*/

    if(proc->burst > quanta && proc->next != NULL)
    {
      proc->working += quanta;
      proc->waiting = time - proc->waiting;
      proc->burst -= quanta;
      trail = proc;
      proc = proc->next;
      time += quanta;
      switches++;
      output<<"c1: time removed, new process"<<endl;
    }


  /*If there is less then or equal to the quanta burst time left and there is another process in the queue, do this:*/
    else if(proc->burst <= quanta && proc->next != NULL)
    {
      proc->working += proc->burst;
      proc->waiting += time-proc->waiting;
      proc->burst = 0;
      time += proc->burst;
      burst = proc->working;
      wait = proc->waiting;
      proc = proc->next;
      trail->next = proc;
      switches++;
      processesleft--;
      output<<"c2: time reomved, process removed, new process"<<endl;
    }

  /*If there is more then quanta burst time left and there is not another process in the queue, do this:*/
    else if(proc->burst > quanta && proc->next != NULL)
    {
      proc->working += quanta;
      proc->waiting = time - proc->waiting;
      proc->burst -= quanta;
      time += quanta;
      output<<"c3: time removed, no new process"<<endl;
    }

  /*If there is less then or equal to the quanta burst time left and there is not another process in the queue, do this:*/
    else if(proc->burst <= quanta && proc->next != NULL)
    {
      proc->working += proc->burst;
      proc->waiting += time-proc->waiting;
      time += proc->burst;
      proc->burst = 0;
      burst = proc->working;
      wait = proc->waiting;
      processesleft--;
      output<<"c4: time removed,process removed"<<endl;
    }

    //output << processesleft << endl;
  }

  switches *= cswitch;
  burst += switches;

  output<<wait/100<<" "<<burst/100;
  output.close();       
};

---

[edit] My IDE was being naughty about tabs. Had to fix my code. I also noticed that the program was still running (suggestive of your infinite loop, I'll take a look at that and repost the code. [/edit]

Ok I highlighted in red where its getting stuck. I also took the liberty of adding a parameter to the rr function. My way has no hard-coded anything, it merely reads from a properly formated file, and processes however many entries were found in that file.