SRI RAMAKRISHNA ENGINEERING COLLEGE

[Educational Service : SNR Sons Charitable Trust]

[Autonomous Institution, Reaccredited by NAAC with ‘A+’ Grade]
[Approved by AICTE and Permanently Affiliated to Anna University, Chennai]
[ISO 9001:2015 Certified and all eligible programmes Accredited by NBA]
VATTAMALAIPALAYAM, N.G.G.O. COLONY POST, COIMBATORE – 641 022.

B.E. ELECTRONICS & COMMUNICATION

ENGINEERING

20EC2E25 – REAL TIME OPERATING

SYSTEMS
Semester : 06 Year : III
Academic Year : 2024-2025
 VISION OF THE COLLEGE
❖ To develop into a leading world class Technological University consisting
of Schools of Excellence in various disciplines with a co-existent Centre
for Engineering Solutions Development for world-wide clientele.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 2

 MISSION OF THE COLLEGE
❖ To provide all necessary inputs to the students for them to grow into
knowledge engineers and scientists attaining.
❖ Excellence in domain knowledge- practice and theory.
❖ Excellence in co-curricular and Extra curricular talents.
❖ Excellence in character and personality.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 3

 VISION AND MISSION OF THE
DEPARTMENT
Vision
• To develop Electronics and Communication Engineers by keeping pace
with changing technologies, professionalism, creativity research and
employability.
Mission
• To provide quality an contemporary education through effective teaching-
learning process that equips the students with adequate knowledge in
Electronics and Communication Engineering for a successful career.
• To inculcate the students in problem solving and lifelong learning skills
that will enable them to pursue higher studies and career in research.
• To produce engineers with effective communication skills, the abilities to
lead a team adhering to ethical values and inclination serve the society.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 4

 Programme Educational
Objectives(PEOs) of the Programme
• The Program Educational Objective (PEOs) of ECE is established through
consultative process. The PEOs of Electronics and Communication
Engineering will demonstrate the following qualities which would be
attained by the graduates after few years of graduation.
• PEO 1 Excel in professional career to provide engineering solution by
demonstrating technical competence and by acquiring knowledge in
electronics and communication engineering.
• PEO 2 Identify, analyze and formulate problems to offer appropriate
design solutions that are technically superior, economically feasible,
environmentally compatible, professionally ethical and socially
acceptable.
• PEO 3 Achieve progress in professional and research career through
communication skills, team work and knowledge up gradation through
higher education.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 5

 Programme Outcomes (POs)
• PO1. Engineering knowledge: Apply the knowledge of mathematics,
science, engineering fundamentals, and an engineering specialization to
the solution of complex engineering problems.
• PO2. Problem analysis: Identify, formulate, review research literature,
and analyze complex engineering problems reaching substantiated
conclusions using first principles of mathematics, natural sciences, and
engineering sciences.
• PO3. Design/development of solutions: Design solutions for complex
engineering problems and design system components or processes that
meet the specified needs with appropriate consideration for the public
health and safety, and the cultural, societal, and environmental
considerations.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 6

 Programme Outcomes (POs)
• PO4. Conduct investigations of complex problems: Use
research-based knowledge and research methods including design of
experiments, analysis and interpretation of data, and synthesis of the
information to provide valid conclusions.
• PO5. Modern tool usage: Create, select, and apply appropriate
techniques, resources, and modern engineering and IT tools including
prediction and modeling to complex engineering activities with an
understanding of the limitations.
• PO6. The engineer and society: Apply reasoning informed by the
contextual knowledge to assess societal, health, safety, legal and cultural
issues and the consequent responsibilities relevant to the professional
engineering practice.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 7

 Programme Outcomes (POs)
• PO7. Environment and sustainability: Understand the impact of the
professional engineering solutions in societal and environmental
contexts, and demonstrate the knowledge of, and need for sustainable
development.
• PO8. Ethics: Apply ethical principles and commit to professional ethics
and responsibilities and norms of the engineering practice.
• PO9. Individual and team work: Function effectively as an individual,
and as a member or leader in diverse teams, and in multidisciplinary
settings.
• PO10. Communication: Communicate effectively on complex
engineering activities with the engineering community and with society
at large, such as, being able to comprehend and write effective reports
and design documentation, make effective presentations, and give and
receive clear instructions.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 8

 Programme Outcomes (POs)
