When any thread tries to obtain a lock, after the first instruction, there can only be two possible cases:
1) R0 = 0 -> before ts, mem[addr] was 0; after ts, lock is obtained and mem[addr] has been set to 1, then break loop.
2) R0 = 1 -> before ts, mem[addr] was set to 1 by other threads, i.e. lock held by others; after ts, bnz to "lock" and check again...
BensonQiu
I was curious how atomic test-and-set is implemented. The Wikipedia article suggests that test-and-set can be implemented with explicit hardware support using dual-ported RAM (DPRAM). When a processor P1 issues a test-and-set instruction at a particular memory address, DPRAM will store the memory address. If another processor P2 issues a test-and-set instruction at the same memory address, and the test-and-set issued by P1 has not yet completed, DPRAM will see the stored memory address from P1 and issue a BUSY interrupt to P2, indicating to P2 that it needs to wait and retry.
eknight7
Just to clarify as in previous slide, bnz R0, lock simply states if R0 != 0 (because ts didn't set mem[addr], as mem[addr] != 0), then jump to lock and repeat, but if R0 == 0, then no need to jump (because ts must have now set mem[addr] = 1). So the comment "//if 0, lock obtained", means if "R0 == 0" lock obtained.
yangwu
the reason why load-test-store doesn't work but test-and-set works is the latter one use ts operation to load and set value in one operation; in previous one, it uses two operations which allow the other thread comes in.
Richard
Just to make clear, is the approach presented in this slide a "busy waiting" synchronization? I don't think it's a blocking sync, since there isn't any instructions here that can lead to thread switching.
cyl
I think it is busy waiting. Since bnz would jump to ts if it cannot acquire the lock.
What is bnz? And how does it help in this case?
@efficiens You can find it here
When any thread tries to obtain a lock, after the first instruction, there can only be two possible cases:
1) R0 = 0 -> before ts, mem[addr] was 0; after ts, lock is obtained and mem[addr] has been set to 1, then break loop.
2) R0 = 1 -> before ts, mem[addr] was set to 1 by other threads, i.e. lock held by others; after ts, bnz to "lock" and check again...
I was curious how atomic test-and-set is implemented. The Wikipedia article suggests that test-and-set can be implemented with explicit hardware support using dual-ported RAM (DPRAM). When a processor P1 issues a test-and-set instruction at a particular memory address, DPRAM will store the memory address. If another processor P2 issues a test-and-set instruction at the same memory address, and the test-and-set issued by P1 has not yet completed, DPRAM will see the stored memory address from P1 and issue a BUSY interrupt to P2, indicating to P2 that it needs to wait and retry.
Just to clarify as in previous slide, bnz R0, lock simply states if R0 != 0 (because ts didn't set mem[addr], as mem[addr] != 0), then jump to lock and repeat, but if R0 == 0, then no need to jump (because ts must have now set mem[addr] = 1). So the comment "//if 0, lock obtained", means if "R0 == 0" lock obtained.
the reason why load-test-store doesn't work but test-and-set works is the latter one use ts operation to load and set value in one operation; in previous one, it uses two operations which allow the other thread comes in.
Just to make clear, is the approach presented in this slide a "busy waiting" synchronization? I don't think it's a blocking sync, since there isn't any instructions here that can lead to thread switching.
I think it is busy waiting. Since bnz would jump to ts if it cannot acquire the lock.