From e7ef7289e1717e9979ebe4454be914a42e0227fb Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 6 Jan 2010 21:37:59 +0000 Subject: [PATCH] simulator updates --- Robust/TransSim/FileSim.java | 66 ++++++++------- Robust/TransSim/FlexScheduler.java | 125 +++++++++++++++++++++++++++-- Robust/TransSim/ThreadInfo.java | 1 + Robust/TransSim/TransSim.java | 4 +- 4 files changed, 156 insertions(+), 40 deletions(-) diff --git a/Robust/TransSim/FileSim.java b/Robust/TransSim/FileSim.java index 4f42f551..4e979a94 100644 --- a/Robust/TransSim/FileSim.java +++ b/Robust/TransSim/FileSim.java @@ -14,27 +14,38 @@ public class FileSim { FlexScheduler ls=new FlexScheduler(e, FlexScheduler.LAZY, null); ls.start(); - - //Kill others at commit FlexScheduler ls4=new FlexScheduler(e, FlexScheduler.COMMIT, null); ls4.start(); - //Eager attack FlexScheduler ls5=new FlexScheduler(e, FlexScheduler.ATTACK, null); ls5.start(); - //Eager polite - FlexScheduler ls6=new FlexScheduler(e, FlexScheduler.POLITE, null); + FlexScheduler ls6=new FlexScheduler(e, FlexScheduler.SUICIDE, null); ls6.start(); - //Karma - FlexScheduler ls7=new FlexScheduler(e, FlexScheduler.KARMA, null); + FlexScheduler ls7=new FlexScheduler(e, FlexScheduler.TIMESTAMP, null); ls7.start(); + //Random + FlexScheduler ls8=new FlexScheduler(e, FlexScheduler.RANDOM, null); + ls8.start(); + + //Random + FlexScheduler ls9=new FlexScheduler(e, FlexScheduler.KARMA, null); + ls9.start(); + + //Random + FlexScheduler ls10=new FlexScheduler(e, FlexScheduler.POLITE, null); + ls10.start(); + + //Random + FlexScheduler ls11=new FlexScheduler(e, FlexScheduler.ERUPTION, null); + ls11.start(); + ls.join(); System.out.println("Lazy Time="+ls.getTime()); @@ -49,32 +60,27 @@ public class FileSim { System.out.println("Aborts="+ls5.getAborts()+" Commit="+ls5.getCommits()); ls6.join(); - System.out.println("Polite Abort="+ls6.getTime()); + System.out.println("Suicide Abort="+ls6.getTime()); System.out.println("Aborts="+ls6.getAborts()+" Commit="+ls6.getCommits()); ls7.join(); - System.out.println("Karma Abort="+ls7.getTime()); + System.out.println("Timestamp Abort="+ls7.getTime()); System.out.println("Aborts="+ls7.getAborts()+" Commit="+ls7.getCommits()); - ls=null;ls4=null;ls5=null;ls6=null;ls7=null; - - { - //Lock object accesses - FlexScheduler ls2=new FlexScheduler(e, FlexScheduler.LOCK, abortThreshold, abortRatio, deadlockdepth, null); - ls2.start(); - ls2.join(); - System.out.println("Deadlock count="+ls2.getDeadLockCount()); - System.out.println("Lock Abort="+ls2.getTime()); - System.out.println("Aborts="+ls2.getAborts()+" Commit="+ls2.getCommits()); - ls2=null; - } - { - //Lock Commit object accesses - FlexScheduler ls3=new FlexScheduler(e, FlexScheduler.LOCKCOMMIT, abortThreshold, abortRatio, deadlockdepth, null); - ls3.start(); - ls3.join(); - System.out.println("Deadlock count="+ls3.getDeadLockCount()); - System.out.println("LockCommit Abort="+ls3.getTime()); - System.out.println("Aborts="+ls3.getAborts()+" Commit="+ls3.getCommits()); - } + + ls8.join(); + System.out.println("Random Abort="+ls8.getTime()); + System.out.println("Aborts="+ls8.getAborts()+" Commit="+ls8.getCommits()); + + ls9.join(); + System.out.println("Karma Abort="+ls9.getTime()); + System.out.println("Aborts="+ls9.getAborts()+" Commit="+ls9.getCommits()); + + ls10.join(); + System.out.println("Polite Abort="+ls10.getTime()); + System.out.println("Aborts="+ls10.getAborts()+" Commit="+ls10.getCommits()); + + ls11.join(); + System.out.println("Eruption Abort="+ls11.getTime()); + System.out.println("Aborts="+ls11.getAborts()+" Commit="+ls11.getCommits()); } } \ No newline at end of file diff --git a/Robust/TransSim/FlexScheduler.java b/Robust/TransSim/FlexScheduler.java index eb7c81e9..5cc7c9b9 100644 --- a/Robust/TransSim/FlexScheduler.java +++ b/Robust/TransSim/FlexScheduler.java @@ -30,6 +30,7 @@ public class FlexScheduler extends Thread { r=new Random(100); eq=new PriorityQueue(); backoff=new int[e.numThreads()]; + retrycount=new int[e.numThreads()]; objtoinfo=new Hashtable(); threadinfo=new ThreadInfo[e.numThreads()]; blocked=new boolean[e.numThreads()]; @@ -68,10 +69,14 @@ public class FlexScheduler extends Thread { public static final int LAZY=0; public static final int COMMIT=1; public static final int ATTACK=2; - public static final int POLITE=3; - public static final int KARMA=4; + public static final int SUICIDE=3; + public static final int TIMESTAMP=4; public static final int LOCK=5; public static final int LOCKCOMMIT=6; + public static final int RANDOM=7; + public static final int KARMA=8; + public static final int POLITE=9; + public static final int ERUPTION=10; PriorityQueue eq; int policy; @@ -85,13 +90,18 @@ public class FlexScheduler extends Thread { Event[] currentevents; Random r; int[] backoff; + int[] retrycount; Hashtable objtoinfo; ThreadInfo[] threadinfo; boolean[] blocked; public boolean isEager() { - return policy==ATTACK||policy==POLITE||policy==KARMA; + return policy==ATTACK||policy==SUICIDE||policy==TIMESTAMP||policy==RANDOM||policy==KARMA||policy==POLITE; + } + + public boolean countObjects() { + return policy==KARMA||policy==ERUPTION; } public boolean isLock() { @@ -129,6 +139,12 @@ public class FlexScheduler extends Thread { eq.add(nev); } + //Aborts another thread... + public void stall(Event ev, long time) { + ev.setTime(time); + eq.add(ev); + } + private void releaseObjects(Transaction trans, int currthread, long time) { //remove all events @@ -229,6 +245,7 @@ public class FlexScheduler extends Thread { if (!abort) { //if it is a transaction, increment comit count if (trans.numEvents()>1||trans.getEvent(0)!=Transaction.DELAY) { + threadinfo[ev.getThread()].priority=0; commitcount++; if (serCommit!=null) { serCommit.addPoint(ev.getTime(),ev.getThread()); @@ -236,6 +253,7 @@ public class FlexScheduler extends Thread { } //Reset our backoff counter backoff[ev.getThread()]=BACKOFFSTART; + retrycount[ev.getThread()]=0; //abort the other threads for(int i=0;imaxpriority) + maxpriority=threadinfo[thread].priority; + } + if (maxpriority>threadinfo[ev.getThread()].priority) { + //we lose + threadinfo[ev.getThread()].priority++; + //stall for a little while + stall(ev, time+20); + return false; + } else { + //we win + for(Iterator thit=threadstokill.iterator();thit.hasNext();) { + Integer thread=(Integer)thit.next(); + reschedule(thread, time); + abortcount++; + } + return true; + } + } else if (policy==ERUPTION) { + int maxpriority=0; + //abort other transactions + for(Iterator thit=threadstokill.iterator();thit.hasNext();) { + Integer thread=(Integer)thit.next(); + if (threadinfo[thread].priority>maxpriority) + maxpriority=threadinfo[thread].priority; + } + if (maxpriority>threadinfo[ev.getThread()].priority) { + //we lose + //stall for a little while + stall(ev, time); + int ourpriority=threadinfo[ev.getThread()].priority; + for(Iterator thit=threadstokill.iterator();thit.hasNext();) { + Integer thread=(Integer)thit.next(); + threadinfo[thread].priority+=ourpriority;; + } + return false; + } else { + //we win + for(Iterator thit=threadstokill.iterator();thit.hasNext();) { + Integer thread=(Integer)thit.next(); + reschedule(thread, time); + abortcount++; + } + return true; + } + } else if (policy==POLITE) { + int retry=retrycount[ev.getThread()]++; + if (retry==22) { + for(Iterator thit=threadstokill.iterator();thit.hasNext();) { + Integer thread=(Integer)thit.next(); + reschedule(thread, time); + int dback=backoff[thread.intValue()]*2; + if (dback>0) + backoff[thread.intValue()]=dback; + abortcount++; + } + return true; + } else { + //otherwise stall + stall(ev, time+r.nextInt((1<0) backoff[ev.getThread()]=dback; abortcount++; return false; - } else if (policy==KARMA) { + } else if (policy==TIMESTAMP) { long opponenttime=0; for(Iterator thit=threadstokill.iterator();thit.hasNext();) { @@ -452,7 +552,12 @@ public class FlexScheduler extends Thread { //record read event if (!rdobjmap.containsKey(object)) rdobjmap.put(object,new HashSet()); - ((Set)rdobjmap.get(object)).add(new Integer(ev.getThread())); + if (((Set)rdobjmap.get(object)).add(new Integer(ev.getThread()))) { + //added new object + if (countObjects()) { + threadinfo[ev.getThread()].priority++; + } + } if (isEager()) { //do eager contention management Set conflicts=rdConflictSet(ev.getThread(), object); @@ -465,7 +570,11 @@ public class FlexScheduler extends Thread { //record write event if (!wrobjmap.containsKey(object)) wrobjmap.put(object,new HashSet()); - ((Set)wrobjmap.get(object)).add(new Integer(ev.getThread())); + if (((Set)wrobjmap.get(object)).add(new Integer(ev.getThread()))) { + if (countObjects()) { + threadinfo[ev.getThread()].priority++; + } + } if (isEager()) { Set conflicts=wrConflictSet(ev.getThread(), object); if (conflicts!=null) { diff --git a/Robust/TransSim/ThreadInfo.java b/Robust/TransSim/ThreadInfo.java index e359e5d6..48812c5d 100644 --- a/Robust/TransSim/ThreadInfo.java +++ b/Robust/TransSim/ThreadInfo.java @@ -8,6 +8,7 @@ public class ThreadInfo { boolean stalled; int oid; int index; + int priority; public void setObject(int oid) { this.oid=oid; diff --git a/Robust/TransSim/TransSim.java b/Robust/TransSim/TransSim.java index ce14e5b5..e34cfa15 100644 --- a/Robust/TransSim/TransSim.java +++ b/Robust/TransSim/TransSim.java @@ -65,14 +65,14 @@ public class TransSim { p.getSeries("ATTACK").addPoint(i, ls.getTime()); //Eager polite - ls=new FlexScheduler(e, FlexScheduler.POLITE, null); + ls=new FlexScheduler(e, FlexScheduler.SUICIDE, null); ls.dosim(); System.out.println("Polite Abort="+ls.getTime()); System.out.println("Aborts="+ls.getAborts()+" Commit="+ls.getCommits()); p.getSeries("POLITE").addPoint(i, ls.getTime()); //Karma - ls=new FlexScheduler(e, FlexScheduler.KARMA, null); + ls=new FlexScheduler(e, FlexScheduler.TIMESTAMP, null); ls.dosim(); System.out.println("Karma Abort="+ls.getTime()); System.out.println("Aborts="+ls.getAborts()+" Commit="+ls.getCommits()); -- 2.34.1