NPTEL Online Certification Courses Indian Institute

of Technology Kharagpur

Foundations of Cyber-Physical Systems

Assignment- Week 3
TYPE OF QUESTION: MCQ/MSQ/Numerical

Number of questions: 10 Total mark: 10 X 3 = 30

Question 1

Construct the schedule according to the RM policy for the following set of periodic tasks {𝜏1 , 𝜏2 , 𝜏3 }. Here, 𝐶𝑖 , 𝑇𝑖
𝑗
are the execution time and periods of task 𝜏𝑖 respectively and 𝜏𝑖 denotes j-th instance of task 𝜏𝑖 .

Tasks 𝐶𝑖 𝑇𝑖
𝜏1 2 6
𝜏2 2 8
𝜏3 2 12

a. 𝜏11 𝜏21 𝜏12 𝜏31 𝜏22 𝜏13 𝜏32 𝜏33 𝜏14

b. 𝜏11 𝜏21 𝜏31 𝜏12 𝜏22 𝜏13 𝜏32 𝜏23 𝜏14
c. 𝜏11 𝜏21 𝜏12 𝜏31 𝜏22 𝜏13 𝜏32 𝜏23 𝜏14
d. Not RM schedulable

Correct Answer: b. 𝜏11 𝜏21 𝜏31 𝜏12 𝜏22 𝜏13 𝜏32 𝜏23 𝜏14

Detailed Explanation:

Hyper-period = lcm(6,8,12) = 24

The ordering of the tasks as per priority according to RM scheduling policy (task with smallest period
has the highest priority) is 𝜏1 > 𝜏2 > 𝜏3

The execution of the tasks following RM scheduling will look like

𝑗
This leads to the schedule: 𝜏11 𝜏21 𝜏31 𝜏12 𝜏22 𝜏13 𝜏32 𝜏23 𝜏14 where 𝜏𝑖 denotes j-th instance of task 𝜏𝑖
NPTEL Online Certification Courses Indian Institute
of Technology Kharagpur

Question 2

Construct the schedule according to the RM policy for the following set of periodic tasks {𝜏1 , 𝜏2 }. Here, 𝐶𝑖 and 𝑇𝑖
are the execution time and periods of task 𝜏𝑖 respectively.

Tasks 𝐶𝑖 𝑇𝑖

𝜏1 2 5
𝜏2 4 7

a. 𝜏11 𝜏21 𝜏12 𝜏21 𝜏22 𝜏13 𝜏22 𝜏23 𝜏14 𝜏23 𝜏15 𝜏24 𝜏16 𝜏24 𝜏25 𝜏17 𝜏25
b. 𝜏11 𝜏21 𝜏12 𝜏21 𝜏22 𝜏13 𝜏22 𝜏23 𝜏14 𝜏23 𝜏15 𝜏24 𝜏16 𝜏24 𝜏25 𝜏26 𝜏27
c. 𝜏11 𝜏21 𝜏12 𝜏22 𝜏13 𝜏23 𝜏14 𝜏23 𝜏15 𝜏24 𝜏16 𝜏25 𝜏17
d. Not RM schedulable

Correct Answer: d. Not RM schedulable

Detailed Explanation:

At t=0, both the tasks arrive but 𝜏1 is executed as it has higher priority. It executes up to t=2. At t=2, 𝜏2
begins execution. At t=5, 𝜏2 is yet to finish its execution, but second instance of 𝜏1 arrives which has
higher priority and thus preempts 𝜏2 . Second instance of 𝜏1 executes up to t=5+2=7. At this point, first
instance of 𝜏2 is incomplete but second instance of 𝜏2 arrives. Therefore, first instance of 𝜏2 misses its
deadline.

Question 3

Construct the EDF schedule for the following task set {𝜏1 , 𝜏2 , 𝜏3 }. Here, 𝐶𝑖 , 𝐷𝑖 , and 𝑇𝑖 are the execution time,
relative deadline, and periods of task 𝜏𝑖 respectively.

Tasks 𝐶𝑖 𝐷𝑖 𝑇𝑖
𝜏1 2 5 6
𝜏2 2 4 8
𝜏3 4 8 12
a. 𝜏11 𝜏21 𝜏31 𝜏12 𝜏22 𝜏13 𝜏32 𝜏23 𝜏14
b. 𝜏11 𝜏21 𝜏31 𝜏12 𝜏22 𝜏32 𝜏13 𝜏23 𝜏14
c. Not EDF Schedulable
d. 𝜏21 𝜏11 𝜏31 𝜏12 𝜏22 𝜏13 𝜏32 𝜏23 𝜏14

