Locks - do they really serve any purpose?

g3cwi · 2012-03-08 11:16

I am starting to explore the Propellor Locks. If I understand the manual correctly these are not really locks in that nothing is locked by them. If that is the case I wonder what additional benefits they offer over simply setting a flag at a particular memory location?

Regards

Richard

Rayman · 2012-03-08 11:44

Good question. Was just looking at this old thread:
http://forums.parallax.com/showthread.php?109727-Does-anyone-use-LOCKs

Last post by Lonesock makes me wonder if the SD card reading code, FSRW, uses locks or not.

I'm also wondering if Locks are in Prop2 or if Chip decided to drop them...

Sariel · 2012-03-08 11:46

I am no expert on this, but from what I read, it is up to the programmer to use the locks... meaning, it is up to your code to find out if a section is "Locked" or not, depending on the values of the checked out lock(s) in question. If I am wrong, someone please clarify this for me too.

Heater. · 2012-03-08 11:47

If many processes, running in two cogs in the case of the Prop, want to read / update some complicated data structure in shared HUB RAM the they need some way to acheive mutual exclusion so that they don't end up reading half updated inconsistant data in.
If you think about this a bit you will see it cannot be done with simple flags that you read and write.
If the flag is clear when you read it, indicating you have access, how do you know someone else has not also read it as clear before you right back "not clear". If they have then then you will both be writing/reading the data structure at the same time and corrupting it.
Have a google for "mutual exclusion" or "atomic locks" I'm sure you will find something that explains it well.
However in many cases you can get by with no lock. A single reader process and a single writer process can cooperate with just simple flags or other means.
Have a look at how FullDuplexSerial works for the classic exa.ple.in the Propeller world.

mindrobots · 2012-03-08 11:50

True, a lock by itself locks nothing more than the bit implementing the lock mechanism. The LOCKSET instruction reads the the current state of the bit and returns it to you and ALWAYS sets the lock to one. If the state returned to you is == 0, then nobody had the lock set before you, so now it is yours (and set to 1). If the bit returned to you is == 1 then someone else had it locked and you should wait until you get a 0 returned. This read/write (test/set) sequence is not interruptable by any other COG so if you go to test it, someone else can't come in and set it before you do.

