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

1、軟件體系結構及應用軟件體系結構及應用4 4 數(shù)據(jù)流體系結構風格數(shù)據(jù)流體系結構風格主要內容n4.1 數(shù)據(jù)流體系結構風格的基本特征n4.2 管道-過濾器(pipe-and-filter)n4.3 批處理(batch sequential)n4.4 批處理與管道-過濾器的比較4.1 數(shù)據(jù)流體系結構風格的基本特征數(shù)據(jù)流風格的直觀理解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)結構：數(shù)據(jù)在各處理之間的有序移動) in a pure data flow system, there is no other interaction between processes (在純數(shù)據(jù)流系統(tǒng)中，處理之間除了數(shù)據(jù)交換，沒有任何其他的交互)數(shù)據(jù)流風格的基本構件(COMPONENT)nComponents: data processing components(基本構件：數(shù)據(jù)處理) Interfaces are input ports and output ports

3、 ( Interfaces are input ports and output ports (構件接口：輸入端口和構件接口：輸入端口和輸出端口輸出端口) ) 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 (計算模型：從輸入端口讀數(shù)，經(jīng)過計算計算模型：從輸入端口讀數(shù)，經(jīng)過計算/ /處理，處理，然后寫到輸出端口然后寫到輸出端口) )數(shù)據(jù)流風格的連接件(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 (計算模型計算模型: : 把數(shù)據(jù)從一個處理的輸出端口把數(shù)據(jù)從一個處理的輸出端口傳送到另一個處理的輸入端口傳送到另一個處理的輸入端口)數(shù)據(jù)流風格的拓撲結構(TOPOLOGY)數(shù)據(jù)流VS. 控制流n在von Neumann的計算機體系結構中，有控制流與數(shù)據(jù)流之分； 控制流(Control flow) 數(shù)據(jù)流(Data flow)n討論：二者有什么區(qū)別和聯(lián)系？能否分別舉出幾個例子？二者有什么區(qū)別和聯(lián)系？能否分別舉出幾

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

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

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

9、數(shù)據(jù))nStream to stream transformation (從“數(shù)據(jù)流”“數(shù)據(jù)流”的變換) enrich data by computation and adding information (通過計算和增加信息來豐富數(shù)據(jù)) refine by distilling data or removing irrelevant data (通過濃縮和刪減來精煉數(shù)據(jù)) transform data by changing its representation (通過改變數(shù)據(jù)表現(xiàn)方式來轉化數(shù)據(jù)) decompose data to multiple streams (將一個數(shù)據(jù)流分解為多個

10、數(shù)據(jù)流) merge multiple streams into one stream (將多個數(shù)據(jù)流合并為一個數(shù)據(jù)流)過濾器對數(shù)據(jù)流的五種變換類型過濾器讀取與處理數(shù)據(jù)流的方式nIncrementally transform data from the source to the sink (遞增的讀取和消費數(shù)據(jù)流) 在輸入被完全消費之前，輸出便產(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 (對其他過濾器無任何了解) collections can be used to buffer the data passed through pipes: files,arrays, dictionaries, trees, etc. (可使用數(shù)據(jù)緩沖區(qū)臨時保存數(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不同的管道中流動的數(shù)據(jù)流，具有不同的

13、數(shù)據(jù)格式不同的管道中流動的數(shù)據(jù)流，具有不同的數(shù)據(jù)格式(Data (Data format)format)。n原因：數(shù)據(jù)在流過每一個過濾器時，被過濾器進行了原因：數(shù)據(jù)在流過每一個過濾器時，被過濾器進行了豐富、豐富、精練、轉換、融合、分解精練、轉換、融合、分解等操作，因而發(fā)生了變化。等操作，因而發(fā)生了變化。管道中流動的數(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)管道中流動的數(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)管道-過濾器風格的一些變化形式數(shù)據(jù)流的分類：推式與拉式nQuestion: what is the force that make data flow? (是什么力量推動數(shù)據(jù)在管道中流動？)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ù)管道)過濾器的分類：主動與被動nActive filter: drivers the data flow on the pipes. (主動過濾器：驅動數(shù)據(jù)流動, pull+push)nPassi

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

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

21、濾器的狀態(tài)n停止狀態(tài):表示過濾器處于待啟動狀態(tài)，當外部啟動過濾器后，過濾器處于處理狀態(tài)。n處理狀態(tài)：表示過濾器正處理輸入數(shù)據(jù)隊列中的數(shù)據(jù)。n等待狀態(tài)：表示過濾器的輸入數(shù)據(jù)隊列為空，此時過濾器等待，當有新的數(shù)據(jù)輸入時，過濾器處于處理狀態(tài)。PIPE-AND-FILTER風格的典型應用PIPE-AND-FILTER風格的典型應用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 (信號處理信號處理) )nVoice and video streaming (Voice and video streaming (聲音與圖像處理聲音與圖像處理) )n管道-過濾器風格的例子管道-過濾器風格的例子：UNIX SHELL管道-過濾器風格的例子： UNIX SHELL管道-過濾器風格的例子：編譯器(1)管道-過濾器風格的例子：編譯器(2)管道-過濾器風格的優(yōu)點n使得系統(tǒng)中的構件具有良好的使得系統(tǒng)中的構件具有良好的隱蔽性

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

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

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

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