WO2013091908A1 - Verfahren und vorrichtung zum einfügen von synchronisationsbefehlen in programmabschnitte eines programms - Google Patents

Verfahren und vorrichtung zum einfügen von synchronisationsbefehlen in programmabschnitte eines programms Download PDF

Info

Publication number
WO2013091908A1
WO2013091908A1 PCT/EP2012/062571 EP2012062571W WO2013091908A1 WO 2013091908 A1 WO2013091908 A1 WO 2013091908A1 EP 2012062571 W EP2012062571 W EP 2012062571W WO 2013091908 A1 WO2013091908 A1 WO 2013091908A1
Authority
WO
WIPO (PCT)
Prior art keywords
program
command
ssi
resource
wait
Prior art date
Legal status (The legal status 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 status listed.)
Ceased
Application number
PCT/EP2012/062571
Other languages
English (en)
French (fr)
Inventor
Stefan Kempf
Ronald VELDEMA
Michael Philippsen
Michael Wieczorek
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Siemens AG
Friedrich Alexander Universitaet Erlangen Nuernberg
Siemens Corp
Original Assignee
Siemens AG
Friedrich Alexander Universitaet Erlangen Nuernberg
Siemens Corp
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 AG, Friedrich Alexander Universitaet Erlangen Nuernberg, Siemens Corp filed Critical Siemens AG
Publication of WO2013091908A1 publication Critical patent/WO2013091908A1/de
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G06F8/458—Synchronisation, e.g. post-wait, barriers, locks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G06F8/456—Parallelism detection

