1

As we know, the compiler or the CPU may reorder the execution as they want, only if they follow the as-if rule. For example, if we have such a piece of code:

C = A + B;
D = E + F;

The compiler or the CPU may execute D = E + F before C = A + B. I can understand that.

Now let's talk about another case.

Saying that I have two threads a and b. I want to set some marks while executing so that I can monitor the whole process of a and b.

queue q; // thread safe

void thread_a()
{
    // do something
    q.push("a - 1");
    // do something
    q.push("a - 2");
}

void thread_b()
{
    // do something
    q.push("b - 1");
    // do something
    q.push("b - 2");
}

My question is: since we have the as-if rule and the execution order may be reordered, does it mean that the messages in the q is not reliable? Meaning that the real execution order is a - 1, b - 1, b - 2 and a - 2 but in the q there might be a - 1, a - 2, b - 1 and b - 2? If this could happen, how should I design or which kind of techinque should I use to monitor the process of multi-threading?

Yves
  • 11,597
  • 17
  • 83
  • 180
  • Just to check: You say `queue q;` is thread safe. You're aware [`std::queue` is *not* thread safe](https://stackoverflow.com/q/36762248/364696), right? Actual thread safe queues using locking (or lockless atomics) would almost certainly enforce ordering constraints (at the very least acquire/release semantics) that would inhibit arbitrary reordering. – ShadowRanger Mar 24 '21 at 02:35
  • I'm somewhat skeptical that both pushes can be reordered in this fashion. Can you kindly show an example of such a novel `queue` where that's true? – Sam Varshavchik Mar 24 '21 at 02:36
  • @SamVarshavchik Does it matter? There does exist some thread-safe queue, right? Or we can use mutex in the two functions. Are you telling me that thread-safe queue or mutex in the two functions would forbid the reordering? – Yves Mar 24 '21 at 02:39
  • If the queue is not thread safe then another thread could observe a queue of size 2 with no entries. Or only one of the two entries. – Zan Lynx Mar 24 '21 at 02:42
  • @ShadowRanger OK, so what about thread-unsafe queue with mutex in the two functions? I mean I set a mutex before I execute `q.push()`. Will this also inhibit reordering? – Yves Mar 24 '21 at 02:42
  • 2
    You need to define what the `real execution order` is. None of the source code lines in the given example is an atomic operation (*even* in a thread safe implementation). It is entirely possible that execution steps into `q.push("b - 1");` before `q.push("a - 1");` starts, but returns after it ended. – dxiv Mar 24 '21 at 02:43
  • I'm sure that there is a thread-safe queue. But there is always a big difference in which order things get pushed into a queue. Otherwise it wouldn't be a queue. Therefore, the order of things getting pushed into a queue is material, and cannot be reordered. The End. – Sam Varshavchik Mar 24 '21 at 02:47
  • The compiler can not change the order in-which threads execute. It can only change the order in-which a single threads instructions execute while that thread is running. – Galik Mar 24 '21 at 02:49
  • @Galik That's enough man. If the compiler move `q.push("a - 2")` forward a little, things in the `q` could be different. – Yves Mar 24 '21 at 02:53
  • But that would break the "as if" rule. A queue is a queue after all. `q.push("a - 2")` must come after `q.push("a - 1")`. – Galik Mar 24 '21 at 02:54
  • The compiler has no control over when each thread runs, if at all. So the relative timing of the threads is irrelevant. They could run 1 week apart for all the compiler knows. It can only select the order of instructions in any single thread. – Galik Mar 24 '21 at 02:56
  • It is the Operating System's thread scheduler that will decide if the queue contents gets interleaved between what `thread_a` does and what `thread_b` does, not the compiler. – Galik Mar 24 '21 at 02:59
  • @dxiv Good point. I understand what you said. So it means that trying to monitor such a thing is kind of meaningless... – Yves Mar 24 '21 at 10:06

1 Answers1

1

Reordering and multithreading are 2 different things:

Via multi threading, possible outputs are:

  • "a - 1", "a - 2", "b - 1", "b - 2"
  • "a - 1", "b - 1", "a - 2", "b - 2"
  • "a - 1", "b - 1", "b - 2", "a - 2"
  • "b - 1", "b - 2", "a - 1", "a - 2"
  • "b - 1", "a - 1", "b - 2", "a - 2"
  • "b - 1", "a - 1", "a - 2", "b - 2"

You just have the guaranty that "a - 1" comes before "a - 2", and "b - 1" comes before "b - 2". (unrelated to reordering)

Reordering with the as-if rule is just an optimization.

as_if states:

The C++ compiler is permitted to perform any changes to the program as long as the following remains true:

  1. Accesses (reads and writes) to volatile objects occur strictly according to the semantics of the expressions in which they occur. In particular, they are not reordered with respect to other volatile accesses on the same thread. (since C++11)
  2. At program termination, data written to files is exactly as if the program was executed as written.
  3. Prompting text which is sent to interactive devices will be shown before the program waits for input.
  4. If the ISO C pragma #pragma STDC FENV_ACCESS is supported and is set to ON, the changes to the floating-point environment (floating-point exceptions and rounding modes) are guaranteed to be observed by the floating-point arithmetic operators and function calls as if executed as written, except that the result of any floating-point expression other than cast and assignment may have range and precision of a floating-point type different from the type of the expression (see FLT_EVAL_METHOD) notwithstanding the above, intermediate results of any floating-point expression may be calculated as if to infinite range and precision (unless #pragma STDC FP_CONTRACT is OFF)

Your code (except potentially the // do something) does nothing of that, so it can even drop the 2 code completely, push "c - 1".

But if after you print queue content, then the content should be one of the 6 shown above.

Jarod42
  • 203,559
  • 14
  • 181
  • 302