5.5.Synchronization
5.5.Synchronization
1.Some concepts
2.Lock synchronization
3.Hardware synchronization
\(a.\)Possible lock problem
To solve the problem, the multiprocessor must have the ability ot atomically read and modify a memory location. That is, nothing else can interpose itself between the read and the write of the memory location.
For example, consider two processors that each try to do
lw
operation. This race is prevented, since exactly one of the processors will performlw
first, returning 0, and the second processor will return 1 when it does this. This is because the operation is atomic: the exchange is indivisible, and two simultaneous exchanges will be ordered by the hardware.
\(b.\)instruction pair
To implement atomical property, we can set a pair of instructions in which the second instruction returns a value showing whether the pair of instructions was executed as if the pair was atomic.
In RISC-V, this pair of instructions includes a
(lr, d)
and a (sc, d)
:
- Thus,
sc.d
specifies three registers: one to hold the address, one to indicate whether the atomic operation failed or succeeded, and one to hold the value to be stored in memory if it succeeded.
Notice that
(lr, d)
operation not only load a word into pointed memory, but also record the memory address internally, namely reservation. That's why we can use(sc, d)
to check if the operation is atomical.
We can use this pair to implement atomic swap:
1 | again: lr.d x10, (x20) |
Any time a processor intervenes and modifies the value in memory
between the lr.d
and sc.d
instructions, the
sc.d
writes a nonzero value into x11
, causing
the code sequence to try again.
Since the store-conditional will fail after either another attempted store to the load reservation address or any exception, care must be taken in choosing which instructions are inserted between the two instructions. In particular, only integer arithmetic, forward branches, and backward branches out of the load-reserved/store-conditional block can safely be permitted; otherwise, it is possible to create deadlock situations where the processor can never complete the sc.d because of repeated page faults. In addition, the number of instructions between the load-reserved and the store-conditional should be small to minimize the probability that either an unrelated event or a competing processor causes the store-conditional to fail frequently.
Other atomic memory operations can be built using
lr/sc
pairs, some are listed below: