SA02.3Style黑板虛擬機(jī)獨(dú)立組.ppt

1,SE3121021: Software Architecture Software Architecture Style,Blackboard,2,，如同多位不同專長(zhǎng)的專家在同一黑板上交流思想，每個(gè)專家都可以獲得別的專家寫(xiě)在黑板上的信息，同時(shí)也可以用自己的分析去更新黑板上的信息，從而影響其它專家。,Blackboard,解決無(wú)確定性求解策略問(wèn)題。 語(yǔ)境：一個(gè)不成熟的領(lǐng)域，其中沒(méi)有相近的或可行的方法 問(wèn)題：針對(duì)那些需要把原始數(shù)據(jù)轉(zhuǎn)換成高層數(shù)據(jù)結(jié)構(gòu)，但沒(méi)有可行的確定性解的場(chǎng)合。 在合理的時(shí)間內(nèi)，解空間的完全求解不可行。 由于領(lǐng)域不成熟，模塊應(yīng)易于替換以便試驗(yàn)。 對(duì)子問(wèn)題的求解可以有多種算法。 解決方案： 設(shè)計(jì)公共數(shù)據(jù)結(jié)構(gòu)。 設(shè)計(jì)多個(gè)專用組件，每個(gè)組件解決任務(wù)的一個(gè)特定部分。 每個(gè)組件可對(duì)公共數(shù)據(jù)結(jié)構(gòu)進(jìn)行添加、修改、刪除 仲裁者組件對(duì)每個(gè)組件的工作結(jié)果進(jìn)行評(píng)估，以次為依據(jù)協(xié)調(diào)各組件的工作。 多個(gè)專家，以多個(gè)步驟解決問(wèn)題,4,Blackboard的組成,（1）知識(shí)源：包含獨(dú)立的、與應(yīng)用程序相關(guān)的知識(shí)，知識(shí)源之間不直接進(jìn)行通訊，它們之間的交互只通過(guò)黑板來(lái)完成。一個(gè)知識(shí)源只能解決問(wèn)題的一部分 （2）黑板數(shù)據(jù)結(jié)構(gòu)：按照與應(yīng)用程序相關(guān)的層次來(lái)組織的解決問(wèn)題的數(shù)據(jù)，知識(shí)源利用黑板的接口對(duì)黑板進(jìn)行讀寫(xiě)，通過(guò)不斷地改變黑板數(shù)據(jù)來(lái)解決問(wèn)題。 （3）控制（仲裁者）：控制完全由黑板的狀態(tài)驅(qū)動(dòng)，監(jiān)視黑板的變化，決定下一步使用哪個(gè)知識(shí)源進(jìn)行工作,5,6,Knowledge Sources,Objective: contribute knowledge that leads to solution 提供解決問(wèn)題的知識(shí) Representation: procedures, sets of rules, logic assertions 過(guò)程、規(guī)則、邏輯斷言 Action: modify only the blackboard (or control data - magic) 只修改黑板 Responsibility: know when its possible to help 知道何時(shí)能發(fā)揮作用 Selection: loosely-coupled subtasks, or areas of specialization 低耦合的子任務(wù)，或者有特別的能力,7,Blackboard Data Structure,Objective: hold data for use by knowledge sources 保存知識(shí)源要使用的數(shù)據(jù) Representation: stores objects from solution space, including 保存來(lái)自解空間的數(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 分層；鏈接同層或不同層的對(duì)象 與倉(cāng)庫(kù)的區(qū)別 黑板：黑板的狀態(tài)觸發(fā)進(jìn)一步的操作 倉(cāng)庫(kù)：操作的執(zhí)行次序是預(yù)先確定的,8,Control,Objective: make knowledge sources respond opportunistically 讓知識(shí)源響應(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 了解各個(gè)知識(shí)源的能力，決策解決問(wèn)題的步驟 Remark: the control mechanisms are thoroughly ad hoc 控制機(jī)制是徹底的與時(shí)俱進(jìn)、隨機(jī)應(yīng)變,9,Blackboard Style,需要一個(gè)模塊來(lái)控制讓哪個(gè)ks工作（調(diào)度）,10,The Blackboard Model,Knowledge Sources Problem-appropriate knowledge partitioned into separate, independent computations 把問(wèn)題分成幾個(gè)部分，每個(gè)部分獨(dú)立計(jì)算 React to changes in blackboard Blackboard Data Structure Global database containing entire state of problem solution 全局?jǐn)?shù)據(jù)庫(kù)包含解域的全部狀態(tài) Only means by which knowledge sources interact 知識(shí)源互相作用的唯一媒介 Control 完全由黑板的狀態(tài)驅(qū)動(dòng)，黑板的狀態(tài)的改變決定使用的特定知識(shí) Knowledge sources respond “opportunistically” 讓知識(shí)源響應(yīng)偶然事件 Historical examples: Hearsay I, Hearsay II, HASP/SAIP, CRYSALIS, ATOME Originally most were from signal processing, problem solving (planning, logistics, diagnostics) （信號(hào)處理、專家系統(tǒng)、模式識(shí)別領(lǐng)域經(jīng)常采用）,11,The Blackboard Model,12,Blackboard Architecture,13,Blackboard Problem Characteristics,no direct algorithmic solution 沒(méi)有直接的算法可解 multiple approaches to solving the problem 多種方法都可能解決問(wèn)題 various domain expertise required to solve the problem 需要多個(gè)領(lǐng)域的專門(mén)知識(shí)協(xié)作解決 uncertainty error and variability in data and solution 數(shù)據(jù)和解決方法可能錯(cuò)誤或變化 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 問(wèn)題沒(méi)有唯一的解答，或者“正確”答案會(huì)變化,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é)分割問(wèn)題）: “Marys truck” versus “Mary struck” Ambiguity in stress（重音問(wèn)題）: “disease” versus “dizzies” Ambiguity in grammar（語(yǔ)法問(wèn)題）: “The horse raced past the barn fell” Ambiguity in semantics（語(yǔ)義問(wèn)題）: “I saw the man on the hill with the binoculars”,17,Problem Solving Strategy,Had to be incremental, opportunistic, flexible 必須是增量的、機(jī)會(huì)主意的、靈活的 Hearsay-II employed several strategies: Bottom-up (synthetic) Top-down (analytic) General hypothesize-and-test （猜測(cè)和測(cè)試） Blackboard structure entertained many simultaneous hypotheses 黑板結(jié)構(gòu)可以同時(shí)處理多種假設(shè) Control was complex: had a monitor portion and a priority based scheduler 控制很復(fù)雜：有一個(gè)監(jiān)視器，采用基于優(yōu)先級(jí)的調(diào)度 1971年至1976年， Hearsay-II 就已經(jīng)在DEC PDP-10s上實(shí)現(xiàn)。,18,Problem Solving,問(wèn)題求解是從人工智能初期的智力難題、棋類(lèi)游戲、簡(jiǎn)單數(shù)學(xué)定理證明等問(wèn)題的研究中開(kāi)始形成和發(fā)展起來(lái)的一大類(lèi)解題技術(shù) 問(wèn)題求解系統(tǒng)一般由全局?jǐn)?shù)據(jù)庫(kù)、算子集和控制程序三部分組成 解題過(guò)程可以運(yùn)用正向推理，即從問(wèn)題的初始狀態(tài)開(kāi)始，運(yùn)用適當(dāng)?shù)乃阕有蛄薪?jīng)過(guò)一系列狀態(tài)變換直到問(wèn)題的目標(biāo)狀態(tài)。這是一種自底向上的綜合方法。也可以運(yùn)用逆向推理，即從問(wèn)題的目標(biāo)出發(fā)，選用另外的算子序列將總目標(biāo)轉(zhuǎn)換為若干子目標(biāo)，也就是將原來(lái)的問(wèn)題歸約為若干較易實(shí)現(xiàn)的子問(wèn)題，直到最終得到的子問(wèn)題完全可解。這是一種自頂向下的分析方法。,19,Problem Solving - Bottom-up (synthetic),狀態(tài)空間表示：如果一個(gè)問(wèn)題求解系統(tǒng)運(yùn)用正向推理，而且每次算子對(duì)全局?jǐn)?shù)據(jù)庫(kù)操作后都生成一新?tīng)顟B(tài)，則該系統(tǒng)采用的解題方法就稱狀態(tài)空間表示法。右中樹(shù)的節(jié)點(diǎn)標(biāo)號(hào)代表狀態(tài)，其中 為初始狀態(tài)， 為目標(biāo)狀態(tài)；有向弧線的標(biāo)號(hào)代表算子；從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)經(jīng)歷 的狀態(tài)變換。這時(shí)問(wèn)題的一個(gè)解便是能將問(wèn)題初始狀態(tài)最終變換為目標(biāo)狀態(tài)的一個(gè)有限的算子序列。本例中即為P2-P2-P4。而尋找問(wèn)題的解，也就是尋找適用的算子序列的過(guò)程，這稱為搜索。,20,Problem Solving - Top-down (analytic),問(wèn)題歸約表示 問(wèn)題歸約有三個(gè)要素，即目標(biāo)、算子集和基元問(wèn)題集。目標(biāo)：即問(wèn)題的初始描述。算子集：用來(lái)將給定問(wèn)題變換為若干子問(wèn)題?；獑?wèn)題集：已有解或其解十分明顯可以直接描述的問(wèn)題。問(wèn)題約表示是同逆向推理聯(lián)系在一起的。右圖為問(wèn)題的歸約表示，其中每個(gè)節(jié)點(diǎn)標(biāo)號(hào)代表一個(gè)問(wèn)題或一組問(wèn)題,標(biāo)號(hào)為A的根節(jié)點(diǎn)（即沒(méi)有射入弧線的節(jié)點(diǎn)）代表原始問(wèn)題或問(wèn)題組。沒(méi)有射出弧線的節(jié)點(diǎn)稱為葉或終端節(jié)點(diǎn)（或終止節(jié)點(diǎn)），其標(biāo)號(hào)代表基元問(wèn)題。運(yùn)用算子實(shí)行問(wèn)題變換。,21,Hearsay II Structure,22,Hearsay II Model,黑板結(jié)構(gòu)是一個(gè)六至八層的層次結(jié)構(gòu)，每一層都抽象了與之相鄰的較低一層的信息 黑板元素代表了關(guān)于語(yǔ)音解釋的假設(shè) 知識(shí)源代表整個(gè)問(wèn)題求解中的獨(dú)立的子任務(wù)，比如分割原始信號(hào)、識(shí)別音素、產(chǎn)生候選詞、假定語(yǔ)法片斷、提供語(yǔ)義解釋 每個(gè)知識(shí)源被組織成一個(gè)條件部分和一個(gè)動(dòng)作部分，條件部分規(guī)定什么時(shí)候知識(shí)源可用，動(dòng)作部分負(fù)責(zé)處理相關(guān)的黑板元素并產(chǎn)生新的元素 控制構(gòu)件作為黑板的監(jiān)控程序和調(diào)度程序；通常將黑板知識(shí)源應(yīng)用到黑板中各種元素具有優(yōu)先次序，調(diào)度程序負(fù)責(zé)監(jiān)控黑板和計(jì)算的優(yōu)先次序。,23,Software Architecture Style: Virtual Machine 為什么Java可以“一次書(shū)寫(xiě)，多處運(yùn)行”？ 如何在PC上開(kāi)發(fā)iPhone上的程序？,什么是虛擬機(jī)？,一種軟件 創(chuàng)建了虛擬的環(huán)境 屏蔽了底層平臺(tái) 分類(lèi)： 系統(tǒng)級(jí)（硬件虛擬機(jī)）：可以把一臺(tái)電腦虛擬為運(yùn)行不同OS的多臺(tái)電腦 進(jìn)程級(jí)（應(yīng)用程序虛擬機(jī)）：JVM 機(jī)器聚合：云計(jì)算,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,虛擬機(jī)在高層和底層間建立屏障，但如何把高層的請(qǐng)求映射到底層硬件/OS來(lái)執(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. 解釋器是用來(lái)“執(zhí)行其他程序的程序”，很多腳本語(yǔ)言都采用解釋的方式運(yùn)行，即程序源代碼直接被解釋執(zhí)行（不需編譯）。瀏覽器也是典型的解釋器。,27,Interpreter,Solution: System model: virtual machine Components: one state machine (the execution engine) and three memories (current state of execution engine在某時(shí)刻需要執(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)引擎,解釋器引擎,組件：一個(gè)狀態(tài)機(jī)（解釋引擎）、三個(gè)存儲(chǔ)區(qū) 連接件：過(guò)程調(diào)用/對(duì)存儲(chǔ)區(qū)的數(shù)據(jù)訪問(wèn),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í)行”的總時(shí)間 每次解釋執(zhí)行時(shí)，都需要分析程序結(jié)構(gòu)，而編譯器只需一次性編譯代碼,31,解釋器的用途,解釋型語(yǔ)言 VB、Javascript、VBScript、HTML、Java字節(jié)碼、Matlab 腳本、配置文件 游戲內(nèi)置腳本引擎 通信協(xié)議 用戶輸入 游戲中的組合按鍵,32,Rule-based system,所要解決的問(wèn)題,當(dāng)業(yè)務(wù)規(guī)則很復(fù)雜時(shí)，不宜用if-else結(jié)構(gòu)表示 寫(xiě)為代碼的業(yè)務(wù)不易理解 按照OCP（開(kāi)放/封閉原則），應(yīng)把可變部分與不變部分分離開(kāi)，在前者發(fā)生變化時(shí)就不會(huì)影響后者 核心：把頻繁變化的、復(fù)雜的業(yè)務(wù)規(guī)則抽取出來(lái)，形成獨(dú)立的規(guī)則庫(kù)，而不是將規(guī)則寫(xiě)入代碼。 規(guī)則使用基于XML或自然語(yǔ)言的規(guī)則定義語(yǔ)言（絕不是程序設(shè)計(jì)語(yǔ)言），規(guī)則形如（IfThen）。其余部分仍舊使用高級(jí)語(yǔ)言 系統(tǒng)根據(jù)目前的狀態(tài)，從規(guī)則庫(kù)中選擇合適的規(guī)則，對(duì)規(guī)則進(jìn)行解釋，根據(jù)結(jié)果控制系統(tǒng)的運(yùn)行,33,基于規(guī)則的系統(tǒng)：使用模式匹配搜索來(lái)尋找規(guī)則，并在正確時(shí)機(jī)應(yīng)用正確的規(guī)則的虛擬機(jī),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存儲(chǔ)區(qū) 的結(jié)構(gòu)，構(gòu)件與解釋器風(fēng)格類(lèi)似,說(shuō)明,優(yōu)點(diǎn) 降低修改業(yè)務(wù)邏輯的成本與風(fēng)險(xiǎn) 縮短開(kāi)發(fā)時(shí)間 規(guī)則可在多個(gè)應(yīng)用共享 與解釋器風(fēng)格的不同 解釋器：在高級(jí)程序語(yǔ)言與OS/硬件平臺(tái)間建立虛擬機(jī) 基于規(guī)則的系統(tǒng)：在自然語(yǔ)言/XML規(guī)則和高級(jí)程序語(yǔ)言間建立虛擬機(jī),35,常見(jiàn)的規(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ù)需要多個(gè)proc協(xié)同，prco間的協(xié)同通過(guò)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