1 package Analysis.Scheduling;
3 import java.util.Hashtable;
4 import java.util.Iterator;
5 import java.util.LinkedList;
6 import java.util.Queue;
7 import java.util.Vector;
8 import java.util.Map.Entry;
10 import Analysis.TaskStateAnalysis.FlagState;
11 import Analysis.TaskStateAnalysis.TaskAnalysis;
12 import IR.ClassDescriptor;
14 import IR.TaskDescriptor;
17 public class ScheduleSimulator {
19 private Vector<Schedule> scheduling;
20 private Vector<CoreSimulator> cores;
21 private Vector<TaskSimulator> tasks;
22 private Vector<CheckPoint> checkpoints;
23 private int processTime;
24 private int invoketime;
27 TaskAnalysis taskanalysis;
29 public ScheduleSimulator(int coreNum, State state, TaskAnalysis taskanalysis) {
31 this.coreNum = coreNum;
32 this.scheduling = null;
35 this.checkpoints = null;
39 this.taskanalysis = taskanalysis;
42 public ScheduleSimulator(int coreNum, Vector<Schedule> scheduling, State state, TaskAnalysis taskanalysis) {
44 this.coreNum = coreNum;
45 this.scheduling = scheduling;
46 this.cores = new Vector<CoreSimulator>(this.coreNum);
47 for(int i = 0; i < this.coreNum; i++) {
48 this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
50 this.tasks = new Vector<TaskSimulator>();
51 this.checkpoints = null;
55 this.taskanalysis = taskanalysis;
59 public Vector<CheckPoint> getCheckpoints() {
63 public int getCoreNum() {
67 public void setCoreNum(int coreNum) {
68 this.coreNum = coreNum;
69 if(this.cores != null) {
72 this.cores = new Vector<CoreSimulator>(this.coreNum);
73 for(int i = 0; i < this.coreNum; i++) {
74 this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
76 if(this.scheduling != null) {
81 public int getUtility(int index) {
82 return (this.cores.elementAt(index).getActiveTime() * 100) / this.processTime;
85 public Vector<Schedule> getScheduling() {
89 public void setScheduling(Vector<Schedule> scheduling) {
90 this.scheduling = scheduling;
91 if(this.tasks == null) {
92 this.tasks = new Vector<TaskSimulator>();
96 if(this.cores != null) {
97 for(int i = 0; i < this.coreNum; i++) {
98 CoreSimulator core = this.cores.elementAt(i);
100 core.setRSchedule(FIFORSchedule.getFIFORSchedule());
103 this.cores = new Vector<CoreSimulator>(this.coreNum);
104 for(int i = 0; i < this.coreNum; i++) {
105 this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
108 if(this.checkpoints != null) {
109 this.checkpoints.clear();
115 public void applyScheduling() {
116 assert(this.state != null);
118 for(int i = 0; i < this.scheduling.size(); i++) {
119 Schedule temp = this.scheduling.elementAt(i);
120 CoreSimulator cs = this.cores.elementAt(temp.getCoreNum());
121 cs.deployTasks(temp.getTasks());
122 cs.setTargetCSimulator(temp.getTargetCoreTable());
123 cs.setAllyCSimulator(temp.getAllyCoreTable());
124 cs.setTargetFState(temp.getTargetFStateTable());
126 // inject a Startup Object to each core
127 for(int i = 0; i < this.coreNum; i++) {
128 ClassDescriptor startupobject=(ClassDescriptor)state.getClassSymbolTable().get(TypeUtil.StartupClass);
129 FlagState fsstartup = (FlagState)taskanalysis.getRootNodes(startupobject).elementAt(0);
130 ObjectSimulator newObj = new ObjectSimulator(startupobject, fsstartup);
131 this.cores.elementAt(i).addObject(newObj);
135 public Vector<TaskSimulator> getTasks() {
139 public int process() {
140 assert(this.scheduling != null);
144 if(this.checkpoints == null) {
145 this.checkpoints = new Vector<CheckPoint>();
147 this.checkpoints.clear();
150 this.processTime = 0;
152 // first decide next task to execute on each core
154 for(i = 0; i < this.cores.size(); i++) {
155 CoreSimulator cs = this.cores.elementAt(i);
156 TaskSimulator task = cs.process();
158 this.tasks.add(task);
162 // add STARTTASK checkpoint for all the initial tasks
163 CheckPoint cp = new CheckPoint(this.processTime);
164 for(i = 0; i < this.tasks.size(); i++) {
165 TaskSimulator task = this.tasks.elementAt(i);
166 Action action = new Action(task.getCs().getCoreNum(), Action.TASKSTART);
167 action.setTd(task.getTd());
168 cp.addAction(action);
170 this.checkpoints.add(cp);
173 // if no more tasks on each core, simulation finish
174 if(this.tasks.size() == 0) {
178 // for each task in todo queue, decide the execution path of this time
179 // according to statistic information
180 //int index = 0; // indicate the task to finish first
181 int finishTime = Integer.MAX_VALUE;
182 Vector<TaskSimulator> finishTasks = new Vector<TaskSimulator>();
183 for(i = 0; i < this.tasks.size(); i++) {
184 TaskSimulator task = this.tasks.elementAt(i);
186 int tempTime = task.getCurrentRun().getFinishTime();
187 if(tempTime < finishTime) {
188 finishTime = tempTime;
190 finishTasks.add(task);
191 } else if (tempTime == finishTime) {
192 finishTasks.add(task);
195 for(i = 0; i < this.tasks.size(); i++) {
196 TaskSimulator task = this.tasks.elementAt(i);
197 if(!finishTasks.contains(task)) {
198 task.getCs().updateTask(finishTime);
201 this.processTime += finishTime;
202 cp = new CheckPoint(this.processTime);
203 Action action = null;
204 for(i = 0; i < finishTasks.size(); i++) {
205 TaskSimulator task = finishTasks.elementAt(i);
206 this.tasks.removeElement(task);
207 if(task instanceof TransTaskSimulator) {
208 TransTaskSimulator tmptask = (TransTaskSimulator)task;
209 // add ADDOBJ task to targetCore
210 int targetCoreNum = tmptask.getTargetCoreNum();
211 ObjectInfo objinfo = tmptask.refreshTask();
212 ObjectSimulator nobj = objinfo.obj;
213 FlagState fs = objinfo.fs;
214 int version = objinfo.version;
215 this.cores.elementAt(targetCoreNum).addObject(nobj, fs, version);
216 action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd());
217 cp.addAction(action);
218 if(!tmptask.isFinished()) {
219 // still have some objects to be transpotted
220 this.tasks.add(task);
222 if(this.cores.elementAt(targetCoreNum).getRtask() == null) {
223 TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process();
224 if(newTask != null) {
225 this.tasks.add(newTask);
226 // add a TASKSTART action into this checkpoint
227 action = new Action(targetCoreNum, Action.TASKSTART);
228 action.setTd(newTask.getTd());
229 cp.addAction(action);
233 CoreSimulator cs = task.getCs();
234 int coreNum = cs.getCoreNum();
235 if(task.getCurrentRun().getExetype() == 0) {
236 Hashtable<Integer, Queue<ObjectInfo>> transObjQueues = new Hashtable<Integer, Queue<ObjectInfo>>();
237 if(task.getCurrentRun().getNewObjs() == null) {
238 action = new Action(coreNum, Action.TASKFINISH);
239 action.setTd(cs.getRtask().getTd());
241 action = new Action(coreNum, Action.TFWITHOBJ);
242 action.setTd(cs.getRtask().getTd());
243 Vector<ObjectSimulator> nobjs = task.getCurrentRun().getNewObjs();
244 for(int j = 0; j < nobjs.size(); j++) {
245 ObjectSimulator nobj = nobjs.elementAt(j);
246 action.addNewObj(nobj.getCd(), Integer.valueOf(1));
247 // send the new object to target core according to pre-decide scheduling
248 Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
250 // this obj will reside on this core
253 Integer targetCore = cores.poll();
254 if(targetCore == coreNum) {
255 // this obj will reside on this core
258 if(!transObjQueues.containsKey(targetCore)) {
259 transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
261 Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
262 tmpqueue.add(new ObjectInfo(nobj));
265 // enqueue this core again
266 cores.add(targetCore);
269 // check if this object becoming shared or not
270 Vector<Integer> allycores = cs.getAllyCores(nobj.getCurrentFS());
271 if(allycores != null) {
272 nobj.setShared(true);
273 for(int k = 0; k < allycores.size(); ++k) {
274 Integer allyCore = allycores.elementAt(k);
275 if(allyCore == coreNum) {
278 if(!transObjQueues.containsKey(allyCore)) {
279 transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
281 Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
282 ObjectInfo nobjinfo = new ObjectInfo(nobj);
283 if(!tmpqueue.contains(nobjinfo)) {
284 tmpqueue.add(nobjinfo);
294 cp.addAction(action);
295 Vector<ObjectSimulator> transObjs = cs.finishTask();
296 if(transObjs != null) {
297 for(int j = 0; j < transObjs.size(); j++) {
298 ObjectSimulator tobj = transObjs.elementAt(j);
299 // send the object to target core according to pre-decide scheduling
300 Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
301 tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
303 // this obj will reside on this core
306 Integer targetCore = cores.peek();
307 if(targetCore == coreNum) {
308 // this obj will reside on this core
311 if(!transObjQueues.containsKey(targetCore)) {
312 transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
314 Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
315 tmpqueue.add(new ObjectInfo(tobj));
320 // check if this object becoming shared or not
321 Vector<Integer> allycores = cs.getAllyCores(tobj.getCurrentFS());
322 if(allycores != null) {
323 tobj.setShared(true);
324 for(int k = 0; k < allycores.size(); ++k) {
325 Integer allyCore = allycores.elementAt(k);
326 if(allyCore == coreNum) {
329 if(!transObjQueues.containsKey(allyCore)) {
330 transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
332 Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
333 ObjectInfo nobjinfo = new ObjectInfo(tobj);
334 if(!tmpqueue.contains(nobjinfo)) {
335 tmpqueue.add(nobjinfo);
345 // add 'transport' tasks
346 Iterator it_entries = transObjQueues.entrySet().iterator();
347 while(it_entries.hasNext()) {
348 Entry<Integer, Queue<ObjectInfo>> tmpentry = (Entry<Integer, Queue<ObjectInfo>>)it_entries.next();
349 Integer tmpCoreNum = tmpentry.getKey();
350 Queue<ObjectInfo> nobjs = tmpentry.getValue();
351 TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
352 this.tasks.add(tmptask);
356 transObjQueues = null;
357 } else if (task.getCurrentRun().getExetype() == 1) {
358 action = new Action(coreNum, Action.TASKABORT);
359 action.setTd(cs.getRtask().getTd());
360 cp.addAction(action);
361 Vector<ObjectSimulator> transObjs = cs.finishTask();
362 } else if (task.getCurrentRun().getExetype() == 2) {
363 action = new Action(coreNum, Action.TASKREMOVE);
364 action.setTd(cs.getRtask().getTd());
365 cp.addAction(action);
366 Vector<ObjectSimulator> transObjs = cs.finishTask();
368 // Choose a new task for this core
369 TaskSimulator newTask = cs.process();
370 if(newTask != null) {
371 this.tasks.add(newTask);
372 // add a TASKSTART action into this checkpoint
373 action = new Action(coreNum, Action.TASKSTART);
374 action.setTd(cs.getRtask().getTd());
375 cp.addAction(action);
379 this.checkpoints.add(cp);
383 SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime,
384 this.coreNum, this.checkpoints);
385 System.out.println("Simulate scheduling #" + this.invoketime + ": ");
386 System.out.println("\tTotal execution time is: " + this.processTime);
387 System.out.println("\tUtility of cores: ");
388 for(int j = 0; j < this.cores.size(); j++) {
389 System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
392 this.checkpoints.clear();
393 this.checkpoints = null;
394 return this.processTime;
397 public class CheckPoint {
398 private int timepoint;
399 private Vector<Action> actions;
401 public CheckPoint(int timepoint) {
403 this.timepoint = timepoint;
404 this.actions = new Vector<Action>();
407 public Vector<Action> getActions() {
411 public void addAction(Action action) {
412 this.actions.add(action);
415 public int getTimepoint() {
420 public class Action {
421 public static final int ADDOBJ = 0;
422 public static final int TASKFINISH = 1;
423 public static final int TFWITHOBJ = 2;
424 public static final int TASKSTART = 3;
425 public static final int TASKABORT = 4;
426 public static final int TASKREMOVE = 5;
430 private TaskDescriptor td;
431 private Hashtable<ClassDescriptor, Integer> nObjs;
433 private ClassDescriptor transObj;
435 public Action(int coreNum, int type) {
437 this.coreNum = coreNum;
440 if(this.type == TFWITHOBJ) {
441 this.nObjs = new Hashtable<ClassDescriptor, Integer>();
446 this.transObj = null;
449 public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
451 assert(type == ADDOBJ);
452 this.coreNum = coreNum;
455 this.nObjNum = objNum;
456 this.transObj = transObj;
459 public void addNewObj(ClassDescriptor cd, Integer num) {
460 assert(this.type == TFWITHOBJ);
462 if(this.nObjs.containsKey(cd)) {
463 Integer sum = this.nObjs.get(cd) + num;
464 this.nObjs.put(cd, sum);
466 this.nObjs.put(cd, num);
470 public int getCoreNum() {
474 public int getType() {
478 public int getNObjNum() {
482 public ClassDescriptor getTransObj() {
486 public TaskDescriptor getTd() {
490 public void setTd(TaskDescriptor td) {
494 public Hashtable<ClassDescriptor, Integer> getNObjs() {