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 perform lw 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:

again: lr.d x10, (x20)
       sc.d x11, x23, (x20)
       bne x11, x0, again   // branch if store fails
       addi x23, x10, 0     // put loaded value in x23

  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:

  \(c.\)Test-and-Set instruction