Priority inversion in dynamic priority driven scheduling algorithms due to imperfect clock synchronization

Traditionally, networks supporting hard real-time applications such as process control or manufacturing applications use static scheduling policies for message scheduling within the bus. The main reason for that being the fact that for these applications guarantees must be insured by the network. On the other hand, recent works have shown that under certain conditions or limitations in the real-time traffic it is possible to achieve guarantees with dynamic priority driven scheduling algorithms such as earliest deadline first or minimum laxity first. These guarantees are based on what is called schedulability functions. Thus, if a message set fulfils the conditions imposed by the schedulability functions, then its scheduling without missing deadlines is guaranteed. However, one common assumption for calculating the schedulability functions is that clocks of the different nodes are perfectly synchronized. This assumption does not correspond to the reality. In real distributed systems it is not possible to achieve perfect clock synchronization. In this paper, we make a step further in finding schedulability guarantees for dynamic priority driven algorithms used to schedule messages over a bus. In fact, we address the problem that can arise due to the imperfect clock synchronization of local clock of stations. We prove that this lack of clock synchronization can lead to priority inversion and propose a new schedulability test which can be used in such a case