數(shù)據(jù)流體系結構風格

軟件體系結構及應用

4數(shù)據(jù)流體系結構風格主要內(nèi)容■4.1

數(shù)據(jù)流體系結構風格的基本特征

■4.2管道-過濾器(pipe-and-filter)■

4.3

批處理(batch

sequential)■4.4批處理與管道-過濾器的比較4.1數(shù)據(jù)流體系結構風格

的基本特征mA

dataflow

system

is

one

in

which-

theavailabilityofdatacontrolstheomputation(

數(shù)據(jù)的可用性決定著處理<計算單元>是否執(zhí)行)-the

structure

of

the

design

is

dominated

by

orderly

motion

of

data

from

process

to

process

(系統(tǒng)結構：數(shù)

據(jù)在各處理之間的有序移動)-in

a

pure

data

flow

system,there

is

no

otherinteraction

between

processes

(在純數(shù)據(jù)流系統(tǒng)中，處理之間除了數(shù)據(jù)交換，沒有任何其他的交互)數(shù)據(jù)流風格的直觀理解處理：數(shù)據(jù)到達即被激活，

無

數(shù)

據(jù)

時

不

工

作數(shù)據(jù)流風格的基本構件(COMPONENT)■Components:dataprocessingcomponents(基本構件：

數(shù)據(jù)處理)-Interfaces

are

input

ports

and

output

ports(構件接口：輸入端口和

輸出端口)-Input

ports

read

data;output

ports

write

data(從輸入端口讀取數(shù)據(jù)，

向輸出端口寫入數(shù)據(jù))-Computationalmodel:readdatafrom

input

ports,compute,write

data

r

算模型：從輸入端口讀數(shù)，經(jīng)過計算/處理，然口)(計端ts出po后寫到輸to

outputData

Arrival

<<Trigger=>I

]Read.CompWriteO數(shù)據(jù)流風格的連接件(CONNECTOR)mConnectors:dataflow(data

stream)(連接件：數(shù)據(jù)流)-Uni-directional,usuallyasynchronous,buffered(單向、通常是異步、有緩沖)-Interfacesarereaderandwriterroles(接口角色：

reader和writer)-Computational

model

(計算模型：把數(shù)據(jù)從一個處理的輸出端口

傳送到另一個處理的輸入端口)<<Role>>Writerbuffering>>ReaderO<<dataRead,

Comp2Comp1WriteWriteReadOI工數(shù)據(jù)流風格的拓撲結構(TOPOLOGY)Arbitrary

graphs(任意拓撲結構的圖)Often

we

are

primarilyOrin

very

simple,highly(或在限度內(nèi)的循環(huán)數(shù)據(jù)流)In

general,data

can

flow

inArbitrary

patterns(一般來說，數(shù)據(jù)的流向是無序的)InterestedinnearlylinearDataflow

systems(我們主要關注近似線性的數(shù)據(jù)流)constrainedcyclic

structures數(shù)據(jù)到達即被激活，無數(shù)據(jù)時不工作數(shù)據(jù)流VS.控制流■在von

Neumann的計算機體系結構中，有控制流與數(shù)據(jù)流之分；控制流(Control

flow)一

數(shù)據(jù)流(Data

flow)■

討

論：二者有什么區(qū)別和聯(lián)系?能否分別舉出幾個例子?兩種典型的數(shù)據(jù)流風格■

Pipe-and-Filter(管道-過濾器)Batch

Sequential

(批

處

理)4.2管道與過濾器風格PIPE-AND-FILTER從

“自

來

水

管

道

系

統(tǒng)

”

看

Pipe-And-FilterPipes

(管道)Datasource(數(shù)據(jù)源點)Data

sink(數(shù)據(jù)終止點)Filters

(

過

濾

器

)基本定義■

語境：

數(shù)據(jù)源源不斷的產(chǎn)生，

系統(tǒng)需要對這些數(shù)據(jù)進

行若干處理(分析、計算、轉(zhuǎn)換等)?！?/p>

解決方案：一把系統(tǒng)分解為幾個序貫的處理步驟，這些步驟之間通過數(shù)據(jù)流連接，

一個步驟的輸出是另一個步驟的輸入；一

每個處理步驟由

一

個過濾器構件(Filter)實現(xiàn)；

一

處理步驟之間的數(shù)據(jù)傳輸由管道(Pipe)負責?！?/p>

理中

(輸過入濾的器數(shù))都據(jù)有流一，組經(jīng)輸過入內(nèi)和部輸處出理，，過然濾后器產(chǎn)

生輸出數(shù)據(jù)流并寫入管道中。Pipe-And-Filter風格的基本構成Components:Filters—processdatastreams(構件：過濾

器，處理數(shù)據(jù)流)-A

filter

encapsulates

a

processing

step

(algorithm

or

computation)(一

個過濾器封裝了

一

個處理步驟)-Datasource

and

data

sink

are

particularfilters(數(shù)

據(jù)

源點

和

數(shù)據(jù)

終

止

點

可以

看

作

是

特

殊

的

過

濾

器

)-Pipesmovedatafroma

filteroutputtoafilterinput(轉(zhuǎn)

發(fā)

數(shù)據(jù)

流)-Data

isa

stream

of“objects”

(數(shù)據(jù)是特定類型的“對象”mTopo流l

gy:Connectors

define

data

flow

graph(連接器定義了

數(shù)

據(jù)

流圖

，

形

成

拓

撲

結

構

)o)mConnectors:Apipeconnectsasource

and

a

sink

filter(連接件：管道，連接一個源和一個目的過濾器)1

過

濾

器(Filter)■Incrementally

transform

some

of

the

source

data

into

sinkdata(目標：將源數(shù)據(jù)變換成目標數(shù)據(jù))Streamtostreamtransformation

(

從

“

數(shù)

據(jù)流

”

“數(shù)據(jù)流”的變換)enrich

data

bycomputation

andaddinginformation(通過計算和增加信息來豐富數(shù)據(jù))-refine

by

distilling

data

or

removing

irrelevant

data(通過濃縮

和刪減來精煉數(shù)據(jù))-transform

data

by

changing

its

representation(通過改變數(shù)據(jù)表現(xiàn)方式來轉(zhuǎn)化數(shù)據(jù))-decomposedatatomultiple

streams(將一個數(shù)據(jù)流分解為多個數(shù)據(jù)流)-merge

multiple

streams

into

one

stream

(將多個數(shù)據(jù)流合并為一個數(shù)據(jù)流)data:a

data:a+b

data:a

data:a-b

增加/豐富

刪減/濃縮

data:a

data:a’過濾器對數(shù)據(jù)流的五種變換類型

data:a

data:bdata:b

合并

da

a:a+b

分解

data:a+b

data:a過濾器讀取與處理數(shù)據(jù)流的方式Incrementally

transformdatafromthesourcetothesink(遞增的讀取和消費數(shù)據(jù)流)一

在輸入被完全消費之前，輸出便產(chǎn)生了。n

3

2

1

Filtern

3

2

Filter

1'■

n

3

Filter2’

1’n

Filter3'2'

1”過濾器的一些基本特征Filtersare

independententities,i.e.,一

no

context

in

processing

streams(無上下文信息)一

no

state

preservation

between

instantiations(不保留狀態(tài))一

no

knowledge

of

upstream/downstream

filters(對其他過濾器無任何了解)一

collectionscanbe

used

to

buffer

the

data

passed

through

pipes:

files,arrays,dictionaries,trees,etc.(可使用數(shù)據(jù)緩沖區(qū)臨時保

存數(shù)據(jù)流)●蓄水池-

A

pipe

may

implement

a

buffer

(可能具有緩沖區(qū))-

Pipes

form

data

transmission

graph(管道形成傳輸

圖

)■

不同的管道中流動的數(shù)據(jù)流，具有不同的數(shù)據(jù)格式

(Dataformat)。■

原因：數(shù)據(jù)在流過每一個過濾器時，被過濾器進行了

豐富、精練、轉(zhuǎn)換、融合、分解等操作，因而發(fā)生了

變化

。2

管

道(Pipe)■

Move

data

from

a

filter's

output

to

a

filter's

input(or

to

a

device

or

file)(作用：在過濾器之間傳送數(shù)據(jù))way

flow

fromonedata

sourcetoone

data(單向流)-

One

sink

a

een

two

threads

of

a

single

process

(e.g.,Java一

Streammay

containreferencestosharedlanguageobjects(e.g.,UNIX

Named

Pipes)一stream

maycontainreferencesto

sharedOS

objects

(e.g.,msbeteeStrPip

i

t

e

o

processes

in

a

distributed

system

(e.g.,

a

i(e.g.,pass

pipesencorenacts"refebstrbytelctweea-loAhtiBgdOhtess

Centlimi,paemntseplerencimcontefeolsmrcastoreaotrSttknSocweeInPPinebetweentwoorocessesona

singlehostcomnuter管道中流動的數(shù)據(jù)類型■-

ab

t

fstAreSa

II

text

lines

with

line

separator-

br

l

tt

c

oar)d

attributes

are

strings,

separatednodes

enumerated

inpreorder,postorder,inorder)mrermoaorreasudaoyeoerewsr管道中流動的數(shù)據(jù)類型■

Tradeoffcompatibility

and

reusability

"everythingisastream"nested

record

stream

(record

attribute

is

in

turn

a

-

sequence)-typed

stream

with

a

header

containing

its

type

-

information(e.g.,

columnheadings)-v

so.tfyp

,

yPopularstreamdata

formatsxafstream

representing

a

tree

traversal(inner

nodes

/leafeventstreams(eventnameandeventarguments)"stream

of

Persons,stream管道-過濾器風格的一些變化形式數(shù)據(jù)流的分類：

推式與拉式Question:whatistheforce

thatmake

data

flow?(是什么

力量推動數(shù)據(jù)在管道中流動?)Three

choice,all

with

force

emanating

from

filters:一

Push:data

source

pushes

data

in

downstream

direction(推式：

前面的過濾器把新產(chǎn)生的數(shù)據(jù)推入管道)一

Pull:datasinkpullsdatafromupstreamdirection(拉式：

隨后的過濾器從管道中拉出所需數(shù)據(jù))—Push/pull:a

filter

is

actively

pulling

from

upstream,computing,and

pushing

downstream(

推拉式：過濾器以循環(huán)的方式，從管道中拉出其輸入數(shù)據(jù)，并將其處理產(chǎn)生的數(shù)據(jù)壓入后續(xù)管道)個

Filter

4m

Passive

filter:is

driven

by

the

data

flow

onthe(input/output)pipes.

(被動過濾器：被管道中的輸入或輸出數(shù)據(jù)流所驅(qū)動)■

Attention:系統(tǒng)中至少有一個主動過濾器(可以來自

外部環(huán)境，如用戶輸入)filter:drivers

the

data

flow

on

the(主動過濾器：驅(qū)動數(shù)據(jù)流動，

pull+push)過濾器的分類：

主動與被動while(true){Element

x

outputPipe.write]Blocking

readBlocking

writemActivepipes.=inputPipe.read

(f

【x)→→—(..);■Pull

Strategy:The

filter

is

apassive

objectthat

is

drivenbythe

subsequent

pipeline

elementthat

pulls

output

data

from

thefilter;(采用拉式策略的被動過濾器：該過濾器不會主動執(zhí)行，

而是在后續(xù)過濾器的“拉”動作的驅(qū)動下才執(zhí)行)■PushStrategy:Thefilterisapassive

objectthatis

driven

bythe

previous

pipeline

element

that

pushes

input

data

into

the

filter.(采用推式策略的被動過濾器：該過濾

器不會主動執(zhí)行，而是在前續(xù)過濾器

的“推”動作的驅(qū)動下才執(zhí)行)java.io.inputStream

in

the

Java

Class

LibraryPipedinputstreama

tri

tf

l

erlikea

passiveoneread(}I

ttu

n

-fm

p;ut.readxIrxreineavectjava.io.OutputStream

in

the

JavaClass

LibraryFileOutputstreamTreatanMyPushFilterone被動過濾器所采用的兩種策略void

vrite

(int

b){

myoutput.write(f(b))OutputStreamwrite

(b:int)FileInputStreamStringBufferInputStreamByteArrayInputstreamPipedOutputStreamByteArayOutputStreamactive

filterlihe

a

pasaiveinputstreamread)):intMyPullFilter();intpull/push:

主

動push:被

動push:被動個

filter1

filter2采

用

推

式

策略

的

被

動

過

濾

器f2(data)<-write(data)≤-dataSou

rcepushActive

Filter(數(shù)據(jù)

源作

為主動

過濾

器)push:

被

動Vdatasinkfl(data)write(data)data

sourcefilter2pushfilterl

pushdataSinkwrite(data)filterlpulldata:=readOdara:=readO采

用

拉

式

策略

的

被

動

過

濾

器taSink

pullActive

Filter(

數(shù)

據(jù)

終

止

點作為

主

動

過

濾

器

)pull/push:

主

動個data

sinkpull:

被

動4data

sourcepull:

被

動filter

2pull:

被

動filter

1data:=readO<--f2(data)<:fl(data)filter2pulldataSource一個混合型的管道-過濾器系統(tǒng)pull/push:

主

動filter

1pull:

被

動個1datasourcepull:

被

動filter2push:

被

動data

sinkdataSink

filterlpull/pushActive

Filter(中間某個過濾器

作為主動過濾器)一

個

混

合

型

的

管

道

-

過

濾

器

系

統(tǒng)data:=readO<--f2(data)<-filter2

pull<-f1(data)data:=readOdataSourcewrite(data)<-pull:被

動pull/push:主動

pull/push:

主

動push:

被

動filter2緩沖區(qū)帶有緩沖區(qū)的混合型管道-過濾器系統(tǒng)個datasourceYdata

sinkfilter

1filter2pul

pushActive

Filter(中間某個過濾器

作為主動過濾器)f2(data)≤-dataSource

filterlpull/pushdata:=read)ActiveFilter(中間某個過濾器

作為主動過濾器)帶

有

緩

沖區(qū)

的

混

合

型

管

道

-

過

濾

器

系

統(tǒng)bufferingPipe兩個過濾器之間

(管道)的緩沖區(qū)write)1.filter