• PO11. Project management and finance: Demonstrate knowledge and
understanding of the engineering and management principles and apply
these to one’s own work, as a member and leader in a team, to manage
projects and in multidisciplinary environments.
• PO12. Life-long learning: Recognize the need for, and have the
preparation and ability to engage in independent and life-long learning in
the broadest context of technological change.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 9

 COURSE OUTCOME
✔ CO1 Explain the concepts of real time systems, scheduling
algorithms and real time databases. PO1, PO12, PS01
✔ CO2 Summarize the MicroC / OS Real Time kernel concepts.
PO1, PO12, PS01
✔ CO3 Interpret FreeRTOS operation and its working concepts.
PO1, PO12, PS01
✔ CO4 Infer the attributes of FreeRTOS and its working
methodology in real time Systems PO1, PO12, PS01

20EC2E25- RTOS RAJASEKAR T, AP/ECE 10

 INTRODUCTION TO REAL TIME
SYSTEM
• Issues in real time computing - Structure of a real time
system - Task classes - Performance measures for real time
systems- Estimating program run times- Task assignment and
scheduling- Classical uniprocessor scheduling algorithms
-Uniprocessor scheduling of IRIS tasks - Task assignment -
Mode changes and Fault tolerant scheduling- Real Time
Databases- Main Memory Databases.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 11

 Micro C/OS REAL TIME KERNEL

• μC/OS - features - Interrupts under μ C/OS- task

Management - Creating - Stack checking stack :Deleting,
requesting, changing, suspending, resuming a task -Time
management- delaying- Resuming a task – Semaphore
management : Creating, deleting, waiting, signalling -
Memory management - Memory control blocks - Creating,
obtaining, returning a memory blocks- Obtaining status of a
memory partitions -Waiting for memory blocks from a
partition.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 12

 FREE RTOS

• Free RTOS Distribution- Creating a Free RTOS Project- Heap

Memory Management- Dynamic Memory All location - Heap
Related Utility Functions - Task Management: Creating Tasks -
Task Priorities -Deleting a Task- Queue Management:
Characteristics of a Queue-Using a Queue

20EC2E25- RTOS RAJASEKAR T, AP/ECE 13

 FREE RTOS ATTRIBUTES

• Interrupt Management: Free RTOSAPI from an ISR- Deferred

Interrupt Processing-Binary and Counting Semaphores-
Interrupt Nesting- Resource Management: Critical Sections
and Suspending the scheduler - Mutexes- Gate keeper Tasks

20EC2E25- RTOS RAJASEKAR T, AP/ECE 14

TEXT BOOKS
1. [Link] and Kang [Link], "Real-Time Systems", 2nd Edition, Tata Mc Graw
Hill Education,2011.
2. Jean [Link], "Micro C/OS- III The Real-Time Kernel", Micrium Press, 2011.
3. Richard Barry,"Using the Free RTOS Real Time Kernel: A Practical Guide", Real
Time Engineers, 2010.
REFERENCES
1. Stuart Bennett, "Real Time Computer Control- An Introduction", 2nd Edition,
Pearson Education, 2011.
2. Jane [Link], "Real-Time Systems", Pearson Education, India, 2012.
3. Rajib Mall, "Real-Time Systems: Theory and Practice", Pearson Education, 2007.
WEBREFERENCES
1. [Link]
2. [Link]
20EC2E25- RTOS RAJASEKAR T, AP/ECE 15
 Real-time System
• A real-time system means that the system is subjected to
real-time, i.e., the response should be guaranteed within a
specified timing constraint or the system should meet the
specified deadline. For example flight control systems,
real-time monitors, etc.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 16

 • Types of real-time systems based on timing constraints:
• Hard real-time system: This type of system can never miss its
deadline. Missing the deadline may have disastrous
consequences. The usefulness of results produced by a hard
real-time system decreases abruptly and may become
negative if tardiness increases. Example: Flight controller
system.
• Soft real-time system: This type of system can miss its
deadline occasionally with some acceptably low probability.
Missing the deadline have no disastrous consequences.
Example: Telephone switches.
•

