带空间限制的实时多处理器系统调度研究

发布时间：2020-09-19 08:29

　　实时多处理器系统作为一个数学模型,它刻画表达和反映自然界、人类社会中大量、广泛的实际问题,在现实生活的各个领域中有广泛的应用,而与其相应的任务调度理论研究则成为实时系统研究的一个重要课题。当前对实时多处理器系统调度理论的研究很少考虑到空间的约束,但在许多实际问题中,空间都是一个不可回避的因素。文献[6-8]将空间因素引入到实时多处理系统中,首次提出了带空间限制的实时多处理器系统调度模型。论文则是在这个模型框架下针对任务占用空间情况重点研究了实时并行模型、线性并发模型,非线性并发模型的调度算法性能,时空利用率等性质。论文研究工作主要集中在以下方面：针对已有文献提出的实时并行模型中主调度算法与全局调度算法存在的不足：(1)在划分极大相容组时,忽略了问题的实时性,没有保证重要任务的优先调度,任务的时间限有可能得不到满足；(2)在同一极大相容组中,有可能因各个任务的Ci／Ti值相差较大,从而导致调度时系统的利用率较低,论文提出了一种与文献[7]思路不同的调度算法,即基于EDF的优先级驱动调度算法,该算法很好的解决了文献[7]的调度算法的不足。从算法调度成功率以及时空利用率等方面考虑并经过实例分析,得出该算法明显优于文献[7]的调度算法,而且得出结论只要文献[7]的算法能调度的任务集,则论文提出的调度算法一定能调度。针对文献[6]提出的LCM并发模型,对贪心算法与循环算法的性质作进一步的研究,得到并证明了定理：基于LCM模型的贪心算法与循环算法调度,它们的时空利用率均可达到(2k-1)/(2k)。该定理在理论研究上有一定价值。针对任务pi的空间占用函数di(t)的多样性以及di(t)为抛物线下降情形的典型性,论文提出了PCM并发模型并对该模型的时空利用率及相应的贪心算法性质作了初步研究,得到如下结论：定理5.2.1对于PCM下GA算法,对任意k≥2,k∈N,系统的时空利用率eG=(2k-1)/(2k) 定理5.2.2对于PCM下GA算法,对任意k≥2,k∈N,系统同时运行任务个数平均为：定理5.2.3对于PCM下GA算法,对任意k≥2,k∈N,当经过一定的时间时,系统趋于稳定,即每隔一个固定的时间,系统切入一个任务,记住个时间间隔为t0,则有：定理5.3.1 (2k-1)/(2k)是所有PCM模型中有效调度的时空利用率的上界。
【学位单位】：广西师范大学
【学位级别】：硕士
【学位年份】：2010
【中图分类】：TP332

【参考文献】