SA02.3 Style 黑板 虚拟机 独立组件

1、1SE3121021: Software ArchitectureSoftware Architecture StyleBlackboard2如同多位不同专长的专家在同一黑板上交流思想，每个专家都可以获得别的专家写在黑板上的信息，同时也可以用自己的分析去更新黑板上的信息，从而影响其它专家 “黑板”属于“仓库”的变种，黑板的作用相当于“共享内存”Blackboard 解决无确定性求解策略问题（边走边看，摸着石头过河） 不成熟的领域，其中没有相近的或可行的方法 在合理的时间内，解空间的完全求解不可行 由于领域不成熟，模块应易于替换以便试验 对子问题的求解可以有多种算法 解决方案： 设计公共数据结构

2、。 设计多个专用组件，每个组件解决任务的一个特定部分 每个组件可对公共数据结构进行添加、修改、删除 仲裁者组件对每个组件的工作结果进行评估，协调各组件的工作各有专长的多个专家，以多个步骤解决问题各有专长的多个专家，以多个步骤解决问题3Blackboard的组成 知识源（专家） 包含独立的、与应用程序相关的知识，知识源之间不直接进行通讯，它们之间的交互只通过黑板来完成。一个知识源只能解决问题的一部分（一个方面） 黑板数据结构 按照与应用程序相关的层次来组织的解决问题的数据，知识源利用黑板的接口对黑板进行读写，通过不断地改变黑板数据来解决问题。 控制（仲裁者） 控制完全由黑板的状态驱动，监控黑板的

3、变化，决定下一步选用哪个知识源进行工作45Knowledge SourcesObjective: contribute knowledge that leads to solution提供解决问题的知识Representation: procedures, sets of rules, logic assertions表现为过程、规则、逻辑断言Action: modify only the blackboard (or control data - magic)仅能修改黑板，无法与其他知识源交互Responsibility: know when its possible to help知道何时

4、能发挥作用Selection: loosely-coupled subtasks, or areas of specialization低耦合的子任务，或者有特别的能力6Blackboard Data StructureObjective: hold data for use by knowledge sources 保存知识源要使用的数据Representation: stores objects from solution space, including保存来自解空间的数据，包括 input data, partial solutions, alternatives, final sol

5、utions, 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分层；同层或不同层的对象之间的关联 与仓库的区别 黑板：黑板的状态触发进一步的操作 仓库：操作的执行次

6、序是预先确定的7Control Objective: make knowledge sources respond opportunistically让知识源响应偶然事件 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 contr

7、ol mechanisms are thoroughly ad hoc控制机制是与时俱进、随机应变的8Blackboard Style需要一个模块来控制让哪个ks工作（调度）9The Blackboard Model Knowledge Sources Problem-appropriate knowledge partitioned into separate, independent computations 把问题分成几个部分，每个部分独立计算 React to changes in blackboard 对黑板的变化做出反应 Blackboard Data Structure Glob

8、al database containing entire state of problem solution全局数据库包含解决方案的全部状态 Only means by which knowledge sources interact知识源互相关联的唯一媒介 Control 完全由黑板的状态驱动，黑板的状态的改变决定使用的特定知识 Knowledge sources respond “opportunistically” 让知识源响应偶然事件10The Blackboard Model11Blackboard Architecture12Blackboard Problem Characte

9、ristics no direct algorithmic solution没有直接的算法可解 multiple approaches to solving the problem多种方法都可能解决问题 various domain expertise required to solve the problem需要多个领域的专门知识协作解决 uncertainty error and variability in data and solution数据和解决方法可能错误或变化 moderate to low “signal-to-noise-ratio” in data数据中信噪比的变化 Un

10、certainty interferes with algorithmic solutions算法接口的变化 Best-effort” or approximation is good enough no single discrete answer to problem, or “right” answer may vary问题没有唯一的解答，或者“正确”答案会变化13Example：The Puzzle Metaphor14Example：The Puzzle MetaphorData within the blackboard is often structured hierarchic

11、allyLevel 4assemble chunksLevel 3build chunks of edges build chunks of skyLevel 2collect edge piecescollect sky piecesLevel 1Turn all pieces picture side up15Hearsay II Complex blackboard system to deal with arbitrary speech recongition (a difficult problem): Ambiguity in segmentation（音节分割问题）: “Mary

12、s 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”16Problem Solving StrategyHad to be incremental, opportunistic, flexible必须

13、是增量的、机会主意的、灵活的Hearsay-II employed several strategies: Bottom-up (synthetic) Top-down (analytic) General hypothesize-and-test （猜测和测试）Blackboard structure entertained many simultaneous hypotheses黑板结构可以同时处理多种假设Control was complex: had a monitor portion and a priority based scheduler控制很复杂：有一个监视器，采用基于优先级

14、的调度1971年至1976年， Hearsay-II 就已经在DEC PDP-10s上实现。17Problem Solving 问题求解是从人工智能人工智能初期的智力难题、棋类游戏、简单数学定理证明等问题的研究中开始形成和发展起来的一大类解题技术 问题求解系统一般由全局数据库、算子集和控制程序三部分组成 解题过程可以运用正向推理，即从问题的初始状态开始，运用适当的算子序列经过一系列状态变换直到问题的目标状态。这是一种自底向上的综合方法。也可以运用逆向推理，即从问题的目标出发，选用另外的算子序列将总目标转换为若干子目标，也就是将原来的问题归约为若干较易实现的子问题，直到最终得到的子问题完全可解。

15、这是一种自顶向下的分析方法。18Problem Solving - Bottom-up (synthetic)状态空间表示：如果一个问题求解系统运用正向推理，而且每次算子对全局数据库操作后都生成一新状态，则该系统采用的解题方法就称状态空间表示法。右中树的节点标号代表状态，其中 为初始状态， 为目标状态；有向弧线的标号代表算子；从初始状态到达目标状态经历 的状态变换。这时问题的一个解便是能将问题初始状态最终变换为目标状态的一个有限的算子序列。本例中即为P2-P2-P4。而寻找问题的解，也就是寻找适用的算子序列的过程，这称为搜索。19Problem Solving - Top-down (anal

16、ytic)问题归约表示问题归约有三个要素，即目标、算子集和基元问题集。目标：即问题的初始描述。算子集：用来将给定问题变换为若干子问题。基元问题集：已有解或其解十分明显可以直接描述的问题。问题约表示是同逆向推理联系在一起的。右图为问题的归约表示，其中每个节点标号代表一个问题或一组问题,标号为A的根节点（即没有射入弧线的节点）代表原始问题或问题组。没有射出弧线的节点称为叶或终端节点（或终止节点），其标号代表基元问题。运用算子实行问题变换。20Hearsay II Structure21Hearsay II Model 黑板结构是一个六至八层的层次结构，每一层都抽象了与之相邻的较低一层的信息 黑板元

17、素代表了关于语音解释的假设 知识源代表整个问题求解中的独立的子任务，比如分割原始信号、识别音素、产生候选词、假定语法片断、提供语义解释 每个知识源被组织成一个条件部分和一个动作部分，条件部分规定什么时候知识源可用，动作部分负责处理相关的黑板元素并产生新的元素 控制构件作为黑板的监控程序和调度程序；通常将黑板知识源应用到黑板中各种元素具有优先次序，调度程序负责监控黑板和计算的优先次序。22Software Architecture Style: Virtual Machine为什么Java可以“一次书写，多处运行”？如何在PC上开发Android或iOS程序？什么是虚拟机？ 一种软件 创建了虚拟

18、的环境 屏蔽了底层平台 分类： 系统级（硬件虚拟机）：可以把一台电脑虚拟为运行不同OS的多台电脑 进程级（应用程序虚拟机）：JVM 机器聚合：云计算2324Virtual Machines体系结构的成员 Interpreters Simulate functionality which is not native to the hardware Rule-based systems Specialization of an interpreter Other Syntactic（句法的） shells Command language processors虚拟机在高层和底层间建立“屏障”，但如

19、何把高层的请求映射到底层硬件/OS来执行？25Interpreter 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