Correct Answer: d. 𝜏21 𝜏11 𝜏31 𝜏12 𝜏22 𝜏13 𝜏32 𝜏23 𝜏14

Detailed Explanation:

EDF gives priority to the task having earliest deadline. Therefore, the priority ordering of the tasks is
𝜏2 > 𝜏1 > 𝜏3 . At t=0, 𝜏2 will be executed first followed by 𝜏1 and then 𝜏3 .
NPTEL Online Certification Courses Indian Institute
of Technology Kharagpur

Question 4

Consider seven tasks, A, B, C, D, E, F, and G, with precedence relations among them as: 𝐴 → 𝐶, 𝐵 →
𝐶, 𝐵 → 𝐷, 𝐶 → 𝐸, 𝐶 → 𝐹, 𝐷 → 𝐹, 𝐷 → 𝐺 where 𝑥 → 𝑦 implies 𝑦 can start its execution only after the
completion of 𝑥’s execution. The task graph representing this precedence relation is given below.

Assume that all tasks have arrived at t=0, have deadlines d = 25, and their computation times are
2,3,3,5,1,2,5 respectively. Modify the deadlines of the tasks similar to EDF*. Consider that the new
release time of a task can be replaced by the maximum between the finishing time of its immediate
predecessors and the release time of that task. With the modified release times and deadlines,
construct the EDF schedule. Assume that period of each task is same as its deadline.

a. B,A,D,C,E,F,G
b. A,B,D,C,E,F,G
c. B,A,C,D,E,F,G
d. A,B,C,D,E,F,G

Correct Answer: a. B,A,D,C,E,F,G

Detailed Explanation:

According to the modified release time and deadline, at t=0, tasks A and B are available. Following
EDF, B will execute first up to t=3. At t=3, A, C, and D are available. Following EDF, either A or D can
start its execution. Let us consider A executes up to t = 3+2 = 5. Next, D will start its execution. At t=6,
F arrives. But, according to EDF policy, D will keep executing up to t = 5 + 5 = 10. This way, we get the
final schedule as B,A,D,C,E,F,G.
NPTEL Online Certification Courses Indian Institute
of Technology Kharagpur

Question 5

A real-time operating system runs in 𝑃𝑈𝐴 that follows deadline monotonic (DM) scheduling. Unlike
earliest deadline first (EDF) scheduling policy, DM is a fixed-priority static scheduling policy that gives
highest priority to the task that has smallest deadline. In each sampling period, the tasks 𝑇𝑠 (sensor
task), 𝑇𝑐 (control task) and 𝑇𝑇𝑥 (transmission task) are released respectively at t = 0ms, t = 1.8ms and t
= 9.5ms. Following are the details of the tasks mapped in 𝑃𝑈𝐴

Consider the communication bus follows a time division multiple access (TDMA) scheduling policy with
a bandwidth of 12.8Kbps. The transmission task 𝑇𝑇𝑥 transmits the 8 Byte control data in a particular slot
in every cycle of TDMA. Consider another processing unit 𝑃𝑈𝐵 connected to the bus. It receives the
control data by executing the recipient task 𝑇𝑅𝑥 and then the actuation task 𝑇𝑎 actuates the plant using
this control input data. The real-time operating system that runs in 𝑃𝑈𝐵 follows earliest deadline first
(EDF) scheduling policy. Following are the details of tasks mapped in the 𝑃𝑈𝐵 .

What is the minimum offset of 𝑇𝑅𝑥 in milliseconds (ms)?

Correct Answer: 15 or 16 (Both are correct)

Detailed Explanation:

In 𝑃𝑈𝐴, the tasks are scheduled following deadline monotonic scheduling policy. At t=0, only 𝑇𝑠 is
available. Therefore, 𝑇𝑠 executes from t=0 to t=0.2. At t=1.8, 𝑇𝑐 arrives and executes till t = 1.8+3.2 = 5.
The transmission task 𝑇𝑇𝑥 arrives at t = 9.5 and executes up to t = 9.5+0.5 = 10. Hence, the control task
will be available to be transmitted inside the bus only at t=10 ms.

It is given that the bandwidth of the bus is 12.8Kbps. Therefore, transmitting 8 Byte data takes 8 ×
8
s = 5 ms.
12800

Periodicity of the control task 𝑇𝑐 is 25 ms. Therefore, the TDMA cycle length is 25 ms with each slot
being at least 5 ms. Since, the control data can be available at every 10 ms in the bus, the control data
is allocated to 3rd slot in a TDMA cycle. Therefore, 𝑃𝑈𝐵 receives control data at every 15 ms. Therefore,
the minimum offset of reception task 𝑇𝑅𝑥 at 𝑃𝑈𝐵 is 15 ms.
NPTEL Online Certification Courses Indian Institute
of Technology Kharagpur

