數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格

軟件體系結(jié)構(gòu)及應(yīng)用

4數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格主要內(nèi)容■4.1

數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格的基本特征

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

4.3

批處理(batch

sequential)■4.4批處理與管道-過濾器的比較4.1數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格

的基本特征mA

dataflow

system

is

one

in

which-

theavailabilityofdatacontrolstheomputation(

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

structure

of

the

design

is

dominated

by

orderly

motion

of

data

from

process

to

process

(系統(tǒng)結(jié)構(gòu)：數(shù)

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

a

pure

data

flow

system,there

is

no

otherinteraction

between

processes

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

無

數(shù)

據(jù)

時(shí)

不

工

作數(shù)據(jù)流風(fēng)格的基本構(gòu)件(COMPONENT)■Components:dataprocessingcomponents(基本構(gòu)件：

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

are

input

ports

and

output

ports(構(gòu)件接口：輸入端口和

輸出端口)-Input

ports

read

data;output

ports

write

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

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

input

ports,compute,write

data

r

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

outputData

Arrival

<<Trigger=>I

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

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

reader和writer)-Computational

model

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

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

Comp2Comp1WriteWriteReadOI工數(shù)據(jù)流風(fēng)格的拓?fù)浣Y(jié)構(gòu)(TOPOLOGY)Arbitrary

graphs(任意拓?fù)浣Y(jié)構(gòu)的圖)Often

we

are

primarilyOrin

very

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

general,data

can

flow

inArbitrary

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

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

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

Neumann的計(jì)算機(jī)體系結(jié)構(gòu)中，有控制流與數(shù)據(jù)流之分；控制流(Control

flow)一

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

flow)■

討

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

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

Sequential

(批

處

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

“自

來

水

管

道

系

統(tǒng)

”

看

Pipe-And-FilterPipes

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

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

(

過

濾

器

)基本定義■

語境：

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

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

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

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

一個(gè)步驟的輸出是另一個(gè)步驟的輸入；一

每個(gè)處理步驟由

一

個(gè)過濾器構(gòu)件(Filter)實(shí)現(xiàn)；

一

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

理中

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

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

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

filter

encapsulates

a

processing

step

(algorithm

or

computation)(一

個(gè)過濾器封裝了

一

個(gè)處理步驟)-Datasource

and

data

sink

are

particularfilters(數(shù)

據(jù)

源點(diǎn)

和

數(shù)據(jù)

終

止

點(diǎn)

可以

看

作

是

特

殊

的

過

濾

器

)-Pipesmovedatafroma

filteroutputtoafilterinput(轉(zhuǎn)

發(fā)

數(shù)據(jù)

流)-Data

isa

stream

of“objects”

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

gy:Connectors

define

data

flow

graph(連接器定義了

數(shù)

據(jù)

流圖

，

形

成

拓

撲

結(jié)

構(gòu)

)o)mConnectors:Apipeconnectsasource

and

a

sink

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

過

濾

器(Filter)■Incrementally

transform

some

of

the

source

data

into

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

