Thread: Almost finished with Round Robin algorithm

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    16

    Infinite loop in Round Robin process scheduling 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();        
    };
    Last edited by Shinobi-wan; 12-19-2004 at 02:24 PM.

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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?

  3. #3
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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.
    Last edited by master5001; 12-19-2004 at 03:21 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. About aes
    By gumit in forum C Programming
    Replies: 13
    Last Post: 10-24-2006, 03:42 PM
  2. Round Robin Scheduling using c.
    By eclipt in forum C Programming
    Replies: 8
    Last Post: 12-28-2005, 04:58 PM
  3. round robin algorithm!
    By visham in forum C Programming
    Replies: 9
    Last Post: 10-13-2005, 03:14 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM