Is this algorithm an existing real-time system algorithm?

Question

I have developed a scheduling algorithm that provides probabilistic soft real-time guarantees, but it seems too obvious and simple to be novel. I have had a hard time though relating it to published real-time scheduling algorithms (EDF, sporadic server, etc.). Is the following scheduling algorithm a known real-time algorithm?

Assumptions:

• All tasks are drawn from a distribution where X percentage of tasks require fewer than R cpu-seconds
• All tasks have the same deadline. If a task takes longer than T seconds, then it is a failure for that task
• Task arrivals are separated by a known minimum inter-arrival time, MIN_INTER_ARRIVE_T
• The scheduler has a taskset which can hold a maximum of H tasks at any time (during every time step, all tasks in the taskset make equal progress by sharing the CPU equally)
• Tasks cannot affect each other

Guarantee:

• (1) If X percentage of tasks require fewer than R cpu-seconds and (2) R <= T/H, (3) MIN_INTER_ARRIVE_T >= T/H, then at least X percentage of tasks will finish within T seconds

Algorithm:

• If a task arrives and the taskset is full, then evict the task that has used the most CPU. The assumptions guarantee that such a task will have used at least R cpu-seconds. So the only tasks that can be evicted will be tasks that are failures anyway. Any task that requires fewer than R cpu-seconds will complete on time.

Answer 1

I'm not an expert in hard real-time scheduling, but this is what your algorithm sounds like to me.

It bears very strong resemblance with what happens in aerospace systems. Your system looks more flexible, but basically it all grinds down to knowing in advance that you have the resources to run the tasks that you need to run.

Critical embedded aerospace systems prefer to be deterministic, but as a protection against potential flaws (tasks can run longer than allocated, if let), the tasking engine will interrupt those tasks to let other taks complete. Any free cycle left can sometimes be used to complete the interrupted tasks, or the task is deemed to have failed.

Note that you can only fail tasks that are not critical, so you must construct your critical tasks carefully, or have a priority system whereby critical tasks have a chance to complete no matter what.

You're now back to square one: you need to make sure that the ressources are sufficient to run the tasks required in advance.

hth,
asoundmove.