[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO2005109196A1 - Verfahren zur bestimmung von verklemmungen in nebenläufigen prozessen - Google Patents

Verfahren zur bestimmung von verklemmungen in nebenläufigen prozessen Download PDF

Info

Publication number
WO2005109196A1
WO2005109196A1 PCT/EP2005/051986 EP2005051986W WO2005109196A1 WO 2005109196 A1 WO2005109196 A1 WO 2005109196A1 EP 2005051986 W EP2005051986 W EP 2005051986W WO 2005109196 A1 WO2005109196 A1 WO 2005109196A1
Authority
WO
WIPO (PCT)
Prior art keywords
state
system model
deadlock
objects
waiting
Prior art date
Application number
PCT/EP2005/051986
Other languages
English (en)
French (fr)
Inventor
Michael Kersten
Original Assignee
Siemens Aktiengesellschaft
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Siemens Aktiengesellschaft filed Critical Siemens Aktiengesellschaft
Priority to JP2007512180A priority Critical patent/JP4637175B2/ja
Priority to US11/579,554 priority patent/US20080092147A1/en
Priority to EP05742661A priority patent/EP1745375A1/de
Publication of WO2005109196A1 publication Critical patent/WO2005109196A1/de

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
    • G06F9/524—Deadlock detection or avoidance

Definitions

  • the invention relates to a method for determining deadlocks in concurrent processes, in which at least one object in one state is waiting for another object in a specific state, for an object-oriented system model of a reactive system.
  • UML Unified Modeling Language
  • object-oriented, computer-implemented language not only software programs but also complex technical systems, such as motor vehicles and airplanes, can be described and their functions verified. Due to the high security requirements in these areas, the combination of a standard modeling language with formal methods is desirable in order to be able to reliably detect misconduct already in the construction phase. In such systems, deadlocks in cyclic processes can also occur.
  • a deadlock is a state of processes in which at least two processes wait for resources that are assigned to the other process. As a result, both processes block each other. A jam can then only be eliminated by ending individual processes or restarting the system. Both can be very problematic in safety-critical systems.
  • Deadlocks can occur in systems that are capable of running multiple processes in parallel (multi-task systems) and in which the order of resource allocation is not fixed.
  • T. Shufer, A. Knapp and S. Merz: "Model Checking UML State Machines and Collaborations", in: Electronic Notes in Theoretical Computer Science 47 (2001), pp. 1 - 13 describes a method for demonstrating freedom from deadlocks and other model properties for relatively small systems using the methodology of model checking.
  • These are specialized computer programs that disadvantageously require a transformation of the system into a model checker input language.
  • Each state of a state machine is modeled by an individual process. For each state machine of the UML system model, two additional processes are used to output events that are stored in an event queue and to handle transitions.
  • the object of the invention is therefore to provide an improved method for determining jams in concurrent
  • Steps a) and b) are used to extract the properties of a system model that are relevant for a deadlock, and from this in step c) a state-waiting diagram is generated, which can later be statistically analyzed to find out which "waiting-on" relations exist between active objects.
  • the internal states of the active objects are described.
  • the possible deadlock situations are determined. If no deadlock situations are found, the process is complete and the result can be displayed. Otherwise, in a third phase, the accessibility of the identified possible deadlock situations is calculated by calculating the possible paths into the identified potential deadlock situations that were found in the previous phase using a search algorithm. It is then analyzed whether these paths can be executed using a heuristic simulation approach.
  • Active objects in the sense of the invention are language means used to describe processes in the system modeling language.
  • An active object in the object-oriented model corresponds to a concurrent process of the modeled technical reactive system.
  • a concurrent process can sometimes be cyclical. This is often the case with reactive systems, but is not a necessary condition for the application of the method.
  • step a) of extracting all active objects the active objects are preferably extracted from a static and dynamic structure view of the system model and stored in an object list.
  • an assigned class is then stored in a class list for each active object and the associated state diagram for specifying a state machine is evaluated for each class in the class list.
  • the specified state machines can then be saved in a state machine list.
  • the possible deadlock situations are preferably determined using a depth-first search known per se (depth-first search).
  • the availability of the identified possible deadlock situations is preferably checked heuristically by determining the activated transitions based on an initial state of the system model and selecting the activated transition that brings the system model closer to the deadlock event.
  • Activated transitions exist, for example, when the guard condition for the assigned object is true and the event of the object is in an input queue.
  • Step e) of checking all possible paths for each deadlock situation is preferably carried out iteratively until either a deadlock state is reached or all paths have been followed by a predetermined number.
  • the system model is particularly preferably described with the Unified Modeling Language UML.
  • the object is further achieved by a computer program with program code means for carrying out the method described above when the computer program is executed on a computer.
  • Figure 1 flow chart of the method according to the invention for determining deadlocks
  • Figure 2 Static system structure (class diagram) of an exemplary measuring system model
  • Figure 4 the detailed view of the behavior of the controller of the exemplary measuring system model
  • FIG. 5 detailed view of the behavior of the first sensor of the exemplary measuring system model
  • FIG. 6 detailed view of the behavior of the second sensor of the exemplary measuring system model
  • FIG. 7 detailed view of the behavior of the clock of the exemplary measuring system model
  • the starting point is a system model described graphically and object-oriented with the Unified Modeling Language UML, hereinafter referred to as the UML system model.
  • UML system model The method is equally suitable for other description languages that describe technical systems in an object-oriented manner.
  • a) the active objects of the UML system model are extracted, as well as their properties and relations.
  • the properties of the UML system model that are relevant for jamming are extracted and stored in mathematical structures, such as lists, quantities and tuples, which enable evaluation with an effective algorithm in the subsequent phases.
  • call events are viewed as consumer events and call actions as event creators. Events are only taken into account if their producers and consumers are appropriately associated.
  • a second phase b) an analysis is carried out to identify potential deadlock events.
  • This analysis can be carried out by statically evaluating a UML state diagram to find out which waiting relationships exist between the active objects. For this purpose, a state wait graph is inserted which, in contrast to the classic wait graph, shows the internal state of the active objects. The detection of cycles in the state wait graph initiates the existence and location of potential deadlocks.
  • a potential deadlock is a cyclical waiting situation between competing or parallel components of a system, each of which is within a specific state.
  • Deadlocks can be identified in a state waiting graph.
  • This is a directed graph in which each node an active object in a specific state (of the associated state diagram) and each edge represents a "wait on" relation.
  • the number of vertices of the state wait graph is the same as the number of states of all state diagrams of the model associated with active classes.
  • the number of edges depends on the transitions defined in these state diagrams.
  • the head of each edge is connected to the node waiting for a specific event.
  • the node connected to the end of the edge is a potential originator of this special event.
  • a potential deadlock situation is a situation in which two or more objects, each in a specific state, wait for each other to generate a specific event.
  • Phase b) all cycles are detected in the state waiting graph and the relevant cycles are sorted out. Cycles are not potential deadlocks, but logical errors in the corresponding state diagram, in which all nodes of the cycle are the same object. Cycles with two or more nodes of different objects, on the other hand, are potential deadlock situations if no object with more than one state is involved in the cycle. Otherwise, these are cycles with "over-involved" objects.
  • the detection of all cycles in the state waiting graph is carried out with an improved depth search algorithm (depth-first search algorithm) which is known per se and which covers all cycles of the Graphs and the division are calculated in a single pass.
  • depth-first search algorithm depth-first search algorithm
  • the remaining potential deadlock situations are then examined with regard to the outgoing edges. This is done by traversing the graph and calculating the initial degree of each node.
  • the initial degree is the number of edges coming from the node. If all nodes have an initial degree of one, there is a potential deadlock situation in the sense of the invention. If there are nodes with an initial degree of more than one, it depends on the target object of the edge pointing out of the cycle whether the examined cycle is a potential deadlock. If the target object is not involved in the considered cycle, the examined cycle is not a deadlock. Otherwise it must be checked whether the edges connect two states of the same object.
  • the potential deadlock is combined with a logical error and the logical error should be corrected before the deadlock detection is continued. Otherwise, a further cycle is recognized in the state waiting graph, which is to be evaluated later. In this case, the next phase c) can be initiated since the cycle detection ensures that all cycles are found and processed separately in the further analysis of the accessibility of the potential deadlock situations.
  • Potential deadlock situation means that it is statistically possible that a deadlock occurs. However, whether the deadlock event actually occurs during the runtime depends on dynamic aspects of the system model, which in the next phase c) analyze the accessibility of the potential deadlock situations is examined separately from phase b) of the analysis to identify potential deadlock situations.
  • phase b If no potential jamming situation is found in phase b), the system is free of jamming and the next phase c) can be skipped.
  • phase c the accessibility of the potential deadlock situations is then analyzed.
  • Each potential deadlock situation identified in phase b) is examined by calculating the possible paths into the potential deadlock situations using a search algorithm and analyzing whether these paths can be carried out using a heuristic simulation approach.
  • the search algorithm performs a specialized depth search for each relevant state diagram and stores all paths to potential deadlock situations in a path list.
  • Each path list contains all states and transitions of the respective path.
  • the path lists are used as input data for the subsequent heuristic simulation.
  • the state machines of the UML system model are executed with a simulator that implements the exact UML semantics according to the OMG standard (www.omg.org).
  • OMG standard www.omg.org
  • the sensors Sensor1, Sensor2 have a measuring unit that carries out the actual measurement and its behavior is abstracted in the measurement system model.
  • the clock has a clockwork that models the progression of time and returns the current time when called.
  • the measuring system model also abstracts from the exact functioning of the clock.
  • the clock is required by the sensors Sensor1, Sensor2 in order to stamp the measured values with time stamps.
  • the control unit is for starting the
  • Components responsible and continuously polls both sensors Sensor1, Sensor2 at system runtime can be started and stopped by the user.
  • the behavior of the user can be modeled for analysis purposes.
  • FIG. 2 shows the static system structure of the measurement system model in the form of a class diagram.
  • the plots + and - used in the class diagram represent the visibility of the element that they precede. All elements (operations and / or attributes) annotated with "+” are declared public. These are visible to all other classes that are associated with the relevant class. Elements that are annotated with "-" are private (private) and therefore only visible within the relevant class. This means that the private elements can be called by the class itself, for example in the associated state diagram, but not by other classes. In the example, all operations of the classes are public, ie declared with "+ > . Only the attributes that are used to store values are privately declared with "- ⁇ ". This corresponds to the secret principle in object-oriented modeling and means that the values of the attributes of classes can only be manipulated with their operations, and limits the danger of side effects.
  • the query is forwarded to the measuring unit via the sensor component, which carries out the actual measurement, whereby a time stamp with the command "Give time stamp" from the clock during the measurement for everyone Sensor Sensorl, Sensor2 is queried.
  • the measured values are sent via the sensors Sensor1, Sensor2 together with the time stamp to the controller and via this to the user.
  • FIG. 3 shows a block diagram of the dynamic system structure of the measurement system model. It becomes clear that the controller is used to parameterize the clock, which in turn takes the time measurements time measurement 1, time measurement 2 when measuring by sensors Sensor1, Sensor2. The measured values together with the time stamp are sent as signals measurement 1, measurement 2 to the controller and, via this, to the environment of a user.
  • FIG. 4 shows the behavioral view of the controller as a diagram. After initialization, the controller parameterizes the clock and starts it with the command
  • the first measurement (measurement 1) is triggered by the “Sensor.Request_Measured value” command.
  • FIG. 5 shows the behavioral view of the sensor 1.
  • the measurement is carried out with a request for the time stamp on the clock with the command "Request_Measured value / clock .Request_Timestamp_Sensorl".
  • FIG. 6 shows a corresponding behavioral view of sensor 2. For the explanation, what has been said is referred to.
  • FIG. 7 shows the behavioral view of the watch.
  • the state of the parameterization of the clock is carried out by the controller and a running state "running" is stimulated with the signal "Start".
  • Control unit is requested.
  • the control unit waits for the measured value and, in a loop, the control unit requests the measured value to give further measured values.
  • the state is ended by the command "Controller. Stop” to the control unit.
  • phase a) of the feature extraction the features required for the deadlock detection are extracted from the UML system model and stored in the structures shown below.
  • this part of the feature extraction can be different. However, this is not the subject of the present invention.
  • this list is run through exactly once, and the associated class for each object is saved in a class list.
  • the length of the class list is saved as number_classes.
  • the associated state diagram is analyzed and the state machine specified there is saved in the state machine list.
  • the number m is the number of actions that can be triggered by a transition.
  • the state is the state of the state machine in which the object can generate the action if the associated transition switches.
  • the target object is the object to which the call action is addressed.
  • the target event is the event of the target object, which is generated and placed in the input queue (input queue).
  • a waiting quantity table is then created. This is achieved by selecting the associated state machine from the state machine list for each object from the object list via the associated class from the class list and determining which events (events) the object is waiting for in which state and which object can generate the respective event. The information about which object can generate the respective event is taken from the actions table.
  • the waiting quantity table has the following form:
  • the object name is listed under the entry object analogous to an action table.
  • the waiting amount is like this structured that a set of object-state combinations can be saved for each state of the state machine of the object.
  • An object-state combination has the form “object. State ", in which case” object “denotes the object to be waited for and” state "the state to be waited for.
  • object 1 in state 1 waits for object 2 in state 1 and object 2 in state 2.
  • the waiting quantity is free of duplicates.
  • the results of the feature extraction are the following:
  • Object list [Ben-> object, Con-> object, Snl-> object, Sn2-> object, U-> object]
  • Class List [User-> Class, Controller-> Class, Sensorl-> Class, Sensor-> Class, Clock-> Class]
  • phase b) "potential deadlock detection”
  • a so-called state-wait graph is generated from the waiting quantity table. This is a graph, the nodes of which denote object-state combinations and the edges of which indicate "wait-on” - Denote relationships (wait-for-relations). From this graph, statements such as object 1 is waiting in
  • a potential deadlock in the sense of the method under consideration is a cyclic "wait-for" relationship with some other properties.
  • Phase b) of the analysis to identify potential deadlock situations works in two stages. In the first stage, a cycle detection is carried out on the status wait graph. The result is a lot of potential deadlock situations. In the second stage, those potential deadlock situations that have the following properties are separated from the set of potential deadlocks:
  • the method for cycle detection is based on the well-known depth-first search method.
  • FIG. 9 shows an exemplary state waiting graph for the measuring system model.
  • the final set of potential deadlocks is passed to the next phase c) of analyzing the accessibility of the potential deadlock events.
  • the "deadlock reachability analysis” serves to prove that the potential deadlocks found can be reached at runtime of the system. Again, there are various standard methods that can be used for the reachability analysis. It is particularly important for the present method that the deadlock phase - Reachability analysis does not give away the runtime advantages that result from the extremely favorable time complexity.
  • the expected time is expected to be linear to the number of edges and nodes of the state waiting graph.
  • the first step in the analysis of the reachability of the potential deadlock events is the calculation of the local paths of the objects involved. So-called Path lists constructed that can be derived from the state machines of the model. Then the execution of the model is simulated by checking which transitions are activated, ie which, based on the initial state of the model
  • Transitions can switch if and only if the guard condition is true and the event is in the input queue. Then the transition that brings the model closer to the potential deadlock situation is selected according to a suitable heuristic.
  • the simulation stops when the potential deadlock situation has been reached or all paths have been traversed a specified number of times and no potential deadlock condition could be reached. In the latter case, no statement can be made as to whether the potential state of the deadlock can still be reached.
  • Path lists have the form:
  • Path list ⁇ [(ZI, Z2), ..., (Zi, Zj)], ... ⁇ ,
  • (ZI, Z2) is an ordered pair, where ZI denotes the source state of a transition, Z2 the target state of the transition and Zj lies in the set of potential deadlock situations.
  • a model state for a model with a number n of objects is given by
  • n denotes the respective object and Z the current state of the object.
  • ES_i is the input queue of 0_i.
  • the trace set is the set of all episodes
  • M_a is the initial state of the model and M_z the last state before termination of the simulation and (O.Z_a, O.Z_b) a transition of the object O from Z_a to Z_b.
  • FIG. 10 leaves the sequence diagram for the result of the
  • a frame with rounded corners serves to visually summarize the messages involved in the deadlock.
  • the states of the objects involved in the deadlock are specified in a note box.

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Debugging And Monitoring (AREA)

