随机petri网和系统性能评价

【实例简介】
林闯，随机petri网和系统性能评价第二版
狮机Per网 都系统性能评价 (第2版) 林闯著 清华大学出版社 北京 内容简介 本书是随机Petr网理论和技术方面的专著,主要内容包括:各种随机Petr网理论和分析技术;随 机Petr阿的模型方法模型的分解和压缩技术以及性能界限求解技术;随机 Petri网在通信议、ATM 网络、柔性制造系统计算机系统和软件系统性能评价、工作流中的应用随机Peti阿软榫具。木书 内容基本上是自包含的内容新颖,容易理解,便于应用。主要读者对象是计算机、首动控制等相关专业 的大学高级学生研究生、程技术和科研人员。 版权所有翻印必究。举报电话:010而282989135012566781380310933 本书封面贴有清华大学出版社防伪标签,无标签者不得销售。 本书防伪标签用特殊防伪校术,用户可遴过在图案表面涂抹清水,图案消失水干斤图聚复魂;或将表 面得下,放在白纸上用彩笔涂抹,图案在白纸上再现的方法识别真伪a 图书在版编自{CIP)数据 随机 Petri阿和系统性能平价/林陶著.2版.一北京:清华大学出杜,205.4 ISBN7-302-10651 「.随…Ⅱ.林…Ⅲ.计算机网络F.TF393 中国版本图书馆C]P数据核字(205)第020115号 出版者:清华大学出版社 地址:北京清华大学学研大度 http://www.tup,comrn 邮编:100084 杜总权:010-6270175 客户服务:(10-6277969 资任编辑:醛證 印利者:北京矗丰华彩印有限公司 订者;…河市李旗庄少明装订厂 发行者:新华书店总店北京发行所 开本:185×260印张:23,75字教:546干字 版次:n5年4月第?版205年4月第1次印刷 书号:ISN7-502-10651-7/TP·7213 印数:01~3000 定价:49.00元 第2版前言 K随机Peti网和系统性能评价》一书出版已5年了,一本好的科技书都悬要通过使 用、修改、再使用、再修改,而且计算机技术的发展日新月异,随机Per网作为描述计算 机系统和网络的种重要的性能模型和分析具,也要不断完善,从而造应日益复杂的各 种新的应用领域。因此在木书的第2版中,新增加了作者及网内外相关学者近些年来在 该领域的最新科研城果:(1)在第5章中增加了一节“非乘积解随机 Petri网的乘积形式 近似求解”,(2)在第6章中增加了一节“随机 Petri网非乘积解系统的判定与界限求解”, 〔3)新增了第11章“在Web服务器集群中的应用”和第12章“在工作流中的应用”。同 时,本版对原版中的一些错误也进行了更正。 作者 2095年2月12日 前 随着计算机科学和技术的发展,计算机应用不断普及和深入,人们越承越感到计算机 系统性能评价在社会技术进步中的重要性。 计算杌系统性能评价研究的目的主要有三个:选择、改进和设计。在众多的系统(方 案)中选择—^最适合需要的系统(方案〕,即在一定的价格范围内迭择性能最好的系统 达到较好的性能价格比;对已有系统的性能缺陷和瓶颈进行改进和提高其运行效率;对 未米设计的系统进行性能预测,在性能成本方面实现最佳设计或配置 计算机系统的性能般包括以下两个方面:个方面足它的可靠性或可利用性,亦 即,计算机系统能正常工作的时间,其指标可以是能够持续工作的时间长度,如平均无故 障时间;也可以是在一段时间内,能正常工作的时间所占的百分比。另一方面是它的处 理能力或效率。这又可分为三类指标:一类指标是各种吞吐率,如系统在单位时间内能 处理正常作业的个数。另类指标是各种响应的时间,即从系统得到输人至给出输出之 间的时间。再一类指标是各种利用率,即在给定的时间区间中,各种部件(包括硬设备利 软系统)被使月的时间与整个时间之比。当然不同的系统对性能指标的描述有所不同 例如局域网络常用的性能评估指标为信道传输速率、信道吞吐量和容量、信道利用率、传 输延迟、响应时间和负载能力等 计算机系统的性能取决于多种因素,最基本的因素是系统的配置{即指系统构成所 包括的各种软件、硬件的成分、数量、能力和系统结构、处理和调度策略路等〕和系统负载(即 指工作负载和丁作方式例如交方式批处理方式等 性能評价的主要仟务就是研究系统配置、系统负载性能指标之间的相互关系。 性能评价的方法大致可以分为两类: 1)测量方法 通过一定的测量设备或一定的测量程序可以直接从计算机系统测得各项性能指标或 与之密切相关的量,然后由它们经过些简单的运算求出柑应的性能描标。这是最直接 也是最基本的方法,其他方法在定程度上也要依赖于它。但是这种方法只能适用于已 经存在并运行的系统,面且比较费时间。测量方案和测量手段是测量方法的关键 (2)模型方法 首先对要评价的计算机系统建立一个适当的模型,然后求出模型的性能指标,以便 对系统进行性能评价。模型中一般包括许多参数,这些参数的确定往往依赖于对实际系 统的测量结果或对系统参数的佔价。与测量方法相比,模型方法有两个优点:—是它不 仅可以应用于已有的系统的性能评价,而且也可以应用于尚未存在系统的性能预测; 是它的T作量一般比测量方法要小,比测量手段的费用要少。 模型方法又可分为模拟方法和分析方法两种。模拟方法是用一个程序动态地模拟 个系统及其负载。一般首先使用一个模拟语言来为系统建立模型,然后在模拟时,通过 随机Per网和系统性能评价 用负载驱动系统模型从而得出模型的性能指标。模拟方法可以详细地刻画系统,得出较 精确的性能指标,但是构造和使用模型时的费用较高。 分析方法则是应用数学理论与方法来研究和描述性能与系统、负载之间的关系。为 了数学上描述与计算的方便,往往要对系统模型进行-些笸化和假设,因响这种模型刻 画系统的详细程度较低,得出的性能指标精度也较低。但是这种方法理论基础强,可以 明显地刻画备种因素之间的关系,而且构造和使用模型时的费用也较低。 随着讦算机技术的发展,系统的庞大和复杂化使得系统性能评价问题变得越来越复 杂并越来越引起人们的重视。提供有效的数学理论工具、直观的模型描述方法和有效的 模型分析方法以及实用的辅助分析软件,是系统性能评价所而临的迫切需要解决的问 题,这也正是本书所要介绍的随机Petr网分析技术的核心 性能分析方法传统上采用排队论数学埋论来鮮决系统的描述问题,数学求解的基础 是马尔可夫随机过程。80年代初随机 PEtri网的提出为系统的性能分析又提供了个 新的数学述工具。随机 Petri网研究爿前已是一个热门课题。 Petri阿是可应用到很多系统和领域的图形和数学模型工具。 Petri网是信息处理系 统描述和模型的有力工具之一,它的主要特性包括:并行、不确定性、异步和分布描述能 力和分析能力。作为图形工具, Petri网除了具有类似流程图、框图和网图的可视描述功 能外,它还可通过标记( token)的流动模拟系统的动态和活动行为,所以可以说, Petri 网是动态图形描述工具。作为数学工具, Petri网可以建立状态方程代数方程和其他数 学模型来描述系统的行为。 Petri网既可为理论工作者也可为程人员所使用。它可以 作为理论者和实践者之间的通信媒介,以便于人们进行交流和理解 随着信息处理系统的日益庞大和复杂化,人们越来越需要采用系统T程的方法来设 计和维护信息处理系统。在信息处理系统的整个生命期内,采用图形化的数学工具来完 成系毓的形式描述、系统的正确性险证、系统性能的评价、系统的「标实现和测试是卡常 必要的。 Petri网是适应上述各项任务的有效工具,可以在一个 Petri网系统模型的框架 上完成各项任务。在这-点上,其他图形或数学工其则不具备如此的功能 系统性能评价方法,尤其是排队纶分析方法的发展和所遇到的问题,包括并行系统 的资源共享描述和非乘积解的问题,给Peri网应用领域的拓宽和发展带来了勃勃生机。 从8年代初随机 Petri网提出以来,系统性能评价过成为 Petri网最成功的应用领域 之 从1985年起,相关Pet网和性能模型的国际研讨会也开始召开,这个研讨会每两 年召开一次。在随机Peri网简短的发展历史中,它的应用范围经超出了讦算机科学 成为研究离散事件动态系统的一种有力工具。很有前途的应用领域包括计算机网络、分 布式软件系统、分布式数据库系统、并发和并行计算系统、柔性制造与工业削造系统、 离散事件系统、多处理机系统、容譜与故障诊斷系统、办公自动化系统和决策模型等。 作者进行了不同级别 Petri树和各种随机 Petri网的多年研究,并在国际上首先提出 了随机高级Peti网及其分析技术和在一些系统性能评价中的应用。本书的主要内容是 作者十多年工作的总结。据作者所知,本书是国内外第一本随机Petr网理论和技术方 面的专著。本书的目的是使读者能基本掌据随机Peri网的理论模型方法、分析技术和 前言 应用思路;同时了解当前隨机Petr网理论和庇用的发展,为读者的系统性能评价学习 丁作和研究课题提供一条有效途径。 本书的主要内容包括四部分: 1)在第1章至第3章中介绍了各种随机Petr网理论和分析技术,包括随机 Petri 网(SPN)、广义随机Petn网(GSPN)、随机回报网(SRN)随机高级 Petri网(SHPN)和 确定与随机Petr网(DsPN)。在这些Petn网理论和分析技术中,着重描述了可达集和 稳定状态概率的算法,可达分析和入变量的计算及分析方法。介绍了系统的性能特性分 析和算法。这部分是随机 Petri网的基础知识,足学习其他章节的基础。 2)在第4章至第6章中讨论了随机Peri网的模型方法,随机网模型的分解和压缩 技术以及模型性能界限求解技术。SPN模型性能评价的一个主要问题是模型状态空间 的爆炸状态的数量会随着模型的规模和复杂性的增加而是指数性地增长,使实际系统的 性能评价不可能。这一点会严重地阻得SPN模型的实际应用,也是当前SPN研究的热 点问题。这部分所介绍的技术可以应用到各种复杂大型系统的性能模型和评价屮,这些 技术是掌握SPN分杆方法的关键,也是深入进行SPN研究的基础。 (3)在第7章至第10章屮,着重介绍了随机Per网在通倍协议性能模型,ATM网 络性能模型、柔性制造系统性能模型以及在计算机系统和软件系统性能评价中的应用。 在随机Per网的应用中,注意了专有对象的描述问题的求解及分析方法的有效性。介 绍了一些基本计算杋和网络系统的性能模型方法,系统模型的基本化简技术,系统性能 参数,例如系统的吐吞量资源的利用率和用户平均响应时间等的实际计算和分析。 (4)为了方便读者使用随机Petr网软件工具,在第12章中介绍了随机Peti网软件 包—SFNP确定与隨机 Petri网敦件包 DSPNexpress以及本书作者开发的随 机高级Per网辅助软件 SHLPNA。在SPNP的介绍中,侧重介绍实际模型例了的 分析软件程序,读者很容易套用这些例子编写自已的软件程序。而在 DSPNexpress和 SHLPNA的介绍中,则侧重程序和数据结构的描述,读者可以了解随机 Petri网软件工具 的开发和使用。 本书的主要特点是: (1)书中的内容基本上是自包含的,随机Petr网的知识完整。本书包括了随杌 Pet网理论、模型方法、化筒技术和应用以及软件工具的介绍。 (2)容易理解,便于应用。本书淡化了数学形式的描述,注重了实际系统的模型;对 于每种形式的定义和推导,都给出模型例了进行引导。软件T具的介绍便于读者对实 你问题模型的理解 (3)内容新颖。本书包括了随机Pet网领域的主要最新研究成果和作者近年来的 工作 目前在随机Petr网领域里已取得的成果远多于本书所介绍的内容。本书仅是学习 随机 Petri网的第一步,深一步的学习还需读者阅读其他资料。 囡家自然科学基金委员会和国家重点基础研究发展规划项目(编号:G1999270307 Ⅵ 随机Petr网和系统生能评价 对作者的研究T作给予了连续的资助,本书的出版得到了“国家科学技术学术著作出版基 金”的资助。北京航空航天大学计算机系杨文龙教授、中国科学院数学研究所陆维明研究 员和上海复旦大学计算机系是时霖教授对本书的内容进行了认直的审阅,在此一并致谢 本书写作期间,我的家人和朋友给了我极大鼓励科帮助,作者谨以此书献给我的家人 和朋友 林闯 1998年12月于北京 目录 第1章Per网的基本概念和术语 1.1Peri网研究与发展简况…… 冒甲昏■■看暑 1.2 Petri网模型介绍… 1甲甲■卜昏督晶b 1.3网的基础知识… 1.4位置,/变迁(PT)系统… 5高级Peri网(HLPN》系统… 甲甲冒鲁■■倡F■晶口 1.6不同级别系统之间的关系与变换……… 参考文献 血自自L甲 14 第2章几种随机Petr网模型与分析方法 2.1随机时间变迁的实施… 甲1冒■■■1b山bbh甲 D4D PE 29 2.2随机 Petri网(SPN 23 2.3·义随机 Petri网(GSPN} ·甲1·甲1山*···啊…B" 2 2.4随机回报网(SRN)…… 日日甲甲■■血pd 2.5确定与随机 Petri网<DSPN) 甲甲4上晶 36 2.6随机 Petri网与排队论 40 参考文献… ………………………42 第3宜随机扃錾 Petri网{ SHLPN)………… 3.1 SHLPN的定义和复合标识概念…… 1卜■▲由■ 3,2具有标识变量的SHPN 3.3广义随机高级Pe:ri网( GSHLPN)……………… 6 3.4 SHLPN的标记流路和S不变量… 62 参考文献 69 第4章随机P网的模型方法 P·■冒■■▲1■晶pp甲ppm 4,1模型抽象组织 4甲gp■p 4.2模型精化设计 甲L普甲b■昌 8 参考文献 ■鲁■·暑画■▲』·■·"■嚕··跏幽▲■」mn■a■晷■+ 92 第5章随机er网的分解和压缩技术 ■量 5.时间数量级分解… ·日日日甲d■d晶 .93 5,2接迈无关的分解… …-97 5.3响应时间保留压缩替换 画山血 10 5.4流等价压缩替换 5.5层次模型和分层分析 日■ …………111 6乘积形式解 44-日·=4甲44aaF甲4.4Ah- 自d 119 【实例截图】
【核心代码】