检索结果-内蒙古大学图书馆

计算机研究与发展 2001年第9期38卷 1097-1104页

作者：许何赵建华李宣东郑国梁南京大学软件新技术国家重点实验室南京210093 南京计算机科学与技术系南京210093

介绍了一个就线性时段特性验证实时系统正确性的工具的设计思想以及相关算法 .使用时间自动机作为实时系统的描述模型 .同时 ,为了便于描述并发实时系统 ,使用带共享变量和通道的时间自动机网作为模型描述并发实时系统 .在检验时间自动... 详细信息

介绍了一个就线性时段特性验证实时系统正确性的工具的设计思想以及相关算法 .使用时间自动机作为实时系统的描述模型 .同时 ,为了便于描述并发实时系统 ,使用带共享变量和通道的时间自动机网作为模型描述并发实时系统 .在检验时间自动机网时 ,用户可以使用工具提供的合成程序将其合并为一个时间自动机然后进行检验 .由于时间自动机的状态空间是无穷的 ,通过引入整数状态和状态等价关系的概念 ,将整个状态空间划分为有限的状态等价类空间 .模型检验过程只需要通过对等价类空间的搜索就可以完成 .但往往等价类空间的规模很大 ,超出了现在计算机的处理能力 ,原始搜索算法仅仅在理论上是可行的 .为了增强工具的使用性 ,工具中使用的算法运用了一些优化技术来避免对等价类空间的穷尽搜索 ,使得工具在使用时具有比较好的时间和空间效率 .

关键词：形式化方法时间自动化自动验证并发实时系统线性时段性质

来源：评论

学校读者我要写书评

暂无评论

并发实时系统的模型及其形式化

并发实时系统的模型及其形式化

引用

作者：陈艳广西师范大学

学位级别：硕士

并发实时系统指多处理器环境下有实时要求的并发计算系统。本文第一章中介绍了一般实时系统的发展。实时系统领域的研究者通常考虑有周期性截止期的任务,任务调度问题是实时系统研究的重点,这一领域的研究成果包括有效的调度算法及相... 详细信息

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

关键词：并发实时系统时空占用量时空利用率时段演算分离逻辑进程代数

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：