UED: The Unified Execution Diagram

Introduction

Modern professional software applications are often multi-threaded applications with multiple processes that are distributed over multiple PCs. For these complex systems it is important that the execution architecture is well designed and properly documented. Well-designed means that there are no problems with respect to deadlocks, race conditions, context switches, thread starvation etc. In practice we often experience problems in the execution architecture and the quality of the documentation describing it is often insufficient.

This article describes a modeling technique for making diagrams of the execution architecture. The diagram is called a Unified Execution Diagram (UED). The UED shows the threads, processes, PC deployment, inter process communication, reentrant code, queues, blocking functions etc. These diagrams can be used on architectural level as well as on implementation level. To ease the creation of new UEDs we have made a MS Visio stencil available (click here to download the Visio stencil) (Pascal T. Wolkotte and Carlo van Asma, 2011) that contains all symbols that can be used in a UED. Visio turned out to be a very suitable tool for this work especially because of the auto routing and line crossing support. Like UML, a UED is very suitable to model hybrid systems that consists of hardware and software modules.

This new modelling technique has been developed because visualizing concurrency in, for example UML, does not offer a satisfying solution. Many software engineers confirmed this and because of this reason the UED has been quickly adopted in many design teams within Philips Healthcare. For example, a sequence diagram is often used to depict a specific use-case, where occasionally limitted thread interaction is included. Other shortcomming of UML with respect to a UED will become clear when reading the rest of the document. The UED depicts the interaction between all threads in a single diagram. A UED can depict all information that is relevant for an execution architecture.

In the remaining part of the article we describe the background and motivation of using UEDs within Philips Healthcare. The definitions of the UED itself are described in the section Unified Execution Diagrams. At the end of the article we present an example.

Background

The UED has been developed within the interventional XRay department (iXR) of Philips Healthcare, where it is used to design and document the execution architecture of our professional Philips (XRay) healthcare applications. It is crucial for these systems that they have a very good performance and are extremely reliable. A typical healthcare application is divided in several subsystems and each subsystem is divided in units. The UEDs supports hierarchy which is crucial to design the execution architecture of such complex systems.

Within Healthcare the UED has already proven to be very useful for designing and documenting the execution architecture. In our largest software project we used a process where a UED is created for every component. The UED shows the execution architecture of the component and the context similar to the example given in this article.

Unified Execution Diagrams

The basis of a UED is called a graph called Unified Execution Graph (UEG). The UED is in fact the visualization of this graph. An example of such a UED is shown in Figure 1. Later in this article this example will be explained in more detail. The execution architecture is represented as a graph. In practice you will directly create a UED using the symbols of the UED. The concept of a graph is useful to refer to standard graph terminology such as a root node, leaf node and a cycle in a graph. Furthermore, in a later stage the graph can be used for analysis purposes to identify potential threading problems like dead locks. In the next section the basic symbols are described that are used in the UED. After the introduction of all basic symbols, the UED is described in Visualization section and an example of a UED is described at the end of this article.

(Click on the image to enlarge it)

Figure 1 Example of an UED

Unified Execution Graph

A UEG is a directed graph that consists of a set of nodes and edges. The UEG describes all concurrent execution paths (started by threads, events, etc.) and their interaction. For each graph element additional information can be added which are called annotations. Examples of these annotations are the node type, the edge type, a module, a thread context. These are discussed in the next sections.

Node Types

There are different types of nodes that are grouped into four groups. The first group of nodes contains the function nodes. A function node represents a group of functions, which can be implemented by both software and hardware. A function group is a non-empty set of functions. The intersection between two function groups is always empty. This means each function is part of exactly one function group. Currently, we have defined the following function nodes:

A UED distinguishes two different types of function groups which are: the non-blocking function group and a blocking function group. Before explaining the difference between these function groups, a definition is given of a blocking function.

Definition: A function is blocking if the function waits for a synchronization object (such as a semaphore or mutex) or a condition that may prevent the thread from further execution until another thread has signaled or released that synchronization object or has set the condition.

