Attempting to catch memory reordering in .NET

Question

I have a slightly bizarre program in which I am attempting to catch some memory reordering in .NET:

private static volatile int x, y;
private static int b = -1;
private static int a = -1;

static void Main()
{
    Run(); 
}

public static void Run()
    {
        Random rand = new Random();
        var time = DateTime.Now;
        while ((a != 0 || b != 0))
        {
            int t1StartId = rand.Next(1, 10);
            int t2StartId = rand.Next(1, 10);

            Thread t1 = new Thread(RunOne);
            Thread t2 = new Thread(RunTwo);

            for (int i = 0; i <= 10; i++)
            {
                if (t1StartId == i)
                {
                    t1.Start();
                }

                if (t2StartId == i)
                {
                    t2.Start();
                }
            }

            t1.Join();
            t2.Join();
            x = 0;
            y = 0;
        }

        Console.WriteLine("Memory Reordered!!!!!!!!!!!!!!!!!!!!!");
        Console.WriteLine("Time Taken: {0}", DateTime.Now - time);
    }

    static void RunOne()
    {
        x = 1;
        a = y;
    }

    static void RunTwo()
    {
        y = 1;
        b = x;
    }
}

Now from the reading I have been doing (here, here, here, here), it *should be possible for both a and b to equal 0 after each thread has completed executing. Is anyone able to confirm this? Are any of my operations presenting a memory barrier under the scenes of which I am not aware of which would prevent reordering and thus keep the infinite loop going?

I am running this on x86 CPU, which I suspect could also have impact on the result.

edit:

So after running the program multiple times it is now getting out of the loop:

I'm still not convinced this is a result of memory reordering.

Second run:

So conclusive question! - Is this truly a result of memory reordering, or is it something else?

You seem to have two contradictory questions. One question asks whether reordering is possible in your example, or if you've introduced a memory barrier that would prevent it. The other question asks "is this truly a result of memory reordering?" Well, I don't see how it could be anything else. Without reordering, your code would run forever. That's clear enough just working through the logic in the code. Since it must be reordering, it seems to me that answers the first question too: of course reordering is possible, because you've seen it. — Peter Duniho, Nov 15 '15 at 05:01

score 3 · Accepted Answer · answered Nov 16 '15 at 17:55

3

Yes, your example demonstrates memory reordering. I could not reproduce it myself, but that's probably a result of my specific setup.

I will use a down arrow ↓ to represent a volatile read and an up arrow ↑ to represent a volatile write. Think of the arrow head as pushing away any other reads and writes. The code that generates these memory fences is free to move around as long as no instruction goes up through a down arrow and down through an up arrow. The memory fences (the arrows), however, are locked in place at the spot where they were originally declared in the code. So reproducing your code with the fences illustrated would look like this.

static void RunOne()
{
    ↑                 // volatile write fence
    x = 1;            
    var register = y; 
    ↓                 // volatile read fence
    a = register;
}

static void RunTwo()
{
    ↑                 // volatile write fence
    y = 1;
    var register = x;
    ↓                 // volatile read fence
    b = register;
}

So you can see that in RunOne the write to x and the read of y can be swapped legally. Similarly in RunTwo the write y and the read of x can be swapped legally as well.

The fact that you are using the x86 architecture has no implication on this example because a volatile write followed by a volatile read is the only arrangement still allowed to be swapped in the x86's strong memory model.

answered Nov 16 '15 at 17:55

Brian Gideon

47,849
13
107
150

Great, thanks for the responses. Interestingly I am also not able to reproduce this on my work pc, while my home PC will normally have reordered the operations within ~1-5mins. But like you say it's most likely to do with something setup related – William Nov 16 '15 at 19:18
Hi Brian . why did you add `register ` for ? – Royi Namir Jan 07 '16 at 20:39
@RoyiNamir: To more clearly delineate the separation of the read of `x` and `y` from the write to `a` and `b`. It's not quite as obvious when both operations are packed into a single line. I chose `register` because a cpu register would be involved in the load and store operations. – Brian Gideon Jan 07 '16 at 21:18
Yes but isn't the whole operation should be within the push arrow head scope ? I mean ↑ x = 1; var register = y; a = register ↓ – Royi Namir Jan 07 '16 at 21:24
@RoyiNamir: No. The read of `y` and write to `a` are two different operations. Only the operation acting on `y` generates a memory barrier. Since a volatile read produces an acquire-fence the arrow must immediately follow the read. Remember, `a=y` is composed of two independent operations in which the rhs happens before the lhs. – Brian Gideon Jan 08 '16 at 05:13

Attempting to catch memory reordering in .NET

1 Answers1