Previous | Next --- Slide 11 of 30
Back to Lecture Thumbnails
mangocourage

How is test-and-set implemented? After loading a memory address into memory, is the associated write somehow tagged so that the interconnect can guarantee that that particular write happens before any other write to the same address?

kayvonf

Modern processors implement compare_and_swap or LL/SC (load linked store conditional). Here's a rough sketch of an approach: the cache loads line in exclusive state, but will not allow the exclusive state to be relinquished until the processor completes the ts operation.

byeongcp

Just to clarify, is the ts R0, mem[addr] atomic implementation that puts together

ld R0, mem[addr]
cmp R0, #0
st mem[addr], #1

from the previous slide? The problem in the previous slide was that multiple processors could load address addr and if mem[addr] happened to be 0, these processors could acquire the lock at the same time. Having load, compare, and set as a atomic instruction would prevent multiple processors from seeing mem[addr] as 0 when they all try to acquire the lock (and hence prevent multiple processors from acquiring the lock at the same time).

kayvonf

Yes, @byeongcp, that is correct.

jiajunbl

In the intel instruction set, there is the LOCK prefix for assembly instructions. From what I understand the meaning of this has evolved from locking the entire memory bus to locking a specific cache line.

What's the overhead of such bus locks in modern day computers. I.e. how much badness is having the LOCK prefix in today's context?

rokislt10

Funny, I actually accidentally implemented this lock on Assignment 2. Ultimately, it proved to be too slow since it used a while loop, but I thought I was being very clever for a bit.