With all that said, there still need to be rules about using locks in your code to protect memory (pins, code, etc.). If any code that changes a shared structure and wants to be be safe, it should lock the lock the lock associated with the structure (wait, if it can't be locked), manipulate the structure, then unlock the lock associated with the structure. If you want to break the rules, you can write code that ignores the lock and just manipulates the structure. The lock doesn't really protect anything, it just gives you a tool to create an agreement in your code that can be protected if everybody follows the rules.

Make sense?

Heater. · 2012-03-08 11:51

At some pont Chip did ask the forum if it would be OK to drop the locks. Turns out there is Prop code out there that depends on locks and I'm sure the decision was to retain them in Prop II.

Duane Degn · 2012-03-08 11:55

Heater. wrote: »

At some pont Chip did ask the forum if it would be OK to drop the locks. Turns out there is Prop code out there that depends on locks and I'm sure the decision was to retain them in Prop II.

I've noticed Kye's objects you locks.

I haven't had many cases when a flag wouldn't do but I was glad to have the locks in those few cases.

Heater. · 2012-03-08 11:57

After you have your head around the need for mutual exclusion between processes and how atomic locks are used to implement that have another google for "deadly embrace" to see how a system made safe with locks can hang forever as one or more processes try to aquire locks on multiple resources at the same time.

mindrobots · 2012-03-08 12:04

Locks(semaphores) come in very handy when you start working at an OS level and look to creating multiple code threads running on either a single processor or full multi-threaded multi-processor environments. Many of the switching/dispatching data structures are heavily lock protected. Fun Stuff!!

mindrobots · 2012-03-08 12:05

a "deadly embrace" sure eliminates data corruption of shared structures!!

pedward · 2012-03-08 13:26

Chip said a while back he planned on removing the locks, but the instruction set in the 2.0 specs shows they have been retained.

Unless some problem comes up, I'm pretty certain that the instruction set in v2.0 is golden, not subject to change.

Dr_Acula · 2012-03-08 14:10

heater said

If the flag is clear when you read it, indicating you have access, how do you know someone else has not also read it as clear before you right back "not clear". If they have then then you will both be writing/reading the data structure at the same time and corrupting it.
Have a google for "mutual exclusion" or "atomic locks" I'm sure you will find something that explains it well.

My head has gone all funny!

Ok, thinking further, in the world of parallel processing, I wonder if there could be things one could learn from the most powerful parallel processor in the known universe? (ie that thing between your ears).

Rather than having locks which are an all or nothing affair, how about a numerical value associated with how much a process needs to access a shared resource. As the desire for access increases, so does its numerical value. For a biological example, think of your desire for food after a meal, 5 hours after a meal and 2 days after a meal. Actually, many biological desires work like that. Food. Sleep. Bladder. Bowel. Reproduction.

So thinking further, if the organism as a whole (ie the propeller chip) is not doing very much, it can afford to process the occasional serial byte that has come in, or the odd keypress.

But as the overall processing increases, this could be a way to prioritise things. The serial buffer that is almost full is like the kid at the back of the classroom with his hand up saying "please Miss, I *really* need to go to the bathroom".

I wonder if this might give smoother control overall. Or to use the analogy of all-or-nothing locks, you don't want that kid to get all the way to the bathroom to then find the door is locked!

Cluso99 · 2012-03-08 14:22

mindrobots: That is a nice explanation - clear and concise.

Locks are software only locks. That is, it is up to the software to acknowledge the use of the locks. There is no hardware protection provided by these locks, so its up to the programmer.

Locks provide a simple mechanism to the programmer. We could implement locks in hub using a number of instructions to achieve the same thing. The lock instructions are easier.

However, locks are hardly required because we tend to only require co-operation between cogs. An example is in Kye's SD driver. The upper cog ensures the command flag is clear (the slave cog driving the SD card) is no longer doing anything (it shouldn't because the upper cog is now going to set something) which indicates the upper cog can give the driver/slave a command. If ok, he sets up some parameters for the driver, and lastly sets the command flag that tells the driver that all parameters are set and to go do something. The driver should be waiting for the command flag to be set to something. When set, the driver determines using the flag and parameters, what it is to do, and when done, returns any parameters or buffers, and lastly clears the command flag to indicate it has completed its job.

Kye also uses locks in his SD code. IIRC that is for when the driver may be used by multiple threads to access the driver. I say threads meaning that it could be multiple cogs, or it could be one cog that accesses more than one file on the sd card. This ensures that the common parameters required for the driver are not inadvertantly changed - i.e. it is a protection mechanism for poorly written user code above Kyes upper and driver/slave code. (it is quite hard to explain)

Mike Green · 2012-03-08 14:41

Locks are absolutely necessary for a multiprocessor system like the Propeller ... any time you have multiple simultaneously executing processors sharing a resource like common memory. There was a time when a lot of work was done to prove that locks were not necessary in some specific circumstances like a single producer / consumer interaction. Chip's question about whether they were necessary to have was more about whether it was enough to only use interactions like the single producer / consumer where locks were not necessary or whether other multiprocessor interactions might be necessary to support. Kye's SD card driver shows that there might be and it's impossible to provide true locks without building the capability into the hardware.

Dave Hein · 2012-03-08 14:48

Cluso99 wrote: »

However, locks are hardly required because we tend to only require co-operation between cogs.

Not sure if you meant that locks are not normally required or locks are not required. I would agree that locks are not normally required in the applications that most people write. However, there are cases where locks make it easy to synchronize operations among multiple processors. Try writing to FullDuplexSerial from multiple cogs. Not only will you get a jumbled mess, but at some point one cog will use a different value for txhead than the value that another cog is using, and they'll write over each others output. Using a lock can convert this jumbled mess into a clean output.