20EC2E25- RTOS RAJASEKAR T, AP/ECE 17

 • Terms related to real-time system:
• Job: A job is a small piece of work that can be assigned to a
processor and may or may not require resources.
• Task: A set of related jobs that jointly provide some system
functionality.
• Release time of a job: It is the time at which the job
becomes ready for execution.
• Execution time of a job: It is the time taken by the job to
finish its execution.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 18

 • Deadline of a job: It is the time by which a job should finish
its execution. Deadline is of two types: absolute deadline and
relative deadline.
• Response time of a job: It is the length of time from the
release time of a job to the instant when it finishes.
• The maximum allowable response time of a job is called its
relative deadline.
• The absolute deadline of a job is equal to its relative deadline
plus its release time.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 19

 • Processors are also known as active resources. They are
essential for the execution of a job. A job must have one or
more processors in order to execute and proceed towards
completion. Example: computer, transmission links.
• Resources are also known as passive resources. A job may or
may not require a resource during its execution. Example:
memory, mutex

20EC2E25- RTOS RAJASEKAR T, AP/ECE 20

 Real-time computing
• Real-time computing, also known as reactive computing, is
used to describe a computer system that reacts to events by
performing tasks within a specific time interval. The time
frame for these actions to be carried out is in the order of
milliseconds.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 21

 Issues in Real-time System Design
• Realtime Response
• Recovering from Failures
• Working with Distributed Architectures
• Asynchronous Communication
• Race Conditions and Timing

20EC2E25- RTOS RAJASEKAR T, AP/ECE 22

 Realtime Response
• Realtime systems have to respond to external interactions in
a predetermined amount of time. Successful completion of
an operation depends upon the correct and timely operation
of the system. Design the hardware and the software in the
system to meet the Realtime requirements.
• Eg., Telephone switching system

20EC2E25- RTOS RAJASEKAR T, AP/ECE 23

 Realtime response requirements
• Is the architecture suitable? If message communication involves too
many nodes, it is likely that the system may not be able to meet the
Realtime requirement due to even mild congestion. Thus a simpler
architecture has a better chance of meeting the Realtime requirements.
• Are the link speeds adequate? Generally, loading a link more than
40-50% is a bad idea. A higher link utilization causes the queues to build
up on different nodes, thus causing variable amounts of delays in
message communication.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 24

 • Are the processing components powerful enough? A CPU
with really high utilization will lead to unpredictable Realtime
behavior. Also, it is possible that the high priority tasks in the
system will starve the low priority tasks of any CPU time. This
can cause the low priority tasks to misbehave.
• Is the Operating System suitable? Assign high priority to
tasks that are involved in processing Realtime critical events.
Consider preemptive scheduling if Realtime requirements
are stringent. When choosing the operating system, the
interrupt latency and scheduling variance should be verified.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 25

 Recovering from Failures
• Realtime systems must function reliably in event of failures.
These failures can be internal as well as external.
• Internal Failures
• Internal failures can be due to hardware and software
failures in the system.
• different types of failures
• Software Failures in a Task
• Processor Restart
• Board Failure
• Link Failure

20EC2E25- RTOS RAJASEKAR T, AP/ECE 26

 • External Failures
• Realtime systems have to perform in the real world. Thus
they should recover from failures in the external
environment
• Invalid Behavior of External Entities
• Inter Connectivity Failure

20EC2E25- RTOS RAJASEKAR T, AP/ECE 27

 Working with Distributed
Architectures
• Most Realtime systems involve processing on several
different nodes. The system itself distributes the processing
load among several processors. This introduces several
challenges in design:
– Maintaining Consistency
– Initializing the System
– Inter-Processor Interfaces
– Load Distribution
– Centralized Resource Allocation

20EC2E25- RTOS RAJASEKAR T, AP/ECE 28

 Asynchronous Communication
• Remote procedure calls (RPC) are used in computer systems
to simplify software design. RPC allows a programmer to call
procedures on a remote machine with the same semantics as
local procedure calls.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 29

 Race Conditions and Timing