(

從

“

數(shù)

據(jù)流

”

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

data

bycomputation

andaddinginformation(通過計(jì)算和增加信息來豐富數(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(將一個(gè)數(shù)據(jù)流分解為多個(gè)數(shù)據(jù)流)-merge

multiple

streams

into

one

stream

(將多個(gè)數(shù)據(jù)流合并為一個(gè)數(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(遞增的讀取和消費(fèi)數(shù)據(jù)流)一

在輸入被完全消費(fèi)之前，輸出便產(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í)保

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

A

pipe

may

implement

a

buffer

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

Pipes

form

data

transmission

graph(管道形成傳輸

圖

)■

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

(Dataformat)?！?/p>

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

豐富、精練、轉(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管道-過濾器風(fēng)格的一些變化形式數(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ù)管道)個(gè)

Filter

4m

Passive

filter:is

driven

by

the

data

flow

onthe(input/output)pipes.

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

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

外部環(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:被動個(gè)

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ù)

終

止

點(diǎn)作為

主

動

過

濾

器

)pull/push:

主

動個(gè)data

sinkpull:

被

動4data

sourcepull:

被

動filter

2pull:

被

動filter

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

主

動filter

1pull:

被

動個(gè)1datasourcepull:

被

動filter2push:

被

動data

sinkdataSink

filterlpull/pushActive

Filter(中間某個(gè)過濾器

作為主動過濾器)一

個(gè)

混

合

型

的

管

道

-

過

濾

器

系

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

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

動pull/push:主動

pull/push:

主

動push:

被

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

sinkfilter

1filter2pul

pushActive

Filter(中間某個(gè)過濾器

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

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

作為主動過濾器)帶

有

緩

沖區(qū)

的

混

合

型

管

道

-

過

濾

器

系

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

(管道)的緩沖區(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)■

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

當(dāng)外部啟動過濾

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

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

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

器等待，

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

風(fēng)格的典型應(yīng)用Pipe-And-Filter

風(fēng)格的典型應(yīng)用■

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

Unixpipes(Unix管道)Image

processing(圖像處理)Signal

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

·管

道

-

過

濾

器

風(fēng)

格的

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

Unix

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

"text"l

sort>output.txtgrep

sortinput.txt1s

grep

-e

exp

sortlprData

Flowas

ASCI

StreamComputationFilteroutput.txt管道-過濾器風(fēng)格的例子：

Unix

ShellTask:Printasorted

listofwordsthatoccurmorethan

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

十

十ErrorMessageDecoratedA

ctN

x

A

c

axstendyNot

SreestraTbdesyntaoSeaerrtTbsBytecode

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

CodeStream。sCeh

i語法分析rcetcaBytecode

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

StreamParser詞法分析Token

Stream機(jī)器碼生成StreamMov

ax,[BP]mov

dx,[BP-2]

{Oiload_o

1

iload_

12if_icmpge

7

5

iload_o6iretum7

iload_

1

&iretun

ti"

etypead432

incomp340

expecte管道-過濾器風(fēng)格的例子：編譯器(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十管道-過濾器風(fēng)格的優(yōu)點(diǎn)■

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

合

的

特

點(diǎn)

；■

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

支持軟件復(fù)用：一

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

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

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

起

來兩個(gè)過都

可

被供適合器提濾要過只任務(wù)并行執(zhí)行。管道-過濾器風(fēng)格的缺點(diǎn)■通常導(dǎo)致進(jìn)程成為批處理的結(jié)構(gòu)一這是因?yàn)殡m然過濾器可增量式地處理數(shù)據(jù)，但它們是獨(dú)

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

當(dāng)需要增量地顯示改變時(shí)，這個(gè)問題尤為嚴(yán)重；■因?yàn)樵跀?shù)據(jù)傳輸上沒有通用的標(biāo)準(zhǔn)，每個(gè)過濾器都增

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

下降，

并

增

加了

編

寫

過

濾

器

的

復(fù)

雜

性

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

Batch

Sequential

Style批

處

理

風(fēng)

格的

直

觀

結(jié)

構(gòu)(a)(b)

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

磁帶

作

為

計(jì)

算

設(shè)

備的

輸

入

，

進(jìn)行

計(jì)

算，

得

到

輸出

結(jié)

果將

用

戶

輸

入的

紙帶

上的

數(shù)

據(jù)

寫

入

磁帶打印

計(jì)

算結(jié)

果Output

tapeInput

tapeSystemtape批處理風(fēng)格的直觀結(jié)構(gòu)tapeUpdatetaptapeValidatetapeSortreportReportData

TransformationData

Flowtape基本定義■Processingsteps

are

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

Each

stepruns

tocompletionbeforenextstep

starts(每

一

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

as

a

whole

between

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

整

的

,

以整體的方式傳遞)■Typical

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

compilation/computeraidedsoftware譯

/CASE

工

具

)-classical

program

(程序編engineering基本構(gòu)成■

Components

(processing

steps)are

independentprograms(基本

構(gòu)件：獨(dú)立的應(yīng)用程序)Connectors

are

some

type

of

media

-traditionally

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

define

data

flow

gr