1

pulls

datafromsource2.filter2starts

toread

butsuspends3.fiter

1

pushesresult

to

pipe4.filter2continues

sincedata

inpipe5.filter2sendsresultto

datasink6.filter1suspends

sincefilter2

notwaiting7filter2

reads

data,releases

filter

1長

-

-

-≤--fl(data)K-data:=read)>data:=read()dataSinkwrite()write()過濾器的狀態(tài)■

停止狀態(tài)：表示過濾器處于待啟動狀態(tài)，

當外部啟動過濾

器后，過濾器處于處理狀態(tài)?！?/p>

處理狀態(tài)：表示過濾器正處理輸入數(shù)據(jù)隊列中的數(shù)據(jù)?！?/p>

等待狀態(tài)：表示過濾器的輸入數(shù)據(jù)隊列為空，此時過濾

器等待，

當有新的數(shù)據(jù)輸入時，過濾器處于處理狀態(tài)。Pipe-And-Filter

風格的典型應用Pipe-And-Filter

風格的典型應用■

Complier(scan,parse,generatecode,…)(編譯器)■

Unixpipes(Unix管道)Image

processing(圖像處理)Signal

processing(信號處理)■Voiceandvideostreaming(聲音與圖像處理)■

·管

道

-

過

濾

器

風

格的

例子g(f(x))hf(x)四h(g(f(x)))k(g(f(x)))XfK管道-過濾器風格的例子：

Unix

ShellUnix中的“管道與過濾器”catinput.txtlgrep

"text"l

sort>output.txtgrep

sortinput.txt1s

grep

-e

exp

sortlprData

Flowas

ASCI

