Bug 562791 - RTA for task in Non-preemptive and preemptive environment
Change-Id: I73d3969900ccf05e3c94def72c91be60dda559b3
Signed-off-by: Zero <zerovnb@gmail.com>
diff --git a/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/NPandPRTA.java b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/NPandPRTA.java
new file mode 100644
index 0000000..148c365
--- /dev/null
+++ b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/NPandPRTA.java
@@ -0,0 +1,313 @@
+package org.eclipse.app4mc.gsoc_rta;
+
+import java.math.BigDecimal;
+import java.math.BigInteger;
+import java.math.RoundingMode;
+import java.text.DecimalFormat;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.log4j.Logger;
+import org.eclipse.app4mc.amalthea.model.Amalthea;
+import org.eclipse.app4mc.amalthea.model.AmaltheaServices;
+import org.eclipse.app4mc.amalthea.model.ProcessingUnit;
+import org.eclipse.app4mc.amalthea.model.Runnable;
+import org.eclipse.app4mc.amalthea.model.Task;
+import org.eclipse.app4mc.amalthea.model.Time;
+import org.eclipse.app4mc.amalthea.model.TimeUnit;
+import org.eclipse.app4mc.amalthea.model.util.FactoryUtil;
+import org.eclipse.app4mc.amalthea.model.util.SoftwareUtil;
+import org.eclipse.app4mc.amalthea.model.util.RuntimeUtil.TimeType;
+import org.eclipse.emf.common.util.EList;
+
+public class NPandPRTA {
+ private final int[] ia;
+ private final Amalthea model;
+ private final int[] preemptionTypeArray;
+
+ /*
+ * PreemptionTypeArray will have the same length with mapping indexArray (ia), just with different value
+ * This will be set up when the class is initialize, the meaning of the number in array are:
+ * 0 = preemptive
+ * 1 = non-preemptive
+ * 2 = cooperative
+ *
+ * ia = { 5, 1, 5, 0, 1, 0, 2, 1, 2, 1, 6, 3, 4, 6 } - mapping array
+ * pta = { 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,} - the preemption type array
+ * this mean the first and second task of the model have non-preemption mode, the rest are preemptive
+ */
+ public NPandPRTA(final Amalthea modelp, final int[] iap) {
+ this.ia = iap;
+ this.model = modelp;
+ this.preemptionTypeArray = new int[iap.length];
+ setupPTArray();
+ }
+
+ /**
+ * Calculate classic RTA of task using this formula
+ * Ri = Ci + Sum j among HP(i)[Ri/Tj]*Cj
+ * https://www.it.uu.se/edu/course/homepage/realtid/ht10/schedule/Scheduling-periodic.pdf
+ * @param thisTask
+ * @param ia
+ * @return
+ */
+ public Time getClassicRTA(Task thisTask, int[] ia, final TimeType executionCase) {
+ //Adding decimal Format for better visual checking when debugging
+ //ie 6000000000 ps -> 6,000,000,000 ps
+ DecimalFormat df = new DecimalFormat("#,###.##");
+ final Logger log = Logger.getLogger(NPandPRTA.class);
+ Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ /*Initialize variable to compare previous and current iteration in the formula*/
+ BigDecimal temp = BigDecimal.valueOf(2.0);
+
+ CPURta rtaia = new CPURta(this.model);
+ List<Task> groupTaskList = groupTask(thisTask, ia);
+ List<Task> sortedTaskList = rtaia.taskSorting(groupTaskList);
+
+ int taskIndex = sortedTaskList.indexOf(thisTask);
+ //Loop through all task inside the list (until thisTask)
+ for (int i = 0; i < taskIndex + 1; i++) {
+ //Highest priority -> get executed first all the damn time
+ if (taskIndex == 0) {
+ log.debug(
+ df.format(getExecutionTime(thisTask, ia, executionCase).getValue()) + " ps - Task [" + thisTask.getName() + "] classic response time");
+ return getExecutionTime(thisTask, ia, executionCase);
+ }
+
+ //Calculate rta by looping until the result of the previous and current are the same
+ else if (i == taskIndex) {
+ BigDecimal rZero = BigDecimal.ZERO;
+ /*Set up r_0 for the calculation*/
+ for (int j = 0; j < i + 1; j++) {
+ Task jTask = sortedTaskList.get(j);
+ Time jTaskExecutionTime = getExecutionTime(jTask, ia, executionCase);
+ BigDecimal bigDecVal = new BigDecimal(jTaskExecutionTime.getValue());
+ rZero = rZero.add(bigDecVal);
+ }
+
+ BigDecimal currentVal = rZero;
+
+ //iterate until current value = previous value
+ while (!temp.equals(currentVal)) {
+ temp = currentVal;
+
+ /**
+ * The iteration loop of
+ * Ri = Ci + Sum j among HP(i)[Ri/Tj]*Cj
+ * k loop are the part after the Sum symbol, after the loop we add Ci
+ */
+ BigDecimal iteration = BigDecimal.ZERO;
+ for (int k = 0; k < i; k++) {
+ Task kTask = sortedTaskList.get(k);
+ Time kTaskExecutionTime = getExecutionTime(kTask, ia, executionCase);
+ Time kTaskPeriod = CommonUtils.getStimInTime(kTask);
+ //Need to change all time value to PS for calculation
+ BigInteger kTaskPeriodInPs = AmaltheaServices.convertToPicoSeconds(kTaskPeriod);
+
+ //execution time and period in bigDecimal
+ BigDecimal kTaskExetimeDec = new BigDecimal(kTaskExecutionTime.getValue());
+ BigDecimal kTaskPeriodDec = new BigDecimal(kTaskPeriodInPs);
+
+ // multiplyPart = [Ri/Tj] * Cj
+ // RiTj = roundupPart, Cj = kTaskExetimeDec
+ BigDecimal roundUpPart = currentVal.divide(kTaskPeriodDec, RoundingMode.CEILING);
+ BigDecimal multiplyPart = roundUpPart.multiply(kTaskExetimeDec);
+ iteration = iteration.add(multiplyPart);
+ }
+ //Adding Ci after the iteration
+ Task iTask = sortedTaskList.get(i);
+ BigDecimal iTaskExecutionTimeDec = new BigDecimal(getExecutionTime(iTask, ia, executionCase).getValue());
+ currentVal = iteration.add(iTaskExecutionTimeDec);
+ }
+ BigDecimal thisTaskPeriodInBigDec = new BigDecimal(AmaltheaServices.convertToPicoSeconds(CommonUtils.getStimInTime(thisTask)));
+ if (currentVal.compareTo(thisTaskPeriodInBigDec) > 0) {
+ log.error("!!! UNSCHEDULABLE !!!");
+ log.error("Response time of task [" + thisTask.getName() + "] is bigger than its period, return 0 for RT ");
+ log.error(df.format(currentVal) + " > " + df.format(thisTaskPeriodInBigDec));
+ //result is 0
+ return result;
+ }
+
+ log.debug(df.format(currentVal) + " ps - Task [" + thisTask.getName() + "] classic response time");
+ //result is currentVal calculated above
+ result.setValue(currentVal.toBigInteger());
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Calculation uses classic RTA + max(max_{j of type NP and in lp(i)} C_j}
+ * basically just add a blocking time (the longest execution time of tasks) among task within the same processor
+ * @param thisTask
+ * @param ia
+ * @param executionCase
+ * @return
+ */
+ public Time getNonPreemptaskRTA(Task thisTask, int[] ia, TimeType executionCase) {
+ //Adding decimal Format for better visual checking when debugging
+ //ie 6000000000 ps -> 6,000,000,000 ps
+ DecimalFormat df = new DecimalFormat("#,###.##");
+ final Logger log = Logger.getLogger(NPandPRTA.class);
+ EList<Task> listTask = this.model.getSwModel().getTasks();
+ Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ Time blockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ Time taskClassicRTA = getClassicRTA(thisTask, ia, executionCase);
+ CPURta rtaia = new CPURta(this.model);
+ List<Task> sortedTaskList = rtaia.taskSorting(groupTask(thisTask, ia));
+
+ //Reverse the order from highest -> lowest to the opposite lowest -> highest
+ Collections.reverse(sortedTaskList);
+ List<Task> lowerPriorityTaskList = new ArrayList<>();
+
+ /*Loop through all the task in the sorted Task list and add them to lowerPriorityTaskList until we see thisTask
+ * I have reversed the order of the task list above so we will capture all task with lower priority via top down iteration
+ */
+ for (Task task : sortedTaskList) {
+ int taskIndex = listTask.indexOf(task);
+ int preempTypeValue = this.preemptionTypeArray[taskIndex];
+ //add task to our list if it has lower priority and is non-preemptive (preempTypeValue = 1 )
+ if (!task.equals(thisTask) && preempTypeValue == 1) {
+ lowerPriorityTaskList.add(task);
+ }
+ //Get out of the loop when we met thisTask in the sorted task list
+ //Without this, lowerPriorityTaskList may add the task with higher priority
+ else if (task.equals(thisTask)) {
+ break;
+ }
+ }
+
+
+ /**
+ * if there is no non-preemptive task with lower priority allocate to the processor
+ */
+ if (lowerPriorityTaskList.isEmpty()) {
+ //blockingTime = 0 initially
+ result = result.add(blockingTime);
+ log.debug(df.format(blockingTime.getValue()) + " - Non-preemptive blocking time, no blocking");
+ }
+ /**
+ * adding blocking time of lower priority task with non-preemptive mode (take the longest among our list)
+ */
+ else {
+ for (Task task : lowerPriorityTaskList) {
+ Time currentBlockingTime = getExecutionTime(task, ia, executionCase);
+ //Compare to find the longer one when iterate
+ if (blockingTime.compareTo(currentBlockingTime) <= 0) {
+ blockingTime = currentBlockingTime;
+ }
+ log.debug(df.format(currentBlockingTime.getValue()) + " ps - Lower priority task [" + task.getName() + "] blockingTime");
+ }
+ //add blocking time when we have find the maximum execution time among
+ result = result.add(blockingTime);
+ log.debug(df.format(blockingTime.getValue()) + " ps - Final Non-preemptive blocking time: ");
+ }
+ //final result should be RTA = blockingTime + classicRTA(task)
+ result = result.add(taskClassicRTA);
+
+ BigDecimal thisTaskPeriodInBigDec = new BigDecimal(AmaltheaServices.convertToPicoSeconds(CommonUtils.getStimInTime(thisTask)));
+ if (result.getValue().compareTo(thisTaskPeriodInBigDec.toBigInteger()) > 0) {
+ log.error("!!! UNSCHEDULABLE !!!");
+ log.error("Response time of task [" + thisTask.getName() + "] is bigger than its period, return 0 for RT ");
+ log.error(df.format(result.getValue()) + " > " + df.format(thisTaskPeriodInBigDec));
+ //result is 0
+ result.setValue(BigInteger.ZERO);
+ return result;
+ }
+ log.debug(df.format(result.getValue()) + "ps - Task [" + thisTask.getName() + "] NP environment response time :");
+
+ return result;
+ }
+
+
+ /**
+ * this function will get PURE execution time via calculate execution time of task's runnables
+ * @param thisTask
+ * @param ia
+ * @return
+ */
+ public Time getPureExecutionTime(Task thisTask, int[] ia, final TimeType executionCase) {
+ Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ final int currentIndex = this.model.getSwModel().getTasks().indexOf(thisTask); //get index of the task in the array
+ final int PUI = ia[currentIndex]; // get the index of processing unit
+ final List<ProcessingUnit> pul = CommonUtils.getPUs(this.model);
+ final ProcessingUnit pu = pul.get(PUI);
+ RTARuntimeUtil rtautil = new RTARuntimeUtil();
+
+ /* The list of runnables of the given task */
+ final List<Runnable> runnableList = SoftwareUtil.getRunnableList(thisTask, null);
+
+ /*Add all execution time of runnable inside thisTask to get its PURE execution time*/
+ for (Runnable r : runnableList) {
+ Time runnableExecutionTime = rtautil.getExecutionTimeForRTARunnable(r, pu, executionCase);
+ result = result.add(runnableExecutionTime);
+ }
+ return result;
+ }
+
+ /**May sound stupid in the beginning but this will make things easier to control when
+ * Adding blocking/contention at the end of the function.
+ * @param thisTask
+ * @param ia
+ * @param executionCase
+ * @return
+ */
+ private Time getExecutionTime(Task thisTask, int[] ia, final TimeType executionCase) {
+ Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+
+ result = result.add(getPureExecutionTime(thisTask, ia, executionCase));
+ /**
+ * Add other blocking/waiting method here if needed.
+ */
+ return result;
+ }
+
+ /**
+ * Initialize preemptive array.
+ */
+
+ private void setupPTArray() {
+ final Logger log = Logger.getLogger(NPandPRTA.class);
+ log.debug("Initialize class NPandPRTA");
+ EList<Task> listTask = this.model.getSwModel().getTasks();
+ for (Task task : listTask) {
+ int taskIndex = listTask.indexOf(task);
+ String preemp = task.getPreemption().getLiteral();
+ if (preemp.matches("preemptive")) {
+ this.preemptionTypeArray[taskIndex] = 0;
+ }
+ else if (preemp.matches("non_preemptive")) {
+ this.preemptionTypeArray[taskIndex] = 1;
+ }
+ else if (preemp.matches("cooperative")) {
+ this.preemptionTypeArray[taskIndex] = 2;
+ }
+ }
+
+ log.debug(Arrays.toString(this.ia) + " - ia");
+ log.debug(Arrays.toString(this.preemptionTypeArray) + " - pta");
+
+ }
+
+ private List<Task> groupTask(final Task thisTask, int[] ia) {
+ final List<Task> stepOneTaskList = new ArrayList<>();
+ final EList<Task> taskList = this.model.getSwModel().getTasks();
+ final int currentIndex = this.model.getSwModel().getTasks().indexOf(thisTask);
+
+ CPURta rtaia = new CPURta(this.model);
+ final int PUI = ia[currentIndex];
+ for (int i = 0; i < ia.length; i++) {
+ if (PUI == ia[i]) {
+ stepOneTaskList.add(taskList.get(i));
+ }
+ }
+
+ return rtaia.taskSorting(stepOneTaskList);
+
+ }
+
+
+
+}
diff --git a/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/RTARuntimeUtil.java b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/RTARuntimeUtil.java
index 71a96a7..cc56c17 100644
--- a/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/RTARuntimeUtil.java
+++ b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/RTARuntimeUtil.java
@@ -335,7 +335,7 @@
* @return
* execution time of the observed runnable
*/
- private Time getExecutionTimeForRTARunnable(final Runnable runnable, final ProcessingUnit pu, final TimeType executionCase) {
+ protected Time getExecutionTimeForRTARunnable(final Runnable runnable, final ProcessingUnit pu, final TimeType executionCase) {
log.debug(executionCase.toString());
Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
final double freq = AmaltheaServices.convertToHertz(pu.getFrequencyDomain().getDefaultValue()).longValue();