# Linux: Synchronization

In modern computers, we have multi-core (multi-processor) to do parallel programming, however, synchronization between the threads is very hard to achieve. To deal with these sync issues, some solutions are provided.

## Basics
### Hardware Support
#### 1. Atomic instruction
Instruction that cannot be stopped while exectuting.
- test and set
- compare and swap
- fecch and add

#### 2. Memory Barrier
Many compilers will optimize the code by **reordering** the instruction. Sometimes we don't want that, for example, we don't want some value be modified before the permission is granted.

Memory barrier ensures **all load/store before the barrier are done before load/store after the barrier**.

// thread 1
// ensure flag is loaded before x
while (!flag)
    memory_barrier();
print(x);

// thread2
// ensure x is modified before setting the flag
x = 100;
memory_barrier();
flag = 1;

### Lock
If a segment of code contains some **shared resources**, then it is called a **critical section**.

Before entering the CS, each thread must acquire the lock.

// thread 1, 2 might call this fn
void fn() {
    acquirelock(lock);
    
    // CS
    x = 100;
    
    releaselock(lock);
}

### Deadlock
If two processes are waiting to acquire the lock of each other, then a deadlock occurs.

// thread1
acquirelock(lock1);  // 1st
acquirelock(lock2);  // 3rd

// thread2
acquirelock(lock2);  // 2nd
acquirelock(lock1);  // 4th

## xv6
xv6 provides 2 types of lock
- spinlock
- sleeplock

### spinlock
By using

- test and set
- memory barrier

to achieve locking.

// Acquire the lock.
// Loops (spins) until the lock is acquired.
void
acquire(struct spinlock *lk)
{
  push_off(); // disable interrupts to avoid deadlock.
  if(holding(lk))
    panic("acquire");

  // Atomically acquire the flag
  while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

  // Memory Barrier
  // we don't want load/store before the lock is actually acquired.
  __sync_synchronize();

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();
}

// Release the lock.
void
release(struct spinlock *lk)
{
  if(!holding(lk))
    panic("release");

  lk->cpu = 0;

  // Memory Barrier
  __sync_synchronize();

  // Atomically set lk->locked = 0.
  __sync_lock_release(&lk->locked);

  pop_off();
}

However, this will decrease CPU performance, as it is just keeping asking if the lock is available, not completing the actual task.

So here comes the second kind of lock.

### Sleeplock
It is similar to **conditional variable**.

We have a spinlock `lk` (call it **small lock** here) to protect the sleeplock `lock` (call it **big lock**).

// Long-term locks for processes
struct sleeplock {
  uint locked;       // Is the lock held?
  struct spinlock lk; // spinlock protecting this sleep lock
  
  // For debugging:
  char *name;        // Name of lock.
  int pid;           // Process holding lock
};

The sleeplock works as follows
1. acquire the small `lk`
2. try to acquire the sleeplock
3. if sleeplock is not available: sleep and atomically release `lk`
4. if waked up: atomically acquire `lk` and go to 2.
5. release `lk`

void
acquiresleep(struct sleeplock *lk)
{
  acquire(&lk->lk);
  while (lk->locked) {
    // atomically release the lock and be put to sleep queue
    sleep(lk, &lk->lk);
  }
  lk->locked = 1;
  lk->pid = myproc()->pid;
  release(&lk->lk);
}

void
releasesleep(struct sleeplock *lk)
{
  acquire(&lk->lk);
  lk->locked = 0;
  lk->pid = 0;
  // put a process waiting for this lock into ready queue
  wakeup(lk);
    
  // release the lock
  release(&lk->lk);
}

If we just look at the code of sleeplock, we can discover an issue called **lost wakeup** problem.

If process 1 releases the small lock and has not yet entered the sleep queue, meanwhile, process 2 acquires the small lock and calls `wakeup()` to found no one to wakeup, then process 1 sleeps and so it will never get up.

In fact, it will not happen, as each process has another spinlock to protect its state.

void
sleep(void *chan, struct spinlock *lk)
{
  struct proc *p = myproc();
  
  // Must acquire p->lock in order to
  // change p->state and then call sched.
  // Once we hold p->lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup locks p->lock),
  // so it's okay to release lk.

  acquire(&p->lock);  // prevents lost-wakeup
  release(lk);

  // Go to sleep.
  p->chan = chan;
  p->state = SLEEPING;

  sched();

  // Tidy up.
  p->chan = 0;

  // Reacquire original lock.
  release(&p->lock);
  acquire(lk);
}

void
wakeup(void *chan)
{
  struct proc *p;

  for(p = proc; p < &proc[NPROC]; p++) {
    if(p != myproc()){
        
      // must acquire process lock to read/write its state
      acquire(&p->lock);
      
      if(p->state == SLEEPING && p->chan == chan) {
        p->state = RUNNABLE;
      }
      release(&p->lock);
    }
  }
}

### conclusion
Although sleeplock has a spinlock to protect it, processes won't wait much time spinning, as the spinlock just protects the acquisition of sleeplock, which is just a small CS !

In summary, **spinlock** is good for protecting **short critical section**, while **sleeplock** is good for **long critical section**.

###### tags: `Linux`