实时可调度性确定方法和实时系统

摘要

本发明涉及一种用于确定是否能用多个处理器来对多个任务执行实时调度的方法，包括：计算Lk和∑i：整数)；以及如果对于所有k，所有任务都满足条件：∑则确定可以使用处理器来对任务执行实时调度，Lk如下表示：如果Mk≤(M+1)/2，Lk＝(M－Mk+1)－(M－2Mk+1)Ck/Dk；以及Uk，i如下表示：(1)如果Mk≤(M+1)/2，Mi＜(M+1)/2，并且Xk，i≤0，Uk，i＝Ci/Ti{1+(Ti－Di)/Dk}+Ci/Dk；(2)如果Mk≤(M+1)/2，Mi＜(M+1)/2，并且0＜Xk，i＜Ci/Ti，Uk，i＝Ci/Ti{1+(Ti－Di)/Dk}+(Ci－Xk，i*Ti)/Dk；以及(3)如果Mk≤(M+1)/2，Mi＜(M+1)/2，并且Ci/Ti≤Xk，i，Uk，i＝Ci/Ti{1+(Ti－Di)/Dk}，以及Xk，i＝{Mk－Mi+(M－2Mk+1)Ck/Dk}/(M－2Mi+1)。

主权项

1.一种用于确定是否能使用多个处理器来对多个任务执行实时调度的可调度性确定方法，所述方法包括：计算Lk和∑i＝1...NMi*Uk，i(1≤k，i≤N；k，i：整数)，其中Lk对应于任务中包含的一个任务k，Mi表示任务i同时使用的一个或多个处理器的数目，Uk，i对应于任务k和任务i，并且N表示的是任务的数目；以及如果对于所有k，所有任务都满足多个条件：∑i＝1...NMi*Uk，i≤Lk(1≤k≤N)，则确定可以使用处理器来对任务执行实时调度，其中：Lk对应于一个将被检测满足其中一个相应条件的任务k，并且Lk是如下表示的：(1)如果Mk≤(M+1)/2，那么Lk＝(M-Mk+1)-(M-2Mk+1)Ck/Dk；以及Uk，i是如下表示的：(1)如果Mk≤(M+1)/2，Mi＜(M+1)/2，并且Xk，i≤0，那么Uk，i＝Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk；(2)如果Mk≤(M+1)/2，Mi＜(M+1)/2，并且0＜Xk，i＜Ci/Ti，那么Uk，i＝Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk，i*Ti)/Dk；以及(3)如果Mk≤(M+1)/2，Mi＜(M+1)/2，并且Ci/Ti≤Xk，i，那么Uk，i＝Ci/Ti{1+(Ti-Di)/Dk}，其中M表示处理器数目，Ti表示包含在任务中的任务i的时间间隔，Ci表示用于处理任务i的处理时间，Di表示任务i的相对截止期限，以及Xk，i＝{Mk-Mi+(M-2Mk+1)Ck/Dk}/(M-2Mi+1)。