1 import java.util.HashSet;
3 public class Scheduler {
6 public Scheduler(Executor e, long time) {
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()];
16 computeFinishing(time);
28 public long getTime() {
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);
40 lasttime[transnum][threadnum]=threadtime;
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];
49 schedule[step+1][iturn]--;
53 ThreadClass thread=e.getThread(iturn);
54 int transnum=schedule[0][iturn]-schedule[step][iturn];
57 starttime=schedtime[transnum-1][iturn];
58 Transaction prevtrans=thread.getTransaction(transnum-1);
59 starttime+=prevtrans.getTime(prevtrans.numEvents()-1);
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);
67 switch(trans.getEvent(ev)) {
68 case Transaction.READ:
70 //just need to check write time
71 long newstart=lastwr[step][evobject]-evtime;
72 if (newstart>starttime)
76 case Transaction.WRITE:
78 //just need to check both write and read times
79 long newstart=lastwr[step][evobject]-evtime;
80 if (newstart>starttime)
83 newstart=lastrd[step][evobject]-trans.getTime(trans.numEvents()-1);
84 if (newstart>starttime)
91 //check to see if start time is okay
92 if (starttime>lasttime[transnum][iturn])
95 //good to update schedule
96 schedtime[transnum][iturn]=starttime;
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];
104 long finishtime=starttime+trans.getTime(trans.numEvents()-1);
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;
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;
126 // System.out.println("thread="+iturn+" trans="+transnum+" stime="+starttime+" ftime="+finishtime+" transtime="+trans.getTime(trans.numEvents()-1));
131 public void dosim() {
132 for(int i=0;i<e.numThreads();i++) {
133 schedule[0][i]=e.getThread(i).numTransactions();
136 int lastEvent=e.numEvents()-1;
139 for(int step=0;step<=lastEvent;step++) {
141 for(;iturn<e.numThreads();iturn++) {
142 if (schedule[step][iturn]>0)
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)) {
157 boolean lgood=scheduleTask(step, iturn);
159 if (step==lastEvent&&lgood) {
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)
170 if (maxfinish<=shorttesttime) {
172 shorttesttime=maxfinish;
173 computeFinishing(shorttesttime);
177 if (!lgood||step==lastEvent) {
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)
187 for(;iturn<e.numThreads();iturn++) {
188 if (schedule[step][iturn]>0)
191 if (iturn<e.numThreads()) {
192 //found something to iterate
193 if (scheduleTask(step, iturn))
204 public static boolean checkConflicts(Transaction t1, Transaction t2) {
205 HashSet writeset=new HashSet();
206 HashSet readset=new HashSet();
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));
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)))
224 } else if (t2evt==Transaction.WRITE) {
225 if (writeset.contains(new Integer(t2obj))||
226 readset.contains(new Integer(t2obj)))