Abstract

Verfahren zur Bestimmung von Verklemmungen (Deadlocks) in nebenläufigen Prozessen, für ein objektorientiert beschriebenes Systemmodell: a) Extrahieren aller aktiven Objekte des objektorientierten Systemmodells; b) Feststellen der Transitionen zwischen den Objekten; c) Erzeugen der Zustands-Warte-Relationen zwischen den aktiven Objekten; d) Ermitteln möglicher Verklemmungs-Situationen als Zyklen aufeinander wartender Instanzen von zwei oder mehr unterschiedlichen Objekten, und für jede Verklemmungs-Situation: e) Überprüfen aller möglichen Pfade, die zu einer ermittelten Verklemmungs-Situation führen und durch simulierte Ausführung des Systemmodells.

Description

Verfahren zur Bestimmung von Verklemmungen in nebenläufigen Prozessen
Die Erfindung betrifft ein Verfahren zur Bestimmung von Verklemmungen (Deadlocks) in nebenläufigen Prozessen, bei denen mindestens ein Objekt in einem Zustand auf ein anderes Objekt in einem bestimmten Zustand wartet, für ein objektorientiert beschriebenes Systemmodell eines reaktiven Systems .
Für die Entwicklung und Konstruktion reaktiver Systeme hat sich die sogenannte Unified-Modeling-Language UML zu einer Standardmodellierungssprache auf dem Gebiet des objektorientierten Designs entwickelt. Mit dieser grafischen objektorientierten computerimplementierten Sprache lassen sich nicht nur Softwareprogramme, sondern auch komplexe technische Systeme, wie zum Beispiel Kraftfahrzeuge und Flugzeuge beschreiben, und deren Funktionen verifizieren. Auf Grund der hohen Sicherheitsanforderungen in diesen Gebieten ist die Kombination einer Standardmodellierungssprache mit formalen Methoden erwünscht, um Fehlverhalten bereits in der Kontruktionsphase sicher erkennen zu können. In solchen Systemen kann es auch zu Verklemmungen (Deadlocks) in zyklischen Prozessen kommen. Ein Deadlock ist in der Informatik ein Zustand von Prozessen, bei dem mindestens zwei Prozesse untereinander auf Betriebsmittel warten, die dem jeweils anderen Prozess zugeteilt sind. Hierdurch blockieren sich beide Prozesse gegenseitig. Eine Verklemmung kann dann nur durch Beendigung einzelner Prozesse oder Neustart des Sy stems beseitigt werden. Beides kann in sicherheitskritischen System sehr problematisch sein.
Deadlocks können bei Systemen eintreten, die fähig sind mehrere Prozesse parallel ablaufen zu lassen (Multitasksysteme) und bei denen die Reihenfolge der Betriebsmittelvergabe nicht festgelegt ist. Beispielsweise aus T. Schäfer, A. Knapp und S. Merz: "Model Checking UML State Machines and Collaborations", in: Electronic Notes in Theoretical Computer Science 47 (2001) , pp. 1 - 13 ist ein Verfahren zum Nachweis der Deadlock- Freiheit sowie anderer Modell-Eigenschaften für relativ kleine Systeme mit der Methodik des Model-Checking beschrieben. Dies sind spezialisierte Computerprogramme, die nachteilig eine Transformation des Systems in eine Modelchecker-Eingabesprache erfordern. Dabei wird jeder Zustand eines Zustandsautomatens durch einen individuellen Prozess modelliert. Für jeden Zustandsautomaten des UML- Systemmodells dienen zwei zusätzliche Prozesse zum Ausgeben von Ereignissen, die in einer Ereigniswarteschlange abgespeichert sind, und zur Behandlung von Transitionen. Für die Überprüfung objektorientierter Systemmodelle ist jedoch eine aufwendige Transformation in die verfügbaren Modellierungsspräche mit stark eingeschränkter Modellierungsmächtigkeit erforderlich. Ein großes Problem stellt auch die Berücksichtigung der Datentypen von objektorientierten Modellen dar, die zu einem sehr großen Zustandsraum führen. Dadurch ist die Größe der prüfbaren Systemmodelle beschränkt.
Aufgabe der Erfindung ist es daher, ein verbessertes Verfahren zur Bestimmung von Verklemmungen in nebenläufigen
Prozessen für objektorientiert beschriebene Systemmodelle von reaktiven Systemen zu schaffen.
Die Aufgabe wird gelöst durch die Schritte:
a) Extrahieren aller aktiven Objekte des objektorientierten Systemmodells;
b) Feststellen mindestens der von den aktiven Objekten konsumierten und/oder produzierten Ereignissen, der
Transitionen zwischen den Objekten und von Wächterbedingungen von Zustandsautomaten des UML-Systemmodells zur Beschreibung des Systemmodells zur Beschreibung des Zustandsverhaltens der Objekte;
c) Erzeugen der Zustands-Warte-Relationen zwischen den aktiven Objekten aus den Ereignissen als Liste von Objekten, die in einem definierten Zustand auf ein anderes Objekt in einem definierten Zustand warten;
d) Ermitteln möglicher Verklemmungs-Situationen als Zyklen aufeinander wartender Instanzen von zwei oder mehr unterschiedlichen Objekten, wobei in dem Zyklus kein Objekt mit mehr als einem Zustand involviert ist und keines der Objekte des Zyklus auf ein Objekt außerhalb des Zyklus wartet; und für jede Verklemmungs-Situation;
e) Überprüfen aller möglichen Pfade die zu einer ermittelten Verklemmungs-Situation führen und aus den Zustandsautomaten des UML-Systemmodells abgeleitet werden, durch simulierte Ausführung des UML-Systemmodells unter Berücksichtigung der Ereignisse und aktivierten Transitionen zur Analyse der Erreichbarkeit der ermittelten möglichen Verklemmungs-Situationen .
Mit einem solchem Verfahren ist der Nachweis der Deadlock- Freiheit für große objektorientierte Systemmodelle technischer reaktiver Systeme mit vielen parallelen Komponenten unter Berücksichtigung komplexer Datentypen möglich.
Gemäß der vorliegenden Erfindung wird ein mehrstufiges
Prüfverfahren vorgeschlagen. Mit den Schritten a) und b) werden die für einen Deadlock relevanten Eigenschaften eines Systemmodells extrahiert und hieraus im Schritt c) ein Zustands-Warte-Diagramm erzeugt, das später statistisch analysiert werden kann, um herauszufinden, welche "Warte- Auf"-Relationen zwischen aktiven Objekten existieren. Dabei werden die internen Zustände der aktiven Objekte beschrieben. In einer zweiten Phase werden die möglichen Verklemmungs- Situationen ermittelt. Sofern keine Verklemmungs-Situationen gefunden wurden, ist das Verfahren beendet und das Ergebnis kann dargestellt werden. Ansonsten erfolgt in einer dritten Phase die Analyse der Erreichbarkeit der ermittelten möglichen Verklemmungs-Situationen durch Berechnung der möglichen Pfade in die erkannten potentiellen Verklemmungs- Situationen, die in der vorhergehenden Phase aufgefunden wurden, unter Verwendung eines Suchalgorhithmus . Dann wird analysiert, ob diese Pfade durch einen heuristischen Simulationsansatz ausführbar sind.
Aktive Objekte im Sinne der Erfindung sind in der Systemmodellierungssprache verwendete Sprachmittel zur Beschreibung von Prozessen. Ein aktives Objekt im objektorientierten Modell entspricht einem nebenläufigen Prozess des modellierten technischen reaktiven Systems. Ein nebenläufiger Prozess kann unter Umständen zyklisch sein. Dies ist bei reaktiven Systemen häufig der Fall, aber keine notwendige Bedingung für die Anwendung des Verfahrens.
Vorzugsweise werden im Schritt a) des Extrahierens aller aktiven Objekte die aktiven Objekte aus einer statischen und dynamischen Struktursicht des Systemmodells extrahiert und in einer Objekt-Liste gespeichert.
Vorteilhaft ist, wenn dann für jedes aktive Objekt eine zugeordnete Klasse in einer Klassen-Liste abgespeichert wird und für jede Klasse in der Klassen-Liste das zugehörige Zustandsdiagramm zur Spezifikation eines Zustandsautomaten ausgewertet wird. Die spezifizierten Zustandsautomaten können dann in einer Zustandsautomaten-Liste abgespeichert werden.
Auf diese Weise wird eine mathematische Listenstruktur bereitgestellt, die eine effektive analytische Auswertung ermöglicht. Die Ermittlung der möglichen Verklemmungs-Situationen erfolgt vorzugsweise mit einem an sich bekannten Tiefensucheverfahren (Depth-First-Search) .
Die Überprüfung der Erreichbarkeit der ermittelten möglichen Verklemmungs-Situationen erfolgt vorzugsweise heuristisch, in dem ausgehend von einem initialen Zustand des Systemmodells die jeweils aktivierten Transitionen ermittelt werden und diejenige aktivierte Transition ausgewählt wird, welche das Systemmodell näher an das Verklemmungs-Ereignis heranbringt.
Aktivierte Transitionen liegen beispielsweise dann vor, wenn die Wächterbedingung für das zugeordnete Objekt wahr ist und das Ereignis des Objektes in einer Eingabewarteschlange liegt.
Vorzugsweise wird der Schritt e) des Überprüfens aller möglichen Pfade für jede Verklemmungs-Situation (Phase C) , solange iterativ durchgeführt, bis entweder ein Verklemmungs- Zustand erreicht ist oder alle Pfade eine festgelegte Anzahl durchlaufen wurden.
Das Systemmodell wird besonders bevorzugt mit der Unified- Modeling-Language UML beschrieben.
Die Aufgabe wird weiterhin durch ein Computerprogramm mit Programmcodemitteln zur Durchführung des oben beschriebenen Verfahrens gelöst, wenn das Computerprogramm auf einem Rechner ausgeführt wird.
Die Erfindung wird nachfolgend an Hand der beigefügten Zeichnungen beispielhaft näher erläutert. Es zeigen:
Figur 1 - Flussdiagramm des erfindungsgemäßen Verfahrens zur Bestimmung von Verklemmungen; Figur 2 - Statische Systemstruktur (Klassendiagramm) eines beispielhaften Messsystemmodells;
Figur 3 - Dynamische Systemstruktur des beispielhaften Messsystemmodells aus Figur 2;
Figur 4 - der Detailansicht des Verhaltens des Controllers des beispielhaften Messsystemmodells
Figur 5 - Detailansicht des Verhaltens des ersten Sensors des beispielhaften Messsystemmodells;
Figur 6 - Detailansicht des Verhaltens des zweiten Sensors des beispielhaften Messsystemmodells;
Figur 7 - Detailansicht des Verhaltens der Uhr des beispielhaften Messsystemmodells;
Figur 8 - Detailansicht des Verhaltens des Benutzers des beispielhaften Mess- Systems
Figur 9 - Zustands-Warte-Graph eines beispielhaften
Durchlaufs zur Erkennung potentieller Verklemmungen;
Figur 10 - Sequenzdiagramm zur Darstellung des
Analyseergebnisses des erfindungsgemäßen Verfahrens am
Beispiel des Messsystemmodells.
Die Figur 1 lässt ein Flussdiagramm des erfindungsgemäßen mehrphasigen Verfahrens zur Bestimmungen von Verklemmungen
(Deadlocks) in nebenläufigen Prozessen erkennen.
Ausgangspunkt ist ein mit der Unified-Modeling-Language UML grafisch und objektorientiert beschriebenes Systemmodell, nachfolgend UML-Systemmodell genannt. Das Verfahren ist gleichermaßen für andere Beschreibungssprachen geeignet, die technische Systeme objektorientiert beschreiben. In einer ersten Phase a) erfolgt eine Extraktion der aktiven Objekte des UML-Systemmodells, sowie deren Eigenschaften und Relationen. Die für eine Verklemmung relevanten Eigenschaften des UML-Systemmodells werden dabei extrahiert und in mathematische Strukturen, wie zum Beispiel Listen, Mengen und Tupel abgespeichert, die eine Auswertung mit einem effektiven Algorithmus in den nachfolgenden Phasen ermöglichen.
Bei der Extraktion werden alle aktiven Klassen des UML- Systemmodells hinsichtlich ihrer Kommunikationseigenschaften analysiert. Konkret bedeutet dies, dass für jede aktive Klasse ein Satz von erzeugten Ereignissen und konsumierten Ereignissen berechnet und in Erzeuger-Ereignis-Listen und Verbraucher-Ereignis-Listen abgespeichert wird. In dieser
Hinsicht werden Aufruf-Ereignisse als Verbraucher-Ereignisse und Aufrufaktionen als Erzeuger von Ereignissen angesehen. Ereignisse werden nur dann berücksichtigt, wenn ihre Erzeuger und Verbraucher geeignet assoziiert sind.
In einer zweiten Phase b) erfolgt eine Analyse zur Erkennung potentieller Verklemmungs-Ereignisse. Diese Analyse kann durch statische Auswertung eines UML-Zustandsdiagramms erfolgen, um herauszufinden, welche Warte-Relationen zwischen den aktiven Objekten existieren. Für diesen Zweck wird ein Zustands-Warte-Graph eingefügt, der im Unterschied zum klassischen Wartegraphen den internen Zustand der aktiven Objekte wiedergibt. Die Detektion von Zyklen in dem Zustands- Warte-Graphen initiiert die Existenz und den Ort potentieller Verklemmungen.
Eine potentielle Verklemmung ist eine zyklische Wartesituation zwischen konkurrierenden oder parallelen Komponenten eines Systems, die sich jeweils innerhalb eines spezifischen Zustands befinden. Die potentiellen
Verklemmungen können in einem Zustands-Warte-Graphen erkannt werden. Dies ist ein gerichteter Graph, in dem jeder Knoten ein aktives Objekt in einem spezifischen Zustand (des zugeordneten Zustandsdiagramms) und jede Kante eine "Warteauf"-Relation darstellt. Die Anzahl der Scheitelpunkte des Zustands-Warte-Graphen ist die gleiche wie die Anzahl von Zuständen aller Zustandsdiagramme des Modells, die aktiven Klassen zugeordnet sind. Die Anzahl der Kanten hängt von den in diesen Zustandsdiagrammen definierten Transitionen ab. Der Kopf jeder Kante ist mit dem auf ein spezifisches Ereignis wartenden Knoten verbunden. Der mit dem Ende der Kante verbundene Knoten ist ein potentieller Urheber dieses speziellen Ereignisses.
Die Analyse potentieller Verklemmungs-Situationen startet mit der Erzeugung eines Zustands-Warte-Graphen. Dies wird durch Berechnung der in der Phase der Extraktion der aktiven
Objekte und deren Eigenschaften und Relationen, zum Beispiel durch Berechnung von Konsumenten- und Produzenten-Listen durchgeführt. Nach Erzeugung des gesamten Zustands-Warte- Graphen des Systems können potentielle Verklemmungs- Situationen detektiert werden. Eine potentielle Verklemmungs- Situation ist eine Situation, in dem zwei oder mehrere Objekte jeweils in einem spezifischen Zustand gegenseitig auf die Erzeugung eines bestimmten Ereignisses warten.
Bei dem erfindungsgemäßen Verfahren werden nunmehr in der
Phase b) alle Zyklen in dem Zustands-Warte-Graphen detektiert und die relevanten Zyklen aussortiert. Dabei sind Zyklen keine potentiellen Deadlocks, sondern logische Fehler in dem korrespondierenden Zustandsdiagramm, bei denen alle Knoten des Zykluses dasselbe Objekt sind. Zyklen mit zwei oder mehr Knoten unterschiedlicher Objekte sind hingegen potentielle Deadlock-Situationen, wenn kein Objekt mit mehr als einem Zustand in dem Zyklus involviert ist. Andernfalls handelt es sich um Zyklen mit "über-beteiligten" Objekten. Die Detektion aller Zyklen in dem Zustands-Warte-Graphen wird mit einem verbesserten an sich bekannten Tiefensuchalgorithmus (Depth- First-Search Algorhythm) durchgeführt, der alle Zyklen des Graphen und die Aufteilung in einem einzigen Durchlauf berechnet. Die Erkennung logischer Fehler und Zyklen mit "über-beteiligten" Objekten wird unter Verwendung von Mengen- Operationen (Set-Operations) durchgeführt. Anschließend werden die verbleibenden potentiellen Deadlock-Situationen hinsichtlich der abgehenden Kanten untersucht. Dies wird durch Durchquerung des Graphen und Berechnung des Ausgangsgrades von jedem Knoten durchgeführt. Der Ausgangsgrad ist die Anzahl der vom Knoten abgehenden Kanten. Wenn alle Knoten einen Ausgangsgrad von eins haben, liegt eine potentielle Deadlock-Situation im Sinne der Erfindung vor. Falls Knoten mit einem Ausgangsgrad von mehr als eins vorhanden sind, hängt es von dem Zielobjekt der aus dem Zyklus herausweisenden Kante ab, ob der untersuchte Zyklus ein potentieller Deadlock ist. Wenn das Zielobjekt nicht in den betrachteten Zyklus involviert ist, handelt es sich bei dem untersuchten Zyklus nicht um einen Deadlock. Andernfalls muss überprüft werden, ob die Kanten zwei Zustände des gleichen Objektes verbinden. Falls bei dieser Überprüfung festgestellt wird, dass die Kanten zwei Zustände des gleichen Objektes verbinden, wird der potentielle Deadlock mit einem logischen Fehler kombiniert und der logische Fehler sollte korrigiert werden, bevor die Deadlock-Erkennung weitergeführt wird. Ansonsten wird ein weiterer Zyklus in dem Zustands- Warte-Graphen erkannt, der später auszuwerten ist. In diesem Fall kann die nächste Phase c) initiiert werden, da die Zyklendetektion sicherstellt, dass alle Zyklen aufgefunden und separat in der weiteren Analyse der Erreichbarkeit der potentiellen Verklemmungs-Situationen abgearbeitet werden.
Potentielle Verklemmungs-Situation (Deadlock) bedeutet, dass es statistisch möglich ist, dass ein Deadlock auftritt. Ob das Deadlock-Ereignis tatsächlich während der Laufzeit eintritt hängt jedoch von dynamischen Aspekten des Systemmodells ab, die in der nächsten Phase c) der Analyse der Erreichbarkeit der potentiellen Verklemmungs-Situationen separat von der Phase b) der Analyse zur Erkennung potentieller Verklemmungs-Situationen untersucht wird.
Falls keine potentiellen Verklemmungs-Situation in der Phase b) aufgefunden werden, ist das System verklemmungsfrei und die nächste Phase c) kann übersprungen werden.
In der Phase c) erfolgt dann die Analyse der Erreichbarkeit der potentiellen Verklemmungs-Situationen. Hierbei wird jedes in der Phase b) erkannte potentielle Verklemmungs-Situation untersucht, indem die möglichen Pfade in die potentiellen Verklemmungs-Situationen unter Verwendung eines Suchalgorithmus berechnet und dahingehend mit einem heuristischen Simulationsansatz analysiert werden, ob diese Pfade ausführbar sind. Der Suchalgorithmus führt eine spezialisierte Tiefensuche für jedes relevante Zustandsdiagramm durch und speichert alle Pfade zu potentiellen Verklemmungs-Situationen in einer Pfadliste. Jede Pfadliste enthält alle Zustände und Transitionen des jeweiligen Pfades.
Die Pfadlisten werden als Eingangsdaten für die nachfolgende heuristische Simulation genutzt. In der Simulation werden die Zustandsautomaten des UML-Systemmodells mit einem Simulator ausgeführt, der die exakte UML-Semantik gemäß OMG-Standard (www.omg.org) implementiert. Neben sehr speziellen Merkmalen, wie die Warteschlangenlänge und die Untersuchungsreihenfolge von in den Semantiken definierten Ausdrücken müssen die folgenden Aspekte des Modells berücksichtigt werden:
Wächterbedingungen, Ereignisparameterwerte und Atributwerte.
Für den Fall, dass eine oder mehrere Pfade in eine potentielle Deadlock-Situation vorhanden sind, ist es ausreichend, einen ausführbaren Pfad während der Simulation aufzufinden. Der andere Fall ist wesentlich aufwendiger. Wenn alle Pfade der Pfadliste einmal ausgeführt wurden und dabei kein ausführbarer Pfad aufgefunden wurde kann nicht gefolgert werden, ob ein ausführbarer Pfad vorhanden ist oder nicht. Auch nach theoretisch unendlich vielen Ausführungen kann nicht mit abschließender Sicherheit ausgesagt werden, dass die nächste Ausführung nicht in eine potentielle Deadlock- Situation führt. Es wird daher vorgeschlagen, die Simulation nach einer festlegbaren Anzahl n von Ausführungen abzubrechen .
Der Nachteil dieses heuristischen Simulationsansatzes ist, dass die Nichtexistenz von Deadlocks nicht bewiesen werden kann, falls potentielle Verklemmungs-Situationen vorliegen, die in der Phase c) nicht erreichbar sind, d. h. bei denen kein ausführbarer Pfad nach einer Anzahl n Simulationen aufgefunden wurde. In diesem Ausnahmefall hilft nur eine aufwendige Suche über einen vollständig ungefalteten Zustandsraum zur Modellprüfung.
In der letzten Phase d) werden die Analyseergebnisse dann dargestellt. Dies kann beispielsweise mit einem erweiterten UML-Sequenzdiagramm erfolgen.
Das erfindungsgemäße Verfahren wird nachfolgend an Hand eines Beispiels eines Mess-Systemmodells beschrieben, das aus einem ersten und zweiten Sensor Sensorl und Sensor2, einer
Steuerungseinheit Controller sowie einer Uhr besteht. Die Sensoren Sensorl, Sensor2 verfügen über eine Messeinheit, die die eigentliche Messung durchführt und deren Verhalten im Mess-Systemmodell abstrahiert wird. Die Uhr verfügt über ein Uhrwerk, dass das Fortschreiten der Zeit modelliert und bei Aufruf den aktuellen Zeitpunkt zurückliefert. Auch von der exakten Funktionsweise der Uhr wird im Mess-Systemmodell abstrahiert. Die Uhr wird von den Sensoren Sensorl, Sensor2 benötigt, um die Messwerte mit Zeitstempeln zu versehen. Die Steuerungseinheit Controller ist für das Starten der
Komponenten zuständig und fragt zur Laufzeit des Systems immer wieder beide Sensoren Sensorl, Sensor2 ab. Das System kann durch den Benutzer gestartet und gestoppt werden. Das Verhalten des Benutzers kann zu Analysezwecken modelliert werden .
Die Figur 2 lässt die statische Systemstruktur des Mess- Systemmodells in Form eines Klassendiagramms erkennen.
Die im Klassendiagramm verwendeten Zeichnen + und - stehen für die Sichtbarkeit des Elements, dem sie vorangestellt sind. Alle mit „+" annotierten Elemente (Operationen und/oder Attribute) sind als öffentlich (public) deklariert. Diese sind für alle anderen Klassen, die mit der betreffenden Klasse assoziiert sind, sichtbar. Elemente, die mit „-" annotiert sind, sind privat (private) und deshalb nur innerhalb der betreffende Klasse sichtbar. D. h., dass die privaten Elemente zwar von der Klasse selbst zum Beispiel im zugehörigen Zustandsdiagramm aufgerufen werden können, aber nicht von anderen Klassen. Im Beispiel sind alle Operationen der Klassen öffentlich, d. h. mit „+> deklariert. Nur die Attribute, die zum Speichern von Werten dienen sind privat mit ,,-■" deklariert. Dies entspricht dem Geheimnisprinzip in der objektorientierten Modellierung und bewirkt, dass die Werte der Attribute von Klassen nur mit deren Operationen manipuliert werden können, und schränkt die Gefahr von Seiteneffekten ein.
Es wird deutlich, dass der Benutzer in einer Anfrage "Gebe_Messwert" für zwei Werte Wert 1, Wert2 stellt, die dieser vom Controller als Parameter zurückerhält. Der Controller startet den Messprozess mit dem Befehl "+Start()" und fordert Messwerte des ersten und zweiten Sensors Sensorl, Sensor2 an (Gebe_Messwert_Sensorl, Gebe_Messwert_Sensor2) .
Die Anfrage wird über die Komponente Sensor an die Messeinheit weitergeleitet, die die eigentliche Messung durchführt, wobei ein Zeitstempel mit dem Befehl "Gebe Zeitstempel" von der Uhr bei der Messung für jeden Sensor Sensorl, Sensor2 abgefragt wird. Die Messwerte werden über die Sensoren Sensorl, Sensor2 zusammen mit dem Zeitstempel an den Controller und über diesen an den Benutzer zurückgeschickt .
Die Figur 3 lässt ein Blockdiagramm der dynamischen Systemstruktur des Mess-Systemmodells erkennen. Es wird deutlich, dass der Controller zur Parametrierung der Uhr genutzt wird, die ihrerseits die Zeitmessungen Zeitmessung 1, Zeitmessung 2 bei der Messung durch die Sensoren Sensorl, Sensor2 vornimmt. Die Messwerte werden zusammen mit dem Zeitstempeln als Signale Messung 1, Messung 2 an den Controller und über diesen an die Umgebung eines Benutzers zurückgeschickt .
Das Verhalten der einzelnen Systemelemente ist wie folgt:
Die Figur 4 lässt die Verhaltenssicht des Controllers als Diagramm erkennen. Nach der Initialisierung parametrisiert der Controller die Uhr und startet diese mit dem Befehl
"Start/Uhr . Start" . Weiterhin wird die erste Messung (Messung 1) durch den Befehl "Sensor.Anfrage_Messwert" angestoßen. Anschließend wird der Messwert des ersten Sensors abgefragt (Gebe_Messwert_Sensorl (Messwert) /Messwert l:=Messwert) und die zweite Messung (Messung 2) durch den zweiten Sensor (Sensor2) mit dem Befehl "Sensor2.Anfrage_Messwert" angestoßen. Von der zweiten Messung (Messung 2) erfolgt eine Rückkopplung zur ersten Messung (Messung 1) mit den Anfragen "Gebe_Messwert_Sensor2 (Messwert) /Messwert 2 :=Mess-wert" der erneuten Anfrage des Messwerts bei Sensorl durch den Befehl "Sensorl .Anfrage_Messwert" sowie gegebenenfalls die Weitergabe der Messwerte an den Benutzer durch den Befehl "Benutzer. Gebe_Messwert (Messwert 1, Messwert 2)".
Diese Schleife wird solange durchlaufen, bis Stoppsignale für die Uhr, den Sensorl und den Sensor2 ausgeschickt werden (Stop/Uhr. Stop) ; Sensorl .Stop; Sensor2. Stop). Die Figur 5 lässt die Verhaltenssicht des Sensorsl erkennen. Nach Initialisierung erfolgt die Messung mit einer Anfrage nach dem Zeitstempel bei der Uhr mit dem Befehl "Anfrage_Messwert/Uhr .Anfrage_Zeitstempel_Sensorl" . Das Ergebnis des Zustands Hole_Zeit ist die Weitergabe des Zeitstempels an den Sensorl zur Verknüpfung mit dem Messwert Sensorl (Gebe_Zeitstempel/Aktuell :=Messeinheit . MessungO; Controller .Gebe_Messwert_Sensorl (Aktuell) .
Nach Erhalt des Stopp-Signals "Sensorl .Stop" wird der Zustand "Messen" beendet.
Die Figur 6 lässt eine entsprechende Verhaltenssicht des Sensors2 erkennen. Für die Erläuterung wird das vorher gesagte verwiesen.
Die Figur 7 lässt die Verhaltenssicht der Uhr erkennen. Nach Initialisierung erfolgt der Zustand der Parametrierung der Uhr durch den Controller und es wird mit dem Signal "Start" ein laufender Zustand "laufend" angeregt. Dieser Zustand gibt einen Zeitstempel an den Sensorl (Sensorl .Gebe_Zeitstempel (Zeitstempel) ) weiter und beantwortet die Anfrage nach einem Zeitstempel durch den Sensor2 durch Setzen des Zeitstempels auf die aktuelle Uhrzeit des Uhrwerks (Anfrage_Zeitstempel_Sensor2/Zeitstempel :=Uhrwerk.aktuelle_Ze it()). Solange ein Zustand "Anfrage_l" noch eine Anfrage nach einem Zeitstempel durch einer der Sensoren Sensorl, Sensor2 feststellt, wird mit den Befehlen "Anfrage_Zeitstempel_Sensor2/Zeitstempel :=Uhrwerk.Aktuelle_Ze it" der Zeitstempel für den Sensor2 festgestellt und dem Sensor2 mit dem Befehl
"Sensor2.Gebe_Zeitstempel (Zeitstempel) " ein Zeitstempel zugeordnet .
Ansonsten wird mit dem Befehl "Stop" der Zusand gestoppt. Die Verhaltenssicht des Benutzers ist in der Figur 8 dargestellt. Nach der Initialisierung wird im Zustand "Starte" durch den Befehl "Controller .Start" die Steuerungseinheit gestartet und der Zustand "Beobachter" aufgerufen, indem das Ereignis "Gebe-Messwert" von der
Steuerungseinheit abgefordert wird. In dem anschließenden Zustand "Beobachter2" wird auf den Messwert von der Steuerungseinheit gewartet und in einer Schleife durch die Anfrage "Gebe-Messwert" von der Steuerungseinheit weitere Messwerte abgefordert. Der Zustand wird durch den Befehl "Controller. Stop" an die Steuerungseinheit beendet.
Für dieses beispielhafte Mess-Systemmodell wird nun zurückkommend auf die Figur 1 auf die Phasen a) bis d) im einzelnen eingegangen.
In der Phase a) der Merkmalsextraktion werden die für die Deadlock-Detektion benötigten Merkmale aus dem UML- Systemmodell extrahiert und in den im folgenden dargestellten Strukturen gespeichert.
Zunächst wird unter Berücksichtigung der statischen und dynamischen Struktursicht (Klassen- und Objektdiagramme) ermittelt, welche Komponenten des Systems bei der Analyse zu berücksichtigen sind. Da dies von der Art des UML- Systemmodells abhängt, muss das UML-Systemmodell in einer speziellen Form (UML-Dialekt) vorliegen. Im vorliegendem Beispiel wird von der Erzeugung der einzelnen Komponenten des Systems abstrahiert. Es wird davon ausgegangen, dass beim Start des Gesamtsystems alle aktiven Objekte erzeugt werden und über alle Eigenschaften verfügen, die im Klassendiagramm für die zugehörigen Klassen modelliert wurden. Die Links (Instanzen der Assoziationen zwischen den Klassen) zwischen den Objekten haben die Eigenschaften, die die zugehörigen Assoziationen im Klassendiagramm tragen. Ferner wird davon ausgegangen, dass bei der Instanziierung von Objekten, die ihnen durch Kompositionsbeziehungen zugeordneten Objekten ebenfalls instanziiert werden. Deshalb sind alle im Objektdiagramm dargestellten Objekte gerade die in der Detektion zu berücksichtigenden.
Je nach Einsatzgebiet der Unified Modeling Language bzw. dem entsprechenden UML-Profil kann dieser Teil der Merkmalsextraktion unterschiedlich ausfallen. Dies ist jedoch nicht Gegenstand der vorliegenden Erfindung.
Nachdem aus dem Objektdiagramm alle aktiven Objekte extrahiert und in einer Objekt-Liste gespeichert wurden, wird diese Liste genau einmal durchlaufen, und zu jedem Objekt die dazugehörige Klasse in einer Klassen-Liste gespeichert. Die Länge der Klassen-Liste wird als Anzahl_Klassen gespeichert. Dann wird zu jeder Klasse in der Klassen-Liste, d. h. den aktiven Klassen, das dazugehörige Zustandsdiagramm analysiert und der dort spezifizierte Zustandsautomat in der Zustandsautomaten-Liste gespeichert.
Anschließend werden alle Objekte an Hand der zugeordneten Klassen in der Klassen-Liste hinsichtlich ihrer produzierten Aktionen untersucht. Dazu muss jeweils der richtige Zustandsautomat aus der Zustandsautomaten-Liste selektiert werden und alle Transitionen der Reihe nach untersucht werden. Jede Transition kann 0 bis n=beliebig viele Aktionen auslösen. Von den verschiedenen Typen der Aktionen, die in der UML-Sprache definiert sind, werden vom Verfahren nur die Aufruf-Aktionen (Call Actions) berücksichtigt. Ferner kann das Verfahren optional auch Signal-Aktionen (Send Aktions) berücksichtigen. Da in der Regel je nach Art der Modellierung nur einer der beiden Typen von Aktionen verwendet werden, wird das Verfahren nachfolgend nur hinsichtlich der Aufruf- Aktionen beschrieben. Die gefundenen Aufruf-Aktionen werden in einer Aktionen- Tabelle gespeichert, die wie folgt aufgebaut ist:
Objekt Aktion Objekt 1 { [Zustand, Zielobjekt, Zielereignis] , ... }
Dabei ist in der Aktionen-Tabelle unter dem Eintrag Objekt der Objektnahme zu finden und unter dem Eintrag Aktion eine Menge von 0 bis m Aktionen, die jeweils aus den Komponenten Zustand, Zielobjekt und Zielereignis bestehen. Die Anzahl m ist die Anzahl der Aktionen, die durch eine Transition ausgelöst werden können. Der Zustand ist der Zustand des Zustandsautomaten, in dem das Objekt die Aktion erzeugen kann, wenn die dazugehörige Transition schaltet. Das Zielobjekt ist das Objekt, an dass die Aufruf-Aktion adressiert ist. Das Zielereignis ist das Ereignis (Event) des Zielobjekts, das dabei erzeugt und in dessen Eingabe Warteschlange (Input-Queue) gelegt wird.
Danach wird eine Wartemengen-Tabelle erzeugt. Diese ergibt sich, indem für jedes Objekt aus der Objekt-Liste über die dazugehörige Klasse aus der Klassen-Liste der zugehörige Zustandsautomat aus der Zustandsautomaten-Liste selektiert und festgestellt wird, auf welche Ereignisse (Events) das Objekt in welchem Zustand wartet und welches Objekt das jeweilige Ereignis erzeugen kann. Die Information, welches Objekt das jeweilige Ereignis erzeugen kann, wird aus der Aktionen-Tabelle entnommen.
Die Wartemengen-Tabelle hat die folgende Form:
Objekt Wartemenge
Objekt 1 [Zustand 1, (Objekt 2. Zustand 1, Objekt 2. Zustand
2)], [Zustand 2, (Objekt 3. Zustand 2)] ...
Dabei ist unter dem Eintrag Objekt analog zu einer Aktionen- Tabelle der Objektname verzeichnet. Die Wartemenge ist so strukturiert, dass zu jedem Zustand des Zustandsautomaten des Objekts eine Menge von Objekt-Zustandskombinationen gespeichert werden kann. Eine Objekt-Zustandskombination hat die Form „Objekt. Zustand", wobei hierbei "Objekt" das Objekt bezeichnet, auf das gewartet wird und "Zustand" den Zustand, auf den gewartet wird.
In der oben genannten Tabelle wartet zum Beispiel das Objekt 1 in Zustand 1 auf das Objekt 2 in Zustand 1 und das Objekt 2 in Zustand 2. Wie jede andere Menge in der Mathematik ist auch die Wartemenge frei von Duplikaten.
Nach Erstellung der Wartemengen-Tabelle werden alle Ergebnisse der Merkmalsextraktion in einer Struktur „Modell- Merkmale" zusammengefasst, die einen effizienten Zugriff auf alle Merkmale zuläßt und diese in den anderen Phasen b) , c) und d) zur Verfügung stellt.
Für das beispielhafte Messsystemmodell sind die Ergebnisse der Merkmalsextraktion die folgenden:
Anzahl-Klassen = 5
Objekt-Liste = [Ben->Objekt, Con->Objekt, Snl->Objekt, Sn2- >Objekt, U->Objekt]
Klassen-Liste = [Benutzer->Klasse, Controller->Klasse, Sensorl->Klasse, Sensor->Klasse, Uhr->Klasse]
Aktionen-Tabelle:
Objekt Aktion Ben ([Start, Con, Start])
Con ([Parametrierung, U, Start], [Messungl, Sn2, Anfrage_Messwert] , [Messung2, Ben, Gebe_Messwert] , [Messung2, Snl, Anfrage_Messwert] , [Messung2, Uhr, Stop], [Messung2, Snl, Stop], [Messung2, Sn2, Stop]) Snl
([Messen, U, Anfrage _Zeitstempel_Sensorl] , [Hole_Zeit, Con,
Gebe_Messwert-Sensorl] )
Sn2 ([Messen, U, Anfrage-Zeitstempel_Sensor2] , [Hole_Zeit,
Con, Gebe_Messwert_Sensor2] )
U ([Laufend, Snl, Gebe_Zeitstempel] , [Anfrage_Eins, Sn2,
Gebe_ZeitStempel] )
Wartemengen-Tabelle :
Objekt Wartemenge Ben [Beobachte, (Con.Messung2) ] , [Beobachte2, (Con.Messung2) ]
Con [Parametrierung, (Ben. Starte) ] , [Messungl, (Snl.Hole_Zeit) ] , [Messung2, (Ben.Beobachte2) ] Snl [Messen, (Con.Messung2) ] , [Hole_Zeit, (U. Laufend)] Sn2 [Messen, (Con.Messungl) ] , [Hole_Zeit, (U.Anfrage_Eins) ] U [Parametrierung, (Con. Parametrierung) ] , [Laufend, (Sn2.Messen) ] , [Anfrage_Eins, (Sn2.Messen, Con .Messung2) ] ,
Nach der Erstellung der Wartemengen-Tabelle werden diese Merkmale in der Struktur „Modell-Merkmale" zusammengefasst und den weiteren Phasen b) , c) und d) des Verfahrens zur Verfügung gestellt. Hierdurch wird ein effizienter Zugriff auf die verschiedenen Merkmale ermöglicht.
In der Phase b) „Potentielle Deadlock Detektion" wird aus der Wartemengen-Tabelle ein sogenannter Zustands-Wartegraph (State-Wait-Graph) erzeugt. Dies ist ein Graph, dessen Knoten Objekt-Zustandskombinationen bezeichnen und dessen Kanten „Warte-Auf"-Beziehungen (Wait-For-Relations) bezeichnen. Aus diesem Graph lassen sich Aussagen wie Objekt 1 wartet in
Zustand 1 auf Objekt 2 in Zustand 1, etc. treffen. Analog zu den Wartemengen sind die Kantenmengen von Graphen duplikatsfrei. Dies vereinfacht die Anwendung von Algorithmen auf Graphen und verringert deren Komplexität.
Eine potentielle Verklemmungs-Situation (Deadlock) im Sinne des betrachteten Verfahrens ist eine zyklische „Warte-Auf"- Beziehung mit einigen weiteren Eigenschaften.
Die Phase b) der Analyse zur Erkennung potentieller Verklemmungs-Situationen arbeitet in zwei Stufen. In der ersten Stufe wird eine Zyklenerkennung auf dem Zustands- Warte-Graph durchgeführt. Das Ergebnis ist eine Menge potentieller Verklemmungs-Situationen. In der zweiten Stufe werden diejenigen potentiellen Verklemmungs-Situationen aus der Menge der potentiellen Deadlocks ausgesondert, welche die folgenden Eigenschaften aufweisen:
a) ein Objekt ist mit mehreren Zuständen am Deadlock beteiligt; b) es existiert eine Kante zu einem Objekt, das am Deadlock nicht beteiligt ist; c) nur ein Objekt ist am Deadlock beteiligt.
Alle nicht ausgesonderten Verklemmungs-Situationen bilden die endgültige Menge der potentiellen Deadlocks.
Das Verfahren zur Zyklenerkennung basiert auf dem allgemein bekannten Tiefensucheverfahren (Depth-First-Search) .
Die Figur 9 lässt einen beispielhaften Zustands-Wartegraphen für das Messsystemmodell erkennen.
Nach der Zyklenerkennung ist die Menge der potentiellen Deadlocks wie folgt:
( (Ben.Beobachte2, Con.Messung2) , (Con.Messungl, Snl.Hole Zeit, U. Laufend, Sn2.Messen)) Nach Aussonderung ist die Menge potentieller Deadlocks reduziert wie folgt:
( (Con.Messungl, Snl .Hole_Zeit, U. Laufend, Sn2. Messen))
Die potentielle Verklemmungs-Situation (Ben.Beobachte2, Con.Messung2) wurde ausgesondert, weil eine Kante im Zustands-Wartegraphen von Con.Messung2 nach Sn2.Hole_Zeit existiert und deshalb für ihn die oben genannte Bedingung b) erfüllt ist, d. h. dass eine Kante zu einem Objekt existiert, das am Deadlock nicht beteiligt ist.
Die finale Menge potentieller Deadlocks wird an die nächste Phase c) der Analyse der Erreichbarkeit der potentiellen Verklemmungs-Ereignisse übergeben.
Die „Deadlock-Erreichbarkeitsanalyse" dient dem Nachweis, dass die gefundenen potentiellen Deadlocks zur Laufzeit des Systems erreichbar sind. Auch hier gibt es verschiedenen Standardverfahren, die zur Erreichbarkeitsanalyse eingesetzt werden können. Besonders wichtig für das vorliegenden Verfahren ist, dass in der Phase der Deadlock- Erreichbarkeitsanalyse nicht die Laufzeitvorteile, die durch die äußert günstige Zeitkomplexität resultieren, verschenkt werden. Die erforderliche Zeit verhält sich voraussichtlich linear zu der Anzahl der Kanten und Knoten des Zustands- Wartegraphen .
Aus diesem Grunde werden bei der Erreichbarkeitsanalyse in der Phase c) Heuristiken eingesetzt. Es werden neben den Ereignissen (Events) und Aktionen (Actions) an den Transitionen (Transitions) auch Wächter-Bedingungen (Guard- Conditions) der Zustandsautomaten berücksichtigt.
Der erste Schritt der Analyse der Erreichbarkeit der potentiellen Verklemmungs-Ereignisse ist die Berechnung der lokalen Pfade der beteiligten Objekte. Dazu werden sogenannte Pfad-Listen konstruiert, die aus den Zustandsautomaten des Modells abgeleitet werden können. Anschließend wird die Ausführung des Modells simuliert, indem ausgehend vom initialen Zustand des Modells geprüft wird, welche Transitionen jeweils aktiviert sind, d. h. welche
Transitionen schalten können. Transitionen können genau dann schalten, wenn die Wächter-Bedingung wahr ist und das Ereignis in der Eingabewarteschlange liegt. Dann wird nach einer geeigneten Heuristik jeweils diejenige Transition ausgewählt, die das Modell näher an die potentielle Verklemmungs-Situation heranbringt .
Die Simulation bricht ab, wenn die potentielle Verklemmungs- Situation erreicht wurde oder alle Pfade eine festgelegte Anzahl n mal durchlaufen wurden und kein potentieller Zustand der Verklemmung erreicht werden konnte. Im letzteren Fall kann keine Aussage gemacht werden, ob der potentielle Zustand der Verklemmung noch erreicht werden kann.
Bei der Erreichbarkeitsanalyse werden Pfadlisten und Spuren- Mengen (Traces set) generiert. Dabei haben Pfadlisten die Form:
Pfadliste = {[(ZI, Z2) , ..., (Zi, Zj ) ] , ...},
wobei (ZI, Z2) ein geordnetes Paar ist, bei dem ZI den Quellzustand einer Transition, Z2 den Zielzustand der Transition bezeichnet und Zj in der Menge der potentiellen Verklemmungs-Situationen liegt.
Ein Modellzustand für ein Modell mit einer Anzahl n von Objekten ist gegeben durch
< 0_1.Z, ..., 0_n.Z, 0_1.A_1, ..., 0_n.A_m, ES_1, ... ES_n >,
wobei 0_i, 1 < i <n, m >= n das jeweilige Objekt bezeichnet und Z den jeweils aktuellen Zustand des Objektes. A_j , 1 <= j <= m ist der aktuelle Wert des jeweiligen Attributs des betreffenden Objektes und
ES_i ist die Eingabewarteschlange von 0_i .
D. h. zu jedem Modellzustand gehört der Zustand (alle Attributwerte) sowie die Eingabewarteschlange aller Objekte.
Die Spuren-Menge ist die Menge aller Folgen
{ [M_a, (O.Z_a, O.Z_b), M_z]},
wobei M_a der initiale Zustand des Modells ist und M_z der letzte Zustand vor Abbruch der Simulation und (O.Z_a, O.Z_b) eine Transition des Objektes O von Z_a nach Z_b.
Die Ausführung von Aktionen, das Auftreten von Ereignissen etc. wird nicht mit aufgezeichnet, sondern ist an der Änderung des Modellzustandes erkennbar.
Die Ergebnisse der Erreichbarkeitsanalyse am Beispiel des Messsystemmodells sind wie folgt:
Eingabe:
Menge der potentiellen Verklemmungs-Situationen nach Aussonderung = { {Con.Messungl, Snl .Hole_Zeit, U. Laufend, Sn2.Messen} }
Ausgabe:
Pfadliste_Ben = { (Starte, Beobachte) } Pfadliste_Con = { (Parametrierung, Messungl) } Pfadliste_Snl = { (Messen, Hole_Zeit) } Pfadliste_Sn2 = { } Pfadliste U = { (Parametrierung, Laufend) } Spuren_Menge={<Ben. Starte, Con. Parametrierung, Snl. Messen, Sn2. Messen, U. Parametrierung, Con.A.Messwertl=99.9, Con.A.Messwert2=99.9, Snl .A.Aktuell=999, U.A. Zeitstempel=999, Ben.ES=[], Con.ES=[], Snl.ES=[], Sn2.ES=[], U.ES=[]>, (Ben. Starte, Ben. Beobachte) , <Ben. Beobachte,
Con. Parametrierung, Snl.Messen, Sn2.Messen, U. Parametrierung, Con.A.Messwertl=99.9, Con.A.Messwert2=99.9, Snl.A.Aktuell=999, U.A. Zeitstempel=999, Ben.ES=[], Con.ES= [Start] , Snl.ES=[], Sn2.ES=[], U.ES=[]>,
(Con. Parametrierung, Con.Messungl) , <Ben. Beobachte, Con. essungl, Snl.Messen, Sn2.Messen, U. Parametrierung, Con.A.Messwert1=99.9, Con.A.Messwert2=99.9, Snl.A.Aktuell=999, U.A. Zeitstempel=999, Ben.ES=[], Con.ES=[], Snl.ES=[Anfrage_Messwert] , Sn2.ES=[], U.ES= [Start] >,
(U. Parametrierung, U. Laufend), <Ben. Beobachte, Con.Messungl, Snl.Messen, Sn2.Messen, U. Laufend, Con.A.Messwertl=99.9, Con.A.Messwert2=99.9, Snl .A.Aktuell=999, U.A. Zeitstempel=999, Ben.ES=[], Con.ES=[], Snl .ES= [Anfrage_Messwert] , Sn2.ES=[], U.ES=[]>, (Snl.Messen, Snl .Hole_Zeit) , <Ben. Beobachte, Con.Messungl, Snl .Hole_Zeit, Sn2.Messen, U. Laufend, Con.A.Messwertl=99.9, Con.A.Messwert2=99.9,
Snl.A.Aktuell=999, U.A. Zeitstempel=999, Ben.ES=[], Con.ES=[], Snl.ES=[], Sn2.ES=[], U.ES= [Anfrage_Zeitstempel_Sensorl] >}
In der Phase d) werden die Analyseergebnisse dann dargestellt. Die Visualisierung des Verfahrensergebnisses richtet sich an den Systementwickler mit fundierten UML- Kenntnissen und Erfahrungen in der Systemmodellierung. Wesentliches Darstellungsmittel ist dabei das bekannte
Sequenzdiagramm, in dem sehr gut dargestellt werden kann, nach welcher Sequenz von Nachrichten die Deadlocksituation eintritt.
Die Figur 10 lässt das Sequenzdiagramm für das Ergebnis der
Erreichbarkeitsanalyse anhand des untersuchten beispielhaften Messsystemmodells erkennen. Im Beispiel wurde für die Darstellung der an der Verklemmungs-Situation beteiligten Nachrichten das graphische
Symbol <->- verwendet, welches für den Stereotyp «deadlock» steht.
Ein Rahmen mit abgerundeten Ecken dient, dazu, die am Deadlock beteiligten Nachrichten optisch zusammenzufassen. Zusätzlich werden in einem Notizkasten die Zustände der am Deadlock beteiligten Objekte angegeben.