It would have been nice to have more locks in P2, but as long as there is at least one hardware lock we can implement as many lock as we need in software.

localroger · 2012-03-08 15:03

There is nothing the lock accomplishes that can't also be accomplished by an atomically written numeric flag, but the lock does save a byte of RAM and a few runtime instructions since you don't have to write a claim value and check to make sure it stayed written before using the resource.

Bill Henning · 2012-03-08 15:34

Hi

- GCC needs locks as pthreads uses locks

- Morpheus needs locks

I am sure other applications use them too.

rokicki · 2012-03-08 16:53

fsrw does not use locks. Any locking needs to be done at a higher level.

In general, designing concurrent access to resources with significant state
like secure digital cards can be challenging. (What if one thread changes
the "current directory"; how does it "inform" the other thread? Or is there
some per-thread structure that is allocated to maintain this information?
A lock itself is not sufficient; nor is "separate file" support.)

mindrobots · 2012-03-08 17:10

See msg#11 in this thread - looks like lucky locks linger.

Kye · 2012-03-08 17:41

It would be nice to have an xChange instruction and compareAndSwap instruction like in X86.

Then you could have any many locks as you need.

Cluso99 · 2012-03-08 17:42

Dave: Yes, I should have said not normally required.

Mike: Locks can be achieved using the existing instruction set. But using the instructions is far easier and less prone to errors. Of course the priority has been reversed because the last to claim it in a loop will get it.
Here is an example...

wait     readbyte   test,lockptr  wz     
  if_nz  jmp          #wait                     'wait for lock to be free =0
          writebyte   ourcogid,lockptr     'claim the lock with our cogid
          readbyte   test,lockptr            'recheck we got it
          cmp         test,ourcogid wz
  if_nz  jmp          #wait
'we got it

rockiki: Kye can have multiple files open at a time. Locks are his protection from higher level coding errors when multiple versions of his code are running. BTW did you do the later mb-rawb-spi26 code that lonesock released?

Locks are often resolved by read-modify-write. This could be achieved in a different way on any hub location by having an instruction that writes to hub memory and returns a condition code if that hub memory was zero before the write. But of course, this would mean complicating hub memory and I would think this would most likely require the hub access to become 2 cycle.

IMHO we need the locks, and that is what appears to be in P2 anyway.

MagIO2 · 2012-03-08 23:47

And now let's have 2 COGs which run that code:

COG1                                           COG2
wait   readbyte    test,lockptr  wz            ...
if_nz  jmp         #wait                       ...
       writebyte   ourcogid,lockptr            wait   readbyte    test,lockptr  wz
       readbyte    test,lockptr                if_nz  jmp         #wait           
       cmp         test,ourcogid wz                   writebyte   ourcogid,lockptr
if_nz  jmp         #wait                              readbyte    test,lockptr    
                                                      cmp         test,ourcogid wz
                                               if_nz  jmp         #wait

Where COG2s readbyte HUB-window was before COG1s writebyte HUB-Window. BOTH COGs would "think" that they got the lock!

And this is exactly why it is the easiest way to have locks. What you try to accomplish with lockptr is a real atomic operation for the lock instruction.

Heater. · 2012-03-08 23:52

Cluso,

Mike: Locks can be achieved using the existing instruction set.

This is not true. In the general case of multiple readers and writers it is not possible to guarantee data integrity without some kind of atomic read/write operation. It is impossible to do it on the Prop without using the locks.

Drat, I said "impossible", now someone will show how to do it:)

MagIO2 · 2012-03-09 00:32

It is not possible if any COG is allowed to access the lockvar at any time. It IS possible if you synchronize the reads. Reading for first check only takes place at a certain computable timeframe where the timeframe is a full HUB round robin cycle. And reading for the recheck is done a few cycles later. The COG which finds it's ID in the lockvar won the lottery ;o)

But besides wasting codespace you also waste time, thus a lock is much better!

kuroneko · 2012-03-09 00:45