• A race condition occurs when the state of a resource
depends on timing factors that are not predictable. This is
best explained with an example. Telephone exchanges have
two way trunks which can be used by any of the two
exchanges connected by the trunk. The problem is that both
ends can allocate the trunk at more or less the same time,
thus resulting in a race condition. Here the same trunk has
been allocated for a incoming and an outgoing call. This race
condition can be easily resolved by defining rules on who
gets to keep the resource when such a clash occurs. The race
condition can be avoided by requiring the two exchanges to
work from different ends of the pool. Thus there will be no
clashes under low load. Under high load race conditions will
be hit which will be resolved
20EC2E25- RTOS
by the pre-defined rules.
RAJASEKAR T, AP/ECE 30
 Structure of Realtime system

20EC2E25- RTOS RAJASEKAR T, AP/ECE 31

 Scheduling
• Scheduling is the process of deciding which task should be
executed at any point in time based on a predefined algorithm. The
logic for the scheduling is implemented in a functional unit called the
scheduler. The scheduling process is not present only in RTOS, it can
be found in one form or another even in simple “bare-bone”
applications
• Types:
1. Preemptive Scheduling
2. Non-preemptive Scheduling (Co-Operative Scheduling)

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

32
 Scheduling
• Scheduling criteria
• CPU utilization – keep the CPU as busy as possible
• Throughput – # of processes that complete their execution per time unit
• Turnaround time – amount of time to execute a particular process
• Waiting time – amount of time a process has been waiting in the ready
queue and blocked queue
• Response time – amount of time it takes from when a request was
submitted until the first response is produced, not output (for
time-sharing environment)

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

33
 Scheduling
• Optimization Criteria
1. Max CPU utilization
2. Max throughput
3. Min turnaround time
4. Min waiting time
5. Min response time

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

34
 Scheduling
• Type of Process Schedulers
• A scheduler is a type of system software that allows you to handle
process scheduling.

• There are mainly three types of Process Schedulers:

1. Long Term Scheduler

2. Short Term Scheduler
3. Medium Term Scheduler

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

35
 Scheduling
• Long Term Scheduler
• Long term scheduler is also known as a job scheduler. This scheduler
regulates the program and select process from the queue and loads them
into memory for execution. It also regulates the degree of
multi-programing. However, the main goal of this type of scheduler is
to offer a balanced mix of jobs, like Processor, I/O jobs., that allows
managing multiprogramming.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

36
 Scheduling
• Medium Term Scheduler
• Medium-term scheduling is an important part of swapping. It
enables you to handle the swapped out-processes. In this scheduler, a
running process can become suspended, which makes an I/O request.
• A running process can become suspended if it makes an I/O
request. A suspended processes can’t make any progress towards
completion. In order to remove the process from memory and make
space for other processes, the suspended process should be moved to
secondary storage.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

37
 Scheduling
• Short Term Scheduler
• Short term scheduling is also known as CPU scheduler. The main
goal of this scheduler is to boost the system performance according to
set criteria. This helps you to select from a group of processes that are
ready to execute and allocates CPU to one of them. The dispatcher
gives control of the CPU to the process selected by the short term
scheduler.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

38
 Scheduling
• Process State Diagram

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

39
 Scheduling

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

40
 Scheduling
• Types of Scheduling Algorithms
• There are many scheduling algorithms that can be used for
scheduling task execution on a CPU. They can be classified into two
main types: preemptive scheduling algorithms and non-preemptive
scheduling algorithms.
• Preemptive Scheduling
• Preemptive scheduling allows the interruption of a currently
running task, so another one with more “urgent” status can be run. The
interrupted task is involuntarily moved by the scheduler from running
state to ready state. This dynamic switching between tasks that this
algorithm employs is, in fact, a form of multitasking. It requires
assigning a priority level for each task. A running task can be
interrupted if a task with a higher priority enters the queue.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

41
 Scheduling
• Preemptive Scheduling
•

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

42
 Scheduling
• Non-Preemptive Scheduling
• In non-preemptive scheduling, the scheduler has more restricted
control over the tasks. It can only start a task and then it has to wait for
the task to finish or for the task to voluntarily return the control. A
running task can’t be stopped by the scheduler.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

43
 Scheduling
• Popular Scheduling Algorithm
• We will now introduce some of the most popular scheduling
algorithms that are used in CPU scheduling. Not all of them are suitable
for use in real-time embedded systems. Currently, the most used
algorithms in practical RTOS are non-preemptive scheduling,
round-robin scheduling, and preemptive priority scheduling.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

