multithreading - Duplicate math result in Bakery Algorithm (C# code)

Question

Index out of bounds when create new thread with parameters? - Continue to my previous topic , now i got a new problem with my my Bakery Algorithm code !

Here's my code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace BakeryAlgorithm
{
    class Program
    {
        static int threads = 10;
        static string x = "";
        static int count = 0;
        static int[] ticket = new int[threads];
        static bool[] entering = new bool[threads];

        public static void doLock(int pid)
        {
            for (int i = 0; i < threads; i++)
            {
                ticket[i] = 0;
                entering[i] = false;
            }
                entering[pid] = true;

            int max = 0;

            for (int i = 0; i < threads; i++)
            {
                if (ticket[i] > ticket[max]) { max = i; }
            } 

            ticket[pid] = 1+max;
            entering[pid] = false;


            for (int i = 0; i < threads; ++i)
            {
                if (i != pid)
                {
                    while (entering[i]) 
                    {
                        Thread.Yield();   
                    } 
                    while (ticket[i] != 0 && (ticket[pid] > ticket[i] ||
                              (ticket[pid] == ticket[i] && pid > i)))
                    {
                        Thread.Yield();
                    }
                }
            }  
           if (x == "C" || x == "c")
Console.WriteLine("[System] PID " + pid.ToString() + " get    into critical section"); 
        }

        public static void unlock(int pid)
        {
            ticket[pid] = 0;
            count++;
            Console.WriteLine("[Thread] PID " + pid.ToString() + " complete.");
        }

        public static void arrayInit()
        {
            for (int i = 0; i < threads; i++)
            {
                ticket[i] = 0;
                entering[i] = false;
            }
        }

        public static void simThread(int i)
        {
            doLock(i);
            if (x == "C" || x=="c")
            Console.WriteLine("[Thread] PID " + i.ToString() + " begin to process...");
            //Do some thing ????
            Random rnd = new Random((int)DateTime.Now.Ticks & 0x0000FFFF);
            int a = rnd.Next(1,99); 
            int b = rnd.Next(1,99);
            int c = rnd.Next(1,4);

            int d = 0;
            string o="";

            if (c == 1)
            {
                d = a + b;
                o="+";
            }
            else if (c == 2)
            {
                d = a * b;
                o="*";
            }
            else if (c == 3)
            {
                d = a / b;
                o="/";
            }
            else
            {
                d = a - b;
                o="-";
            }

            if (x == "C" || x == "c")
                Console.WriteLine("Math Result : " + a.ToString() + o + b.ToString() + "=" + d.ToString());
            unlock(i);
        }
        [STAThread]
        static void Main(string[] args)
        {
            arrayInit();
            string choice="C";
            while (choice == "C" || x == "c")
            {
                        Console.WriteLine("Process log (C=Yes,K=No) : ");
                        x = Console.ReadLine();
                        if (x == "")
                            x = "C";

                Console.Clear();
                Console.WriteLine("----------------------------------");
                Console.WriteLine("Bakery Algorithm C#");
                Console.WriteLine("Number of threads : " + threads.ToString());
                Console.WriteLine("Process Log...");
                Console.WriteLine("----------------------------------");

                Thread[] threadArray = new Thread[threads];
                for (int i = 0; i < 10; i++)
                {
                    int copy = i;
                    threadArray[i] = new Thread(() => simThread(copy));
                    if (x == "C" || x == "c")
                    Console.WriteLine("[System] PID " + i.ToString() + " created");
                    threadArray[i].Start();
                }

                Console.ReadLine();
                Console.WriteLine("----------------------------------");
                Console.WriteLine("Complete processed " + count.ToString() + " threads !");
                count = 0;
                Console.WriteLine("----------------------------------");


                        Console.WriteLine("You want to restart  (Yes=C or No=K)");
                        choice = Console.ReadLine();
                        if (choice == "")
                            choice = "C";
            }
        }
    }
}

The result are here :

2*2=4
2*2=4 << duplicated
3*2=6
4*2=8
4*6=24
4*2=8 << duplicated

.... and continue with duplicate values ( random position ) !

Hope somebody here can help !

Answer 1

There's many things wrong with your code, but the most important part is that you didn't read the requirements that make Lamport's bakery work:

Lamport's bakery algorithm assumes a sequential consistency memory model.

You will be hard-pressed to find a modern computer that has sequential consistency.

So even if your implementation was correct with respect to those constraints, it would still be wrong on pretty much any computer that runs .NET. To make this work on a modern CPU and in .NET, you'll need to insert memory barriers to prevent instruction reordering and introduce cache refreshing to make sure each CPU core sees the same values... and by then you're probably better off using different synchronization primitives altogether.

Now, fixing these kinds of algorithms tends to be rather hard - multi-threading is hard on its own, doing lock-less multi-threading just pushes this to absurd territory. So let me just address some points:

1) You can't just use new Random() and expect statistically random numbers from that. Random has an internal state that's by default initialized to the current OS tick - that means that creating 10 Randoms in a row and then doing Next on each of those is pretty likely to produce exactly the same "random" numbers.

One way of handling that gracefully would be to have a thread-local field:

ThreadLocal<Random> rnd 
  = new ThreadLocal<Random>(() => new Random(Guid.NewGuid().GetHashCode()));

Each of your threads can then safely do rnd.Value.Next(...) and get reliable numbers without locking.

However, since the whole point of this excercise is to allow shared access to mutable state, a solution more in line with the task would be to use a single shared Random field instead (created only once, before starting the threads). Since the Bakery algorithm is supposed to make sure you can safely use shared stuff in the critical section, this should be safe, if implemented correctly :)

2) To actually make the Bakery part work, you need to enforce the only proper instruction ordering.

This is hard. Seriously.

I'm not actually sure how to do this safely.

The best way to start is to insert an explicit memory barrier before and after each read and write of shared state. Then you can go one by one and remove those that aren't necessary. Of course, you should only need this in the doLock and unlock methods - the rest of simThread should be single-threaded.

For a short sample:

Thread.MemoryBarrier();
entering[pid] = true;
Thread.MemoryBarrier();

int max = 0;

for (int i = 0; i < threads; i++)
{
  if (ticket[i] > ticket[max]) { max = i; }
} 

Thread.MemoryBarrier();
ticket[pid] = 1+max;
Thread.MemoryBarrier();
entering[pid] = false;
Thread.MemoryBarrier();

So, which one of those is it safe to remove? I have no idea. I'd have to use a lot of mental power to make sure this is safe. Heck, I'm not sure if it's safe as is - do I need to rewrite the for cycle too? Are ticket[i] and ticket[max] going to be fresh enough for the algorithm to work? I know some are definitely needed, but I'm not sure which can safely be left out.

I'm pretty sure this will be slower than using a simple lock, though. For any production code, steer clear away from code like this - "smart" code usually gets you in trouble, even if everyone in your team understands it well. It's kind of hard finding those kinds of experts, and most of those wouldn't touch lock-less code like that with a meter-long stick :)