Subj : Re: possible lock-free stack on G4 livelock issue... To : comp.programming.threads From : Joseph Seigh Date : Mon Jan 17 2005 02:32 pm On Mon, 17 Jan 2005 14:15:34 -0500, Joseph Seigh wrote: > On Mon, 17 Jan 2005 10:42:24 -0800, SenderX wrote: > >> In the push function for a lock-free stack the new node's next pointer to >> set to the front of the stack before the actual atomic operation ( cas or >> ll/sc ) that updated the stack is executed: >> >> retry: >> lwarx r2,0,r3 >> stw r2,0(r4) >> sync >> stwcx. r4,0,r3 >> bne- retry >> >> >> What if more than once node's next pointers are in the same reservation >> granule? What if the new node's next pointer was on the same granule as the >> stack anchor? >> >> I believe this could cause a possible race-and-live-lock scenario. Any >> thoughts? >> .... > > For push you could just do a regular load and store into the new node, > then do a load reserved and test that value with the previously loaded > value and retry if different. Might need a sync between the store and > load reserved which would be expensive so I'd confirm it was actually > going to be a problem first before trying that approach. Actually, this is what the list insertion example in appendix E of the powerpc architecture manual does. There's only the one sync but you need it anyway. Joe Seigh -- Joe Seigh .