Implementing synchronization algorithm in C#

Question

Hi

I trying to implement synchronization algorithm in C#, without success.

Why isn't the following code thread safe?

using System;
using System.Threading;

namespace SoftwareLockTest
{
    class Program
    {
        private static volatile bool _isLocked1 = false;
        private static volatile bool _isLocked2 = false;
        private static volatile int _count = 0;

        static void Main(string[] args)
        {
            Thread thread2 = new Thread(Thread2Work);
            thread2.Start();

            Thread1Work();
        }

        public static void Thread1Work()
        {
            while (true)
            {
                _isLocked1 = true;

                while (_isLocked2)
                {
                    _isLocked1 = false;
                    while (_isLocked2) ;
                    _isLocked1 = true;
                }

                CriticalSection();
                _isLocked1 = false;
            }
        }

        public static void Thread2Work()
        {
            while (true)
            {
                _isLocked2 = true;

                while (_isLocked1)
                {
                    _isLocked2 = false;
                    while (_isLocked1) ;
                    _isLocked2 = true;
                }

                CriticalSection();
                _isLocked2 = false;
            }
        }

        private static void CriticalSection()
        {
            if (_count != 0)
            {
                Console.WriteLine("NOT THREAD SAFE 1");
                _count = 0;
            }

            _count++;

            if (_count != 1)
            {
                Console.WriteLine("NOT THREAD SAFE 2");
            }

            _count--;

            if (_count != 0)
            {
                Console.WriteLine("NOT THREAD SAFE 3");
            }
        }
    }
}

Answer 1

Well, it isn't entirely clear what you are trying to do with the lock flags, and understanding the code is critical with threading, but in the absence of lock / Monitor, I would expect to see a lot of Interlocked for the increment (.Increment) / decrement (.Decrement) / test (.CompareExchange). Just because it is volatile doesn't mean that two threads can't get tripped up when doing ++/--.

But frankly, I would just use a lock unless you have a good reason not to. You want to keep it simple - "obviously no bugs", rather than "no obvious bugs".

Answer 2

Why don't you simply use lock?

lock (_anyInstantiatedObject)
{
    CriticalSection();
}

That way you rely on OS to take care that no other thread enters the critical section at the same time.

Answer 3

I'm still trying to work this out, and obviously normally you should indeed use locks... but I suspect the problem is that volatile probably doesn't mean exactly what you think it should.

I expect you think it means "when I write to this variable, make that write visible immediately; when I read from this variable, read an absolutely up-to-date value". It doesn't mean quite that (despite what MSDN says and indeed my own threading tutorial; I need to update that when I've got a better handle on it).

I'll see if I can work out exactly what's going on, but it does look odd. I think I understand what your code is trying to do, and I haven't managed to break it when making the "simple" assumption about volatility yet... (and I've reproduced the problem, which is always helpful)

Answer 4

The problem is that a write followed by a read may be reordered (even with "volatile"). You need to call Thread.MemoryBarrier(); in front of the four "while (_isLockedX)" loops.

Please read http://www.albahari.com/threading/part4.aspx for an explanation of memory barriers and volatile.

For any real project, please prefer existing lock implementations instead of trying to make your own.

Answer 5

Amusingly, this same query was up on codeguru a few hours ago... here's my reply, adapted from there, but the high bit is you need a memory fence for this code to work right.

The problem with your code is that it relies on your system to be sequentially consistent. x86 systems are not SC. They are what is known as processor consistent.

Its very subtle, so lets simplify your code just a tad:

thread1:

WRITE _isLocked1, 1
READ _isLocked2
(skip the while loop)
critical section
WRITE _isLocked1, 0

thread2:

WRITE _isLocked2, 1
READ _isLocked1
(skip the while loop)
critical section
WRITE _isLocked2, 0

Processor consistency only says that thread1 observes the writes done by thread 2 in the order they are performed (so write 1 then write 0). Conversely thread 2's observation of thread 1's writes. What is biting you is processor consistency says little about how the writes from thread1 are interleaved with the writes from thread2, except that causality of dependent operations are maintained (which isn't important to your example).

The AMD documentation Volume 2, section 7.2 has a nice set of examples on this that will help you see it and references Dekker's algorithm and why it needs a memory fence on x86 systems.

Answer 6

You are trying to implement Dekker's algorithm. Unfortunately, he lived in simpler times, back when hardware designers and software engineers were still talking to each other. The cut-throat competition between vendors in the PC business, emphasizing speed and cores, spelled doom to Mr. Dekker's ingenuity. Kinda glad, I must have reviewed that algorithm dozens of times and never not got a headache.

Well, that's kinda meta. Review the "Note" in that Wikipedia article to see why the algorithm doesn't work anymore. You got plenty of alternatives offered that do work. Key point is that what ever literature you find about concurrency that's over 5 years old is no longer relevant.