Question 6

Considering the same real-time system setup demonstrated in Question 5, what is the minimum offset
of 𝑇𝑎 in milliseconds (ms)?

Correct Answer: 16.5

Detailed Explanation:

The control tasks in 𝑃𝑈𝐵 are scheduled following EDF scheduling policy. Therefore, 𝑇𝑠𝑒𝑐 has the
highest priority. The first conflict happens at t=15 when both 𝑇𝑠𝑒𝑐 and 𝑇𝑅𝑥 are available. Since, 𝑇𝑠𝑒𝑐 has
the earliest deadline, it will be executed. Therefore, 𝑇𝑅𝑥 will start execution at t=15+1=16 and executes
up to t=16+0.5=16.5. The actuation task can only start its execution after 𝑇𝑅𝑥 com pletes processing the
control data. Therefore, the minimum offset of 𝑇𝑎 is 16.5 ms.

Question 7

Considering the same real-time system setup demonstrated in Question 5, what is the minimum
sensor-to-actuator delay in milliseconds (ms)?

Correct Answer: 19.5

Detailed Explanation:

The actuation task 𝑇𝑎 will start its execution at t=16.5 and executes up to t=16.5+3=19.5 (considering
the minimum offset of 𝑇𝑎 ). Therefore, the minimum sensor-to-actuator delay is 19.5 ms.

Question 8

Consider the following messages being transmitted through the CAN bus.

Messages Period 𝑝𝑖 (ms) Deadline 𝑑𝑖 (ms) Execution Time 𝑐𝑖 (ms) ID

𝑚1 30 15 5 2
𝑚2 20 12 8 3
𝑚3 40 30 12 1

Compute the blocking time of each of the messages.

a. 𝐵𝑚1 = 8, 𝐵𝑚2 = 8, 𝐵𝑚3 = 0

b. 𝐵𝑚1 = 12, 𝐵𝑚2 = 12, 𝐵𝑚3 = 0
c. 𝐵𝑚1 = 12, 𝐵𝑚2 = 0, 𝐵𝑚3 = 12
d. 𝐵𝑚1 = 8, 𝐵𝑚2 = 0, 𝐵𝑚3 = 8

Correct Answer: d. 𝐵𝑚1 = 8, 𝐵𝑚2 = 0, 𝐵𝑚3 = 8

Detailed Explanation:
NPTEL Online Certification Courses Indian Institute
of Technology Kharagpur

Blocking time of message 𝑚𝑖 is calculated as 𝐵𝑚𝑖 = max 𝑐𝑘 where 𝑙𝑝(𝑚𝑖 ) denotes the messages
𝑘∈𝑙𝑝(𝑚𝑖 )
that have lower priority than 𝑚𝑖

Therefore, 𝐵𝑚1 = max(8) = 8, 𝐵𝑚2 = 0, B𝑚3 = max(5,8) = 8

Question 9

Considering the same CAN bus setup in Question 8, compute the busy period of each of the
messages.

a. 𝑡𝑚1 = 38, 𝑡𝑚2 = 20, 𝑡𝑚3 = 38

b. 𝑡𝑚1 = 25, 𝑡𝑚2 = 38, 𝑡𝑚3 = 20
c. 𝑡𝑚1 = 20, 𝑡𝑚2 = 38, 𝑡𝑚3 = 25
d. 𝑡𝑚1 = 38, 𝑡𝑚2 = 38, 𝑡𝑚3 = 20

Correct Answer: b. 𝑡𝑚1 = 25, 𝑡𝑚2 = 38, 𝑡𝑚3 = 20

Detailed Explanation:
𝑘
𝑡𝑚
𝑘+1 = 𝐵 𝑖
Busy period of message 𝑚𝑖 is calculated as, 𝑡𝑚𝑖 𝑚𝑖 + ∑∀𝑚∈ℎ𝑝(𝑚𝑖 )∪𝑚𝑖 ⌈ 𝑝𝑚
⌉ 𝑐𝑚 where ℎ𝑝(𝑚𝑖 ) denotes
0 is set with 𝑐 .
the messages that have higher priority than 𝑚𝑖 and initially 𝑡𝑚𝑖 𝑚𝑖

Busy period for 𝑚1

0 =5
𝑡𝑚1

