Invited Session Mon.2.H 3010

Monday, 13:15 - 14:45 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Real-time scheduling


Chair: Sanjoy Baruah



Monday, 13:15 - 13:40 h, Room: H 3010, Talk 1

Martin Niemeier
Scheduling with an orthogonal resource constraint

Coauthor: Andreas Wiese


We address a type of scheduling problems that arises in highly parallelized environments like modern multi-core CPU/\allowbreak GPU computer architectures. Here simultaneously active jobs share a common limited resource, e.g., a memory cache. The scheduler must ensure that the demand for the common resource never exceeds the available capacity. This introduces an orthogonal constraint.
Almost any scheduling problem can be made "resource aware'' by adding this constraint.
Here we focus on two classes of scheduling problems.
On the one hand, we study "classical'' makespan minimization problems
such as scheduling on identical machines. On the other hand, we study
real-time scheduling problems (e.g., partitioned scheduling of synchronous/\allowbreak sporadic tasks on parallel multi-processors).
We present approximation algorithms (either in terms of makespan minimization or machine-speedup minimization) for several variants of the problem.



Monday, 13:45 - 14:10 h, Room: H 3010, Talk 2

Suzanne van der Ster
Mixed-criticality scheduling of sporadic task systems on a single machine

Coauthors: Sanjoy K. Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Leen Stougie


We consider scheduling an implicit-deadline task system on a single machine in a mixed-criticality (MC) setting. MC systems arise when multiple functionalities are scheduled upon a shared computing platform. This can force tasks of different importance (i.e., criticality) to share a processor.
Each task generates a (possibly infinite) string of jobs, released with an interarrival time bounded from below by a task-dependent period. Each job has a relative deadline equal to the length of its period.
In an MC setting, each task has multiple levels of worst-case execution times and its own criticality level. By executing the tasks, we learn what level the system is in, which may change over time. When the system is in level l, all jobs of tasks of level l should be scheduled for their level-l execution time, to meet their deadline.
We give an algorithm for scheduling an MC task system, called EDF-VD (Earliest Deadline First with Virtual Deadlines). We give sufficient conditions to check feasibility for K levels. We show that if a 2-level task system is schedulable on a unit-speed processor, it is correctly scheduled by EDF-VD on a processor of speed 4/3.



Monday, 14:15 - 14:40 h, Room: H 3010, Talk 3

Jian-Jia Chen
Resource augmentation in real-time systems

Coauthor: Samarjit Chakraborty


Timing satisfaction is an important property for maintaining the stability or correctness of many real-time embedded systems, especially for avionic or automotive applications. For decades, schedulability of real-time systems has been extensively studied, from periodic tasks, to sporadic tasks, and even to tasks with irregular arrival curves. A task set is guaranteed to be schedulable if it passes the correct schedulability tests. However, the main issue for such an approach is to answer what can be guaranteed when a task set does not pass the schedulability test. For such cases, the resource augmentation factor provides a nice feature to ensure the schedulability by augmenting the resources, e.g., by speeding-up, adding more processors, etc. This talk will focus on the recent
researches on resource augmentation with respect to speeding-up and allocating more processors in real-time systems for sporadic real-time tasks, from uniprocessor systems to multiprocessor systems. The analysis for resource augmentation upper bound and lower bound will be presented.


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.