A Relational Approach to Monitoring
`Complex Systems
`
`RICHARD SNODGRASS
`University of North Carolina
`
`in
`role
`tools, and plays a central
`is an essential part of many program development
`Monitoring
`Traditional
`monitoring
`techniques
`debugging, optimization,
`status
`reporting,
`and reconfiguration.
`are inadequate when monitoring
`complex systems such as multiprocessors
`or distributed
`systems. A
`new approach
`is described
`in which a historical
`database
`forms
`the conceptual
`basis
`for
`the
`information
`processed by the monitor. This approach permits advances
`in specifying
`the low-level
`data collection,
`specifying
`the analysis of the collected data, performing
`the analysis, and displaying
`the results. Two prototype
`implementations
`demonstrate
`the feasibility
`of the approach.
`
`Distributed
`Networks]:
`[Computer-Communication
`Categories and Subject Descriptors: C.2.4
`Testing and Debugging-debug-
`Systems--distributed
`applications; D.2.5 [Software
`Engineering]:
`Programming
`Environments;
`D.4.8
`ging aids; monitors;
`tracing; D.2.6
`[Software
`Engineering]:
`[Operating
`Systems]:
`Performance-measurements;
`monitors; H.2.3
`[Database Management]:
`Languages-query
`languages; Qucl
`
`General Terms: Measurement
`
`Additional
`TQuel
`
`Key Words and Phrases: Graphical monitoring,
`
`historical
`
`database,
`
`relational
`
`algebra,
`
`1. INTRODUCTION
`concerning a computational
`information
`Monitoring
`is the extraction of dynamic
`process, as that process executes. This definition
`encompasses aspects of obser-
`vation, measurement,
`and testing.* Much has been written
`about monitoring
`uniprocessor
`systems
`(cf.,
`the bibliographies
`[2] and
`[54]), and
`the general
`
`for
`a synonym
`that should be mentioned:
`of monitor
`two other definitions
`least
`i There are at
`operating system, and an arbiter of access to a data structure
`in order
`to ensure specified
`invariants,
`usually
`relating
`to synchronization
`[27]. Both definitions
`emphasize
`the control,
`rather
`than
`the
`obseruationul aspects of monitoring. Monitoring
`is closely associated with, but strictly
`separate
`from,
`activities
`that change
`the course of the computational
`activity.
`The
`term monitor, as used in this
`paper, is the (usually software) agent performing
`the monitoring.
`
`the Defense
`in part, by
`was sponsored,
`University
`at Carnegie-Mellon
`research performed
`The
`Advanced Research Projects Agency
`(DOD), ARPA order 3597, monitored by the Air Force Avionics
`Laboratory
`under contract F33615-78-C-1551,
`the Ballistic Missile Defense Advanced Technological
`Center under contract DASG60-81-0077,
`and
`through a National
`Science Foundation
`graduate
`fellowship. The research performed at the University
`of North Carolina at Chapel Hill was supported
`by the National Science Foundation
`under grant DCR-8402339 and by an IBM Faculty Development
`Award.
`Author’s address: Department
`27599-3175.
`the copies are not
`that
`is granted provided
`fee all or part of this material
`to copy without
`Permission
`made or distributed
`for direct commercial advantage,
`the ACM copyright notice and the title of the
`publication
`and its date appear, and notice
`is given that copying
`is by permission of the Association
`for Computing Machinery.
`To copy otherwise,
`or
`to
`republish,
`requires a fee and/or
`specific
`permission.
`@1988ACM0734-2071/88/0500-0157$01.50
`
`of North Carolina, Chapel Hill, NC
`
`of Computer Science, University
`
`ACM Transactions on Computer Systems, Vol. 6, No. 2, May 1986, Pages 157-196.
`
`Oracle Exhibit 1012, page 1
`
`

`

`158
`
`l
`
`Richard Snodgrass
`
`techniques of tracing and sampling are well established. These approaches do
`not scale well to m,onitoring complex systems, which
`include
`large uniprocessors,
`tightly
`coupled multiprocessor
`systems, and loosely coupled
`local and long-haul
`networks. Two distinctions
`relevant
`to monitoring
`are that complex systems
`often exhibit a lack of central control and that the quantitative
`jump in complex
`systems
`in the number of system components
`(processors, processes, memory,
`addressing domains, etc.) leads to a qualitative
`difference
`in the sophistication
`required of the monitor. These
`two aspects conspire
`to make monitoring
`complex system a difficult
`(and thus interesting)
`task.
`In this paper, we argue that a historical database, an extension of a conventional
`relational database, is an appropriate
`formalization
`of the information
`processed
`by the monitor
`of a complex system. This approach
`induces changes
`in
`the
`ordering of the steps performed during monitoring,
`as well as changes within
`the
`steps themselves.
`In Section 2 we examine
`the sequential process of traditional
`monitoring,
`primarily
`to contrast
`it with
`the approach espoused here. Sections
`3-8 propose the new approach, exposing
`the many opportunities
`such an approach
`presents. Section 9 briefly
`examines
`two
`implementations,
`and
`the
`last
`two
`sections offer conclusions and directions
`for future work.
`
`a
`
`2. APPROACH
`Monitoring
`is a fundamental
`
`component of many computing activities:
`
`the debugging of complex programs.
`use of limited
`computing
`resources
`
`is a
`
`is to facilitate
`use of monitoring
`-One
`-Ensuring
`that
`tools make efficient
`second use.
`can be used to query a computing
`-Monitoring
`measures, but merely
`for status information.
`-Finally,
`monitoring
`information may also be used internally
`programs
`for
`load balancing
`and graceful degradation
`in
`hardware and software
`failures.
`
`system, not
`
`for performance
`
`by application
`the presence of
`
`Debugging proceeds in five stages [50]: (1) o b serve the behavior of a computer
`program;
`(2) compare
`this behavior with
`the desired behavior;
`(3) analyze
`the
`differences;
`(4) devise changes to the program
`to make its behavior conform more
`closely
`to the desired behavior; and (5) alter
`the program
`in accordance with
`these changes. Monitoring
`is concerned with
`the first and, to some extent,
`the
`second and third stages in this process. Monitoring
`is a first step in understanding
`of what happened,
`a computational
`process,
`for it provides an indication
`thus
`to ascertaining why it happened.
`serving as a prerequisite
`Ideally, optimiza-
`Performance
`tuning also requires monitoring
`information.
`tion of resources would be done analytically,
`but in general a priori determination
`of run-time efficiency
`is impossible. Thus,
`it is necessary to tune an application
`program once it
`is implemented.
`Tuning
`requires
`feedback on the program’s
`efficiency, which
`is determined
`from measurements on the program while
`it is
`running.
`such as how far a computation
`can also provide status information,
`Monitoring
`has progressed, who is logged on the system (the system status command of most
`ACM Transactions
`on Computer Systems, Vol. 6, No. 2, May 1988.
`
`Oracle Exhibit 1012, page 2
`
`

`

