EEET1262 Real Time Systems Design

Assignment 2: Scheduling

Lecturer: Prof. Roy Ferguson ([Link]@[Link])

Submision Date: 2007/05/14

Students: Wilson Castillo Bautista (s3143667@[Link])

Subject Code: EEET1262 Real Time Systems Design

Melbourne, May 4th, 2007

EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

Table of Contents

1 Introduction ......................................................................................................................................4
2 Question 1 .........................................................................................................................................4
3 Question 2 .........................................................................................................................................7
4 References ........................................................................................................................................9

RMIT University © 2007 2 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

Table of Figures

Figure 1: Conventions used for timing diagrams (Buttazzo G C, 1997) .........................................5

Figure 2: Timing Diagram for tasks set Question 1) case a).............................................................5
Figure 3: Timing Diagram for tasks set Question1) case b)..............................................................6
Figure 4: Timing Diagram for tasks set Question1) case c) ..............................................................6
Figure 5: Timing Diagram using EDF scheduling algorithm for tasks set Question 1) case c) ...7

Table of Tables

Table 1: Utilisation Bound U(n)...............................................................................................................4

Table 2: Tasks set Question 1) Case a) ................................................................................................5
Table 3: Tasks set Question 1) Case b) ................................................................................................5
Table 4: Tasks set Question 1) case c) .................................................................................................6

RMIT University © 2007 3 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

Scheduling

1 Introduction

Every system designed to execute a specific function is composed by different process.

Each process requests frequently the exclusive use of the CPU; and very often, there are
situations where two process are simultaneously ready to run. Then, the operating system is
responsible to define which process is going to run every time. And this is done by a part of
the operating system called the scheduler associated with a scheduling algorithm.

Scheduling is the assignation, in a multiprogrammed application, of the CPU to processes in

order to make the whole program behave accordingly to its design. Generally, there are
two types of scheduling; preemptive and nonpreemtive. The former is when the CPU can
be taken away from a process and nonpreemtive is when the CPU cannot be taken
away.

This assignment has to do with some practical exercises related with scheduling (Ferguson,
R C, 2007).

2 Question 1

For each of the following cases, determine whether the set of task is schedulable using rate
monotonic scheduling, given the utilisation bound table as follows:

Number of Tasks n Utilisation Bound U(n)

1 1.000
2 0.8284
3 0.7798
4 0.7568
Infinity 0.6931
Table 1: Utilisation Bound U(n)

Show working including timing diagrams (for the Completion Time Theorem) where
required. If the entire set of 4 tasks is not schedulable determine the subset of task that are
schedulable.

For cases that fail the Utilisation Bound test also give the timing diagrams showing the
execution of these tasks sets using the Earliest Deadline First (EDF) scheduling algorithm,
starting with all tasks being released simultaneously. For EDF if instances of different tasks
have the same deadline then the one with the earliest release time has the priority.

a)

Computation
Task Period T Utilisation U
Time C
T1 12 3 0.25

RMIT University © 2007 4 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

T2 15 3 0.20
T3 20 3 0.15
T4 25 5 0.20
Utilisation Bound U(4) 0.8
Table 2: Tasks set Question 1) Case a)

For this first case the Utilisation Bound Test fails because it is 0.8 which is bigger that 0.7568
as can be seen in Table 1. It means that these set of tasks exceed the processor utilisation.
However, the fact that this test fails gives nothing to say about the feasibility of the set
(Buttazzo G C, 1997).

Therefore, it is necessary to draw the timing diagram for this set of tasks. For this the
conventions showed in Figure 1 are used. And the length of the time line to be drawn is
determined by the longest period (Burns A and Wellings A, 1996). In this case T4 with period
T = 25.

Figure 2 shows the diagram and as it can be seen of all of the tasks reach their deadline
which means the set of tasks are schedulable.

This confirms that the Utilisation Bound Test is sufficient but not necessary and in the cases
where the set of tasks passes the test, it will meet all deadline; however, if the test fails,
nothing can be said about that (Burns A and Wellings A, 1996).

Process Release Time Deadline met

Pre-empted Deadline missed

Excecuting
Figure 1: Conventions used for timing diagrams (Buttazzo G C, 1997)

T1

T2

T3

T4
0 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

Figure 2: Timing Diagram for tasks set Question 1) case a)

b)

Computation
Task Period T Utilisation U
Time C
T1 12 3 0.25
T2 15 3 0.20
T3 20 3 0.15
T4 25 3 0.12
Utilisation Bound U(4) 0.72
Table 3: Tasks set Question 1) Case b)

RMIT University © 2007 5 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

In this case the set of task passes the Utilisation Bound Test and this give a certainty that the
set is schedulable and all of the tasks will meet their deadlines. This can be seen in Figure 3

T1

T2

T3

T4
0 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

Time
Figure 3: Timing Diagram for tasks set Question1) case b)

c)

