Thời gian thực - hệ thống P11

Real-Time Systems: Scheduling, Analysis, and Verification. Albert M. K. Cheng Copyright ¶ 2002 John Wiley & Sons, Inc. ISBN: 0-471-18406-3 CHAPTER 11 TIMING ANALYSIS OF PREDICATE-LOGIC RULE-BASED SYSTEMS As rule-based expert systems become widely adopted in new application domains such as real-time systems, ensuring that they meet stringent timing constraints in these safety-critical and time-critical environments emerges as a challenging prob-lem. As described in detail in chapter 10, in these systems, a change in the envi-ronment may trigger a number of rule firings to compute an appropriate response. If the computation takes too long, the expert system may not have sufficient time to respond to the ongoing changes in the environment, making the result of the com-putation useless or even harmful to the system being monitored or controlled. To evaluate and control the performance of a real-time expert system, it is necessary to relate the quality of a response computed by the expert system to the time available to compute it. Even in a case where response time is not a major concern or a deadline is not imposed, the predictability is still a desired quality which may improve the resource utilization or the user productivity. For example, if the programmer has a tool to measure an upper bound on the maximal program response time, he/she will not have to guess whether the program runs into an infinite loop or the program just takes a long time to complete execution, thus avoiding unnecessary waiting for the program to complete execution or undesirable interrupting of program execution. This is particularly true for production systems whose rule firing patterns depend on initial working memory contents. Unfortunately, rule-based expert systems are computationally expensive and slow. Moreover, they are considered less predictable and analyzable because of their context-sensitive control flow and possible nondeterminism. To remedy this prob-lem, two solutions are proposed in the literature. The first is to reduce the execution time via parallelism in the matching phase and/or firing phase of the MRA [Brown-ston et al., 1986] cycle. Several approaches [Cheng, 1993b; Ishida, 1994; Kuo and 367 368 TIMING ANALYSIS OF PREDICATE-LOGIC RULE-BASED SYSTEMS Moldovan, 1991; Pasik, 1992; Schmolze, 1991] have been provided to achieve this goal. The other solution is to optimize the expert system by modifying or resynthe-sizing the rule base if the response time is found to be inadequate [Zupan and Cheng, 1994a; Zupan and Cheng, 1998]. In this chapter, we present more approaches for the response-time analysis of rule-based systems. In particular, we study the timing properties of programs written in the predicate-logic-based OPS5 language [Forgy, 1981] (and other OPS5-style languages), which is not designed for real-time purposes although it has been widely adopted in practice. In chapter 10, we introduced the propositional-logic-based rule-based language EQL (equational rule-based language), for real-time applications. EQL is a simple, rule-based language with well-defined semantics. It has been used to program a number of practical real-time applications. OPS5 exhibits an incremental increase in expressiveness over MRL [Wang, Mok, and Cheng, 1990; Wang, 1990a] but it is not as complex as more recent object-oriented rule-based languages. OPS5 has been successfully used in a variety of ap-plications [Forgy, 1985]. MRL is designed to be an extension of EQL. It includes set variables (working memories) and logical quantifiers over set variables. How-ever, MRL does not include the timing tags in its working memory, so many conflict resolution strategies, such as LEX and MEA, cannot be applied to MRL programs. It is entirely the programmer’s responsibility to guarantee that any firing sequence is a normal execution flow. Under this situation, the programmer usually needs to avoid interference among rules; otherwise, the program may be hard to debug and maintain. OPS5 has been used to implement several industrial expert systems, including MILEX (The Mitsui Real Time Expert System) and XCON/R1, which is generally considered the first commercially successful expert system [Forgy, 1985]. Our goal is to obtain a tighter bound on the execution time that is close to the real upper bound. We consider the case where an OPS5 expert-system program forms the decision module of a real-time monitoring and controlling system [Payton and Bihari, 1991]. This real-time system takes sensor input readings periodically, and the embedded expert system must produce, based on these input values and state values from previous invocations of the expert system, an output decision that ensures the safety and progress of the real-time system and its environment prior to the taking of the next sensor input values. Thus, the upper bound on the expert system’s execution time cannot exceed the length of the period between two consecutive sensor input readings [Cheng et al., 1993; Chen and Cheng, 1995b]. Therefore, our goal is to determine, before run-time, a tight upper bound on the execution time of the expert system in every invocation following each reading of sensor input values. To analyze the timing behavior of an OPS5 program, we first formalize a graph-ical representation of rule-based programs. This high-level data-dependency graph captures all possible logical control paths in a program. Based on this graph, we design a termination detection algorithm to determine whether an OPS5 program al-ways terminates in bounded time. If an OPS5 program is not detected to terminate for all initial program states, then the “culprit” conditions that cause nontermination are extracted to assist programmers in correcting the program. They then modify THE OPS5 LANGUAGE 369 the program to ensure program termination. Note that this modification is performed off-line, prior to the execution of the expert system, and the modified version must still satisfy the logical correctness constraints. On the other hand, if the termination of an OPS5 program is guaranteed, we proceed to determine an upper bound on its execution time. Instead of using static analysis, we build a tool to aid timing analy-sis of OPS5 expert systems. This tool generates a set of working memory elements (WMEs) which cause the program to consume maximum time. We take this set of WMEs as the initial working memory (WM) and test the program to determine the maximum execution time. In real applications, the initial WM is usually restricted to a certain domain. The OPS5 programs can execute only normally with this restric-tion. So, we also take this information into consideration. Users can then provide their requirements of the initial WM to our tool, making it possible to reduce the size of the WMEs we generate and thus produce more accurate analysis results. We briefly introduce the OPS5 language in the next section. Then we describe the Cheng–Tsai analysis methodology, partially based on the graphical representation of the control paths of OPS5 programs. Next we present the Cheng–Chen analysis methodology, based on a different set of quantitative algorithms. 11.1 THE OPS5 LANGUAGE This section provides an overview of the OPS5 language, with examples, and de-scribes the Rete matching network for determining instantiations of rules. 11.1.1 Overview An OPS5 rule-based program [Forgy, 1981; Brownston et al., 1986; Cooper and Wogrin, 1988] consists of a finite set of rules, each of which is of the form (p rule-name (condition-element-1) (condition-element-2) : (condition-element-m) --> (action-1) : (action-n)) and a database of assertions, each of which is of the form (class-name ^attribute-1 ^attribute-2 ^attribute-p value-1 value-2 : value-p) The symbol “^” means there is an attribute name following it. The set of rules is called the production memory (PM) and the database of assertions is called the 370 TIMING ANALYSIS OF PREDICATE-LOGIC RULE-BASED SYSTEMS working memory (WM). Each assertion is called a working memory element (WME). A rule has three parts: • the name of the rule, rule-name; • the left-hand-side (LHS), that is, a conjunction of the condition elements, each of which can be either a positive condition element or negative condition ele-ment; and • theright-hand-side(RHS),thatis,theactions,eachofwhichmaymake,modify, or delete a WME, perform I/O, or halt. All atoms are literals unless put in variable brackets <>. The scope of variables is a single rule. A WME is an instance of an element class. An element class defines a WME structure in the same way a C data type defines the structure of entities in a C program. An element class is the template from which instances are made. It is identified by class-name and by a collection of attributes describing characteristics relevant to the entity. The following is an OPS5 rule for processing sensor informa-tion from a radar system: (p radar-scan ; an OPS5 rule (region-scan1 ^sensor object) ; positive condition element (region-scan2 ^sensor object) ; positive condition element (status-check ^status normal) ; positive condition element - (interrupt ^status on) ; negative condition element { ; positive condition element (configuration ^object-detected 0) } --> (modify ^object-detected 1)) ; action If both radars, (region-scan1) and (region-scan2), detect an object, the status of the radar system is normal, there is no interrupt, and the attribute object-detected in the element class configuration is 0, then assign 1 to object-detected. The nota-tion WME is used to name the matching WME for use in this action. Hence, refers to the “configuration” WME matched in the LHS. Otherwise, the number of the matching conditions in the LHS may be used in modify and delete commands. Comments are given following the semicolon. When the working memory contains the WMEs (region-scan1 ^sensor object) (region-scan2 ^sensor object) (status-check ^status normal) (configuration ^object-detected 0) but does not contain the WME (interrupt ^status on), the above rule is said to have a successful matching. More precisely, a rule is enabled if each of its positive con-dition elements is matched with a WME in the working memory and each of its negative condition elements is not matched by any WME in the working memory. A rule firing is the execution of the RHS actions in the order they appear in the rule. The above rule fires by modifying the attribute object-detected in the element class configuration to have the value 1. THE OPS5 LANGUAGE 371 A condition element can consist of value tests, other than equality,that a matching WME value must satisfy. These tests may be specified using the following compo-nents. Consider the WME (airport ^airport-terminals 3 ^vacancies 3), which is an instance of the element class airport. • Variables: variables are specified in brackets and are used for matching values in the WMEs, or for defining a relationship between two values. Variables are implicitly existentially quantified over the rule LHS and RHS. Note that the following example requires the same value for the attributes airport-terminals and vacancies. ^airport-terminals ^vacancies • Predicate operators: for restricting the range of values that can match. ^airport-terminals > 0 • Disjunctions: for specifying a list of values, one of which must be equal to the value in the WME. ^airport-terminals << 1 2 3 >> • Conjunctions: for specifying a group of value tests that must be satisfied by one WME value. ^airport-terminals { > 1 <> nil } • Variable semantic restrictions: any variable may be further qualified using these predicates by inclusion in the braces, as in (airport ^airport-terminals { > 0 }). The execution of the OPS5 program is known as the MRA cycle [Brownston et al., 1986] and is executed by the inference engine. The MRA cycle consists of three phases: • Match: for each rule, determine all sets of WMEs that match the condition elements of the rule. Note that a rule may have more than one matching. The result of a successful match is called an instantiation. The set of all satisfied rule instantiations is called the conflict set. • Resolve (Select): a single rule instantiation is selected from the conflict set ac-cording to some conflict-resolution strategies. Two common strategies are LEX (lexicographic ordering) and MEA (means-end analysis). • Act: the selected rule instantiation is executed in the act phase. The actions in the selected rule are executed sequentially in the order they appear in the rule. ... - tailieumienphi.vn