Integrated Real-Time Resource Scheduling
Group Members:
Motivation
Real-time periodic applications, such as multimedia applications, that utilize
multiple system resources, such as CPU, disks, and network link, require
coordinated scheduling of these resources in order to meet their
end-to-end performance requirements.
While real-time scheduling for a single resource, such as CPU, disk, and network,
has been studied extensively in the real-time, and more recently multimedia
computing community, the issues of efficient resource allocation and
coordinated scheduling of multiple heterogeneous system resources on a
single machine have not received the attention they deserve.
Most state-of-the-art operating systems support at best independent
resource allocation and deadline-driven scheduling for individual resources,
but lack a uniform model to coordinate allocation and scheduling of heterogenous
resources on the same machine.
Integrated Real-Time Resource Scheduling
To address the above issue, we propose an Integrated Real-time
Resource Scheduling (IRS) framework that provides soft real-time
guarantees to applications requiring access to multiple resources.
In the IRS framework, real-time applications
are modeled as a periodic execution of their Task Precedence Graph (TPG).
A TPG is a directed acyclic graph among individual tasks of an application.
Each task in the TPG corresponds to the consumption of a particular resource
and the edges of TPG represent the precedence ordering among tasks.
IRS makes the following specific contributions.
-
The most important component of IRS is a multi-resource allocation and
deadline assignment algorithm. Given the TPG and period of a real-time application,
IRS transparently allocates heterogenous resources and computes delay budget
(deadline per period) for each task under
the constraint that the entire TPG must be completed within one period.
For linear TPGs, we have derived a direct optimal solution to the
delay-budget allocation problem. This optimal solution maximizes the number of
real-time applications admitted into the system.
For non-linear TPGs, i.e., in the case of tasks being related
to each other by a partial order, we have developed an iterative
hueristic algorithm which attempts to achieve close to optimal
delay budget allocation by balancing the relative loads on different resources.
Given the current resource availability in the system,
the algorithm starts by allocating the unused resource
capacity to the tasks of TPG and computes the minimal delay budget
required to complete each task.
These minimal delay budgets are then relaxed
by apportioning the available
slack in delay budget of the TPG according to the load on each resource.
The algorithm stops the relaxation process at a optimal resource
allocation where the TPG can still meet its periodic deadlines. The relaxation
mechanism aims to balance the load among different resources thus allowing more
real-time applications to be admitted into the system in the long term.
-
IRS features a two-level real-time scheduler architecture
which consists of a global scheduler that has a complete knowledge of
each application's task graph and resource requirements,
and a set of local schedulers, each corresponding to
a particular resource. The global scheduler
is responsible for making sure that a task's dependencies
are all satisfied before it is placed in the request queue of the corresponding
resource. Local schedulers manage individual resources
and perform scheduling decisions based on both task deadlines and
resource utilization efficiency. The global scheduler acts as a glue
between local resource schedulers using its global knowledge of task
deadlines and resource requirements for a given application.
-
IRS features a dynamic real-time disk scheduler,
called Deadline Sensitive
SCAN (DSSCAN) that uses the notion of start-time scheduling to greedily optimize for
disk utilization efficiency while satisfying deadlines of all real-time disk requests.
The basic idea of DSSCAN is to maintain two queues - one ordered by start deadlines
and the other ordered by scan positions of requests.
The start deadlines based queue orders requests by the latest time
the requests can be dispatched to the disk and still complete before
their deadline. The DSSCAN scheduler services the next
I/O request in the scan-ordered queue if this would not cause
the request with the earliest start-deadline to miss its deadline. Otherwise,
the scheduler services the disk request with the earliest start-deadline
and then re-arranges the scan-order queue accordingly.
-
Real-time applications are written against an IRS programming API that allows
programmers to specify the resource and timing requirements of the application
as well as precedence constraints among its tasks. The specifications are
declarative in nature and the programmer need not worry about
explicit deadline management in program code.
Current Status
An IRS prototype has been implemented as part of LINUX operating system running on
Intel Pentium-based machines. Real-time applications link to a user-level IRS
library that uses IRS specific system calls to communicate resource requirements
to the OS. An admission controller makes admission decisions and allocates resources
to applications. A global scheduler dispatches tasks from application's TPG to
individual resource schedulers according to their precedence constraints. Real-time
file-system operations allow real-time I/O through disk subsystem. A resource usage
monitor tracks applications' resource usage and provides feedback to applcations.
Publications