Computation
Task Period T Utilisation U
Time C
T1 12 3 0.25
T2 15 3 0.20
T3 20 5 0.25
T4 25 5 0.20
Utilisation Bound U(4) 0.90
Table 4: Tasks set Question 1) case c)

This case the set fails the Utilization Bound Test. Figure 4 shows its time diagram and as it can
be seen Task 4 misses its first deadline at t = 25, which means that the set of processes is not
schedulable.

T1

T2

T3

T4
0 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

Time
Figure 4: Timing Diagram for tasks set Question1) case c)

Any combination of three processes will pass the Utilisation Bound Test because it would be
less than U(3) = 0.7798.

UT1,T2,T3 = U1 + U2 + U3= 0.70 < 0.7798

UT1,T2,T4 = U1 + U2 + U4 = 0.65 < 0.7798
UT2,T3,T4 = U2 + U3 + U4 = 0.65 < 0.7798
UT1,T3,T4 = U1 + U3 + U4 = 0.70 < 0.7798

RMIT University © 2007 6 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

Figure 5 shows the executing of this set of tasks using the Earliest Deadline First (EDF)
scheduling algorithm. As it can be seen all of the tasks meet their deadline, which means
that using EDF algorithm the set of tasks is schedulable.

T1

T2

T3

T4
0 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

Time
Figure 5: Timing Diagram using EDF scheduling algorithm for tasks set Question 1) case c)

3 Question 2

An embedded system contains the following independent software tasks:

Task M: Alarm Monitoring

A set of 8 alarm sensors are connected to the processor via a slow-speed serial
interface. It takes 75 milliseconds to transmit each individual monitoring transaction (for
one alarm) across the link. The serial link is buffered so a delay in reading a transaction
can be tolerated. Processing each individual monitoring transaction takes 20
milliseconds. The 8 alarms must each be scanned once every second. It is assumed that
the alarms are scanned in sequence.

Task D: Display Driving

A standard monitor is used to display the system status. The display subsystem has a
dedicated graphics board. The display must be updated 25 times per second and it
takes a maximum of 10 milliseconds to perform update.

Task C: Control

The system performs closed-loop control of a multi-axis robot at a rate of 12 Hz, with a
maximum processing time of 15 milliseconds for each loop.

Task L: Data Logging

A data logging process runs four times a second, and takes a maximum of 25
milliseconds each time it runs.

a) Develop a cyclic schedule for scheduling this set of processes. What is the major
cycle period?. What is the minor cycle period?. Give the processes schedule for
one major cycle. Note: The gcd test cannot be used as the task periods are not all
integers.

RMIT University © 2007 7 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

Computation
Task Period T (ms) Utilisation U
Time C (ms)
D 1/24 = 41.67 10 0.24
C (1/24)*2 = 83.33 15 0.18
M (1/24)*3 = 125 20 0.16
L (1/24)*6 = 250 25 0.10
Utilisation Bound U(4) 0.68
Table 5: CPU Utilisation time

The major cycle is MCT = 250 ms.

The minor cycle is mct = 1/24 = 41.667 ms

mct
0 D C
1 D M
2 D C
3 D L
4 D C
5 D M
Figure 6: Timing Sequence. Question 2) part a)

b) How would you allow for an additional aperiodic task (Task A) that has a minimum
period of 200 milliseconds, with an execution time of 12 milliseconds for each
release?.

Computation
Task Period T (ms) Utilisation U
Time C (ms)
D 1/24 = 41.67 10 0.24
C (1/24)*2 = 83.33 15 0.18
M (1/24)*3 = 125 20 0.16
A (1/24)*4.8 = 200 12 0.06
L (1/24)*6 = 250 25 0.10
Utilisation Bound U(4) 0.74
Table 6: Adding a new aperiodic task A (T = 200ms, C = 12ms)

Being A an aperiodic task, it can be inserted at any slot time in 1 and 4. This is shown in the
following figure.

mct
0 D C A
1 D M
2 D C
3 D L
4 D C A
5 D M
Figure 7: New Task (A) added

RMIT University © 2007 8 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007
EEET1262 Real Time Systems Design Scheduling
Assignment 2 Student: Wilson Castillo (s3143667)
Laboratory Report

4 References

Burns A, Wellings A, 1996, Real-Time Systems and Programming Languages, Second Edition,
Addison-Wesley, Harlow, England.
Buttazo G C, 1997, Hard Real-Time Computing Systems. Predictable Scheduling Algorithms
and Applications, Kluwer Academic Publishers, Norwell, USA.
Ferguson R C, 2007, Assignment 2, 2007, EEET1262 Real-Time Systems Design, School of
Electrical and Computer Engineering, RMIT University, Melbourne, Australia.
Ferguson R C, 2007, Real-Time Systems Design, Lecture Notes, School of Electrical and
Computer Engineering, RMIT University, Melbourne, Australia
Tanenbaum A S, 2001, Modern Operating Systems, Second Edition, Prentice Hall, Upper
Saddle River, USA

RMIT University © 2007 9 of 9

School of Electrical and Computer Engineering Melbourne, 14th May, 2007