MagIO2 wrote: »

It is not possible if any COG is allowed to access the lockvar at any time.

Maybe it's not my day. Can you explain this to me? The sequence shown (Cluso99) is rdbyte/wrbyte/rdbyte (3 consecutive hub windows).

Heater. · 2012-03-09 00:59

A single writer and a single reader can safely share RAM (or other resource) using a flag or fifo. That sneaky buffer sharing in FullDuplexSerial is one of my favorite software tricks.

That means:
1. A chain can be formed of processes linked by fifos. For each fifo there is only one writer and one reader so all is safe.
2. We can now loop the end of the chain back to the first process, via another fifo, and circulate data safely around the loop.
3. The processes now pass a "token" from node to node around the loop. That is to say that if a node has just received some special message it is said to hold the token. If it has just sent that message on down the line it then it no linger holds the token.
4. Whichever process holds the token is allowed to access a resource that they all share. When done with the resource the token is passed on.

Ergo, we don't need locks to achieve mutual exclusion between multiple readers and writers.

Cluso, my apologies, I think I have proved myself wrong.

If it woks for sharing time on a network cable, the token ring LANs, it should be sound.

Heater. · 2012-03-09 01:17

Guys,

Is it so that I have missed a point here and Cluso's lock loop is actually is safe?

Looking at it I was forgetting where I am and that on the Propeller:

1) There are no interrupts to introduce arbitrary delays between wrbyte and rdbyte.

2) Access to HUB is forced to follow the round robin cycle.

Is it so that given those conditions the lock loop is safe? Thinking it through some more....

Now what about doing it from Spin? At first sight it looks like all bets are off.

Cluso99 · 2012-03-09 01:48

MagIO2 wrote: »

And now let's have 2 COGs which run that code:

COG1                                    COG2                                    HUB(after instr)
wait   readbyte    test,lockptr  wz     ...                                     0 (free)
if_nz  jmp         #wait                ...                                     0
       xxxx                             wait   readbyte    test,lockptr  wz     0 (free)
       writebyte   ourcogid,lockptr     if_nz  jmp         #wait                1 (1 claims it)
       xxxx                                    xxxx                             1
       xxxx                                    writebyte   ourcogid,lockptr     2 (2 claims it)
       readbyte    test,lockptr                xxxx                             2
       cmp         test,ourcogid wz            xxxx                             2
if_nz  jmp         #wait                       readbyte    test,lockptr         2 (1 lost it)
                                               cmp         test,ourcogid wz     2
                                        if_nz  jmp         #wait                2 (2 has it!)

What is wrong with this?

I am not sure spin could achieve the same, and certainly not a mix of spin and pasm. But, we could "nobble" spin to implement the pasm code

MagIO2 · 2012-03-09 01:51

kuroneko wrote: »

Maybe it's not my day. Can you explain this to me? The sequence shown (Cluso99) is rdbyte/wrbyte/rdbyte (3 consecutive hub windows).

What I mean is that the 2 (or more) COGs which have to share a resource are allowed to request the resource at any time they want. As I showed in post #22 with the read/write/read sequence, you can have a scenario where both COGs really think that they have the exclusive lock. (one line shows which instruction is executed in which COG at the same time.) You can only ensure that read/write/read works when you have sync-points for this.

1st read has to take place when each COG can be sure that no other COG will update it in the next few instructions
write for all COGs has to take place in the exactly same HUB-cycle
2nd read for checking has to take place after that write cycle

Tokens of course solve the problem, but would you really prefere a token implementation over the locks? Where do you find token ring hardware these days? ;o)

MagIO2 · 2012-03-09 02:00

@kuroneko: Oh ... maybe it's me who stands beside himself currently ;o) Guess I have to think about it after work.

Heater. · 2012-03-09 02:05

Where do you find token ring hardware these days?

If you have old Macs around they used token ring in the AppleTalk network to printers and such.

Anyway my token ring need no hardware but the Prop.

Locks - do they really serve any purpose?

Comments