（计算机软件与理论专业论文）虚拟接口体系结构及其petri网模型.pdf

山 东 大 学 硕 士 学 位 论 文 摘要 现今，随着并行计算机的问世及发展，人们逐渐意识到并行处理系统对科学 计算及商业发展的重要帮助。对于并行处理系统，人们希望要有较高的结点运算 速度，系统的加速比性能接近线性增长，并行应用程序的开发要高效、方便。目 前， 机群系统大多采用商用高性能工作站或高档 p c ，结点的运算速度问题不是很 突出，因而主要的研究方面是在提高系统的并行效率、使系统的使用更为方便上， 关键是建立高效的通信子系统。通信子系统完成系统中各节点之间数据传递的功 能， 其性能的好坏直接影响到并行计算的加速比和效率。而机群系统下的通信子 系统的性能是整个系统的薄弱环节。 究其原因，其中最主要的恐怕就是分层网络 软件频繁的系统调用和内存一 内存拷贝，造成了物理层和应用层之间的性能鸿沟。 一些研究团体为了解决这些问题， 提出了象a m, v mmc , f m, u - n e t 和b i p 等 一些通信系统， 并且所有这些通信系统使用的通信协议比传统的t c p / i p 协议都要 简单。在这些新系统里，传统的网络软件层大都被淘汰了，而且操作系统所起的 作用大大减少。在其中一些系统里，用户应用程序被允许直接访问网络接口，通 常被称为用户层网络接口。虚拟接口体系结构就是在这些通信系统的基础上发展 起来的一种崭新的通信思想体系。 虚拟接口体系结构是一种用来彻底提高与延迟相关的网络操作性能而设计的 通信协议。它通过提供一个高速率的机群通信接口，将一个强大的技术带给客户/ 服务器计算环境。虚拟接口体系结构是独立于硬件的，并可以和现今的网络互连， 如 : s e r v e r n e t , e t h e r n e t , a t m 和m y r i n e t e 虚 拟 接口 体系 结 构 定 义了 一 个 标 准 的软件接口和一个硬件接口。软件接口可以支持不同的高效编程模式，以此来简 化应用的开发并确保最佳的性能; 硬件接口模式可以和标准的网络兼容， 包括 a t m 网络、以太网和光纤通道，以及系统区域网。 第二章首先给出 p e t r i网的基本概念，介绍了 p e t r i网的理论分析方面，包 括有界性分析、活性分析、安全性分析、公平性分析等等。停一 等协议是一个比 较 典型的通信协议，在第三章中通过建立它的工作模式的有限自 动机模型和 p e t r i 网模型，得出用p e t r i 网作为分析工具具有的优越性。 随着虚拟接口思想的深入发展，国际上出现了许多相关的模型，在第四章中对国 际上影响比较大的由加利福尼亚大学的b e r k e l e y 实验室创建的模型作了详细的介 绍与分析。 . . . . . 勺 . . . . . . . . . . 口 . . . . . . . . . . 口 . . . . . . - 目 曰. . . . . i 山 东 大 学 硕 士 学 位 论 文 在建立 p e t r i网 模型的 基础上，第五章中首先给出建立连接的可达图，并把 变迁与随机的指数分布实施延时相联系起来。给 p / t网的每个变迁相关连一个实 施速率， 得到的模型就是随机 p e t r i 网模型。由马尔可夫过程， 在 s p n可达图上 很容易获得m c转移速率矩阵的参数，因此能够计算出m c的每个状态 ( 标识)的 稳定状态下的稳定概率。通过解方程组得到每个标识在稳定状态的稳定概率后， 本文建立并分析了一些性能指标，如位置中标记概率密度可反映系统部件的利用 率，变迁的利用率可反映系统吞吐量和延时等。 本文的阐述表明虚拟接口体系结构带给我们一种崭新的进程之间的通信思 想，它是一 利 ， 用来彻底提高与延迟相关的网络操作性能而设计的通信协议。本文 又 借助 p e t r i网为工具为这种通信协议建立模型， 并进行相关的理论分析与性能 分析，得到的一些性能指标为今后的科学研究打下了理论基础。今后通过对相关 的性能指标加以实际测试数据，将会得到进一步的结论。 关键词:p e t r i 网，马尔可夫链，马尔可夫过程，通信协议，虚拟接口体系结构 一一一. . .月 口. . 网 .， t 1 山 东 大 学 硕 士 学 位 论 文 a b s t r a c t n o w a d a y s , w i t h t h e p r o d u c t i o n a n d d e v e l o p m e n t o f h i g h - s p e e d p a r a l l e l c o m p u t e r , p e o p l e g r a d u a l l y r e a l i z e d t h e i 帅o r t a n c e o f p a r a l l e l s y s t e m t o s c i e n c e c o m p u t i n g a n d b u s i n e s s d e v e l o p m e n t . p e o p l e h o p e t o g e t . h i g h c o m p u t i n g r a t e b e t w e e n n o t e s , t h e l i n e a r r i s e i n s y s t e m a c c e l e r a t i n g r a t i o a n d h i g h c l u s t e r e f f i c i e n c y i n t h e d e v e l o p s y s t e m a l m o s t a l l u s e h i g h o f p a r a l l e l p e r f o r m a n c e p r o g r a m s . r e c e n t l y , t h e w o r k s t a t i o n c o m p u t e r . e f f i c i e n c y n o t e . t h e s o t h e mai n r e s e a r c h a s p e c t s i s h o w t h e u s a g e c o n v e n i e n t , n o t a d v a n c e o r p e r s o n a l t h e p a r a l l e l a n d m a k i n g k e y w o r k c o m p u t i n g r a t e o f t h e h i g h d a t a ofof i s t o c o n s t r u c t c o m m u n i c a t i n g s u b s y s t e m e f f i c i e n c y . t h e c o m m u n i c a t i o n s u b s y s t e m c o m p l e t e s t h e f u n c t i o n t r a n s f e r b e t w e e n t h e n o t e s i n t h e s y s t e m . t h e p e r f o r m a n c e o f t h e c o m m u n i c a t i n g s u b s y s t e m i s t h e f r a i l l i n k i n t h e c l u s t e r s y s t e m . t h e m a i n r e a s o n i s p r o b a b l y t h e c o n t i n u a l l y s y s t e m c a l l a n d m e m o r y - t o - m e m o r y c o p y c a u s i n g t h e p e r f o r m a n c e c h a s m b e t w e e n t h e p h y s i c a l l e v e l a n d a p p l i c a t i o n l e v e l . s o m e r e s e a r c h b o d i e s p u t t h e c o m m u n i c a t i n g s y s t e m s l i k e a m , v m m c f m , u - n e t . , b i p a n d s o o n t o s o l v e t h e p r o b l e m . t h e c o m m u n i c a t i n g p r o t o c o l s i n t h e s e s y s t e m s a r e s i m p l e r t h a n t h e t r a d i t i o n a l t c p / i p p r o t o c o l . . i n t h e s e s y s t e m s , t r a d i t i o n a l n e t w o r k s o f t w a r e l e v e l w a s a b a n d o n e d a n d t h e a f f e c t i o n o f t h e o p e r a t i n g s y s t e m h a d b e e n g r e a t l y r e d u c e d . i n s o m e o f t h e m , t h e a p p l i c a t i o n s h a v e a c c e s s t o t h e n o r m a l l y c a l l e d u s e r - l e v e l n e t w o r k i n t e r f a c e . v i r t u a l i n t e r f a c e a r c h i t e c t u r e i s a n e w c o m m u n i c a t i n g s y s t e m d e v e l o p i n g f r o m t h e s e s y s t e m s v i r t u a l i n t e r f a c e a r c h i t e c t u r e i s a c o m m u n i c a t i n g p r o t o c o l t o c o m p l e t e l y a d v a n c e t h e n e t w o r k o p e r a t i n g p e r f o r m a n c e r e l a t e d t o d e l a y . i t p r o v i d e s a g r e a t t e c h n o l o g y t o c u s t o m / s e r v e r s y s t e m t h r o u g h a h i g h r a t e o f c o m m u n i c a t i n g i n t e r f a c e i n t h e c l u s t e r . t h i s a r c h i t e c t u r e i s i n d e p e n d e n t t o h a r d w a r e a n d c a n c o n n e c t t o t h e n e t w o r k i n n o w a d a y s , s u c h a s s e r v e r n e t , e t h e r n e t , a t m a n d m y r i n e t . i t d e f i n e s a h a r d w a r e i n t e r f a c e a n d a s o f t w a r e i n t e r f a c e . t h e s o f t w a r e i n t e r f a c e c a n s u p p o r t d i f f e r e n t p r o g r a m m i n g m o d e l : t h e h a r d w a r e i n t e r f a c e i s c o m p a t i b l e w i t h t h e a t m , e t h e r n e t , s y s t e m a r e a 丁 了 1 山 东 大 学 硕 士 学 位 论 文 n e t w o r k . i n t h e s e c o n d c h a p t e r , w e f i r s t p r o v i d e t h e b a s e c o n c e p t o f p e t r i n e t s . t h e n w e i n t r o d u c e t h e a n a l y s i s o f l i m i t p r o p e r t y , a v i d i t y , s a f e t y , e q u i t y . s t o p - a n d - w a i t p r o t o c o l i s a c l a s s i c a l c o m m u n i c a t i n g p r o t o c o l . i n c h a p t e r t h r e e , t h r o u g h c o n s t r u c t i n g t h e土 i m i t e d a u t o m a t i c m a c h i n e m o d e l a n d p e t r i n e t s m o d e l o f s t o p - a n d - w a i t p r o t o c o l , w e d r a w t h e s u p e r i o r i t y o f p e t r i n e t s s e r v e d a s a k i n d o f a n a l y s i s t o o l w i t h t h e d e v e l o p m e n t o f t h e i d e a o f v i r t u a l i n t e r f a c e a r c h i t e c t u r e t h e r e a r e m a n y r e l a t e d m o d e l s i n t h e w o r l d . i n c h a p t e r f o u r , w e i n t r o d u c e a n d a n a l y z e t h e b e r k e l e y m o d e l c o n s t r u c t e d b y c a l i f o r n i a u n i v e r s i t y b e r k e l e y l a b . i t i s i n f l u e n t i a l a m o n g t h e w o r l d . r e a c h a b l e p i c t u r e i s i m p o r t a n t i n p e t r i n e t s a n a l y s i s . f r o m t h e r e a c h a b l e p i c t u r e , w e c a n a n a l y z e t h e s a f e t y , c o n s e r v a t i o n , a v i d i t y , e t c . b a s e d o n p e t r i n e t s m o d e l , w e f i r s t g i v e t h e r e a c h a b l e p i c t u r e o f c o n s t r u c t i n g c o n n e c t i o n a n d r e l a t e t h e t r a n s p o r t s t o t h e f i r i n g d e l a y o f s t o c h a s t i c e x p o n e n t d i s t r i b u t i n g . g i v i n g e a c h t r a n s p o r t a r e l a t i n g f i r i n g r a t e , w e g e t t h e m o d e l o f s t o c h a s t i c p e t r i n e t s . u s i n g m a r k o v p r o c e s s , w e g e t t h e r e f e r e n c e o f t r a n s f e r r i n g r a t e s m a t r i x i n t h e r e a c h a b l e p i c t u r e . t h e n t h e s o l i d r a t e o f e v e r y s o l i d s t a t e i s g i v e n . i n t h i s p a p e r , w e c o n s t r u c t a n d a n a 土 y z e s o m e p e r f o r m a n c e t a r g e t s . t h e d e n s i t y o f t h e m a r k r e f l e c t s t h e u t i l i z a t i o n r a t i o o f t h e d e p a r t m e n t o f t h e s y s t e m a n d t h e u t i l i z a t i o n r a t i o o f t h e t r a n s p o r t r e f l e c t s t h e d e l a y . t h e v i r t u a l i n t e r f a c e a r c h i t e c t u r e i n t r o d u c e d i n t h i s p a p e r i n d i c a t e s t h a t i ti s a n e w c o m m u n i c a t i n g i d e a b e t w e e n t w o p r o c e s s e s , a n d i t i s a c o m m u n i c a t i n g p r o t o c o l t o c o m p l e t e l y a d v a n c e t h e n e t w o r k o p e r a t i n g p e r f o r m a n c e r e l a t e d t o d e l a y .工 t i s u s e f u l f o r i m p o r t i n g t h e p r o t o c o l t o c o n s t r u c t m o d e l s a n d g i v e r e l a t e d a n a l y s i s o f t h e c o m m u n i c a t i n g p r o t o c o l s t h r o u g h p e t r i n e t s . t h e s e p e r f o r m a n c e t a r g e t s d e r i v e d f r o m a n a l y s i s o f i t w i l b e c o m e t h e t h e o r y b a s i s o f t h e f u t u r a l s c i e n c e r e s e a r c h . i n t h e f u t u r e , w e w i l l g e t f a r t h e r c o n c l u s i o n t h r o u g h a c t u a l d a t a o f r e l a t i n g p e r f o r m a n c e l a 了 g e t s . k e y w o r d s : p e t r i n e t s , ma r k o v c h a i n , m a r k o v p r o c e d u r e , v i r t u a l i n t e r f a c e a r c h i t e c t u r e n 山 东 大 学 硕 士 学 位 论 文 原创性声明和关于论文使用授权的说明 原 创 性 声 明 本人郑重声明: 所呈交的学位论文， 是本人在导师的指导下， 独立 进行研究所取得的成果。 除文中已 经注明引用的内容外， 本论文不包含 任何其他个人或集体己经发表或撰写过的科研成果。 对本文的研究作出 重要贡献的个人和集体， 均己在文中以明确方式标明。 本声明的法律责 任由本人承担。 论文作者签名:日期: 关于学位论文使用授权的声明 本人完全了 解山东大学有关保留、 使用学位论文的规定，同意学校保留或向m , 家有 关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅:本人授权山东大学可 以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名:导师签名:日期: 山 东 大 学 硕 士 学 位 论 文 第一章绪论 第一节机群及其通信 一、机群系统 机群 1 系统是利用高速通用网络将一组高性能工作站或高档 p c机，按某种结 构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一 调度，协调处理，实现高效并行处理的系统。从结点和结点间的通信方式来看， 它属于分布存储系统，主要利用消息传递方式实现各主机之间的通信，由建立在 一般操作系统之上的并行编程环境完成系统的资源管理及相互协作，同时也屏蔽 工作站及网络的异构性，对程序员和用户来说， 机群系统是一个整体的并行系统。 对于并行处理系统，人们希望要有较高的结点运算速度，系统的加速比性能 接近线性增长，并行应用程序的开发要高效、方便。目 前，机群系统大多采用商 用高性能工作站或高档p c ，结点的运算速度问 题不是很突出，因而主要的研究方 面是在提高系统的并行效率、使系统的使用更为方便上，关键是建立高效的通信 子系统。通信子系统完成系统中各节点之间数据传递的功能，其性能的好坏直接 影响到并行计算的加速比和效率。而机群系统下的通信子系统的性能是整个系统 的薄弱环节。 二、影响通信的因素 1 .网络带宽低 机群系统使用的网络是普通的局域网， 而局域网的带宽通常都比 较低， 如传统 以太网的带宽只有 l o mb / s 。局域网的带宽之所以低，原因主要是局域网是为长距 离的数据通信而设计的，由于通信距离较长，限制了通信速度的提高，因为信号 的频率越高，它能够传输的距离也越短。另外一个原因是处于价格上的考虑，为 了降低网络系统布线所需的成本， 大多数局域网 共享一根信号总线进行数据传输， 因 此这也在很大程度上影响了网 络系统的性能， 特别是在网络负载较重时，由于 各节点都要抢占信号总线，很容易造成通信阻塞，使得实际通信带宽比其最大带 宽要小的多。 2 .传统的t c p / i p 协议层次太多 t c p / i p协议是面向低速率、高差错和大数据包传输而设计的，虽然 t c p及 t p 4 等通用协议为连接管理、 差错控制和流量控制提供了复杂的控制机制， 它们的 山 东 大 学 硕 士 学 位 论 文 第一章绪论 第一节机群及其通信 一、机群系统 机群 1 系统是利用高速通用网络将一组高性能工作站或高档 p c机，按某种结 构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一 调度，协调处理，实现高效并行处理的系统。从结点和结点间的通信方式来看， 它属于分布存储系统，主要利用消息传递方式实现各主机之间的通信，由建立在 一般操作系统之上的并行编程环境完成系统的资源管理及相互协作，同时也屏蔽 工作站及网络的异构性，对程序员和用户来说， 机群系统是一个整体的并行系统。 对于并行处理系统，人们希望要有较高的结点运算速度，系统的加速比性能 接近线性增长，并行应用程序的开发要高效、方便。目 前，机群系统大多采用商 用高性能工作站或高档p c ，结点的运算速度问 题不是很突出，因而主要的研究方 面是在提高系统的并行效率、使系统的使用更为方便上，关键是建立高效的通信 子系统。通信子系统完成系统中各节点之间数据传递的功能，其性能的好坏直接 影响到并行计算的加速比和效率。而机群系统下的通信子系统的性能是整个系统 的薄弱环节。 二、影响通信的因素 1 .网络带宽低 机群系统使用的网络是普通的局域网， 而局域网的带宽通常都比 较低， 如传统 以太网的带宽只有 l o mb / s 。局域网的带宽之所以低，原因主要是局域网是为长距 离的数据通信而设计的，由于通信距离较长，限制了通信速度的提高，因为信号 的频率越高，它能够传输的距离也越短。另外一个原因是处于价格上的考虑，为 了降低网络系统布线所需的成本， 大多数局域网 共享一根信号总线进行数据传输， 因 此这也在很大程度上影响了网 络系统的性能， 特别是在网络负载较重时，由于 各节点都要抢占信号总线，很容易造成通信阻塞，使得实际通信带宽比其最大带 宽要小的多。 2 .传统的t c p / i p 协议层次太多 t c p / i p协议是面向低速率、高差错和大数据包传输而设计的，虽然 t c p及 t p 4 等通用协议为连接管理、 差错控制和流量控制提供了复杂的控制机制， 它们的 山 东 大 学 硕 士 学 位 论 文 优点是为大量应用提供标准的点到点传输服务，而付出的代价是协议性能。由 于 主机对基于内核的传输站的如下一些操作费用，传统的网络体系结构不能提供应 用所需要的相关性能。这种处理费用在一些方面有不利的性能: ( 1 )带宽:这种费用限制了一个给定网络所能发送的实际带宽。网络硬件带 宽提高了几个数量级，而软件在可用的网络工作栈费用方面却保持相对静止不变。 ( 2 ) 延迟和同步:有效的同步操作对于分布式和基于网络的一些应用来说是 一个大的可量测性因素，而费用直接花在了端对端的用于同步操作的消息延迟。 ( 3 )主机处理负载:该费用消耗了 c p u的一段本可以用于其他处理的一段 时间。 这些费用本质上是由于t c p / i p 协议是一个多层次的软件结构:网络接口层、 网间网层 ( i p ) 、传输层 ( t c p )和应用层，协议有内部的不足:第一，协议层次 多，在进行数据传输时，数据需要经过多次拷贝才能从应用层传递到网络接口或 从网络接口传送到应用层，而多次的拷贝带来了很大的网络延迟时间。第二，对 于流量控制、差错控制、出错重发机制、拥塞控制等功能的实现都与缓冲管理密 切相关。 通常的缓冲管理机制都比 较复杂， 例如， b e r k e l e y u n i x采用一种叫m b u f s 的结构对协议的数据包进行缓冲管理，但 m b u f s算法很复杂，开销很大。在 d e c s t a t i o n 5 0 0 0上，对单字节 t c p消息缓冲管理，m b u f s 需要 1 0 0微秒，而对 5 1 2 字节数据包需要3 0 0 微秒， 可见缓冲管理带来的网络延迟也很大。 传统的协议 开销会是实际传输延迟的好几倍，而这对大多传输来说是实质性的，对于那些经 常发送小的数据包的细粒度并行程序和分布式相关性协议来说，这个问题会尤其 急剧。 在高性能通信环境中，用几十微妙的开销来发送仅仅一个数据包是无法接 受的， 而面对高的数据连接率，我们急需将开销最小化。最后一方面，在网络协 议实现中涉及到上下文切换、调入/ 调出页面、启动 1 / o设备、中断响应等操作系 统处理，有时这些开销可能比协议本身的处理开销还大。比如，在s u n 3 / 6 0系 统上t c p / i p对一个数据包的协议处理时间为1 0 0 微秒， 而操作系统的额外开销却 高达 2 4 0微秒，这就造成了通信性能对操作系统一定程度上的依赖。因此， 要降 低网络延迟，提高通信系统性能，应当尽量使通信与计算重叠，减少操作系统对 数据传输的干涉。 三、降低网络延迟的方法 ( 1 )采用高速网络，提高网络带宽 2 山 东 大 学 硕 士 学 位 论 文 为了提高机群系统的网络带宽， 必须采用新型的高速网络来取代 i o mb / s 以太 网。目 前， 快速以 太网、 a t m、 千兆网和m y ri n e t 己 经出 现， 这些高速网 络推动了 网络硬件的飞速发展，给网络软件，即网络协议的不断更新提供了 广阔的空间。 ( 2 )设计新的通信协议，降低通信延迟 高速网络性能的提高，往往是指其峰值带宽。与传统以太网比，高速网的峰 值带宽有了很大程度的提高， 从1 0 m b / s 增长到1 0 0 m b / s . 6 4 0 mb / s、 1 0 0 0 m b / s , 甚至1 g b / s 。 但是峰值带宽都是在大数据包传输时得到的， 对小数据包来说， 其性 能不尽人意。 表i 是对1 0 m b / s 以 太网 和6 4 0 m b / s m y ri n e t 一个字节数据包往返延 迟时间的测试结果。 表 1 网络类型 t c p 往返延迟( us )u d p 往返延迟( us ) 以太网 1 4 3 81 1 4 6 my r in e t 1 5 0 61 3 7 0 m y r i n e t 的通信延迟反而比以 太网 还大( 在第四 章中我们会详细分析与m y ri n e t 相关的问题) 。由 此可见，高速网 络在传输小数据包时的性能并不理想， 而小数据 包下网络系统性能的好坏，对并行计算有很大影响。因此减小高速网络小数据包 传输的延迟时间是提高网络系统性能的重要方法之一。 为了 提高网络系统性能， 必须对传统的通信协议作较大的修改， 以克服传统协 议的不足，主要有两种方法: 1 、 在用户空间实现通信协议 为了减少操作系统系统的额外开销，一个重要的方法是在用户空间实现一个 用户态的协议层，使得此协议层能够旁路操作系统的影响，直接对网络硬件设备 进行操作，这样就可减少数据拷贝次数，提高通信效率:把协议实现在用户空间 的另一优点是可以减少操作系统调用的时间开销，而且通讯协议能够与用户的实 际应用密切结合。这样做必须解决好在没有核心参与的情况下，如何管理有限的 网络资源问题。在虚拟接口体系结构中，用一个用户层库来管理用户的进程，除 了一些关键的命令，如创建虚拟接口、建立连接、断开连接等等要内核参与外， 其余的数据传输相关工作都由用户直接通过虚拟接口和网络通信，节省了很大的 操作系统开销，这将在第四章中详细分析。 3 山 东 大 学 硕 士 学 位 论 文 2 ,精简通信协议 前面对传统协议机构层次的分析说明，传统通信协议通信开销大很大程度上 是由于协议层次多、数据拷贝频繁引起的，因此减少协议的层次，使得通信协议 变为一层，将会减少数据拷贝次数，降低系统开销。 近些年来，随着计算机硬件的发展，网络硬件支持每秒钟大约为g b / s 的带宽 已 成为现实。但是用户应用程序所使用的带宽却一直相对低些，并且应用和应用 之间的通讯延迟也相对高些。究其原因，其中最主要的恐怕就是分层网络软件频 繁的系统调用和内存一 内存拷贝，造成了物理层和应用层之间的性能鸿沟。一些研 究团体为了 解决这些问题， 提出了象a m, v m m c , f m, u - n e t 和b i p 等一些通 讯系统，并且所有这些通讯系统使用的通讯协议比 传统的t c p / i p 协议都要简单。 在这些新系统里，传统的网络软件层大都被淘汰了，而且操作系统所起的作用大 大减少。在其中一些系统里，用户应用程序被允许直接访问网络接口，通常被称 为用户层网络接口。下面就将这几种用户层网络协议 ( u s e r - l e v e l n e t w o r k , u l n? 2 3 4 5 ) 6 做一 下 介绍 和分析: l . a c t i v e m e s s a g e s. 它 是 第一 个 被 广 泛 使 用的u l n , 最初 是为 并 行的 微 机 开发的，在不同的网络接口硬件上应用， 接着发展成为一种用于通讯的汇编语一言。 在这种用户层网络机制中，小的消息对应于过程调用期间寄存器中所传送的参数， 大一些的消息被当作是内存一 内存的传送。当目的地处的消息准备好时，处理程序 就以消息的有关数据为参数在远程用户的地址空间里执行，将数据从队列中移到 处理程序的参量中。其中，结点包含简单的发送和接收队列，从网络接口 卡上可 以进行页面调入和调出，但是他们的内部结构是隐藏的，这同本文第四章要介绍 的 虚拟接口 体系结构中的思想是不同的。 2 . u - n e t在用户层上将设备驱动程序能看到的描述符队列和缓存区结构虚化， 这同虚拟接口体系结构是相同的， 并且在所有的u l n中它的设计思想和虚拟接口 体系结构最相似，不同之处在于队列的结构和缓存区的地址映射方案如何执行等 细节方面。 t c p就建立在虚拟接口 体系结构基础之上加上了 用户进程处理出 错检 测、超时和重试机制。 3 . f a s t m e s s a g e s . 它用的 是g a m接口 ， 并不 将底部的队列结构展示出 来， 排除了处理程序的隐含执行， 而是由用户进程为即将到来的消息提供缓存管理( 在 这一点上和 v i a相同，但机制要简单一些)并管理流量以避免死锁。它被广泛应 山 东 大 学 硕 士 学 位 论 文 用于机群互连，并推动了为解决由大批传送引起的节点争夺问题等相关协议的发 展。 4 . v i r t u a l m e m o ry - m a p p e d c o m m u n i c a t i o n ( v m m c ) . 是一 个和 前 面 所 有 系 统 非常不同的通讯模式。这种通讯机制是在网间建立一个相对存储区，从一边写入 的被自动地传播到另一边。由于操作系统参与建立所需的映射，因此这种模式包 含了正确的虚拟和多路复用的较复杂的技术， 但是v mmc不展示队列并拥有非常 基本的操作，这是它的可取之处。用户应用程序通常与通讯区域建立消息队列， 以方便消，急传递。 5 . b i p .它是并行机制最基本的 接口， 是用于m y r i n e t 的一种简单的u l n a 在这种机制中，每个结点上的进程都有一对唯一的发送队列和接收队列，为基本 的b i p _ s e n d ( ) 和b i p r e e v ( ) 调用提供指向 数据缓存区的直接指针。当队列被使用 时，它们并不直接展示给用户层进程。 第二节p e t r i 网概况 1 9 6 2 年， 原联邦德国达姆士塔技术学院数学和物理系的c a r l a d a m p e t r i 在他的 博士 论 文 “ k o m m u n ik a t i o n m it a u t e m a te n ( 自 动 机 通 信) i7 1 中 首次 提出p e t r i 网 ( p n s ) 这一概念。文中p e t r i 阐述了一台计算机中的两个异步分支间的通信理论的基础。 他特别注意到事件之间因果关系的描述，并证明了正规自 动机不可能认识上下文 无关文法和上下文有关文法。这篇论文是p e t r i 网理论发展的奠基石。 p e t r i 网诞生于德国，但其发展与拓广却是在美国。 p e t r i 的论述引 起了人w h o l t 和其他在a d r ( 应用数据研究) 公司信息系统理论 课题组工作的人们的注意许多关于p e t r i 网的早期理论、记号和表示方法， 都是由 信息系统理论课题组导出或拟定的。这些早期成果发表在这个课题组的最后研究 报告 18 l和另 一 篇 题为“ 事 件与 条 件， 的 报告 中 19 1 。 这 些 文章展 示了 如 何 用p e t r i 网 来模拟和分析具有并行分支的系统， 此外， 他们还把p e t r i 的学位论文翻译成英语， 大大地拓展了p e t r i 的结论。 p e t r i 的工作也引起了麻省理工学院的m a c课题组的注意。由t a c k b . d e n n i s 教授指导的计算结构研究组在p e t r i 网理论方面作了 大量的研究工作并发表了许多 文章，其中包括几篇p h 。学位论文和大量的研究报告。 5 山 东 大 学 硕 士 学 位 论 文 用于机群互连，并推动了为解决由大批传送引起的节点争夺问题等相关协议的发 展。 4 . v i r t u a l m e m o ry - m a p p e d c o m m u n i c a t i o n ( v m m c ) . 是一 个和 前 面 所 有 系 统 非常不同的通讯模式。这种通讯机制是在网间建立一个相对存储区，从一边写入 的被自动地传播到另一边。由于操作系统参与建立所需的映射，因此这种模式包 含了正确的虚拟和多路复用的较复杂的技术， 但是v mmc不展示队列并拥有非常 基本的操作，这是它的可取之处。用户应用程序通常与通讯区域建立消息队列， 以方便消，急传递。 5 . b i p .它是并行机制最基本的 接口， 是用于m y r i n e t 的一种简单的u l n a 在这种机制中，每个结点上的进程都有一对唯一的发送队列和接收队列，为基本 的b i p _ s e n d ( ) 和b i p r e e v ( ) 调用提供指向 数据缓存区的直接指针。当队列被使用 时，它们并不直接展示给用户层进程。 第二节p e t r i 网概况 1 9 6 2 年， 原联邦德国达姆士塔技术学院数学和物理系的c a r l a d a m p e t r i 在他的 博士 论 文 “ k o m m u n ik a t i o n m it a u t e m a te n ( 自 动 机 通 信) i7 1 中 首次 提出p e t r i 网 ( p n s ) 这一概念。文中p e t r i 阐述了一台计算机中的两个异步分支间的通信理论的基础。 他特别注意到事件之间因果关系的描述，并证明了正规自 动机不可能认识上下文 无关文法和上下文有关文法。这篇论文是p e t r i 网理论发展的奠基石。 p e t r i 网诞生于德国，但其发展与拓广却是在美国。 p e t r i 的论述引 起了人w h o l t 和其他在a d r ( 应用数据研究) 公司信息系统理论 课题组工作的人们的注意许多关于p e t r i 网的早期理论、记号和表示方法， 都是由 信息系统理论课题组导出或拟定的。这些早期成果发表在这个课题组的最后研究 报告 18 l和另 一 篇 题为“ 事 件与 条 件， 的 报告 中 19 1 。 这 些 文章展 示了 如 何 用p e t r i 网 来模拟和分析具有并行分支的系统， 此外， 他们还把p e t r i 的学位论文翻译成英语， 大大地拓展了p e t r i 的结论。 p e t r i 的工作也引起了麻省理工学院的m a c课题组的注意。由t a c k b . d e n n i s 教授指导的计算结构研究组在p e t r i 网理论方面作了 大量的研究工作并发表了许多 文章，其中包括几篇p h 。学位论文和大量的研究报告。 5 山 东 大 学 硕 士 学 位 论 文 计算机结构研究组在7 0 年代举行过两次p e t r i 网方面的重要会议:1 9 7 0 年在 w o o d s h d e 举行了讨论并行系统和并行计算的ma c课题组会议;1 9 7 5 年在麻省 理工学院举行了讨论p e tr i 网和相关方法的会议。 这两个会议对于传播p e t r i 网理论 的结果和方法起了一定作用。 7 0 年代末到8 0 年代初，p e tr i 网的理论与应用研究大大的扩展了。 1 9 7 7 年在巴黎成立了p e t r i 网专题学术委员会。 1 9 7 9 年在汉堡出现了通用网理 论的现代学科，一个专致于p e t r i 网研究的学术团体在德国形成。目前，每两年开 一次的国际会议专门讨论p e t r i 网问 题与系统性能，迄今已有六届。国际著名出 版 社s p r in g e r -v e r la g 在其灰 皮 书系 列l n c s ( l e c t u r e n o t e s in c o m p u te r s c i e n c e ) 中 每年至少出一卷p e t r i 网研究专