20、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

21、(possibly virtual) machine or language already supported by the execution environment.解释器是用来“执行其他程序的程序”，很多脚本语言都采用解释的方式运行，即程序源代码直接被解释执行（不需编译）。浏览器也是典型的解释器。26Interpreter Solution: System model: virtual machine Components: one state machine (the execution engine) and three memories (current state of exe

22、cution engine在某时刻需要执行哪些命令, program being interpreted, current state of program being interpreted) 1个状态机+3个存储区 Connectors: data access and procedure call Control structure: usually state-transition（状态转移） for execution engine; input driven for selection of what to interpret Significant Variants: Exper

23、t 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.27Interpreter程序执行的当前状态被解释执行的程序解释器内部状态引擎解释引擎组件：一个状态机（解释引擎）、三个存储区连接件：过程调用

24、/对存储区的数据访问28Interpreter : Advantages Functionality: Can simulate non-native functionality Testing: Can simulate “disaster” modes (e.g. for safety-critical applications) Flexibility: Very general-purpose tool29Interpreter : Disadvantages Efficiency: Much, much slower than hardware Much slower than co

25、mpiled system Testing: Additional layer of software to be verified 解释器和编译器的区别解释器的执行速度慢于编译器产生的目标代码的执行速度，但低于“编译+链接+执行”的总时间每次解释执行时，都需要分析程序结构，而编译器只需一次性编译代码30解释器的用途 解释型语言 VB、JavaScript、HTML、Matlab、R 脚本（shell）、配置文件 游戏内置脚本引擎（Lua） 通信协议 用户输入 游戏中的组合按键/快捷键31Rule-based system所要解决的问题 当业务规则很复杂时，不宜用if-else结构表示 多层的

26、if-else嵌套不易理解和修改 按照OCP（开放/封闭原则），应把可变部分与不变部分进行分离，在前者发生变化时就不会影响后者 核心：把频繁变化的、复杂的业务规则抽取出来，形成独立的规则库，而不是将规则写入代码。 规则使用基于XML或自然语言的规则定义语言（不是程序设计语言），规则形如（IfThen）。其余部分仍旧使用高级语言 系统根据目前的状态，从规则库中选择合适的规则，对规则进行解释，根据结果控制系统的运行32基于规则的系统：一种特殊的虚拟机，使用模式匹配搜索来寻找规则，并在正确时机应用正确的规则33Rule-based system : features 1引擎 Interpretati

27、on engine (rule interpreter) 3存储区 Code to be executed (knowledge base) Control state of interpreter (rule/data selection) Current state of the code (working memory)仍然是 1引擎+3存储区 的结构，构件与解释器风格类似说明 优点 降低修改业务逻辑的成本与风险 缩短开发时间 规则可在多个应用中共享 与解释器风格的不同 解释器：在高级程序语言与OS/硬件平台间建立虚拟机 基于规则的系统：在自然语言/XML规则和高级程序语言间建立虚拟机3

28、4常见的规则 用户界面输入的合法性检查 安全规则/权限控制规则 业务策略（如VIP折扣策略等）与“Strategy模式”类似35各种促销+多级别VIP折扣36Sophisticated rule-based system37Recovering the simplicity38Hearsay-II Recast as Interpreter39Software Architecture Style: Independent Component 40Independent Components Communicating Processes Messages passed among named

29、 participants Event Systems Implicit invocation among unnamed participants Others Multicast to agents Interrupt-drive processes41Motivation New Processors with complicated software supporting multiprocesses (multithreads) Multiprocessors introducing parallel computing High speed networks leading to

30、distributed computing Already in wide use Operating systems Distributed applications42Communicating Processes完成任务需要多个proc协同，prco间的协同通过msg完成msg是“显性”的，即需要指明“源”和“目的地”43Communicating Processes Problem: This pattern is suitable for applications that involve a collection of distinct, largely independent c

31、omputations 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. 通信策略取决于OS的支持组件间相对独立，依靠“发消息”通信44Communicating Processes : Model Solution: System model: independent communicating processes Components: processes that send and receive messages to/fr