-
Notifications
You must be signed in to change notification settings - Fork 0
/
CALCULATIONS
47 lines (28 loc) · 2.89 KB
/
CALCULATIONS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#Feasibility analysis
The first set of calculus that has been developed is a feasibility analysis for RMA and EDF. The analysis for RMA are a pessimistic result in the sense that they establish a sufficient but not necessary condition.
Within RMA a set of m tasks is feasible if:
**SUMMATION**(Ci/Ti) < m((2^(1/m))-1)
where Ci is the worst-case execution time for task i and Ti is the period of task i.
Within EDF a set of m tasks with Di (Deadline for task i) = Ti is feasible if and only if:
**SUMMATION**(Ci/Ti) <= 1
where Ci is the worst-case execution time for task i and Ti is the period of task i.
#Uniprocessor's response time analysis
The second set of calculus that has been developed is the response time analysis for a set of tasks in a uniprocessor. In this case RMA and DMS scheduling algorithms have benn taken into account. The calculus are done iteratively using the following formula:
Wi(n+1) = Ci + **SUMMATION**[(Wi+Jj)/Tj]*Cj
where Ci is the worst-case execution time for task i, j is an index used to traverse the tasks which priority is higher than the one that is being calculated, Jj is the release jitter for task j, Tj is the period of task j and Cj is the worst-case execution time for task j. In the first iteration Wi(0) is equal to Ci.
As said before the calculus are done iteratively and they stop when Wi(n+1) is equal to Wi(n). When this condition is reached the response time can be calculated as follows:
Ri = Wi(n) + Ji
Now, whether the task meets its deadline can be checked, ergo, Ri should be less or equal to Di. If some of the tasks doesn't meet its deadline then the task set is not feasible under that order.
##Shared resources on uniprocessors
Calculation of shared resources is an extension of the the previous model with the difference that it takes into account the execution time of the shared resources. Depending on the protocol being used this execution time varies. The calculus are done iteratively using the following formula:
Wi(n+1) = Ci + Bi + **SUMMATION**[(Wi+Jj)/Tj]*Cj
where Bi is the worst-case execution time for shared resources.
###Priority Inheritance Protocol (PIP)
If the protocol being used is PIP a task can be blocked at most once per each lower level task and at most once per each resource.
###Priority Ceiling Protocol (PCP)
On the contrary if PCP is used the blocking time for a task is bounded by the longer time any lower priority task can use any resource which can be used by a task of equal or higher priority than the actual task.
###Immediate Priority Ceiling Protocol (IPCP)
IPCP has the same properties as PCP regarding to blocking and response time calculus.
##Busy period
Let’s assume tasks’ deadlines greater than their periods. Level i busy period is the maximum time for which a processor executes tasks of priority i or higher. The response instant of the q−th job of a task can be calculated by:
Wi(q) = (q+1)*Ci + **SUMMATION**[(Wi(q)+Jj)/Tj]*Cj