Description

In many real-time systems such as modern games, multimedia/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. 

Contact

Alejandro Masrur