Multiple-readers, single-writer synchronization lock between processes

[ahmd]

There's a well-known algorithm that employs readers/writer lock synchronization between threads of a single process on a Windows platform using pure WinAPIs/C++:
http://www.glennslayden.com/code/win...er-writer-lock

In my case I need to do this between several processes, i.e. the writer is in one process, and readers are in other processes. Any idea how to do that?

PS. I need this for an already developed project, so I can't use anything other than C++/MFC or pure WinAPIs. In other words I can't use Boost or the like extensions.

[Igor Vartanov]

Named mutex of a name in global namespace (single reader/writer access). Or a dedicated read/write broker.

[Igor Vartanov]

Oh, actually named semaphore could be used for counting readers. And named event to indicate writing in progress.

[ahmd]

Oh, actually named semaphore could be used for counting readers. And named event to indicate writing in progress.

Thanks, Igor. Replacing the critical section with global named mutex should work. The issue is in the counter of readers. I actually thought to use named semaphores for it too, but couldn't come up with a working code. The issue is that semaphores count down and this algorithm needs to count up & down.

So can I ask you to demonstrate what you meant in code?

[Igor Vartanov]

The idea actually was for reader to inverse the logic behind semaphore object and use ReleaseSemaphore(by 1) to indicate read operation start and WaitForSingleObject to indicate read completion. The semaphore should be created with maximum allowed count but initial count is zero. Of course, reader should catch the mutex and immediately release it after incrementing semaphore. Symmetrically, writer should not grab the mutex until semaphore becomes non-signalled.

One potential danger thing to be confirmed that died reader never blocks the whole mechanism.

[ahmd]

The idea actually was for reader to inverse the logic behind semaphore object and use ReleaseSemaphore(by 1) to indicate read operation start and WaitForSingleObject to indicate read completion. The semaphore should be created with maximum allowed count but initial count is zero. Of course, reader should catch the mutex and immediately release it after incrementing semaphore. Symmetrically, writer should not grab the mutex until semaphore becomes non-signalled.

One potential danger thing to be confirmed that died reader never blocks the whole mechanism.

But how would you know that there're no readers reading the data?

[Igor Vartanov]

No readers is indicated by semaphore non-signalling state.

[ahmd]

Let's put it into code:

//For simplicity I'm writing it for a single process
class MultiReaderSingleWriter
{
private:
	CRITICAL_SECTION m_csWrite;
	CRITICAL_SECTION m_csReaderCount;
	//long m_cReaders;
	HANDLE m_semCounter;
	HANDLE m_hevReadersCleared;

public:
	MultiReaderSingleWriter()
	{
		m_semCounter = CreateSemaphore(NULL, 0, 1000, NULL);
		InitializeCriticalSection(&m_csWrite);
		InitializeCriticalSection(&m_csReaderCount);
		m_hevReadersCleared = CreateEvent(NULL,TRUE,TRUE,NULL);
	}

	~MultiReaderSingleWriter()
	{
		WaitForSingleObject(m_hevReadersCleared,INFINITE);
		CloseHandle(m_semCounter);
		CloseHandle(m_hevReadersCleared);
		DeleteCriticalSection(&m_csWrite);
		DeleteCriticalSection(&m_csReaderCount);
	}


	void EnterReader(void)
	{
		EnterCriticalSection(&m_csWrite);
		EnterCriticalSection(&m_csReaderCount);
		//if (++m_cReaders == 1)
		//	ResetEvent(m_hevReadersCleared);

		ReleaseSemaphore(m_semCounter);   //Can we call it here with the count being 0?
		//So how do you check the semaphore count here?
		
		LeaveCriticalSection(&m_csReaderCount);
		LeaveCriticalSection(&m_csWrite);
	}

	void LeaveReader(void)
	{
		EnterCriticalSection(&m_csReaderCount);
		//if (--m_cReaders == 0)
		//	SetEvent(m_hevReadersCleared);

		WaitForSingleObject(m_semCounter, 0);
		//Same problem here??

		LeaveCriticalSection(&m_csReaderCount);
	}

	void EnterWriter(void)
	{
		EnterCriticalSection(&m_csWrite);
		WaitForSingleObject(m_hevReadersCleared,INFINITE);
	}

	void LeaveWriter(void)
	{
		LeaveCriticalSection(&m_csWrite);
	}
};

It doesn't seem to work. I don't know that semaphores can be used as counters? I might be wrong. If so, correct me.

[Igor Vartanov]

The code below is just an idea that needs to be proved, or disproved, or corrected. And no, I never did anything like this before.

#include <windows.h>
#include <crtdbg.h>

class MultiReaderSingleWriter
{
	HANDLE m_hSemRead;  // counts active readers
	HANDLE m_hEvtNoRead;  // prevents read operation

public:
	MultiReaderSingleWriter()
	{
		m_hSemRead = CreateSemaphore(NULL, 0, 1000, NULL);
		m_hEvtNoRead = CreateEvent(NULL, TRUE, FALSE, NULL);
	}

	~MultiReaderSingleWriter()
	{
		CloseHandle(m_hSemRead);
		CloseHandle(m_hEvtNoRead);
	}

	BOOL EnterRead()
	{
		DWORD waitRes = WaitForSingleObject(m_hEvtNoRead, INFINITE); // blocks until write completion
		_ASSERT(WAIT_OBJECT_0 == waitRes);	
		LONG count = 0;
		BOOL res = ReleaseSemaphore(m_hSemRead, 1, &count); // increments semaphore counter
		// here you can log count to see internal semaphore counter before you incremented it
		_ASSERT(res);
		return res;
	}

