An Approach to the Design of Software for Distributed Real-Time Systems
Andrew J.Vickers?and John A.McDermid
Department of Computer Science
University of York
Heslington
York
Y015DD
ABSTRACT
The design of distributed real-time systems is dif?cult because of the large number
of issues involved with their design—inter-process communication,module
structure,timing constraints,hardware constraints,reliability,etc.In this paper,we
show how such issues may usefully be partitioned through the use of viewpoints
before being combined together to provide an overall design solution.Our design
approach and notation is based upon a set of concepts which are analagous to the
construction industry’s notion of an architecture which acts as the central artefact
within the civil engineering design process.The approach is introduced by way of
a small case study which allows the reader to be exposed to the detail of the
notation as it becomes necessary within the development of the example design.
1.Introduction
Distributed real-time systems are becoming more and more widely used in applications such as power station monitoring systems,aeroplane control systems,etc.A distributed system typically contains logically separate multiple processing units that communicate by way of some underlying electronic network[1].Such units may be housed together or be physically separate and may or may not share memory.Distributed real-time software controls such systems and in doing so must satisfy many of the requirements of traditional data processing software.In addition such software must service the needs of its environment within well-de?ned timing deadlines(the penalties in terms of risk and safety to man and the environment are often severe if such deadlines are missed).This issue,and others like it(including reliability)are often termed non-functional and are prevalent in this type of software[2].
It is typically these kinds of requirement that make the successful design and implementation of real-time systems so dif?cult.These requirements are dif?cult to specify,dif?cult to validate against and dif?cult to satisfy in implementation.Perhaps however,the main dif?culty in realising distributed real-time systems is that the requirements are hard to design with;at least in part this is because the non-functional properties are emergent,rather than being properties which we can allocate or budget in some top-down design process[3].It is usually the case that such non-functional issues are dealt with late in the design process,i.e.during implementation[4,5]where they are often addressed through the use of‘tinkering’or‘optimisation’techniques.Whilst this works occasionally,it fails when the issue was ultimately decided by some previous design decision(for example,no amount of optimisation will increase system performance if some structural design decision was taken which introduced bottlenecks at all of the performance
?Andrew Vickers is funded by an SERC Studentship.
sensitive areas).The answer to this problem is to design with these issues in mind—have a design that incorporates all aspects of the solution[5].We must?nd ways of bringing some of these emergent properties explicitly into the design process.This is the underlying concept of an architecture.
Turning for the moment to a construction industry view of this problem,we note that the architecture of a building is devised by an Architect as a‘‘grand plan’’[6]of what is to be built —the architecture is the central artefact of the design process.Analysis of poorly understood requirements is still important,but it is not undertaken in isolation without the design being considered,at least to some extent.Requirements are expected to change as the problem becomes better understood and are themselves merged with statements concerning the solution[7].
In this way the Architect builds up an evolvable description of the solution to the problem—the design is progressively shaped as the requirements become clearer.Requirements issues which would only be relevant in terms of certain design decisions are delayed until those decisions have been made—for example,the detailed requirements for a?oor-to-?oor moving pathway would only be considered once the?oors themselves had been committed to in a design sense.The resultant architecture is then used as a workplan for the actual implementation as well as providing an‘assured yardstick’with which to measure the correctness of the building construction.In this way the architecture is able to act as the basis for contractual agreement between the customer and the developer.
This should be contrasted with conventional Software Engineering wisdom where the requirements speci?cation is usually what is agreed to—which is essentially what the developer thinks that the customer thinks is wanted.There is a difference in emphasis between the two industries:the importance of requirements in Software Engineering as opposed to architecture in Civil Engineering.
A major tenet of our work is that a similar philosophy needs to be,and can be,used in developing software systems,especially distributed real-time systems where what is required is heavily contingent upon what can be realised(such an approach acknowledges the realities and constraints of concurrent engineering).Within this context one can consider a computational architecture as having to serve two purposes:
1.It should include all of the information necessary to subsequently allow each part of the
system to be developed independently.
2.It should tell you everything you need to know to show that the requirements will be satis?ed
if and only if the components are implemented as speci?ed.
In order to allow for subsequent development,the notation used to describe the architecture must be suf?ciently complete to allow for the representation and manipulation of all relevant information.It is important that the architectural design notation is not‘‘representationally myopic’’[8]—it needs to be capable of representing the issues that can in?uence and effect a distributed real-time system’s design[2].The completeness also provides con?dence from the assessment that must be made in determining whether the architecture describes a suitable solution to the given problem de?nition.If all the relevant information concerning subsequent construction has been declared,then techniques should be available for deciding whether the solution is going to be an adequate one without having to implement it.Clearly this is an idealised view—but our
aim is to approach this ideal as closely as possible.This paper deals principally with the
representational needs of an architectural design and provides the outline of this analytical work which will be reported elsewhere.
This is the background to the work that is described in this paper.This paper describes a design approach for distributed real-time systems that uses a number of different design
viewpoints and associated notations to provide some sense of completeness to the ?nal design representation.Firstly we outline the issues that are important in a distributed real-time system before going on to give a brief overview of some of the in?uential approaches described in the literature.We then describe the fundamental principles of our approach before allowing a case study to introduce the technical details by example.
2.Distributed Real-Time System Design Information
The representational capability of an architectural design notation should be determined by the purpose of the notation.The joint purpose of our notation has been set down in two parts and can be summarised as:provide enough information to completely describe the subsequent implementation;and provide enough information to argue (at the design stage)that this design will satisfy the requirements.
The representational capability is thus directly in?uenced by the core of information that captures these two purposes.As a staring point to this discussion,Buxton and McDermid [5]provide a simple data model which captures some of this fundamental information.de?nes
contains depends
Processes
Modules Data uses
Resources related_to Module Function
used_by describes
Module Interface
supports
implements
contains
Dependencies Figure 1—The Information Content of an Architecture
This is a very‘functionalist’view but it does identify the major representative vehicles of design information—module,process and data structures.A module can be considered to be the static component of a system that performs some function.It is a building block that can be combined with other modules in order to perform work.A module structure thus describes the static structure of a system.A process on the other hand,uses modules in order to perform some work.A process is dynamic and is a schedulable thread of execution.A process characterises a control?ow in terms of the modules that it uses together with some notion of state that it maintains as it uses the modules—it has some behaviour or functionality which can be realised through the use of a number of passive modules.A process structure thus describes the dynamic structure of a system.In this sense,processes do not contain modules,nor do modules contain processes.
These three structures(process,module and data)together with their connection and interface information provide the basic structural information which describes a software design. Taken together with a hardware description(including resource allocation)and a suitable mapping,they are able to describe in totality a distributed system’s design(subject to the entities having suitable attributes).
For such a description to be architecturally useful,it must provide useable abstractions of implementation entities.If such components can not be manipulated and discussed at the design level then it is unlikely that the architecture will be able to provide enough information for subsequent development to proceed within the bounds set at the architectural stage.When this happens,the implementor may need to add extra information that compromise the design decisions made previously and thus invalidate the‘correctness’of the design.
The second purpose of an architecture was that it should allow the‘correctness’of a design, with respect to its requirements,to be assessed.It is undesirable to have to implement a design to see if it satis?es the requirements.It is more useful to be able to derive the information from a design that will enable the designer to assess the correctness of the design without having to wait for the implementation.In this way it can be seen that the purpose of an architecture is to look two ways along the life-cycle:forwards to the implementation and backwards to the requirements.
We shall now outline some of the more speci?c issues that are important within the broad model described to far.To avoid the limited representation trap described earlier[2]and[5]were used in order to provide a view of the issues that are of use.The following descriptions are views rather than partitions and so may overlap in places.
2.1.Process Information to be Represented
1.The existence of a thread of execution.
2.The state of a process.
3.The modules used by the process and the control?ow through the modules.
4.The functionality of a process.
5.The timing issues—deadlines,response times and periods.
6.The inter-process connectivity and communication.
7.The type of process—periodic or aperiodic.
8.The events that control a process’s operation.
These issues are those which are considered fundamental(although not necessarily complete, the list does provide a basis).As stated previously,a process is a schedulable thread of execution that maintains some state,calling a number of static program modules in order to implement some particular functionality.A process may have associated with it a number of timing constraints, execution deadlines for example.Such information is necessary for showing that a particular task set may be scheduled.
A process may be connected to other processes in order to communicate information dynamically.We adopt the same view of process connectivity as[5]by rejecting hierarchical process structures.Buxton and McDermid argue that hierarchical structures complicate matters and are unnecessary—they can always be reduced to more understandable?at structures by altering time budgets and priorities,for example.
Processes may be periodic(repeatedly executing everyτseconds)or aperiodic(only being initiated for the duration of a single execution on the occurrence of some event).We make the assumption that there will always be a minimum inter-arrival time between the events that trigger aperiodic processes.We argue this by noting that such triggering events must be communicated to the system through?nitely fast devices.We make these restrictions for purely pragmatic reasons —without them it would be very dif?cult to build workable real-time systems.
The role of events is not con?ned to triggering aperiodic processes.Events may also control the operation of periodic processes by providing stimuli that initiate and terminate behaviour.A periodic process,for example,may lie dormant for some time before entering into periodic activity.It may then continue exhibiting periodic behaviour until some other event which may cause it to pause or terminate.Similarly aperiodic processes become active on some event—however they do not have terminating events as they,by de?nition,perform their action until completion and then suspend.All such event roles must be recorded with their appropriate processes.
2.2.Module Information to be Represented
1.The existence of a module.
2.The module functionality.
3.The timing constraints.
4.The module hierarchy.
5.The module connectivity and interfaces.
A module de?nes a block of code(not necessarily one procedure)with associated functionality that can be used by some process.The module will have timing attributes that will typically include worst case execution time,for example.Such information is necessary for showing that process deadlines can in fact be achieved.Modules may be connected together in linear and hierarchical orderings with any such connections being governed by well-de?ned interfaces.
It should be noted that there will be some connection between the module attributes and the process attributes.Many of the process attributes will be directly dependent upon the module attributes because the processes rely upon the modules to implement their functionality,perform
work within their deadlines,etc.Part of the analysis framework will be showing that these relationships are consistent.
2.3.Interface Information to be Represented
1.The communication of data.
2.The direction of the?ow of data.
3.The format of the data being communicated.
4.The direction of the?ow of control.
5.The protocol of the communication.
6.The time performance at the interface.
7.The synchronisation of components.
Inter-process and inter-module communication should be governed by strict well-de?ned interfaces.These interfaces should describe the direction and format of any?ow of data,the direction of the control at the interface and any protocol of communication that exists across the interface.An interface may have timing behaviour associated with it which will include issues such as timeouts for example.Finally and with particular reference to inter-process communication,is the need to represent those communications that act speci?cally as means of synchronisation rather than purely communication.
Again it should be noted that there are dependencies between the information classi?ed as interface speci?c and some of the other information described previously.The timing behaviour at an inter-module interface,for example,is linked with the time that the called module will take to execute on average.Any overall framework must be able to record such dependencies.
2.4.Data Store Information to be Represented
1.The existence of a data store.
2.The access interfaces to that data(in the manner of abstract data types).
The degree of representation for data will depend upon the constraints of the system,but the existance of a data store and the available interfaces to that store must be considered a minimum. It may be that size information,history,etc may also be important,but they can always be added if we have the above as a base.As modules will be involved in the actual implementation of data stores and their associated interfaces,there will again be some link and commonality in design representation between them and the data store.
2.5.Resource Information to be Represented
1.The physical hardware components in the design.
2.The physical connectivity.
3.The components performance characteristics.
4.The use of the operating system.
Any distributed real-time software system must execute on some physical hardware platform and make use of resources that exist within that environment.A design needs to be able to represent these issues and show how the software maps onto this environment.The performance characteristics of the hardware are important from an analytical view in that they help determine the schedulability and performance issues that are important from a‘backward looking’architectural view.We include the use of the operating system as a resource because it provides services that may be used throughout the system—all components may make use of the operating system(assuming they are hosted on some processing element with one)to provide control variables for synchronisation for example.The recognition of such a resource is vital from an analytical point of view because the use of the operating system will require CPU cycles and they must be accounted for in any analysis.
2.6.Other Information
Clearly the level of detail within a given design is going to be as great as is required for that particular application.The purpose of this section has been to outline the sort of representation that is needed to provide a framework for a design.If the framework is complete and sound extra detail can be added in a straightforward manner.What a framework must also be able to cope with is information which affects the design but is perhaps not directly representable as properties of individual design components—what are normally called non-functional properties.
Non-functional issues typically include reliability,performance,maintainability,etc.They effect the representation of a design by driving the structure,the connectivity,etc of the system components.Any approach for the design of distributed real-time systems must allow for these dominant issues to be included in a controlled and analysable manner.Many of these are system-wide properties,and not properties of individual components.They need to be represented at some more abstract level.
This notion of analysability is very important.If a design does not include enough information to show that what is going to be implemented will satisfy the requirements then it is inadequate.Such analysability must include the means to examine the functionality,timing, schedulability,reliability,etc.If not,an implementation may be generated with unknown or uncertain properties which is clearly unsatisfactory.Before going on to see how our approach addresses these issues,we shall brie?y outline some of the relevant research in this?eld.
3.Traditional Approaches to Distributed Real-Time System’s Design
Many different approaches and notations have been used for the design of distributed real-time systems.We can view these techniques as belonging to one of three families:those targetted at traditional uni-processor systems,those targetted at distributed systems and those(few)that try to take a more general overall view.This split broadly mirrors the historical development of distributed systems and the increased understanding of the issues that are involved.Figure2 attempts to show how the different families are in?uenced by different facets of a computer system.
Hardware Traditional uniprocessor methods
Distributed systems approaches
Software
levels of
abstraction Complete approaches
Figure 2—The Different Families of Approach
The early approaches concentrated upon using the methods that had been successful for the development of software for uni-processor systems.Such methods (Yourdon [9],MASCOT
[10],JSD [11],etc)had some success in representing software designs but were not
representationally complete to the level described in the previous section.Their major failing was typically the lack of consideration for the in?uences of the underlying hardware and those of the,not directly representable,non-functional issues.The methods were successful for the parts of the design to which they applied,but much of the work had to be done outside of the framework.
In practise,these methods were used in one of two ways;either in the multi-program or
single-program approach [2].The multi-program approach involved writing separate programs for each machine in the target system.A decision was taken very early on as to which parts of the functionality should be sited where and then programs were written (using the method)for each of the https://www.doczj.com/doc/dd9987452.html,munication between these programs then takes place through explicit use of the operating system —such inter-program interaction typically takes place outside of the method’s framework.Whilst such an approach allows the hardware platform to in?uence the design,it occurs in an in?exible and early manner,clearly destroying any generality in the design of the software solution.It is also harder for a compiler,for example,to check the ‘correctness’of an overall system,even at a syntactic and type level.
The single-program approach can be used in one of two ways:either a pre-partitioning or post-partitioning manner.The post-partitioning technique is most commonly used with traditional design methods as the program is written as if for one processor.It is only then partitioned into separate components,often by automatic tools.These tools must introduce the means by which the separate programs are able to communicate with each other.This makes the design of the software very much easier as it can all be done within the design framework.Unfortunately,the
introduction of the hardware is much too late to properly in?uence the design of the software and this makes the design of fault-tolerance mechanisms,for example,very dif?cult.
The alternative single-program approach,pre-partitioning,is the basis of many so called
distributed systems design methods.These methods make a deliberate attempt to recognise the
hardware distribution in the overall solution.Most pre-partitioning techniques are based upon the concept of the virtual node[12].
A virtual node is a collection of processes,code and data that is guaranteed to be allocated to one physical node in a system—that is,not distributed across more than one node.This means that all communication between elements in a virtual node may take place using normal intra-program interfaces.If an element within a virtual node wishes to communicate to an element in another virtual node then it must be do so through message passing.Such a framework allows general designs to be produced,with the underlying hardware providing a controlled in?uence upon the design approach.Burns and Wellings[2]note how this acts as a basis for CONIC[13], SR[14],Argus[15]and StarMod[16].
The virtual node concept allows us recognise the the interaction between the hardware and the software of a distributed system in a controlled manner.Unfortunately,the notations that are founded upon this concept often do not provide suf?cient abstractions and representational capability.Indeed,they typically represent less than the traditional methods as far as general software structure is concerned.What is needed is some sort of combined approach which enables a complete picture of the software to be represented and also provides a model for the way that software interacts with the hardware.One such complete‘middle out’method that tries to do this is DORIS[17].
DORIS is based upon MASCOT3used in a single-program format.A software system is devised independently of the hardware and then‘re?ned’into components that can be mapped onto a particular hardware distribution.In common with MASCOT3,there are a number of representational weaknesses but this seems to be an approach that enables the distribution of a system to be handled in a sensible way.We explore these concepts further in the next section.
4.An Architectural Approach
The absence of complete design descriptions in traditional methods has meant that designs have been unable to ful?ll the important role of adequately describing all the necessary issues. This has led to unanalysable designs with the result that it has been impossible to decide whether a particular design satisfactorily describes a solution to a problem in hand until the implementation has been produced.The key areas that seem to prove dif?cult are non-functional issues(including time)and the fact that the target system may be distributed.
We term a design that acts as a complete description of what is to be built as architecture.An architecture is an evolvable description of the solution and is re?ned and extended as the requirements for a particular problem become better understood.An architecture must exist within a framework that will allow the issues described so far to be handled in a controlled manner. Within this framework,the architecture should allow information to be derived from it as to the eventual operation of the solution;indeed,there should be no need for an implementor to add design information(apart from more detail)outside of the framework devised by the Architect. We can de?ne an architecture to be a software structure together with a mapping onto a physical structure which together will satisfy the totality of requirements within the constraints imposed by the execution environment.
The techniques that seem to offer the greatest prospect of solution for the above problems are
the virtual node concept and the merging of software with hardware used in DORIS.Both provide a means of separating the basic software structure from the hardware,whilst maintaining control of the hardware’s in?uence.We host our approach within a framework that captures the generality of these two techniques:the TARDIS framework[18].
TARDIS partitions a design into two architectures:a logical and a physical.The logical architecture is a description of the system without the constraints of the environment.In effect it is an abstraction based on the assumption of suf?cient,perfectly reliable resources.The physical architecture then introduces‘real world’constraints into the logical architecture in order to make it work when mapped onto some hardware con?guration operating within a particular environment. In this way a separation of concerns is provided over the design information.These physical issues do not effect the fundamental behaviour of the system and so they may be considered independently.
The issues that drive the generation of the physical design are typically the non-functional requirements.Issues such as performance and reliability are concerned with how some fundamental logical design will operate within some real physical environment.Such requirements can thus be used as‘re?nement agents’to derive the physical architecture that will provide the functionality of the logical architecture,but operating on some distributed hardware within some particular environment—thus performance,reliability,time etc can be‘factored out’of the logical level.They provide the force that reshapes and re?nes the logical structure into a design that can be implemented to solve all of the requirements.
The development of these two architectures will almost always occur in parallel to some extent.That is,the logical design may be produced and mapped onto some physical platform.If (with these extra physical issues)the design no longer solves the requirements(functional, performance,timing,etc)then some restructuring may have to be done at the logical level.The goal in having a sound representational base is that such evaluation can take place at the design level.
A TARDIS design progresses through the establishment of https://www.doczj.com/doc/dd9987452.html,mitments are speci?c design decisions that will be preserved throughout the design process and can not be compromised by anything else that is subsequently decided.A commitment may result in the introduction of obligations which must be satis?ed by subsequent commitments.For example, there may be a commitment to having a particular process structure that will result in a number of obligations concerning the individual process’s deadlines and periods.The deadlines become obligations on the timing characteristics of the modules that are used and the periods become obligations to the scheduling algorithm that is to be used.
Commitments and obligations provide a means of describing a design within the logical and physical descriptions.The logical and physical designs themselves can be considered to be viewpoints of the actual implementable design(although the physical viewpoint is in reality a complete view of the design).Viewpoints provide a means of isolating particular facets of a design whilst still providing an overall view when considered in totality[19].The logical and physical viewpoints are essentially‘meta-viewpoints’in that they are views of a design which themselves may be composed of viewpoints.We describe viewpoints within this logical/physical partition which map across both meta-views to partition the information in a design.
Lonn[1]points out that,within a distributed system,it is possible to distribute the program,
the data and the control elements.Clearly these elements need to be represented within both logical and physical designs and so it seems useful to generalise and consider separately these particular issues through the use of viewpoints.We introduce a viewpoint for control (processes)and a viewpoint for code 1(modules)—as well as a separate viewpoint to show the hardware characteristics of the distributed system.We show the relationships between these viewpoints in ?gure 3—essentially this relationship applies within either of the meta-viewpoints with the obvious removal of the hardware view from the logical design.M
M P
P
P
Logical
Front
Elevation
Plan Views
Processes Modules
Operating System Hardware
Physical
Figure 3—The Relationships between the Viewpoints
Using this collection of viewpoints,it is possible to view the design information in some sort of abstract hierarchical manner (this should not be confused with a hierarchical design involving subsystems).At the highest level the control structure describes the way in which the processes within a system communicate and interact.These processes then use code modules to implement their functionality.These modules represent the code that needs to be written.These modules may use the operating system in their work and this too is recorded.All of these elements must be mapped onto the actual hardware platform of the target.Some of the information that will be represented within these views may not be applicable within both the logical and physical 1We group data with ‘code’as data must be manipulated and managed by code (running under processes)and it seems
more useful to recognise the occurrence of data within these viewpoints rather than on its own.It is less useful to mix
processes and modules as it is not generally the case that one will always contain the other —but at the design stage,
processes clearly use data.
viewpoints but the diagram shows the overall relationship.
Each of the viewpoints in this diagram can be considered to provide a plan view of some particular aspect of the design information.When considered in totality,in a‘sideways’overall view,they provide a‘front elevation’.There will be some common points across the various plan views,the most obvious one being the use of devices or peripherals.They will appear in similar
‘geographical’positions across each of the views.The process and module views are valid across both meta views although the nature of the design information will be different.
4.1.The Process Structure or Active View—What will Run
The principal requirement of the active view to to provide a notation capable of representing the fundamental process structure of a real-time system.The process structure exists within both the logical and physical architectures and so any candidate notation must be capable of representing both the totality of design information that is necessary and also the logical subset—in summary,it should provide a fundamental representation that is easily extensible.
One such notation that seems to provide this capability is MASCOT3.MASCOT3’s notation is based upon networks of processes that communicate through the use of shared data areas. MASCOT3does not provide a separate graphical representation for modules nor does it provide any time abstractions.It does,however,provide a sound basic notation for our active view and can act as a basis for the addition of the information that was outlined in section2.
Within this structural process description,there is a need to be able to represent the functionality of what each process‘does’.There is no graphical means within MASCOT3for this and so we must integrate some other technique.We chose to link StateCharts[20]with the process representation in order to describe a process’s functionality.StateCharts represent functionality through collections of states and state transitions.Each process(activity)within the active view bounds a StateChart which is then able to de?ne the process’s behaviour in terms of its connections to its environment.
These two notations thus provide a structural and behavioural view of the control within a concurrent system.At the logical stage there is no need to discuss time or base hardware.It is only within the physical design that these extra issues need be considered,when the actual implementable components are described.The physical view of this viewpoint will therefore include mappings of these components to the processing elements and extra attributes(deadlines and periods)which will enable schedulability analysis to be carried out.
4.2.The Module Structure or Passive View—What will be Implemented
Each process will use a number of modules in order to implement its functionality.The organisation of these modules is recorded within the passive view.A notation that provides a very basic means of representing static module structures is Myers’Structure Charts[21].
We use this as a base notation but introduce some of the extentions described in[5]together with some of the formality that exists within MASCOT3.We chose to add MASCOT3formalisms to Structure Charts because MASCOT3is the‘stronger’of the two notations and is more widely
used.The principle concept that we bring to Structure Charts is procedurally typed interfaces between modules.We are thus able to draw a graph-like network of the code that is to be used by the activities to provide the desired functionality.The functionality of the modules become obligations for subsequent detailed design and implementation to satisfy.It is also possible to model access to the operating system from within this view by treating the underlying operating system as a collection of software modules that can be used like any other code.
The generation of the physical passive view will involve transforming the logical modules into physical modules through a mapping to a particular memory unit,the introduction of timing obligations,the use of fault-tolerant replication strategies,etc.There is a close link between the information presented in the active view and that presented in the passive view—this link and the issues important when moving from the logical to the physical architectures will be demonstrated more clearly by way of the example.
4.3.The Hardware Structure View—What will be Used
The hardware description language that is used is the PMS[22](Processor Memory Switch) notation that provides a very basic means for representing communication,processors,memory etc.This is all that needs to be represented and so the notation is suf?cient.The main aim of this view is to identify those physical elements that can have software elements allocated to them, together with any obligations on the hardware that are required to support the software.There is no representation of this view within the logical architecture.
5.A Worked Example—A Mine Pump
It is the purpose of this paper to describe,by way of an example,a new approach to the design of distributed real-time systems.It was felt that by presenting the techniques described in ‘action’as direct answers to‘real’design problems,they may be better understood by the reader. The example chosen is one that is beginning to obtain a reputation as a de facto real-time problem —the mine sump pump[18,23,24].The requirements for the system shall now be presented before some general comments concerning the methodological approach and the case study itself.
5.1.The Mine Pump Problem Domain
The description for this problem is taken from[18].The problem concerns the design of a control system for a pump which is responsible for preventing water?ooding in a mine.When the water level in the mine reaches a de?ned height,the pump should be turned on to remove some of the water.When the water drops below another de?ned level,the pump should be turned off.An operator is able to intervene to switch the pump on or off independently of the control system providing that the water is between the two critical levels.A supervisor may turn the pump on or off whatever the level.
The pump should not be operated when the atmosphere contains too much methane,as measured by a methane sensor.There are two other sensors:a carbon monoxide sensor and an
air?ow sensor.If either of these two sensors register critical then the shaft should be evacuated of all personnel.Any critical reading should be registered with the human operator.All readings
Pump Control System
Pump
Hight Water Level Detectorr
Sump Low Water Level Detector
Carbon Monoxide Sensor
Methane Sensor
Air?ow Sensor Operator
Log
Figure 4—The Mine Pump System
from the sensors are to be logged for possible future analysis,as are records of the pump’s activities with the times of these activities.
In addition to these base functional issues,there are a number of important non-functional requirements to consider —reliability,safety,timing and security.The system should be reliable enough so as to only lose one shift in a thousand through pump failure.If the pump does fail,then there will be one hour before the water becomes too deep to work in.The safety requirement is a measure of the probability of causing an explosion through operation of the pump when the methane level is too high,a typical ?gure of 10-7explosions per operational hour is taken.
There are three timing issues to consider:monitoring periods,shutdown deadline and
operator information deadline.The monitoring period of the sensors is assumed to be sixty
seconds,except for the methane sensor which is ?ve seconds.The pump shall have a shutdown deadline of one second.The operator must be informed of critical levels within one second of their being detected.These ?gures are largely arbitrary,but are taken as ?rm requirements for the sake of the example.
The security requirement is that an operator should not be able to masquerade as the
supervisor and thus gain the capability of switching the pump on or off whatever the water level.It is assumed that there is some form of logging onto and logging off from the system for the
operator and supervisor.Once the supervisor has logged on,all commands from him/her will pre-empt the operator’s commands (we assume one operator and one supervisor for simplicity.
5.2.The Approach to the Design
The logical design is the?rst design entity that is produced,providing an immediate‘?rst cut’of the software design.There is no mention of time or hardware speci?c details in this view as these are extraneous to the basic software structure.The process connectivity graph is the?rst entity produced as it sets the framework for the system.As the activities become de?ned,then the logical functionality and module structure can be produced.It is not always the case that the module structuring will mirror the structuring of the processes,but it is the case in this short paper-based example as it makes the traceability between the views clearer.In reality the active and passive views would not necessarily be geographically similar,nor would the logical design be produced in a single iteration.Such reality is ignored in this paper for simplicity’s sake.
On conclusion of the logical design,analysis would take place to show that the fundamental requirement properties have been solved(we perform analysis using a transaction based approach that will be described elsewhere).The plan view of the hardware would then be produced and used as the logical design was mapped to the physical design.The mapping would involve the addition of(amongst other things)timing attributes which would lead to obligations for the detailed design to satisfy.There would again be more analysis to show that this physical design satis?ed these physical properties(as well as the initial logical ones).This paper will concentrate on representation but will identify the major issues involved in the analysis.
The design is presented in a‘top down’manner with major subsystems being identi?ed and then decomposed individually down to their base components2.StateCharts and passive module diagrams will be presented at appropriate times within the design(the active and the passive will therefore be mixed).This was done to make the design easier to read.This collection of techniques and use of the TARDIS design framework is collectively known as MASCOT3+.We provide a complete logical description of the mine pump to give the reader a feel for the notation. The physical description only concentrates on some of the more interesting issues to avoid repetition.
The symbols that will be used in the active view are shown in?gure5.
2The basic breakdown and structure of the design is taken from[18]but the nature of our notation means that there is con-
siderable difference in the level of technical detail.
Figure5—Symbology of the Active Viewpoint
Much of the symbology is similar to MASCOT3notation.The two kinds of activity(blank aperiodics and crescent mooned periodics)communicate information to each other via data stores (idas,channels and pools).These data areas are drawn in a dashed manner to indicate their essentially non-active role in this viewpoint(it is the activities that are fundamentally active).The presence of the passive data stores is retained because they capture the nature of communication between the active elements.Actual communication takes place across typed access interfaces. The ported ends demand procedural(in the traditional programming sense)calls to be provided by the windowed ends(which is where the procedures are implemented).Interfaces may be strictly data communicating or may perform some synchronising action as well.All of these entities may be packaged up inside subsystems.The symbology of the passive view is shown in?gure6.
Figure6—Symbology of the Passive Viewpoint
The symbology of the passive viewpoint is essentially that given by Myers but augmented with some of the applicable MASCOT3concepts.The basic module symbol is drawn with a thick boundary to indicate a composite nature(in the same way that active subsystems are drawn with heavy boundaries).Library modules are those that have already been written.The relationship between library modules and composite library modules is similar.Modules communicate by the same access interface mechanism as used in the active view.There is one symbol for data areas which will include any protection mechanisms for actively shared data.There is also a separate symbol for explicit use of the operating system.
5.2.1.The Logical Design
The minepump system can be viewed as consisting of four interacting active subsystems:an archive,an environment monitor,a pump controller and a users interface.The base connectivity of these active subsystems is presented in?gure73with each connection between the subsystems using a MASCOT3style access interface.These interfaces de?ne what variables are passed and returned between any two communicating elements.This diagram represents a high-level structural commitment.
3In common with the MASCOT notation,there is a textual equivalent to the active and passive diagrams presented in this
document.It is here that much of the attribute information(which is discussed informally throughout the example)would
be presented in a structured way.Only the diagrams are shown as they demonstrate the broad concepts in a clearer way than
the text.The absence of the text means that some of the more detailed parts of the design will not be presented;it is hoped
that this does not mask any of the principles.
Figure7—The Top Level Active Structure
The pump subsystem responds to commands from the users and from methane information from the environment monitor,operating the pump accordingly and recording all information in the archive.The environment monitor records all of the sensor readings, provides the pump subsystem with methane readings and warns the users(through a synchronising call)if any sensor indicates a critical reading.The users subsystem interacts with the operator and supervisor providing commands(in a similar fashion to the alarms)to the pump whilst the archive records all the relevant information to backing store.These subsystem
‘functional descriptions’become obligations for the subsequent design to satisfy.
The archive subsystem contains a periodic activity,formatter that reads values from two data stores and writes them to a backing store.The two stores in this case are both channels indicating that all the data‘sent’here will be available(the channel acts as a queue subject to storage space)for the periodic formatter.This organisation of elements becomes a commitment within which the described behaviour must be generated—an obligation for the StateChart and passive view descriptions.
Figure8—The Active Structure of the Archive Subsystem
The formatter writes these formatted values to the backing store where they will be kept for future use.Readers familiar with MASCOT3will note that the device server component has not been included.This is because the server combined both active and passive elements in an attempt to provide an abstraction for device usage.It was felt that such a combination did not?t comfortably within our multi-viewpoint approach and that we could capture the relevant information by simply‘access interfacing’the link between an activity and a device.That is,we de?ne a procedure that can be invoked by the formatter to access the backing store.This will be an obligation within the passive view.
We capture the functionality of the formatting process through the use of a StateChart,shown in?gure9.The area where the StateChart has to interface with the activity’s description is at the access interfaces.The procedures that the activity uses are going to in?uence its behaviour which is de?ned by the StateChart.At the logical design stage we are not concerned with failure models and so we need only represent the fact that a procedure has been invoked and then completed(in a physical model we may want the possibility of being able to timeout).We therefore de?ne the behaviour of the periodic activity in terms of a number of completed procedure calls that retrieve the data of interest and then write it to the store.
A state transition occurs if the procedure invoked on a particular port completes.The basic format for a transition is virtually the same as for a StateChart but includes a means of linking the transition to some particular port:
connection_identi?er:procedure(parameter_list)[condition]/action In this example,formatter has four states and functions in a straightforward manner by successfully reading values from each of the data stores and then writing them to the output device.The actual procedures would be de?ned in the textual speci?cation of the access interfaces.If we were progressing to detailed design,we may also introduce a number of state changes that were internal to the activity to show greater detail.In this example,‘Read Values’is shown to be the initial state.
Read Values Output Values Output State
Read State
o:store(rec_form::Form_record)
o:store(rec’_form:Form_record’)p:get_values(VAR rec’:Record)
r:get_states(VAR rec:Record)
Figure 9—The Functionality of the Archive’s Formatting Process
This breakdown of the activity’s behaviour provides us with a relatively straightforward means of deriving the passive viewpoint for this subsystem 4,as shown in ?gure 10.The code that implements the data stores is provided by the ‘monitor-like’states and values .In all the examples of data stores in this paper,there will be no commitments to use any operating system supported synchronising primitives to support data integrity (the mutual exclusion problem).This is because we advocate Simpson’s four slot fully asynchronous communication mechanism [25].This mechanism describes an algorithm that is dependent only on the guarantee that the writing and reading to a ‘bit’is guaranteed to be atomic.With this obligation,no time consuming ‘non-synchronising’mutual exclusion mechanisms are needed.It should be noted that more than one thread of execution could be active at any time within this composite module (either of the activities that write to the stores and the activity that reads from them).
4The passive viewpoint of the software is not guaranteed always to follow the structure outlined by the active viewpoint.