On the efficient scheduling of non-periodic tasks in hard real-time systems
On the efficient scheduling of non-periodic tasks in hard real-time systems
复制标题
硬实时系统中非周期性任务的高效调度
DOI：
10.1109/real.1999.818836
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Jyh
中科院分区：
文献类型：
--
作者：
M. Thomadakis;Jyh
提出了在固定优先级实时系统中保证和联合调度固定非周期、硬零星和周期任务的线性时间在线算法。我们开发并利用了一种方法，该方法精确地计算任意调度间隔(a，b)的空闲容量Z(a，b)的时间/SPL Theta/(N)，据我们所知，这是文献中报道的第一个线性时间算法。以前的技术水平的方法导致伪多项式时间来保证在线的单个非周期性，并且产生用于松弛维护的连续开销。我们的方法保证并调度固定任务以接收FIFO或EDF服务，分别产生/SPL Theta/(N)和/SPL Theta/(n+k)的一次性线性成本，其中k是未决的固定任务的数量。
The paper presents linear time, online algorithms which guarantee and jointly schedule firm aperiodic, hard sporadic and periodic tasks in fixed priority real time systems. We develop and capitalize on a methodology which computes the spare capacity Z(a,b) exactly in time /spl Theta/(n), for arbitrary schedule intervals (a,b), which, to the best of our knowledge, is the first linear time algorithm reported in the literature. Previous state of the art methods incur pseudopolynomial time to guarantee online a single aperiodic and incur continuous overhead for slack maintenance. Our method guarantees and schedules firm tasks to receive FIFO or EDF service, incurring a one-time linear cost of /spl Theta/(n) and /spl Theta/(n+k) respectively, where k is the number of pending firm tasks.