A blocking function group shall be used if the function group contains a blocking function otherwise the non-blocking function group shall be used. A blocking function group potentially may cause a deadlock which cannot occur in case of a non-blocking function group. For a deadlock free design, one must be able to proof for each blocking function group that no deadlock can occur.

The second group is the set of initiation nodes. Examples of initiation nodes are a process, thread, a timer, or event (e.g. an interrupt or a UI event). An initiation node is the start of an execution path within the application. The initiation nodes always execute a function of a function node. In the UED we can use the following initiation nodes:

The third group contains all the resource nodes, which represent resource instances that are used by one or more function nodes. A resource node is used for thread synchronization and store of data. Examples of resource instances are a queue, (shared) memory, a mutex, monitor, and semaphore. We can represent these nodes by the following symbols in the UED:

The last node type is an interface node, which represents the interface of a module. Interface nodes enable the designer to make a UED that shows only parts of the graph. Instead of the real module’s implementation, only the (external) interfaces of a module are shown. In the UED the interface nodes are represented by the following symbols:

An input interface is blocking if the corresponding function group is blocking or (indirectly) calls another blocking function group. The general interface is used when (non-)blocking is not applicable, for example HW interface or output interface.

Edge Types

The nodes of the UEG are connected by edges. There are two types of edges. Call edges are used to show the execution flow (e.g. a function call from one function group to another). The direction of the call edge represents the execution flow. Access edges are used to show the communication with resource nodes. The direction of the access edge represents the flow of information. In the UED we use the following lines to represent the two edge types:

A thick line of an edge indicates that there are multiple concurrent executions of a function or accesses to a resource.

Execution Context

Every edge has an execution context that specifies which initiation node performs the execution. In this article each execution context is indicated by a different line color as shown in the example of Figure 2. The non-blocking function group f is called by a thread t1 and a timer t2. The function group f calls the blocking function group g. The execution context of a call to g is {t1, t2}, which means that g can be executed from either context t1 or t2. Using different colors for the different threads makes it easy to identify multi-threaded code.

Figure 2 Execution context

Modules

A module is a collection of nodes in the UEG. An example of a module is a PC, a component, a class instance. For the name of a module we use the following format: name:<type><[count]>, where name is the instance name, type is the type of the component and count indicates the number of instances. The modules are visualized by the following symbols:

For a module in a UED you can either show only the module’s external interfaces or the interface together with the internal implementation. Furthermore, a dashed line indicates that only a part of module’s interface or implementation is shown. A complete implementation module shows the module’s complete implementation. In a partial implementation some parts of the implementation may omitted from the UED, such that not its full implementation is shown. A complete interface module has to show all the module’s external interfaces, which can be represented by both interface nodes and child interface modules. In a partial interface module not all external interfaces are shown

Figure 3 Module composition (a) and aggregation (b)

A module in a UED can contain another module. Figure 3a shows this com-position relation where a module calls a function group of an internal module. Figure 3b shows the aggregation relation where a module calls a function group of another external module.

Composed Nodes

For some generic modules we have defined a set of composed nodes that simplify the UED. For deferred procedure calls we have the DPC node (or event loop), which has two inputs (synchronous and asynchronous). The synchronous input blocks until the deferred procedure call is executed by the thread connected to the DPC. The asynchronous input is non-blocking. Figure 4 shows the symbol for a DPC node and the decomposition of this node in terms of the primitive nodes.

Figure 4 DPC symbol, decomposition of DPC

For remote procedure calls we split the DPC node in a proxy and stub node to create two RPC nodes that are interconnected by a channel.

Channels

For communication between two modules it is possible to draw a (duplex) channel. This simplifies the UED but also shows their client server relation. There are different symbols used for channels that stay within a process and channels that cross a process boundary. For the latter composed RPC nodes are used. The fill color of the node indicates the direction of a communication (grey towards the server, white towards the client).

