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