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

1、軟件體系結(jié)構(gòu)及應(yīng)用軟件體系結(jié)構(gòu)及應(yīng)用4 4 數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格主要內(nèi)容n4.1 數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格的基本特征n4.2 管道-過濾器(pipe-and-filter)n4.3 批處理(batch sequential)n4.4 批處理與管道-過濾器的比較4.1 數(shù)據(jù)流體系結(jié)構(gòu)風(fēng)格的基本特征數(shù)據(jù)流風(fēng)格的直觀理解nA data flow system is one in which the availability of data controls the omputation (數(shù)據(jù)的可用性決定著處理是否執(zhí)行) the structure of the design is dom

2、inated by orderly motion of data from process to process (系統(tǒng)結(jié)構(gòu)：數(shù)據(jù)在各處理之間的有序移動(dòng)) in a pure data flow system, there is no other interaction between processes (在純數(shù)據(jù)流系統(tǒng)中，處理之間除了數(shù)據(jù)交換，沒有任何其他的交互)數(shù)據(jù)流風(fēng)格的基本構(gòu)件(COMPONENT)nComponents: data processing components(基本構(gòu)件：數(shù)據(jù)處理) Interfaces are input ports and output ports

3、 ( Interfaces are input ports and output ports (構(gòu)件接口：輸入端口和構(gòu)件接口：輸入端口和輸出端口輸出端口) ) Input ports read data; output ports write data ( Input ports read data; output ports write data (從輸入端口讀取數(shù)據(jù)，從輸入端口讀取數(shù)據(jù)，向輸出端口寫入數(shù)據(jù)向輸出端口寫入數(shù)據(jù)) ) Computational model: read data from input ports, compute, write data Computationa

4、l model: read data from input ports, compute, write data to output ports (to output ports (計(jì)算模型：從輸入端口讀數(shù)，經(jīng)過計(jì)算計(jì)算模型：從輸入端口讀數(shù)，經(jīng)過計(jì)算/ /處理，處理，然后寫到輸出端口然后寫到輸出端口) )數(shù)據(jù)流風(fēng)格的連接件(CONNECTOR)nConnectors: data flow (data stream) (連接件：數(shù)據(jù)流) Uni-directional, usually asynchronous, buffered (單向、通常是異步、單向、通常是異步、有緩沖有緩沖) Inter

5、faces are reader and writer roles (接口角色：接口角色：readerreader和和writerwriter) Computational model (計(jì)算模型計(jì)算模型: : 把數(shù)據(jù)從一個(gè)處理的輸出端口把數(shù)據(jù)從一個(gè)處理的輸出端口傳送到另一個(gè)處理的輸入端口傳送到另一個(gè)處理的輸入端口)數(shù)據(jù)流風(fēng)格的拓?fù)浣Y(jié)構(gòu)(TOPOLOGY)數(shù)據(jù)流VS. 控制流n在von Neumann的計(jì)算機(jī)體系結(jié)構(gòu)中，有控制流與數(shù)據(jù)流之分； 控制流(Control flow) 數(shù)據(jù)流(Data flow)n討論：二者有什么區(qū)別和聯(lián)系？能否分別舉出幾個(gè)例子？二者有什么區(qū)別和聯(lián)系？能否分別舉出幾

6、個(gè)例子？兩種典型的數(shù)據(jù)流風(fēng)格nPipe-and-Filter (管道-過濾器)nBatch Sequential (批處理)4.2 管道與過濾器風(fēng)格PIPE-AND-FILTER從“自來水管道系統(tǒng)”看PIPE-AND-FILTER基本定義n語境：數(shù)據(jù)源源不斷的產(chǎn)生，系統(tǒng)需要對(duì)這些數(shù)據(jù)進(jìn)行若干處理(分析、計(jì)算、轉(zhuǎn)換等)。n解決方案： 把系統(tǒng)分解為幾個(gè)序貫的處理步驟，這些步驟之間通過數(shù)據(jù)流連接，一個(gè)步驟的輸出是另一個(gè)步驟的輸入； 每個(gè)處理步驟由一個(gè)過濾器構(gòu)件(Filter)實(shí)現(xiàn)； 處理步驟之間的數(shù)據(jù)傳輸由管道(Pipe)負(fù)責(zé)。n每個(gè)處理步驟(過濾器)都有一組輸入和輸出，過濾器從管道中讀取輸入的數(shù)據(jù)