On interface modules we do not want to draw the full details of simplex and duplex channels. For that we use the symbols on the right side.

These symbols are attached to an interface module’s border, such that it is clear that the module implements either the stub or proxy interface for a particular channel.

Visualization

A UED is the visualization of a UEG. A UED shows all aspects that are important for the execution architecture such as: process deployment, inter process communication channels, threads, queues, and blocking functions. The creator of the diagram decides which level of detail the diagram reveals. The aim of a UED is to show the complete execution architecture of a sub-system or module in a single diagram.

From architectural point of view a system can be divided into smaller sub-modules (components). A strong feature of the UED is that you can make separate UEDs of the top-level and each sub-module. The top level diagram typically shows only the sub-modules’ interfaces, their interaction, and PC deployment. The UED for a sub module shows all relevant threading aspects for that sub-module within a particular scope. Due to this property, a UED is called an aspect oriented visualization technique.

Another strong feature of the UED is the support for multiple instances. A thick line of a node, edge or module indicates multiple instances of that element. In the UED only the module for one instance is shown which keeps the diagrams compact. The aim of a UED is to show the complete execution architecture of a sub system or module in only one diagram.

Linked elements

For convenience there also exists a so-called element link. This is a line that connects two or more distributed parts of the same element in the UED. This gives you more freedom in drawing the diagrams. See for example the WCF communication channels in the example given in the Example of a UED section. Furthermore, it is used to associate different modules as described in the Multiplicity section.

Coloring

The use of colors is very powerful in a UED as it enables the creator to visualize annotations of the UEG. In the UED we restrict the coloring and line-style of particular elements in the UED, such that a uniform meaning emerges across all UEDs. The fill color of modules is free to choose by the creator of the UED. In the UED examples given in this article line colors are used as follows. When edges connected to the same node have different colors, they represent different execution contexts. A function that is multithreaded can easily be identified. A function group is multithreaded in case it has call edges with different colors or in case the call edge is bold representing multiple calls from different threads. A thread, or other initiation node, has the same line color as the edges that correspond with that execution context. The use of colors is not mandatory. An alternative way to specify a thread context is by specifying the thread context name as shown in Figure 2. All other nodes will have black colored lines.

Multiplicity

For every UED module and node it is possible to indicate that there are multiple instances of the element by drawing the symbol with an outer thick line. The number of instances of the module or node is indicated between rectangular brackets (e.g. X[2] means two instances of the module X).

Figure 5 Example with multiple instances

Figure 4 shows a situation where two modules (X and Y) are both instantiated twice. On the left side a fully expanded UED is shown and on the right side a collapsed diagram, which has the identical meaning. The element link indicates that one instance of X is associated with one instance of module Y. Without this explicit association the meaning of the edge between X and Y is that every instance of X calls every instance of Y.

Example of a UED

To illustrate the use of a UED we use the well-known “dining philosophers” problem (Hoare, 1985) to present a UED example. The problem is famous because a wrong implementation can easily result in a dead lock or race condition. In this article eight philosophers are sitting at a circular table. Each philosopher can do one of two things: eating and thinking. While eating they are not thinking and vice versa. To eat they require two forks. A fork is shared between each pair of adjacent philosophers. A philosopher may only use the fork to his left and to his right. Finally, philosophers are not allowed to speak.

Figure 6 Dining Philosophers Example

In order to demonstrate how deployment can be visualized in a UED, we have extended the dining philosophers problem by dividing the table in four quadrants. Each table quadrant has two seats for a philosopher, and two forks. In our implementation of the dining philosopher problem, a philosopher is hosted in the Seat process and the forks are hosted in the Cutlery process. Furthermore, the processes for each table quadrant run on a different PC. For communication between a Philosopher and a Fork two simplex WCF channel are used. The top level UED for this example is shown in Figure 6. This diagram shows that there are four PCs. On each PC there are two Seat processes running and one Cutlery process. A Cutlery process contains of two fork components and a seat process contains one Philosopher component. The right fork for one of the philosophers is located on a different PC therefor the inter process communication is routed outside the PC module.

