baum@apple.com (Allen Baum) (04/25/91)
I'm a bit confused about the explanation for Load Linked & Store Conditionally. Supposedly, a compare&swap can be implemented with: Ld_Linked old->tmp & set status Branch if tmp!=match to .skip ;(didn't match) Store_Conditionally new->old & clr status Now, if some other processor jumps in between the Branch & store with the whole sequence,does the status bit get cleared in this processor? - if its a CAS sequence to the same lock, then it must, else both will think they got the lock - if its a CAS sequence to a different lock, then you don't want to? (because you'll be reduced to spinning on that location) If not, how do you keep track of which location this processor is CAS'ing (excuse the verbing of CAS, please). If you, say, have a reg. that keeps track of it, what happens if another process on the same processor gets swapped in & wants to CAS to anothe location- does it clobber the old address? etc. etc. etc.... It might be simply that ANY other Ld_Linked clears the status, so you spin once (perhaps) & either fail if someone else grabbed it, or succeed if someone else grabbed another lock. On the other hand, this isn't that different than a test&set spinlock to a single global system-wide lock. So..... what am I missing?
mash@mips.com (John Mashey) (04/25/91)
In article <51947@apple.Apple.COM> baum@apple.com (Allen Baum) writes: >I'm a bit confused about the explanation for Load Linked & Store Conditionally. >Supposedly, a compare&swap can be implemented with: >Ld_Linked old->tmp & set status >Branch if tmp!=match to .skip ;(didn't match) >Store_Conditionally new->old & clr status > >Now, if some other processor jumps in between the Branch & store with >the whole sequence,does the status bit get cleared in this processor? Yes, it has to. >- if its a CAS sequence to the same lock, then it must, else both will > think they got the lock >- if its a CAS sequence to a different lock, then you don't want to? > (because you'll be reduced to spinning on that location) If not, how do > you keep track of which location this processor is CAS'ing > (excuse the verbing of CAS, please). If you, say, have a reg. that keeps > track of it, what happens if another process on the same processor gets > swapped in & wants to CAS to anothe location- does it clobber the old > address? etc. etc. etc.... >It might be simply that ANY other Ld_Linked clears the status, so you spin >once (perhaps) & either fail if someone else grabbed it, or succeed if >someone else grabbed another lock. On the other hand, this isn't that >different than a test&set spinlock to a single global system-wide lock. A minimal implementation would: 1) Keep 1 bit to indicate outstanding LL 2) Turn bit off upon any exception. 3) Turn bit off if any other processor does a store that causes an invalidate or update request to come to this processor, for any cache line whatsoever. 4) Always, SC returns previous value of bit, and inhibits the store if the bit was not set. In this case, what you have is a safe, but minimal implementation. For more performance: 1) Keep the bit, as in 1) and 2) above. 2) When you do a LL, turn the bit on, and also save the address of the cache line in which the LL'd word appears. 3) When you must do a snoop for invalidate and update, turn the bit off if-and-only-if the snoop address matches the address you have saved. -- -john mashey DISCLAIMER: <generic disclaimer, I speak for me only, etc> UUCP: mash@mips.com OR {ames,decwrl,prls,pyramid}!mips!mash DDD: 408-524-7015, 524-8253 or (main number) 408-720-1700 USPS: MIPS Computer Systems MS 1/05, 930 E. Arques, Sunnyvale, CA 94088-3650