This is the tenth part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

We have already seen how to implement custom mutex using memory mapped files and CAS operation. It has one drawback — it is not reentrant. Actually, if we try to take if recursively we will end up with deadlock. Today we will fix it.

Since our mutex protocol requires a delegate to execute while holding mutex (kind of a RAII pattern or try-with-resources approach) we don’t need to worry about taking the mutex and not releasing it. Conceptually, this is not allowed:

mutex.Lock()
mutex.Lock() // again
...
mutex.Release()
// Not releasing again

It is guaranteed that mutex will be released once it’s taken. Well, this is not 100% true as there are AccessViolation exceptions resulting in finally block not being executed but we will ignore this fact. So, we don’t need to take lock for the second time if we can guarantee that we won’t try releasing it.

Let’s see this code:

using System;
using System.Diagnostics;
using System.IO.MemoryMappedFiles;
using System.Linq;
using System.Runtime.InteropServices;
using System.Threading;

namespace MutexUtils
{
    public static class MutexUtils
    {
        [DllImport("kernel32.dll", SetLastError = true)]
        unsafe public static extern long InterlockedCompareExchange64(long* destination, long exchange, long comperand);

        public static unsafe bool DoWithMutex(string name, Action action, int timeoutInSeconds = int.MaxValue, int spinTimeout = 250)
        {
			var myPid = Process.GetCurrentProcess().Id;
			var myTid = AppDomain.GetCurrentThreadId();
			
            // Store <PID><TID> as one field
            long myIdentifier = ((long)myPid << 32) + myTid;

            // Calculate timeout wall clock
            DateTime end = DateTime.UtcNow.AddSeconds(timeoutInSeconds);

            // Open memory mapped file initialized with zeros
            using (var memoryMappedFile = MemoryMappedFile.CreateOrOpen(name, 8))
            using (var viewStream = memoryMappedFile.CreateViewStream(8, 8))
            {
                var pointer = viewStream.SafeMemoryMappedViewHandle.DangerousGetHandle();
				
				try
				{
					var currentLock = Interlocked.Read((long*)pointer);
					if(GetPid(currentLock) == myPid && GetTid(currentLock) == myTid){
						action();
						return true;
					}
				}
				catch(Exception e)
				{
					Console.WriteLine($"Something very bad happened: {e}");
					return false;
				}

                try
                {
                    int holderPid = -1;
                    int holderTid = -1;

                    while (DateTime.UtcNow < end)
                    {
                        // Take lock only if it is not taken
                        var currentLock = InterlockedCompareExchange64((long*)pointer, myIdentifier, 0);

                        if (currentLock == 0)
                        {
                            action();
                            return true;
                        }

                        // Lock is taken, let's see who holds it
                        holderTid = GetTid(currentLock);
                        holderPid = GetPid(currentLock);

                        bool exists = false;
                        try
                        {
                            exists = Process.GetProcessById(holderPid).Threads.OfType<ProcessThread>().Any(t => t.Id == holderTid);
                        }
                        catch
                        {
                        }

                        // If holding thread doesn't exist then the lock is abandoned
                        if (!exists)
                        {
                            // Clear lock only if it is still held by previous owner
                            var currentLock2 = InterlockedCompareExchange64((long*)pointer, 0, currentLock);
                            if (currentLock == currentLock2)
                            {
                               Console.WriteLine($"Mutex {name} was abandoned by pid={holderPid} tid={holderTid}");
                            }
                        }

                        Thread.Sleep(spinTimeout);
                    }

                    Console.WriteLine($"Timeout when waiting on mutex {name} held by pid={holderPid} tid={holderTid}");
                }
                finally
                {
                    // Clear lock only if I'm the one holding it
                    var currentLock = InterlockedCompareExchange64((long*)pointer, 0, myIdentifier);
                    if (currentLock != myIdentifier)
                    {
                        Console.WriteLine($"I tried to release mutex held by someone else, pid={GetPid(currentLock)} tid={GetTid(currentLock)}");
                    }
                }
            }

            return false;
        }

