Improvements for Constant-Time Admission Control for DM and EDF Scheduling (Bachelorarbeit)


Ahn Tu Bui


An admission control test is required for a real-time system to decide whether an incoming task could be accepted while the system already has a set of running tasks, so that the whole tasks set including the new one is feasible. For online real-time systems the admission control decisions are to be taken on-line, and, of course, as accurate as possible. There are already many algorithms introduced to fulfill those requirements. In this paper we focus on improvements on admission control tests which were introduced by Dr. Alejandro Masrur, Prof. Samarjit Chakraborty and Dr. Georg Faerber in the year 2010 and 2011 for tasks scheduled on identical processors under partitioned Earliest Deadline First (EDF) and for tasks scheduled under partitioned Deadline Monotonic (DM). We assume the tasks in the case have constraint-deadlines, which means that the relative deadlines of each job may be less than the minimum separation between two consecutive task activations or jobs ( in short tasks with deadlines smaller or equals to their periods ). While the proposed test for DM policy in the publication in 2011 seems to be near-optimal" for tasks set with random tasks and is also the updated of the test proposed in the publication in 2010 for EDF policy, those tests could still be improved more, as described later in this paper. And these tests with improvements are tests with the highest accuracy/complexity ratio we know so far. We evaluate the improvements with the original proposed tests and with other tests with high complexities and the tests with highest accuracies. We use Matlab for the simulations."