Comparing Variants of Scheduling Algorithms

Description: These programs are used to test and compare the variants in different scheduling algorithms; they are Greedy algorithm, Semi-clairvoyant R algorithm, Shortest Processing Time First (SPF) algorithm and First In First Out (FIFO) algorithm. The Greedy job scheduler focus on minimizing the past-due-date penalties, and the others focus on minimizing the average flow time and average stretch.

In the Greedy algorithm, the jobs ordered in respect to Wi by quick sorter and scheduled by their deadlines. This algorithm cares more about reaching as much as possible job deadlines; as a result, the penalties caused by passing the due date are minimized. But the Semi-Clairvoyant R algorithm, SPF and FIFO focus on achieving good average flow time and average stretch, and they are preemption allowed.

To get direct and complete comparison data, the jobs are randomly generated with their own descriptions, such as job Ids, release times, weights and so on. This Greedy scheduler treats each job processing time as one time unit, and the Schedule-comparer processes the jobs according to their own processing times.

Example:This is what my code outputs on these inputs.

These screen shots are the scheduling results of the random generated jobs. And they are divided into three sections, they are job description, scheduling parameter calcution,and scheduling list respectively.

In the programs, there have limitations for generating random jobs just for convenience handy checking.

The followings are part of the codes:

Greedy.java

/******************************************************
* Project:         Testing the variants in scheduling algorithms
* File:            Greedy.java
* Discription:     a random number of jobs are gennerated with random weights. Jobs are
*                  sorted according to job weights, and then
*                    scheduled per Greedy algorithm.
*
* Start date:      Oct. 11, 2004
* Programmer:      Qian Li
*
*******************************************************/


class Greedy {

   Job[] jobList;
   Job[] sortedJobList;
   int[] schedule;

   public Greedy()
   /*-----------------------------
   PURPOSE: constructor, creat jobs and add to job list
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   {

      int jobCounts;
      int wipi, processsTime, deadLine;

      jobCounts = getRandom(30);

      jobList = new Job[jobCounts];
      sortedJobList = new Job[jobCounts];
      schedule = new int[jobCounts];

      for(int i=0; i<jobCounts; i++)
      {
         wipi = getRandom(100);
         //processsTime = getRandom(10);
         processsTime = 1;
         deadLine = getRandom(jobCounts);
         // ??? algrithm limit: dead line can not over job count.
         //jobList[i] = new Job(i+1, wipi, processsTime, deadLine);
         jobList[i] = new Job(i+1, wipi, processsTime, deadLine);
      }

   }

   /*-----------------------------
   PURPOSE: display all jobs in job list.
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   private void displayData()
   {
      System.out.println("\r\n\r\nJob List:");
      System.out.println("\r\njobno\tWi/Pi\tprocessTime\tdeadLine\tweights");
      System.out.println(
         "-----------------------------------------------------------------");
      for(int i=0; i<jobList.length; i++)
      {
         System.out.println( "  " + jobList[i].getJobNumber() + "\t  "
                         + jobList[i].getWeight() + "\t  "
                         + jobList[i].getProcessTime() + "\t\t  "
                         + jobList[i].getDeadLine() + "\t\t  "
                         + (jobList[i].getWeight() * jobList[i].getProcessTime())
                         );
      }
   }

   /*-----------------------------
   PURPOSE: generate a random integer under a max number.
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   private int getRandom(int Max)
   {
      return((int)(Math.random() * (double)Max) + 1);
   }

   /*-----------------------------
   PURPOSE: Display sorted job list for debugging.
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   private void displaySortedData()
   {
      System.out.println("\r\n\r\nSorted Job List:");
      System.out.println("\r\njobno\tWi/Pi\tprocessTime\tdeadLine\tweights");
      System.out.println(
         "-----------------------------------------------------------------");
      for(int i=0; i<sortedJobList.length; i++)
      {
         System.out.println(  "  " + sortedJobList[i].getJobNumber() + "\t  "
                         + sortedJobList[i].getWeight() + "\t  "
                         + sortedJobList[i].getProcessTime() + "\t\t  "
                         + sortedJobList[i].getDeadLine() + "\t\t  "
                         + (sortedJobList[i].getWeight() * sortedJobList[i].getProcessTime())
                         );
      }
   }

   /*-----------------------------
   PURPOSE: Sort jobs according to job weights with quick sort algorithm.
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   public void sort()
   {
      Sorter sortJob = new QuickSorter();
      sortJob.sort(jobList, sortedJobList);
   }

   /*-----------------------------
   PURPOSE: make schedule per Greedy algorithm.
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   private void makeSchedule()
   {
      scheduleMaker scheduleJob = new GreedyScheduleMaker();
      scheduleJob.makeSchedule(sortedJobList, schedule);
   }

   /*-----------------------------
   PURPOSE: Display sccheduled job list and statistics.
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   private void displayResult()
   {
      System.out.println("\r\n\r\nSchedule:");
      System.out.println("\r\ntime\tjobno");
      System.out.println("--------------");
      for(int i=0; i<jobList.length; i++)
      {
         System.out.println("  " + (i+1) + "\t" + schedule[i]);
      }


      int penalties = 0;
      int penalty_count = 0;
      for(int k=0; k<jobList.length; k++)
      {
         if( (k+1) > jobList[schedule[k]-1].getDeadLine() )
         {
            penalty_count++;
            penalties += jobList[schedule[k]-1].getWeight();
         }
      }
      System.out.println("\r\nThe number of late tasks = " + penalty_count);
      System.out.println("\r\nThe total penalties = " + penalties);
   }

   public static void main(String args[])
   /*-----------------------------
   PURPOSE: creates instance of class Greedy. Sort, make schedule and
          display scheduled job list.
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   {
      System.out.println("Starting Greedy job scheduler ...");
      Greedy testObj = new Greedy();
      testObj.displayData();
      testObj.sort();
      testObj.displaySortedData();

      /*testObj.sortWeights();*/
      testObj.makeSchedule();
      testObj.displayResult();
      System.out.println("\r\n");
   }

}


