Mutual exclusion strategy
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Thread: Mutual exclusion strategy

  1. #1
    Join Date
    Jan 2010
    Posts
    20

    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

  2. #2
    Arjay's Avatar
    Arjay is offline Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,418

    Re: Mutual exclusion strategy

    Quote Originally Posted by stolencoin View Post
    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).

  3. #3
    Join Date
    Jan 2010
    Posts
    20

    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.

  4. #4
    Join Date
    Nov 2003
    Posts
    1,819

    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

  5. #5
    Join Date
    Jan 2010
    Posts
    20

    Re: Mutual exclusion strategy

    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.

  6. #6
    Join Date
    Nov 2003
    Posts
    1,819

    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

  7. #7
    Arjay's Avatar
    Arjay is offline Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,418

    Re: Mutual exclusion strategy

    You've made a few statements that I want to comment on.

    Quote Originally Posted by stolencoin View Post
    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 View Post
    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).

  8. #8
    Join Date
    Jan 2010
    Posts
    20

    Re: Mutual exclusion strategy

    *sigh* I wish people showed this much interest to my intellisense thread

    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.

  9. #9
    Arjay's Avatar
    Arjay is offline Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,418

    Re: Mutual exclusion strategy

    Quote Originally Posted by stolencoin View Post
    *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 View Post
    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 View Post
    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 View Post
    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 View Post
    And it looks like noone wants to touch fibers.
    No one wants to touch fibers because we don't think they'll help.

  10. #10
    Join Date
    Nov 2003
    Posts
    1,819

    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

  11. #11
    Join Date
    Jan 2010
    Posts
    12

    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?

  12. #12
    Join Date
    Nov 2003
    Posts
    1,819

    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

  13. #13
    Join Date
    Jan 2010
    Posts
    20

    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.

  14. #14
    Join Date
    Nov 2003
    Posts
    1,819

    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

  15. #15
    Join Date
    Jan 2010
    Posts
    20

    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.

Page 1 of 2 12 LastLast

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center