Click here to Skip to main content
15,887,746 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I'm working on a project in which I have to implement the Round Robin algorithm
in a c++ code using a circular linked list. I didn't really understand the codes I found on the internet so I decided to do it all myself. The algorithm is easy to understand, but I can't seem to realize what am I doing wrong in my code:
C++
#include<iostream>
#include<cstring>
using namespace std;
struct Nod{
	char nameProc[100];
	int arrivalT;
	int burstT;
	Nod *next;
};
Nod *head = NULL;
Nod *tail = NULL;

struct process
{
	char nameProcess[100];
	int arrival_Time;
	int burst_Time;
	int inList;
};

void deleteHead (Nod *&head)
{
      Nod* toDelete = head;
      head = head->next;
      delete toDelete;
      return;
}

void addArrivals(int time,Nod *&head,struct process p[],int n){
    int i;
    for(i=0;i<n;i++){
if((p[i].arrival_time<=time)&&(p[i].inlist==0)) {

="" if(head="=NULL)" if="" the="" list="" is="" empty
="" {
="" head="new" nod;="" memory="" for="" first="" one
="" strcpy(head-="">nameProc,p[i].nameProcess);
        head->arrivalT = p[i].arrival_Time;
        head->burstT = p[i].burst_Time;
        head->next = head; // It's the only one, so it's connected to itself
        tail =head; //  and it is tail also
        p[i].inList=1;
    }
    else // the list is not empty
    {   Nod * nod = new Nod; // memory for a new one
        strcpy(nod->nameProc,p[i].nameProcess);    // put the data in it
        nod->arrivalT = p[i].arrival_Time;
        nod->burstT = p[i].burst_Time;
        nod->next = head;  // link tail to the head
        tail->next = nod;    // the ex tail is linked to the new one
        tail = nod;          // the new one is tail now
         p[i].inList=1;

    }
      }
     }

return;
}

void exeProc(Nod *&head, int quantum,int &time)      //execution of the process

{   tail=head;         // the ex head becomes tail (who's been interrupted goes to the end)
    head=head->next;        // and the next one becomes head
        if(head->burstT>quantum)  {        //bt>quantum

   head->burstT=head->burstT-quantum;
    time=time+quantum;
    cout <<"At "<<time<<" ,"<<="" head-="">nameProc<< " has been executing for "<<quantum<<" secs.="" it="" has="" "<<head-="">burstT<<" more."<<endl;
 }
="" else="" {="" if(head-="">burstT>0) {time=time+head->burstT;          // bt <= quantum deci se incheie
                    cout<<"At "<<time<<" ,"<<head-="">nameProc<<" has been executing for "<<head->burstT<<" secs. The process "<<head->nameProc<<" is finished."<<endl;
 head-="">burstT=0;
                    deleteHead(head);
                  }}
}

int main()
{
    int quantum,n,i,time=0;   // time= current moment in time    n=number of proc      quantum= alocated execution time
    struct process p[100];


    cout<<"Give quantum: ";      //read quantum
    cin>>quantum;
while (quantum<1||quantum>10)
	{
		cout << "Quantum is not valid. Give a valid one: ";
		cin >>quantum;
	}


cout<<"Give number of proc:";
cin>>n;

for(i=0;i<n;i++)
 {="" cout<<"add="" name,="" at,="" bt="" "<<i+1<<":="" ";="" arrival="" time="" &="" burst="" time
="" cin="">>p[i].nameProcess;
		cin>>p[i].arrival_Time;
		cin>>p[i].burst_Time;
		p[i].inList=0;            //no process is in the list yet
	}


// I start working with the circular linked list
    Nod*head=NULL;
    Nod*tail=NULL;


do{
        addArrivals(time,head,p,n);
        exeProc(head,quantum,time);
}while(head!=NULL);  ///??? condition for circular list ???
cout<<"At "<<time<<", all="" they="" are="" finished."<<endl;
return="" 0;
}
If anyone could give me some suggestions I'd deeply appreciate it.

What I have tried:

I tried so many different ways of using those functions I've made but I can't seem to get it to give the right output order of the processes. For the input:
name arrival burstTime with quantum=3
P1 0 5
P2 1 3
P3 3 6
P4 5 1
P5 6 4
I am getting the order: P1 P2 P1 P5 P3 P4 P3 P5
Instead of: P1 P2 P3 P1 P4 P5 P3 P5
Posted
Updated 20-Mar-19 11:59am
v2

Quote:
The algorithm is easy to understand, but I can't seem to realize what am I doing wrong in my code:

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your cpde is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
 
Share this answer
 
A heavily commented, working (at least it looks so) version of your code.
C++
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Process
struct Proc
{
  string name;
  size_t arrival; // time of arrival
  size_t exec; // toatal execution time
  bool scheduled; // true if the process is inserted in the execution list
};

// show the Process
ostream & operator << ( ostream & os,  const Proc & proc);

// Execution node
struct Node
{
  const Proc * pproc; // pointer to the actual process
  size_t remain; // remaining execution time
  Node * next;
};

// Execution list
class ExecList
{
  Node* head = nullptr;
  size_t quantum = 3;
  size_t time = 0; // current global execution time

public:
  ~ExecList();
  void insert_nodes( vector <Proc> & vproc); // inserts suitable nodes
  bool execute(); // executes current process ('head')
  void remove();  // removes current process 
  void next(); // moves (head) to next process in the list
  bool is_empty(); // true if there are no more processes in the list
  void dump(); // shows the list (debugging)
};

void ExecList::next()
{
  head = head->next;
}

bool ExecList::is_empty()
{
  return (head == nullptr);
}

void ExecList::dump()
{ 
  Node * cur = head;
  if ( cur == nullptr) return;
  do
  { 
    cout << *(cur->pproc) << "\n";
    cur = cur->next; 
  } while (cur != head);
}

void ExecList::insert_nodes( vector <Proc> & vproc )
{

  // make a sublist with suitable nodes (for later insertion in the execution list) 
  Node * first = nullptr; // sublist first node
  Node * last = nullptr; // sublist last node
  for (auto & proc : vproc)
  {
    // add only not yet scheduled ones
    if ( ! proc.scheduled && proc.arrival <= time )
    {
      Node * cur = new Node();
      cur->pproc = &proc;
      cur->remain = proc.exec;
      proc.scheduled = true; // mark inserted process as 'scheduled'
      cur->next = nullptr;

      if ( first == nullptr )
      {
        first = cur;
        last = cur;
      }
      else
      {
        last->next = cur;
        last = cur;
      }
    }
  }
  // append the sublist at the end of the execution list
  if ( first != nullptr )
  {
    if ( head == nullptr)
    {
      head = first;
      last->next = head;
    }
    else
    {
      // find the last node of the execution list
      Node * exec_last = head;
      while ( exec_last->next != head)
        exec_last = exec_last->next;
      last->next = head;
      exec_last->next = first;
    }
  }
}

ExecList::~ExecList()
{
  // Release (if needed) allocated memory
  Node * cur;

  if ( ! head ) return;

  cur = head;
  do
  {
    Node * next = cur->next;
    delete cur;
    cur = next;
  } while ( cur != head );
}

// executes the current porcess (head). Returns true if the process is finished and should be removed
bool ExecList::execute()
{
  cout << "time " << time << ", executing process " << head->pproc->name << "\n";

  size_t dt = min( quantum, head->remain);

  head->remain -= dt;

  time += dt;

  return (head->remain == 0);
}

// removes the current process (head)
void ExecList::remove()
{
  if ( ! head ) return;

  if ( head->next == head )
  {
    delete head;
    head = nullptr;
    return;
  }

  Node * last = head->next;
  while ( last->next != head )
    last = last->next;

  last->next = head->next;
  delete head;
  head = last->next;
}

ostream & operator << ( ostream & os, const  Proc & proc)
{
  os << "name " << proc.name << ", arrival " << proc.arrival << ", exec " << proc.exec << ", scheduled " << proc.scheduled;
  return os;
}

istream & operator >> (istream & is, Proc & proc)
{
  is >> proc.name >> proc.arrival >> proc.exec;
  proc.scheduled = false;
  return is;
}

int main()
{
  size_t proc_count;
  cout << "how many processes?\n";
  cin >> proc_count;
  vector <Proc> vproc;

  for (size_t n=0; n < proc_count; ++n)
  {
    Proc proc;
    cout << "enter process " << n << " name, arrival time, execution time\n";
    cin >> proc;
    vproc.push_back( proc );
  }

  ExecList el;

  cout << "Execution:\n";

  bool process_finished = false;
  for (;;)
  {
    el.insert_nodes(vproc);
    //el.dump(); // uncomment this line to see the process list at this step
    if ( el.is_empty() ) break;
    if ( process_finished )
    {
      el.remove();
      if ( el.is_empty() ) break;
    }
    else
      el.next();

    process_finished = el.execute();
  }
}
 
Share this answer
 
v2
Comments
Member 14186705 21-Mar-19 17:15pm    
Thank you very much. I really appreciate it
CPallini 22-Mar-19 3:42am    
You are welcome.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900