Claims

Patentansprüche
1. Verfahren zur Bestimmung von Verklemmungen (Deadlocks) in nebenläufigen Prozessen, bei denen mindestens ein Objekt in einem Zustand auf ein anderes Objekt in einem bestimmten Zustand wartet, für ein objektorientiert beschriebenes Systemmodell eines reaktiven Systems mit den Schritten:
a) Extrahieren aller aktiven Objekte des objektorientierten Systemmodells;
b) Feststellen mindestens der von den aktiven Objekten konsumierten und/oder produzierten Ereignissen, der Transitionen zwischen den Objekten und von Wächterbedingungen von Zustandsautomaten des Systemmodells zur Beschreibung des Zustandsverhaltens der Objekte;
c) Erzeugen der Zustands-Warte-Relationen zwischen den aktiven Objekten aus den Ereignissen als Liste von Objekten, die in einem definierten Zustand auf ein anderes Objekt in einem definierten Zustand warten;
d) Ermitteln möglicher Verklemmungs-Situationen als Zyklen aufeinander wartender Instanzen von zwei oder mehr unterschiedlichen Objekten, wobei in dem Zyklus kein Objekt mit mehr als einem Zustand involviert ist und keines der Objekte des Zyklus auf ein Objekt außerhalb des Zyklus wartet, und für jede Verklemmungs-Situation:
e) Überprüfen aller möglichen Pfade, die zu einer ermittelten Verklemmungs-Situation führen und aus den Zustandsautomaten des Systemmodells abgeleitet werden, durch simulierte Ausführung des Systemmodells unter
Berücksichtigung der Ereignisse und aktivierten Transitionen zur Analyse der Erreichbarkeit der ermittelten möglichen Verklemmungs-Situation .
2. Verfahren nach Anspruch 1 dadurch gekennzeichnet, dass im Schritt a) des Extrahierens aller aktiven Objekte die aktiven Objekten aus einer statischen und dynamischen Struktursicht des Systemmodells extrahiert und in einer Objekt-Liste gespeichert werden.
3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass für jedes aktive Objekt eine zugeordnete Klasse in einer Klassen-Liste abgespeichert wird und für jede Klasse in der Klassen-Liste das zugehörige Zustandsdiagramm zur Spezifikation eines Zustandsautomaten ausgewertet wird und die spezifizierten Zustandsautomaten in einer Zustandsautomaten-Liste abgespeichert werden.
4. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die Ermittlung der möglichen Verklemmungs-Situationen mit einem an sich bekannten Tiefensucheverfahren (Depth-First-Search) erfolgt.
5. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die Überprüfung der Erreichbarkeit der ermittelten möglichen Verklemmungs- Situationen heuristisch erfolgt, in dem ausgehend von einem initialen Zustand des Systemmodells die jeweils aktivierten Transitionen ermittelt werden und diejenige aktivierte Transition ausgewählt wird, welche das Systemmodell näher an die Verklemmungs-Situation heran bringt.
6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass aktivierte Transitionen vorliegen, wenn die Wächterbedingung für das zugeordnete Objekt wahr ist und das Ereignis des Objektes in einer Eingabewarteschlange liegt.
7. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass der Schritt e) des Uberprüfens aller möglichen Pfade für jede Verklemmungs-Situation solange iterativ durchgeführt wird, bis entweder ein Verklemmungs- Zustand erreicht ist oder alle Pfade eine festgelegte Anzahl (n) durchlaufen wurden.
8. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass das Systemmodell mit der Unified-Modeling-Language beschrieben wird.
9. Computerprogramme mit Programmcodemitteln zur Durchführung des Verfahren nach einem der vorhergehenden Ansprüche, wenn das Computerprogramm auf einem Rechner ausgeführt wird.
PCT/EP2005/051986 2004-05-04 2005-05-02 Verfahren zur bestimmung von verklemmungen in nebenläufigen prozessen WO2005109196A1 (de)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2007512180A JP4637175B2 (ja) 2004-05-04 2005-05-02 二次的に実行されるプロセスにおけるデッドロックを検出する方法
US11/579,554 US20080092147A1 (en) 2004-05-04 2005-05-02 Method for Determining Deadlocks in Secondary Processes
EP05742661A EP1745375A1 (de) 2004-05-04 2005-05-02 Verfahren zur bestimmung von verklemmungen in nebenläufigen prozessen

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE102004021975A DE102004021975A1 (de) 2004-05-04 2004-05-04 Verfahren zur Bestimmung von Verklemmungen in nebenläufigen Prozessen
DE102004021975.3 2004-05-04