        private static int GetPid(long value)
        {
            return (int)(value >> 32);
        }

        private static int GetTid(long value)
        {
            return (int)(value & 0xFFFFFFFF);
        }
    }
}

We check in line 34 if the current owner of the lock is us — in that case we just execute the action and return early. If something wrong happened (we have exception) then we cannot assume anything about lock owner or executed action so we need to return immediately. The only thing we know for sure is that we didn’t modify the lock. You may be tempted to set a flag that lock is on us and return it in the exception handler — thinking that the exception was thrown by the executed action — but you cannot guarantee that you started executing the action (think about OOM thrown after setting the flag and before calling the handler). You could try enhancing this by using CER but then you constrain yourself a lot.

This is the ninth part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

Last time we implemented custom mutex based on memory mapped files. We can use it to track who owns the lock in much simpler way. Today we will implement a counting semaphore.

Idea is simple: we want to create multiple mutexes, iterate through all of them and choose first available. If none is free, we just choose one and wait on it for a little longer. This is very dirty implementation and can lead to starvation, though.

public static void DoWithSemaphore(string name, int semaphoresCount, Action action)
{
	bool checkedAll = false;
	string fullName;

	for (int index = 0; ; index = (index + 1) % semaphoresCount)
	{
		fullName = name + index;
		if (DoWithMutex(fullName, action, checkedAll ? 20 : 1))
		{
			break;
		}

		if (index == semaphoresCount - 1)
		{
			checkedAll = true;
		}
	}
}

So we accept number of semaphores (each of them being a binary semaphore) and we try to implement naive WaitAny. This is obviously less than optimal and doesn’t work every time, but in reasonable system should perform pretty well. Once again, your mileage may vary and I take no responsibility.

This is the eighth part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

We know how to use global mutexes to synchronize processes. However, there is a big drawback — we don’t know who owns the mutex and we cannot get that information easily. There is https://docs.microsoft.com/en-us/windows/win32/debug/wait-chain-traversal API for reading that information but it is not easy to follow. Can we do better?

One common trick is to use memory mapped files to store the information. Let’s see the code:

using System;
using System.Diagnostics;
using System.IO.MemoryMappedFiles;
using System.Linq;
using System.Runtime.InteropServices;
using System.Threading;

namespace MutexUtils
{
    public static class MutexUtils
    {
        [DllImport("kernel32.dll", SetLastError = true)]
        unsafe public static extern long InterlockedCompareExchange64(long* destination, long exchange, long comperand);

        public static unsafe bool DoWithMutex(string name, Action action, int timeoutInSeconds = int.MaxValue, int spinTimeout = 250)
        {
            // Store <PID><TID> as one field
            long myIdentifier = ((long)Process.GetCurrentProcess().Id << 32) + AppDomain.GetCurrentThreadId();

            // Calculate timeout wall clock
            DateTime end = DateTime.UtcNow.AddSeconds(timeoutInSeconds);

            // Open memory mapped file initialized with zeros
            using (var memoryMappedFile = MemoryMappedFile.CreateOrOpen(name, 8))
            using (var viewStream = memoryMappedFile.CreateViewStream(8, 8))
            {
                var pointer = viewStream.SafeMemoryMappedViewHandle.DangerousGetHandle();

                try
                {
                    int holderPid = -1;
                    int holderTid = -1;

                    while (DateTime.UtcNow < end)
                    {
                        // Take lock only if it is not taken
                        var currentLock = InterlockedCompareExchange64((long*)pointer, myIdentifier, 0);

                        if (currentLock == 0)
                        {
                            action();
                            return true;
                        }

                        // Lock is taken, let's see who holds it
                        holderTid = GetTid(currentLock);
                        holderPid = GetPid(currentLock);

                        bool exists = false;
                        try
                        {
                            exists = Process.GetProcessById(holderPid).Threads.OfType<ProcessThread>().Any(t => t.Id == holderTid);
                        }
                        catch
                        {
                        }

                        // If holding thread doesn't exist then the lock is abandoned
                        if (!exists)
                        {
                            // Clear lock only if it is still held by previous owner
                            var currentLock2 = InterlockedCompareExchange64((long*)pointer, 0, currentLock);
                            if (currentLock == currentLock2)
                            {
                               Console.WriteLine($"Mutex {name} was abandoned by pid={holderPid} tid={holderTid}");
                            }
                        }

                        Thread.Sleep(spinTimeout);
                    }

                    Console.WriteLine($"Timeout when waiting on mutex {name} held by pid={holderPid} tid={holderTid}");
                }
                finally
                {
                    // Clear lock only if I'm the one holding it
                    var currentLock = InterlockedCompareExchange64((long*)pointer, 0, myIdentifier);
                    if (currentLock != myIdentifier)
                    {
                        Console.WriteLine($"I tried to release mutex held by someone else, pid={GetPid(currentLock)} tid={GetTid(currentLock)}");
                    }
                }
            }

            return false;
        }

