BASIC CONCEPTS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 23

2

BASIC CONCEPTS

2.1 INTRODUCTION

Over the last few years, several algorithms and methodologies have been proposed in
the literature to improve the predictability of real-time systems. In order to present
these results we need to define some basic concepts that will be used throughout the
topic. We begin with the most important software entity treated by any operating
system, the process . A process is a computation that is executed by the CPU in a
sequential fashion. In this text, the term process is used as synonym of task and thread .
However, it is worth saying that some authors prefer to distinguish them and define a
process as a more complex entity that can be composed by many concurrent tasks (or
threads) sharing a common memory space.

When a single processor has to execute a set of concurrent tasks - that is, tasks that
can overlap in time - the CPU has to be assigned to the various tasks according to
a predefined criterion, called a scheduling policy . The set of rules that, at any time,
determines the order in which tasks are executed is called a scheduling algorithm . The
specific operation of allocating the CPU to a task selected by the scheduling algorithm
is referred as dispatching .

Thus, a task that could potentially execute on the CPU can be either in execution (if it
has been selected by the scheduling algorithm) or waiting for the CPU (if another task
is executing). A task that can potentially execute on the processor, independently on
its actual availability, is called an active task. A task waiting for the processor is called
a ready task, whereas the task in execution is called a running task. All ready tasks
waiting for the processor are kept in a queue, called ready queue . Operating systems
that handle different types of tasks may have more than one ready queue.