SA02.3Style黑板虛擬機獨立組.ppt

1,SE3121021: Software Architecture Software Architecture Style,Blackboard,2,，如同多位不同專長的專家在同一黑板上交流思想，每個專家都可以獲得別的專家寫在黑板上的信息，同時也可以用自己的分析去更新黑板上的信息，從而影響其它專家。,Blackboard,解決無確定性求解策略問題。 語境：一個不成熟的領(lǐng)域，其中沒有相近的或可行的方法 問題：針對那些需要把原始數(shù)據(jù)轉(zhuǎn)換成高層數(shù)據(jù)結(jié)構(gòu)，但沒有可行的確定性解的場合。 在合理的時間內(nèi)，解空間的完全求解不可行。 由于領(lǐng)域不成熟，模塊應(yīng)易于替換以便試驗。 對子問題的求解可以有多種算法。 解決方案： 設(shè)計公共數(shù)據(jù)結(jié)構(gòu)。 設(shè)計多個專用組件，每個組件解決任務(wù)的一個特定部分。 每個組件可對公共數(shù)據(jù)結(jié)構(gòu)進行添加、修改、刪除 仲裁者組件對每個組件的工作結(jié)果進行評估，以次為依據(jù)協(xié)調(diào)各組件的工作。 多個專家，以多個步驟解決問題,4,Blackboard的組成,（1）知識源：包含獨立的、與應(yīng)用程序相關(guān)的知識，知識源之間不直接進行通訊，它們之間的交互只通過黑板來完成。一個知識源只能解決問題的一部分 （2）黑板數(shù)據(jù)結(jié)構(gòu)：按照與應(yīng)用程序相關(guān)的層次來組織的解決問題的數(shù)據(jù)，知識源利用黑板的接口對黑板進行讀寫，通過不斷地改變黑板數(shù)據(jù)來解決問題。 （3）控制（仲裁者）：控制完全由黑板的狀態(tài)驅(qū)動，監(jiān)視黑板的變化，決定下一步使用哪個知識源進行工作,5,6,Knowledge Sources,Objective: contribute knowledge that leads to solution 提供解決問題的知識 Representation: procedures, sets of rules, logic assertions 過程、規(guī)則、邏輯斷言 Action: modify only the blackboard (or control data - magic) 只修改黑板 Responsibility: know when its possible to help 知道何時能發(fā)揮作用 Selection: loosely-coupled subtasks, or areas of specialization 低耦合的子任務(wù)，或者有特別的能力,7,Blackboard Data Structure,Objective: hold data for use by knowledge sources 保存知識源要使用的數(shù)據(jù) Representation: stores objects from solution space, including 保存來自解空間的數(shù)據(jù)，包括 input data, partial solutions, alternatives, final solutions, control data objects and properties define the terms of the discourse relationships are denoted by named links (“next-to”, “part-of”) Organization: hierarchical, possibly multiple hierarchies; links between objects on same or different levels 分層；鏈接同層或不同層的對象 與倉庫的區(qū)別 黑板：黑板的狀態(tài)觸發(fā)進一步的操作 倉庫：操作的執(zhí)行次序是預(yù)先確定的,8,Control,Objective: make knowledge sources respond opportunistically 讓知識源響應(yīng)偶然事件 Representation: keeps various sorts of information about which knowledge sources could operate and picks a sequence that allows the solution process to proceed a step at a time 了解各個知識源的能力，決策解決問題的步驟 Remark: the control mechanisms are thoroughly ad hoc 控制機制是徹底的與時俱進、隨機應(yīng)變,9,Blackboard Style,需要一個模塊來控制讓哪個ks工作（調(diào)度）,10,The Blackboard Model,Knowledge Sources Problem-appropriate knowledge partitioned into separate, independent computations 把問題分成幾個部分，每個部分獨立計算 React to changes in blackboard Blackboard Data Structure Global database containing entire state of problem solution 全局數(shù)據(jù)庫包含解域的全部狀態(tài) Only means by which knowledge sources interact 知識源互相作用的唯一媒介 Control 完全由黑板的狀態(tài)驅(qū)動，黑板的狀態(tài)的改變決定使用的特定知識 Knowledge sources respond “opportunistically” 讓知識源響應(yīng)偶然事件 Historical examples: Hearsay I, Hearsay II, HASP/SAIP, CRYSALIS, ATOME Originally most were from signal processing, problem solving (planning, logistics, diagnostics) （信號處理、專家系統(tǒng)、模式識別領(lǐng)域經(jīng)常采用）,11,The Blackboard Model,12,Blackboard Architecture,13,Blackboard Problem Characteristics,no direct algorithmic solution 沒有直接的算法可解 multiple approaches to solving the problem 多種方法都可能解決問題 various domain expertise required to solve the problem 需要多個領(lǐng)域的專門知識協(xié)作解決 uncertainty error and variability in data and solution 數(shù)據(jù)和解決方法可能錯誤或變化 moderate to low “signal-to-noise-ratio” in data 數(shù)據(jù)中信噪比的變化 Uncertainty interferes with algorithmic solutions 算法接口的變化 Best-effort” or approximation is good enough no single discrete answer to problem, or “right” answer may vary 問題沒有唯一的解答，或者“正確”答案會變化,14,Example：The Puzzle Metaphor,15,Example：The Puzzle Metaphor,Data within the blackboard is often structured hierarchically,16,Hearsay II,Complex blackboard system to deal with arbitrary speech recongition (a difficult problem): Ambiguity in segmentation（音節(jié)分割問題）: “Marys truck” versus “Mary struck” Ambiguity in stress（重音問題）: “disease” versus “dizzies” Ambiguity in grammar（語法問題）: “The horse raced past the barn fell” Ambiguity in semantics（語義問題）: “I saw the man on the hill with the binoculars”,17,Problem Solving Strategy,Had to be incremental, opportunistic, flexible 必須是增量的、機會主意的、靈活的 Hearsay-II employed several strategies: Bottom-up (synthetic) Top-down (analytic) General hypothesize-and-test （猜測和測試） Blackboard structure entertained many simultaneous hypotheses 黑板結(jié)構(gòu)可以同時處理多種假設(shè) Control was complex: had a monitor portion and a priority based scheduler 控制很復(fù)雜：有一個監(jiān)視器，采用基于優(yōu)先級的調(diào)度 1971年至1976年， Hearsay-II 就已經(jīng)在DEC PDP-10s上實現(xiàn)。,18,Problem Solving,問題求解是從人工智能初期的智力難題、棋類游戲、簡單數(shù)學(xué)定理證明等問題的研究中開始形成和發(fā)展起來的一大類解題技術(shù) 問題求解系統(tǒng)一般由全局數(shù)據(jù)庫、算子集和控制程序三部分組成 解題過程可以運用正向推理，即從問題的初始狀態(tài)開始，運用適當(dāng)?shù)乃阕有蛄薪?jīng)過一系列狀態(tài)變換直到問題的目標(biāo)狀態(tài)。這是一種自底向上的綜合方法。也可以運用逆向推理，即從問題的目標(biāo)出發(fā)，選用另外的算子序列將總目標(biāo)轉(zhuǎn)換為若干子目標(biāo)，也就是將原來的問題歸約為若干較易實現(xiàn)的子問題，直到最終得到的子問題完全可解。這是一種自頂向下的分析方法。,19,Problem Solving - Bottom-up (synthetic),狀態(tài)空間表示：如果一個問題求解系統(tǒng)運用正向推理，而且每次算子對全局數(shù)據(jù)庫操作后都生成一新狀態(tài)，則該系統(tǒng)采用的解題方法就稱狀態(tài)空間表示法。右中樹的節(jié)點標(biāo)號代表狀態(tài)，其中 為初始狀態(tài)， 為目標(biāo)狀態(tài)；有向弧線的標(biāo)號代表算子；從初始狀態(tài)到達目標(biāo)狀態(tài)經(jīng)歷 的狀態(tài)變換。這時問題的一個解便是能將問題初始狀態(tài)最終變換為目標(biāo)狀態(tài)的一個有限的算子序列。本例中即為P2-P2-P4。而尋找問題的解，也就是尋找適用的算子序列的過程，這稱為搜索。,20,Problem Solving - Top-down (analytic),問題歸約表示 問題歸約有三個要素，即目標(biāo)、算子集和基元問題集。目標(biāo)：即問題的初始描述。算子集：用來將給定問題變換為若干子問題?；獑栴}集：已有解或其解十分明顯可以直接描述的問題。問題約表示是同逆向推理聯(lián)系在一起的。右圖為問題的歸約表示，其中每個節(jié)點標(biāo)號代表一個問題或一組問題,標(biāo)號為A的根節(jié)點（即沒有射入弧線的節(jié)點）代表原始問題或問題組。沒有射出弧線的節(jié)點稱為葉或終端節(jié)點（或終止節(jié)點），其標(biāo)號代表基元問題。運用算子實行問題變換。,21,Hearsay II Structure,22,Hearsay II Model,黑板結(jié)構(gòu)是一個六至八層的層次結(jié)構(gòu)，每一層都抽象了與之相鄰的較低一層的信息 黑板元素代表了關(guān)于語音解釋的假設(shè) 知識源代表整個問題求解中的獨立的子任務(wù)，比如分割原始信號、識別音素、產(chǎn)生候選詞、假定語法片斷、提供語義解釋 每個知識源被組織成一個條件部分和一個動作部分，條件部分規(guī)定什么時候知識源可用，動作部分負責(zé)處理相關(guān)的黑板元素并產(chǎn)生新的元素 控制構(gòu)件作為黑板的監(jiān)控程序和調(diào)度程序；通常將黑板知識源應(yīng)用到黑板中各種元素具有優(yōu)先次序，調(diào)度程序負責(zé)監(jiān)控黑板和計算的優(yōu)先次序。,23,Software Architecture Style: Virtual Machine 為什么Java可以“一次書寫，多處運行”？ 如何在PC上開發(fā)iPhone上的程序？,什么是虛擬機？,一種軟件 創(chuàng)建了虛擬的環(huán)境 屏蔽了底層平臺 分類： 系統(tǒng)級（硬件虛擬機）：可以把一臺電腦虛擬為運行不同OS的多臺電腦 進程級（應(yīng)用程序虛擬機）：JVM 機器聚合：云計算,24,25,Virtual Machines體系結(jié)構(gòu)的成員,Interpreters Simulate functionality which is not native to the hardware Rule-based systems Specialization of an interpreter Other Syntactic（句法的） shells Command language processors,虛擬機在高層和底層間建立屏障，但如何把高層的請求映射到底層硬件/OS來執(zhí)行？,26,Interpreter,Problem: This pattern is suitable for applications in which the most appropriate language or machine for executing the solution is not directly available. The pattern is also suitable for applications in which the core problem is defining a notation for expressing solutions, for example as scripts. Interpreters are sometimes used in chains, translating from the desired language/machine to an available language/machine in a series of stages. Context: The interpreter will most often be designed to bridge the gap between the desired machine or language and some (possibly virtual) machine or language already supported by the execution environment. 解釋器是用來“執(zhí)行其他程序的程序”，很多腳本語言都采用解釋的方式運行，即程序源代碼直接被解釋執(zhí)行（不需編譯）。瀏覽器也是典型的解釋器。,27,Interpreter,Solution: System model: virtual machine Components: one state machine (the execution engine) and three memories (current state of execution engine在某時刻需要執(zhí)行哪些命令, program being interpreted, current state of program being interpreted) Connectors: data access and procedure call Control structure: usually state-transition（狀態(tài)轉(zhuǎn)移） for execution engine; input driven for selection of what to interpret Significant Variants: Expert systems are often implemented as interpreters for the collections of rules, or productions, that represent the expertise. Because the productions require a complex selection rule, specialized forms of interpreters have evolved.,28,Interpreter,程序執(zhí)行的當(dāng)前狀態(tài),被解釋執(zhí)行的程序,解釋器內(nèi)部狀態(tài)引擎,解釋器引擎,組件：一個狀態(tài)機（解釋引擎）、三個存儲區(qū) 連接件：過程調(diào)用/對存儲區(qū)的數(shù)據(jù)訪問,29,Interpreter : Advantages,Functionality: Can simulate non-native functionality Testing: Can simulate “disaster” modes (e.g. for safety-critical applications) Flexibility: Very general-purpose tool,30,Interpreter : Disadvantages,Efficiency: Much, much slower than hardware Much slower than compiled system Testing: Additional layer of software to be verified 解釋器和編譯器的區(qū)別 解釋器的執(zhí)行速度慢于編譯器產(chǎn)生的目標(biāo)代碼的執(zhí)行速度，但低于“編譯+鏈接+執(zhí)行”的總時間 每次解釋執(zhí)行時，都需要分析程序結(jié)構(gòu)，而編譯器只需一次性編譯代碼,31,解釋器的用途,解釋型語言 VB、Javascript、VBScript、HTML、Java字節(jié)碼、Matlab 腳本、配置文件 游戲內(nèi)置腳本引擎 通信協(xié)議 用戶輸入 游戲中的組合按鍵,32,Rule-based system,所要解決的問題,當(dāng)業(yè)務(wù)規(guī)則很復(fù)雜時，不宜用if-else結(jié)構(gòu)表示 寫為代碼的業(yè)務(wù)不易理解 按照OCP（開放/封閉原則），應(yīng)把可變部分與不變部分分離開，在前者發(fā)生變化時就不會影響后者 核心：把頻繁變化的、復(fù)雜的業(yè)務(wù)規(guī)則抽取出來，形成獨立的規(guī)則庫，而不是將規(guī)則寫入代碼。 規(guī)則使用基于XML或自然語言的規(guī)則定義語言（絕不是程序設(shè)計語言），規(guī)則形如（IfThen）。其余部分仍舊使用高級語言 系統(tǒng)根據(jù)目前的狀態(tài)，從規(guī)則庫中選擇合適的規(guī)則，對規(guī)則進行解釋，根據(jù)結(jié)果控制系統(tǒng)的運行,33,基于規(guī)則的系統(tǒng)：使用模式匹配搜索來尋找規(guī)則，并在正確時機應(yīng)用正確的規(guī)則的虛擬機,34,Rule-based system : features,Code to be executed (knowledge base) Interpretation engine (rule interpreter) Control state of interpreter (rule/data selection) Current state of the code (working memory),仍然是 1引擎+3存儲區(qū) 的結(jié)構(gòu)，構(gòu)件與解釋器風(fēng)格類似,說明,優(yōu)點 降低修改業(yè)務(wù)邏輯的成本與風(fēng)險 縮短開發(fā)時間 規(guī)則可在多個應(yīng)用共享 與解釋器風(fēng)格的不同 解釋器：在高級程序語言與OS/硬件平臺間建立虛擬機 基于規(guī)則的系統(tǒng)：在自然語言/XML規(guī)則和高級程序語言間建立虛擬機,35,常見的規(guī)則,用戶界面輸入的合法性檢查 安全規(guī)則/權(quán)限控制規(guī)則 業(yè)務(wù)策略（如VIP折扣策略等）,36,37,Sophisticated rule-based system,38,Recovering the simplicity,39,Hearsay-II Recast as Interpreter,40,Software Architecture Style: Independent Component,41,Independent Components,Communicating Processes Messages passed among named participants Event Systems Implicit invocation among unnamed participants Others Multicast to agents Interrupt-drive processes,42,Motivation,New Processors with complicated software supporting multiprocesses (multithreads) Multiprocessors introducing parallel computing High speed networks leading to distributed computing Already in wide use Operating systems Distributed applications,43,Communicating Processes,完成任務(wù)需要多個proc協(xié)同，prco間的協(xié)同通過msg完成 msg是“顯性”的，即需要指明“源”和“目的地”,44,Communicating Processes,Problem: This pattern is suitable for applications that involve a collection of distinct, largely independent computations whose execution should proceed independently. The computations involve coordination of data or control at discrete points in time. As a result, correctness of the system requires attention to the routing and synchronization of the messages. Context: The selection of a communication strategy is often dictated by the communication support provided by the available operating system.,45,Communicating Processes : Model,Solution: System model: independent communicating processes Components: processes that send a