7、流，經(jīng)過內(nèi)部處理，然后產(chǎn)生輸出數(shù)據(jù)流并寫入管道中。PIPE-AND-FILTER風(fēng)格的基本構(gòu)成nComponents: Filters process data streams (構(gòu)件：過濾器，處理數(shù)據(jù)流) A filter encapsulates a processing step (algorithm or computation) (一個(gè)過濾器封裝了一個(gè)處理步驟) Data source and data sink are particular filters (數(shù)據(jù)源點(diǎn)和數(shù)據(jù)終止點(diǎn)可以看作是特殊的過濾器)nConnectors: A pipe connects a source an

8、d a sink filter (連接件：管道，連接一個(gè)源和一個(gè)目的過濾器) Pipes move data from a filter output to a filter input (轉(zhuǎn)發(fā)數(shù)據(jù)流) Data is a stream of “objects” (數(shù)據(jù)是特定類型的“對(duì)象”流)nTopology: Connectors define data flow graph (連接器定義了數(shù)據(jù)流圖，形成拓?fù)浣Y(jié)構(gòu))1 過濾器(FILTER)nIncrementally transform some of the source data into sink data(目標(biāo)：將源數(shù)據(jù)變換成目標(biāo)

9、數(shù)據(jù))nStream to stream transformation (從“數(shù)據(jù)流”“數(shù)據(jù)流”的變換) enrich data by computation and adding information (通過計(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ù)) decompose data to multiple streams (將一個(gè)數(shù)據(jù)流分解為多個(gè)

10、數(shù)據(jù)流) merge multiple streams into one stream (將多個(gè)數(shù)據(jù)流合并為一個(gè)數(shù)據(jù)流)過濾器對(duì)數(shù)據(jù)流的五種變換類型過濾器讀取與處理數(shù)據(jù)流的方式nIncrementally transform data from the source to the sink (遞增的讀取和消費(fèi)數(shù)據(jù)流) 在輸入被完全消費(fèi)之前，輸出便產(chǎn)生了。過濾器的一些基本特征nFilters are independent entities, i.e.,Filters are independent entities, i.e., no context in processing streams

11、 (無上下文信息) no state preservation between instantiations (不保留狀態(tài)) no knowledge of upstream/downstream filters (對(duì)其他過濾器無任何了解) collections can be used to buffer the data passed through pipes: files,arrays, dictionaries, trees, etc. (可使用數(shù)據(jù)緩沖區(qū)臨時(shí)保存數(shù)據(jù)流) 蓄水池2 管道(PIPE)nMove data from a filters output to a filte

12、rs input (or to a Move data from a filters output to a filters input (or to a device or file)(device or file)(作用：在過濾器之間傳送數(shù)據(jù)作用：在過濾器之間傳送數(shù)據(jù)) ) One way flow from one data source to one data sink (單向流) A pipe may implement a buffer (可能具有緩沖區(qū)) Pipes form data transmission graph (管道形成傳輸圖)n不同的管道中流動(dòng)的數(shù)據(jù)流，具有不同的

13、數(shù)據(jù)格式不同的管道中流動(dòng)的數(shù)據(jù)流，具有不同的數(shù)據(jù)格式(Data (Data format)format)。n原因：數(shù)據(jù)在流過每一個(gè)過濾器時(shí)，被過濾器進(jìn)行了原因：數(shù)據(jù)在流過每一個(gè)過濾器時(shí)，被過濾器進(jìn)行了豐富、豐富、精練、轉(zhuǎn)換、融合、分解精練、轉(zhuǎn)換、融合、分解等操作，因而發(fā)生了變化。等操作，因而發(fā)生了變化。管道中流動(dòng)的數(shù)據(jù)類型nPipe between two threads of a single process (e.g., Java Streams) Stream may contain references to shared language objectsnPipe between t

14、wo processes on a single host computer (e.g., UNIX Named Pipes) stream may contain references to shared OS objects (e.g., files)nPipe between two processes in a distributed system (e.g., Internet Sockets) Stream contents limited to raw bytes Protocols implement high-level abstractions (e.g., pass pi

15、pes as reference, pass COBA object references)管道中流動(dòng)的數(shù)據(jù)類型nTradeoffTradeoff compatibility and reusability everything is a stream vs. type safety stream of Persons, stream of TextsnPopular stream data formatsPopular stream data formats raw byte stream stream of ASCII text lines with line separator reco

