Scheduling algorithm time complexity

[yuanbin]

Hi!Recently I am studying the implementation of some classical real-time scheduling algorithm, so I read the code about fp and edf in Erika Enterprise. But what make me confused is that in the fp and edf kernel, when activating the task,the kernel just insert the task to an array which make the time complexity of it increasing to O(n).Although in scheduling the extraction of tasks can reduce to O(1), considering the situation that the OS can support dynamic activation of tasks which may make the system unpredictable. How to deal with this? Maybe bitmap algorithm works ?

[paolo.gai]

Hi,

It is correct, FP and EDF, FRSH (and if I'm not wrong, HR) have a O(n) queuing. Also the BCC1, ECC1 have linear queuing.

For FP the choice was simplicity of the implementation.
For EDF the alternative would have been to implement a heap.

BCC1 and ECC1 use linear queuing similar to FP; BCC2 and ECC2 use a bitmap O(1).

Ciao,

PJ

[yuanbin]

Maybe a skip list is a good idea?

[paolo.gai]

not sure how relevant the problem is in reality.

- the number of tasks is often not that high
- an O(1) solution exists
- on many automotive applications the size of the queue at runtime is very limited
- what about the RAM consumption, as well as the time to maintain the list?

Ciao,

PJ