Multiple-readers, single-writer synchronization lock between processes

[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.)

[Igor Vartanov]

Not sure I understand how this helps when reader dies without cleaning its own record.

[ahmd]

Here's a quick pseudo code for the part of the writer's critical section:

//Making sure that there're no readers reading
WaitForSingleObject(hSharedMemMutex, INFINITE);

for(;WaitForSingleObject(hStopEvent, 1) == WAIT_TIMEOUT;)
{
	BOOL bGotLiveReader = FALSE;
	PROC_INFO* pPIs = mapped_offset_of_shared_mem_array;
	for(int i = 0; i < size_of_shared_mem_array / sizeof(PROC_INFO); i++)
	{
		if(!pPIs[i].dwProcID)
			continue;

		HANDLE hProc = OpenProcess(PROCESS_QUERY_INFORMATION, FALSE, pPIs[i].dwProcID);
		FILETIME ftCreated;
		if(GetProcessTimes(hProc, &ftCreated, ...) &&
		    ftCreated == pPIs[i].ftCreatedTime)
		{
			bGotLiveReader = TRUE;
			break;
		}
		else
		{
			pPIs[i].dwProcID = NULL;
		}

		CloseHandle(hProc);
	    }
	}

	if(bGotLiveReader)
		break;
}

ReleaseMutex(hSharedMemMutex);

