Object-Oriented Flow Design
A new, simple unified approach
Barry is a member of the Computer and Communication Engineering Department at Edith Cowan University. He can be contacted at [email protected]
My article "TERSE: A Tiny Real-Time Operating System" (DDJ, December 1995) presented a simple dataflow kernel that delivered messages between code modules (nodes) and scheduled execution of the nodes. The example I used in the article was for the Intel 8051 microcontroller family, although it could be adapted to other microcontrollers with relative ease.
Of course, a simple dataflow scheduler may not justify being called an "operating system," especially if the scheduling sequence is static. However, TERSE employs a combination of compile-time and bounded-run-time scheduling, well suited to reactive systems. Additionally, TERSE delivers messages between processors in distributed systems. Since that article, I've made improvements to TERSE, including implementing a scheduling algorithm that supports interprocessor messaging. Other developers are working on TERSE ports, multiple TERSE virtual machines under OS/2, and a 68HC11-based TERSE for the controller-area network interface. Ultimately, TERSE provides an underlying vehicle for the implementation phase of a complete object-oriented dataflow methodology. The graphical notation for this methodology is called "GOOFEE."
Over the last 15 years or so, computer scientists have told us that any substantial problem must be decomposed into multiple views or diagrams, each with its own graphical or textual notation. The GOOFEE methodology is comparatively simple. GOOFEE notation uses a single graphical notation for every phase of design, and a single diagram for all phases. Within the domain of embedded systems, designs done with GOOFEE notation are more readable and easier to develop than others, including object-oriented techniques such as Booch and OMT.
Controlflow versus Dataflow OO
When you begin analyzing a problem, one starting point is to sketch flow or state diagrams to represent your ideas. If you are following the object-oriented approach, you sketch diagrams composed of objects (Booch clouds, for example). However, languages like C++ (and, by implication, Booch clouds) are inherently procedure oriented, or (to use the correct terminology) method and controlflow oriented, which is different from the dataflow approach.
The idea of the procedure-oriented object is that it encapsulates data and provides procedures/functions that other objects can call. A dataflow object, on the other hand, can still encapsulate data, with the dataflow being more correctly referred to as "messages." The synchronous dataflow model provides the facility of automatic synchronization of execution: When all messages have arrived, execution occurs. The node then performs internal data transformation, and messages are posted upon exit, causing the next appropriate node to fire. Apart from inherent synchronization, the dataflow model is superb for developing systems that require multiple threads of execution, including those over multiple processors.
In his book Object-Oriented Software Construction (Prentice Hall, 1989), Bertrand Meyer expresses an opposing point of view.
...the dataflow-directed methods...use the flow of information through a system as the primary structuring criterion. The order in which things happen to a piece of data is thus considered essential.
In contrast, object-oriented design adopts a more neutral attitude towards ordering: the designer lists the various operations that are applicable to a certain kind of data, and specifies the effect of each operation, but defers for as long as possible the specification of the order in which these operations may be applied.
GOOFEE lies between these extremes, so it tends to bring forward implementation details that a procedure-based OOD methodology may be able to defer. When it comes to embedded systems, there are pros and cons. However, if required, GOOFEE diagrams can be constrained to look like a procedure-based OOD methodology, at least at the higher levels.
The Hierarchical Methodologies
Figure 1 shows that, in accordance with conventional thinking, you need at least three views to adequately represent a design. For the OO paradigm, the messaging view equates to object diagrams, and the inheritance view equates to class diagrams. In other words, messages passed between objects are shown in one view, but the inheritance relationships are shown in another. Figure 1 is a simplification; you also need to think about data persistence and timing. Object and class diagrams don't show time relationships very well; this would require more views.
For instance, say module 19 in one of the object diagrams has an inheritance relationship with module 5 in another object diagram. Since they are separate diagrams, the only way the inheritance can be properly shown is by the inheritance view. The root cause of this separation of views is hierarchical decomposition. Specialized notations that are different for each view have been developed. Because each view is a partial picture of the total system, the number of notational elements for each view proliferate. GOOFEE notation abandons three-dimensional hierarchy, so that all design is in a two-dimensional plane. It uses a single unified notation in which a node can be a class, an object, a method, a state, or whatever, depending on the context in which it is drawn. In short, GOOFEE provides at-a-glance comprehension of how a system functions-at any level of detail-and immediate comprehension of relationships between any part of the system.
GOOFEE notation consists of 19 textual and graphical elements. As Figure 2 illustrates, however, even with a unified notation, messaging and inheritance relationships require different representation. Notice that the messaging (or dataflow) arcs are distinct from the I/O arcs. The latter are direct accesses by a node's internal code to/from a resource, which may be memory or hardware. I/O arcs have nothing to do with the operating-system message delivery and node scheduling: The arcs with solid arrows are handled by the OS. The notification arc is a special case, as it is delivered by the OS, but does not affect the execution scheduler; and it is allowed to queue (the others are not). The normal messaging arcs (straight lines, solid arrows) obey synchronous dataflow in that all input messages to a node must arrive before the node can fire, and they can only queue one-deep. When a node fires, it consumes all input messages (tokens).
Some of the nodes in Figure 2 are drawn as two rings. In fact, nodes can be any number of rings, and they are referred to as "iterative nodes:" They are a structured-programming mechanism for allowing local loops, or iterations, in a synchronous-dataflow model. To summarize how iterative nodes work, first entry is at the outer ring, as is final exit, but local iterations are an exit from any inner ring: Therefore, one ring will be active. If exit occurs from an inner ring, that node can only refire when all inputs to the active ring have arrived. The inheritance relationships are shown by what I call a "joining bar," which also shows whether mutual exclusion of execution of the joined nodes is to be enforced. The joining bar also has an option called "union," which means that the joined nodes are one and the same: This is how decomposition is achieved without three-dimensional hierarchy. It is only the internal code and data that is common (in union): The node itself, including ports (terminals), is different for each clone.
Figure 3 shows all of the required textual adornments. All other information is conveyed graphically, though, of course, comments can be placed anywhere. "Action" and "event" are optional, and can be aliases, such as short descriptions of what happens, while "name" can be just a node number. At the lowest level of decomposition, "action" and "event" would be actual actions and events.
Figure 4 shows various messages and inheritance relationships. (By the way, do not take Figure 4 as an example of good diagram construction.) Any node or composite node, without externally connected messaging arcs (not counting I/O arcs), is a class. Any node or composite node with externally connected message arcs is an object (instantiation). Inheritance of external connections occurs by implication. Node Z shows this. It is not a class (it has an external arc), but since it is a clone of Node C, it has the same ports. In fact, any external connections that are left off Node Z are inherited from Node C. Figure 4 shows that inheritance (and nonconcurrency) can be represented between anything in the diagram, and also represent decomposition. The naming of composite nodes as PU2 and PU3 is not intended to imply that a composite node equates to a processor unit, though it could. PU2B is a decomposition of PU2; PU3B is a decomposition of PU3; and 6B is a decomposition of Node 6. (One thing about this notation is that you don't need to worry about which things are objects and which things are classes, nor do you need to express direction of inheritance.) A composite node is not a node, only a logical grouping or subdiagram, but it can make use of the joining bar. Most importantly, arcs go straight through the boundary of the composite node without any scheduling repercussions. The composite node boundary does impose visibility limits on quasi-global data, however.
A Case Study
Figure 5 is a typical GOOFEE diagram-an elevator control system. I first drew the physical layout, showing where processors are located and to what resources they are connected. Next, I decided that each processor would equate to one composite node. A CASE tool could have the ability to represent the picture of the elevator as a background bit-mapped image, maybe grayed out, as a visual adornment. I made some early implementation decisions, as is often required in embedded systems. (My book Object-Oriented Flow Design for Embedded Systems, Karda Prints, 1996, includes a Windows-hosted visual diagrammer CASE tool. See http://www.icenet.com .au/~karda/ or http://www.swannet .com.au/ ~goofee/ for more details.) The composite nodes in each elevator are identical, so you can see the type of joining bar I have used; likewise for the composite nodes on each floor. However, each composite node has its own local configuration data, which is explicitly shown. Note that the default behavior for any resource/data connected to a node is that it is only visible to that node. This top-level view has shown all of the physical connections, and now the decomposition can proceed, on the two-dimensional plane, as Figure 6 shows.
For the sake of brevity, these figures do not have all possible textual adornments, nor is decomposition necessarily complete. For example, nodes A, B, C, and D are joined by an implied union/joining bar, and I have shown a union/joining bar going off to the right to indicate how further decomposition can proceed. The nodes A, B, C, and D show the technique I recommend for accessing all shared resources (even where nonconcurrency of the clients is obvious)-in this case, the motor/door control. You can reach the resource from various parts of the diagram through its own access node-what I call a "clone" node. This is described in my book; as is access to the local-button database. Thus, you can see exactly how and when a resource is being used, without needing another diagram or table.
The basic idea of the composite node PU4B in Figure 6 is that execution starts at the node labeled "Waiting" with a request for information from the local-button manager and from the supervisor processor, which has the button database for the floors. When a message comes back to go to a particular floor, the iterative node exits to either the Down or Up node, and what amounts to a finite-state machine (FSM) gets going-except that I chose to do it by structured-programming principles (composite node EE). Exiting from Down or Up gives control back to Waiting. Deciding which floor to stop at is a time-critical operation, as information in real time must be obtained from the supervisor as well as from the local database, so I decided to implement "current floor" as a quasi-global variable, accessed directly by I/O arcs. Note, however, that it is only visible inside the current composite node (or super node). The supervisor processor maintains separate Up and Down button databases: This simplifies the logistics of the system.
I decouple the inside-button press interrupt, via Node U, to clarify mutual exclusion to the database, though Node U could have been placed in the decomposition of Node T. Node T will require further decomposition, but as with all bottom-level decompositions, how you document them is up to you. You could do something like Node EE, pseudocode, or even direct code. A CASE tool will be expected to have a pop-up text editor for entering code into a node, or the tool could autogenerate code from a diagram. Figure 7 shows the decompositions of the other processors, though, again, some of the nodes could be further decomposed.
Node 1 has clones, in a union/nonconcurrency relationship, which also means that Node 1 is exactly the same, internally, as its clones. If a message arrives at Node 1 from the elevator processor (right elevator), requesting button information (the message will have status, such as current floor), Node 1 can access the database and respond with the next floor destination. Node 1's clones (Z and 4) can only execute when Node 1 isn't executing (specified by the joining bar), so there is no problem with multiple accesses to the database; likewise for the other clones S2 and S1. Node N controls the firing of Node Z and Node V, and the latter two will unload the queued button data and update the database whenever Nodes 1/2/4/5 aren't performing those tasks. In fact, the floor processors chug away sending notifications to the supervisor whenever a button is pressed. The notifications queue up at the supervisor until it executes its Node Z or Node V (or a clone) to consume them. Node Z and Node V (and clones) can also post messages to the floors to update the floor displays, passing information as they receive it from the elevator processors.
Finally, the Super-arc from PU1 to PU5 doesn't go to PU6 and the like, but it does, by inheritance implication. Messages out of PU1 are delivered to all the floor PUs. The reverse also is true.
Even though I short-circuited the decomposition process to keep the multiple-elevator case study within three diagrams, the example is clearly not trivial. Some nodes need further decomposition. Still, in just three diagrams I was able to describe the entire system and begin coding. The case study also shows how one notation and diagram contains every aspect of OOD, including dataflow, controlflow, timing, synchronization, classes and inheritance, objects and messaging, cardinality, resource handling, mutual exclusion, FSM, concurrency, multiple inheritance, exception handling, metaclass, and more. For comparison, you might like to study the multiple-elevator case study in Software Design Methods for Concurrent and Real-Time Systems, by Hassan Gomaa (Addison-Wesley, 1993) which uses CORBA for analysis and CODARTS/DA for design.
After you decompose to the lowest level, you can translate to code, which could be done manually, although I am working on a code-generation extension to my CASE tool. I am targeting programming in plain-vanilla C or assembly, as all OOP requirements can be expressed at the visual-diagram level. Implementation does not require TERSE underneath; however, the modified external set signature (MESS) scheduling, my latest technique used in TERSE, is a powerful tool for scheduling nodes, detecting error conditions, and performing timeouts. It is fully documented in my book. I invite your participation in the further development of both GOOFEE and TERSE. For details, see http://scorpion.cowan.edu.au/science/terse/terse.htm.
Figure 1: Conventional hierarchical decomposition.
Figure 2: Messaging and inheritance elements.
Figure 3: Textual adornments.
Figure 4: Example diagram.
Figure 5: Elevator control-system diagram.
Figure 6: Decomposition of an elevator composite node.
Figure 7: Further decomposition of elevator system.