44
 Scheduling
• First Come, First Served (FCFS)
• FCFS is a non-preemptive scheduling algorithm that has no priority
levels assigned to the tasks. The task that arrives first into the
scheduling queue (i.e enters ready state), gets put into the running state
first and starts utilizing the CPU. It is a relatively simple scheduling
algorithm where all the tasks will get executed eventually. The response
time is high as this is a non-preemptive type of algorithm.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

45
 Scheduling
• First Come, First Served (FCFS)
• Process Burst Time
• P1 24
• P2 3
• P3 3
• Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

Waiting time for P1 = 0; P2 = 24; P3 = 27

• Average waiting time: (0 + 24 + 27)/3 = 17

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

46
 Scheduling
• First Come, First Served (FCFS)
• Suppose that the processes arrive in the order
• P2 , P3 , P1 .
• The Gantt chart for the schedule is:

P2 P3 P1

0 3 6 30

• Waiting time for P1 = 6; P2 = 0; P3 = 3

• Average waiting time: (6 + 0 + 3)/3 = 3

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

47
 Scheduling
• Shortest Job First (SJF)
• In the shortest job first scheduling algorithm, the scheduler must
obtain information about the execution time of each task and it then
schedules the one with the shortest execution time to run next.

• SJF is a non-preemptive algorithm, but it also has a preemptive

version. In the preemptive version of the algorithm (aka shortest
remaining time) the parameter on which the scheduling is based is the
remaining execution time of a task. If a task is running it can be
interrupted if another task with shorter remaining execution time enters
the queue.

• A disadvantage of this algorithm is that it requires the total execution

time of a task to be known before it is run.
RAJASEKAR T, AP/ECE 20EC2E25- RTOS
48
 Scheduling
• Shortest Job First (SJF)- Non-Preemptive
• Process Arrival Time Burst Time
• P1 0.0 7
• P2 2.0 4
• P3 4.0 1
• P4 5.0 4

P1 P3 P2 P4

0 3 7 8 12 16

• Average waiting time = (0 + 6 + 3 + 7)/4 = 4

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

• 49
 Scheduling
• Shortest Job First (SJF)- Preemptive
• Process Arrival Time Burst Time
• P1 0.0 7
• P2 2.0 4
• P3 4.0 1
• P4 5.0 4
P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

• Average waiting time = (9 + 1 + 0 +2)/4 = 3

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

• 50
 Scheduling
• Priority Scheduling
• Priority scheduling is one of the most popular scheduling
algorithms. Each task is assigned a priority level. The basic principle is
that the task with the highest priority will be given the opportunity to
use the CPU.
• In the preemptive version of the algorithm, a running task can be
stopped if a higher priority task enters the scheduling queue. In the
non-preemptive version of the algorithm once a task is started it can’t
be interrupted by a higher priority task.
• Of course, not all tasks can have unique priority levels and there
will always be tasks that have the same priority. Different approaches
can be used for handling the scheduling of those tasks (e.g FCFS
scheduling or round-robin scheduling).
•
RAJASEKAR T, AP/ECE 20EC2E25- RTOS
51
 Scheduling
• Priority Scheduling
•

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

52
 Scheduling
• Priority Scheduling
• Advantages of priority scheduling
✔ Easy to use scheduling method
✔ Processes are executed on the basis of priority so high priority does not
need to wait for long which saves time
✔ This method provides a good mechanism where the relative important of
each process may be precisely defined.
✔ Suitable for applications with fluctuating time and resource
requirements.
•

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

53
 Scheduling
• Priority Scheduling
• Disadvantages of priority scheduling
✔ If the system eventually crashes, all low priority processes get lost.
✔ If high priority processes take lots of CPU time, then the lower priority
processes may starve and will be postponed for an indefinite time.
✔ This scheduling algorithm may leave some low priority processes
waiting indefinitely.
✔ A process will be blocked when it is ready to run but has to wait for the
CPU because some other process is running currently.
✔ If a new higher priority process keeps on coming in the ready queue,
then the process which is in the waiting state may need to wait for a long
duration of time.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

54
 Scheduling
