ECEN 5623 Real-Time Embedded Systems

Sairam Udaya Janardhana Muttavarapu

Exercise #1 (Invariant LCM Schedules) Report

Q1. Given three services S1, S2, and S3 with (T1, C1) = (3, 1), (T2,
C2) = (5, 2), (T3, C3) = (15, 3) where all times are in milliseconds,
Where T1, T2, T3 are the request time periods (deadlines), and
C1, C2, C3 are the WCETs (Worst Case Execution Times) of
the three services S1, S2 and S3 respectively.
Rate Monotonic (RM) Fixed Policy states that services which
share a CPU core should multiplex it based on priority, where
highest priority is assigned to the most frequently requested
service and lowest priority is assigned to the least frequently AND
total share CPU core utilization must preserve some margin (not to
be fully utilized or overloaded).
As per RM Fixed Policy, the timing diagram for the service set (S1,
S2, S3) is as follows:

From inspection, we can see from above timing diagram that the
service set S1, S2, S3 is feasible with RM Fixed Policy Schedule.
There is no deadline miss of any service within the LCM period of
all services i.e. LCM of 3, 5, 15 milliseconds = 15 milliseconds time
period. As the schedule is invariant indefinitely as per the RM Fixed
Policy, the above RM Schedule is safe i.e. it is unlikely to ever miss
a deadline.
Utilization Factor of the processor is defined to be the fraction of
processor time spent in the execution of the task set.
Where U = Utilization Factor,
Ci = Execution Time of Service i,

Ti = Request Period of Service i.

U1 = Utilization Factor of Task 1 = C1/T1 = 1/3 = 0.333.
U2 = Utilization Factor of Task 2 = C2/T2 = 2/5 = 0.4.
U3 = Utilization Factor of Task 3 = C3/T3 = 3/15 = 0.2.
Total CPU Utilization = U = U1 + U2 + U3 = 0.933 i.e. 93.3 %
RM LUB (Least Upper Bound) Feasibility Test is a sufficient
condition test to check the feasibility of any RM Schedule, RM LUB
value for m services is defined as
RM LUB Utilization Factor = m (21/m 1)
RM LUB for 3 services = 3(21/3 1) = 0.7797.
As per RM LUB Feasibility Test, Utilization factor for 3 services has
to be less than RM LUB value i.e. 0.7797. But the above RM
Schedule is failing this test as 0.933 > 0.7797.
Though the above RM Schedule is failing RM LUB Feasibility Test, it
can be seen from the timing diagram that it is still feasible. As it is
only a sufficient condition test and not a necessary condition test,
a RM Schedule with U > RM LUB can still be feasible.

Q2. Summary of the Apollo 11 Overload Story:

The jobs scheduled for the systems in Apollo 11 were allocated an
erasable memory to store the intermediate computational values, but
not to store the data. Each job was allocated a core set which has 12
memory locations and if the job needs extra memory then a VAC was
allocated with 44 word memory. And there a total of 7 core sets and 5
VAC memory locations.
When more number of jobs were being scheduled than the OS can
accommodate in the core sets or the VACs, Alarm/Abort routines were
executed and for non-availability of free core set, a 1202 alarm was
raised and for non-availability of a VAC, a 1201 alarm was raised. So,
this was the main issue raised during Apollo 11 landing on the moon.
Multiple alarms were being raised continuously due to overloading of
the processor with many unnecessary tasks.
The issue was raised due to an error in the checklist, which has made
the rendezvous radar data processes to be placed in a different order.
Due to this, there was a stream of data continuously being sent for
processing which made the processor flooded with unnecessary tasks
and when the landing related tasks were scheduled, the alarms were
raised due to non-availability of the core sets and the VACs.
Owing to the robust code written by the folks at MIT, the system could
handle this situation. So, when such alarms raise continuously the
system was designed in a such a way that, it initiates an instant
reboot after which the system flushes all the lower priority tasks such
as the rendezvous radar tasks and restores the higher priority tasks
and allocates resources to them. This way the important tasks related
to the landing have been allocated resources and thus avoiding a
mission abort situation.
Root Cause and RM policy failure:
The flooding of the processor with unnecessary tasks from the
rendezvous radar data caused the non-availability of the resources to
the landing related tasks.
If the RM policy has been used in the system for Apollo 11, the main
reason it could have failed is because, the more frequently occurring
radar tasks were assigned lower priority and they were flushed the
less frequently requesting landing tasks were given higher priority.

LUB plot as a function of Number of services:

