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

1,SE3121021: Software Architecture Software Architecture Style,Blackboard,2,，如同多位不同专长的专家在同一黑板上交流思想，每个专家都可以获得别的专家写在黑板上的信息，同时也可以用自己的分析去更新黑板上的信息，从而影响其它专家。,Blackboard,解决无确定性求解策略问题。 语境：一个不成熟的领域，其中没有相近的或可行的方法 问题：针对那些需要把原始数据转换成高层数据结构，但没有可行的确定性解的场合。 在合理的时间内，解空间的完全求解不可行。 由于领域不成熟，模块应易于替换以便试验。 对子问题的求解可以有多种算法。 解决方案： 设计公共数据结构。 设计多个专用组件，每个组件解决任务的一个特定部分。 每个组件可对公共数据结构进行添加、修改、删除 仲裁者组件对每个组件的工作结果进行评估，以次为依据协调各组件的工作。 多个专家，以多个步骤解决问题,4,Blackboard的组成,（1）知识源：包含独立的、与应用程序相关的知识，知识源之间不直接进行通讯，它们之间的交互只通过黑板来完成。一个知识源只能解决问题的一部分 （2）黑板数据结构：按照与应用程序相关的层次来组织的解决问题的数据，知识源利用黑板的接口对黑板进行读写，通过不断地改变黑板数据来解决问题。 （3）控制（仲裁者）：控制完全由黑板的状态驱动，监视黑板的变化，决定下一步使用哪个知识源进行工作,5,6,Knowledge Sources,Objective: 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 知道何时能发挥作用 Selection: loosely-coupled subtasks, or areas of specialization 低耦合的子任务，或者有特别的能力,7,Blackboard Data Structure,Objective: hold data for use by knowledge sources 保存知识源要使用的数据 Representation: stores objects from solution space, including 保存来自解空间的数据，包括 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 分层；链接同层或不同层的对象 与仓库的区别 黑板：黑板的状态触发进一步的操作 仓库：操作的执行次序是预先确定的,8,Control,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 control mechanisms are thoroughly ad hoc 控制机制是彻底的与时俱进、随机应变,9,Blackboard Style,需要一个模块来控制让哪个ks工作（调度）,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 全局数据库包含解域的全部状态 Only means by which knowledge sources interact 知识源互相作用的唯一媒介 Control 完全由黑板的状态驱动，黑板的状态的改变决定使用的特定知识 Knowledge sources respond “opportunistically” 让知识源响应偶然事件 Historical examples: Hearsay I, Hearsay II, HASP/SAIP, CRYSALIS, ATOME Originally most were from signal processing, problem solving (planning, logistics, diagnostics) （信号处理、专家系统、模式识别领域经常采用）,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 需要多个领域的专门知识协作解决 uncertainty error and variability in data and solution 数据和解决方法可能错误或变化 moderate to low “signal-to-noise-ratio” in data 数据中信噪比的变化 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（音节分割问题）: “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 黑板结构可以同时处理多种假设 Control was complex: had a monitor portion and a priority based scheduler 控制很复杂：有一个监视器，采用基于优先级的调度 1971年至1976年， Hearsay-II 就已经在DEC PDP-10s上实现。,18,Problem Solving,问题求解是从人工智能初期的智力难题、棋类游戏、简单数学定理证明等问题的研究中开始形成和发展起来的一大类解题技术 问题求解系统一般由全局数据库、算子集和控制程序三部分组成 解题过程可以运用正向推理，即从问题的初始状态开始，运用适当的算子序列经过一系列状态变换直到问题的目标状态。这是一种自底向上的综合方法。也可以运用逆向推理，即从问题的目标出发，选用另外的算子序列将总目标转换为若干子目标，也就是将原来的问题归约为若干较易实现的子问题，直到最终得到的子问题完全可解。这是一种自顶向下的分析方法。,19,Problem Solving - Bottom-up (synthetic),状态空间表示：如果一个问题求解系统运用正向推理，而且每次算子对全局数据库操作后都生成一新状态，则该系统采用的解题方法就称状态空间表示法。右中树的节点标号代表状态，其中 为初始状态， 为目标状态；有向弧线的标号代表算子；从初始状态到达目标状态经历 的状态变换。这时问题的一个解便是能将问题初始状态最终变换为目标状态的一个有限的算子序列。本例中即为P2-P2-P4。而寻找问题的解，也就是寻找适用的算子序列的过程，这称为搜索。,20,Problem Solving - Top-down (analytic),问题归约表示 问题归约有三个要素，即目标、算子集和基元问题集。目标：即问题的初始描述。算子集：用来将给定问题变换为若干子问题。基元问题集：已有解或其解十分明显可以直接描述的问题。问题约表示是同逆向推理联系在一起的。右图为问题的归约表示，其中每个节点标号代表一个问题或一组问题,标号为A的根节点（即没有射入弧线的节点）代表原始问题或问题组。没有射出弧线的节点称为叶或终端节点（或终止节点），其标号代表基元问题。运用算子实行问题变换。,21,Hearsay II Structure,22,Hearsay II Model,黑板结构是一个六至八层的层次结构，每一层都抽象了与之相邻的较低一层的信息 黑板元素代表了关于语音解释的假设 知识源代表整个问题求解中的独立的子任务，比如分割原始信号、识别音素、产生候选词、假定语法片断、提供语义解释 每个知识源被组织成一个条件部分和一个动作部分，条件部分规定什么时候知识源可用，动作部分负责处理相关的黑板元素并产生新的元素 控制构件作为黑板的监控程序和调度程序；通常将黑板知识源应用到黑板中各种元素具有优先次序，调度程序负责监控黑板和计算的优先次序。,23,Software Architecture Style: Virtual Machine 为什么Java可以“一次书写，多处运行”？ 如何在PC上开发iPhone上的程序？,什么是虚拟机？,一种软件 创建了虚拟的环境 屏蔽了底层平台 分类： 系统级（硬件虚拟机）：可以把一台电脑虚拟为运行不同OS的多台电脑 进程级（应用程序虚拟机）：JVM 机器聚合：云计算,24,25,Virtual Machines体系结构的成员,Interpreters Simulate functionality which is not native to the hardware Rule-based systems Specialization of an interpreter Other Syntactic（句法的） shells Command language processors,虚拟机在高层和底层间建立屏障，但如何把高层的请求映射到底层硬件/OS来执行？,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. 解释器是用来“执行其他程序的程序”，很多脚本语言都采用解释的方式运行，即程序源代码直接被解释执行（不需编译）。浏览器也是典型的解释器。,27,Interpreter,Solution: System model: virtual machine Components: one state machine (the execution engine) and three memories (current state of execution engine在某时刻需要执行哪些命令, program being interpreted, current state of program being interpreted) Connectors: data access and procedure call Control structure: usually state-transition（状态转移） 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,程序执行的当前状态,被解释执行的程序,解释器内部状态引擎,解释器引擎,组件：一个状态机（解释引擎）、三个存储区 连接件：过程调用/对存储区的数据访问,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 解释器和编译器的区别 解释器的执行速度慢于编译器产生的目标代码的执行速度，但低于“编译+链接+执行”的总时间 每次解释执行时，都需要分析程序结构，而编译器只需一次性编译代码,31,解释器的用途,解释型语言 VB、Javascript、VBScript、HTML、Java字节码、Matlab 脚本、配置文件 游戏内置脚本引擎 通信协议 用户输入 游戏中的组合按键,32,Rule-based system,所要解决的问题,当业务规则很复杂时，不宜用if-else结构表示 写为代码的业务不易理解 按照OCP（开放/封闭原则），应把可变部分与不变部分分离开，在前者发生变化时就不会影响后者 核心：把频繁变化的、复杂的业务规则抽取出来，形成独立的规则库，而不是将规则写入代码。 规则使用基于XML或自然语言的规则定义语言（绝不是程序设计语言），规则形如（IfThen）。其余部分仍旧使用高级语言 系统根据目前的状态，从规则库中选择合适的规则，对规则进行解释，根据结果控制系统的运行,33,基于规则的系统：使用模式匹配搜索来寻找规则，并在正确时机应用正确的规则的虚拟机,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存储区 的结构，构件与解释器风格类似,说明,优点 降低修改业务逻辑的成本与风险 缩短开发时间 规则可在多个应用共享 与解释器风格的不同 解释器：在高级程序语言与OS/硬件平台间建立虚拟机 基于规则的系统：在自然语言/XML规则和高级程序语言间建立虚拟机,35,常见的规则,用户界面输入的合法性检查 安全规则/权限控制规则 业务策略（如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,完成任务需要多个proc协同，prco间的协同通过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