数据流 订阅
数据流(data stream)是一组有序,有起点和终点的字节的数据序列。包括输入流和输出流。数据流最初是通信领域使用的概念,代表传输中所使用的信息的数字编码信号序列。这个概念最初在1998年由Henzinger在文献87中提出,他将数据流定义为“只能以事先规定好的顺序被读取一次的数据的一个序列”。 展开全文
数据流(data stream)是一组有序,有起点和终点的字节的数据序列。包括输入流和输出流。数据流最初是通信领域使用的概念,代表传输中所使用的信息的数字编码信号序列。这个概念最初在1998年由Henzinger在文献87中提出,他将数据流定义为“只能以事先规定好的顺序被读取一次的数据的一个序列”。
信息
外文名
data stream
提出时间
1998年
发展原因
2个
计算类型
可分为两类:基本计算和复杂计算
释    义
以规定顺序被读取一次的数据序列
中文名
数据流
数据模式
4个
概念提出人
Henzinger
数据流产生背景
数据流应用的产生的发展是以下两个因素的结果:已经能够持续自动产生大量的细节数据。这类数据最早出现于传统的银行和股票交易领域,后来则也出现为地质测量、气象、天文观测等方面。尤其是互联网(网络流量监控,点击流)和无线通信网(通话记录)的出现,产生了大量的数据流类型的数据。我们注意到这类数据大都与地理信息有一定关联,这主要是因为地理信息的维度较大,容易产生这类大量的细节数据。需要以近实时的方式对更新流进行复杂分析。对以上领域的数据进行复杂分析(如趋势分析,预测)以前往往是(在数据仓库中)脱机进行的,然而一些新的应用(尤其是在网络安全和国家安全领域)对时间都非常敏感,如检测互联网上的极端事件、欺诈、入侵、异常,复杂人群监控,趋势监控(track trend),探查性分析(exploratory analyses),和谐度分析(harmonic analysis)等,都需要进行联机的分析。在此之后,学术界基本认可了这个定义,有的文章也在此基础上对定义稍微进行了修改。例如,S. Guha等[88]认为,数据流是“只能被读取一次或少数几次的点的有序序列”,这里放宽了前述定义中的“一遍”限制。为什么在数据流的处理中,强调对数据读取次数的限制呢?S. Muthukrishnan[89]指出数据流是指“以非常高的速度到来的输入数据”,因此对数据流数据的传输、计算和存储都将变得很困难。在这种情况下,只有在数据最初到达时有机会对其进行一次处理,其他时候很难再存取到这些数据(因为没有也无法保存这些数据)。
收起全文
精华内容
下载资源
问答
  • 一、数据流图 ( DFD ) 简介 、 二、数据流图 ( DFD ) 概念符号 、 1、数据流 、 2、加工 ( 核心 ) 、 3、数据存储 4、外部实体 、 三、数据流图 ( DFD ) 分层 、 1、分层说明 、 2、顶层数据流图 、 3、中层数据流图...





    一、数据流图 ( DFD ) 简介



    数据流图 ( Data Flow Diagram ) :

    需求分析 阶段 , 使用的工具 , 在 “结构化分析” 中 , 数据流图 ( DFD ) 使用频率很高 ;

    数据流图涉及内容 : 基本概念符号 , 数据字典 , 数据平衡原则 ;





    二、数据流图 ( DFD ) 概念符号





    1、数据流


    数据流 : 数据流由 一组固定成分的数据 组成 , 表示 数据的流向 ;

    数据流命名 : 每个数据流都有一个 命名 , 该命名表达了 该数据流传输 数据的含义 ; 如在箭头上标注 “账号信息” , 表示该数据流是传输账号信息 的 , 表示 数据的内容 ;

    数据字典 : 数据流箭头上只标明了 “账号信息” , 没有具体的格式内容 , 是只有账号 , 还是有账号/密码/验证码等信息 , 这些数据详细格式 , 都在 数据字典中定义 ;

    符号表示 : 数据流 使用 箭头 表示 , 箭头所指的方向 , 代表了数据流向 ;
    在这里插入图片描述



    2、加工 ( 核心 )


    加工 : 描述 “输入数据流”“输出数据流” 之间的变换 , 即 对数据进行了什么样的处理 , 使得 “输入数据流” 变为 “输出数据流” ;

    主要操作 : 在程序中的体现是 处理 数据的过程 , 向 “加工” 中输入数据流后 , 将数据进行加工 , 处理 , 变换后 , 产生新的 “输出数据流” ;

    符号表示 : 使用 圆形 / 圆角矩形 表示加工 ;
    在这里插入图片描述



    3、数据存储


    数据存储 ( 文件 ) : 表示 暂时存储的数据 , 数据存储的粒度是以 表 为单位 ;

    文件名称 : 每个 数据存储 ( 文件 ) 都有 名字 ;

    方向 : 流向文件的数据流 表示 向文件内写入内容 , 从文件流出的数据流 表示 从文件读取内容 ;

    符号表示 : 使用 双横线 / 半框形矩形 表示
    在这里插入图片描述



    4、外部实体


    外部实体 : 软件系统之外的 人员 / 组织 ;

    符号表示 : 矩形 ;

    在这里插入图片描述





    三、数据流图 ( DFD ) 分层



    在这里插入图片描述



    1、分层说明


    数据流图分层 , 最上层是 顶层数据流图 , 第二层是 0 0 0 层数据流图 , ⋯ \cdots , 最底层是 底层数据流图 ,

    “顶层数据流图”“底层数据流图” 之间是若干 中层数据流图 ,

    中层数据流图 需要进行编号 , 0 0 0 开始编号 ;



    2、顶层数据流图


    顶层数据流图 : 中间的椭圆 是需要开发的 系统 , 周边的矩形 表示的是 外部实体人或组织 , 外部实体 与 系统 之间 , 有数据传输关系 ;

    一个形象的说明是 多个人吃火锅 , 外层周边是人 , 中心位置火锅是系统 ;


    顶层数据流图 能够表达的信息是非常有限的 , 其 将整个系统 , 使用一个节点表示 ,

    其可以体现出 系统与外界实体之间的交互 ,

    但是 系统内部的情况 , 系统内部模块之间的数据交换 是没有体现的 ;



    3、中层数据流图


    “顶层数据流图” 进行细化 , 细化后的 0 0 0 层数据流图 ,

    与 顶层数据流图 比较没有变化的部分 : 外部实体 , 外部实体与系统之间的数据流 , 是没有变化的 ;

    变化部分 : 有变化的部分是系统内部 , 系统内部进行了细化 , 原来系统是一个节点 , 在 中层数据流图 中 , 会将一个节点 拆分成 多个节点 , 这些节点就是系统中的数据处理部件 , 即 加工 ;

    这些数据处理部件 ( 加工 ) 之间会有数据流的交互 ,



    4、底层数据流图


    针对每个加工 节点 , 将其拆分 , 绘制其中的更详细的数据流转情况 ;

    数据流图 ( DFD ) 分层 , 是从 顶层 -> 中层 -> 底层 , 逐层进行分解 , 这种分解思路 , 与结构化的开发方法 , 是完全匹配的 ;

    因此 , 数据流图 是 结构化 开发方法中 , 最常用的工具 ;

    绘制数据流图时 , 要保证 上一层数据流图 与 下一层数据流图 保持平衡 , 这就是 数据流图平衡原则 ;

    展开全文
  • 数据流图——从软考真题中学画数据流图DFD

    千次阅读 多人点赞 2019-03-28 16:27:45
    根据层次关系一般将数据流图分为顶层数据流图、中间数据流图和底层数据流图,除顶层图外,其余分层数据流图从0开始编号。对任何一层数据流图来说,称它的上层数据流图为父图,在它的下一层的数据流图为子图。也就是...

    题目

    建议将题目复制到word后与此文分屏查看。后面需要多次查看题目。

    某高校欲开发一个成绩管理系统,记录并管理所有选修课程的学生的平时成绩和考试成绩,
    其主要功能描述如下:
    1. 每门课程都有3到6个单元构成,每个单元结束后会进行一次测试,其成绩作为这门课程
    	的平时成绩。课程结束后进行期末考试,其成绩作为这门课程的考试成绩。
    2. 学生的平时成绩和考试成绩均由每门课程的主讲教师上传给成绩管理系统。
    3. 在记录学生成绩之前,系统需要验证这些成绩是否有效。首先,根据学生信息文件来确
    	认该学生是否选修这门课程,若没有,那么这些成绩是无效的;如果他的确选修了这门课
    	程,再根据课程信息文件和课程单元信息文件来验证平时成绩是否与这门课程所包含的
    	单元相对应,如果是,那么这些成绩是有效的,否则无效。
    4. 对于有效成绩,系统将其保存在课程成绩文件中。对于无效成绩,系统会单独将其保存
    	在无效成绩文件中,并将详细情况提交给教务处。在教务处没有给出具体处理意见之前,
    	系统不会处理这些成绩。
    5. 若一门课程的所有有效的平时成绩和考试成绩都已经被系统记录,系统会发送课程完成
    	通知给教务处,告知该门课程的成绩已经齐全。教务处根据需要,请求系统生成相应的
    	成绩列表,用来提交考试委员会审查。
    6. 在生成成绩列表之前,系统会生成一份成绩报告给主讲教师,以便核对是否存在错误。
    	主讲教师须将核对之后的成绩报告返还系统。
    7. 根据主讲教师核对后的成绩报告,系统生成相应的成绩列表,递交考试委员会进行审
    	查。考试委员会在审查之后,上交一份成绩审查结果给系统。对于所有通过审查的成
    	绩,系统将会生成最终的成绩单,并通知每个选课学生。
    现采用结构化方法对这个系统进行分析与设计,得到如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。  
    


      
      图1-1
      顶层数据流图
      

      

     
      图1-2
      0层数据流图
      

    【问题1】(4分)
      使用说明中的词语,给出图1-1中的外部实体E1~E4的名称。
    【问题2】(3分)
      使用说明中的词语,给出图1-2中的数据存储D1~D5的名称。
    【问题3】(6分)
      数据流图1-2缺少了三条数据流,根据说明及数据流图1-1提供的信息,
      分别指出这三条数据流的起点和终点。
    【问题4】(2分)
      数据流图是在系统分析与总体设计阶段宏观地描述系统功能需求的重要图形化工具,程序流
      程图也是软件开发过程中比较常用的图形化工具。简要说明程序流程图的适用场合与作用。
    

    画顶层图

    我们先不看给出的图,凭借题目给出的信息自己画图,先是顶层图,画顶层图步骤有3步:
    1.将软件系统看作加工,
    2.确定外部实体,
    3.画出数据流
    找到题目中的软件系统,题目第一句就可以看到“成绩管理系统”

    浏览题目一遍,不难找出所有外部实体

    根据各个外部实体与软件系统进行的交互操作,可以得到数据流

    与题目给出的图对比
    在这里插入图片描述
    【问题1】的答案就已经出来了,很明显E1为考试委员会,E2为主讲教师,E3为学生,E4为教务处。

    画0层图

    接下来是画0层图,0层图作画步骤:
    1.细分顶层图的加工
    2.数据流连接加工
    再次从头开始看全文,看到第3句,
    在记录学生成绩之前,系统需要验证这些成绩是否有效
    这里之前是被我们忽略掉的,在画顶层图时,这里算作总的成绩管理系统的加工,现在需要细分成绩管理系统了,我们就需要把此系统的功能提取出来——命名为“验证成绩”的加工。

    继续往后看,到第4句
    对于有效成绩,系统将其保存在课程成绩文件中。对于无效成绩,系统会单独将其保存在无效成绩文件中,并将详细情况提交给教务处。
    这里我们又看到系统的两个功能,“保存课程成绩文件”与“保存无效成绩文件”,也就是两个加工。

    继续看到第5句
    若一门课程的所有有效的平时成绩和考试成绩都已经被系统记录,系统会发送课程完成通知给教务处,告知该门课程的成绩已经齐全。教务处根据需要,请求系统生成相应的成绩列表
    前面的“系统会发送课程完成通知给教务处”,明显是数据流而不算作是功能,后面的“请求系统生成相应的成绩列表”才体现出功能,我们命此加工为“生成成绩列表”。

    直到最后的一句
    “系统将会生成最终的成绩单,并通知每个选课学生。”
    可见又是一个加工,我们命名为“生成成绩单”

    下面要做是补全数据流
    所有这些加工实质就是整体的软件系统的加工,所以可以先把顶层图的数据流照搬过来

    这里注意每条数据流要对应好加工,图中省略了外部实体,这没关系。
    然后加上数据存储文件

    画到这一步并没有完,有部分数据流并没表示出来,比如保存课程成绩文件与保存无效成绩文件的数据输入还有生成成绩单的数据输入流,但没关系,解第二题足够了,若把所有数据流加上那第三题就迎刃而解了。在这里插入图片描述
    【问题2】答案
    D1就是学生信息文件夹
    D2为课程单元信息文件
    D3为课程信息文件
    D4为课程成绩文件(图中我命名为了 有效成绩文件)
    D5为无效成绩文件

    第一次画就是上图那样不能掌握布局所以很乱,第二次画时根据这张图规划好布局就可以画得更工整了
    【问题3】
    第一条数据流:由说明的第5条可知,生成成绩列表时,是需要从课程成绩文件中获取信息的,“课程成绩文件”是图中的D4。而D4和加工4之间并没有数据流,因此这就是一条缺失的数据流。
      第二条数据流:生成成绩单时是需要学生信息的。且不符合数据输入输出平衡(文末有相关知识),加工5应该从D1中获取相应的信息,这样就找到了第二条数据流。
      第三条数据流:说明的第7句告诉我们,只有“对于所有通过审查的成绩,系统将会生成最终的成绩单,并通知每个选课学生”。也就是说,从成绩列表到成绩单的生成是有条件的。这意味着,在加工4和加工5之间应该存在一条数据流,这就是第3条数据流。
    所以完整的0层图应如下图所示
    在这里插入图片描述

    解题技巧

    (1)适当地为数据流、加工、数据存储、外部实体命名,名字应反映该成分的实际含义, 避免空洞的名字。

    (2)画数据流而不要画控制流。

    (3)每条数据流的输入或者输出是加工。

    (4)—个加工的输出数据流不应与输入数据流同名,即使它们的组成成分相同。

    (5)允许一个加工有多条数据流流向另一个加工,也允许一个加工有两个相同的输出数据流流向两个不同的加工。

    (6)保持父图与子图平衡。
    为了表达较为复杂问题的数据处理过程,用一个数据流图往往不够。一般按问题的层次结构进行逐步分解,并以分层的数据流图反映这种结构关系。根据层次关系一般将数据流图分为顶层数据流图、中间数据流图和底层数据流图,除顶层图外,其余分层数据流图从0开始编号。对任何一层数据流图来说,称它的上层数据流图为父图,在它的下一层的数据流图为子图。也就是说,父图中某加工的输入输出数据流必须与它的子图的输入输出数据流在数量和名字上相同。值得注意的是,如果父图的一个输入(或输出)数据流对应于子图中几个输入(或输出)数据流,而子图中组成这些数据流的数据项全体正好是父图中的这一个数据流,那么它们仍然算是平衡的。

    (7)在自顶向下的分解过程中,若一个数据存储首次出现时只与一个加工有关,那么这个数据存储应作为这个加工的内部文件而不必画出。

    (8)保持数据守恒。
    也就是说,一个加工所有输出数据流中的数据必须能从该加工的输入数据流中直接获得,或者是通过该加工能产生的数据。每个加工必须有输入数据流和输出数据流,反映此加工的数据来源和加工变换结果。一个加工的输出数据流只由它的输入数据流确定。数据流必须经过加工,即必须进入加工或从加工中流出。每个加工必须既有输入数据流,又有输出数据流。

    (9)在整套数据流图中,每个数据存储必须既有读的数据流,又有写的数据流。但在某 一张子图中可能只有读没有写,或者只有写没有读。

    展开全文
  • 数据流

    千次阅读 热门讨论 2015-04-29 08:01:23
     数据流图(Data Flow Diagram):简称DFD,它从数据传递和加工角度,以图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程,是结构化系统分析方法的主要表达工具及用于表示软件模型的一种图示...

    简介

      数据流图(Data Flow Diagram):简称DFD,它从数据传递和加工角度,以图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程,是结构化系统分析方法的主要表达工具及用于表示软件模型的一种图示方法。

      数据流图是结构化系统分析方法中使用的工具,它以图形的方式描绘数据在系统中流动和处理的过程,由于它只反映系统必须完成的逻辑功能,所以它是一种功能模型。在结构化开发方法中,数据流图是需求分析阶段产生的结果。

      数据流图英文缩写DFD(Data Flow Diagram)它是描绘信息流和数据从输入移动到输出的过程中所经受的变换。

      数据流图从数据传递和加工的角度,以图形的方式刻画数据流从输入到输出的移动变换过程。

    数据流图包括:

      a.指明数据存在的数据符号,这些数据符号也可指明该数据所使用的媒体;

      b.指明对数据执行的处理的处理符号,这些符号也可指明该处理所用到的机器功能;

      c.指明几个处理和(或)数据媒体之间的数据流的流线符号;

      d.便于读、写数据流图的特殊符号。

    组成元素

      →:数据流。数据流是数据在系统内传播的路径,因此由一组成分固定的数据组成。如订票单由旅客姓名、年龄、单位、身份证号、日期、目的地等数据项组成。由于数据流是流动中的数据,所以必须有流向,除了与数据存储之间的数据流不用命名外,数据流应该用名词或名词短语命名。

      □:数据源(终点)。代表系统之外的实体,可以是人、物或其他软件系统。

      ○:对数据的加工(处理)。加工是对数据进行处理的单元,它接收一定的数据输入,对其进行处理,并产生输出。

      〓:数据存储。表示信息的静态存储,可以代表文件、文件的一部分、数据库的元素等。

    设计原则

      1.一个加工的输出数据流不应与输入数据流同名,即使它们的组成成分相同。

      2.保持数据守恒。也就是说,一个加工所有输出数据流中的数据必须能从该加工的输入数据流中直接获得,或者说是通过该加工能产生的数据。

      3.每个加工必须既有输入数据流,又有输出数据流。

      4.所有的数据流必须以一个外部实体开始,并以一个外部实体结束。

      5.外部实体之间不应该存在数据流

    查看错误技巧

      首先根据父图中的输入输出各自总数来查看子图中是否符合,然后,在看各个子项中的输入输出直接的细节关联是否符合具体业务
    和规则,根据试题描述实体和实体之间是不能有数据流的;存储于存储直接也不能有数据流;实体和存储直接也不能有数据流;对于一个加工而言,输入和输出流的名字不能相同;加工不能只进不出,或只出不进。

    展开全文
  • 数据流分析

    千次阅读 2019-03-22 17:49:44
    最近在看Accurate Recovery of Functions in COTS Binaries,但是关于数据流分析没看懂,找到了这篇博客,感觉写的很好,加深了自己理解 引子 编译器后端会对前端生成的中间代码做很多优化,也就是在保证程序语义...

    最近在看Accurate Recovery of Functions in COTS Binaries,但是关于数据流分析没看懂,找到了这篇博客,感觉写的很好,加深了自己理解


    引子

    编译器后端会对前端生成的中间代码做很多优化,也就是在保证程序语义不变的前提下,提高程序执行的效率或减少代码size等优化目标。优化需要依靠代码分析给出的“指导信息”来相应地改进代码,而代码分析中最重要的就是数据流分析。另外数据流分析是程序静态分析的基础。所以掌握数据流分析对编译后端极为重要。

    • 何为数据流分析
    • 数据流抽象
    • 数据流分析模式
    • 基本块上的数据流模式

    何为数据流分析

    数据流分析指的是一组用来获取有关数据如何沿着程序执行路径流动的相关信息的技术《编译原理》

    数据流分析的目的是提供一个过程(或一大段程序)如何操纵其数据的全局信息《高级编译器设计与实现》

    从上面的表述中,我们可以看出数据流分析通过静态代码来“推断”程序动态执行的相关信息,数据流分析并不真正执行程序。虽然数据流分析和符号执行在某些方面比较相似,但还是两种完全不同的概念,更确切的说数据流分析是符号执行的基础。

    数据流分析和符号执行从某些方面都很相似,例如符号执行有程序点(ProgramPoint)的概念,并且在当前程序点存储着程序运行到此刻的所有状态和值信息(一般情况下不会维护历史程序点的信息,开销太大)。数据流分析中也有程序点的概念,程序点存储着数据流信息。两者都是在CFG(Control Flow Graph)图的基础上,进行的分析。Clang的静态分析示意图如下所示,Clang会时刻维护符号执行当前的状态和内存信息。从这一点上看,符号执行和虚拟机更为相似。

    这里写图片描述

    但数据流分析和符号执行还是不同的,虽然都有程序点,但程序点存储的信息却是两个不同的概念。数据流分析中程序点存储的是数据流值,这些数据流值是和具体的数据流问题相关的,有可能是当前程序点的定值信息,也有可能是可用表达式信息,这些信息标识着该程序内含的一些属性。符号执行中程序点存储的是程序符号执行到此处的所有状态和值信息,这些信息和程序运行更为相关。

    而且两者的分析方法也不同,符号执行是单次执行,而数据流分析大多采用迭代分析的框架,然后在迭代分析的过程中不断更新程序点的数据流信息,最终得到比精确解更小(更保守)的解。但为了进行更为激进的优化,要求数据流分析在保证保守的同时又尽可能是激进的。


    数据流抽象

    前面的文章中我们也提到过,程序的执行可以看作是程序状态的一系列转换。程序状态是由程序中所有变量的值以及运行时栈帧上的相关值组成。程序语句对应着转换函数,将前一个程序点的输入程序状态转换到下一个程序点的新的输出状态。

    这里写图片描述

    上图所示中的红点表示的就是程序点,数据流转换函数就是作用在程序点上的状态,并沿着程序路径一步步进行的。其实这个过程就是一个自动机,抽象出的自动机如下图所示。程序点代表自动机中的一个节点,程序语句或者说是转换函数代表自动机中的一条边。一般来说,一个程序有无穷多条可能的执行路径,执行路径的长度并没有上界(例如死循环)。程序分析可以推断出各个程序点的程序状态(有穷的特性集合),当然很少有哪种数据流分析会用到所有的数据流信息,一般只是提取出感兴趣的特性集合进行分析。

    这里写图片描述

    我们考虑的多数数据流分析问题关注的是各种程序对象(常数,变量,定值,表达式等)的集合,以及在过程内任意一点这些对象的什么集合是合法的有关判断。另外在数据流分析中,一般是会忽略掉路径条件判断的,也就是说默认所有路径都可达(这种近似是正确且有效的,现在我还没有找到忽略控制条件也能够保证数据流分析正确性的证明!),在程序分析中忽略掉程序控制条件,所以核心的部分就是状态数据如何变化了,也就是数据流分析。

    我们虽然可以对过程的控制流图进行数据流分析,但通常更有效的做法是将它分解为局部数据流分析全局数据流分析,局部数据流分析针对每一个基本块进行,全局数据流分析针对控制流图进行分析,其实就是一个粒度问题。我们可以将同一个基本块内的各个语句的作用综合起来合成整一个基本块的作用。例如我们可以将上面的自动机改造为基于基本块的形式,如下图所示。

    这里写图片描述


    数据流分析模式

    在数据流分析中,程序点一般和数据流值(data-flow value)关联起来,注意这个数据流值不是程序中变量的值。“这个值是在该点可能观察到的所有程序状态的集合的抽象表示”,这句话说起来有点绕口,每个数据流分析问题都有其对应的值域,每个程序点的数据流值都是该值域的子集。比如,到达定值的数据流值的域是程序的定值集合的所有子集的集合。某个数据流值是一个定值的集合,数据流分析的目的就是推导出所有程序点与其对应的到达定值的集合。

    一个定值是对某个变量的赋值。可能沿着某条路径到达某个程序点的定值称为到达定值(reaching definition)。

    我们把每个语句s之前和之后的数据流值分别记为IN[s]和OUT[s]。数据流问题就是对一组约束求解,得到所有IN[s]和OUT[s]的结果。

    这里写图片描述

    每个语句都约束了该语句之前程序点状态和之后程序点状态的关系,也就是说语句s限定了IN[s]和OUT[s]之间的关系。整个程序就是由无穷个这样的约束构成的。数据流问题(data-flow problem)就是对这一组约束求解,另外约束不仅有语义(传递函数)上的约束,更有基于控制流的约束。

    传递函数

    在一个语句之前和之后的数据流值受该语句语义的约束,也就是程序语句前后程序点的数据流值受该语句语义的约束,这种约束关系成为传递函数(transfer function)

    传递函数有两种风格:数据流信息可能沿着执行路径向前传播,或者沿着程序路径逆向流动,相应的就有前向(forward)数据流问题后向(backward)数据流问题

    Forward data-flow analysis, Information at a node is based on what happens earlier in the flow graph. 
    Backward data-flow analysis, Information at a node is based on what happens later in the flow graph.

    大部分人刚接触到后向数据流问题时会比较困惑,数据流值怎么会依赖于后面的数据流值信息呢。其实这是由于有些人还是对于数据流值的概念不是很理解,将数据流值简单的归结于变量的值,如果这么对比的话,就会出现矛盾

    对于前向数据流问题,一个程序语句s的传递函数以语句前程序点的数据流值作为输入,并产生出语句之后程序点对应的新数据流值。例如到达定值就是前向数据流问题。

    这里写图片描述

    对于后向数据流问题,一个程序语句s的传递函数以语句后的程序点的数据流值作为输入,转变成语句之前程序点的新数据流值。例如活变量分析就是后向数据流问题。

    这里写图片描述

    控制流约束

    第二组关于数据流值的约束是从控制流中得到的,基本块内都是顺序执行,没有控制流的约束。但是基本块之间有相应的控制流约束,例如一个基本块的最后一个语句和后继基本块的第一个语句之间的约束,这些约束比较复杂。

    基本块上的数据流模式

    前面我们已经提到过程序语句的约束分为两种,基于程序语句语义的约束和基于控制流的约束。基本块之间的约束都是基于控制流的约束,由于基本块内没有分支,所以我们可以基于整个基本块来描述基本块对于数据流值的约束,而不是基于程序语句(前面也提到过,我们可以使用局部数据流和全局数据流分析结合更加高效)。我们以基本块为最小单位来研究基本块上的数据流模式。

    这里写图片描述

    基本块的传递函数和基本块内程序语句所表示的传递函数之间的关系如上图所示。那么基本块之间的约束是如何的呢?如下图所示。

    这里写图片描述

    图中展示出来的是基本块之间的前向数据流问题的约束方程。后向数据流问题的方程如下图所示。

    这里写图片描述

    数据流分析就是根据这一组约束,得到一个满足这些约束的解。和线性算术方程不同,数据流方程通常没有唯一解。数据流分析的目标是寻找一个最“精确的”满足这两组约束(即控制流和传递函数)的解,当然这个解必须是保守的,能够保证我们根据这个解进行代码优化不会导致不安全的转换。

    当然数据流分析,不是直接联立方程求解的,一般是通过一种迭代分析的方法来求解的。

    这里写图片描述

    到达定值
    什么是到达定值
    “到达定值”是最常见的和有用的数据流模式之一。编译器能够根据到达定值信息知道 x 在点 p 上的值是否为常量,而如果 x 在点 p 上被使用,则调试器可以指出x是否未经定值就被使用。

    如果存在一条从紧随在定值 d 后面的程序点到达某一个程序点 p 的路径,并且在这条路径上 d 没有被“杀死”,我们就说定值 d 到达程序点 p 。如果在这条路径上有对变量x的其他定值,我们就说变量 x 的这个定值(定值 d )被”杀死”了。 《编译原理》

    到达定值的示意图如下所示。

    è¿éåå¾çæè¿°

    注:上面这个图不严谨,p是程序点,应该紧挨着下面的矩形而不是表示矩形。图中的矩形表示的是一条语句。 
    到达定值有以下用法:

    创建use/def链
    常量传播
    循环不变量外提

    è¿éåå¾çæè¿°
    变量x的一个定值是(可能)将一个值赋给x的语句。过程参数、数组访问和间接引用都可以有别名,因此指出一个语句是否向特定程序变量x赋值并不是件很容易的事情。 《编译原理》

    存在别名的情况下的需要作别名分析,如果为了提高分析效率而不介意损失一些分析精度的话,可以做保守估计,例如我们不知道当前语句对哪个变量赋值,我们就在此处针对每个变量产生一个定值。这是一种无奈的折中。此处我们不考虑别名情况。

    到达定值的传递函数


    首先我们做一些假设:

    一个语句节点至多能够对一个变量定值
    我们可以通过节点编号索引到该赋值语句
    当然,在实际情况中一个语句节点有可能会对不止一个变量定值。下面我们定义一下 gen [n]函数和 kill [n]函数。

    gen[n] :节点 n 产生的定值(假设一个语句节点至多一个定值) 
    kill[n] :节点 n“杀死”的定值


    上面的表格列举了一些程序语句的 gen 和 kill 传递函数形式。第一行的列举的“s: t = b op c”,产生了定值s并”杀死”了除定值s以外所有对变量t的定值。 
    注意:定值是一个程序语句,对同一个变量可以存在多个不同的定值

    我们也可以先计算出各个程序语句的 gen 和 kill 结果,然后综合基本块中的各个语句生成整个基本块的 gen 和 kill 集合。如下图所示,其中我们先默认各个基本块的起始和结束处所有定值都可以到达,下图程序中总共有7个定值,分别为d1, d2, d3, d4, d5, d6, d7。

    经过第一次的传递函数作用,各个基本块到达定值集合的变化情况如图左所示。

    到达定值的保守性


    在前面介绍数据流分析时,曾经提到过数据流分析允许一定的不精确性。但是它们都是在“安全”或者说“保守”的方向上不精确。如下图所示:

    è¿éåå¾çæè¿°

    只要我们得到的解偏于保守的一方即可,然后再尽力的向精确的方向靠近,不同的应用“保守”的定义也不同。在 大部分到达定值的应用 中,在一个定值不可能到达某点的情况下假设其能够到达是保守的。如下图所示:

    è¿éåå¾çæè¿°

    因此在设计一个数据流模式的时候,我们必须知道这些信息将如何被使用,并保证我们做出的任何估算都是在“保守”或者说“安全”的方向上。每个模式和应用都要单独考虑。 《编译原理》

    也就是说,不能套用同一个模式来判断“保守”或者“安全”的方向,在可用表达式中,“安全”的定义就和到达定值不同。如果可用表达式没有到达某个程序点,而得出的解表明到达了,则这是不安全的。

    到达定值的传递方程以及控制流方程


    到达定值对于单个语句的传递方程如下图所示,一个基本块内的依据就是按照这组方程建立起联系的。和单个语句一样,一个基本块也会生成一个定值集合,并杀死一个定值集合。

    è¿éåå¾çæè¿°

    根据基本块之间的控制流得到的约束集合,我们可以生成一个控制流方程。其实控制流方程的含义就是在路径交叉点进行数据流值的交汇,在到达定值中,交汇运算就是并集运算(∪)。

    è¿éåå¾çæè¿°

    对于到达定值来说,只要一个定值能够沿着至少一条路径到达某个程序点,就说这个定值到达该程序点。所以控制流方程的交汇运算时并集,但是对于其他一些数据流问题交汇运算时交集,例如可用表达式。

    到达定值的迭代分析算法


    假设每个控制流图都有两个空的基本块,代表了控制流图的ENTRY节点和EXIT节点。由于没有定值到达这个图的开始,所以基本块ENTRY的传递函数是一个简单的返回空集Ø的常函数,即OUT[ENTRY] = Ø.

    到达定值问题使用下面方程的定义: 
    OUT[ENTRY] = Ø 
    且对于所有的不等于ENTRY的基本块B,有

    OUT[B] = gen(B) U ( IN[B] - kill(B) ) 
    IN[B] = U OUT[P] ,其中P是B的一个前驱基本块

    我们可以使用下面的算法来求这个方程组的解。这个算法来自《编译原理》中到达定值部分。

    到达定值算法: 
    输入:一个流图,其中每个基本块 B 的 kill(B) 集和 gen(B) 集都已经计算出来了。 
    输出:到达流图中各个基本块 B 的入口点和出口点的定值的集合,即 IN[B] 和 OUT[B] 。 
    方法:我们使用迭代的方法来求解。一开始,我们“估计”对于所有基本块 B 都有 OUT[B] = Ø,并逐步逼近想要的 IN 和 OUT 值。因为我们必须不停地迭代直到各个 IN 值(因此各个 OUT 值也)收敛,所以我们使用一个 bool 变量 change 来记录每次扫描各基本块时是否有 OUT 值发生改变。

    è¿éåå¾çæè¿°

    从算法中我们可以明确看到,数据流值是从前驱 P 到 IN[B] 然后再流向 OUT[B] 这样一个从前向后不断传播的。然后从Ø 不断扩大直到越过精确解到达“保守解”。

     

    迭代算法不断从空向到达定值结果越来越多的方向靠近,最终会跨越精确解到达保守解的部分,主要因为两个原因导致一定会越过精确解: 
    (1)不考虑路径条件,假设所有路径都可达;这样某些定值最终会到达他们本来到达不了的地方 
    (2)存在别名时,给无法确认的“别名”赋值时,给所有变量添加一个定值(注意此处并没有kill掉所有的定值,因为添加所有可能的定值,删除肯定被kill掉的定值,这样才能保证“保守”)

    这个算法还有可以改进的地方,其中一个就是精心安排迭代分析时基本块的顺序,基本按照CFG从入口ENTRY到EXIT的顺序。在《迭代数据流分析中的逆后序(Reverse Postorder)》中我们会提到,对于前向数据流问题来说,逆后序是最高效的方式。如果当前基本块的到达定值结果发生了改变,那么就把其所有后继基本块加入待迭代的工作列表 WorkList 。

    另外到达定值使用了一种位向量的结构,来表示到达定值集合。即每个程序点的到达定值使用一个位向量表示,例如该程序有7个定值,那么位向量为7位,初始向量“0000 000”表示此时定值为空,如果第3号定值到达了当前程序点,那么位向量为“0010 000”。

    活跃变量分析


    活跃变量分析是一个后向数据流分析问题,因为当前变量x是否在未来的某个地方被用到,只能通过从后面节点的信息中获知。

    A variable is live at a particular point in the program if its value at that point will be used in the future(dead, otherwise) 
    To compute liveness at a given point, we need to look into the future

    活跃变量的重要用途之一是为基本块进行寄存器分配。计算机技术中有很多类似于寄存器分配的场景,也就是有限的资源去满足无限的需求,例如cache有限,但是欲放入cache的数据却又很多;另或者主存空间有限,而磁盘中欲放如主存的数据有很多等。所以这时候就需要某种资源共享,保证不冲突,并且采用某种算法来求得把资源分配给哪些数据更合理。例如LRU换页算法,或者cache的空间局部性原理等。当然这些问题都不是程序员需要深入考虑的,底层软件或工具软件会在背地里完成。

    Register Allocation

    A program contains an unbounded number of variables
    Must execute on a machine with a bound number of registers
    Two variables can use the same register if they are never in use at the same time(i.e, never simultaneously live).
    所以寄存器分配需要活变量的信息来决定两个变量能否使用同一个寄存器,另外在所有寄存器都被占用时,如果我们还需要申请一个寄存器的话,那么应该考虑使用一个存放了已死亡的值的寄存器,因为这个值我们不需要保存到内存,无需register spill。

    活跃变量的数据流方程


    我们给出两个定义:

    def(or definition)
    use
    def[v] = 定义变量v的所有CFG节点集合 
    def[n] = 节点n定义的变量集合

    use[v] = 使用变量v的CFG节点集合 
    use[n] = 在节点n使用的变量集合

    计算活跃性的规则:

    (1)产生活跃性

    è¿éåå¾çæè¿°

    (2)活跃性如何越过程序语句节点之间的边

    è¿éåå¾çæè¿°

    (3)活跃性如何越过程序语句节点

    è¿éåå¾çæè¿°

    我们列出活跃变量的数据流方程如下所示,注意此处我们将语义约束和控制约束同时写出来了(因为我们现在是以单个程序语句为图节点,而不是单个基本块)

    in [n] = use [n] U ( out [n] - def [n] )
    out [n] = U in [s] , 其中s是节点n的后继节点
    从这两个方程我们可以看出,对于活跃变量分析来说数据流是从后向前传播的。我们这里解释一下为什么要从out[n]中删除def[n],

    è¿éåå¾çæè¿°

    下面给出活跃变量分析的算法:

     è¿éåå¾çæè¿°
    注:此处CFG是以程序语句为单个节点构建的

    当然这个算法没有考虑到CFG图中节点的顺序,效率比较低,我们将CFG图中的节点反序,用来求解。改进算法如下:

    è¿éåå¾çæè¿°

    我们也可以基本块为单位来就行活跃变量的分析,但是我们得首先根据基本块中程序语句的传递函数合并成为基本块的传递函数。定义如下:

    def [B] 是指如下变量的集合,这个变量在B中的定值(即被明确地)先于任何对它们的使用
    use [B]是指如下变量的集合,它们的值可能在B中先于任何对它们的定值被使用
    注意:上述我们标注的黑色部分,在def[B]中需要被明确定值,而在use中条件弱化,只需要可能就行了。类似于到达定值,这样做是为了保守性。在活跃变量中,假设变量活跃到程序结束是没有问题的,只是会损失些可以优化的点(例如寄存器分配时两个变量的活跃区间相互重叠的概率就会变得很大),但是如果将变量的活跃期缩短的话,有可能就将该寄存器挪做他用,这样就会导致程序错误。所以在活跃变量分析中,将活跃变量尽可能的向前传播是有利于偏向保守的。但是不能一味的偏于保守,否则得到的信息就没有任何价值,在保证保守的同时,尽可能的向精确解靠拢(所以杀死被明确赋值的变量)

    所以我们在杀死变量时(即在基本块内明确定义,在 def[B] 中)必须明确规定,但是尽可能地向前传播(也就是如果可能在use[B] 中,直接加入就好)。如下图所示,我们所求得的结果必须能够保证在保守解部分,并尽力向精确解靠近。为了保证保守性,需要做到如下两点:

    忽略路径分支条件,保证所有路径都可达
    只要有可能是活的,就向其中加入该变量。只有在该活跃变量被明确杀死时(例如被明确赋值),才删除

    è¿éåå¾çæè¿°
    如果以基本块为单位,那么得到的数据流方程如下图所示:

    è¿éåå¾çæè¿°

    第一个方程描述了边界条件,即在程序出口处没有变量是活跃的。 
    第二个方程说明一个变量要在进入一个基本块时活跃,必须满足两个条件中的一个:要么它在基本块内被重新定值之前就被使用;要么它在基本块的出口处活跃且在基本块内没有对它进行重新定值。 
    第三个方程说明一个变量在一个基本块的出口处活跃当前仅当它在该基本块的某个后继入口处活跃。

    和到达定值相同,活跃变量不需要在后继基本块入口都活跃,只要在其中一个基本块入口活跃即可。但是活跃变量是后向数据流模式。在各个数据流模式中,我们都沿着路径传播信息,有的数据流问题,要求对应性质需要在所有路径上都成立,而有的数据流只需要存在一个满足该性质的路径即可。

    基于基本块的活跃变量分析算法: 
    输入:一个流图,其中每个基本块的use和def已经计算出来了。 
    输出:该流图中的各个基本块B的入口和出口处的活跃变量集合,即 IN[ B ] 和 OUT[ B ]。

    è¿éåå¾çæè¿°

    该算法得到的具有最小活跃变量(亦即尽量向精确解靠近)的集合。

    展开全文
  • 软件设计师笔记之数据流

    千次阅读 2019-06-02 14:13:30
    数据流图的改错,包括修正数据流名称、数据流的起点与终点、删除多余数据流。 目录 一、数据流图技术 1. 数据流图的基本元素 2. 分层数据流图(DFD) 3. 数据字典 4. 数据平衡原则 二、作答技巧 1. 补充...
  • 数据流图的画法,如何画数据流

    千次阅读 2020-04-15 16:19:58
    1.数据流图的定义: 数据流图是结构化分析方法中使用的工具,它以图形的方式描绘数据在系统中流动和处理的过程,由于它只反映系统必须完成的逻辑功能,所以它是一种功能模型。 数据流图英文缩写DFD(Data Flow ...
  • 数据流数据流框架

    千次阅读 2018-07-29 15:39:38
    1,数据流是行为与响应的抽象。 用户在页面上输入表单、按下按钮、拖拽等行为,页面会根据用户的行为给出一些响应,如刷新、跳转、局部刷新、Ajax局部刷新、数据更新等。以对象、方法来把它们抽象出来,这就是数据...
  • 分层数据流图简单介绍

    千次阅读 2020-08-23 09:20:27
    一、分层数据流图 从数据流图的基本目标出发,可以考虑在一张数据流图中包含多少个元素合适的问题。一些调查研究表明,如果一张数据流图中包含的加工多于5-9个,人们就难于领会它的含义了。因此为了表达较为复杂问题...
  • 一、数据字典 、 二、数据流图平衡原则 、 1、父图 ( 上层数据流图 ) 与 子图 ( 下层数据流图 ) 平衡 、 2、子图内平衡 、 三、数据流图绘制原则 、
  • 软件工程数据流图的画法

    千次阅读 多人点赞 2019-04-27 19:55:49
    并且,数据流的分析过程是逐步对实际过程求精的,从顶层数据流图,到分层数据流图,数据流,过程类型也逐步增加,直到形成最后的数据字典和底层数据流图。需要注意的是数据流图和程序设计中的程序流程图(Flow Chat...
  • 控制流和数据流

    万次阅读 2018-03-06 00:04:48
    数据流 数据流——描述程序运行过程中数据的流转方式及其行为状态 在MVC模型中,Model层的本质就是“数据”,数据在MVC的各个构成要素中流转并且在不同的层次扮演着不同的角色。当程序运行起来之后,我们会发现...
  • 软件工程:数据流图和结构图怎么画?

    万次阅读 多人点赞 2020-09-01 18:43:03
    文章目录Step 1:根据软件的功能描述,绘制数据流图:Step 2:根据数据流图,分级绘制结构图:•边界划分:•第一级分解:•第二级分解:•精化减少耦合: Step 1:根据软件的功能描述,绘制数据流图: 问题表述: ...
  • uml:什么是数据流

    千次阅读 2019-05-19 11:04:52
    什么是数据流图? 数据流图 (DFD) 用于表示业务信息系统中的数据流,它表达了系统中的据传从输入到存储间所涉及的程序。 数据流图可以分为逻辑形和物理形。逻辑数据流图描述了用以完成某业务功能所涉及的、业务...
  • 理解实时数据流与离线数据流

    千次阅读 2019-07-16 19:53:19
    1.离线数据流: 该数据流日常周期性的(每周执行一次/每日执行一次/每小时执行一次)将某些数据源(Mysql/Oracle/CSV/…)等历史数据(全量数据/增量数据)迁移到某个存储引擎上(Hive/Hbase/….)。 2.实时...
  • 数据流聚类算法

    千次阅读 2018-04-27 17:17:00
     数据流的特点:海量的(massive)、时序的(temporally ordered)、快速变化的和潜在无限、高维的(potentially infinite)。  数据流挖掘的特点---挑战: (a)数据是海量的,不可能在内存及硬盘上存储整个流...
  • java数据流

    千次阅读 2018-11-13 14:44:27
    Java数据流 Java数据流分为两种:字节流(Byte)和字符流(Character) 标准流 字节流:以8位为为单位对二进制数据进行操作对数据不进行转换。这些类都是InputStream和OutputStream的子类. FileInputStream(File ...
  • 软件工程-数据流

    万次阅读 多人点赞 2019-01-10 08:39:57
    (1)数据流图1缺少了一条数据流(在图2中也未给出该数据流),请给出此数据流的起点和终点,并采用说明中的词汇给出此数据流名。 (2)数据流图2中缺少了与“查询房屋”加工相关的数据流,请指出此数据流的起点...
  • 一、概念 它是将提供给用户的业务流程图(“物理模型”)进行功能建模,转化成开发...即在DFD中包括哪些主要元素,数据流、加工、数据存储、外部实体。 (1)数据流:用单箭头表示,如――>。是由一组固定成分的数.
  • 软件工程-分层数据流图的画法

    千次阅读 多人点赞 2020-10-26 14:35:49
    本文来源于《软件工程(第...Data Flow Diagram(简称DFD):描述输入数据流到输出数据流的变换(即加工)过程,用于对系统的功能建模,基本元素包括: 数据流图示例: 数据流图的扩充符号 描述一个加工的多个数据流之间
  • 数据流图(DFD)概念及画法

    万次阅读 多人点赞 2019-04-16 11:42:40
    转载自:... 数据流图(Data Flow Diagram):简称DFD,它从数据传递和加工角度,以图形方式来表达系统的逻辑功能、以图形的方式描绘数据在系统中流动和处理的过程,...
  • 数据流图的画法

    万次阅读 多人点赞 2015-06-28 09:48:30
    一、数据流图的基本组成成分 数据流:是由一组固定成分的数据组成,表示数据...除了流向数据存储或从数据存储流出的数据不必命名外,每个数据流必须要有一个合适的名字,以反映该数据流的含义。 加工:加工描述了输
  • 数据流中获取中位数

    万次阅读 2020-02-29 11:55:55
    数据流中获取中位数需求描述需求分析C++代码如下python代码 需求描述   有一个动态的数据流,如何比较快的获得数据流的中位数。这个过程中,数据流可能会有新的数据加入。中位数定义为元素个数为奇数的序列的...
  • 在面向数据流的设计方法中,一般把数据流图中的数据流划分为 (16) 两种。 (16)A.数据流和事务流 B.变换流和数据流 C.变换流和事务流 D.控制流和事务流 数据流的类型决定映射的方法。数据流有两种类型:变换...
  • 数据流分析初探

    千次阅读 2018-09-15 16:50:46
    什么是数据流分析 数据流分析是一种通过静态代码来“推断”程序动态执行的相关信息的技术,数据流分析并不真正执行程序。虽然数据流分析和符号执行在某些方面比较相似,但还是两种完全不同的概念,更确切的说数据流...
  • 白盒测试--数据流测试

    千次阅读 2019-06-11 11:43:05
    文章目录白盒测试--数据流测试基础定义最少测试用例数计算 白盒测试–数据流测试 基础定义 数据流测试主要用于优化代码,早期的数据流分析常常集中于定义/引用异常的缺陷。 变量被定义,但从来没有使用(未使用) ...
  • 数据流分析(一)

    万次阅读 2016-02-21 17:25:12
    优化需要依靠代码分析给出的“指导信息”来相应地改进代码,而代码分析中最重要的就是数据流分析。另外数据流分析是程序静态分析的基础。所以掌握数据流分析对编译后端极为重要。 何为数据流分析 数据流抽象 数据流...
  • 数据流图、数据字典

    千次阅读 2020-01-21 17:24:06
    结构化分析方法使用:数据流图和数据字典 数据流图 1.只能表示主要的基本逻辑功能,不考虑实现 2.描述系统逻辑模型的一种常用的工具,不存在任何物理元素,只表示信息处理情况 数据流图的层次结构: 为了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,037,655
精华内容 815,062
关键字:

数据流