Bug 562792: Add P-CP RTA (part 4)
Change-Id: Ie7f9224d99eeb6c5fff6e5e16d1eafd9ebbbca89
Signed-off-by: The Bao Bui <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
index 1b7f000..8fdefb8 100644
--- 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
@@ -690,132 +690,252 @@
return blockingTime;
}
/**
- * Calculation uses classic RTA + max(max_{j of type NP and in lp(i)} C_j; max_{k of type C and in lp(i)} c_k.
- * basically just add a blocking time
- * (choose the longest time, task A will be block by another task (B/C/D) depends on each's execution time
- * or each's runnable's execution time) among tasks within the same processor depend on each's preemption mode
+ * calculate task's response time when thisTask is preemptive/cooperative type and there exist non-preemp/cooperative task with lower priority
+ * finishing time = start time + execution time + preemption by higher priority task(s).
+ * Response time = finishing time - period, (using k-instance)
* @param thisTask
* @param ia
* @param executionCase
+ * @param pTypeArray - leave null if don't use
+ * @boolean usePtypeArray - true if use pType array, otherwise false
* @return
*/
- public Time getMixedPreempRTA(Task thisTask, int[] ia, TimeType executionCase) {
+ public Time getPreempCoopMixedTaskRTA(Task thisTask, int[] ia, TimeType executionCase, int[] pTypeArray, boolean usePtypeArray) {
//Adding decimal Format for better visual checking when debugging
//ie 6000000000 ps -> 6,000,000,000 ps
- DecimalFormat df = new DecimalFormat("#,###.##");
- EList<Task> listTask = this.model.getSwModel().getTasks();
- Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
- Time nonPreempBlockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
- Time coopBlockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
- Time taskClassicRTA = getResponseTimeViaRecurrenceRelation(thisTask, ia, executionCase);
+ Time responseTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+
+ //time that lp tasks may block thisTask in worst case response time
+ BigDecimal blockingTime = new BigDecimal(getLowerPriorityBlockingTime(thisTask, ia, executionCase, pTypeArray, usePtypeArray).getValue());
+
CPURta rtaia = new CPURta(this.model);
+ int[] thisIA = ia.clone();
+ List<Task> sortedTaskList = rtaia.taskSorting(groupTask(thisTask, thisIA));
- List<Task> sortedTaskList = rtaia.taskSorting(groupTask(thisTask, ia));
-
- //Reverse the order from highest -> lowest to the opposite lowest -> highest
- Collections.reverse(sortedTaskList);
- List<Task> npLowerPriorityTaskList = new ArrayList<>();
- List<Task> coopLowerPriorityTaskList = 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
- * lowest -> highest prio
- */
- 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) {
- npLowerPriorityTaskList.add(task);
- }
-
- //add task to the list if has lower priority and in cooperative (preempTypeValue = 2 )
- else if (!task.equals(thisTask) && preempTypeValue == 2) {
- coopLowerPriorityTaskList.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;
- }
+ /* Check ultilization value here, if ultiValue > 100% then ultiCheck = false*/
+ boolean ultiCheck = getUltilizationCheck(sortedTaskList, thisIA, executionCase);
+ if (!ultiCheck) {
+ //response time = 0 here, cuz the core would be damned if we use this set
+ return responseTime;
}
-
- /**
- * if there is no non-preemptive task with lower priority allocate to the processor
- */
- if (npLowerPriorityTaskList.isEmpty()) {
- //blockingTime = 0 initially
- result = result.add(nonPreempBlockingTime);
- log.debug(df.format(nonPreempBlockingTime.getValue()) + " ps - Non-preemptive blocking time, no blocking");
- }
-
- /**
- * if there is no cooperative task with lower priority in the same processor
- */
- if (coopLowerPriorityTaskList.isEmpty()) {
- //coop blocking time = 0
- result = result.add(coopBlockingTime);
- log.debug(df.format(coopBlockingTime.getValue()) + " ps - Cooperative blocking time, no blocking");
- }
+ int taskIndex = sortedTaskList.indexOf(thisTask);
+ Time iPeriodTime = CommonUtils.getStimInTime(thisTask);
+ BigInteger iPeriodInPs = AmaltheaServices.convertToPicoSeconds(iPeriodTime);
+ Time iExecutionTime = getExecutionTime(thisTask, thisIA, executionCase);
- /**
- * adding blocking time of lower priority task with non-preemptive mode and cooperative
- * Take the longer blocking time among the 2
- * Only block if there either/both task in our task lists (coop + np)
- */
- if (!npLowerPriorityTaskList.isEmpty() || !coopLowerPriorityTaskList.isEmpty()) {
- for (Task task : npLowerPriorityTaskList) {
- int taskIndex = listTask.indexOf(task);
- Time currentBlockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ /* ----- Get LEVEL - I for each task ------ */
+ BigDecimal lv0 = BigDecimal.ZERO;
+ BigDecimal currentLv = BigDecimal.ONE;
- /**
- * 1 task can only have either np or coop preemption mode anyway
- */
- if (this.preemptionTypeArray[taskIndex] == 1) {
- currentBlockingTime = getExecutionTime(task, ia, executionCase);
- }
- else if (this.preemptionTypeArray[taskIndex] == 2) {
- currentBlockingTime = getLongestRunnableExecutionTime(thisTask, ia, executionCase);
- }
+ BigDecimal iPeriod = new BigDecimal(iPeriodInPs);
+ BigDecimal iExe = new BigDecimal(iExecutionTime.getValue());
+ BigDecimal iResponseTime = BigDecimal.ZERO;
+ String taskName = thisTask.getName();
- /**
- * after the above we will have the time that [thisTask] is blocked by [task] potentially
- * We only need to loop through all task in [listTask] to find which [task] block [thisTask] the longest
- *
- */
-
- //Compare to find the longer one when iterate
- if (nonPreempBlockingTime.compareTo(currentBlockingTime) <= 0) {
- nonPreempBlockingTime = 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(nonPreempBlockingTime);
- log.debug(df.format(nonPreempBlockingTime.getValue()) + " ps - Final Non-preemptive/coop 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) {
+ /* If blocking time is equal/bigger than task period, then unschedulable for sure,
+ * just return 0 and warning, no need for further calculation*/
+ if (blockingTime.compareTo(iPeriod) >= 0 && schedubilityCheck) {
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));
+ log.error("Blocking time of task [{}] is bigger than its period, return 0 for RT ", taskName);
+ if (logError) {
+ String s1 = df.format(blockingTime);
+ String s2 = df.format(iPeriod);
+ log.error("{} > {} ", s1, s2);
+ }
//result is 0
- result.setValue(BigInteger.ZERO);
- return result;
+ return responseTime;
}
- log.debug(df.format(result.getValue()) + "ps - Task [" + thisTask.getName() + "] NP environment response time :");
- return result;
+ //sum of execution time of all tasks with higher prio not including this task (in TU Dortmund say included, they are imbecile )
+ BigDecimal hpCiSum = BigDecimal.ZERO;
+
+ int iterationCounterLvI = 0;
+ while (!currentLv.equals(lv0)) {
+ lv0 = currentLv;
+ //entry = each small sum of [Li/Tj]Cj, p_j >= p_i ( i = taskIndex)
+ BigDecimal iterationValue = BigDecimal.ZERO;
+
+ for (int entry = 0; entry < taskIndex + 1; entry++) {
+ Task entryTask = sortedTaskList.get(entry);
+ BigInteger entryPeriodInPs = AmaltheaServices.convertToPicoSeconds(CommonUtils.getStimInTime(entryTask));
+ BigDecimal entryPeriod = new BigDecimal(entryPeriodInPs);
+ BigDecimal entryExe = new BigDecimal(getExecutionTime(entryTask, thisIA, executionCase).getValue());
+
+ BigDecimal roundUp = currentLv.divide(entryPeriod, 0, RoundingMode.CEILING);
+ BigDecimal entryValue = roundUp.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ }
+ //First entry of level-i = Bi + Ci, the sum above doesn't exist (or maybe 1, not gonna risk it hence the code below)
+ //check non-premptive scheduler from TUDortmund pdf, google that shit
+ if (iterationCounterLvI == 0) {
+ iterationValue = iExe;
+ }
+ iterationCounterLvI++;
+ /* -- Add blocking if there is non-preemptive or cooperative in the set ----
+ * iteration = current lv + blocking*/
+ iterationValue = iterationValue.add(blockingTime);
+ currentLv = iterationValue;
+ }
+ if (logDebug) {
+ String lv0String = df.format(lv0);
+ log.debug("{} ps - level-i ", lv0String);
+ }
+ /* ----- Get K (total task iteration) ------ */
+ int bigK = lv0.divide(iPeriod, 0, RoundingMode.CEILING).intValue();
+
+ /* ----- Get start time for each task ------ */
+ /**
+ * Things get more complicated from here, we get preemption from higher prio, blocking from lower prio
+ * so we have to calculate the START TIMEEEE with blocking, my man
+ */
+ for (int smallK = 1; smallK <= bigK; smallK++) {
+ log.debug(" --- k instance : {}/{} --------------------------------------------", smallK, bigK);
+ BigDecimal kLv = BigDecimal.ZERO;
+ BigDecimal currentKLv = BigDecimal.ONE;
+ int smallK1 = smallK - 1;
+ BigDecimal kCi1 = iExe.multiply(BigDecimal.valueOf(smallK1));
+
+ //Equation from Tu Dortmund for this is wrong, it's < taskIndex, not < i.
+ for (int entry = 0; entry < taskIndex; entry++) {
+ Task entryTask = sortedTaskList.get(entry);
+ BigDecimal entryExe = new BigDecimal(getExecutionTime(entryTask, thisIA, executionCase).getValue());
+ hpCiSum = hpCiSum.add(entryExe);
+ }
+
+ int iterationCounterK = 0;
+
+ while (!kLv.equals(currentKLv)) {
+ currentKLv = kLv;
+ //entry = each small sum of [Li/Tj]Cj (rown down), j > i, not >=
+ BigDecimal iterationValue = BigDecimal.ZERO;
+ for (int entry = 0; entry < taskIndex; entry++) {
+ Task entryTask = sortedTaskList.get(entry);
+ BigInteger entryPeriodInPs = AmaltheaServices.convertToPicoSeconds(CommonUtils.getStimInTime(entryTask));
+ BigDecimal entryPeriod = new BigDecimal(entryPeriodInPs);
+ BigDecimal entryExe = new BigDecimal(getExecutionTime(entryTask, thisIA, executionCase).getValue());
+
+ BigDecimal roundDown = currentKLv.divide(entryPeriod, 0, RoundingMode.FLOOR);
+ BigDecimal roundDownPlusOne = roundDown.add(BigDecimal.ONE);
+ BigDecimal entryValue = roundDownPlusOne.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ }
+ kLv = iterationValue;
+ kLv = kLv.add(kCi1); //add k*Ci at the end of iteration
+
+ //first iteration = Bi + hpCiSum
+ if (iterationCounterK == 0) {
+ log.debug("hpCiSum - {} blocking {}", hpCiSum, blockingTime);
+ kLv = hpCiSum;
+ //reseti this for next k-task
+ hpCiSum = BigDecimal.ZERO;
+ }
+ log.debug("iterationValue + (k-1)*Ci + blockingtime (ignore if first iteration)");
+ log.debug("{} + {} + {}", iterationValue, kCi1, blockingTime);
+ kLv = kLv.add(blockingTime); // add blocking time here
+ log.debug("current iteration : {}", kLv);
+ iterationCounterK++;
+ }
+
+ /* ----- Get response time for each task (k) ------ */
+ BigDecimal taskStartTime = kLv;
+ BigDecimal taskStartPeriod = iPeriod.multiply(BigDecimal.valueOf(smallK1));
+ /*task finishing time in this case = startTime + Ci + hp_task's preemptive time */
+ BigDecimal taskFinishingTime;
+
+ BigDecimal kTaskFinishingTime = BigDecimal.ONE;
+ BigDecimal currentFinishingTime = BigDecimal.ZERO;
+
+ /* if task is not non-preemptive (coop-preemptive) then
+ * finishingTime = startTime + Ci + hp_task's preemptive time
+ * challenge here is to calculate the preemption from higher priority task*/
+ while (!kTaskFinishingTime.equals(currentFinishingTime)) {
+ currentFinishingTime = kTaskFinishingTime;
+ BigDecimal iterationValue = BigDecimal.ZERO;
+ /*this entry loop will return the preemption time from higher priority task*/
+ for (int entry = 0; entry < taskIndex; entry++) {
+ Task entryTask = sortedTaskList.get(entry);
+ BigInteger entryPeriodInPs = AmaltheaServices.convertToPicoSeconds(CommonUtils.getStimInTime(entryTask));
+ BigDecimal entryPeriod = new BigDecimal(entryPeriodInPs);
+ BigDecimal entryExe = new BigDecimal(getExecutionTime(entryTask, thisIA, executionCase).getValue());
+
+ //roundUp = [fi/tj]up
+ BigDecimal roundUp = currentFinishingTime.divide(entryPeriod, 0, RoundingMode.CEILING);
+
+ //roundDown = [si/tj]down
+ BigDecimal roundDown = kLv.divide(entryPeriod, 0, RoundingMode.FLOOR);
+ //roundDownPlusOne = [si/tj]down +1
+ BigDecimal roundDownPlusOne = roundDown.add(BigDecimal.ONE);
+
+ //bigSum =([fi/tj]up - ([si/tj]down + 1))
+ BigDecimal bigSum = roundUp.subtract(roundDownPlusOne);
+ //this is the preemption time from higher prio task
+ BigDecimal entryValue = bigSum.multiply(entryExe);
+
+ // iteration value = Sum of all entry (each hp task give 1 entry, sum all entry = preemption time, hence the for loop mate)
+ iterationValue = iterationValue.add(entryValue);
+ log.debug("([fi/tj]up - ([si/tj]down + 1)) : {} - {}", roundUp, roundDownPlusOne);
+ log.debug("Sum*Ci= {} = {} x {}", entryValue, bigSum, entryExe);
+ }
+ /*finishingTime = startTime + Ci + hp_task's preemptive time */
+ log.debug("Finishing time = s + Ci + preemp (Sum*Ci) : {} + {} + {}", kLv, iExe, iterationValue);
+ iterationValue = iterationValue.add(kLv).add(iExe);
+ kTaskFinishingTime = iterationValue;
+ }
+
+ //I can just use the kTaskFinishingTime for the calculation below but
+ //....well for the asthetic, taskfinishingTime sound more...in sync with the others
+ taskFinishingTime = kTaskFinishingTime;
+ if (logDebug) {
+ String s1 = df.format(taskStartTime);
+ String s2 = df.format(iExe);
+ String s3 = df.format(taskFinishingTime);
+ String s4 = df.format(taskStartPeriod);
+ log.debug("start time : {} + execution time: {} + finishing time: {}; period: {}", s1, s2, s3, s4);
+ }
+ BigDecimal taskResponseTime = taskFinishingTime.subtract(taskStartPeriod);
+ if (logDebug) {
+ String s1 = df.format(taskResponseTime);
+ log.debug("{} - this k instance response time ", s1);
+ }
+ //biggest value among all k-instance in our busy period would be the worse case response time
+ //but...best case? it is thisTask execution time :))
+ if (taskResponseTime.compareTo(iResponseTime) >= 0) {
+ iResponseTime = taskResponseTime;
+ }
+ if (logDebug) {
+ String s1 = df.format(iResponseTime);
+ log.debug("{} - biggest response time so far ", s1);
+ }
+ }
+ if (logInfo) {
+ String s1 = df.format(iResponseTime);
+ log.info("{} ps - Task [{}] level-i response time in mixed preemptive environment", s1, taskName);
+ }
+
+ //Check schedulability
+ if (iResponseTime.compareTo(iPeriod) > 0 && schedubilityCheck) {
+ log.error("!!! UNSCHEDULABLE !!!");
+ log.error("Response time of task [{}] is bigger than its period, return 0 for RT ", taskName);
+ if (logError) {
+ String s1 = df.format(iResponseTime);
+ String s2 = df.format(iPeriod);
+ log.error("{} > {} ", s1, s2);
+ }
+ //result is 0
+ return responseTime;
+ }
+ //Set response time value after all calculation above
+ responseTime.setValue(iResponseTime.toBigInteger());
+
+ return responseTime;
}
+
/**
* this function will get PURE execution time via calculate execution time of task's runnables
* @param thisTask
@@ -881,12 +1001,22 @@
BigDecimal division = numerator.divide(denominator, 9, RoundingMode.HALF_UP);
ultiValue = ultiValue.add(division);
}
- log.debug(ultiValue.multiply(BigDecimal.valueOf(100)) + " % - core ultilization Value ");
+ if (logDebug)
+ {
+ String s1 = ultiValue.multiply(BigDecimal.valueOf(100)).toString();
+ log.debug("{} % - core ultilization Value ", s1);
+ }
+
//if ultilization percentage > 100% then core exceed it maximum workable ability, should never happen
if (ultiValue.compareTo(BigDecimal.ONE) > 0) {
log.error("!!! UNSCHEDULABLE !!!");
- log.error("Ultilization value :" + ultiValue.multiply(BigDecimal.valueOf(100)) + " exceed 100% ");
+ if (logError)
+ {
+ String s1 = ultiValue.multiply(BigDecimal.valueOf(100)).toString();
+ log.error("Ultilization value :{} exceed 100% ",s1);
+ }
+
checkValue = false;
}