Mutual exclusion strategy
Hi all
For practical purposes I can say that my program has a producer thread and a consumer thread. The producer thread writes data to a circular buffer, and the consumer thread reads data from the same buffer. The circular buffer is protected by a critical section.
I don't have control over the producer thread. In fact that's a function exported by my DLL, and all I can do is to ask the user of this library to be quick in the function, and not to block. Despite the fact that my users comply with these requests, I have all the same observed that there are times the producer thread gets the mutex repeatadly, in succession, to the point of filling the buffer. As a fix, I've written a wrapper function for EnterCriticalSection (producer thread only) and after this thread enters the CS, say N times, it Sleep(50); before trying to enter the critical section.
This works, but is there a nicer or better solution? Does using fibers worth the effort of restructuring my code? Is there a magical data storage concept without any need of synchronization?
Regards
Re: Mutual exclusion strategy
Quote:
Originally Posted by
stolencoin
This works, but is there a nicer or better solution?
One possibility is to have the producers write to a temporary buffer. Then when the library method returns you copy the data into the circular buffer and act on it. That way a user doesn't necessarily be quick (of course you don't need to tell the library users that).
Re: Mutual exclusion strategy
Thanks Arjay, your idea might have worked but rereading my own post I've seen that I might have mislead you, or any other members who have read my post. My apologies.
The function I export is not a callback function. It is a function that writes data to a buffer. Users of this library call this function like WRITE(buffer, size_of_buffer); and they do nothing else. They cetainly don't spend time within the function body itself and they cannot block the execution of the function.
But the original question still stands. How to prevent the same thread entering the critical section repeatedly, other than my fix with the sleep function.
Re: Mutual exclusion strategy
>> ... there are times the producer thread gets the mutex repeatedly, in succession, to the point of filling the buffer.
So why isn't the consumer thread consuming?
How does the code currently handle WRITE requests when the buffer is full? Does it block or return an error?
gg
Re: Mutual exclusion strategy
Quote:
How does the code currently handle WRITE requests when the buffer is full? Does it block or return an error?
Thanks Codeplug, I guess you want to tell me that I should look closer or deeper inside my code to get to the bottom of this, and you are probably right. Maybe I'm not polling frequent enough to see if there is data in the buffer, or maybe I should increase the buffer size. But I'm not trying to make you solve my specific coding problems. I wanted to hear the ideas of programmers on 1)can you think of another solution than my sleep use, or 2)is using fibers worth it.
Re: Mutual exclusion strategy
Instead of polling, notify the consumer thread that there's something to consume.
Example Win32 code: http://www.codeguru.com/forum/showpo...5&postcount=15
gg
Re: Mutual exclusion strategy
You've made a few statements that I want to comment on.
Quote:
Originally Posted by
stolencoin
How to prevent the same thread entering the critical section repeatedly, other than my fix with the sleep function.
I don't understand why you are worried about the same thread being able to reenter a critical section as a critical section is designed to allow the same thread to enter it multiple times without blocking. Do you need a different type of synchronization object?
Quote:
Originally Posted by
stolencoin
Maybe I'm not polling frequent enough to see if there is data in the buffer, or maybe I should increase the buffer size.
Why are you polling the buffer for changes? In your write function, can you set a "data arrived" event that the consumer thread can wake up on when data is in the buffer?
Lastly, is there any reason to use a circular buffer? Another approach is to use a thread safe queue where a consumer thread pops the items off the thread and multiple threads are allowed to push items onto the thread. If a queue is used you don't need to worry about tracking the start/end position with a circular buffer. I don't know if this approach will work for you (but I'm just throwing it out there).
Re: Mutual exclusion strategy
*sigh* I wish people showed this much interest to my intellisense thread ;)
Quote:
I don't understand why you are worried about the same thread being able to reenter a critical section ...
I'm not trying to prevent the same thread entering the critical section recursively. I know it was designed that way. I'm trying to prevent it (especially the producer) to enter the CS ten times in a row.
And I'm not happy about polling either. But I'm using select() in the consumer thread and to set the writefds I need to see if there is something in the buffer, and to do that I need to return from select once in a while (hence maybe not polling frequent enough).
Producer allocating memory and enqueuing, consumer dequeueing and freeing memory will work I guess. With the additional penalty of allocating-deallocating memory.
Thanks for all your ideas. And it looks like noone wants to touch fibers.
Re: Mutual exclusion strategy
Quote:
Originally Posted by
stolencoin
*sigh* I wish people showed this much interest to my intellisense thread ;)
This thread is more interesting than trying to figure out why intellisense doesn't work in a 7 year old environment. ;)
Quote:
Originally Posted by
stolencoin
I'm not trying to prevent the same thread entering the critical section recursively. I know it was designed that way. I'm trying to prevent it (especially the producer) to enter the CS ten times in a row.
My point is that if you need different behavior from what a critical section can do, then you need to use a different synchronization object. A cs can't limit a thread to a specific number of locks in a row.
Quote:
Originally Posted by
stolencoin
And I'm not happy about polling either. But I'm using select() in the consumer thread and to set the writefds I need to see if there is something in the buffer, and to do that I need to return from select once in a while (hence maybe not polling frequent enough).
Polling just seems like a waste of resources when the consuming thread could wait for an event.
Quote:
Originally Posted by
stolencoin
Producer allocating memory and enqueuing, consumer dequeueing and freeing memory will work I guess. With the additional penalty of allocating-deallocating memory.
Yes, but unless you have some very high speed requirements, using a queue probably won't be a performance bottleneck. You'll have to decide on that, but a queue sure would simplify the code.
Quote:
Originally Posted by
stolencoin
And it looks like noone wants to touch fibers.
No one wants to touch fibers because we don't think they'll help. :)
Re: Mutual exclusion strategy
>> But I'm using select() in the consumer thread...
So you could use another file descriptor to represent "there's something to consume". eventfd() in Linux is for this kind of task.
gg
Re: Mutual exclusion strategy
It sounds like you have almost exactly the same situation as I have (although my code doesn't fill my buffer that quickly)
(producer) thread 1) fill buffer until it catches up with the buffer read pointer, then slows down (should never overwrite unconsumed data)
(consumer) thread 2) read buffer until it catches up with the buffer write pointer, then slows down (should never try and read redundant data)
And it does it all without CS or mutex
My producer reads the serial port, so it's almost always waiting on data from the port, the consumer is polling (50ms waits) and when the pointer's moved, it can move on - so my solution is probably not going to work for you. Is this for a *nix env or a win32 env?
If it's *nix, maybe you could drop the priority of your producer thread to slightly lower than your consumer, that way you're consumer has a chance of getting in there. Or you could slow down the producer thread. Any chance you can show us some of your code (if it's sensitive, maybe generalise it to highlight the issue?) - it might make things easier to understand?
Re: Mutual exclusion strategy
>> And it does it all without CS or mutex
You have multiple threads accessing the same memory location without synchronization? That's would just be wrong.
>> ... maybe you could drop the priority of your producer thread ...
Changing priority, adding/removing sleeps, polling faster/slower - all of these are non-solutions in my mind. To be robust, the code simply has to deal with producers not being able to produce - either by blocking or returning an error.
So far, this sounds like a simple case of the consumer sitting in a select() call when it should be consuming. Ideally the consumer would consume as fast as it can, but without polling. Even then, production can out-run consumption.
gg
Re: Mutual exclusion strategy
Thanks for all the input. I've already stated that I was in favor of using events instead of polling, no argument there. But please consider the following code:
Code:
CONSUMER_FN()
{
Loop
select(...)
EnterCS
process_data
LeaveCS
}
PRODUCER_FN(buffer, size)
{
EnterCS
insert_data(size bytes of buffer)
SetEvent
LeaveCS
// or maybe SetEvent here
}
What I'm trying to say is, no matter how select (or a wait function) returns, either after a timeout or by a signal/event set, there is no guarantee that the consumer_fn will enter the CS. Producer_fn is an exported function and the user may call it in a loop, maybe 100 times in a row. Now there are two things here.
1) Consumer_fn returning a value such as bytes written to the queue and the caller of Producer_fn not producing if the return value is zero (i.e. buffer full)... but how? Maybe the caller of Producer_fn should sleep 20ms before retrying? This is only transferring sleep function from one part (my library function) to another (user's software), and we did not get rid off sleep. Or maybe my part should set an event exported by the caller of Producer_fn? This sounds not so easy to manage.
2) What if there is non-stop incoming data and the task of the caller of Producer_fn is to grep the data from whereever it comes and transfer it to my software? In this case the producer has no chance not to produce, and if it cannot write to the buffer, it should store the data itself. To make things worse, what if I'm developing for an embedded device and/or I have memory constraints, and the temporary storage capabilities are minimal?
This is why I'm considering creating a balance between the producer and the consumer.
Re: Mutual exclusion strategy
>> ...there is no guarantee that the consumer_fn will enter the CS.
Both Posix and Windows are capable of predictable scheduling. What is CS? What are you running on? Why do you believe there is no guarantee?
1) Are you asking "how to do you block if the buffer is full"? The awnser is "by using synchronization primitives provided by your threading library". If the producer polls, then there is no guarantee that the producer will make progress. Only the synchronization primitives of you threading library will provide any guarantees.
2) I'm not following you here. You have a library which exposes a PRODUCER_FN. Who cares what the user does outside of calling your library. Either block until it can produce, return an error saying it can't produce, or something in-between via a supplied timeout.
gg
Re: Mutual exclusion strategy
1) I'm not asking how to block if the buffer is full. I'm saying that I can think of two ways to communicate with the producer thread. a) If Producer_fn returns buffer-full, then the producer thread will have to sleep for a while, and call Producer_fn once again to see if it can write or, b) producer thread must export an event handle and wait on that event handle for the consumer thread to set it when the buffer is available. This latter see-saw concept playing with event handles may not be easy to implement.
2) Who cares what the user does outside of calling your library. I do, and probably the user does as well. The idea behind providing such a mechanism (transfer the data to another thread) is not to block the first thread for lengthy operations/calculations/processings. I'm not sure if this is a good example for my case but if you code a network sniffer, not producing data may not be an option.
I wanted to hear different opinions on my concerns. I'm sure people's opinions will differ.
Re: Mutual exclusion strategy
1a) Sleep polling on the producer side is not a good idea. Use event polling if anything - but even that won't guarantee that the thread will make progress if there are multiple producers.
1b) The event doesn't have to be exposed to the user. PRODUCER_FN could deal with it internally. The easy solution is to event-wait within PRODUCER_FN. The API is already a blocking API (due to "EnterCS"), so you're not changing much.
Choosing between the two is a design decision only you can make. You could even combine the two by having both a blocking "produce()" and non-blocking "try_produce(timeout)" (if true non-blocking is required).
2) The only thing you should care about is defining the requirements and semantics of your library interface - and meeting those requirements of course. Then the users of your library can make proper design decisions based on a well-defined API.
For producer/consumer queue's in general:
- Never sleep() poll
- Never sleep() (never necessary in a properly designed multi-threaded app)
- Only event-poll if you absolutely have to
- Always prefer event-waiting over event-polling
- The API must deal with overflow, because it can and will happen.
gg