        private static int GetPid(long value)
        {
            return (int)(value >> 32);
        }

        private static int GetTid(long value)
        {
            return (int)(value & 0xFFFFFFFF);
        }
    }
}

Magic, a lot. Let’s go part by part.

First, we want to store process ID and thread ID somewhere in the lock to be able to read it easily later. In line 18 we encode those in one 64-bit long variable which we can later replace using CAS operation.

In line 21 we just calculate the time when we should stop trying to get lock. This is for timeouts.

Next, we create memory mapped file (lines 24, 25) not backed by any physical file. This is to avoid permission problems — we cannot map the same file in two processes without copy-on-write semantics. We will need separate reader for debugging.

Next, we spin in the loop. Each time we try to take lock (line 37). If current lock value is zero (line 39) then it means that our lock is available and we have just locked it. We execute the action and then return (which is jump to finally).

However, if lock wasn’t available, we now have the owner of the lock (lines 46 and 47). So we need to check if the owner is still alive. We read process and look for thread in line 52.

If it didn’t exist, we try to clear the lock (line 62). We clear it only if it is still held by the same owner. And here is big warning — process ID and thread ID can be recycled so here we may inadvertently release still used mutex!

Then in line 69 we sleep for some timeout and loop again.

Ultimately, in line 77 we try to clear the lock if it is taken by us. We may end up in this line of code if some exception appears so we cannot just blindly release the mutex.

That’s all, you can verify that it should work pretty well. Just be aware of this chance of clearing up some other mutex, you may come up with different identifier if needed.

In theory, this can be solved by using CAS for 128 bits:

public static class MutexUtils
{
	public static void DoWithSemaphore(string name, int semaphoresCount, Action action)
	{
		bool checkedAll = false;
		string fullName;

		for (int index = 0; ; index = (index + 1) % semaphoresCount)
		{
			fullName = name + index;
			if (DoWithMutex(fullName, action, checkedAll ? 20 : 1))
			{
				break;
			}

			if (index == semaphoresCount - 1)
			{
				checkedAll = true;
			}
		}
	}

	[DllImport("kernel32.dll", SetLastError = true)]
	unsafe public static extern bool InterlockedCompareExchange128(long* destination, long exchangeHigh, long exchangeLow, long* comperand);

