Friday 20 April 2012

Process Scheduling

/*
There are N processes. Each may depend on another process to be completed to start.
Write a Program to schedule the processes.
Example Graph :
Process 3 and 5 can run only after Process 0
...
...
Process 1 can run after 2 and 4

Algo:
Initialization : Store in every node a list of all nodes which depend on it. Also store the count of nodes it depends on.
1. Complete the process which is independent, depends count = zero.
2. Now decrease the count of all nodes in its list , i.e., count of all nodes that depend on it.
3. Find next node which has depends count = zero. complete the process. go to step 2.
4. Repeat this for all processes.
*/


#include "iostream"
#include "vector"
class Process
{
public:
 int process_number;
 int depends_on;
 std::vector <Process *> complete_before;
 Process(int num) : process_number(num) , depends_on(0)  {  }
};

int main()
{
 std::vector <Process *> mylist;
 std::vector <Process *> finallist;
 for(int i=0;i<6;i++)
  mylist.push_back(new Process(i));
 // do something to add details

 mylist[0]->complete_before.push_back(mylist[3]);
 mylist[0]->complete_before.push_back(mylist[5]);
 mylist[2]->complete_before.push_back(mylist[1]);
 mylist[3]->complete_before.push_back(mylist[2]);
 mylist[4]->complete_before.push_back(mylist[1]);
 mylist[5]->complete_before.push_back(mylist[2]);
 mylist[5]->complete_before.push_back(mylist[4]);
 mylist[0]->depends_on = 0;
 mylist[1]->depends_on = 2;
 mylist[2]->depends_on = 2;
 mylist[3]->depends_on = 1;
 mylist[4]->depends_on = 1;
 mylist[5]->depends_on = 1;
 std::vector<Process *>::iterator itr = mylist.begin();
 while(itr != mylist.end())
 {
      Process * current = *itr;
      if(current->depends_on == 0)
      {
            std::vector<Process *>::iterator temp_itr = current->complete_before.begin();
            while(temp_itr != current->complete_before.end())
           {
                 (*temp_itr)->depends_on--;
                 temp_itr++;
           }
      }else
     {
            itr++;
           continue;
      }
      finallist.push_back(*itr);
      mylist.erase(itr);
      itr = mylist.begin();
 }
 itr = finallist.begin();
 while(itr != finallist.end())
 {
      std::cout << (*itr)->process_number << std::endl;
      itr++;
 }
 return 0;
}

1 comment:

Manu Machilles said...

Dude, Algorithm will make the soln more descriptive.. Thumbs up for the soln!