`A Relational Approach to Monitoring Complex Systems
`
`l
`
`159
`
`(the catalog or directory com-
`files
`the state of certain
`systems),
`time-sharing
`mands), or the nature of hardware and software
`failures.
`For example,
`And, finally, monitoring
`is required
`for dynamic
`reconfiguration.
`to a particular
`consider a program
`that varies the number of processes dedicated
`concerning
`the
`function based on the request rate for that
`function.
`Information
`hardware utilization
`and
`the number of outstanding
`requests could be used
`by the program
`to determine whether
`to start up more processes
`to handle
`the current demand (e.g., if the utilization
`is low and the request rate high)
`[52,
`55, 731. Monitoring
`information
`is also valuable
`for programs
`that must be reli-
`able; the fact that a processor (executing processes belonging
`to a program) has
`failed,
`for example,
`is important
`to the program
`if it is to recover
`from such
`failures.
`In one study of program development
`function.
`is thus an essential
`Monitoring
`tools
`[31], a quarter of these tools were highly dependent on monitoring
`infor-
`mation,
`including
`those under
`the categories of tracing,
`tuning,
`timing,
`and
`resource allocation.
`are useful. A subject system is the software system being
`A few definitions
`the operating system or a user program. A sensor is a section
`monitored, usually
`of code within
`the subject system, which
`transfers
`to the monitor
`information
`concerning an event or state within
`the system.
`If the sensor is traced, then a
`data packet
`is transferred
`to the monitor each time a particular
`event occurs. If
`the sensor is sampled, then a data packet
`is transferred each time the monitor
`requests the sensor to do so. This data packet may be as simple as a bit that
`is
`complemented when the event occurs, or as complex as a long record containing
`the contents of system queues. The removal of irrelevant
`data packets before
`they are completely processed is termed filtering.
`Implicit
`in most discussions on monitoring
`is an eight-step sequential process:
`
`each sensor will record and where
`
`Step 1: Sensor Configuration
`This step involves deciding what information
`the sensor will be located.
`Step 2: Sensor Installation
`in the subject system.
`Sensors must be coded and placed in the correct location
`Provision must be made for temporary and permanent storage of the collected
`data.
`Step 3: Enabling Sensors
`data whenever
`enabled, storing monitoring
`Some sensors are permanently
`executed, while others may be individually
`or collectively
`enabled, usually by
`directives
`from the user.
`Step 4: Data Generation
`is executed, and the collected data are stored on disk or
`The subject program
`magnetic
`tape. Generally
`the user has little control of the monitoring
`at this
`point.
`Step 5: Analysis Specification
`In most systems the user is given a menu of supported analyses; sometimes a
`simple command
`language
`is available.
`ACM Transactions
`
`on Computer Systems, Vol. 6, No. 2, May 1966.
`
`Oracle Exhibit 1012, page 3
`
`

`