	public static unsafe bool DoWithMutex(string name, Action action, int timeoutInSeconds = int.MaxValue, int spinTimeout = 250)
	{
		// Store <PID><TID> as one field
		long myIdentifier = ((long)Process.GetCurrentProcess().Id << 32) + AppDomain.GetCurrentThreadId();
		long myTime = DateTime.UtcNow.Ticks;

		// Calculate timeout wall clock
		DateTime end = DateTime.UtcNow.AddSeconds(timeoutInSeconds);

		// Open memory mapped file initialized with zeros
		using (var memoryMappedFile = MemoryMappedFile.CreateOrOpen(name, 8))
		using (var viewStream = memoryMappedFile.CreateViewStream(8, 8))
		{
			var pointer = viewStream.SafeMemoryMappedViewHandle.DangerousGetHandle();
			long* currentLock = stackalloc long[2];
			currentLock[0] = 0;
			currentLock[1] = 0;

			try
			{
				int holderPid = -1;
				int holderTid = -1;

				while (DateTime.UtcNow < end)
				{
					// Take lock only if it is not taken
					var isLockFree = InterlockedCompareExchange128((long*)pointer, myIdentifier, myTime, currentLock);

					if (isLockFree)
					{
						action();
						return true;
					}

					// Lock is taken, let's see who holds it
					holderTid = GetTid(currentLock[0]);
					holderPid = GetPid(currentLock[1]);

					bool exists = false;
					try
					{
						exists = Process.GetProcessById(holderPid).Threads.OfType<ProcessThread>().Any(t => t.Id == holderTid);
					}
					catch
					{
					}

					// If holding thread doesn't exist then the lock is abandoned
					if (!exists)
					{
						// Clear lock only if it is still held by previous owner
						var isLockStillOwnedByTheSameOwner = InterlockedCompareExchange128((long*)pointer, 0, 0, currentLock);
						if (isLockStillOwnedByTheSameOwner)
						{
						   Console.WriteLine($"Mutex {name} was abandoned by pid={holderPid} tid={holderTid}");
						}
					}

					Thread.Sleep(spinTimeout);
				}

				Console.WriteLine($"Timeout when waiting on mutex {name} held by pid={holderPid} tid={holderTid}");
			}
			finally
			{
				// Clear lock only if I'm the one holding it
				currentLock[0] = myIdentifier;
				currentLock[1] = myTime;
				if (!InterlockedCompareExchange128((long*)pointer, 0, 0, currentLock))
				{
					Console.WriteLine($"I tried to release mutex held by someone else, pid={GetPid(currentLock[0])} tid={GetTid(currentLock[1])}");
				}
			}
		}

		return false;
	}

	private static int GetPid(long value)
	{
		return (int)(value >> 32);
	}

	private static int GetTid(long value)
	{
		return (int)(value & 0xFFFFFFFF);
	}
}

However, it doesn’t work on my machine, my kernel32.dll doesn’t support this CAS operation.

And since this is playing with very dangerous primitives, I take no responsibility for any failures in your systems if it doesn’t work. I tested it in my situation and it behaved correctly, though.

This is the sixth part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

Let’s start with the following code:

using System;
using System.Threading;

namespace AbandonedMutex
{
    class Program
    {
        static void Main(string[] args)
        {
            var mutex = new Mutex(false, "mutexName");

            try
            {

                while (true)
                {
                    try
                    {
                        if (mutex.WaitOne(TimeSpan.FromSeconds(3)))
                        {
                            break;
                        }
                        else
                        {
                            Console.WriteLine("Timeout");
                        }
                    }
                    catch
                    {
                    }
                }

                Console.WriteLine("Mutex acquired!");
                Console.ReadLine();
            }
            finally
            {
                try
                {
                    mutex.ReleaseMutex();
                    Console.WriteLine("Mutex released");
                }
                catch
                {
                }
            }

            Console.ReadLine();
            Console.WriteLine("Done");
        }
    }
}

We want to acquire a mutex. Since the operation might fail, we want to log the timeout, handle the exception and try again. Finally, we want to release the mutex, catch all exceptions and then exit.

Start this application three times: first instance should acquire the mutex, second and third should just wait. Now kill forcibly first instance (i.e., using Process Explorer). Now one of two other instances should acquire the mutex. Let’s say, that it was the second instance. Focus it and hit enter. It should say Mutex released and wait on another Console.ReadLine(). We expect the third instance to acquire the mutex, however, it still shows timeouts. Why is that?

Explanation

You could use Chain Traversal API to figure out what is happening. However, everything is as designed. If you consult the documentation, you will see the following exception:

AbandonedMutexException	
The wait completed because a thread exited without releasing a mutex. This exception is not thrown on Windows 98 or Windows Millennium Edition.