RM LUB
1
0.95
0.9
CPU utility

0.85
0.8
0.75
0.7
1

10

Number of Services (m)

Assumptions:
1. The requests for all tasks for which hard deadlines exist are
periodic, with constant interval between requests.
2. The tasks are independent in that requests for a certain task do
not depend on the initiation or the completion of requests for
other tasks.
3. Run-time for each task is constant for that task and does not
vary with time. Run-time here refers to the time which is taken
by a processor to execute the task without interruption.
Problems in Fixed Priority LUB derivation:
1. (THEOREM 2) If a feasible priority assignment exists for some
task set, the ratemonotonic priority assignment is feasible for
that task set.

2. (THEOREM 3) For a set of two tasks with fixed priority

assignment, the least upper bound to the processor utilization
factor is U = 2 (2 ~ - 1).
3. (THEOREM 4) For a set of m tasks with fixed priority order, and
the restriction that the ratio between any two request periods
is less than 2, the least upper bound to the processor utilization
factor is U = m (21/m - 1).

Would RM policy help in avoiding 1201/1202 Alarms:

Maybe not. Because, according to the RM policy the higher priority is
given to the most frequently occurring tasks but in the Apollo 11
system, the more frequently occurring radar tasks were assigned
lower priority and they were flushed after the system reboot. This
violates the RM policy. If the system had had not violated RM policy,
the system would have failed.

Q3. Below is the screenshots for Build and Code Execution of POSIX
Clock Linux code:
a.

Code Execution when #define RUN_RT_THREAD is commented

above main function() and without pthread creation using
SCHED_OTHER scheduling policy:

b.

Code Execution when #define RUN_RT_THREAD is uncommented

above main function() and with pthread creation using SCHED_FIFO
scheduling policy:

POSIX Clock Linux Code Description:

In main function, first current scheduling policy is printed using
print_scheduler function.
If #define RUN_RT_THREAD is defined, then thread attributes object
main_sched_attr is initialized. After that, inheritsched attribute is
assigned to PTHREAD_EXPLICIT_SCHED, schedpolicy attribute is
assigned to SCHED_FIFO (Real-Time Scheduling Policy), schedparam
attribute is assigned by giving appropriate priority value. Then,
main_thread is created using the main_sched_attr object, and
mapping delayTest() function as Starting function of main_thread
and sending (void*) 0 as argument to delayTest() function.
If #define RUN_RT_THREAD is not defined, then delayTest() function is
executed.
Inside delayTest() function, a delay of 3 seconds is simulated using
nanosleep() function. Also, clock_gettime() function calls are made to
log start and stop time stamps and are passed to delay_t() function to
find out the actual delay created. There is some delay error between
delay time requested and RT Clock Delay Time stamping. As there is
around 35670 nanoseconds delay error, I think the RT Clock is not that
accurate.
The above RT Clock accuracy can also depend on the timing in
deadline requirements.

And when the same code is executed on VirtualBox Ubuntu machine, I

found a delay error of around 123340 nanoseconds. So, even the RT
Clock accuracy is also varying with the target machine tested.
Most RTOS Vendors brag about the following three things:
1. Low Interrupt handler Latency:
Interrupts have to be handled with as low latency as possible.
Otherwise, an extra overhead will be added to the services which
has to meet deadlines in time. Low Interrupt handler latency is very
important in Real-Time Embedded Systems.
2. Low Context switch time:
Context switch between two processes will take lot of time when
compared with threads. If the context switch time is more, then
again due to addition in the latency there is a high chance of realtime deadline requirements. So, low context switch time is crucial in
Real-Time Operating System.
3. Stable timer services:
If there are no stable timer services, then suppose if we request for
a sleep of 20msec, and if we get actual sleep time of 25msec (>
20msec) or 15msec (< 20msec), then it will affect the tasks in
meeting the real-time deadline requirements. So, timer services
with low jitter are essential in Real-Time systems.
All the above things will add extra latency in meeting the deadlines
and also effect in getting predictable and deterministic output for RealTime Embedded Systems.

Q4. Below are the screenshots for Code Execution of Simple Thread
and Example-Sync codes:
a.) Screenshot of Simple Thread Code (Build and Run) on
Ubuntu Linux - Altera DE1-SoC Development Board:

b.)
Screenshot
of Example-Sync Code (Build) on Ubuntu Linux - Altera DE1SoC Development Board:

Screenshot of Example-Sync Code (Run) on Ubuntu Linux Altera DE1-SoC Development Board:

