Lock 锁的实现

锁的种类

自旋锁(spinlock)：无法获得锁，就一直循环获取，适合短时间的加锁

睡眠锁(sleeplock)：为了防止长时间的循环等待，在获取不到锁时，进程陷入睡眠，当锁释放时对睡眠进程进行唤醒

自旋锁的实现

其实自旋锁的实现很简单，不过是一个状态量置1或者置0的操作

为了防止中断产生死锁以及编译器将临界区的指令重排到锁操作外，使用一些特殊指令

在修改状态量时，使用原子操作确保不会出现操作过程中，其他操作发生。

// 自旋锁的数据结构
// Mutual exclusion lock.
struct spinlock {
  uint locked;       // Is the lock held?

  // For debugging:
  char *name;        // Name of lock.
  struct cpu *cpu;   // The cpu holding the lock.
};

// 辅助函数
// Check whether this cpu is holding the lock.
// Interrupts must be off.
int
holding(struct spinlock *lk)
{
  int r;
  // 锁处于被持有状态并且持有cpu为当前cpu 返回 1(ture)
  r = (lk->locked && lk->cpu == mycpu());
  return r;
}

// 加锁操作
// Acquire the lock.
// Loops (spins) until the lock is acquired.
void
acquire(struct spinlock *lk)
{
  // 关中断
  // 加解锁的流程中需要关闭中断
  // 防止使用锁的过程中中断，而中断处理程序又需要锁，造成死锁
  push_off(); // disable interrupts to avoid deadlock.
  
  // 判读当前cpu是否正在持有该锁
  // 如果当前CPU在其他位置持有了这个锁，那么当前的加锁操作将永远无法完成
  // 程序会阻塞在当前位置，并且其他位置持有锁的位置也无法释放
  // 程序将进入死锁状态
  if(holding(lk))
    panic("acquire");
	
	//  __sync_lock_test_and_set(&lk->locked, 1)	
  // 加锁的原子操作，确保括号中的操作为原子操作，一般是使用CPU的特殊硬件指令实现	
	// 效果：如果lk->locked等于0，我们调用test-and-set将1写入locked字段，并且返回locked字段之前的数值0。
  // 如果lk->locked等于1，则返回1
  
  // 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)
    ;
	
  // __sync_synchronize()	
  // 从当前位置到下一个__sync_synchronize指令之间禁止指令重排
  // 加锁和critical section的代码执行通常完全相互独立，它们之间没有任何关联
  // 因此CPU和编译器极有可能将critical section代码置于锁之外	
  // 对于synchronize指令，任何在它之前的load/store指令，都不能移动到它之后
  // Tell the C compiler and the processor to not move loads or stores
  // past this point, to ensure that the critical section's memory
  // references happen strictly after the lock is acquired.
  // On RISC-V, this emits a fence instruction.
  __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;

  // Tell the C compiler and the CPU to not move loads or stores
  // past this point, to ensure that all the stores in the critical
  // section are visible to other CPUs before the lock is released,
  // and that loads in the critical section occur strictly before
  // the lock is released.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();
	
  // __sync_lock_release()	
  // 原子性的将lk->locked置0
  // Release the lock, equivalent to lk->locked = 0.
  // This code doesn't use a C assignment, since the C standard
  // implies that an assignment might be implemented with
  // multiple store instructions.
  // On RISC-V, sync_lock_release turns into an atomic swap:
  //   s1 = &lk->locked
  //   amoswap.w zero, zero, (s1)
  __sync_lock_release(&lk->locked);

  pop_off();
}

睡眠锁的实现

lost wake-up problem

由于执行顺序的原因，wake up在sleep之前被调用，导致sleep无法被唤醒。

解决方法：使用条件锁，即linux中的pthread_cond_wait

sleep

sleep函数，需要两把锁的使用。

首先是临界区的锁，在sleep中释放临界区锁，让生产者可以获得锁。

其次是进程锁，进程状态需要修改为sleep状态，需要加锁处理

在进入sleep状态时，获取进程锁，释放临界区锁，这里意图是解决lost wake-up问题，

指定进程的chan，修改进程状态，调用sched函数进行进程调度

在被wake up唤醒后，sleep释放进程锁，并且获得临界区锁

wakeup

wakeup函数循环全部进程列表，如果进程sleep在相应的chan中，则将进程状态改为可运行

在判断进程状态时，要先获取该进程锁，防止在判断语句中间，出现其他进程修改了进程状态。

// 睡眠锁的数据结构
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
};

void
acquiresleep(struct sleeplock *lk)
{
  acquire(&lk->lk);
  while (lk->locked) {
    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;
  wakeup(lk);
  release(&lk->lk);
}

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
// sleep函数设置当前进程的chan(表示等待该chan的信息)，
// 然后将进程设置为SLEEPING状态，放弃CPU，进入进程调度
// 被唤醒后，将继续执行sched()函数后面指令，将chan置空
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);  //DOC: sleeplock1
  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);
}

// Wake up all processes sleeping on chan.
// Must be called without any p->lock.
// wakeup函数将所有在当前chan等待的进程状态全部设置成RUNNABLE
void
wakeup(void *chan)
{
  struct proc *p;

  for(p = proc; p < &proc[NPROC]; p++) {
    if(p != myproc()){
      acquire(&p->lock);
      if(p->state == SLEEPING && p->chan == chan) {
        p->state = RUNNABLE;
      }
      release(&p->lock);
    }
  }
}