Publications (1)

Publication Number Publication Date
WO2005109196A1 true WO2005109196A1 (de) 2005-11-17

Family

ID=34967422

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2005/051986 WO2005109196A1 (de) 2004-05-04 2005-05-02 Verfahren zur bestimmung von verklemmungen in nebenläufigen prozessen

Country Status (5)

Country Link
US (1) US20080092147A1 (de)
EP (1) EP1745375A1 (de)
JP (1) JP4637175B2 (de)
DE (1) DE102004021975A1 (de)
WO (1) WO2005109196A1 (de)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2008282165A (ja) * 2007-05-09 2008-11-20 Toshiba Mitsubishi-Electric Industrial System Corp バッチ制御装置及びバッチ制御方法

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20070101338A1 (en) * 2005-10-31 2007-05-03 Microsoft Corporation Detection, diagnosis and resolution of deadlocks and hangs
US7958512B2 (en) * 2005-10-31 2011-06-07 Microsoft Corporation Instrumentation to find the thread or process responsible for an application failure
US10283977B2 (en) * 2016-06-27 2019-05-07 Lg Chem, Ltd. Diagnostic system for a battery system
US10108767B1 (en) * 2016-09-30 2018-10-23 Cadence Design Systems, Inc. Methods, systems, and computer program product for implementing deadlock detection with formal verification techniques in an electronic design

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA2027934C (en) * 1989-12-22 1994-06-21 Cherie C. Barnes Accelerated deadlock detection in congested data transactions
US5734837A (en) * 1994-01-14 1998-03-31 Action Technologies, Inc. Method and apparatus for building business process applications in terms of its workflows
US5832484A (en) * 1996-07-02 1998-11-03 Sybase, Inc. Database system with methods for parallel lock management
CA2287413A1 (en) * 1997-05-08 1998-11-12 Iready Corporation Hardware accelerator for an object-oriented programming language
EP0938045A1 (de) * 1998-02-19 1999-08-25 IMEC vzw Verfahren und Gerät zur effektiven Verifikation mit Hilfe einer generalisierten Analyse von partieller Ordnung
US20050237949A1 (en) * 2000-12-21 2005-10-27 Addessi Vincent M Dynamic connection structure for file transfer
US7715819B2 (en) * 2001-08-03 2010-05-11 The Boeing Company Airborne security manager
EP1343079A1 (de) * 2002-03-07 2003-09-10 Infix Software-Systeme GmbH Verfahren, Software-Produkt und System zur universellen computergestützen Informationsverarbeitung
US7337290B2 (en) * 2003-04-03 2008-02-26 Oracle International Corporation Deadlock resolution through lock requeing

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
KURT JENSEN: "Coloured Petri Nets Volume 2", 1 February 1997, SPRINGER, NEW YORK, ISBN: 0-387-58276-2, XP002340126 *
ROBERT G. PETTIT; HASSAN GOMAA: "Validation of Dynamic Behavior in UML Using Colored Petri Nets", 11 April 2003 (2003-04-11), pages 1 - 5, XP002339665, Retrieved from the Internet <URL:http://web.archive.org/web/20030411064627/http://www.disi.unige.it/person/ReggioG/UMLWORKSHOP/Pettit.pdf> [retrieved on 20050802] *
See also references of EP1745375A1 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2008282165A (ja) * 2007-05-09 2008-11-20 Toshiba Mitsubishi-Electric Industrial System Corp バッチ制御装置及びバッチ制御方法