`160
`
`l
`
`Richard Snodgrass
`
`Step 6: Display Specification
`is available, or the user is given a menu of
`format
`Either only one display
`formats,
`ranging
`from a list of data packets printed
`in a readable
`form
`to
`canned reports
`to simple graphics
`(graphs or histograms).
`Step 7: Data Analysis
`Data analysis usually occurs
`collected.
`Step 8: Display Generation
`after data analysis, although
`immediately
`Usually
`this step occurs
`packages allow
`the analyzed data to be displayed at a later time.
`
`in batch mode long after
`
`the data have been
`
`a few
`
`in
`listed,
`the sequence of phases just
`follow
`systems
`While most monitoring
`the precise order given (e.g., [43,48,70]),
`there is a variety of alternative orderings
`within each phase. Many systems do not differentiate
`between sensor configu-
`ration and sensor installation.
`In some systems, sensors are always enabled, so
`that
`the enabling sensors step occurs
`in the second step when
`the sensors are
`installed
`(e.g., [7, 741). Some systems support only one display
`format, effectively
`combining
`the analysis and display specification
`steps (e.g., [21, 44, 711); other
`systems allow
`the display
`to be specified after the data have been analyzed
`(e.g.,
`[12, 14,341). In some systems, users are even required
`to write
`their own analysis
`and display code (e.g., [42, 48, 491).
`strategy
`of a complex system, an initial
`When considering
`the monitoring
`would extend each step in obvious ways. Such an approach
`is problematic
`at
`every step, due to the logical and physical distribution
`of the monitor and the
`subject program(s).
`Instead, we advocate a more comprehensive examination
`of
`the basic function
`of a monitor.
`In an abstract sense, monitoring
`is concerned
`with
`retrieving
`information
`and presenting
`this information
`in a derived
`form to
`the user. Hence, the monitor
`is fundamentally
`an information
`processing agent,
`with
`the
`information
`describing
`time-varying
`relationships
`between entities
`involved
`in the computation.
`A great deal of research has considered effective ways to process information.
`One of the results of this research has been the relational model [ 111. Conventional
`databases are static,
`in that
`they represent
`the state of an enterprise at a single
`moment of time. Although
`their contents continue
`to change as new information
`is added, these changes are viewed as modifications
`to the state, with
`the old,
`out-of-date
`data being deleted
`from
`the database. The current contents of the
`database may be viewed as a snapshot of the enterprise at a particular moment
`of time.
`there must be a means
`to monitoring,
`databases to be relevant
`For relational
`of recording
`facts that are (were) true only
`for a certain period of time.
`In the
`database area, attention
`has recently been focused on precisely
`this
`issue [65].
`Three
`types of databases have emerged that encode the notion of time: rollback
`databases, which
`record
`the history of database activities;
`historical databases,
`which
`record
`the history
`of the
`real world; and
`temporal databases, which
`incorporate both aspects [67]. The historical
`database
`is the most appropriate
`model of the dynamic state of computation. Historical
`databases require more
`sophisticated
`query
`languages
`than conventional
`databases; TQuel
`(Temporal
`QUEry Language)
`is one that supports historical queries [66]. Examples of TQuel
`ACM Transactions
`on Computer Systems, Vol. 6, No. 2, May 1988.
`
`Oracle Exhibit 1012, page 4
`
`

`

`A Relational Approach
`
`to Monitoring Complex Systems
`
`-
`
`161
`
`in a later section, after a new approach
`
`to monitoring
`
`is
`
`queries will be given
`presented.
`thesis of this paper is that historical databases are an appropriate
`The central
`of the information
`processed by the monitor. The primary benefits
`formalization
`include a simple, consistent
`structure
`for the information,
`the use of powerful
`declarative query languages, and the availability
`of a catalog of optimizations
`to
`be used when interpreting
`queries expressed in these languages. In this approach,
`the user is presented with
`the conceptual view that
`the dynamic behavior of the
`monitored system is available as a collection of historical
`relations, each associ-
`ated with a sensor in the subject system.
`In making historical
`queries on this
`conceptual database, the user is in fact specifying
`in a nonprocedural
`fashion
`the
`sensors to be enabled,
`the analysis
`to be carried out, and even the graphical
`presentation
`of the derived data.
`in a
`the data as relations
`represent
`to actually
`Note that we are not proposing
`database. Instead, we will show that a historical database provides a convenient
`and powerful
`fiction
`that guides
`the processing but does not constrain
`the
`representation.
`In fact, in most cases the relations will never actually collectively
`exist as data stored either
`in main memory or on secondary storage.
`Such an approach changes the ordering and the character of the traditional
`monitoring
`steps described earlier:
`
`Step 1: Sensor Configuration
`of the data
`is a specification
`This step is still performed by the user: the result
`each sensor
`to be collected and the placement of the sensors. Conceptually,
`declared
`in this manner defines a historical
`relation available
`for later use in
`defining other, derived relations. The relations directly associated with sensors
`are termed primitive
`relations, as contrasted with derived relations, which are
`not associated directly with sensors. The specification of the primitive
`relations
`identify
`the information
`available
`to the monitor.
`Step 2: Sensor Installation
`from
`the sensor is produced by the monitor
`This step occurs automatically:
`to the
`the specifications. Relevant aspects of the sensor are communicated
`components of the monitor
`that need to know
`this
`information.
`The sensor
`code handles all the necessary interaction with
`the monitor,
`including enabling
`and buffering, and may be customized
`to the task it is to accomplish and the
`environment
`in which
`it is to execute. Here we replace a manual step with an
`automatic one.
`Step 3: Analysis Specification
`In this step, the user provides one or more historical
`primitive
`relations specified above.
`Step 4: Display Specification
`specification.
`with analysis
`This
`step occurs concurrently
`entities and relationships with graphical
`icons, sophisticated
`dynamic behavior can be generated by the monitor.
`Step 5: Execution
`the data, analyzing
`the sensors, generating
`of enabling
`This step-comprised
`once the queries
`the data, and displaying
`the results-occurs
`automatically
`ACM Transactions
`on Computer Systems, Vol. 6, No. 2, May 1988.
`
`By associating
`illustrations
`of
`
`queries, defined on the
`
`Oracle Exhibit 1012, page 5
`
`

`

`162
`
`-
`
`Richard Snodgrass
`
`Sensor Configuration
`
`(m)
`
`t Sensor Condguration
`
`(m)
`
`Sensor Installation
`
`(m)
`
`+
`
`Sensor Installation
`
`Enabling Sensors (m)
`
`Data Generation
`
`Analysis Specification
`
`(m)
`
`Analysis Specitlcation
`
`(m)
`
`Display Specification
`
`(m)
`
`Display Specification
`
`(m)
`
`Data Analysis
`
`Information Display
`
`%
`
`Execution
`
`Fig. 1. Steps of the new approach to monitoring.
`
`first analyzes the query to determine precisely
`have been specified. The monitor
`the sensors that must be enabled to collect
`the requisite
`low-level
`information
`needed to satisfy
`the query, thereby guaranteeing
`that extraneous
`information
`is not collected. All the techniques previously developed
`for data collection are
`applicable. The monitor can also perform optimizations
`on the query, mapping
`it into a different query with an identical semantics but improved performance.
`Display generation can also be made more efficient by capitalizing
`on the fact
`that only a small portion of the state changes during each transition
`and by
`utilizing
`incremental
`display algorithms. Four traditional
`steps, including one
`that was previously a manual one (enabling
`the sensors) are replaced with
`this
`single automatic step.
`
`in Figure 1. The
`the new approach
`is compared with
`approach
`The traditional
`major change
`is that
`the sensors are enabled and the data generated after the
`analysis specification
`step, allowing
`the sensors to be enabled automatically
`based
`on information
`from the query. A second change is that some aspects of sensor
`installation
`are automated.
`“(m)”
`indicates
`the step is a manual one.
`As with
`the traditional
`approach, variations
`are possible.
`If dynamic sensor
`installation
`is supported
`(say, through
`the use of breakpoints),
`this step might
`be delayed until
`the execution step. By storing one or more relations
`in secondary
`storage, additional
`iterations
`of the analysis specification
`and execution
`steps
`(without
`the enabling and data-generation
`portions) are possible. Finally, defaults
`supported by the monitor may delay some aspects of some of the steps (e.g.,
`display specification),
`until
`the execution
`step when
`they can be performed
`automatically.
`in more detail. Section 3
`this new approach
`The next six sections discuss
`examines how sensors may be configured by the user. An example, used through-
`out the remainder of the paper, is introduced
`in Section 4. Section 5 deals briefly
`with how the sensor configuration
`information
`is used by the monitor
`to install
`the sensors. Section 6 introduces TQuel,
`the query language used to specify
`the
`monitoring
`actions, and Section 7 shows how
`the display can be specified.
`The monitoring
`actions of analyzing
`the query, generating
`the low-level data,
`performing
`the analysis, and displaying
`the data are discussed in Section 8.
`
`ACM Transactions
`
`on Computer Systems, Vol. 6, No. 2, May 1988.
`
`Oracle Exhibit 1012, page 6
`
`

`

`A Relational Approach
`
`to Monitoring Complex Systems
`
`-
`
`163
`
`STEP
`3. THE SENSOR CONFIGURATION
`the data to be collected and the
`During sensor configuration,
`the user specifies
`placement of the sensors. Our approach
`is to provide a simple
`language
`for
`describing
`the information
`to be collected by each sensor, and to allow
`the user
`to indicate where
`the sensor
`is to reside. Once such a specification
`has been
`processed by the monitor,
`the code for the sensors will be available
`to be included
`in the subject program,
`the mechanisms will have been set up to get the data
`packets to the monitor, and the query processing component will know about the
`primitive
`relations associated with
`the sensors defined
`in the specification. As
`with other aspects of the relational
`approach, complexity
`has been managed by
`requiring
`the user to provide a nonprocedural
`description of what is to be done,
`leaving
`the issue of how this
`task is to be done to the monitor, while ensuring
`that the monitor has sufficient
`information
`to make this determination.
`the
`To discuss what aspects are specified
`for each sensor, we need to examine
`as a
`environment
`in which
`the sensors operate. We model
`this environment
`collection
`of typed entities, both passive
`(i.e., data structures,
`such as ready
`queues and semaphores) and active
`(e.g., processes). Entities
`have identifiers,
`which are system-dependent
`names. For instance,
`in UNIX2
`[57], processes are
`indicated with process-ids, and files by pairs of device number and inode index;
`in StarOS
`[32] entities are named using capabilities;
`and in Medusa
`[53], by
`descriptor-list/offset
`pairs. Instances of entity
`types are displayed
`to the user as
`character strings; we assume that
`the operating system supports
`the mapping
`between user-oriented
`character
`strings and
`internal
`entity
`identifiers.
`The
`internal entity
`identifiers
`are assumed to be unique across space and time; this
`assumption can be relaxed at the expense of some additional
`complexity
`in the
`monitor
`[63]. Finally, we assume that
`the monitor can locate an entity given its
`identifier.
`type(s)
`to entities of the
`to be applied
`Type managers export operations
`supported by the manager; all operations on an entity are performed by the type
`manager
`through well-defined
`interfaces,
`implying
`the existence of a type-
`checking mechanism. This model thus
`identifies
`the operation being performed
`on the target by the performer
`(the type manager) as a result of a request by an
`initiator
`(any process). Each sensor is placed in a type manager and is associated
`with an operation
`(or a set of operations) provided by the type man’ager. For
`example,
`the file system (a type manager
`for the file entity
`type) may have a
`ReadFile sensor located in the code performing
`the read operation. Other sensors,
`such as OpenFile, PhysicalBlockRead,
`and ModifyProtection,
`may also be present
`in the file system. Each sensor is associated with a unique
`integer,
`the sensor
`identifier, which
`is combined with
`the collected
`information
`in the data packet
`sent by the sensor to the monitor. The model applies to all levels of granularity;
`in particular,
`a type manager and its sensors may be implemented
`in hardware,
`firmware, or software.
`In some systems (e.g., StarOS, Medusa),
`type managers
`are localized
`in one or a few system processes;
`in other, non-object-oriented
`operating systems (e.g., UNIX),
`each type manager is the entire kernel, although
`each type (e.g., file, process) is managed by a fairly small portion of the kernel.
`
`* UNIX
`
`is a registered
`
`trademark
`
`of AT&T Bell Laboratories.
`
`ACM Transactions
`
`on Computer Systems, Vol. 6, No. 2, May 1988.
`
`Oracle Exhibit 1012, page 7
`
`

`

`164
`
`-
`
`Richard Snodgrass
`
`flag
`Sensors may be enabled by setting an enable flag. The placement of this
`allows flexibility
`in the enabling of events. Enable
`flags associated with a passive
`entity, such as a file, arbitrate
`the collection of monitoring
`information
`for that
`entity. Setting
`the block write event flag associated with a particular
`file causes
`information
`to be collected
`for file block writes only for this file by any file system
`process. On the other hand, setting
`the file block write enable
`flag associated
`with a particular
`file system process (a type manager
`for file objects) causes
`information
`to be collected
`for file block writes on any file performed only by this
`file system process. The placement
`of the
`flags allows
`filtering
`along
`three
`dimensions: by target, performer, or initiator. The placement of the sensor allows
`filtering along the fourth dimension:
`the operation. Each sensor supports
`filtering
`in two of these dimensions:
`the operation and one other dimension. However,
`several sensors can be associated with an operation, each designating a different
`flag
`(with different
`filtering
`characteristics)
`to enable
`the sensor. The
`first
`example
`is filtered on the block write operation and target
`file;
`the second is
`filtered on the block write operation and the performer
`file system process.
`Higher degrees of filtering
`are also possible. An event may be enabled on a
`combination
`of three of the components of the operation, such as a block write
`operation by this file system on this file. Filtering
`on all four aspects represents
`total control over which event records get generated: a block write operation by
`this
`file system process on this
`file, as requested by this
`initiator.
`Achieving
`higher degrees of filtering
`requires additional
`information
`to be stored and
`additional processing
`to determine
`if the event is indeed enabled. This extension
`requires greater than linear space and/or
`time in the number of entities, and thus
`is expensive
`in an environment
`supporting many entities.
`enable
`if multiple
`The enable
`flag can be generalized
`to an integer counter
`requests are made by the monitor before the sensor executes. In this case, enabling
`involves
`incrementing
`the counter, and disabling
`involves decrementing
`the
`counter.
`is
`the operation
`the assumption was made that
`In the preceding discussion,
`the
`sensed and the information
`communicated
`to the rest of the monitor when
`operation occurs. Such data packets are called
`traced data packets, since their
`generation
`is synchronous with
`the operation, and thus with
`the operation whose
`target, performer, and initiator
`is named in the data packet.
`Sampled data packets, on the other hand, are generated at the request of the
`monitor, asynchronously with
`the operation. As an example, a sensor located
`in
`the scheduler of an operating system could generate traced data packets pertain-
`ing to context switching: process x started
`running at time
`tl, process y started
`running at time
`tz, etc. Another sensor located
`in the scheduler could generate
`sampled data packets at the request of the monitor: process z is now running. A
`sampled sensor will usually, but not necessarily,
`clear
`the enable
`flag after
`generating
`the data packet, thereby causing only one data packet to be generated
`per request of the monitor. Multiple
`requests could be handled as before with a
`multiple bit enable flag.
`time stamps from a global clock
`The data packets generated by sensors contain
`maintained across the entire system. Unfortunately,
`it is theoretically
`impossible
`to synchronize
`imprecise physical clocks over a geographically
`distributed
`net-
`ACM Transactions
`on Computer Systems, Vol. 6, No. 2, May 1988.
`
`Oracle Exhibit 1012, page 8
`
`

`

`A Relational Approa’ch to Monitoring Complex Systems
`
`.
`
`165
`
`transmission times [36]. However, Lamport gives an
`work with nondeterministic
`algorithm for maintaining a global clock with a bounded imprecision that main-
`tains the invariant
`that messages are received at a global time that is later than
`the global time the message was sent. The partial ordering of local events
`necessary for debugging will be preserved and the (unknown)
`total ordering will
`embed this partial ordering. This time-keeping algorithm can be implemented in
`the operating system itself, with
`time stamps appended to every message. A
`second option is to simulate Lamport’s algorithm in the monitor. This approach
`incurs a greater overhead than Lamport’s algorithm itself, due to the additional
`communication necessary. Another consideration is that if the operating system
`provides a reliable communication mechanism, supporting recovery from lost
`messages or crashed processors, then a global clock is probably already computed
`by this mechanism (e.g., [6]; all reliable communication mechanisms known to
`the author use some kind of global clock). In any case, if a global clock is provided
`by the monitor, other components of the operating system may profit from its
`presence. Given these considerations, we will assume that a global clock is
`implemented by a distributed algorithm and available to each processor. If such
`a clock is not feasible due to efficiency constraints, as in some real-time systems,
`then more sophisticated approaches, yet to be developed, are necessary.
`Each primitive relation is defined by giving it a name, listing its attributes and
`their types, identifying
`the target type (the performer and the initiator both have
`the process entity type), selecting either sampling or tracing, and specifying any
`additional desired characteristics such as a multiple bit enable flag. Each such
`specification is only a few lines long, allowing many sensors to be defined for a
`subject system with little effort. Such flexibility
`relies on three additional char-
`acteristics of the approach: The monitor must be able to generate the code for
`the sensor automatically,
`the sensors must be very efficient when disabled, and
`the monitor must be able to enable only the particular sensors required by the
`analysis. The first aspect will be discussed in Section 5; future sections will
`examine how enabling is handled and how efficient the sensors are, both when
`disabled and when generating data packets.
`in the
`A simplified version of this data collection model was implemented
`Clouds operating system [13]. One important difference is that Clouds objects
`can contain code, and hence sensors, whereas our model encapsulates the code
`for an object type in its type manager. A second difference is that only filtering
`on the target object is supported.
`in the 4.2BSD UNIX and DEMOS/MP
`Another model was implemented
`operating systems [48, 491. By requiring
`that no a priori knowledge of the
`computation be applied when specifying the sensors, the available event types
`were reduced to 10 “meter events.” Filtering occurs at two points. Individual
`meter events could be disabled (i.e., filtering along the single dimension of event
`type), or the data packets could be generated and later discarded by a separate
`process on the basis of patterns supplied by the user. The filtering performed
`during data collection is thus simplistic; that performed during analysis is more
`general.
`relations are similar to implicit
`Finally, primitive
`relations defined by applying
`operators to arbitrary data structures within a programming environment
`[ 281.
`ACM Transactions
`on Computer Systems, Vol. 6, No. 2, May 1988.
`
`Oracle Exhibit 1012, page 9
`
`

`

`166
`
`l
`
`Richard Snodgrass
`
`4. AN EXAMPLE
`and subsequent steps
`In order to make the actions of the sensor configuration
`more concrete, we introduce an example subject system (an operating system)
`and discuss some sensors that might be defined
`in this system. Since the user is
`encouraged
`to think of sensors as defining historical primitive
`relations, we will
`employ
`the entity-relationship
`model
`[lo]
`to describe
`the sensors. In practice,
`the user employs a sensor-description
`language to specify these primitive
`relations
`[63]. As the syntax of the sensor-description
`language
`is not critical,
`the sensors
`will be specified
`informally,
`rather
`than
`in that
`language. Although
`the entity-
`relationship model can also be used to describe
`the data collected by hardware
`monitors, we will not discuss this possibility
`further.
`to
`In this example,
`there are three
`types of operating system entities known
`the monitor: Processor, Process, and Mailbox. We also assume that
`there are
`several processors, which execute the processes and which share main memory.
`At any point
`in time, a process may be executing on only one processor,
`though
`a process can execute on more than one processor over its lifetime. A process
`may send messages to a mail