1 =8+⌈
5 5
𝑡𝑚1
⌉ × 5 + ⌈ ⌉ × 12 = 25
30 40
2
25 25
𝑡𝑚 1
= 8 + ⌈ ⌉ × 5 + ⌈ ⌉ × 12 = 25
30 40
2 = 𝑡 1 and 𝑡
We stop as 𝑡𝑚1 𝑚1 𝑚1 = 25

Similarly, we can compute 𝑡𝑚2 = 38 and 𝑡𝑚3 = 20

Question 10

Considering the same CAN bus setup in Question 8, compute the response time of each of the
messages.

a. 𝑅𝑚1 = 13, 𝑅𝑚2 = 20, 𝑅𝑚3 = 25

b. 𝑅𝑚1 = 20, 𝑅𝑚2 = 20, 𝑅𝑚3 = 25
c. 𝑅𝑚1 = 25, 𝑅𝑚2 = 25, 𝑅𝑚3 = 20
d. 𝑅𝑚1 = 25, 𝑅𝑚2 = 13, 𝑅𝑚3 = 20
NPTEL Online Certification Courses Indian Institute
of Technology Kharagpur

Correct Answer: c. 𝑅𝑚1 = 25, 𝑅𝑚2 = 25, 𝑅𝑚3 = 20

Detailed Explanation:

If busy period 𝑡𝑚𝑖 < 𝑝𝑚𝑖 , then response time of 𝑚𝑖 is 𝑅𝑚𝑖 = 𝑡𝑚𝑖
Therefore, 𝑅𝑚1 = 𝑡𝑚1 = 25 (as 𝑡𝑚1 = 25 < 𝑝𝑚1 = 30) and 𝑅𝑚3 = 𝑡𝑚3 = 20 (as 𝑡𝑚3 = 20 < 𝑝𝑚3 = 40)
𝑡𝑚2
However, 𝑡𝑚2 > 𝑝𝑚2 . Therefore, 𝑅𝑚2 = max 𝑅𝑚2 (𝑞) where 𝑄𝑚2 = ⌈ ⌉ is the number of
𝑞=0,…,𝑄𝑚2 −1 𝑝𝑚2
instances of 𝑚2 arriving within its busy period. 𝑅𝑚𝑖 (𝑞) is calculated as follows.

𝑅𝑚𝑖 (𝑞) = 𝑤𝑚𝑖 (𝑞) − 𝑞𝑝𝑚𝑖 + 𝑐𝑚𝑖

𝑘 (𝑞)+𝜏
𝑤𝑚
𝑘+1 (𝑞) = 𝐵 𝑖 𝑏𝑖𝑡 0 (𝑞) = 𝐵
𝑤𝑚𝑖 𝑚𝑖 + 𝑞𝑐𝑚𝑖 + ∑∀𝑚∈ℎ𝑝(𝑚𝑖 ) ⌈ 𝑝𝑚
⌉ 𝑐𝑚 where 0 < 𝜏𝑏𝑖𝑡 < 1 and 𝑤𝑚𝑖 𝑚𝑖 + 𝑞𝑐𝑚𝑖 .
𝑘+1 (𝑞) = 𝑤 𝑘 (𝑞)
The recursive method to compute the waiting time 𝑤𝑚𝑖 (𝑞) terminates when 𝑤𝑚𝑖 𝑚𝑖

38
Therefore, 𝑄𝑚2 = ⌈ ⌉ = 2
20
0 (0) = 0
𝑤𝑚 2

1
0 + 𝜏𝑏𝑖𝑡 0 + 𝜏𝑏𝑖𝑡
𝑤𝑚2 (0) = ⌈ ⌉×5+⌈ ⌉ × 12 = 17
30 40
2 (0) = ⌈
17 + 𝜏𝑏𝑖𝑡 17 + 𝜏𝑏𝑖𝑡
𝑤𝑚 2
⌉×5+⌈ ⌉ × 12 = 17
30 40
𝑤𝑚2 (0) = 17
𝑅𝑚2 (0) = 17 + 8 = 25

0 (1) = 8
𝑤𝑚2

1 (1)
8 + 𝜏𝑏𝑖𝑡 8 + 𝜏𝑏𝑖𝑡
𝑤𝑚2
= 8+⌈ ⌉×5+⌈ ⌉ × 12 = 25
30 40
2 (1)
25 + 𝜏𝑏𝑖𝑡 25 + 𝜏𝑏𝑖𝑡
𝑤𝑚2
= 8+⌈ ⌉×5+⌈ ⌉ × 12 = 25
30 40
𝑤𝑚2 (1) = 25
𝑅𝑚2 (1) = 25 − 20 + 8 = 13

𝑅𝑚2 = max{25,13} = 25