Figure 7 UED top level

In general, in a top level diagram only module interfaces are shown. Figure 7 shows three possible implementations of the execution architecture for the Philosopher component. First we will show the UED can be used to explain the different implementations and compare the different designs. It can be noticed that the diagrams show the complete context of the execution architecture as far it is relevant for this component. The fork module used dashed lines to indicate that they only show the execution architecture partially.

(Click on the image to enlarge it)

Figure 8 a) asynchronous interface, b) asynchronous interface and DPC, c) synchronous interface

Each diagram shows that there are eight Seat processes, each one hosting one Philosopher and four Cutlery process, each hosting two forks. The diagram shows that each philosopher has an interface with two Fork modules.

First it will be shown that the execution architecture can easily be explained by means of the UED. The Philosopher is an active component and therefore has its own main thread. The algorithm for each Philosopher is described in its main function group. The Philosopher uses an internal timer to switch from the “thinking” state to the “eating” state and vice versa. In the “eating” state the Philosopher performs an access request via a inter process communication (e.g.WCF) to one Fork at a time. A Fork notifies the Philosopher when the Fork is available.

In the first implementation, the main thread blocks until it receives the signal forkAvailable. The function group inside the philosopher is blocking, because it is waiting on a signal. A well designed algorithm will guarantee that no deadlock occurs. For a deadlock free design, one must be proven that none of the blocking functions can cause a deadlock. Table 1shows all the triggers and the expected notifications. For each trigger it must be proven that the expected notification is always received. It can be proven that if the philosophers acquire the forks in a fixed order that the design is deadlock free. This condition is met when one philosopher starts with acquiring the left fork first while the other philosophers start with acquiring the right fork. This UED helps to identify which components contain blocking functions and potentially may cause a dead lock.

Table 1 Triggers and expected notifications

The second implementation does not use a signal but posts a message on the event loop when the notification is received that the fork is available. For the second implementation it must be guaranteed that no life lock can occur. Also in this case the UED can help to identify the places where a live lock may occur. For this we also need the UED of the Fork as shown in Figure 9. If you combine these two as shown in Figure 8 you can identify a cycle in the graph that contains asynchronous invocations. In this figure the RPC proxy and stub are merged as two DPCs which is from functional point of view identical. For each event loop that is part of a cycle in the graph it must be checked if the event loop generates a trigger for which it expects an (asynchronous) notification. The triggers and expected notifications for the main event loop are exactly the same as for the first implementation (see Table 1). Also the same solution is applicable which means the philosophers must acquire the forks in the same order. This example also shows that threading issues in general cannot be analyzed on module or component level but they must be analyzed on system level.

The third implementation uses a synchronous interface between the Philosopher and the Fork. This means the fork request call blocks until the fork is acquired. This implementation uses a simplex connection because there are no notifications.

Figure 9 a) Cycle in a UED b) further simplification

Although all three implementations can work, the second often is preferred because it there is no multi-threaded code and the design does not require the use of synchronization objects like the signal for forkAvailable.

Similar for the Fork component a UED can be made that shows the execution architecture for the fork. Figure 9 shows three possible implementations of the execution architecture for the fork. In the first implementation the forkStub receives the request for acquiring a fork. The receiving threads are drawn bold to indicate that multiple requests can be received simultaneously. The mutex is used to process the request sequentially. The code in this implementation is multithreaded because multiple threads entering the same function group. In the second implementation, the fork uses its own event loop. The forkStub posts the fork requests to this event loop. In this implementation all the code is single threaded because all code is running on the main thread t1. The first implementation is a multithreaded implementation like an MTA in COM and the second implementation is a single threaded implementation where each fork has its own event loop. The third implementation uses the synchronous interface between Philosopher and the Fork. The function group is blocking to indicate that the fork request blocks until the fork is required. In most cases the second architecture is preferred because in general this architecture is simpler and easier to design correctly.