What is not stated explicitly is: when you get this exception, the mutex IS acquired. This means that our first catch just swallows the exception of an operation which actually succeeded. We loop again, acquire the mutex again (since it is recursive). Later when we release it, it is still locked because we miss one more release.

Solution? Whenever you get this exception you need to break the loop because the mutex is acquired.

This is the fifth part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

Last time we called WinAPI through P/Invoke, today we are going to call it directly.

Code

#include "stdafx.h"
#include <windows.h>
#include <ctime>
#include <cstdio>

using namespace std;

int main()
{
	HANDLE mutex = CreateMutex(NULL, FALSE, L"mutex_cpp");

	while (true) {
		clock_t begin = clock();
		for (int i = 0;i < 100000;++i) {
			WaitForSingleObject(mutex, INFINITE);
			ReleaseMutex(mutex);
		}
		clock_t end = clock();
		double elapsed = double(end - begin) / CLOCKS_PER_SEC * 1000.0;
		printf("%lf\n", elapsed);
	}

	CloseHandle(mutex);

    return 0;
}

Results

The results are:

As you can see, the results are very similar to the P/Invoke ones.

This is the fourth part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

We have already seen a mutex in C# but last time it happened that Java JNI is faster. Let’s compare it with P/Invoke.

Code

using System;
using System.Diagnostics;
using System.Runtime.InteropServices;

namespace MutexPInvoke
{
    class Program
    {
        [DllImport("kernel32.dll")]
        static extern IntPtr CreateMutex(IntPtr lpMutexAttributes, bool bInitialOwner, string lpName);

        [DllImport("kernel32.dll", SetLastError = true)]
        static extern UInt32 WaitForSingleObject(IntPtr hHandle, UInt32 dwMilliseconds);

        [DllImport("kernel32.dll")]
        public static extern bool ReleaseMutex(IntPtr hMutex);

        static void Main(string[] args)
        {
            IntPtr mutex = CreateMutex(IntPtr.Zero, false, "mutex_pinvoke");

            Stopwatch watch = new Stopwatch();

            while (true)
            {
                watch.Restart();
                for (int i = 0; i < 100000; ++i)
                {
                    WaitForSingleObject(mutex, 0xFFFFFFFF);
                    ReleaseMutex(mutex);
                }
                watch.Stop();
                Console.WriteLine(watch.ElapsedMilliseconds);
            }
        }
    }
}

As always, nothing special. Let’s see the results.

Results

Well, slightly better than in pure C#, however, still worse than JNI. It’s time to go down.

This is the third part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

Last time we saw file lock in Java which we can use on every platform. However, if we stick to Windows only, we can use WinAPI mutexes through JNI. Let’s go.

Code

First, Java application:

public class JavaMutex {
    static {
        System.out.println(System.getProperty("java.library.path"));
        System.loadLibrary("MutexJava");
    }

    private native long createMutex();
    private native void acquireMutex(long mutex);
    private native void releaseMutex(long mutex);

    private void test(){
        long mutex = createMutex();

        while(true){
            long startTime = System.currentTimeMillis();
            for(int i=0;i<100000;++i){
                acquireMutex(mutex);
                releaseMutex(mutex);
            }
            long estimatedTime = System.currentTimeMillis() - startTime;
            System.out.println(estimatedTime);
        }
    }

    public static void main(String[] args){
        new JavaMutex().test();
    }
}

We define three methods to use Mutex. Observe that we use long instead of HANDLE. HANDLE is a void* which we can consider a number in our case.

Next, we generate the JNI header:

javac -h . JavaMutex .java

and here is the result:

/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class JavaMutex */

#ifndef _Included_JavaMutex
#define _Included_JavaMutex
#ifdef __cplusplus
extern "C" {
#endif
/*
 * Class:     JavaMutex
 * Method:    createMutex
 * Signature: ()J
 */
JNIEXPORT jlong JNICALL Java_JavaMutex_createMutex
  (JNIEnv *, jobject);

/*
 * Class:     JavaMutex
 * Method:    acquireMutex
 * Signature: (J)V
 */
JNIEXPORT void JNICALL Java_JavaMutex_acquireMutex
  (JNIEnv *, jobject, jlong);

/*
 * Class:     JavaMutex
 * Method:    releaseMutex
 * Signature: (J)V
 */
JNIEXPORT void JNICALL Java_JavaMutex_releaseMutex
  (JNIEnv *, jobject, jlong);

#ifdef __cplusplus
}
#endif
#endif

