5

The part of the language specification dedicated to the Java Memory Model (JMM) (link) mentions "execution trace" a lot.

For example right from the start:

A memory model describes, given a program and an execution trace of that program, whether the execution trace is a legal execution of the program. The Java programming language memory model works by examining each read in an execution trace and checking that the write observed by that read is valid according to certain rules.

But I cannot find there any description/definition of this term.

So, what is "execution trace" exactly according to the JMM, and what exactly does it consist of?
References to specific places in the language specification text are most welcome.

Improve this question
2
  • A single program allows for many different executions. An execution trace is the data collected for one of these executions. Commented Aug 2, 2022 at 7:27
  • @pveentjer yes. You provided the definition of the execution trace. I would add to it that the composition of "the data collected" is specified in the JLS as a mathematical object "execution E". So, as I understand: 1. a program run is an execution; 2. the data recorded during the run is an execution trace; 3. from the data we build a mathematical object execution E which we use to check if the program run was valid according the the JMM rules. Commented Aug 2, 2022 at 19:15

2 Answers 2

Reset to default
3

You're right; it's not very clear. They also refer to it as "program trace", and simply "trace" on its own.

The following is a quote:

Consider, for example, the example program traces shown in Table 17.4-A.

Table 17.4-A.

Thread 1 Thread 2
B = 1; A = 2;
r2 = A; r1 = B;

So, it's simply an ordered list of statements, per thread, representing one possible permutation of how the statements may be executed (since statement may be reordered). A trace may be valid or invalid within the JMM; they are used to exemplify what is legal and what is not.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

"ordered list of statements" — what is the order? As far as I understand, there are some orders defined in the spec (e.g. program order, synchronization order, etc.), but these are just parts of an abstract mathematical model (which the JMM is), and in reality the program is free to do anything as long as the end result of the program execution doesn't contradict to the JMM.
@sanyok The order is the order of execution in a permutation (not necessarily valid or congruent with the original code). You can see that they contrast table 17.4-A with 17.4-B where the statements of the first thread are swapped (validly).
@sanyok Put another way, a program may be executed as any of N valid execution traces, and may not be executed as any of M invalid execution traces, where validity of a trace is determined by the JMM.
IMO "order of execution" is problematic with modern out-of-order CPUs: we know the order of instructions in our program, but don't really know anymore when the instruction execution really finishes.
I edited your answer to make the table a real quote (tip: use > (i.e. > + space) before each line). You may want to add a link to the source of the quote.
|
0

This is not a full-fledged answer, but I think this is worth mentioning.

Even if we don't know what an "execution trace" is in details, we can deduce which information it should provide.

Let's read the first paragraph of 17.4. Memory Model:

A memory model describes, given a program and an execution trace of that program, whether the execution trace is a legal execution of the program. The Java programming language memory model works by examining each read in an execution trace and checking that the write observed by that read is valid according to certain rules.

This means that "a program" (i.e. source code) and "an execution trace" should provide all the information required to determine whether the program execution is legal.
The information is described in 17.4.6. Executions.
I'm not going to copy-paste it here because it's too long.
I'll try to explain it in simple words instead:

  • a program consists of statements, each statement consists of (possibly nested) expressions evaluated in some order
  • an execution of a thread can be represented as a sequence of actions: one action per every simple expression
  • an execution of a program is several threads executing in parallel
  • an execution trace should provide information about actions performed during the program execution, i.e. it should provide provide the following information:

    • all executed actions: a sequence of actions per every thread

      Note: the JMM only cares about so called inter-thread actions (17.4.2. Actions):

      An inter-thread action is an action performed by one thread that can be detected or directly influenced by another thread

      Inter-thread action kinds:

      • read/write
      • volatile read/write
      • lock/unlock
      • various special and synthetic actions (e.g. thread start/stop, etc.)

    • for every action it should store:

      • thread id
      • action kind
      • what expression in the source code it corresponds to
      • for write and volatile write: the written value
      • for read and volatile read: the write action, which provided the value
      • for lock/unlock: the monitor being locked/unlocked
      • various relations with other actions (e.g. position in a so-called synchronization order for synchronization actions)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.