16、rd stream (record attributes are strings, separated by tabulator or comma) nested record stream (record attribute is in turn a sequence) stream representing a tree traversal (inner nodes / leaf nodes enumerated in preorder, postorder, inorder) typed stream with a header containing its type informati

17、on (e.g., column headings) event streams (event name and event arguments)管道-過濾器風(fēng)格的一些變化形式數(shù)據(jù)流的分類：推式與拉式nQuestion: what is the force that make data flow? (是什么力量推動(dòng)數(shù)據(jù)在管道中流動(dòng)？)nThree choice, all with force emanating from filters: Push: data source pushes data in downstream direction (推式：前面的過濾器把新產(chǎn)生的數(shù)據(jù)推入管道) P

18、ull: data sink pulls data from upstream direction (拉式：隨后的過濾器從管道中拉出所需數(shù)據(jù)) Push/pull: a filter is actively pulling from upstream, computing, and pushing downstream (推拉式：過濾器以循環(huán)的方式，從管道中拉出其輸入數(shù)據(jù)，并將其處理產(chǎn)生的數(shù)據(jù)壓入后續(xù)管道)過濾器的分類：主動(dòng)與被動(dòng)nActive filter: drivers the data flow on the pipes. (主動(dòng)過濾器：驅(qū)動(dòng)數(shù)據(jù)流動(dòng), pull+push)nPassi

19、ve filter: is driven by the data flow on the (input/output)pipes. (被動(dòng)過濾器：被管道中的輸入或輸出數(shù)據(jù)流所驅(qū)動(dòng))nAttention:系統(tǒng)中至少有一個(gè)主動(dòng)過濾器(可以來自外部環(huán)境，如用戶輸入)被動(dòng)過濾器所采用的兩種策略nPull Strategy: The filter is a passive object that is driven by the subsequent pipeline element that pulls output data from the filter; (采用拉式策略的被動(dòng)過濾器： 該過濾器不

20、會(huì)主動(dòng)執(zhí)行，而是在后續(xù) 過濾器的“拉”動(dòng)作的驅(qū)動(dòng)下才執(zhí)行)nPush Strategy: The filter is a passive object that is driven by the previous pipeline element that pushes input data into the filter. (采用推式策略的被動(dòng)過濾器：該過濾 器不會(huì)主動(dòng)執(zhí)行，而是在前續(xù)過濾器 的“推”動(dòng)作的驅(qū)動(dòng)下才執(zhí)行)采用推式策略的被動(dòng)過濾器采用拉式策略的被動(dòng)過濾器一個(gè)混合型的管道-過濾器系統(tǒng)一個(gè)混合型的管道-過濾器系統(tǒng)帶有緩沖區(qū)的混合型管道-過濾器系統(tǒng)帶有緩沖區(qū)的混合型管道-過濾器系統(tǒng)過

21、濾器的狀態(tài)n停止?fàn)顟B(tài):表示過濾器處于待啟動(dòng)狀態(tài)，當(dāng)外部啟動(dòng)過濾器后，過濾器處于處理狀態(tài)。n處理狀態(tài)：表示過濾器正處理輸入數(shù)據(jù)隊(duì)列中的數(shù)據(jù)。n等待狀態(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)用nComplier (scan, parse, generate code, .) (Complier (scan, parse, generate code, .) (編譯器編譯器) )nUnix pipes (Unix pipes (UnixUnix管道管道) )nIma

22、ge processing (Image processing (圖像處理圖像處理) )nSignal processing (Signal processing (信號(hào)處理信號(hào)處理) )nVoice and video streaming (Voice and video streaming (聲音與圖像處理聲音與圖像處理) )n管道-過濾器風(fēng)格的例子管道-過濾器風(fēng)格的例子：UNIX SHELL管道-過濾器風(fēng)格的例子： UNIX SHELL管道-過濾器風(fēng)格的例子：編譯器(1)管道-過濾器風(fēng)格的例子：編譯器(2)管道-過濾器風(fēng)格的優(yōu)點(diǎn)n使得系統(tǒng)中的構(gòu)件具有良好的使得系統(tǒng)中的構(gòu)件具有良好的隱蔽性