Definitions

  • the invention relates to a method for inserting synchronization commands into program sections of a program.
  • PLC Programmable Logic Cont ⁇ roller
  • the synchronization commands may be, for example, release and wait commands.
  • the invention relates to a device for inserting synchronization commands into program sections of a program.
  • the invention has for its object to provide a method by which a freedom from error of the insertion of synchronization commands can be increased.
  • this object is achieved by providing a method for inserting synchronization commands into program sections of a program, which The following steps include:
  • the device is prepared to insert a release command after a write command of a first program section to a resource that is shared by the first program section and a second program section if the write command to the resource from the first program section , wherein an embodiment of the enable command, a condition variable set into a set status execute a Le ⁇ sebenning the second program portion of the resource.
  • DA in the device is prepared to insert a wait command for waiting for the Set condition of the conditional variable prior to the read instruction of the second program section on the res ⁇ source, wherein execution of the wait command causes the second program portion to tion with a continuation of the execution of the to wait for the second part of the program until the condition variable is set.
  • the parallel version of the sequential program is synchronized without errors. Furthermore, the method can be automated, so that it can help to reduce a work time for creating a sequential Pro ⁇ program. It is useful if the condition variable ei occasion ⁇ ner program initialization and is in an execution of the corresponding wait command reset. This can be recognized in test runs when a release command is unintentionally used by several wait commands.
  • a preferred embodiment provides that the method comprises a step for detecting a data dependency between parallel callable program sections. Is also preferred if the method comprises a step of determining which pairs of writing and ⁇ Lesebe missing in a predetermined order and which are run sequence must be followed in this case. By pre ⁇ called both measures, the synchronisationsver- will drive amenable to automation.
  • the method includes a step of recognizing a path that bridges a path with a write command to be synchronized to a resource, and a step of having a release command for that resource in the bridging path is inserted. This results in a flawless Since ⁇ tensynchronisation is possible even when a thread has a branch, which results in that a write command is carried out only under certain circumstances. It is also preferable to provide resource-specific or parti- tion-specific condition variables. An optimization option determines that a runtime requirement for different alternatives of partitions is determined and then the one or the alternatives with the lowest runtime requirements are used. The two aforementioned measures can help improve computational performance by reducing a sum of thread latencies.
  • the method includes a step of removing a second condition variable along with its associated release and wait instructions if each release command on a first condition variable postdoments each release command on the second condition variable and each wait command on the first condition variable each wait command on the second condition variable dominates.
  • 1 shows in the upper part schematically a sequence of a sequential program and in the lower part a sequence of a parallelized variant of the sequential program with error-free access order; 2 schematically shows a sequence of an embodiment of a
  • FIG. 3 schematically shows an example of a parallelized program in which a condition variable can be removed together with associated synchronization commands
  • Representation in the upper part schematically shows a first program loop that includes a write command to a memory location, and a subsequent program section that includes a read command to the Spei ⁇ cherstelle, and in the lower part schema ⁇ table a second program loop that fails a Lesebe ⁇ to a memory location and which connects to a program section that includes a write command to the memory location.
  • Programmable logic control programs access memory locations, actuators, and sensors to monitor and control engineering processes.
  • Future generations of programmable logic controllers will use multi-core processors.
  • programs for programmable logic controllers in parallel running strands (threads) up ⁇ shares must be.
  • race races data races
  • 'location' Memory locations whose contents are changed during program execution by means of write commands can also be referred to as variables.
  • FIG 1 shows a flow of SEQUENTIEL ⁇ len program 10.
  • SSi may be an external variable or a global one (but not mandatory).
  • memory locations SSi also subsume other memory-related system components than just memory locations SSi of a data memory in the strict sense. It should also be not necessarily assumed that a memory location SSi maintains its data ⁇ content between a write command 31 and a directly subsequent read command 32 unchanged.
  • a change in the data content may, for example, be design-specific if (not shown in the figures) there is a conflict of interest ing write accesses from a second bus system are vorgese ⁇ hen, or if a purpose of the program code is just to detect an unwanted change in the data content of a memory location SSi.
  • a (not shown in the figures) pair are viewed from an actuator and a sensor for the present purposes as a memory location SSi when the Ak ⁇ tor is suitable (for example, as an actuator of a control loop) to a ( physical) size and the sensor is intended to measure the (physical) size (for example, as a controlled variable).
  • a write command 31 of the first program section PA1 to a first memory location SSi may not after the write ⁇ command 31 of the second program section PA2 be performed in the SpeI ⁇ cherstelle SSi because the memory location SSi otherwise (from the perspective of the second program section PA2 and also from the viewpoint evtl further subse- quent program sections) could be incorrectly pre-assigned.
  • the read command 32 of the second program section PA2 to the storage location SSi must not be executed before the write command 31 of the first program section PA1 to the storage location SSi, because the storage location SSi otherwise from the perspective of the second program section PA2 (and off
  • FIG. 1 shows a sequence of a parallelized variant 12 of the sequential program with faulty free access order.
  • FIG. 2 shows a sequence of an embodiment of a method for producing a data synchronization.
  • the method 100 described in Fol ⁇ constricting is proposed:
  • a first step 110 for example, the dependency analysis described in Much Nick, Steven S .: “Advanced Compiler Design &Implementation" is examined, which data ⁇ dependencies between parallel callable program sections PA1, PA2 (e.g., program modules) are made.
  • the release commands 41 to set condition variables c and the waiting commands 42 for waiting for a Set ⁇ state of condition variables c are known synchronization primitives.
  • the condition variable c can be ⁇ play realized at by means of a flag or in the form of a Softwa- reinterrupt message.
  • Waiting commands 42 NEN with polling (by requesting an associated condition variable c) or in the interrupt process (by receiving a message that is generated by a release command 41) can be realized.
  • the release command 41 for setting a condition variable c may be inserted, for example, immediately after the write command 31 to be protected.
  • the wait command 42 for waiting for a set state of the conditional variable c may be inserted, for example, immediately before a read command 32 to be protected.
  • Each condition variable c is reset at program initialization to ⁇ .
  • the first program section PA1 a branching contained ⁇ th which causes the path with the write command 31 is executed under a specific constraint (which may comprise a plurality of boundary conditions) is run through, and otherwise a different path.
  • similarly acting condition variables c must also be inserted into all those program paths of the first program section PA1 which are passed through without a write command 31 being performed therein. This prevents the second pro- program section PA2 with the wait 42 for an infinitely long time on a release (set state of the conditional variable c) was ⁇ tet when the first program section PA1 is run on paths ⁇ in which the write command 31 is not performed.
  • release instructions 41, wait instructions 42 and condition variables c which are specific for each synchronization point 5j, even if different synchronization points 5j
  • Write and read commands 31, 32 are synchronized to a same memory location SSi. It is then not just a memory location-specific, but also a synchronization-specific synchronization.
  • a SSi spei ⁇ cher stellenspezifische condition variable c also a Parti ⁇ tion be associated with (in other words subset group or Freigabegrup ⁇ pe) of memory locations SSi.
  • the enable command 41 for setting the partition-specific conditional variable c may not be inserted until the write commands 31 for all the memory locations SSi of the partition have been completed in program sections to be executed beforehand.
  • the wait command 42 must be inserted before any read command 32 for one of the memory locations SSi of the partition is executed in subsequently executed program sections PA2.
  • the partition can include all memory locations SSi that are to be synchronized somewhere in the program sequence.
  • the condition variable c need not be memory location-specific.
  • the device which inserts the release commands 41 and the wait commands 42, the runtime requirements for different alternatives of partitions determined and then uses that alternative or one of the age ⁇ native with the lowest duration requirement.
  • a first command A dominates a second command B if the first command A is always guaranteed to be executed before the second command B.
  • a first command A postdominates a second command B if the first command A is always guaranteed to be executed after the second command B.
  • synchronization commands ie enable and wait commands
  • SSi shared memory location
  • each release command 41 on a first condition variable c each Release Certificates ⁇ bebetation 41 'on a second condition variable c', and do ⁇ miniert each wait command 42 on the first Bedingungsvariab ⁇ le c each wait command 42 'on the second condition variable c', then For example, the second condition variable c 'may be removed along with its associated enable commands 41' and wait instructions 42 '.
  • the read command 32 ' can only be executed after the release command 41 has been executed on the first condition variable c.
  • the second conditional variable c 'together with the associated synchronization commands 41 ', 42' are removed. Since also the synchronization commands 41 ', 42' cause runtime costs, this can contribute to the reduction of the computing time.
  • the first program loop 81 illustrated which includes a Schreibbe ⁇ lack 31 to a location SSi, and a subsequent program portion 84 which includes a read command 32 to the memory location SSi.
  • program loops 81, 82 represent a notation for a repetition of the loop contents 80, ie a notation for a chain of repeated executions of the loop contents 80.
  • a program section 84 following a first program loop 81 does not follow each loop pass of the first program loop 81, but only the last loop pass.
  • a program section 84, which is followed by a second program loop 82 does not precede every loop run of the program loop 82, but only the loop pass performed first.
  • a program section 84 which follows a first program loop 81 reads from a memory location SSi which is described within the program loop 81, then execution of the program section 84 following the first program loop 81 must be stopped so long as until the writing of the memory location SSi is completed in the last loop pass. To do so, the setting of the conditional variable c (the execution of the release command 41) may be made conditional on the fact that it is the last loop pass. Taking this proviso into account, it is not absolutely necessary to set the release instruction 41 to the end 86 of the program loop 81. To To remind the conditionality of the release command 41, the release command 41 is shown in dashed lines in FIG.
  • Evaluate program loop 81 It may also be that for reasons of clarity to monitor the termination condition for this purpose is undesirable (for example ei ⁇ ner while, for-each- or forever loop or when the demolition decision depends on a variable termination criterion, the decision parameters only present at the end 86 of the first program loop 81 and not at the time of the release command 41). There is also the alternative of inserting the release command 41 immediately behind or at the end 86 of the previously executed program loop 81 for setting the conditional variable c.
  • a loop content 80 within a (non-parallelized) second program loop 82 reads from a memory location SSi described by a previous program portion 84.
  • a second program loop 82 is shown, which comprises a read command 32 to a memory location SSi and connects to the preceding program section 84, which comprises a write command 31 to the memory location SSi.

Landscapes

  • Engineering & Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Multi Processors (AREA)

Abstract

Zur Datensynchronisation wird eine Vorrichtung und ein Verfahren (100) zum Einfügen von Synchronisationsbefehlen (41, 42) in Programmabschnitte (PA1, PA2) eines Programms (10, 12) bereitgestellt. Dazu wird ein Freigabebefehl (41) nach einem Schreibbefehl (31) eines ersten Programmabschnitts (PA1) auf eine Ressource (SSi) automatisiert eingefügt, die von dem ersten Programmabschnitt (PA1) und einem zweiten Programmabschnitt (PA2) gemeinsam genutzt wird, falls der Schreibbefehl (31) auf die Ressource (SSi) von dem ersten Programmabschnitt (PA1) vor einem Lesebefehl (32) des zweiten Programmabschnitts (PA2) auf die Ressource (SSi) auszuführen ist, wobei eine Ausführung des Freigabebefehls (41) eine Bedingungsvariable (c) in einen Gesetztzustand versetzt. Ein Wartebefehl (42) zum Warten auf den Gesetztzustand der Bedingungsvariable (c) wird vor dem Lesebefehl (32) auf die Ressource (SSi) automatisiert eingefügt, wobei eine Ausführung des Wartebefehls (42) den zweiten Programmabschnitt (PA2) dazu veranlasst, mit einer Fortführung der Abarbeitung des zweiten Programmabschnitts (PA2) zu warten, bis die Bedingungsvariable (c) gesetzt ist.

Description

Beschreibung
Verfahren und Vorrichtung zum Einfügen von Synchronisationsbefehlen in Programmabschnitte eines Programms
Die Erfindung betrifft ein Verfahren zum Einfügen von Synchronisationsbefehlen in Programmabschnitte eines Programms. Bei dem Programm kann es sich beispielsweise um ein Programm handeln, das in einer höheren Programmiersprache und/oder in einer Assemblersprache vorliegt und/oder das für eine spei¬ cherprogrammierte Steuerung (PLC = programmable logic Cont¬ roller) verwendet wird. Die Synchronisationsbefehle können beispielsweise Freigabe- und Wartebefehle sein. Außerdem betrifft die Erfindung eine Vorrichtung zum Einfügen von Synchronisationsbefehlen in Programmabschnitte eines Programms .
In einer parallelen Abarbeitung eines sequentiellen Programms muss sichergestellt werden, dass Zugriffe (Schreib- und Lese¬ befehle) auf Ressourcen (beispielsweise auf Speicherstellen, Aktoren und Sensoren) , die in einem sequentiellen Programm in einer bestimmten Reihenfolge auszuführen sind, auch bei der parallelen Abarbeitung in der gewollten Reihenfolge ausge- führt werden. Andernfalls kann aufgrund fehlender oder fehlerhafter Datensynchronisation eine sogenannte WettlaufSituation auftreten, die zu unerwünschter Datenänderung und/oder unerwünschter Datennutzung führt. Aus McCloskey, B. et al . : Autolocker: Synchronization Infer- ence for Atomic Sections, Conf . Record of the 33rd ACM
SIGPLAN-SIGACT Symposium of Principles of Programming Langua- ges, POPL '06, S. 346 - 358, ist ein Verfahren bekannt, das im Programmcode Stellen analysiert, die als kritische Ab- schnitte markiert sind, und automatisch Mutexe einführt, um einen gegenseitigen Ausschluss zu gewährleisten.
Aus Naik, M. et AI.: Effective Static Race Detection for Java, Proceedings of the ACM SIGPLAN Conference on Programming Lan- guage Design and Implementation, PLDI '06, S. 308 - 319, ist ein weiteres Verfahren bekannt, mit welchem Threads eines Programms analysiert werden und für jede Anweisung untersucht wird, welche Mutexe bei der Anweisung gesperrt sind. Wenn es eine Anweisung gibt, die auf Speicherstellen zugreift, welche von mehreren Threads genutzt werden können, und bei der kein Mutex gesperrt ist, kann bei dieser Anweisung möglicherweise eine WettlaufSituation entstehen.
Trotz der genannten, bekannten Hilfsmittel, muss ein Program- mierer alle kritischen Abschnitte manuell und fehlerfrei er¬ kennen, um eine fehlerfreie Parallelisierung des Programmco¬ des zu erreichen, mit der eine Abarbeitung des Programmcodes in der gewollten Reihenfolge ausgeführt wird. Die Wettlaufsi¬ tuationen müssen also bisher vom Programmierer vermieden wer- den, indem er sogenannte kritische Abschnitte identifiziert, die atomar ausgeführt werden und deshalb auch als 'atomare Blöcke' bezeichnet werden. Der gegenseitige Ausschluss kriti¬ scher Abschnitte kann manuell durch Einfügen von Mutexen oder mit einem transaktionalen Speicher realisiert werden. Das ma- nuelle Einfügen von Synchronisationsbefehlen (wie Freigabe- und Wartebefehlen) in parallelisierten Programmcode ist fehleranfällig .
Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren be- reitzustellen, mit dem eine Fehlerfreiheit der Einfügung von Synchronisationsbefehlen erhöht werden kann.
Erfindungsgemäß wird diese Aufgabe dadurch gelöst, dass ein Verfahren zum Einfügen von Synchronisationsbefehlen in Pro- grammabschnitte eines Programms bereitgestellt wird, das fol- gende Schritte umfasst:
automatisiertes Einfügen eines Freigabebefehls nach einem Schreibbefehl eines ersten Programmabschnitts auf eine Ressource, die von dem ersten Programmabschnitt und einem zweiten Programmabschnitt gemeinsam genutzt wird, falls der Schreibbefehl auf die Ressource von dem ersten Programmabschnitt vor einem Lesebefehl des zweiten Programmabschnitts auf die Ressource auszuführen ist, wobei eine Ausführung des Freigabebefehls eine Bedingungsvariable in einen Gesetztzustand versetzt; und
automatisiertes Einfügen eines Wartebefehls zum Warten auf den Gesetztzustand der Bedingungsvariable vor dem Lesebe¬ fehl des zweiten Programmabschnitts auf die Ressource, wo¬ bei eine Ausführung des Wartebefehls den zweiten Programm- abschnitt dazu veranlasst, mit einer Fortführung der Abar¬ beitung des zweiten Programmabschnitts zu warten, bis die Bedingungsvariable gesetzt ist.
In Bezug auf die Vorrichtung zum Einfügen von Synchronisati- onsbefehlen in Programmabschnitte eines Programms wird die
Aufgabe dadurch gelöst, dass die Vorrichtung dazu vorbereitet ist, einen Freigabebefehl nach einem Schreibbefehl eines ersten Programmabschnitts auf eine Ressource einzufügen, die von dem ersten Programmabschnitt und einem zweiten Programmab- schnitt gemeinsam genutzt wird, falls der Schreibbefehl auf die Ressource von dem ersten Programmabschnitt vor einem Le¬ sebefehl des zweiten Programmabschnitts auf die Ressource auszuführen ist, wobei eine Ausführung des Freigabebefehls eine Bedingungsvariable in einen Gesetztzustand versetzt. Da- bei ist die Vorrichtung dazu vorbereitet, einen Wartebefehl zum Warten auf den Gesetztzustand der Bedingungsvariable vor dem Lesebefehl des zweiten Programmabschnitts auf die Res¬ source einzufügen, wobei eine Ausführung des Wartebefehls den zweiten Programmabschnitt dazu veranlasst, mit einer Fortfüh- rung der Abarbeitung des zweiten Programmabschnitts zu warten, bis die Bedingungsvariable gesetzt ist.
Durch das erfindungsgemäße Verfahren und die erfindungsgemäße Vorrichtung wird die parallele Version des sequentiellen Pro- gramms fehlerfrei synchronisiert. Außerdem ist das Verfahren automatisierbar, so dass es dazu beitragen kann, einen Arbeitszeitaufwand für die Erstellung eines sequentiellen Pro¬ gramms zu verringern. Es ist zweckmäßig, wenn die Bedingungsvariable anlässlich ei¬ ner Programminitialisierung sowie bei einem Abarbeiten des zugehörigen Wartebefehls zurückgesetzt wird. Hierdurch kann in Testläufen erkannt werden, wenn ein Freigabebefehl ungewollt von mehreren Wartebefehlen genutzt wird.
Eine bevorzugte Ausführungsform sieht vor, dass das Verfahren einen Schritt zur Erkennung einer Datenabhängigkeit zwischen parallel aufrufbaren Programmabschnitten umfasst. Ebenso bevorzugt ist, wenn das Verfahren einen Schritt zur Feststellung umfasst, welche Paare von Schreib- und Lesebe¬ fehlen in einer vorgegebenen Reihenfolge auszuführen sind und welche Reihenfolge hierbei einzuhalten ist. Durch die vorge¬ nannten beiden Maßnahmen wird das Datensynchronisationsver- fahren einer Automatisierung zugänglich.
Es hat auch Vorteile, wenn das Verfahren einen Schritt umfasst, in welchem ein Pfad erkannt wird, der einen Pfad mit einem zu synchronisierenden Schreibbefehl auf eine Ressource überbrückt, und einen Schritt umfasst, in welchem in den ü- berbrückenden Pfad ein Freigabebefehl für diese Ressource eingefügt wird. Hierdurch ist auch dann eine fehlerfreie Da¬ tensynchronisation möglich, wenn ein Thread eine Verzweigung enthält, die dazu führt, dass ein Schreibbefehl nur unter be- stimmten Umständen durchgeführt wird. Auch ist es bevorzugt, ressourcenspezifische oder parti- onsspezifische Bedingungsvariablen vorzusehen. Eine Optimierungsoption sieht vor, dass ein Laufzeitbedarf für unterschiedliche Alternativen von Partitionen ermittelt wird und dann die oder eine der Alternativen mit geringstem Laufzeitbedarf genutzt wird. Die beiden vorgenannten Maßnahmen können dazu beitragen, eine Rechenleistung zu verbessern, indem eine Summe von Wartezeiten der Threads verringert wird.
Es kann auch zweckmäßig sein, synchronisationsstellenspezifi- sche Bedingungsvariablen vorzusehen. Hierdurch können bestimmte Formen einer fehlerhaften Wiederverwendung von Bedin- gungsvariablen von vorneherein ausgeschlossen werden.
Eine weitere Optimierungsoption sieht vor, dass das Verfahren einen Schritt umfasst, in dem eine zweite Bedingungsvariable zusammen mit ihren zugehörigen Freigabe- und Wartebefehlen entfernt wird, wenn jeder Freigabebefehl auf einer ersten Bedingungsvariable jeden Freigabebefehl auf der zweiten Bedingungsvariable postdominiert und jeder Wartebefehl auf der ersten Bedingungsvariable jeden Wartebefehl auf der zweiten Bedingungsvariable dominiert. Hierdurch kann eine Rechenleis- tung verbessert werden, indem Laufzeiten für Synchronisationsoperationen eingespart werden.
Die Erfindung ist anhand der beigefügten Zeichnungen näher erläutert, in denen zeigen:
FIG 1 im oberen Teil schematisch einen Ablauf eines sequentiellen Programms und im unteren Teil einen Ablauf einer parallelisierten Variante des sequentiellen Programms mit fehlerfreier Zugriffsreihenfolge; FIG 2 schematisch einen Ablauf einer Ausführungsform eines
Verfahrens zur Herstellung einer Datensynchronisation;
FIG 3 schematisch ein Beispiel eines parallelisierten Programms, in dem eine Bedingungsvariable zusammen mit zugehörigen Synchronisationsbefehlen entfernt werden kann;
FIG 4 in sequentieller (d.h. in nicht parallelisierter)
Darstellung im oberen Teil schematisch eine erste Programmschleife, die einen Schreibbefehl auf eine Speicherstelle umfasst, und einen darauf folgenden Programmabschnitt, der einen Lesebefehl auf die Spei¬ cherstelle umfasst, und in dem unteren Teil schema¬ tisch eine zweite Programmschleife, die einen Lesebe¬ fehl auf eine Speicherstelle umfasst und die an einen Programmabschnitt anschließt, der einen Schreibbefehl auf die Speicherstelle umfasst. Die nachfolgend näher geschilderten Ausführungsbeispiele stellen bevorzugte Ausführungsformen der vorliegenden Erfindung dar.
Programme für speicherprogrammierte Steuerungen greifen auf Speicherstellen, Aktoren und Sensoren zu, um technische Prozesse zu beobachten und zu steuern. In zukünftigen Generationen von speicherprogrammierten Steuerungen werden Mehrkernprozessoren zum Einsatz kommen. Um alle Kerne des Prozessors nutzen zu können, müssen Programme für speicherprogrammierte Steuerungen in parallel ablaufende Stränge (Threads) aufge¬ teilt werden. Dadurch besteht dann jedoch die Möglichkeit, dass die Stränge in nicht vorherbestimmter Reihenfolge auf gemeinsame Speicherstellen, Sensoren oder Aktoren zugreifen. Solche WettlaufSituationen (data races) sollten vermieden werden, da sie zu inkonsistenten Programmzuständen führen können und auch die Aussagekraft von Testergebnissen beeinträchtigen können. Um die Verständlichkeit der Figurenbe¬ schreibung zu fördern, wird im Folgenden der Begriff 'Speicherstelle' statt 'Ressource' verwendet; dies geschieht je- doch ohne Beschränkung der allgemeineren Offenbarung. Speicherstellen, deren Inhalt während des Programmablaufs mittels Schreibbefehlen verändert wird, können auch als Variablen bezeichnet werden.
Der obere Teil von FIG 1 zeigt einen Ablauf eines sequentiel¬ len Programms 10. Hierbei greifen zwei Programmteile PA1, PA2 nacheinander auf eine selbe i-te Speicherstelle SSi zu. Bei SSi kann es sich beispielsweise um eine externe oder um eine globale Variable handeln (dies ist aber nicht zwingend) .
Ohne Beschränkung der Allgemeinheit wird im Folgenden unterstellt, dass die Programme 12 bereits parallelisiert sind (siehe unterer Teil der FIG 1) . D.h. im Quelltext der Pro¬ gramme 12 sind bereits Anweisungen enthalten, die mindestens zwei Threads 21, 22 erzeugen. Allerdings wird unterstellt, dass Schreibbefehle 31 und Lesebefehle 32 auf gemeinsam ge¬ nutzte Daten SSi durch die Parallelisierung des sequentiellen Programms 10 noch nicht synchronisiert wurden. Das heißt, sie sind noch nicht durch Synchronisationsmaßnahmen wie gegenseitigen Ausschluss geschützt.
Eine erweiterte Betrachtung ist möglich, wenn unter Speicherstellen SSi auch andere gedächtnisbehaftete Systemkomponenten subsumiert werden als nur Speicherstellen SSi eines Daten- Speichers im engeren Sinne. Außerdem muss auch nicht zwingend unterstellt werden, dass eine Speicherstelle SSi ihren Daten¬ inhalt zwischen einem Schreibbefehl 31 und einem direkt darauffolgenden Lesebefehl 32 unverändert aufrechterhält. Eine Veränderung des Dateninhalts kann beispielsweise bauartbe- stimmt sein, wenn (in den Figuren nicht dargestellte) konkur- rierende Schreibzugriffe aus einem zweiten Bussystem vorgese¬ hen sind, oder wenn ein Zweck des Programmcodes gerade darin besteht, eine ungewollte Veränderung des Dateninhalts einer Speicherstelle SSi zu erkennen. Entsprechend kann beispiels- weise auch ein (in den Figuren nicht dargestelltes) Paar aus einem Aktor und einem Sensor für die hier interessierenden Zwecke als Speicherstelle SSi betrachtet werden, wenn der Ak¬ tor (beispielsweise als Stellglied eines Regelkreises) dazu geeignet ist, eine (physikalische) Größe zu beeinflussen und der Sensor dazu vorgesehen ist, die (physikalische) Größe (beispielsweise als Regelgröße) zu messen.
Wenn im sequentiellen Code eines Programms 10 ein Programmab¬ schnitt PA2 zeitlich nach einem Programmabschnitt PA1 auszu- führen ist und das Programm 12 in parallelisierter Form fehlerfrei ausgeführt werden soll (und wenn keine weiteren In¬ formationen vorliegen) ist grundsätzlich Folgendes sicherzustellen :
Ein Schreibbefehl 31 des ersten Programmabschnitts PA1 auf eine erste Speicherstelle SSi darf nicht nach dem Schreib¬ befehl 31 des zweiten Programmabschnitts PA2 auf die Spei¬ cherstelle SSi ausgeführt werden, weil die Speicherstelle SSi sonst aus Sicht des zweiten Programmabschnitts PA2 (und auch aus Sicht evtl. weiterer nachfolgender Programm- abschnitte) fehlerhaft vorbesetzt sein könnte.
Der Lesebefehl 32 des zweiten Programmabschnitts PA2 auf die Speicherstelle SSi darf nicht vor dem Schreibbefehl 31 des ersten Programmabschnitts PA1 auf die Speicherstelle SSi ausgeführt werden, weil die Speicherstelle SSi sonst aus Sicht des zweiten Programmabschnitts PA2 (und auch aus
Sicht evtl. weiterer nachfolgender Programmabschnitte) fehlerhaft vorbesetzt sein könnte.
Der untere Teil der FIG 1 zeigt einen Ablauf einer paralle- lisierten Variante 12 des sequentiellen Programms mit fehler- freier Zugriffsreihenfolge.
Die FIG 2 zeigt einen Ablauf einer Ausführungsform eines Verfahrens zur Herstellung einer Datensynchronisation. Um eine fehlerfreie Zugriffsreihenfolge sicherzustellen, die eine ur¬ sprüngliche Semantik des Programms einhält, wird das im Fol¬ genden beschriebene Verfahren 100 vorgeschlagen:
Mittels einer bekannten Abhängigkeitsanalyse wird in einem ersten Schritt 110 (beispielsweise der in Muchnick, Steven S.: "Advanced Compiler Design & Implementation" beschriebenen Abhängigkeitsanalyse) wird untersucht, welche Daten¬ abhängigkeiten zwischen parallel aufrufbaren Programmabschnitten PA1, PA2 (beispielsweise Programmbausteinen) bestehen .
- Unter Berücksichtigung der aufgefundenen Datenabhängigkeiten wird in einem zweiten Schritt 120 festgestellt, welche Paare von Schreib- und Lesebefehlen 31, 32 in einer vorge¬ gebenen Reihenfolge auszuführen sind und welche Reihenfol¬ ge hierbei einzuhalten ist.
- Unter Berücksichtigung der einzuhaltenden Reihenfolge für die Schreib- und Lesebefehle 31, 32 werden in einem drit¬ ten Schritt 130 in das zu parallelisierende oder in das bereits parallelisierte Programm 12 Freigabebefehle 41 zum Setzen von Bedingungsvariablen c und Wartebefehle 42 zum Warten auf einen Gesetztzustand der jeweiligen Bedingungs¬ variablen c automatisiert eingefügt (Schritte 131 und 132) .
Durch Schreib-, Lese, Freigabe- und Wartebefehle werden
Schreib-, Lese, Freigabe- beziehungsweise Wartevorgänge aus- gelöst. Die Freigabebefehle 41 zum Setzen von Bedingungsvariablen c und die Wartebefehle 42 zum Warten auf einen Gesetzt¬ zustand von Bedingungsvariablen c stellen bekannte Synchronisationsprimitive dar. Die Bedingungsvariable c kann bei¬ spielsweise mittels eines Flags oder in Gestalt einer Softwa- reinterrupt-Nachricht realisiert werden. Wartebefehle 42 kön- nen mit Pollingverfahren (mittels Abfrage einer zugeordneten Bedingungsvariablen c) oder im Interrupt-Verfahren (mittels Empfang einer Nachricht, die von einem Freigabebefehl 41 erzeugt wird) realisiert werden. Um einen möglichst hohen Leis- tungsgewinn durch die Programmparallelisierung zu erzielen, ist es von Vorteil, den Freigabebefehl 41 an erstmöglicher Stelle und den Wartebefehl 42 an letztmöglicher Stelle einzufügen. Der Freigabebefehl 41 zum Setzen einer Bedingungsvariable c kann beispielsweise unmittelbar nach dem zu schützen- den Schreibbefehl 31 eingefügt werden. Der Wartebefehl 42 zum Warten auf einen Gesetztzustand der Bedingungsvariable c kann beispielsweise unmittelbar vor einem zu schützenden Lesebefehl 32 eingefügt werden. Jede Bedingungsvariable c ist bei Programminitialisierung zu¬ rückzusetzen. Wenn es in einem parallelisierten Programm 12 für eine selbe Speicherstelle SSi mehrere Synchronisations¬ stellen 5j gibt (siehe FIG 1), an denen für diese Speicherstelle SSi auf eine Freigabe (Gesetztzustand der Bedingungs- variable c) gewartet werden muss (dies ist der Allgemeinfall) , muss die Bedingungsvariable c auch beim Durchlaufen des zuge¬ hörigen Wartebefehls 42 zurückgesetzt werden, damit eine zeitlich hinterher durchlaufene Synchronisationsstelle 5j nicht aufgrund der bereits gesetzten Bedingungsvariable c synchronisationslos durchlaufen wird.
Der erste Programmabschnitt PA1 kann eine Verzweigung enthal¬ ten, die bewirkt, dass der Pfad mit dem Schreibbefehl 31 nur unter einer bestimmten Randbedingung durchlaufen wird (die mehrere Randbedingungen umfassen kann) und ansonsten ein anderer Pfad durchlaufen wird. In diesem Fall müssen gleichwirkende Bedingungsvariablen c auch in alle diejenigen Programmpfade des ersten Programmabschnitts PA1 eingefügt werden, die durchlaufen werden, ohne dass in ihnen ein Schreibbefehl 31 durchgeführt wird. So wird verhindert, dass der zweite Pro- grammabschnitt PA2 mit dem Wartebefehl 42 unendlich lange auf eine Freigabe (Gesetztzustand der Bedingungsvariable c) war¬ tet, wenn der erste Programmabschnitt PA1 auf Pfaden durch¬ laufen wird, in denen der Schreibbefehl 31 nicht durchgeführt wird.
Unabhängig davon kann es ratsam sein, Freigabebefehle 41, Wartebefehle 42 und Bedingungsvariablen c vorzusehen, die für jede Synchronisationsstelle 5j spezifisch sind, und zwar auch dann, wenn an unterschiedlichen Synchronisationsstellen 5j
Schreib- und Lesebefehle 31, 32 auf eine selbe Speicherstelle SSi zu synchronisieren sind. Es handelt sich dann also nicht nur um eine speicherstellenspezifische, sondern auch um eine synchronisationssteilenspezifische Synchronisation .
Anstatt einer einzelnen Speicherstelle SSi kann eine spei¬ cherstellenspezifische Bedingungsvariable c auch einer Parti¬ tion (mit anderen Worten Teilmenge, Gruppe oder Freigabegrup¬ pe) von Speicherstellen SSi zugeordnet sein. In diesem Fall darf der Freigabebefehl 41 zum Setzen der partitionsspezifi- schen Bedingungsvariable c erst eingefügt werden, wenn in vorher auszuführenden Programmabschnitten die Schreibbefehle 31 für alle Speicherstellen SSi der Partition abgeschlossen sind. Umgekehrt muss in diesem Fall der Wartebefehl 42 einge- fügt werden, bevor in nachher auszuführenden Programmabschnitten PA2 irgendein Lesebefehl 32 für eine der Speicherstellen SSi der Partition ausgeführt wird. Im Extremfall kann die Partition alle Speicherstellen SSi umfassen, die irgendwo im Programmablauf zu synchronisieren sind. In diesem Fall braucht die Bedingungsvariable c nicht speicherstellenspezi- fisch zu sein.
Es kann vorgesehen sein, dass die Vorrichtung, welche die Freigabebefehle 41 und die Wartebefehle 42 einfügt, den Lauf- zeitbedarf für unterschiedliche Alternativen von Partitionen ermittelt und dann diejenige Alternative oder eine der Alter¬ nativen mit geringstem Laufzeitbedarf nutzt.
Eine weitere Optimierungsmöglichkeit besteht in einer Verwen- dung von Dominatoren und Postdominatoren in einem Kontroll- flussgraphen zur Erkennung und Beseitigung einer Redundanz in der Datensynchronisation. Die Begriffe 'dominieren' und
'postdominieren' sind wie folgt definiert. Ein erster Befehl A dominiert einen zweiten Befehl B, wenn der erste Befehl A immer garantiert vor dem zweiten Befehl B ausgeführt wird. Ein erster Befehl A postdominiert einen zweiten Befehl B, wenn der erste Befehl A immer garantiert nach dem zweiten Befehl B ausgeführt wird. Zunächst werden Synchronisationsbefehle (d.h. Freigabe- und Wartebefehle) mit je einer Bedingungsvariable c je gemeinsam genutzter Speicherstelle SSi (Variable) eingefügt. In den so synchronisierten Programmabschnitten werden nun Dominatoren und Postdominatoren berechnet. Postdominiert jeder Freigabe- befehl 41 auf einer ersten Bedingungsvariable c jeden Freiga¬ bebefehl 41' auf einer zweiten Bedingungsvariable c', und do¬ miniert jeder Wartebefehl 42 auf der ersten Bedingungsvariab¬ le c jeden Wartebefehl 42' auf der zweiten Bedingungsvariable c', dann kann die zweite Bedingungsvariable c' zusammen mit ihren zugehörigen Freigabebefehlen 41' und Wartebefehlen 42' entfernt werden.
In dem in der FIG 3 gezeigten Beispiel kann der Lesebefehl 32' erst ausgeführt werden, nachdem der Freigabebefehl 41 auf der ersten Bedingungsvariable c ausgeführt wurde. Der nach¬ folgende Wartebefehl 42 ' , dessen zugehöriger Freigabebefehl 41' vor dem Freigabebefehl 41 ausgeführt wird, ist also überflüssig (der Freigabebefehl 41 postdominiert Freigabebefehl 41', und der Wartebefehl 42 dominiert den Wartebefehl 42 ' ) . Damit kann die zweite Bedingungsvariable c' zusammen mit den zugehörigen Synchronisationsbefehlen 41', 42' entfernt werden. Da auch die Synchronisationsbefehle 41', 42' Laufzeitkosten verursachen, kann dies zur Verringerung der Rechenzeit beitragen .
In dem oberen Teil der FIG 4 ist eine (nicht parallelisierte) erste Programmschleife 81 dargestellt, die einen Schreibbe¬ fehl 31 auf eine Speicherstelle SSi umfasst, und ein darauf folgender Programmabschnitt 84, der einen Lesebefehl 32 auf die Speicherstelle SSi umfasst.
Bei Programmschleifen 81, 82 ist zu beachten, dass sie eine Notation für eine Wiederholung des Schleifeninhalts 80, d.h. eine Notation für eine Kette von wiederholten Ausführungen des Schleifeninhalts 80 darstellen. Ein Programmabschnitt 84, der auf eine erste Programmschleife 81 folgt, schließt nicht an jeden Schleifendurchlauf der ersten Programmschleife 81 an, sondern nur an den zuletzt durchgeführten Schleifendurchlauf. Umgekehrt geht ein Programmabschnitt 84, an den eine zweite Programmschleife 82 anschließt, nicht jedem Schleifendurch¬ lauf der Programmschleife 82 voraus, sondern nur dem zuerst durchgeführten Schleifendurchlauf .
Wenn ein Programmabschnitt 84, der auf eine erste Programm- schleife 81 folgt, aus einer Speicherstelle SSi liest, die innerhalb der Programmschleife 81 beschrieben wird, muss also eine Ausführung des Programmabschnitts 84, der auf die erste Programmschleife 81 folgt, so lange angehalten werden, bis das Beschreiben der Speicherstelle SSi im letzten Schleifen- durchgang abgeschlossen ist. Dazu kann das Setzen der Bedingungsvariablen c (die Ausführung des Freigabebefehls 41) von der Bedingung abhängig gemacht werden, dass es sich um den letzten Schleifendurchgang handelt. Unter Beachtung dieser Maßgabe ist es nicht unbedingt erforderlich, den Freigabebe- fehl 41 ans Ende 86 der Programmschleife 81 zu setzen. Um an die Bedingtheit des Freigabebefehls 41 zu erinnern, ist der Freigabebefehl 41 in der FIG 4 gestrichelt gezeichnet.
Es kann jedoch unwirtschaftlich sein, wegen der Bedingtheit des Freigabebefehls 41 die Abbruchbedingung für die erste
Programmschleife 81 auszuwerten. Es kann auch sein, dass aus Übersichtlichkeitsgründen eine Überwachung der Abbruchbedingung zu diesem Zweck unerwünscht ist (beispielsweise bei ei¬ ner while-, for-each- oder forever-Schleife oder wenn die Ab- bruchentscheidung von einem variablen Abbruchkriterium abhängig ist, dessen Entscheidungsparameter erst zum Ende 86 der erste Programmschleife 81 und nicht schon zum Zeitpunkt des Freigabebefehls 41 vorliegen) . Es gibt auch die Alternative, den Freigabebefehl 41 zum Setzen der Bedingungsvariable c un- mittelbar hinter oder an das Ende 86 der vorher auszuführenden Programmschleife 81 einzufügen.
Umgekehrt gibt es auch den Fall, dass ein Schleifeninhalt 80 innerhalb einer (nicht parallelisierten) zweiten Programm- schleife 82 aus einer Speicherstelle SSi liest, die von einem vorausgehenden Programmabschnitt 84 beschrieben wurde. In dem unteren Teil der FIG 4 ist eine zweite Programmschleife 82 dargestellt, die einen Lesebefehl 32 auf eine Speicherstelle SSi umfasst und an den vorausgehenden Programmabschnitt 84 anschließt, der einen Schreibbefehl 31 auf die Speicherstelle SSi umfasst. Es muss sichergestellt werden, dass die Bedin¬ gungsvariable c bei Ausführung des Wartebefehls 42 zwar gele¬ sen und beachtet wird, aber erst anlässlich einer letztmali¬ gen Ausführung der zweiten Programmschleife 82 gelöscht wird. Dazu kann das Löschen der Bedingungsvariable c von der Bedin¬ gung abhängig gemacht werden, dass es sich um den letzten Schleifendurchgang handelt. Dann ist es nicht unbedingt er¬ forderlich, den Wartebefehl 42 an den Beginn 85 der Programmschleife 82 zu setzen. Um an die Bedingtheit des Löschens der Bedingungsvariable c durch den Wartebefehl 42 zu erinnern, ist der Wartebefehl 42 in der FIG 4 gestrichelt gezeichnet.
Es kann jedoch unwirtschaftlich sein, dafür die Abbruchbedingung für die zweite Programmschleife 82 auszuwerten. Bei¬ spielsweise kann aus Übersichtlichkeitsgründen eine Überwachung der Abbruchbedingung zu diesem Zweck unerwünscht sein (beispielsweise bei einer while-, for-each- oder forever- Schleife oder wenn die Abbruchentscheidung von einem variablen Abbruchkriterium abhängig ist, dessen Entscheidungsparameter erst zum Ende 86 der Programmschleife 82 und nicht schon zum Zeitpunkt des Wartebefehls 42 vorliegen) . Außerdem kann es unerwünscht sein, zwischen solchen Wartebefehlen 42 zu unterscheiden, mit denen die zugehörige Bedingungsvariable c zurückgesetzt wird und solchen, mit denen die zugehörige Bedingungsvariable c nicht zurückgesetzt wird. Es gibt auch die Alternative, den Wartebefehl 42 zum Warten auf die Bedingungsvariable c unmittelbar vor oder an den Beginn 85 der nachher auszuführenden Programmschleife 82 einzufügen.
Bezugs zeichenliste
10 sequentielles Programm
12 parallelisiertes Programm
21 erster Thread
22 zweiter Thread
31 Schreibbefehl; Schreibzugriff
32 Lesebefehl; Lesezugriff
41 Freigabebefehl
42 Wartebefehl
5j j-te Synchronisationsstelle
80 Schleifeninhalt
81 erste Schleife
82 zweite Schleife
84 Programmabschnitt
85 Beginn der Programmschleife
86 Ende der Programmschleife
PA1 erster Programmabschnitt
PA2 zweiter Programmabschnitt
SSi i-te Speicherstelle; i-te Ressource
c Bedingungsvariable
100 Verfahren
110 Schritt mit Abhängigkeitsanalyse
120 Schritt mit Analyse der Datenabhängigkeiten
130 Schritt des Einfügens von Synchronisationsbefehlen
131 automatisiertes Einfügen eines Freigabebefehls
132 automatisiertes Einfügen eines Wartebefehls

Claims

Patentansprüche
1. Verfahren (100) zum Einfügen von Synchronisationsbefehlen (31, 32) in Programmabschnitte (PA1, PA2) eines Programms (10, 12) ,
dadurch gekennzeichnet, dass
das Verfahren (100) folgende Schritte (131, 132) umfasst:
automatisiertes Einfügen (131) eines Freigabebefehls (41) nach einem Schreibbefehl (31) eines ersten Programmab- Schnitts (PA1) auf eine Ressource (SSi) , die von dem ers¬ ten Programmabschnitt (PA1) und einem zweiten Programmab¬ schnitt (PA2) gemeinsam genutzt wird, falls der Schreibbe¬ fehl (31) auf die Ressource (SSi) von dem ersten Programmabschnitt (PA1) vor einem Lesebefehl (32) des zweiten Pro- grammabschnitts (PA2) auf die Ressource (SSi) auszuführen ist, wobei eine Ausführung des Freigabebefehls (41) eine Bedingungsvariable (c) in einen Gesetztzustand versetzt; und
automatisiertes Einfügen (132) eines Wartebefehls (42) zum Warten auf den Gesetztzustand der Bedingungsvariable (c) vor dem Lesebefehl (32) des zweiten Programmabschnitts (PA2) auf die Ressource (SSi), wobei eine Ausführung des Wartebefehls (42) den zweiten Programmabschnitt (PA2) dazu veranlasst, mit einer Fortführung der Abarbeitung des zweiten Programmabschnitts (PA2) zu warten, bis die Bedin¬ gungsvariable (c) gesetzt ist.
2. Verfahren (100) nach Ansprüche 1,
dadurch gekennzeichnet, dass
das die Bedingungsvariable (c) anlässlich einer Programmini¬ tialisierung sowie bei einem Abarbeiten des zugehörigen Wartebefehls (42) zurückgesetzt wird.
3. Verfahren (100) nach Anspruch 1 oder 2,
dadurch gekennzeichnet, dass das Verfahren (100) einen Schritt (110) zur Erkennung einer Datenabhängigkeit zwischen parallel aufrufbaren Programmab¬ schnitten (PA1, PA2) umfasst.
4. Verfahren (100) nach einem der Ansprüche 1 bis 3,
dadurch gekennzeichnet, dass
das Verfahren (100) einen Schritt (120) zur Feststellung umfasst, welche Paare von Schreib- und Lesebefehlen (31, 32) in einer vorgegebenen Reihenfolge auszuführen sind und welche Reihenfolge hierbei einzuhalten ist.
5. Verfahren (100) nach einem der Ansprüche 1 bis 4,
dadurch gekennzeichnet, dass
das Verfahren (100) einen Schritt umfasst, in welchem ein Pfad erkannt wird, der einen Pfad mit einem zu synchronisie¬ renden Schreibbefehl (31) auf eine Ressource (SSi) überbrückt, und einen Schritt umfasst, in welchem in den überbrückenden Pfad ein Freigabebefehl (41) für diese Ressource (SSi) einge¬ fügt wird.
6. Verfahren (100) nach einem der Ansprüche 1 bis 5,
dadurch gekennzeichnet, dass
ressourcenspezifische oder partionsspezifische Bedingungsva¬ riablen (c) vorgesehen sind.
7. Verfahren (100) nach einem der Ansprüche 1 bis 6,
dadurch gekennzeichnet, dass
ein Laufzeitbedarf für unterschiedliche Alternativen von Partitionen ermittelt wird und dann die oder eine der Alternati- ven mit geringstem Laufzeitbedarf genutzt wird.
8. Verfahren (100) nach einem der Ansprüche 1 bis 7,
dadurch gekennzeichnet, dass
synchronisationsstellenspezifische Bedingungsvariablen (c) vorgesehen sind.
9. Verfahren (100) nach einem der Ansprüche 1 bis 8,
dadurch gekennzeichnet, dass
das Verfahren (100) einen Schritt umfasst, in dem eine zweite Bedingungsvariable (c') zusammen mit ihren zugehörigen Frei¬ gabebefehlen (41') und Wartebefehlen (42') entfernt wird, wenn jeder Freigabebefehl (41) auf einer ersten Bedingungsvariable (c) jeden Freigabebefehl (41') auf der zweiten Bedingungsvariable (c') postdominiert und jeder Wartebefehl (42) auf der ersten Bedingungsvariable (c) jeden Wartebefehl (42') auf der zweiten Bedingungsvariable (c') dominiert.
10. Vorrichtung (100) zum Einfügen von Synchronisationsbefehlen in Programmabschnitte (PA1, PA2) eines Programms (100), dadurch gekennzeichnet,
dass die Vorrichtung dazu vorbereitet ist, einen Freigabe¬ befehl (41) nach einem Schreibbefehl (31) eines ersten Pro¬ grammabschnitts (PA1) auf eine Ressource (SSi) einzufügen, die von dem ersten Programmabschnitt (PA1) und einem zwei¬ ten Programmabschnitt (PA2) gemeinsam genutzt wird, falls der Schreibbefehl (31) auf die Ressource (SSi) von dem ersten Programmabschnitt (PA1) vor einem Lesebefehl (32) des zweiten Programmabschnitts (PA2) auf die Ressource (SSi) auszuführen ist, wobei eine Ausführung des Freigabe¬ befehls (41) eine Bedingungsvariable (c) in einen Gesetzt¬ zustand versetzt; und
dass die Vorrichtung dazu vorbereitet ist, einen Wartebe¬ fehl (42) zum Warten auf den Gesetztzustand der Bedingungsvariable (c) vor dem Lesebefehl (32) des zweiten Programmabschnitts (PA2) auf die Ressource (SSi) einzufügen, wobei eine Ausführung des Wartebefehls (42) den zweiten Programmabschnitt (PA2) dazu veranlasst, mit einer Fort¬ führung der Abarbeitung des zweiten Programmabschnitts (PA2) zu warten, bis die Bedingungsvariable (c) gesetzt ist .
PCT/EP2012/062571 2011-12-20 2012-06-28 Verfahren und vorrichtung zum einfügen von synchronisationsbefehlen in programmabschnitte eines programms Ceased WO2013091908A1 (de)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE102011089180 2011-12-20
DE102011089180.3 2011-12-20

Publications (1)

Publication Number Publication Date
WO2013091908A1 true WO2013091908A1 (de) 2013-06-27

Family

ID=46506330

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2012/062571 Ceased WO2013091908A1 (de) 2011-12-20 2012-06-28 Verfahren und vorrichtung zum einfügen von synchronisationsbefehlen in programmabschnitte eines programms

Country Status (1)

Country Link
WO (1) WO2013091908A1 (de)

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050108695A1 (en) * 2003-11-14 2005-05-19 Long Li Apparatus and method for an automatic thread-partition compiler

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050108695A1 (en) * 2003-11-14 2005-05-19 Long Li Apparatus and method for an automatic thread-partition compiler

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
MCCLOSKEY, B. ET AL.: "Autolocker: Synchronization Inference for Atomic Sections", CONF. RECORD OF THE 33RD ACM SIGPLAN-SIGACT SYMPOSIUM OF PRINCIPLES OF PROGRAMMING LANGUAGES, POPL '06, pages 346 - 358
NAIK, M. ET AL., EFFECTIVE STATIC RACE DETECTION FOR JAVA, PROCEEDINGS OF THE ACM SIGPLAN CONFERENCE ON PROGRAMMING LANGUAGE DESIGN AND IMPLEMENTATION, PLDI '06, pages 308 - 319

Similar Documents

Publication Publication Date Title
DE68921906T2 (de) Verfahren für ein Multiprozessorsystem mit sich selbst zuordnenden Prozessoren.
EP0907912B1 (de) Synchronisationsverfahren
EP0689694B1 (de) Verfahren zur maschinellen erzeugung von nebenläufig bearbeitbaren befehlsgruppen aus einem programm für superskalare mikroprozessoren
DE69030523T2 (de) Synchronisierung für Multiprozessorsystem
DE69803624T2 (de) Verfahren und Vorrichtung zur generationellen Freispeichersammlung in einem gemeinsam verwendeten Heapspeicher mittels mehrerer Prozessoreinheiten
DE10335989B4 (de) Online-Änderungen von CIL-Code-Programmen für die Industrieautomatisierung
DE10393260T5 (de) Nachdurchgangs-Binäranpassung für eine auf Software basierende spekulative Vorberechnung
LU93299B1 (de) Ablaufsteuerung von Programmmodulen
WO2017140504A1 (de) Verfahren und vorrichtung zum betreiben eines steuergeräts
EP3770766A1 (de) Verfahren zum testen eines systems
DE102016221526A1 (de) Vorrichtung und Verfahren zum Bearbeiten einer Mehrzahl Aufgaben
WO2005076129A1 (de) Verfahren zur konfiguration eines computerprogramms
WO2001040931A2 (de) Verfahren zum synchronisieren von programmabschnitten eines computerprogramms
DE102009050161A1 (de) Verfahren und Vorrichtung zum Testen eines Systems mit zumindest einer Mehrzahl von parallel ausführbaren Softwareeinheiten
DE102023203627A1 (de) Verfahren zur Erzeugung von wenigstens einem neuen Testfall für einen Fuzzing-Softwaretest
DE102006029138A1 (de) Verfahren und Computerprogrammprodukt zur Detektion von Speicherlecks
WO2013091908A1 (de) Verfahren und vorrichtung zum einfügen von synchronisationsbefehlen in programmabschnitte eines programms
EP3759594B1 (de) Verfahren zum ausführen eines computerprogrammes in einem rechnerverbund zum steuern eines mikroskops
WO2006045754A1 (de) Verfahren, betriebssystem und rechengerät zum abarbeiten eines computerprogramms
DE602004007475T2 (de) Verfahren und System zur Erkennung von möglichen Blockierungen in Computerprogrammen
EP4055472B1 (de) Verfahren zur datenmigration eines zeigerelements im zuge einer datenmigration eines programmzustands eines steuerprogramms eines automatisierungssystems
DE102022211270A1 (de) Verfahren zum Testen eines in einer objektorientierten Skriptsprache programmierten Computerprogramms sowie System, Computerprogramm und computerlesbares Speichermedium
WO2013091907A2 (de) Verfahren und vorrichtung zum schützen kritischer abschnitte in threads eines programms
DE102020102996A1 (de) Verfahren für einen integrierten Entwurf zur Modellierung, Simulation und Test einer Echtzeit-Architektur innerhalb einer modellbasierten System- und Softwareentwicklung
DE102024210226A1 (de) Computerimplementiertes Verfahren zum Ausführen eines Prozesses in einer Recheneinheit

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 12733640

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 12733640

Country of ref document: EP

Kind code of ref document: A1