Do I really need locks for this?

pgbpsu

I'm working on a buffering scheme where one (PASM) cog fills a buffer while a SPIN cog empties it. The fill rate is predictable, but the empty rate is not- most times it will exceed the fill rate, but occasionally it will be much slower. My buffer contains 16 slots and I want to be sure that the filling cog has has access to any/all empty slots while the dumping cog is working. My idea was is to have the 2 cogs share a "slotsLeft" variable. When the whole process starts all 16 are empty. As the filing cog fills a slot it decrements this (meaning fewer free slots). As the dumping cog empties a slot it would increment this variable indicating a new free slot. Every time the filling cog (PASM) finishes filling one slot it checks to see if there are any free slots before collecting any more data. If not, it waits until a slot opens up and then fills it.

For this to work I think I need to use a lock/semaphore. The PASM cog requires a read, modify, write to change the value in "slotsLeft". I believe the SPIN cog does it in one operation, but clearly the SPIN cog could try to modify it while the PASM cog has already read it but not yet modified or returned it.

This is a producer/consumer so I'm not convinced I need to do it this way, but I don't see anyway to keep the two cogs running full speed without them sharing info about how many elements are in the buffer.

Is there another way to accomplish this? Can anyone point me to an example using locks with PASM? I can't find any in the examples provided with the Prop Tool?

Thanks in advance,
Peter

Phil Pilgrim (PhiPi)

Why not do it as a circular FIFO buffer? You would have two variables: an enqueue pointer and a dequeue pointer. The PASM code would own the enqueue pointer; the Spin code, the dequeue pointer. That way no locks are required, as they would be with both cogs modifying the same variable.

-Phil

Mike Green

The safest thing to do is to use a lock. The main situation where you can manage without a lock is when only one cog does a read / modify / write operation and other cogs just read this location. In addition, there must never be a case where there will be a problem if the read-only cogs get the value while the read/write cog is changing it. Look at something like FullDuplexSerial for an example using a Producer / Consumer and a circular buffer with a read pointer and a write pointer.

To wait for access to a critical section:

:WaitForIt  LOCKSET  myLock     wc
      if_c  JMP      #:WaitForIt

To release access to a critical section:

            LOCKCLR   myLock

Remember to do a LOCKCLR when you first get the lock with a LOCKNEW. I think a new lock is cleared, but it's best to explicitly clear it initially.

kuroneko

@Mike: The jump condition should be if_c (carry set == locked). Also, the lock state is kept accross lockret/locknew so good advice re: initial clearing.

pgbpsu

Phil,
Thanks for your response. I believe I've got this setup as a circular buffer FIFO but rather than keep track of the enqueue and dequeue pointers, I was trying to keep track of the number of free elements. I think this got me headed in a direction that would require locks. I'll think about this and see how I might re-write this to do what you've suggested.

Mike,
Thanks for the pointer to fullDuplexSerial. I searched as many potential lock programs as I could think of but didn't find lockset in any of them. Hopefully fullDuplexSerial will enlighten me, but if not, thanks to your syntax I can do this as I'd planned. However, the two separate pointer idea seems like it would be faster because right now I've got "wait until lockset stuff" on both sides. The goal here is speed so if the en/dequeue method is faster I'd prefer that.

Kuroneko,
Thanks for the correct syntax. Incorporating this is probably the fastest way to get this working but a rewrite might give better speed.

Regards,
Peter

Mike Green

pgbpsu,
FullDuplexSerial doesn't use locks because it fits the special case where locks aren't needed.

kuroneko,
Thanks for the info and correction

pgbpsu

Hi Mike-

My response was a bit muddled, but based on your initial response, it was clear to me that one way to do this would be locks, another would be to follow the example in fullDuplexSerial (no locks). Thanks though for the clarification.

Mark_T

Phil Pilgrim (PhiPi) wrote: »

Why not do it as a circular FIFO buffer? You would have two variables: an enqueue pointer and a dequeue pointer. The PASM code would own the enqueue pointer; the Spin code, the dequeue pointer. That way no locks are required, as they would be with both cogs modifying the same variable.

-Phil

Yes, this is a nice solution, related to event counters, but is not quite as simple as it first appears, since if the enqueue and dequeue pointers are equal this can represent two different situations - the buffer is empty and the buffer is full. This can be fixed by disallowing the buffer being entirely full (you waste one slot).

However the problem is easily fixed by event counters (sometimes called event tokens or semaphores I think). Basically each agent has control of a counter variable that it only ever increments (the producer counts the items it has produced and placed in the buffer, the consumer counts the number it has removed). To index the buffer you take the counters modulo the size of the buffer, and to test for empty or full is:

PUB  isfull
  result := produced - consumed == BUFFERSIZE
PUB isempty
  result := consumed == produced

Since the counters may overflow the modulo operation could then fail unless you use a power-of-two for the buffer size.

http://en.wikipedia.org/wiki/Producers-consumers_problem#Without_semaphores_or_monitors

Dr_Acula

I only found out about circular buffers relatively recently in programming and they are very useful.

"head" and "tail" seem to be common labels. The code filling up the buffer adds one to the head. (do a logical "and" with a number like %00001111 to make it wrap at that number back to zero which is 16 in that example)
The code reading the data moves the tail up by one.

The buffer is full when head is one less than tail (again allowing for the wraparound). Buffer is empty when head equals tail.

One potential problem is when you code it and forget about the wraparound condition - eg a big buffer like 256 bytes, hardly ever full, wraparound only occurs at byte 255, and so when debugging, it works most of the time and only produces intermittent faults.

I was trying to keep track of the number of free elements.

In a FIFO that is the number of elements used is head minus tail. Free elements is 16 minus that number if you are using 16 slots. Watch the wraparound again though. head = 12, tail is 10 means 12-10 = 2 slots free. head = 1 and tail = 15 is the same situation but 1-15 does not give the correct answer unless you do that wraparound correction.

Fortunately all those wraparound corrections end up being logical and/or type operations which are single spin or pasm commands.

I like to draw FIFO buffers on a piece of paper and check a few of the numbers work correctly.

Locks are safest. There are other solutions too. I've written code where you use a bigger buffer and detect when the head is getting close to the tail. There is some maths based on the speed of data coming in vs the speed it is going out, but if, say, you had a 256 byte buffer and the head was within 10 of the tail, then the sending routine needs to slow down a bit, and/or the receiving routine needs to get a hurry along!

Heater.

Dr_A,
Note that the head and tail indexes do not need to be masked when incremented or compared. They can just keep on growing until they wrap around their 32 bits or whatever size they are. They only need to be masked when actually used to access the buffer. This msy save some code in some circumstances.
Of course if your buffer indexes are held in byte variables they will be automatically masked with FF when stored back to hub with wrbyte. So a 256 element buffer can even work without masking operations.

pgbpsu

Mark_T

Thanks for the wiki link. This is what I followed, which is what both Mike and Phil suggested. Thankfully I wasn't too far off. I canned my slotsFree variable and replaced it with a subtraction of the two different pointers. The c/pseudo code really laid it all out.

Code is working great, now I just need to finish testing it and tune my FIFO size.

Thanks,
Peter