Now we implement the methods in C++ with Visual Studio 2017:

#include <windows.h>

JNIEXPORT jlong JNICALL Java_JavaMutex_createMutex
(JNIEnv *, jobject) {
	HANDLE mutex = CreateMutex(NULL, FALSE, L"mutex_java");
	return (jlong)mutex;
}

JNIEXPORT void JNICALL Java_JavaMutex_acquireMutex
(JNIEnv *, jobject, jlong mutex) {
	WaitForSingleObject((HANDLE)mutex, INFINITE);
}

JNIEXPORT void JNICALL Java_JavaMutex_releaseMutex
(JNIEnv *, jobject, jlong mutex) {
	ReleaseMutex((HANDLE)mutex);
}

Compile, run with -Djava.library.path="..." and test.

Results

As we can see, the results are quite nice, even better than .NET. Next time we will see if we can improve C# code.

This is the second part of the Concurrency series. For your convenience you can find other parts in the table of contents in Part 1 – Mutex performance in .NET

Today we explore system-wide lock in Java 1.8.0_161 on Windows 10 x64.

There is no built-in mechanism in Java for acquiring system wide lock. One trick is to lock a file — if only every interested process locks the same file, we effectively have a system-wide lock for our processes.

Code

import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.channels.FileChannel;
import java.nio.channels.FileLock;

public class Filelock {
    public static void main(String[] args) throws IOException {
        File file = new File("filename");
        FileChannel channel = new RandomAccessFile(file, "rw").getChannel();

        while(true){
            long startTime = System.currentTimeMillis();
            for(int i=0;i<100000;++i){
                FileLock lock = channel.lock();
                lock.release();
            }
            long estimatedTime = System.currentTimeMillis() - startTime;
            System.out.println(estimatedTime);
        }
    }
}

As in previous part, nothing magical. Just a lock, measuring time and showing results.

Results

As we can see, even for one process this lock type is much slower than mutex in previous part.

This is the first part of the Concurrency series. For your convenience you can find other parts using the links below:
Part 1 — Mutex performance in .NET
Part 2 — Java file lock
Part 3 — Java mutex via JNI
Part 4 — .NET with P/Invoke
Part 5 — WinAPI mutex
Part 6 — Abandoned mutex
Part 7 — Semaphores trickery
Part 8 — Tracking mutex owner
Part 9 — Semaphores with custom locks
Part 10 — Reentrant mutex

This is the first part of the Concurrency series in which I explore performance of various locking mechanisms. Once working on a pet project I started wondering how fast is a system wide lock in Windows so I decided to run few simple “benchmarks” just to get the general idea.

The benchmarks are deliberately done this way so I can compare different languages in the same manner. Do not take results for granted, do not consider them reliable.

First I explore WinAPI Mutex called from C#.

Code

Here is the code:

using System;
using System.Diagnostics;
using System.Threading;

namespace MutexDotnet
{
    class Program
    {
        static void Main(string[] args)
        {
            var mutex = new Mutex(false, "mutexName");
            Stopwatch watch = new Stopwatch();

            while (true)
            {
                watch.Restart();
                for(int i = 0; i < 100000; ++i)
                {
                    mutex.WaitOne();
                    mutex.ReleaseMutex();
                }
                watch.Stop();
                Console.WriteLine(watch.ElapsedMilliseconds);
            }
        }
    }
}

Nothing special, just a named mutex and stopwatch. I try to measure the time to acquire mutex 100 thousand times.

Results

Here are the results:

As we can see, to acquire mutex given number of times with 10 processes trying to do that concurrently we need over 4 seconds which gives 0.04 ms for single acquire + release.

In next parts we will see different mechanisms, their performance and quirks.