Page 73 - DCAP608_REAL TIME SYSTEMS

Real Time Systems Sandeep Kumar, Lovely Professional University

Notes Unit 7: Commonly used Algorithm to
Real-time Scheduling

CONTENTS
Objectives
Introduction

7.1 Real-time Scheduling
7.1.1 Interrupts and Tasks
7.2 Effective Release Time and Deadlines
7.3 Optimality of the EDF and LST Algorithm

7.4 Non-optimality of the EDF and LST Algorithm
7.5 Summary
7.6 Keywords
7.7 Review Questions

7.8 Further Readings
Objectives

After studying this unit, you will be able to:
 Describe Real-time Scheduling
 Enumerate Effective Release Time and Deadlines

 Explain Optimality of the EDF and LST Algorithm
 Analyse Non-optimality of the EDF and LST Algorithm

Introduction

The use of computers to control safety-critical real-time functions has increased rapidly over the
past few years. As a consequence, real-time systems — computer systems where the correctness
of a computation is dependent on both the logical results of the computation and the time at
which these results are produced — have become the focus of much study. Since the concept of
“time” is of such importance in real-time application systems, and since these systems typically
involve the sharing of one or more resources among various contending processes, the concept
of scheduling is integral to real-time system design and analysis. In this unit, we will discuss
commonly used Algorithm to Real-time Scheduling.

7.1 Real-time Scheduling

A real-time operating system is a system that schedules execution of tasks in a timely deterministic
manner, and is scalable.
The scheduler follows a set of algorithms that determine which task executes at each moment.
Preemptive priority-based scheduling is a mandatory property of the operating system we

68 LOVELY PROFESSIONAL UNIVERSITY