[mit 6.s081] LEC 10: multiprocessors and locking notes

Lec 10: Multiprocessors and locking

• Ref: https://github.com/huihongxiao/MIT6.S081/tree/master/lec10-multiprocessors-and-locking
• Preparation: xv6 book Chapter 6

Why locks are needed

• Multi core operation improves performance
• Sharing data while reading and writing will generate race conditions (race condition)

Lock object

• API:
  • acquire(&lcok): Only one process can acquire a lock at any time
  • release(&lock): Release the lock , Other processes need to wait until the lock is released to obtain .
• acquire And release The code snippets between them are called critical areas , The overall execution of code fragments is atomic
• Usually, the operating system will have multiple locks , Make different system calls use different locks , Improve parallelism .

When to use the lock

If two processes access a shared data structure , And one of the processes will update the shared data structure , Then you need to lock the shared data structure .
This rule is sometimes strict : Some scenes can work without locking , Programs that do not lock are called lockless programming (lock-free program).
Sometimes it's loose , For some unshared data, the output of atoms is still needed , Such as printf() Output .

The function of lock

• Avoid losing updates
• Make multi-step operation atomic
• Maintain the invariance of shared data structures
  

Deadlock

• Deadlock caused by reentry : A process obtains a lock and tries to obtain the same lock after entering the critical area , Locks can cause deadlocks if they are not reentrant .
• deadly embrace: Multiple processes hold multiple locks , Each other needs to get each other's lock
  A solution : Yes ( In common use ) Lock sorting , Acquire locks in sequence

Lock implementation

Generally with the help of Hardware instructions test-and-set, Such as XV6 Atomic exchange operation in (Atomic Memory Swap) amoswap addr, r1, r2, Memory address can be atomically addr The value of is written to the register r2, Register r1 Write the value of addr.
notes : store Instructions are not necessarily atomic operations .

  // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
  // a5 = 1
  // s1 = &lk->locked
  // amoswap.w.aq a5, a5, (s1)
  while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

Above is XV6 In spin lock test-and-set operation , if lk->locked==0, Then write 1 And back to 0, Loop exit , Indicates that the lock has been obtained . if lk->locked==1, It is also written 1 But it also returns 1, Will continue to cycle , until lk->locked Field is 0 Then you can get the lock .
__sync_synchronize() The function will generate fence Instructions for memory barrier , Prevent command rearrangement .
stay acquire and release Operation requires Turn off interrupt , Prevent atomic operations from being interrupted or lock reentry .