Add numerical example for NPandPRTA. Update readme
Change-Id: I26278f62a985beccaebc5eaec0c61ac099e92e4d
Signed-off-by: The Bao Bui <ZeroVNB@Gmail.com>
diff --git a/eclipse-tools/responseTime-analyzer/README.md b/eclipse-tools/responseTime-analyzer/README.md
index ed9886f..febb611 100644
--- a/eclipse-tools/responseTime-analyzer/README.md
+++ b/eclipse-tools/responseTime-analyzer/README.md
@@ -1,90 +1,100 @@
# GSOC_RTA
-2019 Google Summer of Code (CPU-GPU Response Time and Mapping Analysis)
+2020 Google Summer of Code (Non-Preemptive / Limited preemptive in Response Time Analysis)
+
+[Readthedocs](https://gsoc2020doc.readthedocs.io/en/latest/)
## [Table of Contents]
### 1. Milestone with the goal of each phase
-### 2. Intention
-### 3. Contribution & benefits for the community
-### 4. Contents
-### 5. Diagram Example
-### 6. Instruction
-### 7. Remarks
-### 8. Updates (Phase 2: June/24 ~ July/21)
+### 2. Intention & contribution to the open source community
+### 3. Contents
+### 4. Instruction
+
# 1. Milestone with the goal of each phase
-- Response Time Analysis_CPU Part (Phase 1)
-- **Refine Previous Phase & E2E Latency Foundation (EC, IC, LET) (Phase 2: June/24 ~ July/21)**
-- Finalize LET, EC, IC and the corresponding UI part (Phase 3)
+- Response Time Analysis for non-preemptive environment (Phase 1)
+- Response Time Analysis for limited-preemptive environment (Phase 2)
+- Blocking analysis for non-preemptive and limited-preemptive environment (Phase 3)
-# 2. Intention
-The current APP4MC library does provide several methods which are useful for deriving execution time for a task, a runnable or ticks (pure computation) through the Util package. But methods for response time are still not available. The reason is that response time analysis can be varied depending on the analyzed model so it is hard to be generalized. But since the trends are evolving from homogeneous to heterogeneous platform, the analysis methodology have become much more sophisticated so it is necessary to have CPU response time analysis which can be used for different mapping analysis with a different processing unit type (e.g., GPU).
+# 2. Intention & contribution to the open source community
+There are several paper about response time analysis but not many open source code that developer can use as reference or implementation can be found in the internet.
+This project is my contribution to the open source community in this matter.
+In this project, you can find method to calculate response time in different preemptive environment: non-preemptive, cooperative, or a mixed of the above.
-# 3. Contribution & benefits for the community
-In this project, [a standardized response time analysis methodology](https://www.semanticscholar.org/paper/Finding-Response-Times-in-a-Real-Time-System-Joseph-Pandya/574517d6e47cf9b368003a56088651a1941dcda1)(Mathai Joseph and Paritosh Pandya, 1986) which involves a complex algorithm is used. Not only this, but also a class, `CpuRTA` which is designed for Generic Algorithm Mapping is provided. Since a heterogeneous platfrom usually requires a different analysis methodology for a processing unit according to its type(e.g., CPU & GPU), a class that can be used with GA Mapping and has a built-in general analysis methodology would be very helpful and save a lot of time which otherwise would be spent for implementing the same algorithm for those tasks that are mapped to a particular type of processing units (e.g., CPU). Along with these, another class, `RuntimeUtilRTA` which supports `CpuRTA` class provides several ways to calculate execution time of a task is also provided. The execution time calculation methodology can be different depending on an execution case (e.g., Worst Case, Best Case, Average Case), a transmission type (e.g., Synchronous, Asynchronous) or a different mapping model. This class can be modified and reused for other analysis models if only a method which takes care of a Runnable execution time is adjusted.
+# 3. Contents and how to use
+My utlimate target is to implement response time analysis in a mixed environemnt, where task can be surrounded by different tasks with different preemptive type, from preemptive, cooperative to non-preemptive.
-# 4. Contents
-Since the target of implementing heterogeneous platform is to achieve better performance and efficiency, just simply calculating response time is not enough. To realize the optimized response time analysis, different mapping analysis for the same given model according to Generic Algorithm should be taken into account. Generic Algorithm would map tasks to different processing units in the form of integer array so that the total sum of each task’s response time according to the each GA generation can be delivered and compared each other to come up with a better solution. For this reason, a public method which returns the total sum of each task’s response time and the relevant private methods that are used to support this method are needed. The corresponding methods are followed below.
-**Refer to javadoc below for more details.**
-* [CpuRTA](Add Ref here)
-* [TimeCompIA](Add Ref here)
-* [RuntimeUtilRTA](Add Ref here)
-* [RTApp](Add Ref here)
-
-<`CpuRTA.java`>
-**getCPUResponseTimeSum**
-Calculate the total sum of response times of the tasks of the given Amalthea model with a GA mapping model
-**getTaskCPURT**
-Calculate response time of the given task of the given Amalthea model with a GA mapping model
-**taskSorting**
-Sort out the given list of tasks (in order of shorter period first - Rate Monotonic Scheduling)
-**preciseTestCPURT** (Response Time analysis Equation Explanation)
-Calculate response time of the observed task according to the periodic tasks response time analysis algorithm.
-> Ri = Ci + Σj ∈ HP(i) [Ri/Tj]*Cj ([a standardized response time analysis methodology](https://www.semanticscholar.org/paper/Finding-Response-Times-in-a-Real-Time-System-Joseph-Pandya/574517d6e47cf9b368003a56088651a1941dcda1)(Mathai Joseph and Paritosh Pandya, 1986))
-
-<`RuntimeUtilRTA.java`>
-**getExecutionTimeforCPUTask**
-Calculate execution time of the given task under one of the several configurations.
-**doesThisTaskTriggerCPUTask**
-Find out whether the given triggering task(that has an InterProcessTrigger) triggers a GPU task which is newly mapped to CPU.
-**syncTypeOperation**
-Calculate execution time of the given runnableList in a synchronous manner.
-**asyncTypeOperation**
-Calculate execution time of the given runnableList in an asynchronous manner.
-**getExecutionTimeForGPUTaskOnCPU**
-Calculate execution time of the given task which was originally designed for GPU but newly mapped to CPU by Generic Algorithm Mapping.
-**getExecutionTimeForRTARunnable**
-Calculate execution time of the given runnable.
-**getTaskMemoryAccessTime**
-Calculate memory access time of the observed task.
-**getRunnableMemoryAccessTime**
-Calculate memory access time of the observed runnable.
-> (Explanation)
-> Read(Write)_Access_Time = Round_UP(Size_of_Read_Labels / 64.0 Bytes) * (Read_Latency / Frequency)
-**isTriggeringTask**
-Identify whether the given task has an InterProcessTrigger or not.
-
-<`RTApp.java`>
-User Interface Window
-[APP4RTA_1.0_Description](Add Ref here)('responseTime-analyzer'>'plugins'>'doc'>'APP4RTA_1.0_Description.pdf')
-
-# 5. Diagram Example
-('responseTime-analyzer'>'plugins'>'doc')
-
-# 6. Instruction
-1. Under 'responseTime-analyzer'>'plugins'>'src'>...>'gsoc_rta' folder, there is 'CpuRTA' class. This is the implementation source file. By running them, one can derive the total sum of response times of the given model.
-2. Under 'responseTime-analyzer'>'plugins'>'src'>...>'gsoc_rta'>'ui' folder, there is 'RTApp_WATERS19' class. This is Java Swing UI source file that corresponds to the 'CpuRTA'. This UI is created based on WATERS19 Project. By running this, one may get more detailed visuals of the result of 'CpuRTA' class.
- (Refer to 'APP4RTA_1.0_Description.pdf' for more details.)('responseTime-analyzer'>'plugins'>'doc'>'APP4RTA_1.0_Description.pdf')
-
-# 7. Remarks
-1. 'GPU Task on CPU' part has not been implemented yet, so when T10 – T13 Tasks are mapped to CPU, the result would be not accurate for now.
- => Done.
-
-# 8. Updates (Phase 2: June/24 ~ July/21)
-### July/16
-
-<`CpuRTA`>
-- In the previous phase, the CPU response time analysis had been done without considering the situation where GPU Tasks are mapped to CPU by the new integer array generation. This was rather inaccurate since a GPU Task contains offloading runnables which are used to copy-in and copy-out the local memory when it is mapped to GPU. Not only should these runnables be omitted, but also the labels from the triggering task should be taken into account for the GPU task that is newly mapped to CPU to access the specified memory. Therefore, a function "setGTCL(final Amalthea model)" that takes needed labels and save to a hashMap for each GPU Task has been made.
-
-<`RuntimeUtilRTA`>
-- getExecutionTimeForGPUTaskOnCPU method which only considers a GPU original task's associated labels and ticks but ignores its offloading runnables.
\ No newline at end of file
+My implementation are located in `NPandPRta` class.
+Which include several response time analysis methods.
+**Refer to each methods' javadoc for more info, I will only mention here the most important/useful function go to my [readthedoc](https://gsoc2020doc.readthedocs.io/en/latest/) if you want a full documentation**
+
+
+<`NPandPRta.java`>
+
+There is something need to be mentioned before you try, this class is created based on WATERS2019 model, the functions are tested using that model.
+But you should be able to ultilize this class without many problem as long as you provided 3 input parameters:
+* Amalthea model - The model that you will use to ultilize this method, this should be given when you create the class object
+* Integer array (ia) - This is a representation of how task is allocated to cores, the location of each element represent task, and the value represent core. I.e. {0,2,3,1,1,2} : first task is assigned to first core of the model, 2nd task is assigned to 3rd core, 3rd task is assigned to 4th core and so on
+* Task - the task you want to calculate its response time
+
+Also additionally there are 3 other parameters:
+* executionCase : TimeType.WCET - just put this like this, since you would want to calculate worst case response time most of the time, change to BCET if you want something different.
+* pTypeArray: a customized array that you can use to define tasks' preemption type.
+Leave null if don't use.
+Check javadoc for more info.
+* usePtypeArray: boolean variable to announce whether you want to use pTypeArray or not.
+Leave false if don't use.
+
+Below are the important functions that you will probably use most of the time.
+For the list of all function, refer to the javadoc, [readthedoc](https://gsoc2020doc.readthedocs.io/en/latest/) or open the class, I left lots of comment their
+
+**getRTAinMixedPreemptiveEnvironment**
+Calculate response time of task in mixed environment.
+Drop the task, the integer mapping array, and the model (again this class is made mainly for WATERS2019 derived model, but it should work on other as well) and you get your response time.
+I also opt in an option where you can input your own preemptive type array.
+Where you can change task's preemptive type without changing it in the model.
+**setSchedubilityCheck**
+This function set a boolean variable where you can enable/disable schedubility check.
+Which means if you set to false. Every RTA functions will return the value without checking whether that response time bigger than task's period or not.
+**getResponseTimeViaLevelI**
+Calculate resposne time of task in preemptive environment via level-i busy window technique.
+Pretty vanilla/basic implementation.
+**getResponseTimeViaRecurrenceRelation**
+Calculate resposne time of task in preemptive environment via recurrence relation.
+Again very basic execution of how response time is calculated
+Should give the same result as response time level-i.
+**getPureExecutionTime**
+Using the well-known semantics, where task is run as follow: READ -> EXECUTION -> WRITE
+Calculate all of the element from each step, sum all of them and we have task's execution time.
+
+<`Blocking.java`>
+
+Blocking analysis, calculate blocking time of semaphore(critical section) when they are exist, or else calculate time other tasks have to wait due to global resource occupancy (task had to wait because other task is reading/writing label) )
+Same as the `NPandPRta.java`, this class also created based on WATER 2019 model.
+
+Again I only listed important/useful function. For more info, please refer functions' javadoc and [readthedoc](https://gsoc2020doc.readthedocs.io/en/latest/)
+
+**getGlobalBlockingTime**
+Calculate task's global blocking time ( time blocked by task from other cores) due to semaphore lock.
+If there is no semaphore, the function will calculate blocking time due to resource being read/write by other task.
+The blocking policy is Priority Ceiling Protocol FYI
+**getLocalBlockingTime**
+Same with getGlobalBlockingTime, but this time we calculate blocking time due to local task (task within same core)
+
+
+# 4. Instruction
+First of all, you will need to pull the big repo.
+
+https://git.eclipse.org/c/app4mc/org.eclipse.app4mc.tools.git/
+
+Check out the app4mc0.9.8/gsoc20npRTA.
+This is the branch that have my implementation
+
+1. Under responseTime-analyzer > plugins > src >...> gsoc_rta folder
+You will find `NPandPRta` class. This is the implementation source file. One can calculate task's response time in different environment using this.
+
+2. Under responseTime-analyzer > plugins > src >...> gsoc_rta >'test' folder, there is `NPandPNumerical` class.
+This is a numerical example on how functions/equations used in 'NPandPRta' work.
+
+3. Under responseTime-analyzer > plugins > src >...> gsoc_rta folder
+`Blocking` is also located here, using this will allow you to calculate local and global blocking time of task
diff --git a/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/test/NPandPRTANumerical.java b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/test/NPandPRTANumerical.java
new file mode 100644
index 0000000..509c74b
--- /dev/null
+++ b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/test/NPandPRTANumerical.java
@@ -0,0 +1,625 @@
+package org.eclipse.app4mc.gsoc_rta.test;
+
+import java.math.BigDecimal;
+import java.math.RoundingMode;
+import java.text.DecimalFormat;
+
+import org.apache.log4j.Level;
+import org.apache.log4j.Logger;
+/**
+ * This class is a numerical example of NPandPRTA functions, used to trace/debug the data flow and understand how each equations work.
+ * Include: recurrence rta, level-i rta, level-i non preempt, level-i cooperative.
+ * Hope this will help everybody understand better on how level-i busy window technique work in response time analysis.
+ * @author The Bao Bui (Zero)
+ */
+public class NPandPRTANumerical {
+
+ public static void main(final String[] args) {
+ org.apache.log4j.BasicConfigurator.configure();
+ Logger.getRootLogger().setLevel(Level.DEBUG);
+
+ //Just uncomment the class you want to run, but remember to edit input value if you have others input values.
+ //All of the equation used in this class can be found in my documentation (readthedocs)
+ final NPandPRTANumerical test = new NPandPRTANumerical();
+ // test.levelI();
+ // test.classicRTA();
+ // test.levelIforNonPreemptive();
+ // test.levelIforMixedNPandP();
+ test.levelIforCooperative();
+ }
+
+ private static long roundUp(final long num, final long divisor) {
+ return (num + divisor - 1) / divisor;
+ }
+
+ /**
+ * This function is a numerical example of how recurrence response time analysis work.
+ * It's the implementation of equation 1, if you don't know where is equation 1, it's in my readthedocs.
+ * To understand how equation work, just put a debug pointer in the function and trace the data flow
+ *
+ * Credit:
+ * The input number are derived from the paper "Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines" by Lehoczky (1990)
+ * I just use the number for confirmation.
+ */
+
+ private void recurrenceRTA() {
+ System.out.println("Testing classicRTA here");
+ //Exe = excution time, p = period
+ final int[] exe = { 20, 20, 35 };
+ final int[] p = { 70, 80, 200 };
+
+ //r0 and temp is just variable to spot whether the iteration has come to an end or not.
+ //Iteration ended when previous and current iteration value is the same.
+ int r0 = 0;
+ int temp = 1;
+
+ //Iterate from the highest priority task to the lowest. Task is already ordered.
+ //Calculate response time of all task
+ for (int i = 0; i < exe.length; i++) {
+ r0 = 0;
+ final int taskNo = i + 1;
+ System.out.println("Task number " + taskNo);
+
+ //getting r0.
+
+ for (int j = 0; j < i + 1; j++) {
+ r0 = r0 + exe[j];
+ }
+
+ System.out.println("r0 = " + r0);
+ int current = r0;
+
+ //Iteration loop for each task, response time will be found when this is ended.
+ while (temp != current) {
+ temp = current;
+
+ //Because there will be lots of \frac {R_{i-1}^+} {T_j} if we have several higher priority task, hence the iteration value
+ //Iteration value here is the big sum of all \frac {R_{i-1}^+} {T_j}
+ int iteration = 0;
+ //Sum all \frac {R_{i-1}^+} {T_j}
+ for (int k = 0; k < i; k++) {
+ //This is
+ final long num = roundUp(current, p[k]);
+ final long div = exe[k];
+ iteration = iteration + (int) (num * div);
+ }
+ current = iteration + exe[i];
+ }
+ }
+ }
+
+ /**
+ * calculate level-i busy period. Preemptive
+ *
+ * Credit:
+ * The input number are derived from the paper "Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines" by Lehoczky (1990)
+ * I just use the number for confirmation.
+ */
+ private void levelI() {
+ final Logger log = Logger.getLogger(this.getClass().getName());
+ final DecimalFormat df = new DecimalFormat("#,###.##");
+
+ //Exe = excution time, p = period
+
+ // final int[] exe = { 20, 20, 35 };
+ // final int[] p = { 70, 80, 200 };
+ //
+ final int[] exe = { 20, 50, 60, 80 };
+ final int[] p = { 100, 180, 250, 300 };
+
+ for (int i = 0; i < exe.length; i++) {
+ log.debug("for task " + i);
+ /* ----- Get LEVEL - I for each task ------ */
+ BigDecimal lv0 = BigDecimal.ZERO;
+ BigDecimal currentLv = BigDecimal.ONE;
+
+ final BigDecimal iPeriod = BigDecimal.valueOf(p[i]);
+ final BigDecimal iExe = BigDecimal.valueOf(exe[i]);
+ BigDecimal iResponseTime = BigDecimal.ZERO;
+ while (!currentLv.equals(lv0)) {
+ lv0 = currentLv;
+ //entry = each small sum of [Li/Tj]Cj, p_j >= p_i
+ BigDecimal iterationValue = BigDecimal.ZERO;
+ for (int entry = 0; entry < i + 1; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ final BigDecimal roundUp = currentLv.divide(entryPeriod, RoundingMode.CEILING);
+ final BigDecimal entryValue = roundUp.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ }
+ /* -- Add blocking for nonpreemptive here-- current lv plus blocking*/
+ currentLv = iterationValue;
+
+ }
+ log.debug("level-" + i + ": " + lv0);
+
+ /* ----- Get K (total task iteration) ------ */
+ final int bigK = lv0.divide(iPeriod, RoundingMode.CEILING).intValue();
+
+ /* ----- Get finishing time for each task ------ */
+ for (int smallK = 1; smallK <= bigK; smallK++) {
+ log.debug(" --- k instance : " + smallK + "/" + bigK + " --------------------------------------------");
+
+ BigDecimal kLv = BigDecimal.ZERO;
+ BigDecimal currentKLv = BigDecimal.ONE;
+ final BigDecimal kCi = iExe.multiply(BigDecimal.valueOf(smallK));
+ int counter = 0;
+
+ while (!kLv.equals(currentKLv)) {
+ currentKLv = kLv;
+ //entry = each small sum of [Li/Tj]Cj, j > i, not >=
+ BigDecimal iterationValue = BigDecimal.ZERO;
+ for (int entry = 0; entry < i; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ final BigDecimal roundUp = currentKLv.divide(entryPeriod, RoundingMode.CEILING);
+ final BigDecimal entryValue = roundUp.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ if (counter == 0) {
+ iterationValue = BigDecimal.ZERO;
+ counter++;
+ break;
+ }
+ }
+ kLv = iterationValue;
+ kLv = kLv.add(kCi); //add k*Ci at the end of iteration
+ }
+ /* ----- Get response time for each task (k) ------ */
+ final BigDecimal taskStartTime = iPeriod.multiply(BigDecimal.valueOf(smallK - 1));
+ log.debug("start time " + df.format(taskStartTime) + " - finishing time " + df.format(kLv));
+ final BigDecimal taskResponseTime = kLv.subtract(taskStartTime);
+ if (taskResponseTime.compareTo(iResponseTime) >= 0) {
+ iResponseTime = taskResponseTime;
+ }
+ log.info(df.format(iResponseTime) + " current RT ");
+ }
+ log.info(df.format(iResponseTime) + " - responseTime of task ");
+ System.out.println();
+ }
+
+ }
+
+ /**
+ * calculate level-i busy period for non-preemptive type
+ * add Blocking time = max blocking time from lower priority taskssssss
+ */
+ private void levelIforNonPreemptive() {
+ final Logger log = Logger.getLogger(this.getClass().getName());
+ final DecimalFormat df = new DecimalFormat("#,###.##");
+ log.debug("level-i for non-preemptive here");
+
+ final int[] exe = { 20, 20, 35 };
+ final int[] p = { 70, 80, 200 };
+ //rt = 55 - 75 - 75,
+
+ for (int i = 0; i < exe.length; i++) {
+ BigDecimal blockingTime = BigDecimal.valueOf(35);
+ if (i == 2) {
+ blockingTime = BigDecimal.ZERO;
+ }
+ log.debug("for task " + i);
+ /* ----- Get LEVEL - I for each task ------ */
+ BigDecimal lv0 = BigDecimal.ZERO;
+ BigDecimal currentLv = BigDecimal.ONE;
+
+ final BigDecimal iPeriod = BigDecimal.valueOf(p[i]);
+ final BigDecimal iExe = BigDecimal.valueOf(exe[i]);
+ BigDecimal iResponseTime = BigDecimal.ZERO;
+ //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 < i + 1; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ final BigDecimal roundUp = currentLv.divide(entryPeriod, RoundingMode.CEILING);
+ final BigDecimal entryValue = roundUp.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ }
+ //First entry of level-i = Bi + Ci, the sum above doesn't exist
+ //check non-premptive scheduler from TUDortmund pdf, google that shit
+ if (iterationCounterLvI == 0) {
+ iterationValue = iExe;
+ }
+ iterationCounterLvI++;
+ /* -- Add blocking for nonpreemptive here-- current lv plus blocking*/
+ iterationValue = iterationValue.add(blockingTime);
+ currentLv = iterationValue;
+ }
+ log.debug("level-" + i + ": " + lv0);
+
+ /* ----- Get K (total task iteration) ------ */
+ final int bigK = lv0.divide(iPeriod, RoundingMode.CEILING).intValue();
+
+ /**
+ * 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;
+ final int smallK1 = smallK - 1;
+ final BigDecimal kCi1 = iExe.multiply(BigDecimal.valueOf(smallK1));
+
+ //Equation from Tu Dortmund for this is wrong, it's <i, not <=i.
+ for (int entry = 0; entry < i; entry++) {
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+ 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 < i; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ final BigDecimal roundDown = currentKLv.divide(entryPeriod, RoundingMode.FLOOR);
+ final BigDecimal roundDownPlusOne = roundDown.add(BigDecimal.ONE);
+ final BigDecimal entryValue = roundDownPlusOne.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ }
+ kLv = iterationValue;
+ log.debug(kLv + " + " + kCi1 + " + " + blockingTime);
+
+ kLv = kLv.add(kCi1); //add k*Ci at the end of iteration
+ //first iteration = Bi + hpCiSum
+ if (iterationCounterK == 0) {
+ log.debug("hpCiSum - " + hpCiSum + " blocking " + blockingTime);
+ kLv = hpCiSum;
+ //reseti this for next task
+ hpCiSum = BigDecimal.ZERO;
+ }
+
+ kLv = kLv.add(blockingTime); // add blocking time here
+ log.debug(kLv);
+ iterationCounterK++;
+ }
+ /* ----- Get response time for each task (k) ------ */
+ final BigDecimal taskStartTime = kLv;
+ final BigDecimal taskFinishingTime = taskStartTime.add(iExe);
+ final BigDecimal taskStartPeriod = iPeriod.multiply(BigDecimal.valueOf(smallK1));
+
+ log.debug("start time " + df.format(taskStartTime) + " - finishing time " + df.format(taskFinishingTime) + " - period "
+ + df.format(taskStartPeriod));
+
+ final BigDecimal taskResponseTime = taskFinishingTime.subtract(taskStartPeriod);
+ if (taskResponseTime.compareTo(iResponseTime) >= 0) {
+ iResponseTime = taskResponseTime;
+ }
+ log.info(df.format(iResponseTime) + " current RT ");
+ }
+ log.info(df.format(iResponseTime) + " - responseTime of task ");
+ System.out.println();
+ /* ----- Get finishing time for each task ------ */
+
+ }
+
+
+ }
+
+ /*
+ * calculate level-i busy period for mixed preemptive with non-preemptive type
+ * add Blocking time = max blocking time from lower priority taskssssss to level-i for the busy window
+ * add inteference from higher priority task when calculate finishing time (if task is preemptive type)
+ */
+ private void levelIforMixedNPandP() {
+ final Logger log = Logger.getLogger(this.getClass().getName());
+ final DecimalFormat df = new DecimalFormat("#,###.##");
+ log.debug("level-i for non-preemptive here");
+
+ final int[] exe = { 20, 20, 35, 40 };
+ final int[] p = { 70, 80, 200, 250 };
+ final int[] pType = { 0, 0, 0, 1 };
+ // 0 - preemptive, 1 - non-preemptive, 2 - cooperative
+ //rt = 55 - 75 - 75,
+
+ for (int i = 0; i < exe.length; i++) {
+ BigDecimal blockingTime = BigDecimal.valueOf(40);
+ if (i == 3) {
+ blockingTime = BigDecimal.ZERO;
+ }
+ log.debug("for task " + i + " preemptive type :" + pType[i]);
+ /* ----- Get LEVEL - I for each task ------ */
+ BigDecimal lv0 = BigDecimal.ZERO;
+ BigDecimal currentLv = BigDecimal.ONE;
+
+ final BigDecimal iPeriod = BigDecimal.valueOf(p[i]);
+ final BigDecimal iExe = BigDecimal.valueOf(exe[i]);
+ BigDecimal iResponseTime = BigDecimal.ZERO;
+ //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, j >= i
+ BigDecimal iterationValue = BigDecimal.ZERO;
+
+ for (int entry = 0; entry < i + 1; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ final BigDecimal roundUp = currentLv.divide(entryPeriod, RoundingMode.CEILING);
+ final BigDecimal entryValue = roundUp.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ }
+ //First entry of level-i = Bi + Ci, the sum above doesn't exist
+ //check non-premptive scheduler from TUDortmund pdf, google that shit
+ if (iterationCounterLvI == 0) {
+ iterationValue = iExe;
+ }
+ iterationCounterLvI++;
+ /* -- Add blocking for nonpreemptive here-- current lv plus blocking*/
+ iterationValue = iterationValue.add(blockingTime);
+ currentLv = iterationValue;
+ }
+ log.debug("level-" + i + ": " + lv0);
+
+ /* ----- Get K (total task iteration) ------ */
+ final int bigK = lv0.divide(iPeriod, RoundingMode.CEILING).intValue();
+
+ /**
+ * 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 time.
+ */
+ for (int smallK = 1; smallK <= bigK; smallK++) {
+ log.debug(" --- k instance : " + smallK + "/" + bigK + " --------------------------------------------");
+
+ BigDecimal kTaskStart = BigDecimal.ZERO;
+ BigDecimal currentKLv = BigDecimal.ONE;
+ final int smallK1 = smallK - 1;
+
+ /*starting time = Bi + sum([Si,Tj]+1)*Cj + (k-1)*Ci
+ calculating (k-1)*Ci here, Bi got from above via looping lower priority task execution time */
+ final BigDecimal kCi1 = iExe.multiply(BigDecimal.valueOf(smallK1));
+
+ //Equation from Tu Dortmund for this is wrong, so stick with mine
+ for (int entry = 0; entry < i; entry++) {
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+ hpCiSum = hpCiSum.add(entryExe);
+ }
+ int iterationCounterK = 0;
+
+ while (!kTaskStart.equals(currentKLv)) {
+ currentKLv = kTaskStart;
+ //entry = each small sum of [Li/Tj]Cj (rown down), j > i, not >=
+ BigDecimal iterationValue = BigDecimal.ZERO;
+ for (int entry = 0; entry < i; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ final BigDecimal roundDown = currentKLv.divide(entryPeriod, RoundingMode.FLOOR);
+ final BigDecimal roundDownPlusOne = roundDown.add(BigDecimal.ONE);
+ final BigDecimal entryValue = roundDownPlusOne.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ }
+ kTaskStart = iterationValue;
+ kTaskStart = kTaskStart.add(kCi1); //add k*Ci at the end of iteration
+ //first iteration = Bi + hpCiSum
+ if (iterationCounterK == 0) {
+ log.debug("hpCiSum - " + hpCiSum + " blocking " + blockingTime);
+ kTaskStart = hpCiSum;
+ //reseti this for next task
+ hpCiSum = BigDecimal.ZERO;
+ }
+
+ kTaskStart = kTaskStart.add(blockingTime); // add blocking time here
+ iterationCounterK++;
+ }
+
+
+ /* ----- Get finishing time for each task (k) ------ */
+
+ final BigDecimal taskStartTime = kTaskStart;
+ final BigDecimal taskStartPeriod = iPeriod.multiply(BigDecimal.valueOf(smallK1));
+ BigDecimal taskFinishingTime = BigDecimal.ZERO;
+ final int iPreemptiveType = pType[i]; // 0 - preemptive, 1 - non-preemptive, 2 - cooperative
+
+ /* if task is non-preemptive then startTime + Ci = finishing time */
+ if (iPreemptiveType == 1) {
+ taskFinishingTime = taskStartTime.add(iExe);
+ log.debug("start time " + df.format(taskStartTime) + " - finishing time " + df.format(taskFinishingTime) + " - period "
+ + df.format(taskStartPeriod));
+ }
+
+ /* 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*/
+ else if (iPreemptiveType == 2 || iPreemptiveType == 0) {
+ BigDecimal kTaskFinishingTime = BigDecimal.ONE;
+ BigDecimal currentFinishingTime = BigDecimal.ZERO;
+
+ while (!kTaskFinishingTime.equals(currentFinishingTime)) {
+ currentFinishingTime = kTaskFinishingTime;
+ BigDecimal iterationValue = BigDecimal.ZERO;
+ for (int entry = 0; entry < i; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ final BigDecimal roundUp = currentFinishingTime.divide(entryPeriod, RoundingMode.CEILING);
+ final BigDecimal roundDown = kTaskStart.divide(entryPeriod, RoundingMode.FLOOR);
+ final BigDecimal roundDownPlusOne = roundDown.add(BigDecimal.ONE);
+ final BigDecimal bigSum = roundUp.subtract(roundDownPlusOne);
+
+ final BigDecimal entryValue = bigSum.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ log.debug("([fi/tj]up - ([si/tj]down + 1)) : " + roundUp + " - " + roundDownPlusOne);
+ log.debug("Sum*Ci= " + entryValue + " = " + bigSum + " x " + entryExe);
+ }
+ log.debug("Finishing time = s + Ci + preemp (Sum*Ci) : " + kTaskStart + " + " + iExe + " + " + iterationValue);
+ iterationValue = iterationValue.add(kTaskStart).add(iExe);
+ kTaskFinishingTime = iterationValue;
+ }
+
+ taskFinishingTime = kTaskFinishingTime;
+ log.debug("start time " + df.format(taskStartTime) + " - finishing time " + df.format(taskFinishingTime) + " - period "
+ + df.format(taskStartPeriod));
+ }
+
+
+ /* ----- Get response time for each task (k) ------ */
+ final BigDecimal taskResponseTime = taskFinishingTime.subtract(taskStartPeriod);
+ if (taskResponseTime.compareTo(iResponseTime) >= 0) {
+ iResponseTime = taskResponseTime;
+ }
+ log.info(df.format(iResponseTime) + " current RT ");
+ }
+ log.info(df.format(iResponseTime) + " - responseTime of task ");
+ System.out.println();
+ }
+ }
+
+ /**
+ * calculate level-i busy period for cooperative tasks type. Assume all task is cooperative
+ *
+ * Credit: not me, I just implement his research, the work is from Ignacio. His paper is below
+ * Ignacio Sanudo, Paolo Burgio and Marko Bertogna "Schedulability and Timing Analysis of Mixed Preemptive-Cooperative Tasks on a Partitioned Multi-Core System".
+ */
+ private void levelIforCooperative() {
+ //Adding decimal Format for better visual checking when debugging
+ //ie 6000000000 ps -> 6,000,000,000 ps
+ final Logger log = Logger.getLogger(this.getClass().getName());
+ final DecimalFormat df = new DecimalFormat("#,###.##");
+
+
+ //Exe = execution time, p = period,
+ final int[] exe = { 20, 50, 60, 80 };
+ final int[] p = { 100, 180, 250, 300 };
+ //bl = blocking time (time that the task will be blocked by lower priority task)
+ final int[] bl = { 40, 40, 30, 0 };
+
+
+ for (int i = 0; i < exe.length; i++) {
+
+ /* ----- Get LEVEL - I for each task ------ */
+ BigDecimal lv0 = BigDecimal.ZERO;
+ BigDecimal currentLv = BigDecimal.ONE;
+
+ BigDecimal iPeriod = BigDecimal.valueOf(p[i]);
+ BigDecimal iExe = BigDecimal.valueOf(exe[i]);
+ BigDecimal blockingTime = BigDecimal.valueOf(bl[i]);
+ BigDecimal iResponseTime = BigDecimal.ZERO;
+ log.debug("for task " + i);
+
+ //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;
+
+ /*------Calculating level-i busy window-----*/
+ 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 < i + 1; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ 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;
+ }
+ log.debug("level-" + i + ": " + lv0);
+
+ /*-----------------------------Level-i finished-----------------*/
+ /* ----- Get K (total task iteration) ------ */
+ int bigK = lv0.divide(iPeriod, 0, RoundingMode.CEILING).intValue();
+
+ /* --------- get Task finishing time --------- */
+ /* ----- Get finishing time for each task ------ */
+ 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;
+ int counter = 0;
+ BigDecimal kCi = iExe.multiply(BigDecimal.valueOf(smallK));
+
+
+ while (!kLv.equals(currentKLv)) {
+ currentKLv = kLv;
+ //entry = each small sum of [Li/Tj]Cj, p_j > p_i, not >=
+ BigDecimal iterationValue = BigDecimal.ZERO;
+ for (int entry = 0; entry < i; entry++) {
+ final BigDecimal entryPeriod = BigDecimal.valueOf(p[entry]);
+ final BigDecimal entryExe = BigDecimal.valueOf(exe[entry]);
+
+ BigDecimal roundUp = currentKLv.divide(entryPeriod, 0, RoundingMode.CEILING);
+ BigDecimal entryValue = roundUp.multiply(entryExe);
+
+ iterationValue = iterationValue.add(entryValue);
+ if (counter == 0) {
+ iterationValue = BigDecimal.ZERO;
+ counter++;
+ break;
+ }
+ }
+ kLv = iterationValue;
+ /*--------------Bi + iteration + (k-1)Ci------------ */
+ kLv = kLv.add(kCi).add(blockingTime); //add k*Ci at the end of iteration
+
+ log.debug("finishTime = iterationValue + k*Ci: ");
+ String s1 = df.format(iterationValue);
+ String s2 = df.format(kCi);
+ String s3 = df.format(kLv);
+ String s4 = df.format(blockingTime);
+ log.debug("iteration ,(k-1)Ci, kLv, blocking time");
+ log.debug(s1 + ", " + s2 + ", " + s3 + ", " + s4);
+ }
+ /* ----- Get response time for each task (k) ------ */
+ BigDecimal taskStartTime = iPeriod.multiply(BigDecimal.valueOf(smallK1));
+ String s1 = df.format(taskStartTime);
+ String s2 = df.format(kLv);
+ log.debug("start time (k*period): " + s1 + " - finishing time " + s2);
+
+ BigDecimal taskResponseTime = kLv.subtract(taskStartTime);
+ String s3 = df.format(taskResponseTime);
+ log.debug(s3 + " - this k instance response time");
+
+ if (taskResponseTime.compareTo(iResponseTime) >= 0) {
+ iResponseTime = taskResponseTime;
+ }
+ log.debug(iResponseTime + " - biggest response time so far ");
+ }
+
+ String s1 = df.format(iResponseTime);
+ log.info(s1 + " task " + i + " response time");
+ System.out.println();
+ }
+ }
+
+
+}
\ No newline at end of file
