Bug 562791 - RTA for task in Non-preemptive and preemptive environment


Change-Id: Iaa318a97af56bef41330617b85a307226815c871
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
new file mode 100644
index 0000000..2e0b1ef
--- /dev/null
+++ b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/NPandPRTA.java
@@ -0,0 +1,326 @@
+/*******************************************************************************

+ * Copyright (c) 2019 Dortmund University of Applied Sciences and Arts.

+ *

+ * This program and the accompanying materials

+ * are made available under the terms of the Eclipse Public License 2.0

+ * which accompanies this distribution, and is available at

+ * https://www.eclipse.org/legal/epl-2.0/

+ *

+ * SPDX-License-Identifier: EPL-2.0

+ *

+ * Contributors:

+ *     FH Dortmund - initial API and implementation

+ *******************************************************************************/

+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();