REAL TIME OPERATING SYSTEMS

Lesson-16:
Task Scheduling Cooperative Models

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 1
Inc.
 1. Common scheduling models

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 2
Inc.
 Common scheduling models
• Cooperative Scheduling of ready tasks in a
circular queue. It closely relates to function
queue scheduling.
• Cooperative Scheduling with Precedence
Constraints
• Cyclic Scheduling of periodic tasks and Round
Robin Time Slicing Scheduling of equal priority
tasks
• Preemptive Scheduling
• Scheduling using 'Earliest Deadline First' (EDF)
precedence.
Chapter-8 L16: "Embedded Systems - Architecture,
2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 3
Inc.
 Common scheduling models
 Rate Monotonic Scheduling using ‘higher rate of
events occurrence First’ precedence
 Fixed Times Scheduling
 Scheduling of Periodic, sporadic and aperiodic
Tasks
 Advanced scheduling algorithms using the
probabilistic Timed Petri nets (Stochastic) or
Multi Thread Graph for the multiprocessors and
complex distributed systems.

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 4
Inc.
 2. Cooperative Scheduling in the cyclic
order

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 5
Inc.
 Cooperative Scheduling in the cyclic order
 Each task cooperate to let the running task
finish
 Cooperative means that each task
cooperates to let the a running one finish.
 None of the tasks does block in-between
anywhere during the ready to finish states.
 The service is in the cyclic order

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 6
Inc.
 Worst--case latency
Worst

 Same for every task

 Tworst = {(sti + eti )1 + (sti + eti )2 +...+ (sti + eti
)N-1 + (sti + eti )N} + tISR.
 tISR is the sum of all execution times for the ISRs
 For an i-th task, switching time from one task to
another be is sti and task execution time be is eti
 i = 1, 2, …, N 1 , N, when number of tasks = N

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 7
Inc.
 Program counter assignments (switch) at different
times, when the on the scheduler calls the o tasks
from the list one by one in the circular queue from
the list.

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 8
Inc.
 Cyclic scheduling model in tasks scheduling

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 9
Inc.
First three tasks among N- tasks in washing machine
tasks scheduling

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 10
Inc.
 Messages from the scheduler and task programs
contexts at various instances in washing machine
tasks scheduling

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 11
Inc.
 2. Cooperative Scheduling of Ready Tasks
in List

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 12
Inc.
 Cooperative Scheduling in the order in
which a task is initiated on interrupt
 None of the tasks does block in-between
anywhere during the ready to finish states.
 The service is in the order in which a task is
initiated on interrupt.

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 13
Inc.
 Worst--case latency
Worst

 Same for every task in the ready list

 Tworst = {(dti + sti + eti )1 + (dti + sti + eti )2
+...+ (dti + sti + eti )n-1 + (dti + sti + eti )n} + tISR.
 tISR is the sum of all execution times for the ISRs
 For an i-th task, let the event detection time with
when an event is brought into a list be is dti ,
switching time from one task to another be is sti
and task execution time be is eti
 i = 1, 2, …, n 1 , n

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 14
Inc.
 Scheduler in which the scheduler inserts into a list
the ready tasks for a sequential execution in a
cooperative mode

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 15
Inc.
 3. Cooperative Scheduling of Ready Tasks
Using an Ordered List as per precedence
Constraints

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 16
Inc.
 Cooperative Scheduling in the order of
Ready Tasks using an Ordered List as per
priority precedence
 Scheduler using a priority parameter,
taskPriority does the ordering of list of the
tasks─ ordering according to the precedence
of the interrupt sources and tasks.
 The scheduler first executes only the first
task at the ordered list, and the total, equals
the to period taken by the first task on at the
list. It is deleted from the list after the first
task is executed and the next task becomes
the first.
Chapter-8 L16: "Embedded Systems - Architecture,
2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 17
Inc.
Cooperative Scheduling in the order of
Ready Tasks using an Ordered List as
per priority precedence
 The insertions and deletions for forming the
ordered list are made only at the beginning
of the cycle for each list.

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 18
Inc.
 Worst--case latency
Worst
 Not Same for every task. Varies from (dti +
sti + eti ) p(m)} + tISR
to {(dti + sti + eti )p1 + (dti + sti + eti ) p2 +...+ (dti
+ sti + eti ) p(m-1) + (dti + sti + eti ) p(m)} + tISR.
 tISR is the sum of all execution times for the ISRs
 For an i-th task, let the event detection time with
when an event is brought into a list be is dti ,
switching time from one task to another be is sti
and task execution time be is eti
 i = 1, 2, …, m 1 , m; m is number of ISRs and
tasks in the list
Chapter-8 L16: "Embedded Systems - Architecture,
2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 19
Inc.
 Cooperative Priority based scheduling of the ISRs
executing in the first layer and Priority based ready
tasks at an ordered list executing in the second layer

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 20
Inc.
 Program counter assignments at different times on
the scheduler calls to the ISRs and the corresponding
tasks

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 21
Inc.
 Example of ACVM

 First the coins inserted by the user are read,

then the chocolate delivers, and then display
task displays ‘thank you, visit again’
message.
 Each task cooperates with other to finish.
 The precedence of tasks in the ready list─
reading coins is highest, then of chocolate
delivery and display for the ordered list of
the ready tasks.
Chapter-8 L16: "Embedded Systems - Architecture,
2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 22
Inc.
 Summary

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 23
Inc.
We learnt
 Each task cooperate to let the running task
finish in cooperative scheduling model
 Cyclic order
 Cyclic in list of initiated tasks into a ready
list
 Cyclic in ordered list of initiated tasks into a
ready list and list arranged in order of ISR
and task priorities

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 24
Inc.
 End of Lesson 16 of Chapter 8

Chapter-8 L16: "Embedded Systems - Architecture,

2008 Programming and Design" , Raj Kamal, Publs.: McGraw-Hill, 25
Inc.