Real-Time Scheduling and Virtualization Techniques

Since most embedded systems have to meet deadlines, real-time scheduling techniques become necessary. At RCS, we investigate in different directions towards scheduling techniques that not only allow meeting deadlines, but also a more efficient use of computational resources. Moreover, in line with a consolidation trend in industry, the use of virtual machines to provide for isolation between applications is gaining in importance. This brings up new and interesting research questions concerning how to design and schedule virtualized embedded systems in an efficient manner.

Virtualization in Embedded Systems

Traditionally, different functionalities or applications in the automotive domain are implemented on different electronic control units (ECUs). This has led to a large number of ECUs in modern cars, which increases cost and leads to wiring complications. As a result, lately there is an increasing focus on integrating multiple applications on a single ECU, along with a VM layer to provide isolation between them.

The work we conduct follows this direction with the aim of supporting a mix of hard-real-time control applications with non- or soft-real-time (e.g., multimedia) applications on a commodity VM. In particular, we use the Xen hypervisor, an available open-source VM monitor, and analyze its behavior in the context of real-time applications. We are further concerned with the design of VM schedulers, i.e., how to configure time slices and periods for every VM in the system such that all real-time tasks running on them can meet their deadlines.

The picture here shows the response time of an application running within a VM. The green line shows the application's response time when this does not share the VM with any other application. The red line shows the case where the VM is being shared by multiple applications. Interestingly, scheduling only one application per VM allows utilizing the processor time more efficiently; however, it demands more memory and it is hence less practical. With respect to response time, in case of overload, there is no difference between whether the application runs alone or not.

Admission Control

In many real-time systems such as modern games, multimedia or communication servers, etc., tasks have to be accepted or rejected on-line based on whether it is possible to schedule them or not. The algorithm responsible for testing the schedulability of a new task in a system is normally referred to as admission control test and requires a fast and predictable running time.

The computational complexity of an admission control test depends not only on the used task model, but also on the system architecture. As an admission control algorithm for multiprocessors has to deal with allocating tasks to processors, which is known to be NP-hard in the strong sense, we need to use approximation techniques.

Goal of this project is to develop approximation techniques that allow for sophisticated task models and, at the same time, a low complexity. In particular, we are interested in constant complexity since the running time of the resulting algorithm will not depend on the number of tasks already accepted in the system. 

The curves to the left show the performance of different algorithms for admission control. The exact test takes always the right decision, in the sense that it rejects a task only if this would produce a deadline miss. All other tests are approximations and might reject some tasks that could have been scheduled without deadline misses. On the other hand, the exact test is quite complex (pseudo-polynomial) such that it takes longer to run. All the other tests in the picture have a constant complexity. The load test, the uniform-interval and the non-uniform-interval test were developed at RCS and outperform the other tests from the literature.


Michael Balszun