[gameprogrammer] Re: Single producer consumer

On Thu, 2006-02-09 at 20:52 -0800, Kevin Jenkins wrote:
> Bob, I don't follow your logic.  Pointers are > 1 byte, therefore 
> suppose 2 out of 4 bytes of the pointer were updated and a context 
> switch occured.  Then the pointer comparison would say the pointers are 
> different, when in fact the update was in the middle of making them equal.

Ok, let me work through it and see if I can back up what I said.

For simplicity lets assume a simple ring buffer (FIFO) with 256 entries
and 8 bit unsigned counters used to keep track of what is in the buffer.
One counter counts what has been added, and one counts what has been
removed. They naturally wrap around from 255 to 0 because they are 8 bit
unsigned values. 

What do we know about the values of the removed and added counters? We
know they have to start equal to each other. We know that the added
counter can be incremented so long as incrementing it will not make it
equal to the removed counter. We know that the removed counter can be
incremented when ever it is not equal to the added counter.

What happens if you have a partial update of the added counter? What are
the possible values it can have as the result of a partial update? In
the worst case, where the update can stop at an arbitrary bit, then the
result of a partial update leaves the counter either looking the same as
before: no changed bits have been written. Or different from before:some
changed bits have been written. The worst case is when you have a number
made up of a long sequence of 1s and add 1 to it so that a lot of bits
change to 0s at the same time.

01111111 (A)
+      1
--------
10000000 (B)

B can be written on A in in one of two orders. They can be filled low
order bits first, or they can be filled in high order bits first. The
partial updates can look like the following values

high to low   relation to actual value
11111111          >
10111111          >
10011111          >
10001111          >
10000111          >
10000011          >
10000001          >
10000000          =        full update

low to high  relation to actual value
01111110         <
01111100         <
01111000         <
01110000         <
01100000         <
01000000         <
00000000         <
10000000         =         full update

when we add something we are in the adding thread and that thread always
sees its variables as fully updated, but it can see partially updated
variables in other threads. The adding thread can always add if adding 1
to the counter does not make it equal to the removed counter. But, a
partial update prevents me from being able to tell if the two counters
are equal. I don't know any way to determine equality from a partial
update. 

In other words, I was wrong. You need an atomic read/write to make this
work. 

I have used this in production code, but the counters were 1 byte values
(68000 assembly code) and I am pretty sure that 1 byte read/writes are
atomic on all systems I have every seen. And, 1 byte counters can make a
very nice queue that is big enough for most applications. 

        My apologies to the group for posting false information,

                Bob Pendleton

> 
> The crux of the issue is if a context switch can occur while in the 
> middle of writing multiple bytes to a single variable.
> 
> If not, then what I have posted will work.
> 
> If so, then it won't work - however, the commented out code, if 
> commented back in, will cause it to work.  With the commented code, the 
> pointers are volatile and so is a boolean value inside the data structure.
> 
> It's a double locking mechanism:
> 
> To finish a write:
> Write the boolean true
> Update the write pointer
> 
> Done reading:
> Update the boolean false
> Update the read pointer
> 
> To start reading:
> Check if the boolean is true.
> Check if the read pointer does not pass the write pointer.
> 
> Lets suppose somehow that the boolean was mid-write (4 bits)? and so had 
> a corrupted value of true, when it should be false.  The first pass 
> (check if the boolean is true) would pass, however the second would not.
> 
> Lets suppose the write pointer was corrupted mid-write.  Because the 
> boolean is volatile, it is guaranteed to have been written immediately 
> (and thus before the write pointer was written to).  Therefore, the 
> boolean check would be valid and the operation would be correct despite 
> the pointer being invalid.
> 
> Or that is my logic at least.
> 
> Comments?
> 
> 
> Bob Pendleton wrote:
> > On Thu, 2006-02-09 at 09:21 -0800, Kevin Jenkins wrote:
> > 
> >>We're having a debate at work right now as to if you can write a 
> >>thread-safe single producer consumer class without critical section 
> >>locks.  I claim you can, while another programmer claims you cannot. 
> >>This is what I use:
> >>
> >>http://www.rakkar.org/sourcecode/SingleProducerConsumer.h.txt
> >>
> >>What I do is have two pointers - a write pointer and a read pointer. 
> >>They cannot cross each other.  Each pointer is only modified by one 
> >>thread.  Both threads compare these pointers using the == operator.
> >>
> >>There are a few articles on google claiming correctly you cannot use a 
> >>single shared pointer or index where both threads modify that variable, 
> >>but none use my approach where I have two variables and each is only 
> >>updated by its own thread.
> > 
> > 
> > I have used that technique in production code and it works great.
> > Better, it is provably correct. People get worried about the possibility
> > of comparing partially updated pointers. But, if you look at the range
> > of possible values for the pointers and the values that can be generated
> > by examining a partially updated multibyte pointer you see that this is
> > not a problem.
> > 
> >             Bob Pendleton
> > 
> > 
> >>---------------------
> >>To unsubscribe go to http://gameprogrammer.com/mailinglist.html
> >>
> >>
> >>
> 
> 
> ---------------------
> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
> 
> 
> 
-- 
+--------------------------------------+
+ Bob Pendleton: writer and programmer +
+ email: Bob@xxxxxxxxxxxxx             +
+ web: www.GameProgrammer.com          +
+ www.Wise2Food.com                    +
+ nutrient info on 7,000+ common foods +
+--------------------------------------+



---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts: