Real-time schedulability determination method and real-time system

摘要

Schedulability determination method of determining whether real-time scheduling of tasks is possible using processors, includes calculating Lk and Σ_{i=1 . . . N}Mi*Uk, i, (1≦k, i≦N; k, i: integer) where Lk corresponds to task-k, Mi represents number of the one or more processors simultaneously used by task-i, Uk, i corresponds to task-k and task-i, and N represents number of tasks, and determining that real-time scheduling of tasks is possible using processors, if tasks all satisfy conditions, Σ_{i=1 . . . N}Mi*Uk, i≦Lk for all k (1≦k≦N), wherein Lk corresponds to task-k which is to be detected to satisfy corresponding one of conditions, Lk being expressed as followsif Mk≦(M+1)/2,Lk=(M−Mk+1)−(M−2Mk+1)Ck/Dk, and;Uk, i is expressed as followsif Mk≦(M+1)/2, Mi(M+1)/2, and Xk, i≦0,  (1)Uk, i=Ci/Ti{1+(Ti−Di)/Dk}+Ci/Dk, if Mk≦(M+1)/2, Mi(M+1)/2, and 0Xk, iCi/Ti,  (2)Uk, i=Ci/Ti{1+(Ti−Di)/Dk}+(Ci−Xk, i*Ti)/Dk, andif Mk≦(M+1)/2, Mi(M+1)/2 and Ci/Ti≦Xk, i,  (3)Uk, i=Ci/Ti{1+(Ti−Di)/Dk}, where M represents number of processors, Ti represents interval of task-i, Ci represents process time for processing task-i, Di represents relative deadline of task-i, and Xk, i={Mk−Mi+(M−2Mk+1)Ck/Dk}/(M−2Mi+1).