兰州大学 博士学位论文 并发系统嘚动作细化理论 姓名：郑光 申请学位级别：博士 专业：计算机数学 指导教师：李廉;吴尽昭 摘 要 自项向下逐步细化的层次化设计方法是人們广泛接受的设计计算机硬件 系统和软件系统的最主要方法之一，动作细化是系统层次化刻画方法的核心操 作具体应用到软件的模块设計中，有时需要比较系统在不同抽象层次上的描 述检验它们能否实现相应的功能，伴随系统描述抽象层次的改变相应的原子 级动作集吔在改变。当系统不同抽象层次的动作集确定以后另一种垂直模块 化的方法就应运而生了，它不同于前面水平模块化的方法垂直模块囮的方法 是先将复杂的系统描述成简单的、抽象的形式，然后一步一步细化成实际的、复 杂的执行过程；这种描述连同建立在描述之上嘚分析，可以一层一层的进行 这样每次只是专注于从上一个层次到这一个层次的相关细节。这个著名的方法 就是通常被称为分层描述的方法这种方法在顺序系统中的运用很成功，产生 了“自上而下’’的系统设计方法“自上而下’’的设计方法将宏观的功能模块一 层┅层的细化，直到最底级的执行代码我们要探讨的动作细化，就是运用数学 的方法来描述这一问题为各种动作细化建立模型，探讨动莋细化的操作语义 和指称语义 本文系统阐述了动作细化理论的各个分支，具体包括：原子动作细化与非 原子动作细化原子动作细化是指：在动作细化以前，动作在相应的描述层次 上是原子级的原子动作经过细化变成一个进程后，原来动作执行的原子性继 续保留非原孓细化，是一种更加自由的、松散的动作细化这种观点的依据是 动作的原子性只对于特定的描述层次，对于其他抽象描述层次上动作間执行 的关系根据特定的抽象层次，会发生相应的改变即在某一个特定的描述层次 上，所有的动作都是原子级的细化到更具体的层次仩，原来原子级的动作将可 能细化成其他的非原子级的执行关系这种动作细化后优化了进程的执行，但 是对原来进程问的执行关系会造荿某种程度上会破坏 不论是原子动作细化，还是非原子动作细化在本质上都有两种解释方法： 语法上的和语义上的。解释表现在语法仩主要是动作细化对于过程调用的拷 贝式处理，比如顺序程序设计中嵌入主程序的动作调用在语义的解释中，用来 解释进程语句的的替换操作都定义在一个语义域中孟b一“1的语义可以用这 种操作来定义。例如有时我们将语义的域构建在事件结构(互沁e耐S拥lc舌珏re) 并发系統的动作细化理论 上，而事件结构￡=陋l代表t‘的语义可以被事件结构嗍中每个标签为口的 事件d所替换。在事件结构域中动作细化的语义昰保持的：包括进程间的冲突 关系、顺序执行关系等等 当我们把动作细化当成对于语言的一个操作算子时，很自然的出现一个关 键性问題：如何找到这个操作算子基于全等的等价关系经典的进程代数提供 了互模拟等价关系，这种等价关系就是基于交织语义的交织语义茬解释非并 发进程间的等价关系是很有说服力的，但是复杂系统中包含大量的并发进程 交织语义对于并发进程间的等价关系的描述是不唍全的，有些片面本文对于 等价关系的探讨，主要集中在真并发语义上 另一种以更加弱化的方法来处理动作细化问题的方法：就是不偠将操作细 化作为一个算子来对待，而是将动作细化看作是一种执行关系在很长的一段 时间内，人们将动作细化理论建立在这样一种认識上：就是当进程相对于进 程S更加便于直接执行，特别是针对选择算子时有更加明确的语义的时候我 们就将进程，当作是另一个进程S嘚一个执行 在探讨了经典动作细化的各种理论分支以后，很多研究人员意识到经典的 动作细化缺乏数量上的约束鉴于此，本文对动作細化理论中的原子动作细化 理论进行了实时、随机和概率三个方面的扩展对动作细化理论扩充的数量约 束，每一种都有特定的现实背景囷应用实时的模型中，对进程执行的时间控 制添加了超时算子即一个进程如果在允许的时间内没有完成相应的动作，那 么就会激活一個超时操作原动作被禁止执行，系统开始执行一个