23、和高內(nèi)聚、低耦合隱蔽性和高內(nèi)聚、低耦合的特點(diǎn)；的特點(diǎn)；n允許設(shè)計(jì)者將整個(gè)系統(tǒng)的輸入允許設(shè)計(jì)者將整個(gè)系統(tǒng)的輸入/ /輸出行為看成是多個(gè)過濾輸出行為看成是多個(gè)過濾器的行為的器的行為的簡單合成簡單合成；n支持軟件復(fù)用支持軟件復(fù)用： 只要提供適合在兩個(gè)過濾器之間傳送的數(shù)據(jù)，任何兩個(gè)過濾只要提供適合在兩個(gè)過濾器之間傳送的數(shù)據(jù)，任何兩個(gè)過濾器都可被連接起來；器都可被連接起來；n系統(tǒng)維護(hù)和增強(qiáng)系統(tǒng)性能簡單系統(tǒng)維護(hù)和增強(qiáng)系統(tǒng)性能簡單： 新的過濾器可以添加到現(xiàn)有系統(tǒng)中來，舊的可以被改進(jìn)的過新的過濾器可以添加到現(xiàn)有系統(tǒng)中來，舊的可以被改進(jìn)的過濾器替換掉；濾器替換掉；n允許對(duì)一些如吞吐量、死鎖等屬性的分析允許對(duì)一些

24、如吞吐量、死鎖等屬性的分析；n支持并行執(zhí)行支持并行執(zhí)行： 每個(gè)過濾器是作為一個(gè)單獨(dú)的任務(wù)完成，因此可與其它任務(wù)每個(gè)過濾器是作為一個(gè)單獨(dú)的任務(wù)完成，因此可與其它任務(wù)并行執(zhí)行。并行執(zhí)行。管道-過濾器風(fēng)格的缺點(diǎn)n通常導(dǎo)致進(jìn)程成為批處理的結(jié)構(gòu) 這是因?yàn)殡m然過濾器可增量式地處理數(shù)據(jù)，但它們是獨(dú)立的，所以設(shè)計(jì)者必須將每個(gè)過濾器看成一個(gè)完整的從輸入到輸出的轉(zhuǎn)換；n不適合處理交互的應(yīng)用 當(dāng)需要增量地顯示改變時(shí)，這個(gè)問題尤為嚴(yán)重；n因?yàn)樵跀?shù)據(jù)傳輸上沒有通用的標(biāo)準(zhǔn)，每個(gè)過濾器都增加了解析和合成數(shù)據(jù)的工作，這樣就導(dǎo)致了系統(tǒng)性能下降，并增加了編寫過濾器的復(fù)雜性。 絕大部分處理時(shí)間消耗在格式轉(zhuǎn)換上4.3 順序批處理風(fēng)格

25、BATCH SEQUENTIAL STYLE批處理風(fēng)格的直觀結(jié)構(gòu)將用戶輸入的紙帶上的數(shù)據(jù)寫入磁帶將磁帶作為計(jì)算設(shè)備的輸入，進(jìn)行計(jì)算，得到輸出結(jié)果打印計(jì)算結(jié)果批處理風(fēng)格的直觀結(jié)構(gòu)基本定義nProcessing steps are independent programs(每個(gè)處理步驟是一個(gè)獨(dú)立的程序)nEach step runs to completion before next step starts(每一步必須在前一步結(jié)束后才能開始)nData transmitted as a whole between steps(數(shù)據(jù)必須是完整的，以整體的方式傳遞)nTypical applicati

26、ons(典型應(yīng)用): classical data processing (傳統(tǒng)的數(shù)據(jù)處理) program compilation/computer aided software engineering (程序編譯/CASE工具)基本構(gòu)成nComponents (processing steps) are independent programs(基本構(gòu)件：獨(dú)立的應(yīng)用程序)nConnectors are some type of media - traditionally magnetic tape(連接件：某種類型的媒質(zhì))nTopology: Connectors define data flow graph (連接件定義了相應(yīng)的數(shù)據(jù)流圖，表達(dá)拓?fù)浣Y(jié)構(gòu))nEach step runs to completion before the next step begins (每一步驟必須在前一步驟完全結(jié)束之后方能開始)示例：批處理風(fēng)格的系統(tǒng)數(shù)據(jù)流圖（Da