• Round-Robin Scheduling
• Round-robin is a preemptive type of scheduling algorithm. There
are no priorities assigned to the tasks. Each task is put into a running
state for a fixed predefined time. This time is commonly referred to as
time-slice (quantum). A task can not run longer than the time-slice.
• In case a task has not completed by the end of its dedicated
time-slice, it is interrupted, so the next task from the scheduling queue
can be run in the following time slice. A pre-emptied task has an
opportunity to complete its operation once it’s again its turn to use a
time-slice.

• An advantage of this type of scheduling is its simplicity and relatively

easy implementation
•
RAJASEKAR T, AP/ECE 20EC2E25- RTOS
55
 Scheduling
• Round-Robin Scheduling
•

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

56
 Scheduling
• Round-Robin Scheduling
• Advantages-
✔ It gives the best performance in terms of average response time.
✔ It is best suited for time sharing system, client server architecture and
interactive system.
•
•Disadvantages-
✔ It leads to starvation for processes with larger burst time as they have to
repeat the cycle many times.
✔ Its performance heavily depends on time quantum.
✔ Priorities can not be set for the processes.

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

57
 Scheduling
• Round-Robin Scheduling
•
Ready Queue-
P5, P1, P2, P5, P4, P1, P3, P2, P1

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

58
 Scheduling
• Round-Robin Scheduling
•

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

59
 Scheduling
• Round-Robin Scheduling
• Ready Queue-
P5, P6, P2, P5, P6, P2, P5, P4, P1, P3, P2, P1

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

60
 Scheduling
• Round-Robin Scheduling
•

RAJASEKAR T, AP/ECE 20EC2E25- RTOS

61
20EC2E25- RTOS RAJASEKAR T, AP/ECE 62
20EC2E25- RTOS RAJASEKAR T, AP/ECE 63
 Task Classes
• Classified in 2 ways
– By the predictability of their arrival
– By the consequences of their not being executed on time.
– Periodic & Aperiodic tasks.
• Periodic – Repetitive tasks
• Aperiodic – occasionally occurred tasks
• Aperiodic tasks with a bounded interarrival time –
Sporadic tasks
– Critical & Non-critical tasks (Hard & Soft realtime
systems)

20EC2E25- RTOS RAJASEKAR T, AP/ECE 64

 Performance measures for RTS
• Properties of performance measures
– Represent an efficient encoding of relevant information.
– Provide an objective basis for the ranking of controllers
for application
– Provide objective optimization criteria for design
– Represent verifiable facts.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 65

 Efficient encoding
• Explains how the system handles large volume of data.
• Makes the specifications more precise & cost effective.
• Describes both hardware and software specifications

20EC2E25- RTOS RAJASEKAR T, AP/ECE 66

 Objective basis for ranking
• Performance requirement for the application must be
satisfied by the processor/controllers.
• Ranking of the hardware resource must be accurate and
optimized with application.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 67

 Objective optimization criteria
• More complex system more difficult to optimize.
• Eg., Multiprocessor system.
• The design should reconfigure itself with respect to changes
in the environment both internal & external.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 68

 Verifiable facts
• For low probability and less feasible systems, it is necessary
to decide based on facts.
• Also if the accuracy is too low, based on the facts and results
of previous systems taken into consideration for better
improvement.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 69

 Uniprocessor scheduling algorithms

• Traditional rate-monotonic(RM)
• Rate-monotonic deferred server (DS)
• Earliest deadline first (EDF)
• Precedence and exclusion conditions
• Multiple task versions
• IRIS (Increased reward with increased service)
tasks

20EC2E25- RTOS RAJASEKAR T, AP/ECE 70

 Multiprocessor scheduling
• Utilization balancing algorithm
• Next-fit algorithm
• Bin-packing algorithm
• Myopic-offline scheduling algorithm
• Focused Addressing and bidding algorithm
• Buddy strategy
• Assignment with precedence constraints

20EC2E25- RTOS RAJASEKAR T, AP/ECE 71

 Rate-monotonic scheduling
• Introduced by Liu and Layland
• RMS is a static scheduling policy because it
assigns fixed priorities to processes.
• Rate-monotonic analysis (RMA)
– All processes run periodically on a single CPU.
– Context switching time is ignored.
– There are no data dependencies between processes.
– The execution time for a process is constant.
– All deadlines are at the ends of their periods.
– The highest-priority ready process is always selected
for execution.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 72

 • Priorities are assigned by rank order of