[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

[ahmd]

Mike, I don't want to branch off this discussion into why calling Sleep would be bad ... it's simply a way to relinquish control back to the OS instead of maxing out CPU cycles for unnecessary looping. I can only wish that more developers out there used this approach. Plus, if you look into the code I posted above, the Sleep(1) call is replaced with WaitForSingleObject(hStopEvent, 1), that I agree is a better alternative.

As the kernel synchronization goes, did you see the use of the hSharedMemMutex mutex around the function I posted?

[Codeplug]

>> it's simply a way to relinquish control back to the OS instead of maxing out CPU cycles for unnecessary looping. I can only wish that more developers out there used this approach.
No. Developers should know that calling Sleep is almost always wrong - seeing it in code is an immediate red flag. In this case, using WaitForSingleObject instead is the right the thing to do. Prefer waiting on something instead of nothing.

Also, you should know that if there are any other open handles to a process, then OpenProcess() will succeed even if it exited an hour ago. In other words, using OpenProcess() on a process that has exited will continue to succeed until all handles to that process have been closed.

What is the resource that is actually being written and read? Shared memory? A file or files?

gg

[ahmd]

No. Developers should know that calling Sleep is almost always wrong - seeing it in code is an immediate red flag.

I disagree with you. Here's an example. Let's take my code sample above and the three ways to write an outer loop:

1.

for(;WaitForSingleObject(hStopEvent, 1) == WAIT_TIMEOUT;)    //Preferred

2.

for(;WaitForSingleObject(hStopEvent, 0) == WAIT_TIMEOUT; Sleep(1))    //Almost the same as 1

3.

for(;WaitForSingleObject(hStopEvent, 0) == WAIT_TIMEOUT;)     //BAD!

All three will produce the same outcome. OK, if you go into technicalities, sample 2 will be putting that thread in a non-responsive state for 1 millisecond before checking for a stop event. Will that make a huge difference for an outcome? Yes, if we're dealing with high precision synchronization at stopping that thread. In other cases it is almost identical to sample 1. Sample 3 on the other hand, by not having any artificial delay introduced into it will produce the same outcome but will eat up way more CPU cycles while running, which in turn will translate into wasted energy, i.e. battery life of a device running this software. Many developers don't realize that by "returning CPU back" to the OS they actually let the OS perform all of its necessary power management tasks. (Of course, this greatly depends on the OS too. For instance, something as counter-intuitive as XP or Vista will probably just waste that 1ms, while Windows 7 might "use it wisely", while I'm positive that Windows 8 will "do it right".) This misunderstanding, by the way, is one of the major reasons why most of the legacy Windows software becomes such an energy hog. The point here is that we don't always have a luxury of a delay built into an API (like WaitForSingleObject), so in that case using a short delay like Sleep(1) in a waiting loop is perfectly OK.

So having said that, there's one place where I would not recommend using Sleep, and that is the main GUI thread. In that case relying on a built-in messaging system will be the way to go.

And the last thing I want to say here is that Sleep API seems to have the same kind of infamy as the goto C statement. It's just funny, because both don't compile into anything that you wouldn't get with other waiting APIs or language statements.

Also, you should know that if there are any other open handles to a process,

Yes. I'm aware of it. I need to test this scenario and see if an open handle for a "crashed" process will make a difference here.

What is the resource that is actually being written and read? Shared memory? A file or files?

In my actual example I need it to synchronize read/write access to system registry, but in the example posted above, it is used to access a file.

[MikeAThon]

You replaced Sleep(1) with WFSO(..., 1). In the circumstances you show here, WFSO with a timeout is no better than Sleep. Both are bad. In fact, anything with (1) or (10) or (pick_any_number_of_msecs) are all equally bad, and you need to learn why if you want to write efficient concurrent code.

There are some situations where Sleep(0) might be acceptable, but there's no point in discussing them at this level.

But it's also true that I could have been less blunt and more helpful.

To answer your original question, to share data between readers and writers (sometimes called producers and consumers), one common approach is a circular buffer, or queue. The approach is favored because there is no need to synchronize access to the buffer itself; it's sufficient to synchronize access only to the put and get pointers to the buffer.

I recognize that your question premised only a single writer, not multiple writers. A single writer might simplify things, but it also might be a red-herring in your quest for a good solution. I say that because if there is only a single writer, then even with a circular buffer designed for multiple writers, there will never be contention for the put pointer.

If you decide on a circular buffer, your design is still not finished. You need to decide on a few more details, such as:
From the perspective of the readers: what happens if there is no data in the buffer? Should the read fail immediately (return false) so as to allow the reading thread to do other work? Or is there no other work for the reading thread, such that the thread should wait in a suspended state and thereafter triggered automatically when more data becomes available in the buffer.

From the perspective of the writer: What happens when the buffer is full? Similar to above should we fail immediately or wait for more room to become available. Or, as another alternative, should we simply over-write data already in the buffer.

From the perspective of both reader and writer: if the answers above involve a wait, then what is the shutdown method? Typically, WFMO with a second mutex is involved.

Mike

[Codeplug]

>> Prefer waiting on something instead of nothing.
Sleep is waiting on nothing. Waiting on nothing in multi-threaded code is a "red flag" - which in my mind means "we should take a closer look at this code because the author may of only thought they knew what they were doing".

>> on the other hand, by not having any artificial delay introduced into it will produce the same outcome but will eat up way more CPU cycles while running, which in turn will translate into wasted energy, i.e. battery life of a device running this software.
Not exactly the case here, since it's a 1ms busy loop. What is wasteful is the act of polling itself - as apposed to waiting efficiently on a synchronization object - which in turn keeps your thread in a wait state in the kernel until there is work to be done - which in turn allows the CPU to enter a lower power state. Threads that enter a runnable state may also take the CPU out to a higher power state.

None of that really matters in this particular case since if a writer is waiting efficiently, that just means readers are getting their read-on. And if readers are waiting efficiently, then a writer is getting her write-on.

Do you really need this complexity just for abandoned readers? Why are readers crashing if all they are doing is reading the registry?
What about abandoned writers?

You can build a readers-writer lock with just semaphores, and no polling.
http://en.wikipedia.org/wiki/Readers-writers_problem
The "writers-preference" solution there is fairly straight forward. If you must add abandoned readers logic, I would only have it kick in once a writer finds itself waiting longer than it has to. Reading from the registry should not be time consuming, and since it's a writers-preference algorithm, no writer should have to wait very long.

gg

[ahmd]

In the circumstances you show here, WFSO with a timeout is no better than Sleep. Both are bad. In fact, anything with (1) or (10) or (pick_any_number_of_msecs) are all equally bad, and you need to learn why if you want to write efficient concurrent code.

Yes, I agree. The reason I need a delay is because of the fact that I need to poll for a condition instead of using a kernel waiting function. And unfortunately there's no built-in kernel waiting function to do what I need in this case.

And speaking of concurrency. I also agree that applying my approach of delaying the polling process for 1 ms is not acceptable for a high-precision concurrency. But, as I explained above, this writer/readers lock is intended for the system registry synchronization. And as we all know, there's nothing slower in the Windows OS than requests to the system registry. So if you plot on the graph the timing for my critical section next to the timing needed to actually write/retrieve data from the system registry, it will be quite minuscule. Thus I chose this approach.

So, yes, the asterisk here is this. If you need it for anything that demands high-precision (say, for a "real-time" I/O), this approach will not work and you'll need to look for something else. Possibly a suggested circular buffer approach...

To answer your original question, to share data between readers and writers (sometimes called producers and consumers), one common approach is a circular buffer, or queue.

I considered this approach but decided against it due to one major drawback -- buffer overrun. You also pointed it out yourself. I'll explain the reason why below.

Do you really need this complexity just for abandoned readers?

Yes. I also agree that the chance of a reader crashing within a critical section is very slim, but, neglecting this will constitute for me a "sloppy code." So I chose to go a more difficult route.

You can build a readers-writer lock with just semaphores, and no polling.
http://en.wikipedia.org/wiki/Readers-writers_problem

Yes, absolutely. Igor Vartanov demonstrated above how this could be done. But again, as I already explained, I cannot use a "simpler" code from the Wikipedia page due to the fact that the readers counter should be shared among several processes. And the use of named semaphores, suggested by Igor, has a drawback of locking up a writer in case of a crash within a reader's critical section. Thus, my longer code of manually counting all reader processes + threads from within a writer's critical section.

If you must add abandoned readers logic, I would only have it kick in once a writer finds itself waiting longer than it has to.

OK, now we're going back to the same issue as was brought up by MikeAThon with circular buffers and a possible buffer overrun. An obvious question here is, "How big should the buffer be?", or "How long should a writer wait before considering a reader abandoned?" Seems like both have straightforward answers, but they don't. I can't know for sure the answers to either of these questions. A reader might be legitimately locked for a very long time. For instance, a debugging process might lock it up for minutes. Or, an antivirus/firewall process may lock it up virtually indefinitely if it decides to do its own checks. Or, more down-to-earth situation -- when my Windows 7 comes out from a sleep mode something in the file system (on a kernel level) locks it up for a couple of seconds. That delay might be "enormously long" for an average critical section but is perfectly legitimate in this case. Any of these situations will cause either a buffer overrun, or a timer overrun, that will break your proposed writer/readers approaches.

Again, guys, I did my research and I was not able to come up with anything better than the approach I demonstrated above, that doesn't seem to "cut corners." So if you have any solution that is superior to that, I'll be more than willing to learn it?

[juanpast]

Are you tryed to use TryEnterCriticalSection unless EnterCriticalSection?

I not read all post of the thread, I not have so time... sorry if this way are explored before...

Best regards.

[ahmd]

Are you tryed to use TryEnterCriticalSection unless EnterCriticalSection?
I not read all post of the thread, I not have so time...

juanpast, thank you for trying to help. But I suggest that you do read threads before posting. EnterCriticalSection is not the subject of this discussion.