非抢占式周期任务调度难题研究及高效算法

本文主要探讨了一类特殊的非抢占式周期任务的调度方法，针对现实世界中多任务资源分配和使用的时间敏感性，这类问题在当前的研究中相对较少。研究者首先定义了这类任务的特点，它们通常涉及单处理器实时系统的多个任务，每个任务都有特定的开始时间、执行时间和截止时间约束。周期任务调度问题在计算机工程领域是热门研究课题，Liu和Layland的模型区分了静态调度和动态调度，其中RM算法和EDF算法是常见策略，前者基于周期优先级，后者优先处理截止期最早的任务。 然而，本文关注的是非抢占式调度问题，这种情况下，一旦任务开始执行，就不能被其他优先级更高的任务中断，这使得问题复杂化，已被证明为NP完全问题。相比于可抢占式调度，非抢占式调度的条件更为严格，得到的可调度性往往是必要的，而非充分的。尽管如此，学者们还是针对实际应用中的挑战提出了相应的解决方案，例如在控制系统中，这类特殊的非抢占式周期任务调度方法显得尤为重要。 论文的核心贡献在于提出了一种新的非抢占式周期任务调度模型，并证明了其理论基础。为了解决这个问题，研究者设计了一种模式剪枝算法，用于寻找最优解，以及一种快速求解算法，以应对实际应用中的近似解需求。通过实验验证，这两种算法能够在满足不同场景需求的同时，有效提升调度问题的解决效率。 研究者李智翔、李赟和贺亮来自中国成都的盲信号处理重点实验室，他们的工作不仅填补了非抢占式周期任务调度问题研究的空白，也为实际的单处理器实时系统设计提供了实用的理论依据和技术手段。本文的工作对于理解和优化实时系统中的资源管理和任务调度具有重要意义，为未来相关领域的进一步研究奠定了坚实的基础。