Robust/TransSim/FlexScheduler.java

   1 import java.util.*;
   2
   3 public class FlexScheduler extends Thread {
   4   Executor e;
   5   int abortThreshold;
   6   int abortRatio;
   7   int deadlockcount;
   8   int checkdepth;
   9   int barriercount;
  10
  11   public FlexScheduler(Executor e, int policy, int abortThreshold, int abortRatio, int checkdepth, Plot p) {
  12     this(e, policy, p);
  13     this.abortThreshold=abortThreshold;
  14     this.abortRatio=abortRatio;
  15     this.checkdepth=checkdepth;
  16   }
  17
  18   public void run() {
  19     dosim();
  20   }
  21
  22   public FlexScheduler(Executor e, int policy, Plot p) {
  23     this.e=e;
  24     barriercount=e.numThreads();
  25     aborted=new boolean[e.numThreads()];
  26     currentevents=new Event[e.numThreads()];
  27     rdobjmap=new Hashtable();
  28     wrobjmap=new Hashtable();
  29     this.policy=policy;
  30     r=new Random(100);
  31     eq=new PriorityQueue();
  32     backoff=new int[e.numThreads()];
  33     retrycount=new int[e.numThreads()];
  34     transferred=new int[e.numThreads()];
  35     objtoinfo=new Hashtable();
  36     threadinfo=new ThreadInfo[e.numThreads()];
  37     blocked=new boolean[e.numThreads()];
  38
  39     for(int i=0;i<e.numThreads();i++) {
  40       backoff[i]=BACKOFFSTART;
  41       threadinfo[i]=new ThreadInfo(this);
  42     }
  43     this.p=p;
  44     if (p!=null) {
  45       serCommit=p.getSeries("COMMIT");
  46       serStart=p.getSeries("START");
  47       serAbort=p.getSeries("ABORT");
  48       serStall=p.getSeries("STALL");
  49       serWake=p.getSeries("WAKE");
  50       serAvoid=p.getSeries("AVOIDDEADLOCK");
  51     }
  52   }
  53
  54   int lowid=0;
  55   int countlow=0;
  56
  57   Plot p;
  58   Series serCommit;
  59   Series serStart;
  60   Series serAbort;
  61   Series serStall;
  62   Series serAvoid;
  63   Series serWake;
  64
  65   public int getDeadLockCount() {
  66     return deadlockcount;
  67   }
  68
  69   //Where to start the backoff delay at
  70   public static final int BACKOFFSTART=1;
  71
  72   //Commit options
  73   public static final int LAZY=0;
  74   public static final int COMMIT=1;
  75   public static final int ATTACK=2;
  76   public static final int SUICIDE=3;
  77   public static final int TIMESTAMP=4;
  78   public static final int LOCK=5;
  79   public static final int LOCKCOMMIT=6;
  80   public static final int RANDOM=7;
  81   public static final int KARMA=8;
  82   public static final int POLITE=9;
  83   public static final int ERUPTION=10;
  84   public static final int THREAD=11;
  85   public static final int ATTACKTIME=12;
  86   public static final int ATTACKTHREAD=13;
  87
  88   public static String getName(int policy) {
  89     switch (policy) {
  90     case LAZY:
  91       return new String("LAZY");
  92     case COMMIT:
  93       return new String("COMMIT");
  94     case ATTACK:
  95       return new String("ATTACK");
  96     case SUICIDE:
  97       return new String("TIMID");
  98     case TIMESTAMP:
  99       return new String("TIMESTAMP");
 100     case LOCK:
 101       return new String("LOCK");
 102     case LOCKCOMMIT:
 103       return new String("LOCKCOMMIT");
 104     case RANDOM:
 105       return new String("RANDOM");
 106     case KARMA:
 107       return new String("KARMA");
 108     case POLITE:
 109       return new String("POLITE");
 110     case ERUPTION:
 111       return new String("ERUPTION");
 112     case THREAD:
 113       return new String("THREAD");
 114     case ATTACKTIME:
 115       return new String("ATTACKTIME");
 116     case ATTACKTHREAD:
 117       return new String("ATTACKTHREAD");
 118     }
 119     return null;
 120   }
 121
 122   PriorityQueue eq;
 123   int policy;
 124   boolean[] aborted;
 125   long shorttesttime;
 126   long earliesttime=-1;
 127   long starttime=-1;
 128   Hashtable rdobjmap;
 129   Hashtable wrobjmap;
 130   int abortcount;
 131   int commitcount;
 132   long backoffcycles;
 133   long stallcycles;
 134   long abortedcycles;
 135   Event[] currentevents;
 136   Random r;
 137   int[] backoff;
 138   int[] retrycount;
 139   int[] transferred;
 140   Hashtable objtoinfo;
 141   ThreadInfo[] threadinfo;
 142
 143   boolean[] blocked;
 144
 145   public boolean isEager() {
 146     return policy==ATTACK||policy==SUICIDE||policy==TIMESTAMP||policy==RANDOM||policy==KARMA||policy==POLITE||policy==ERUPTION||policy==THREAD||policy==ATTACKTIME||policy==ATTACKTHREAD;
 147   }
 148
 149   public boolean countObjects() {
 150     return policy==KARMA||policy==ERUPTION;
 151   }
 152
 153   public boolean isLock() {
 154     return policy==LOCK||policy==LOCKCOMMIT;
 155   }
 156
 157   public int getAborts() {
 158     return abortcount;
 159   }
 160
 161   public int getCommits() {
 162     return commitcount;
 163   }
 164
 165   public long getEarliestTime() {
 166     return earliesttime-starttime;
 167   }
 168
 169   public long getTime() {
 170     return shorttesttime-starttime;
 171   }
 172
 173   public long getStallTime() {
 174     return stallcycles;
 175   }
 176
 177   public long getBackoffTime() {
 178     return backoffcycles;
 179   }
 180
 181   public long getAbortedTime() {
 182     return abortedcycles;
 183   }
 184
 185   //Computes wasted time
 186   public void timewasted(int currthread, long currtime) {
 187     Event e=currentevents[currthread];
 188     Transaction trans=e.getTransaction();
 189     int eIndex=e.getEvent();
 190     long eTime=e.getTime();
 191     long timeleft=eTime-currtime;
 192     if (e.isStalled()) {
 193       stallcycles-=timeleft; //this time is no longer stalled...back it out
 194       timeleft=0;//if the event is stalled, we already waited this time...
 195     }
 196     long totaltime=trans.getTime(eIndex);
 197     totaltime-=timeleft;//subtract off time to the next event
 198     abortedcycles+=totaltime;
 199   }
 200
 201   //Aborts another thread...
 202   public void reschedule(int currthread, long currtime, long backofftime) {
 203     long time=currtime+backofftime;
 204     backoffcycles+=backofftime;
 205     currentevents[currthread].makeInvalid();
 206     if (threadinfo[currthread].isStalled()) {
 207       //remove from waiter list
 208       threadinfo[currthread].setStall(false);
 209       getmapping(threadinfo[currthread].getObjIndex()).getWaiters().remove(currentevents[currthread]);
 210     }
 211     if (serAbort!=null) {
 212       serAbort.addPoint(time, currthread);
 213     }
 214     Transaction trans=currentevents[currthread].getTransaction();
 215
 216     releaseObjects(trans, currthread, time);
 217     Event nev=new Event(time+trans.getTime(0), trans, 0, currthread, currentevents[currthread].getTransNum());
 218     currentevents[currthread]=nev;
 219     eq.add(nev);
 220   }
 221
 222   //Aborts another thread...
 223   public void stall(Event ev, long time, long delay) {
 224     stallcycles+=delay;
 225     ev.setTime(time+delay);
 226     ev.setStall();
 227     eq.add(ev);
 228   }
 229
 230   private void releaseObjects(Transaction trans, int currthread, long time) {
 231     //remove all events
 232     for(int i=0;i<trans.numEvents();i++) {
 233       ObjIndex object=trans.getObjIndex(i);
 234
 235       if (object!=null&&rdobjmap.containsKey(object)) {
 236         ((Set)rdobjmap.get(object)).remove(new Integer(currthread));
 237       }
 238       if (object!=null&&wrobjmap.containsKey(object)) {
 239         ((Set)wrobjmap.get(object)).remove(new Integer(currthread));
 240       }
 241       if (object!=null&&objtoinfo.containsKey(object)) {
 242         ObjectInfo oi=(ObjectInfo)objtoinfo.get(object);
 243         if (oi.getOwner()==currentevents[currthread].getThread()) {
 244           oi.releaseOwner();
 245
 246           //wake up one waiter
 247           for(Iterator waitit=oi.getWaiters().iterator();waitit.hasNext();) {
 248             //requeue everyone who was waiting on us and start them back up
 249             Event waiter=(Event)waitit.next();
 250             waitit.remove();
 251             waiter.setTime(time);
 252             threadinfo[waiter.getThread()].setStall(false);
 253             if (serWake!=null)
 254               serWake.addPoint(time,waiter.getThread());
 255             oi.setOwner(waiter.getThread());
 256             eq.add(waiter);
 257             break;
 258           }
 259         }
 260       }
 261     }
 262   }
 263
 264   /* Initializes things and returns number of transactions */
 265   public int startinitial() {
 266     int tcount=0;
 267     for(int i=0;i<e.numThreads();i++) {
 268       Transaction trans=e.getThread(i).getTransaction(0);
 269       long time=trans.getTime(0);
 270       Event ev=new Event(time, trans, 0, i, 0);
 271       currentevents[i]=ev;
 272       eq.add(ev);
 273       tcount+=e.getThread(i).numTransactions();
 274     }
 275     return tcount;
 276   }
 277
 278   public void dosim() {
 279     long lasttime=0;
 280     //start first transactions
 281     int numtrans=startinitial();
 282     System.out.println("Number of transactions="+numtrans);
 283     int tcount=0;
 284     while(!eq.isEmpty()) {
 285       Event ev=(Event)eq.poll();
 286       if (!ev.isValid()) {
 287         continue;
 288       }
 289
 290       Transaction trans=ev.getTransaction();
 291
 292       int event=ev.getEvent();
 293       long currtime=ev.getTime();
 294       lasttime=currtime;
 295       if (trans.started&&starttime==-1)
 296         starttime=currtime;
 297
 298       if (trans.numEvents()==(event+1)) {
 299         tryCommit(ev, trans);
 300         tcount++;
 301         if ((tcount%100000)==0)
 302           System.out.println("Attempted "+tcount+"transactions "+policy);
 303       } else {
 304         enqueueEvent(ev, trans);
 305       }
 306     }
 307     shorttesttime=lasttime;
 308     if (p!=null)
 309       p.close();
 310   }
 311
 312   private ObjectInfo getmapping(ObjIndex obj) {
 313     if (!objtoinfo.containsKey(obj))
 314       objtoinfo.put(obj, new ObjectInfo(this));
 315     return (ObjectInfo)objtoinfo.get(obj);
 316   }
 317
 318   public void tryCommit(Event ev, Transaction trans) {
 319     //ready to commit this one
 320     long currtime=ev.getTime();
 321     releaseObjects(trans, ev.getThread(), currtime);
 322
 323     if (ev.getThread()==lowid) {
 324       countlow++;
 325       if (countlow==4) {
 326         countlow=0;
 327         lowid++;
 328         if (lowid==e.numThreads())
 329           lowid=0;
 330       }
 331     }
 332
 333     //See if we have been flagged as aborted for the lazy case
 334     boolean abort=aborted[ev.getThread()];
 335     aborted[ev.getThread()]=false;
 336     if (!abort) {
 337       //if it is a transaction, increment commit count
 338       if (trans.numEvents()>1||trans.getEvent(0)!=Transaction.DELAY) {
 339         commitcount++;
 340         if (serCommit!=null) {
 341           serCommit.addPoint(ev.getTime(),ev.getThread());
 342         }
 343       }
 344       //Reset our backoff counter
 345       threadinfo[ev.getThread()].priority=0;
 346       threadinfo[ev.getThread()].aborted=false;
 347       backoff[ev.getThread()]=BACKOFFSTART;
 348       retrycount[ev.getThread()]=0;
 349       transferred[ev.getThread()]=0;
 350
 351       //abort the other threads
 352       for(int i=0;i<trans.numEvents();i++) {
 353         ObjIndex object=trans.getObjIndex(i);
 354         int op=trans.getEvent(i);
 355         //Mark commits to objects
 356         if (isLock()&&(op==Transaction.WRITE||op==Transaction.READ)) {
 357           if (object==null) {
 358             System.out.println(op);
 359           }
 360           getmapping(object).recordCommit();
 361         }
 362         //Check for threads we might cause to abort
 363         if (op==Transaction.WRITE) {
 364           HashSet abortset=new HashSet();
 365           if (rdobjmap.containsKey(object)) {
 366             for(Iterator it=((Set)rdobjmap.get(object)).iterator();it.hasNext();) {
 367               Integer threadid=(Integer)it.next();
 368               abortset.add(threadid);
 369               if (isLock()) {
 370                 ObjectInfo oi=getmapping(object);
 371                 oi.recordAbort();
 372               }
 373             }
 374           }
 375           if (wrobjmap.containsKey(object)) {
 376             for(Iterator it=((Set)wrobjmap.get(object)).iterator();it.hasNext();) {
 377               Integer threadid=(Integer)it.next();
 378               abortset.add(threadid);
 379               if (isLock()&&(!rdobjmap.containsKey(object)||!((Set)rdobjmap.get(object)).contains(threadid))) {
 380                 //if this object hasn't already cause this thread to
 381                 //abort, then flag it as an abort cause
 382                 ObjectInfo oi=getmapping(object);
 383                 oi.recordAbort();
 384               }
 385             }
 386           }
 387           for(Iterator abit=abortset.iterator();abit.hasNext();) {
 388             Integer threadid=(Integer)abit.next();
 389             if (policy==LAZY||policy==LOCK) {
 390               //just flag to abort when it trie to commit
 391               aborted[threadid]=true;
 392               if (serAbort!=null)
 393                 serAbort.addPoint(currtime, threadid);
 394             } else if (policy==COMMIT||policy==LOCKCOMMIT) {
 395               //abort it immediately
 396               timewasted(threadid, currtime);
 397               reschedule(threadid, currtime, 0);
 398               abortcount++;
 399             }
 400           }
 401         }
 402       }
 403     } else {
 404       abortcount++;
 405       timewasted(ev.getThread(), currtime);
 406     }
 407
 408     //add next transaction event...could be us if we aborted
 409     int nexttransnum=abort?ev.getTransNum():ev.getTransNum()+1;
 410     if (nexttransnum<e.getThread(ev.getThread()).numTransactions()) {
 411       Transaction nexttrans=e.getThread(ev.getThread()).getTransaction(nexttransnum);
 412       if (serStart!=null) {
 413         if (nexttrans.numEvents()>1||nexttrans.getEvent(0)!=Transaction.DELAY) {
 414           serStart.addPoint(ev.getTime(),ev.getThread());
 415         }
 416       }
 417
 418       Event nev=new Event(currtime+nexttrans.getTime(0), nexttrans, 0, ev.getThread(), nexttransnum);
 419       currentevents[ev.getThread()]=nev;
 420       eq.add(nev);
 421     } else {
 422       if (earliesttime==-1)
 423         earliesttime=currtime;
 424     }
 425   }
 426
 427   public Set rdConflictSet(int thread, ObjIndex obj) {
 428     if (!wrobjmap.containsKey(obj))
 429       return null;
 430     HashSet conflictset=new HashSet();
 431     for(Iterator it=((Set)wrobjmap.get(obj)).iterator();it.hasNext();) {
 432       Integer threadid=(Integer)it.next();
 433       if (threadid.intValue()!=thread)
 434         conflictset.add(threadid);
 435     }
 436     if (conflictset.isEmpty())
 437       return null;
 438     else
 439       return conflictset;
 440   }
 441
 442
 443   int normalize(int tid) {
 444     int newtid=tid-lowid;
 445     if (newtid<0)
 446       newtid+=e.numThreads();
 447     return newtid;
 448   }
 449
 450   public Set wrConflictSet(int thread, ObjIndex obj) {
 451     HashSet conflictset=new HashSet();
 452     if (rdobjmap.containsKey(obj)) {
 453       for(Iterator it=((Set)rdobjmap.get(obj)).iterator();it.hasNext();) {
 454         Integer threadid=(Integer)it.next();
 455         if (threadid.intValue()!=thread)
 456           conflictset.add(threadid);
 457       }
 458     }
 459     for(Iterator it=((Set)wrobjmap.get(obj)).iterator();it.hasNext();) {
 460       Integer threadid=(Integer)it.next();
 461       if (threadid.intValue()!=thread)
 462         conflictset.add(threadid);
 463     }
 464     if (conflictset.isEmpty())
 465       return null;
 466     else
 467       return conflictset;
 468   }
 469
 470   //Takes as parameter -- current transaction read event ev, conflicting
 471   //set of threads, and the current time
 472   //Returning false causes current transaction not continue to be scheduled
 473
 474
 475   public boolean handleConflicts(Event ev, Set threadstokill, long time) {
 476     if (policy==RANDOM) {
 477       boolean b=r.nextBoolean();
 478       if (b) {
 479         //delay
 480         int thread=ev.getThread();
 481         int dback=backoff[thread]*2;
 482         if (dback>0)
 483           backoff[thread]=dback;
 484         stall(ev, time, r.nextInt(backoff[thread]));
 485         return false;
 486       } else {
 487         //abort other transactions
 488         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 489           Integer thread=(Integer)thit.next();
 490           timewasted(thread, time);
 491           reschedule(thread, time, 0);
 492           abortcount++;
 493         }
 494         return true;
 495       }
 496     } else if (policy==KARMA) {
 497       int maxpriority=0;
 498       for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 499         Integer thread=(Integer)thit.next();
 500         if (threadinfo[thread].priority>maxpriority)
 501           maxpriority=threadinfo[thread].priority;
 502       }
 503       if (maxpriority>(threadinfo[ev.getThread()].priority+retrycount[ev.getThread()])) {
 504         //stall for a little while
 505         threadinfo[ev.getThread()].priority--;
 506         retrycount[ev.getThread()]++;
 507         int rtime=r.nextInt(3000);
 508         stall(ev, time, rtime);
 509         return false;
 510       } else {
 511         //we win
 512         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 513           Integer thread=(Integer)thit.next();
 514           int dback=backoff[thread]*2;
 515           if (dback>0)
 516             backoff[thread]=dback;
 517           int atime=r.nextInt(backoff[thread]);
 518           timewasted(thread, time);
 519           reschedule(thread, time, atime);
 520           abortcount++;
 521         }
 522         return true;
 523       }
 524     } else if (policy==ERUPTION) {
 525       int maxpriority=0;
 526       //abort other transactions
 527       for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 528         Integer thread=(Integer)thit.next();
 529         if (threadinfo[thread].priority>maxpriority)
 530           maxpriority=threadinfo[thread].priority;
 531       }
 532       if (maxpriority>(threadinfo[ev.getThread()].priority+retrycount[ev.getThread()])) {
 533         //we lose
 534         threadinfo[ev.getThread()].priority--;
 535         //stall for a little while
 536         int rtime=r.nextInt(3000);
 537         stall(ev, time, rtime);
 538         int ourpriority=threadinfo[ev.getThread()].priority;
 539         ourpriority-=transferred[ev.getThread()];
 540         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 541           Integer thread=(Integer)thit.next();
 542           threadinfo[thread].priority+=ourpriority;
 543         }
 544         transferred[ev.getThread()]=threadinfo[ev.getThread()].priority;
 545         retrycount[ev.getThread()]++;
 546
 547         return false;
 548       } else {
 549         //we win
 550         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 551           Integer thread=(Integer)thit.next();
 552           int dback=backoff[thread]*2;
 553           if (dback>0)
 554             backoff[thread]=dback;
 555           int atime=r.nextInt(backoff[thread]);
 556           timewasted(thread, time);
 557           reschedule(thread, time, atime);
 558           abortcount++;
 559         }
 560         return true;
 561       }
 562     } else if (policy==POLITE) {
 563       int retry=(++retrycount[ev.getThread()]);
 564       if (retry>=22) {
 565         retrycount[ev.getThread()]=0;
 566         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 567           Integer thread=(Integer)thit.next();
 568           timewasted(thread, time);
 569           reschedule(thread, time, 0);
 570           abortcount++;
 571         }
 572         return true;
 573       } else {
 574         //otherwise stall
 575         int stalltime=(1<<(retry-1))*12;
 576         if (stalltime<0)
 577           stalltime=1<<30;
 578         stall(ev, time, r.nextInt(stalltime));
 579         return false;
 580       }
 581     } else if (policy==ATTACK) {
 582       for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 583         Integer thread=(Integer)thit.next();
 584         timewasted(thread, time);
 585         reschedule(thread, time, r.nextInt(backoff[thread.intValue()]));
 586         int dback=backoff[thread.intValue()]*2;
 587         if (dback>0)
 588           backoff[thread.intValue()]=dback;
 589         abortcount++;
 590       }
 591       return true;
 592     } else if (policy==SUICIDE) {
 593       timewasted(ev.getThread(), time);
 594       reschedule(ev.getThread(), time, r.nextInt(backoff[ev.getThread()]));
 595       int dback=backoff[ev.getThread()]*2;
 596       if (dback>0)
 597         backoff[ev.getThread()]=dback;
 598       abortcount++;
 599       return false;
 600     } else if (policy==TIMESTAMP) {
 601       long opponenttime=0;
 602
 603       for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 604         Integer thread=(Integer)thit.next();
 605         Event other=currentevents[thread.intValue()];
 606         int eventnum=other.getEvent();
 607         long otime=other.getTransaction().getTime(other.getEvent());
 608         if (otime>opponenttime)
 609           opponenttime=otime;
 610       }
 611       if (opponenttime>ev.getTransaction().getTime(ev.getEvent())) {
 612         //kill ourself
 613         timewasted(ev.getThread(), time);
 614         reschedule(ev.getThread(), time, 0);
 615         abortcount++;
 616         return false;
 617       } else {
 618         //kill the opponents
 619         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 620           Integer thread=(Integer)thit.next();
 621           timewasted(thread, time);
 622           reschedule(thread, time, 0);
 623           abortcount++;
 624         }
 625         return true;
 626       }
 627     } else if (policy==THREAD) {
 628       long tid=1000;
 629
 630       for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 631         Integer thread=(Integer)thit.next();
 632         Event other=currentevents[thread.intValue()];
 633         int eventnum=other.getEvent();
 634         long otid=normalize(thread.intValue());
 635         if (tid>otid)
 636           tid=otid;
 637       }
 638       if (normalize(ev.getThread())>tid) {
 639         //kill ourself
 640         timewasted(ev.getThread(), time);
 641         reschedule(ev.getThread(), time, 0);
 642         abortcount++;
 643         return false;
 644       } else {
 645         //kill the opponents
 646         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 647           Integer thread=(Integer)thit.next();
 648           timewasted(thread, time);
 649           reschedule(thread, time, 0);
 650           abortcount++;
 651         }
 652         return true;
 653       }
 654     } else if (policy==ATTACKTIME) {
 655       boolean timebased=false;
 656       int tev=ev.getThread();
 657       timebased|=threadinfo[tev].aborted;
 658       for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 659         Integer thread=(Integer)thit.next();
 660         timebased|=threadinfo[thread.intValue()].aborted;
 661       }
 662       if (timebased) {
 663         long opponenttime=0;
 664
 665         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 666           Integer thread=(Integer)thit.next();
 667           Event other=currentevents[thread.intValue()];
 668           int eventnum=other.getEvent();
 669           long otime=other.getTransaction().getTime(other.getEvent());
 670           if (otime>opponenttime)
 671             opponenttime=otime;
 672         }
 673         if (opponenttime>ev.getTransaction().getTime(ev.getEvent())) {
 674           //kill ourself
 675           timewasted(ev.getThread(), time);
 676           reschedule(ev.getThread(), time, 0);
 677           threadinfo[ev.getThread()].aborted=true;
 678           abortcount++;
 679           return false;
 680         } else {
 681           //kill the opponents
 682           for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 683             Integer thread=(Integer)thit.next();
 684             timewasted(thread, time);
 685             reschedule(thread, time, 0);
 686             threadinfo[thread.intValue()].aborted=true;
 687             abortcount++;
 688           }
 689           return true;
 690         }
 691       } else {
 692         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 693           Integer thread=(Integer)thit.next();
 694           timewasted(thread, time);
 695           reschedule(thread, time, 0);
 696           threadinfo[thread.intValue()].aborted=true;
 697           abortcount++;
 698         }
 699         return true;
 700       }
 701     } else if (policy==ATTACKTHREAD) {
 702       boolean threadbased=false;
 703       int tev=ev.getThread();
 704       threadbased|=threadinfo[tev].aborted;
 705       for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 706         Integer thread=(Integer)thit.next();
 707         threadbased|=threadinfo[thread.intValue()].aborted;
 708       }
 709       if (threadbased) {
 710         long opponentthr=1000;
 711
 712         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 713           Integer thread=(Integer)thit.next();
 714           Event other=currentevents[thread.intValue()];
 715           int eventnum=other.getEvent();
 716           long othr=thread.intValue();
 717           if (othr<opponentthr)
 718             opponentthr=othr;
 719         }
 720         if (opponentthr<tev) {
 721           //kill ourself
 722           timewasted(ev.getThread(), time);
 723           reschedule(ev.getThread(), time, 0);
 724           threadinfo[ev.getThread()].aborted=true;
 725           abortcount++;
 726           return false;
 727         } else {
 728           //kill the opponents
 729           for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 730             Integer thread=(Integer)thit.next();
 731             timewasted(thread, time);
 732             reschedule(thread, time, 0);
 733             threadinfo[thread.intValue()].aborted=true;
 734             abortcount++;
 735           }
 736           return true;
 737         }
 738       } else {
 739         for(Iterator thit=threadstokill.iterator();thit.hasNext();) {
 740           Integer thread=(Integer)thit.next();
 741           timewasted(thread, time);
 742           reschedule(thread, time, 0);
 743           threadinfo[thread.intValue()].aborted=true;
 744           abortcount++;
 745         }
 746         return true;
 747       }
 748     }
 749
 750     //Not eager
 751     return true;
 752   }
 753
 754   //Handle current event (read, write, delay) in a transaction and
 755   //enqueue the next one
 756
 757   public void enqueueEvent(Event ev, Transaction trans) {
 758     //just enqueue next event
 759     int event=ev.getEvent();
 760     long currtime=ev.getTime();
 761     ObjIndex object=trans.getObjIndex(event);
 762     int operation=trans.getEvent(event);
 763
 764     if ((operation==Transaction.READ||operation==Transaction.WRITE)&&isLock()) {
 765       ObjectInfo oi=getmapping(object);
 766
 767       if (oi.isRisky()) {
 768         if (oi.isOwned()&&oi.getOwner()!=ev.getThread()) {
 769           //we're going to wait
 770           boolean deadlocked=true;
 771           ObjectInfo toi=oi;
 772           for(int i=0;i<checkdepth;i++) {
 773             //check if stalling would close the loop
 774             if (toi.getOwner()==ev.getThread())
 775               break;
 776             //see if cycle is broken
 777             if (!threadinfo[toi.getOwner()].isStalled()) {
 778               deadlocked=false;
 779               break;
 780             }
 781             //follow one more in depth
 782             toi=getmapping(threadinfo[toi.getOwner()].getObjIndex());
 783           }
 784
 785           if (!deadlocked) {
 786             //don't wait on stalled threads, we could deadlock
 787             threadinfo[ev.getThread()].setStall(true);
 788             threadinfo[ev.getThread()].setObjIndex(object);
 789             if (serStall!=null)
 790               serStall.addPoint(ev.getTime(),ev.getThread());
 791             oi.addWaiter(ev);
 792             return;
 793           } else {
 794             if (serAvoid!=null)
 795               serAvoid.addPoint(ev.getTime(),ev.getThread());
 796             deadlockcount++;
 797           }
 798         } else {
 799           //we have object
 800           oi.setOwner(ev.getThread());
 801         }
 802       }
 803     }
 804
 805     //process the current event
 806     if (operation==Transaction.READ) {
 807       //record read event
 808       if (!rdobjmap.containsKey(object))
 809         rdobjmap.put(object,new HashSet());
 810       if (((Set)rdobjmap.get(object)).add(new Integer(ev.getThread()))) {
 811         //added new object
 812         if (countObjects()) {
 813           threadinfo[ev.getThread()].priority++;
 814         }
 815       }
 816       if (isEager()) {
 817         //do eager contention management
 818         Set conflicts=rdConflictSet(ev.getThread(), object);
 819         if (conflicts!=null) {
 820           if (!handleConflicts(ev, conflicts, currtime)) {
 821             ((Set)rdobjmap.get(object)).remove(new Integer(ev.getThread()));
 822             return;
 823           }
 824         }
 825       }
 826     } else if (operation==Transaction.WRITE) {
 827       //record write event
 828       if (!wrobjmap.containsKey(object))
 829         wrobjmap.put(object,new HashSet());
 830       if (((Set)wrobjmap.get(object)).add(new Integer(ev.getThread()))) {
 831         if (countObjects()) {
 832           threadinfo[ev.getThread()].priority++;
 833         }
 834       }
 835       if (isEager()) {
 836         Set conflicts=wrConflictSet(ev.getThread(), object);
 837         if (conflicts!=null) {
 838           if (!handleConflicts(ev, conflicts, currtime)) {
 839             ((Set)wrobjmap.get(object)).remove(new Integer(ev.getThread()));
 840             return;
 841           }
 842         }
 843       }
 844     } else if (operation==Transaction.BARRIER) {
 845       barriercount--;
 846       if (barriercount==0) {
 847         for(int i=0;i<e.numThreads();i++) {
 848           //enqueue the next event
 849           Event bev=currentevents[i];
 850           int bevent=bev.getEvent();
 851           long bcurrtime=bev.getTime();
 852           Transaction btrans=bev.getTransaction();
 853           long deltatime=btrans.getTime(bevent+1)-btrans.getTime(bevent);
 854           Event nev=new Event(deltatime+currtime, btrans, bevent+1, bev.getThread(), bev.getTransNum());
 855           currentevents[bev.getThread()]=nev;
 856           eq.add(nev);
 857         }
 858         barriercount=e.numThreads();
 859       } else {
 860         //Do nothing
 861         //wait until all threads in barrier
 862       }
 863       return;
 864     }
 865     retrycount[ev.getThread()]=0;
 866     transferred[ev.getThread()]=0;
 867     //enqueue the next event
 868     long deltatime=trans.getTime(event+1)-trans.getTime(event);
 869     Event nev=new Event(deltatime+currtime, trans, event+1, ev.getThread(), ev.getTransNum());
 870     currentevents[ev.getThread()]=nev;
 871     eq.add(nev);
 872   }
 873
 874
 875   class Event implements Comparable {
 876     boolean valid;
 877     long time;
 878     int num;
 879     Transaction t;
 880     int threadid;
 881     int transnum;
 882     boolean stalled;
 883
 884     public boolean isStalled() {
 885       return stalled;
 886     }
 887
 888     public void setStall() {
 889       stalled=true;
 890     }
 891
 892     public void makeInvalid() {
 893       valid=false;
 894     }
 895
 896     public boolean isValid() {
 897       return valid;
 898     }
 899
 900     public int getTransNum() {
 901       return transnum;
 902     }
 903
 904     public Transaction getTransaction() {
 905       return t;
 906     }
 907
 908     public int getEvent() {
 909       return num;
 910     }
 911
 912     public long getTime() {
 913       return time;
 914     }
 915
 916     public void setTime(long time) {
 917       this.time=time;
 918     }
 919
 920     public int getThread() {
 921       return threadid;
 922     }
 923
 924     public Event(long time, Transaction t, int num, int threadid, int transnum) {
 925       this.time=time;
 926       this.t=t;
 927       this.num=num;
 928       this.threadid=threadid;
 929       this.transnum=transnum;
 930       valid=true;
 931     }
 932
 933     //break ties to allow commits to occur earliest
 934     public int compareTo(Object o) {
 935       Event e=(Event)o;
 936       long delta=time-e.time;
 937       if (delta!=0) {
 938         if (delta>0)
 939           return 1;
 940         else
 941           return -1;
 942       }
 943       if (((getEvent()+1)==getTransaction().numEvents())&&
 944           (e.getEvent()+1)!=e.getTransaction().numEvents())
 945         return -1;
 946       if (((getEvent()+1)!=getTransaction().numEvents())&&
 947           (e.getEvent()+1)==e.getTransaction().numEvents())
 948         return 1;
 949       return 0;
 950     }
 951   }
 952 }