Also Published As

Publication number Publication date
EP1745375A1 (de) 2007-01-24
JP2007536661A (ja) 2007-12-13
US20080092147A1 (en) 2008-04-17
DE102004021975A1 (de) 2005-12-01
JP4637175B2 (ja) 2011-02-23

Similar Documents

Publication Publication Date Title
DE69317982T2 (de) Verfahren und Anlage zur Realzeitdatensammlung und Anzeigevorrichtung
DE60115007T2 (de) Verbessertes programmierbares kernmodell mit integrierter graphischer fehlersuchfunktionalität
DE69025543T2 (de) Leistungsmessung bei einem erweiterten endlichen Automaten
DE69900810T2 (de) Verfahren und Vorrichtung zum Testen von ereignisgesteuerten Programmen
DE19860061B4 (de) System zur Prüfung der kombinatorischen Äquivalenz
DE69432974T2 (de) Verfahren und vorrichtung zur automatischen analyse eines zielprogramms
DE69031538T2 (de) System und Verfahren zur Sammlung von Softwareanwendungsereignissen
US7386521B2 (en) Automatic test program generation using extended conditional constraint satisfaction
DE102006050112A1 (de) Verfahren zur Erstellung einer Anforderungsbeschreibung für ein eingebettetes System
DE102006019292A1 (de) Modellieren programmierbarer Einrichtungen
DE112012004499T5 (de) Testen von Transaktionsanwendungen
EP3451202B1 (de) Verfahren zum erzeugen eines auf einem testgerät ausführbaren modells eines technischen systems und testgerät
WO2013076250A1 (de) Simulationsverfahren, simulationssystem und computer-programm-produkt zur steuerung eines produktions-automatisierungssystems mit service-orientierter architektur
EP2648094B1 (de) Verfahren und system zum erzeugen eines quellcodes für ein computerprogramm zur ausführung und simulation eines prozesses
DE10038499A1 (de) Verfahren und System für die verbesserte Entwicklungsprüfung mittels angepasster Ablaufverfolgung
EP3306295A1 (de) Verfahren und vorrichtung zum testen elektronischer steuerungen, insbesondere zum testen von automobilsteuerungen
DE112018006331B4 (de) Testfallgenerierungsvorrichtung, Testfallgenerierungsverfahren und Testfallgenerierungsprogramm
DE10324594A1 (de) Verfahren zum Bereitstellen einer verbesserten Simulationsfähigkeit eines dynamischen Systems außerhalb der ursprünglichen Modellierungsumgebung
WO2005109196A1 (de) Verfahren zur bestimmung von verklemmungen in nebenläufigen prozessen
EP1657670A1 (de) System und Verfahren zur Status- und Fortschriftskontrolle eines technischen Prozesses oder eines technischen Projektes
DE102019008598A1 (de) Identifikation und Visualisierung von Assoziationen zwischen Code, der von einem Modell generiert ist, und Quellen, welche die Codegeneration beeinflussen
EP1380949A2 (de) Automatische Auswertung von Eigenschaften eines Systems auf Basis von Ablaufprotokollen
DE102006047762A1 (de) System zum Testen der Funktion eines Computernetzwerkes
HH NGU et al. Specification and verification of communication constraints for interoperable transactions
EP1202166A1 (de) System zur Verifikation von Software-Anwendungsmodellen in Ketten von Software-Entwurfswerkzeugen

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KM KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SM SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): BW GH GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IS IT LT LU MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
DPEN Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed from 20040101)
WWE Wipo information: entry into national phase

Ref document number: 2005742661

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 11579554

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 2007512180

Country of ref document: JP

NENP Non-entry into the national phase

Ref country code: DE

WWW Wipo information: withdrawn in national office

Country of ref document: DE

WWP Wipo information: published in national office

Ref document number: 2005742661

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 11579554

Country of ref document: US