Robust/TransSim/Scheduler.java

   1 import java.util.HashSet;
   2
   3 public class Scheduler {
   4   Executor e;
   5
   6   public Scheduler(Executor e, long time) {
   7     this.e=e;
   8     schedule=new int[e.numEvents()+1][e.numThreads()];
   9     turn=new int[e.numEvents()];
  10     //give last time an event can be scheduled
  11     lasttime=new long[e.maxEvents()][e.numThreads()];
  12     schedtime=new long[e.maxEvents()][e.numThreads()];
  13     lastrd=new long[e.numEvents()+1][e.numObjects()];
  14     lastwr=new long[e.numEvents()+1][e.numObjects()];
  15     shorttesttime=time;
  16     computeFinishing(time);
  17   }
  18
  19   long currbest;
  20   long shorttesttime;
  21   int[][] schedule;
  22   int[] turn;
  23   long[][] lasttime;
  24   long[][] schedtime;
  25   long[][] lastrd;
  26   long[][] lastwr;
  27
  28   public long getTime() {
  29     return currbest;
  30   }
  31
  32   private void computeFinishing(long totaltime) {
  33     for(int threadnum=0;threadnum<e.numThreads();threadnum++) {
  34       ThreadClass thread=e.getThread(threadnum);
  35       long threadtime=totaltime;
  36       for(int transnum=thread.numTransactions()-1;transnum>=0;transnum--) {
  37         Transaction trans=thread.getTransaction(transnum);
  38         long ltime=trans.getTime(trans.numEvents()-1);
  39         threadtime-=ltime;
  40         lasttime[transnum][threadnum]=threadtime;
  41       }
  42     }
  43   }
  44
  45   private boolean scheduleTask(int step, int iturn) {
  46     for(int i=0;i<e.numThreads();i++) {
  47       schedule[step+1][i]=schedule[step][i];
  48     }
  49     schedule[step+1][iturn]--;
  50     turn[step]=iturn;
  51
  52     //compute start time
  53     ThreadClass thread=e.getThread(iturn);
  54     int transnum=schedule[0][iturn]-schedule[step][iturn];
  55     long starttime=0;
  56     if (transnum>0) {
  57       starttime=schedtime[transnum-1][iturn];
  58       Transaction prevtrans=thread.getTransaction(transnum-1);
  59       starttime+=prevtrans.getTime(prevtrans.numEvents()-1);
  60     }
  61     //Let's check for object conflicts that delay start time
  62     Transaction trans=thread.getTransaction(transnum);
  63     for(int ev=0;ev<trans.numEvents();ev++) {
  64       long evtime=trans.getTime(ev);
  65       int evobject=trans.getObject(ev);
  66
  67       switch(trans.getEvent(ev)) {
  68       case Transaction.READ:
  69         {
  70           //just need to check write time
  71           long newstart=lastwr[step][evobject]-evtime;
  72           if (newstart>starttime)
  73             starttime=newstart;
  74           break;
  75         }
  76       case Transaction.WRITE:
  77         {
  78           //just need to check both write and read times
  79           long newstart=lastwr[step][evobject]-evtime;
  80           if (newstart>starttime)
  81             starttime=newstart;
  82
  83           newstart=lastrd[step][evobject]-trans.getTime(trans.numEvents()-1);
  84           if (newstart>starttime)
  85             starttime=newstart;
  86           break;
  87         }
  88       default:
  89       }
  90     }
  91     //check to see if start time is okay
  92     if (starttime>lasttime[transnum][iturn])
  93       return false;
  94
  95     //good to update schedule
  96     schedtime[transnum][iturn]=starttime;
  97
  98     //copy read and write times forward
  99     for(int obj=0;obj<e.numObjects();obj++) {
 100       lastrd[step+1][obj]=lastrd[step][obj];
 101       lastwr[step+1][obj]=lastwr[step][obj];
 102     }
 103
 104     long finishtime=starttime+trans.getTime(trans.numEvents()-1);
 105
 106     //Update read and write times
 107     for(int ev=0;ev<trans.numEvents();ev++) {
 108       long evtime=trans.getTime(ev);
 109       int evobject=trans.getObject(ev);
 110       switch(trans.getEvent(ev)) {
 111       case Transaction.READ: {
 112           //just need to check write time
 113           if (finishtime>lastrd[step+1][evobject])
 114             lastrd[step+1][evobject]=finishtime;
 115           break;
 116         }
 117       case Transaction.WRITE: {
 118           //just need to check both write and read times
 119           if (finishtime>lastwr[step+1][evobject])
 120             lastwr[step+1][evobject]=finishtime;
 121           break;
 122         }
 123       default:
 124       }
 125     }
 126     //    System.out.println("thread="+iturn+" trans="+transnum+" stime="+starttime+" ftime="+finishtime+" transtime="+trans.getTime(trans.numEvents()-1));
 127     return true;
 128   }
 129
 130
 131   public void dosim() {
 132     for(int i=0;i<e.numThreads();i++) {
 133       schedule[0][i]=e.getThread(i).numTransactions();
 134     }
 135
 136     int lastEvent=e.numEvents()-1;
 137
 138     //go forward
 139     for(int step=0;step<=lastEvent;step++) {
 140       int iturn=0;
 141       for(;iturn<e.numThreads();iturn++) {
 142         if (schedule[step][iturn]>0)
 143           break;
 144       }
 145
 146       //force blank transactions first
 147       for(int i=0;i<e.numThreads();i++) {
 148         if (schedule[step][i]>0) {
 149           Transaction t=e.getThread(i).getTransaction(schedule[0][i]-schedule[step][i]);
 150           if ((t.numEvents()==1)&&(t.getEvent(0)==Transaction.DELAY)) {
 151             iturn=i;
 152             break;
 153           }
 154         }
 155       }
 156
 157       boolean lgood=scheduleTask(step, iturn);
 158
 159       if (step==lastEvent&&lgood) {
 160         long maxfinish=0;
 161         for(int i=0;i<e.numThreads();i++) {
 162           int numTrans=e.getThread(i).numTransactions();
 163           long startt=schedtime[numTrans-1][i];
 164           Transaction lasttrans=e.getThread(i).getTransaction(numTrans-1);
 165           long finisht=startt+lasttrans.getTime(lasttrans.numEvents()-1);
 166           if (finisht>maxfinish)
 167             maxfinish=finisht;
 168         }
 169
 170         if (maxfinish<=shorttesttime) {
 171           currbest=maxfinish;
 172           shorttesttime=maxfinish;
 173           computeFinishing(shorttesttime);
 174         }
 175       }
 176
 177       if (!lgood||step==lastEvent) {
 178         //go backwards
 179         step--;
 180         for(;step>=0;step--) {
 181           //check for delay transaction...just skip them
 182           Transaction oldtrans=e.getThread(turn[step]).getTransaction(schedule[0][turn[step]]-schedule[step][turn[step]]);
 183           if (oldtrans.numEvents()==1&&oldtrans.getEvent(0)==Transaction.DELAY)
 184             continue;
 185
 186           iturn=turn[step]+1;
 187           for(;iturn<e.numThreads();iturn++) {
 188             if (schedule[step][iturn]>0)
 189               break;
 190           }
 191           if (iturn<e.numThreads()) {
 192             //found something to iterate
 193             if (scheduleTask(step, iturn))
 194               break;
 195           }
 196         }
 197         if (step<0)
 198           return;
 199       }
 200     }
 201   }
 202
 203
 204   public static boolean checkConflicts(Transaction t1, Transaction t2) {
 205     HashSet writeset=new HashSet();
 206     HashSet readset=new HashSet();
 207
 208     for(int i=0;i<t1.numEvents();i++) {
 209       int t1obj=t1.getObject(i);
 210       int t1evt=t1.getEvent(i);
 211       if (t1evt==Transaction.READ) {
 212         readset.add(new Integer(t1obj));
 213       } else if (t1evt==Transaction.WRITE) {
 214         writeset.add(new Integer(t1obj));
 215       }
 216     }
 217
 218     for(int i=0;i<t2.numEvents();i++) {
 219       int t2obj=t2.getObject(i);
 220       int t2evt=t2.getEvent(i);
 221       if (t2evt==Transaction.READ) {
 222         if (writeset.contains(new Integer(t2obj)))
 223           return true;
 224       } else if (t2evt==Transaction.WRITE) {
 225         if (writeset.contains(new Integer(t2obj))||
 226             readset.contains(new Integer(t2obj)))
 227           return true;
 228       }
 229     }
 230     return false;
 231   }
 232 }