period, with the process with the shortest
period being assigned the highest priority.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 73

 TABLE

20EC2E25- RTOS RAJASEKAR T, AP/ECE 74

 • Applying the principles of RMA, we give P1 the
highest priority, P2 the middle priority, and P3 the
lowest priority.
• To understand all the interactions between the
periods, we need to construct a timeline equal in
length to the least-common multiple of the
process periods, which is 12 in this case.
• The complete schedule for the least-common
multiple of the periods is called the unrolled
schedule.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 75

20EC2E25- RTOS RAJASEKAR T, AP/ECE 76
• All three periods start at time zero.
• P1’s data arrive first. Because P1 is the highest priority process, it can start
to execute immediately.
• After one time unit, P1 finishes and goes out of the ready state until the
start of its next period.
• At time 1, P2 starts executing as the highest-priority ready process.
• At time 3, P2 finishes and P3 starts executing. P1’s next iteration starts at
time 4, at which point it interrupts P3.
• P3 gets one more time unit of execution between the second iterations of
P1 and P2, but P3 doesn’t get to finish until after the third iteration of P1.
• Consider the following different set of execution times for these processes,
keeping the same deadlines.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 77

20EC2E25- RTOS RAJASEKAR T, AP/ECE 78
 CPU utilization
• The total CPU utilization for a set of n tasks is

• It is possible to show that for a set of two tasks

under RMS scheduling, the CPU utilization U will
be no greater than 2(21/2 - 1) =0.83.
• In other words, the CPU will be idle at least 17%
of the time.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 79

 • When there are m tasks, the maximum
processor utilization is

• As m approaches infinity, the CPU utilization

asymptotically approaches ln 2 = 0.69— the
CPU will be idle 31% of the time. We can use
processor utilization U as an easy measure of
the feasibility of an RMS scheduling problem.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 80

 Shared resources
• Critical sections
• Semaphores
– The semaphore is used to guard a resource.
– The semaphore names are, by tradition, P() to
gain access to the protected resource and V() to
release it.
• /* some nonprotected operations here */
• P(); /* wait for semaphore */
• /* do protected work here */
• V(); /* release semaphore */

20EC2E25- RTOS RAJASEKAR T, AP/ECE 81

 Priority inversion
• Shared resources cause a new and subtle
scheduling problem: a low-priority process
blocks execution of a higher-priority process
by keeping hold of its resource, a
phenomenon known as priority inversion.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 82

 Priority inheritance
• The most common method for dealing with
priority inversion is priority inheritance: promote
the priority of any process when it requests a
resource from the operating system.
• The priority of the process temporarily becomes
higher than that of any other process that may
use the resource.
• Once the process is finished with the resource, its
priority is demoted to its normal value.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 83

 Earliest-deadline-first scheduling
• Earliest deadline first (EDF) is another well-known scheduling
policy that was also studied by Liu and Layland [Liu73].
• It is a dynamic priority scheme—it changes process priorities
during execution based on initiation times.
• As a result, it can achieve higher CPU utilizations than RMS.
• The EDF policy is also very simple: It assigns priorities in order of
deadline.
• The highest-priority process is the one whose deadline is nearest
in time, and the lowest priority process is the one whose deadline
is farthest away.
• Clearly, priorities must be recalculated at every completion of a
process.

20EC2E25- RTOS RAJASEKAR T, AP/ECE 84

20EC2E25- RTOS RAJASEKAR T, AP/ECE 85
20EC2E25- RTOS RAJASEKAR T, AP/ECE 86
20EC2E25- RTOS RAJASEKAR T, AP/ECE 87
 RMS vs EDF
RMS EDF
Achieves lower CPU Higher CPU utilization
utilization
easier to ensure that all Hard to ensure deadlines
deadlines will be
satisfied
Static priority scheduling dynamic priority scheduling

Not expensive to use in Expensive to use in practice

practice
shortest-period process gets Process closest to its deadline
20EC2E25- RTOS RAJASEKAR T, AP/ECE 88
highest priority has highest priority.
 THANK YOU

20EC2E25- RTOS RAJASEKAR T, AP/ECE 89