SchedulerCompare.java

/******************************************************
* Project:         Testing the variants in scheduling algorithms
* File:            SchedulerCompare.java
* Purpose:         For every second, a random number is generated for the number of
*                  job released at this time. If this number is not zero, the exact
*                  number of random jobs are created and added into R,S,F scheduler
*              queue according to respective algorithm. Only the first ten second can
*              release jobs.
*                  The job at the top of scheduler queue run one second as the scheduler
*                  algorithm defined. The program terminated after all scheduler queues
*                  are empty and statistics of the schedules calculated at the end.
*
* Start date:      Oct. 11, 2004
* Programmer:      Qian Li
*
*******************************************************/

class SchedulerCompare {

   public SchedulerCompare()
   /*-----------------------------
   PURPOSE: constructor, creat scheduler queues..
   RECEIVES: nothing
   RETURNS: nothing
   ---------------------------------*/
   {

      R_execQueue = new Queue();
      R_generateQueue = new Queue();
      S_execQueue = new Queue();
      S_generateQueue = new Queue();
      F_execQueue = new Queue();
      F_generateQueue = new Queue();
   }

   public int ReleaseJobsCount(int time)
   /*-----------------------------
   PURPOSE: generate a random number for jobs released at the time.
   RECEIVES: an integer of the time
   RETURNS: an integer of released jobs at the second
   REMARKS: first second at least one job is going to be released..
   ---------------------------------*/
   {
      int count;

      count = (int)(Math.random() * 10);

      if(count < 3)
      {
         count = 0;
      }
      else if(count < 8)
      {
         count = 1;
      }
      else
      {
         count = 2;
      }

      if((time == 1) && (count == 0))
      {
         count = 1;
      }

      return(count);
   }

   public void run()
   /*-----------------------------
   PURPOSE: Loop for every second. Jobs are generated in every second and added into
          R. S. F. working queues. The job at the top of each working queue run
          for one second. The loop end when all working queues are empty and statistics
          are displayed for each scheduler algorithm.
   RECEIVES: nothing.
   RETURNS: nothing.
   REMARKS: only first ten second can generate jobs.
   ---------------------------------*/
   {
      int i, count, R_DONE, S_DONE, F_DONE;
      int time = 1;
      Job currJob;

      Scheduler R_Sched = new Rscheduler();
      Scheduler F_Sched = new FifoScheduler();
      Scheduler S_Sched = new Sscheduler();

      count = ReleaseJobsCount(time);
      for(i=0; i<count; i++) //move to queue
      {
         currJob = new Job(time);
         R_Sched.addJob(currJob);
         R_generateQueue.enQueue(currJob);

         currJob = new Job(currJob);
         S_Sched.addJob(currJob);
         S_generateQueue.enQueue(currJob);

         currJob = new Job(currJob);
         F_Sched.addJob(currJob);
         F_generateQueue.enQueue(currJob);
      }

      R_DONE = 0;
      S_DONE = 0;
      F_DONE = 0;
      while((F_DONE == 0) || (S_DONE == 0) || (R_DONE == 0))
      {
         if((R_DONE == 0) && ((currJob = R_Sched.run(time)) != null))
         {
            R_execQueue.enQueue(currJob);
         }
         else
         {
            R_DONE = 1;
         }

         if((S_DONE == 0) && ((currJob = S_Sched.run(time)) != null))
         {
            S_execQueue.enQueue(currJob);
         }
         else
         {
            S_DONE = 1;
         }

         if((F_DONE == 0) && ((currJob = F_Sched.run(time)) != null))
         {
            F_execQueue.enQueue(currJob);
         }
         else
         {
            F_DONE = 1;
         }

         time++;
         if(time < 10)
         {
            count = ReleaseJobsCount(time);
            for(i=0; i<count; i++) //move to queue
            {
               currJob = new Job(time);
               R_Sched.addJob(currJob);
               R_generateQueue.enQueue(currJob);

               currJob = new Job(currJob);
               S_Sched.addJob(currJob);
               S_generateQueue.enQueue(currJob);

               currJob = new Job(currJob);
               F_Sched.addJob(currJob);
               F_generateQueue.enQueue(currJob);
            }
         }
      }

      System.out.println("\r\n\r\nSemi-clairbvoyant R Scheduler:\r\n");
      R_generateQueue.listJobs();
      R_generateQueue.calculate();
      R_execQueue.listExec();

      System.out.println("\r\n\r\nShortest Processing time First Scheduler:\r\n");
      S_generateQueue.listJobs();
      S_generateQueue.calculate();
      S_execQueue.listExec();

      System.out.println("\r\n\r\nFirst In First Out Scheduler:\r\n");
      F_generateQueue.listJobs();
      F_generateQueue.calculate();
      F_execQueue.listExec();
   }

   public static void main(String args[])
   /*-----------------------------
   PURPOSE: creates new instance of class
            SchedulerCompare, and run scheduler comparation.
   RECEIVES: nothing
   RETURNS: nothing
   REMARKS: The constructor gets called only once, at first start.
   ---------------------------------*/
   {

      System.out.println("Starting Scheduler Compare...\r\n");
      //Job.displayListTitle();


      SchedulerCompare mainFrame = new SchedulerCompare();
      mainFrame.run();
   }

   private Queue R_execQueue;
   private Queue S_execQueue;
   private Queue F_execQueue;
   private Queue R_generateQueue;
   private Queue S_generateQueue;
   private Queue F_generateQueue;

}