论文部分内容阅读
并发实时系统指多处理器环境下有实时要求的并发计算系统。本文第一章中介绍了一般实时系统的发展。实时系统领域的研究者通常考虑有周期性截止期的任务,任务调度问题是实时系统研究的重点,这一领域的研究成果包括有效的调度算法及相关定理,如著名的Liu-layland定理。在第二章中我们引入空间因素,提出了扩充的多处理器实时系统,建立了有空间限制的并发实时系统的模型。在这个模型中,每个任务Pi的运行需要一定的空间（ ）νi t（这个空间可以是常量或变量）,但所提供的空间的总量D是有限的。在这一框架下,我们能清楚地刻画并行和并发,而且能获得有效的调度算法。在第三章中我们讨论并行模型,运用时段演算、分离逻辑的语言给出并行模型的形式化描述。若对（?）i , （1≤i≤m）,νi（t）都是关于t的常数函数,即,我们得到了一个并行模型。Pi的空间需求为。引入空间可分离的概念:,如果∑rj≤1,j∈Δ,则Δ称之为空间可分离的,记为Δs。记,考虑一个分段函数f （t）, f （t）满足对。每一个已给定的f （t）将时间轴上的每个时间段与一个可空间分离的任务集对应。即每个给定的f （t）以及相应的fi（t）对应了一个任务调度表。由此得到如下定理:定理3.1对于实时并行模型,存在一个有效调度的充要条件是存在一个定义在[ 0,1]的分段函数F （ t ）使得:且对,定义在第四章中我们讨论并发模型。当任务Pi占用的空间vi （ t ）是变量时,我们就得到并发模型。建立简单的并发模型LCM:令|D|=1,k是一个固定的正整数,且k≥2。对每个是Pi在第j个请求周期内的运行时段, j∈H。假设对每个Pi ,在时间段内从不间歇。vi （t）是如下定义的动态函数:Pi在时段内的时空占用量定义为,我们的目标是找到一个有效的算法使时空利用率rat尽可能大。考虑下面一个算法（贪心算法）:①当t = 0时,我们在开始时刻运行k个任务。②每个进程一旦运行就直至完成才结束。③当且仅当1k的空间被释放,我们才让另一个任务切入进来并开始运行。我们采用MAPLE环境编程。根据程序输出的结果,猜测LCM在贪心算法的调度下,时空利用率的上界是。由此提出猜想:定理4.1对于并发模型LCM,是任意一个有效的调度算法∑（ t）的时空利用率的上界。鉴于贪心算法将导致复杂的并发进程控制,我们提出了循环算法:①当t = 0,仅让一个任务P1运行。②当时, n是正整数,0 < n < 2 k-1,开始一个新的任务Pn +1。③当t = 1时,任务P1的进程结束,且正好有1k的空间空余出来,同一时刻任务P1的进程再次被切入,将所有空间填满。④当时, n是任意正整数,恰有一个进程结束,并有k1的空间空余出来,使得一个新的任务切入。受循环算法启发,尝试以进程代数的语言给出一种简单的时间自动机的形式化描述。