StreamComputationFilteroutput.txt管道-過濾器風格的例子：

Unix

ShellTask:Printasorted

listofwordsthatoccurmorethan

once管道-過濾器風格的例子：編譯器(1)十

十

十ErrorMessageDecoratedA

ctN

x

A

c

axstendyNot

SreestraTbdesyntaoSeaerrtTbsBytecode

Optimizer字節(jié)碼優(yōu)化ψMachine

CodeStream。sCeh

i語法分析rcetcaBytecode

Senerator字節(jié)碼生成UnicodeCharacterStreamMachineCodeGeneratorScanner掃描Bytecode

StreamParser詞法分析Token

Stream機器碼生成StreamMov

ax,[BP]mov

dx,[BP-2]

{Oiload_o

1

iload_

12if_icmpge

7

5

iload_o6iretum7

iload_

1

&iretun

ti"

etypead432

incomp340

expecte管道-過濾器風格的例子：編譯器(2)cl

lMicat

t

tic

int

min

(int

a,int

b){public·static·int…return

a]//min}//class

MathSc

.<b?a:b

;十十·class·MathBC

GenParSC十管道-過濾器風格的優(yōu)點■

使得系統(tǒng)中的構件具有良好的隱蔽性和高內(nèi)聚、低耦

合

的

特

點

；■

允許設計者將整個系統(tǒng)的輸入/輸出行為看成是多個過濾器的行為的簡單合成；■

支持軟件復用：一

器之間傳送的數(shù)據(jù)，任何兩個■

系統(tǒng)維護和增強系統(tǒng)性能簡單：一新的過濾器可以添加到現(xiàn)有系統(tǒng)中來，舊的可以被改進的過濾器替換掉；■允許對一些如吞吐量、死鎖等屬性的分析；■

支持并行執(zhí)行：一每個過濾器是作為一個單獨的任務完成，因此可與其它接

起

來兩個過都

可

被供適合器提濾要過只任務并行執(zhí)行。管道-過濾器風格的缺點■通常導致進程成為批處理的結構一這是因為雖然過濾器可增量式地處理數(shù)據(jù)，但它們是獨

立的，所以設計者必須將每個過濾器看成一個完整的從輸入到輸出的轉(zhuǎn)換；■不適合處理交互的應用一

當需要增量地顯示改變時，這個問題尤為嚴重；■因為在數(shù)據(jù)傳輸上沒有通用的標準，每個過濾器都增

加了解析和合成數(shù)據(jù)的工作，這樣就導致了系統(tǒng)性能

下降，

并

增

加了

編

寫

過

濾

器

的

復

雜

性

。一絕大部分處理時間消耗在格式轉(zhuǎn)換上4.3順序批處理風格

Batch

Sequential

Style批

處

理

風

格的

直

觀

結

構(a)(b)

(c)(d)(e)(f)將

磁帶

作

為

計

算

設

備的

輸

入

，

進行

計

算，

得

到

輸出

結

果將

用

戶

輸

入的

紙帶

上的

數(shù)

據(jù)

寫

入

磁帶打印

計

算結

果Output

tapeInput

tapeSystemtape批處理風格的直觀結構tapeUpdatetaptapeValidatetapeSortreportReportData

TransformationData

Flowtape基本定義■Processingsteps

are

independentprograms(每個處理步驟是一個獨立的程序)■

Each

stepruns

tocompletionbeforenextstep

starts(每

一

步必須在前一步結束后才能開始)■Datatransmitted

as

a

whole

between

steps(數(shù)據(jù)必須是完

整

的

,

以整體的方式傳遞)■Typical

applications(典型應用):dataprocessing(傳統(tǒng)的數(shù)據(jù)處理)

compilation/computeraidedsoftware譯

/CASE

工

具

)-classical

program

(程序編engineering基本構成■

Components

(processing

steps)are

independentprograms(基本

構件：獨立的應用程序)Connectors

are

some

type

of

media

-traditionally

magnetictape(連接件：某種類型的媒質(zhì))■Topology:Connectors

define

data

flow

gr