Tutorial 3 QnA

Index

• Index
• Q1: synchronises-with is not symmetric
• Q2: When increments happen
  • Addendum to 4.5 example
• Q3: Release Sequences Revisited
  • Relaxed RMW cannot head release sequences
  • Non RMW operations break release sequence chains
  • Synchronises-with inside release sequences

Q1: synchronises-with is not symmetric

Is synchronized-with a symmetric relation? That is, if X synchronizes with Y, then does Y synchronize with X too? My guess is that it’s not, because for X to sync with Y, its release must be on the same memory location as Y’s acquire, so this relationship is inherently directed. But if it’s directed, then in Tut 3 slide 4.4 DON’T Relax Everything, how can we be sure that the sw arrow points right? What’s stopping it from pointing left and leading to a data race?

This is an interesting question. The slide in question:

You are right to say that synchronizes-with relationship is directed. We can infer this from cppreference about memory order.

For this example, because we included acq_rel constraints, we force a hb relationship between (b) and (p). As you correctly point out, there is nothing stopping “b hb p” or “p hb b”.

But, we see that the structure of the if code means that (q) will always happen after the decrement that sees old_count == 1.

Relevant code snippet:

0
1
2
3
4
5
6
7
8

~SharedPtr4()
{
    size_t old_count = m_count->fetch_sub(1, std::memory_order::acq_rel);
    if(old_count == 1) // can only trigger for the last decrement in the example!
    {
        delete m_ptr;
        delete m_count;
    }
}

Since acq_rel orders the decrements and (q) must happen after the last decrement, we know where (q) will be in the coherence order.

The only possible coherence orders given the constraints and structure of the code are:

• [a,s,b,p,q] <--- the tutorial example uses this, where b sw p
• [a,s,p,b,q] <--- it is possible that p sw b, leading to this

Exercise for you: prove that any other coherence order will result in either a violation of the constraints or a situation where the shared pointer deletes itself before the next thread can be spawned to increment m_count.

Can we say for sure which coherence order happens during runtime? No. Either can occur.

So, if during runtime, b sw p, then we get Figure A. If p sw b, then the figure will look like this instead:

For sake of discussion, the tutorial example fixes the coherence order to be the former to show how adding acq-rel enforces a hb relationship, preventing (q) from ever happening before a decrement.

To sum up, the acq_rel constraints and if will force the coherence order to behave such that the delete must always happen after all the decrements, resolving the data race.

Q2: When increments happen

In slide 4.4 Relax Everything, the one with the diagram with 5 boxes, where exactly does the increment of m_count from 1->2 happen?

The slides for 4.4 have been updated to account for every increment from zero.

Addendum to 4.5 example

The example 4.5 in the tutorial sheet (html file) might cause confusion since the modificaion order does not start from 0.

Some of you may be confused how this can happen based on shared pointer increments.

So, I adapted¹ the example to start the count from zero, where thread 1 creates the SharedPtr. The adapted example is a bit more complicated but follows the exact same logic as the tutorial sheet’s example to prove that (b) hb (u).

The adapted example are on the slides for your reference, highlighted in yellow.

Q3: Release Sequences Revisited

What are the possible release sequences? Why do we use (b) in 4.5 as the head?

To answer the 1st qn, I will illustrate more clearly how we can get release sequences.

Consider an arbitrary modification order, where:

$ A_{\text{acq-rel}}, B_{\text{acq-rel}}, C_{\text{acq-rel}}, D_{\text{acq-rel}} $

Assume all the letters are read-modify-write operations.

Recall:

A release sequence headed by a release operation A on an atomic object M is a maximal contiguous sub-sequence of side effects in the modification order of M, where the first operation is A, and every subsequent operation is an atomic read-modify-write operation.

The possible release sequences are any subset (in order!) of the chain:

• A,B,C,D (where A is the head)
• B,C,D (where B is the head)
• C,D (where C is the head)

There are a few properties and caveats.

Relaxed RMW cannot head release sequences

If we change B to be relaxed, the release sequences are:

• A,B,C,D
• C,D

Notice how B can no longer head the release sequence because it cannot be a release operation.

Note that for acq_rel, cppreference defines such operations as “both an acquire operation and a release operation”.

Non RMW operations break release sequence chains

If we change B to be load/store, the release sequences in the ModO are:

• C,D

Notice that B breaks the release sequence chain. Elements of a release sequence must ONLY be RMW operations.

Synchronises-with inside release sequences

Recall:

An atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M and takes its value from any side effect in the release sequence headed by A.

Given a release sequence, we can basically say that the head will sw any element of the release sequence that is an acquire.

For this modification order,
$ A_{\text{acq-rel}}, B_{\text{acq-rel}}, C_{\text{acq-rel}}, D_{\text{acq-rel}} $

Headed by A, we get:

• A sw B, A sw C, A sw D.

Headed by B, we get:

• B sw C, B sw D

Headed by C, we get:

• C sw D

If we change B to relaxed,
$ A_{\text{acq-rel}}, B_{\text{relaxed}}, C_{\text{acq-rel}}, D_{\text{acq-rel}} $

Note the changes to the relationships:

Headed by A, we get:

• A sw B, A sw C, A sw D.

Headed by B, we get: // We no longer have a release seq headed by B!

• B sw C, B sw D

Headed by C, we get:

• C sw D

Note that for A sw C, operation C can still read the side effect from B².

If these examples are clear, then you will understand how we got the release sequence for 4.5 and the sw relationships.

So, why use (b) as the release sequence head in example 4.5?

Out of the different release sequences possible for example 4.5, only the release sequence headed by (b) allows us to show that (b) sw (t), therefore (b) hb (u), showing that there’s no data race between (b) and the nonatomic delete (u).