c.) Screenshot of Binary Semaphore Code Build (ported from

code in VxWorks RTOS) on Ubuntu Linux - Altera DE1-SoC
Development Board:

Screenshot of Binary Semaphore Code Execution (ported

from code in VxWorks RTOS) on Ubuntu Linux - Altera DE1SoC Development Board:

Starte

2
3
4
5

Stop

6
7
8

The bubbles shown in the above figure correspond to the following:

Start => Start of LCM Invariant Schedule
1 => Fib10 Code Execution Complete Event 1
2 => Fib10 Code Execution Complete Event 2
3 => Fib20 Code Execution Complete Event 1
4 => Fib10 Code Execution Complete Event 3
5 => Fib10 Code Execution Complete Event 4
6 => Fib20 Code Execution Complete Event 2
7 => Fib10 Code Execution Complete Event 5

8 => Idle Time Completion which is also the Stop of LCM Invariant
Schedule
Stop => Stop of LCM Invariant Schedule
All the above described bubbles map with the Event Analysis Timing
Diagram as shown in figure below.
VxWorks RTOS Code Description:
Initially a higher priority task called Sequencer is spawned inside
Start() function. Sequencer task creates a middle priority task called
serviceF10 and a low priority task called serviceF20. It also
initializes two binary semaphore locks semF10 and semF20
respectively. serviceF10 and serviceF20 tasks takes semF10 and
semF20 semaphore locks respectively and waits till those locks are
released by Sequencer task.
Sequencer task releases semF10 and semF20 locks in such an
order that it generates a LCM Invariant Schedule as shown below.

Starte
1

Stop
2

serviceF10, serviceF20 tasks emulate work load of 10ms and 20ms

respectively. Sequencer task emulates RM Schedule with LCM period
of services serviceF10, serviceF20, idle (Idle time of CPU) as 100
ms.

Linux Ported Code Description:

VxWorks RTOS Code is ported to Linux Code by creating pthreads in
Linux corresponding to Tasks in VxWorks RTOS. And binary semaphore
implementation is done in Linux by including Semaphore.h. semTake(),
semGive(), semBCreate() functions in VxWorks RTOS map to
sem_wait(), sem_post(), sem_init() functions in Linux. In VxWorks
RTOS, higher priority task is assigned a lower priority number and in
Linux higher priority thread is assigned a higher priority number.
wvEvent() logging in VxWorks RTOS maps to clock_gettime()
timestamping in Linux code. Other OS specific api related changes are
made like Start Function return type in VxWorks RTOS is void while in
Linux it is void*.
clock_gettime() timestamping functionality is leveraged in Linux code
for printing the various events (Start, 1, 2,,8, Stop) described above
and for mapping those timestamps to the timing diagram given in the
Exercise 1 Requirements.
Synthetic Load Generation is basically simulating the work load of
10ms and 20ms inside fib10, fib20 and FIB_TEST() functions. So, the
iterations had to tweaked accordingly to meet the approximately
10ms, 20ms work load requirement in Altera DE1-SoC Development
Board. Iterations inside fib10 function got changed from 170000 in
VxWorks RTOS to 1100000 in Linux and inside fib20 function got
changed from 340000 in VxWorks RTOS to 2495000 in Linux.
I faced two main challenges after porting the Linux code and tweaking
it to meet the timing diagram schedule given in the Exercise 1
requirements. They are:
1. It took some time to understand why there is parallel execution of
three threads (Sequencer, serviceF10, serviceF20) during the same
time.
Then, after searching online about the parallel execution of three
threads during the same time despite giving FIFO scheduling policy
and priority to the threads, I figured out that the issue is because of
multi-core/multi-processor system. Since there are multiple
core/CPU present on Altera DE1-SoC, three threads despite being

following FIFO scheduling policy with different priority; all the

threads are running on different core/CPU as there is other core
availability. After discussing about this issue with Akshay, I even got
more clarity.
So, the fix for this is to give Affinity and link each thread to the
same core. Thus, in a way converting the SMP Program to AMP
Program using Affinity in Linux.
2.

After fixing this issue, then the second challenge was to tweak the
iteration values inside fib10, fib20 functions such that it matches
with the timing diagram mentioned in the Exercise requirements.
The iteration values differed from Virtual Box Ubuntu and Ubuntu
and Altera DE1-SoC Development Board.

Thus given in the below screenshot, I was able to achieve predictable

reliable results invariantly over LCM time period of 100ms and
Synthetic work load of fib10, fib20 as close as possible to 10ms and
20ms.