(Click on the image to enlarge it)

Figure 10 a) asynchronous interface, b) asynchronous interface and DPC, c) synchronous interface

In a well-designed execution architecture it must be guaranteed that no buffer overflow can occur. Also here the UED can help to identify the places where this must be analyzed. Every place where an asynchronous call is made to a DPC (event loop), to an RPC stub or a proxy this may occur. The asynchronous call is the incoming arrow to the input without the cross of a DPC, RPC proxy or RPC stub. In case of the fork there are two philosophers sharing that same fork. The maximum number posted request or fork available notifications is two and hence no overflow can occur.

Another problem that may occur in an execution architecture is thread pool starvation. Also here the UED can help to identify the places where thread pool starvation may occur. For this design thread pool starvation may result in a dead lock. In case of the fork the receiving thread of the forkStub is bold indicating that multiple request can be received simultaneously. Thread pool starvation will not occur if the thread pool has two threads available per fork.

Special attention must be paid to the inter-process communication and communication between event loops because this can easily cause a dead lock. These dead locks can easily be avoided when all processes and the event loops in a process are strictly layered and the convention is applied that all up calls are asynchronous and down calls can be synchronous or asynchronous. This convention guarantees that the shared resources which are in this case the threads of the DPCs and RPC channels are locked in a fixed order and thus no dead lock can occur. The recommendation is to let the UED reflect the same layering so that you can easily check if the design adheres to this convention.

Conclusion

We presented a visual modeling technique in this article to describe and specify the application’s execution architecture. The diagrams are called Unified Execution Diagrams which make it easy to explain the design of the execution architecture. The UEDs were also very useful in identifying and solving threading issues like deadlocks.

The UEDs appeared to be very useful during design discussions, problem solving, or explaining the data and control flow for several use-cases to colleagues. Initially, we started to use them to describe the existing execution architecture. Currently, they are also being used as part of the design specification.

The UEDs help to keep the execution as simple as possible which resulted in a better quality of the product. The UEDs helps to realize simpler execution architecture and significantly reduced the number of threading issues we had such as deadlocks.

A properly made UED must show how many threads the design uses and which synchronization objects such as mutexes are used. It also shows how the software is deployed over PCs and processes. The UEDs show which components contain multithreaded code. During code review extra attention may be given to that code to identify and fix thread unsafe implementations. The UEDs show clearly which processes are communicating to each other via inter process communication. Finally it shows which components contain blocking functions which potentially may lead to deadlocks.

With UEDs the complete execution architecture can be documented. The visualization technique has clearly defined semantics and symbols.

Within Philips healthcare we used the UED for more than five years now. We have modeled the execution architecture of many designs and so far we have been able to model the execution architecture of all of them. We are confident that the set of UED symbols is complete to model any execution architecture. We wrote this article because we think many more people can benefit from the modeling technique and maybe at some day in the future UML will be extended with these symbols so that we can create all documentation models with a single tool.

About the Authors

Carlo van Asma is software architect at Philips Healthcare. He is enthusiastic, eager to learn and result driven. As tech-lead and architect he led several teams (up to 30 developers) successfully in achieving an excellent development. He enjoyed very much the two opportunities he got to realize a complete new software development completely from scratch. In his role as tech-lead and architect he had an important contribution in realizing a good architecture, design, build and test, setup of the archive, branch and release strategy. Carlo has strong focus on quality and always tries to improve the efficiency of a software development. His passion is the realization of an excellent software development. His hobbies are playing squash and piano.

Pascal Wolkotte is software architect at Philips Healthcare with a master’s degree in electrical engineering and a PhD in computer science. Pascal is curious, enthusiast and eager to learn. His passion is to combine the technical and human aspects in product development. This enables him to excel a team using his coaching leadership style. He continuously challenges himself by new projects, where contributes with a holistic system view and pragmatism. In his spare time he enjoys cycling, cooking, and photography.