	BOOL LeaveRead()
	{
		DWORD waitRes = WaitForSingleObject(m_hSemRead, 0); // decrement semaphore counter
		BOOL res = WAIT_TIMEOUT == waitRes;  // here not sure about the exact retcode :)
		_ASSERT(res);
		return res;
	}

	BOOL EnterWrite()
	{
		BOOL res = SetEvent(m_hEvtNoRead); // prevents new reads
		_ASSERT(res);
		DWORD waitRes = 0;
		do
		{
			// loop until last reader gone
			waitRes = WaitForSingleObject(m_hSemRead, 0);
			if (WAIT_OBJECT_0 == waitRes)
				Sleep(10);
			else if (WAIT_TIMEOUT == waitRes)
				return TRUE;
			else
				return FALSE;
		} while (TRUE);

		return FALSE;
	}

	BOOL LeaveWrite()
	{
		BOOL res = ResetEvent(m_hEvtNoRead); // release waiting readers
		_ASSERT(res);
		return res;
	}
};

[ahmd]

Thanks, Igor.

DWORD waitRes = WaitForSingleObject(m_hSemRead, 0); // decrement semaphore counter
BOOL res = WAIT_TIMEOUT == waitRes;  // here not sure about the exact retcode :)

Yes, I'm not sure about this one either. That's what I meant in my previous post that a semaphore object was never intended as just a counter. Although I do appreciate your "bold" approach to it.

One potential danger thing to be confirmed that died reader never blocks the whole mechanism.

Yes, that becomes an issue in case I put your code into several processes. For instance, if one reader crashes and doesn't decrement the semaphore, it will indefinitely deadlock the writer.

Also this, I guess is just nitpicking:

// loop until last reader gone
waitRes = WaitForSingleObject(m_hSemRead, 0);
if (WAIT_OBJECT_0 == waitRes)
	Sleep(10);
else if (WAIT_TIMEOUT == waitRes)
	return TRUE;
else
	return FALSE;

Wouldn't it be better to do:

waitRes = WaitForSingleObject(m_hSemRead, 10);

and drop Sleep(10); to save those 10ms?

[Igor Vartanov]

unconventional approach to using semaphores

Well, the idea was got from MSDN article after reading about start with zero counter. So it's not that unconventional.

let me correct a bug. When you create m_hEvtNoRead event, it must be set to signaled state. Otherwise the first reader will deadlock without the first writer call.

It might be a feature, as long as without first write it might be senseless to read the void. You know this better, as I'm totally unaware of your ultimate design.

The sleep(10) part of the EnterWrite() method seems to be a bottleneck

I said you before that all my experience with synchronization was mostly about dealing with processes where hundreds of milliseconds never matter. Typically for me in business logic keeping precedence matters much more than super timings.

And in case when few milliseconds really is a bottleneck, I'd say that either you need some other synchronization solution, or, which is more probable, your synchronized multi-process reader-writer approach itself is a bottleneck.

but unfortunately I get occasional "read fail". Why do you think would that be?

Like any other pure architectural thing it needs to be analyzed for flaws (code review, sequence diagrams, etc.) and properly debugged (by offline logs or interactively). Seems like I just was able to invest an idea, but have no time to purify it, sorry. Maybe other guys here will help.

[ahmd]

Yes. Thank you. I appreciate it.

[Igor Vartanov]

I had a thought about the problem of dead reader this morning. Seems like writer should initiate full resync once it was not able to write within some guaranteed interval. Resync results in closing semaphore object and opening a new one with a new name.

This has a few implications. Only writer creates (and possesses) synchronization objects, readers just open those, and close immediately after using. Current valid object names must be published by writer somehow (registry?). Any error case while operating with sync object indicates that reader should reopen the object with the newly published name and repeat the action.

I would say that dedicated data read-write server (multithreaded socket or out-of-proc COM) seems like much more simple and reliable solution. Besides, it will be able to use the original sync class you mentioned in your OP.

Or even more radical approach conversion. In your current scheme readers "pull" data. Changing it to "pushing" data (for example, writer posting data over broadcast mailslot and reader listening on the mailslot and caching the last result) may simplify the whole system.

[ahmd]

Thanks for sticking with it.

I actually did solve it by abandoning semaphores as counters. I really liked your idea and it worked really great as long as all readers didn't crash within that specific critical section.

What I went with is a shared memory array for the readers count accessible for all readers and a writer. Each consisting of the following elements:

struct PROC_INFO{
	DWORD dwProcID;			//Process ID of reader
	DWORD dwThreadID;			//Thread ID that entered the reader-reading critical section
	FILETIME ftCreatedTime;			//Time when the process was created to resolve process ID ambiguity in case of a crashed process
};

Then while entering the reader critical section I'd add the calling thread and proc ID into this array and remove it when leaving the critical section. I had to write my own waiting function for the writer though. It'd loop with the Sleep(1) interval and try to open each process by its process ID and if it fails it then removes that element from the shared array. If the count of readers reaches 0 then the writer could begin writing. (Obviously all of these functions with the shared mem must be enclosed it its own mutex controlled critical section.) This approach seems to have eliminated any possible crashes. (Although it requires some additional attention to abandoned mutexes.)

[MikeAThon]

... I had to write my own waiting function for the writer though. It'd loop with the Sleep(1) interval and try to open each process by its process ID and if it fails it then removes that element from the shared array.

You can't write code for inter-process synchronization at the user level. All such code must be at the kernel level which, of course, you have no access to. As such, you must rely on the Windows-provided APIs for synchronization, and work within their premises.

And a call to Sleep will get you laughed out of any serious discussion on synchronization. Get rid of it.

Mike