作业地址

锁的实现

锁的结构

阅读 spinlock.h ，锁的结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 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.
  uint pcs[10];      // The call stack (an array of program counters)
                     // that locked the lock.
};

spinlock 结构体中 locked 作为标识位， locked = 1 则为上锁，否则已经释放锁

acquire()

阅读 xv6 下 spinlock.c，知道 xv6 提供 acquire() 用于获取锁， release() 用于释放锁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Acquire the lock.
// Loops (spins) until the lock is acquired.
// Holding a lock for a long time may cause
// other CPUs to waste time spinning to acquire it.
void
acquire(struct spinlock *lk)
{
  pushcli(); // disable interrupts to avoid deadlock.
  if(holding(lk))
    panic("acquire");

  // The xchg is atomic.
  while(xchg(&lk->locked, 1) != 0)
    ;

  // 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 after the lock is acquired.
  __sync_synchronize();

  // Record info about lock acquisition for debugging.
  lk->cpu = mycpu();
  getcallerpcs(&lk, lk->pcs);
}

acquire() 中首先通过 pushcli() 关闭中断并记录关闭中断次数：获取当前 eflags 中 IF 位，并保存到 mycpu()->intena 中；随后增加中断次数 mycpu()->ncli

一般而言需要先通过判断锁的状态然后再上锁，由于上面两个步骤不是同时进行，假设线程 P 执行到 while 循环，锁没被占用，此时在没改变锁状态下发生调度切换，线程 Q 也执行到 while 循环，也可以占用锁，会造成两个线程获取同一个锁的情况，所以通过 xchg() 保证原子操作实现锁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

static inline uint
xchg(volatile uint *addr, uint newval)
{
  uint result;

  // The + in "+m" denotes a read-modify-write operand.
  asm volatile("lock; xchgl %0, %1" :
               "+m" (*addr), "=a" (result) :
               "1" (newval) :
               "cc");
  return result;
}

__sync_synchronize() 主要为了避免编译器把指令顺序打乱，禁止编译器乱序内存操作， Memory Barriers: a Hardware View for Software Hackers ， Linux Memory Barriers 有所介绍

getcallerpcs() 用于为调试而保存调用栈的信息

reqlease()

release() 主要用于释放锁，主要通过 asm volatile("movl $0, %0" : "+m" (lk->locked) : ); 解锁，这句话能原子操作

holding() 用于检查处理器是否在操作锁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

  lk->pcs[0] = 0;
  lk->cpu = 0;

  // Tell the C compiler and the processor to not move loads or stores
  // past this point, to ensure that all the stores in the critical
  // section are visible to other cores before the lock is released.
  // Both the C compiler and the hardware may re-order loads and
  // stores; __sync_synchronize() tells them both not to.
  __sync_synchronize();

  // Release the lock, equivalent to lk->locked = 0.
  // This code can't use a C assignment, since it might
  // not be atomic. A real OS would use C atomics here.
  asm volatile("movl $0, %0" : "+m" (lk->locked) : );

  popcli();
}

Don’t do this

1
2
3
4

struct spinlock lk;
initlock(&lk, "test lock");
acquire(&lk);
acquire(&lk);

这段代码会导致发生死锁，处理器一直处于死循环状态

Interrupts in ide.c

根据要求修改 ide.c:iderw()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//PAGEBREAK!
// Sync buf with disk.
// If B_DIRTY is set, write buf to disk, clear B_DIRTY, set B_VALID.
// Else if B_VALID is not set, read buf from disk, set B_VALID.
void
iderw(struct buf *b)
{
  struct buf **pp;

  if(!holdingsleep(&b->lock))
    panic("iderw: buf not locked");
  if((b->flags & (B_VALID|B_DIRTY)) == B_VALID)
    panic("iderw: nothing to do");
  if(b->dev != 0 && !havedisk1)
    panic("iderw: ide disk 1 not present");

  acquire(&idelock);  //DOC:acquire-lock

  sti();

  // Append b to idequeue.
  b->qnext = 0;
  for(pp=&idequeue; *pp; pp=&(*pp)->qnext)  //DOC:insert-queue
    ;
  *pp = b;

  // Start disk if necessary.
  if(idequeue == b)
    idestart(b);

  // Wait for request to finish.
  while((b->flags & (B_VALID|B_DIRTY)) != B_VALID){
    sleep(b, &idelock);
  }

  cli();

  release(&idelock);
}

运行后获得如下结果

sched locks

sched locks 可在 proc.c:sched() 中找到，主要是 mycpu()->ncli != 1 导致 panic ， ncli 记录中断次数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Enter scheduler.  Must hold only ptable.lock
// and have changed proc->state. Saves and restores
// intena because intena is a property of this
// kernel thread, not this CPU. It should
// be proc->intena and proc->ncli, but that would
// break in the few places where a lock is held but
// there's no process.
void
sched(void)
{
  int intena;
  struct proc *p = myproc();

  if(!holding(&ptable.lock))
    panic("sched ptable.lock");
  if(mycpu()->ncli != 1)
    panic("sched locks");
  if(p->state == RUNNING)
    panic("sched running");
  if(readeflags()&FL_IF)
    panic("sched interruptible");
  intena = mycpu()->intena;
  swtch(&p->context, mycpu()->scheduler);
  mycpu()->intena = intena;
}
1
2
3
4
5

cpu1: starting 1
cpu0: starting 0
sb: size 1000 nblocks 941 ninodes 200 nlog 30 logstart 2 inodestart 32 bmap start 58
lapicid 1: panic: sched locks
80103c01 80103d72 801058c3 801056fc 801021f7 80100183 801016e7 80100a4d 801053c0 80104899

通过 panic 提供的 eip 查看调用过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

80103c01 sched() -> panic()
80103d72 yield() -> sched()
801058c3 trap() -> yield()
801056fc alltraps() -> trap()
801021f7 sti() -> iderw()
80100183 bread() -> iderw()
801016e7 ilock() -> bread()
80100a4d exec() -> readi()
801053c0 sys_exec() -> exec()
80104899 syscall() -> syscalls()

panic 出现在 trap() ，而 trap() 调用了 yield()

1
2
3
4
5
6
7
8
9

// Give up the CPU for one scheduling round.
void
yield(void)
{
  acquire(&ptable.lock);  //DOC: yieldlock
  myproc()->state = RUNNABLE;
  sched();
  release(&ptable.lock);
}

而通过上面的流程知道，在调用 iderw() ， acquire() 之后， release() 之前，被 tick 中断，随后进入 yield() ，而 yield() 又进行了 acquire() ，此时 mycpu()->ncli == 2

acquire

另一个情况是 acquire() ，当一个 proc 重复获取锁时会触发

1
2

if(holding(lk))
  panic("acquire");
1
2
3
4
5

cpu1: starting 1
cpu0: starting 0
sb: size 1000 nblocks 941 ninodes 200 nlog 30 logstart 2 inodestart 32 bmap start 58
lapicid 1: panic: acquire
80104421 801020a3 80105a15 801056fc 80100183 801016e7 80101d31 80101f03 80100a37 801053c0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

80104421 acquire() -> panic()
801020a3 ideintr() -> acquire()
80105a15 rcr2() -> ideintr()
801056fc alltrap() -> trap()
80100183 bread() -> iderw()
801016e7 ilock() -> bread()
80101d31 namex() -> ilock()
80101f03 namei() -> namex()
80100a37 exec() -> namei()
801053c0 sys_exec() -> exec()

从上面记录得知， iderw() 和 ideintr() 都调用了 acquire() 而且是对于同一个锁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Interrupt handler.
void
ideintr(void)
{
  struct buf *b;

  // First queued buffer is the active request.
  acquire(&idelock);

  if((b = idequeue) == 0){
    release(&idelock);
    return;
  }
  idequeue = b->qnext;

  // Read data if needed.
  if(!(b->flags & B_DIRTY) && idewait(1) >= 0)
    insl(0x1f0, b->data, BSIZE/4);

  // Wake process waiting for this buf.
  b->flags |= B_VALID;
  b->flags &= ~B_DIRTY;
  wakeup(b);

  // Start disk on next buf in queue.
  if(idequeue != 0)
    idestart(idequeue);

  release(&idelock);
}

Interrupts in file.c

获取 file_table_lock() 锁在打开中断后没有 panic 的原因：中断发生后没有再次使用共享数据

xv6 lock implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

  lk->pcs[0] = 0;
  lk->cpu = 0;

  __sync_synchronize();

  asm volatile("movl $0, %0" : "+m" (lk->locked) : );

  popcli();
}

lk->pcs[0] = 0; lk->cpu = 0; 在释放锁前面的原因：

若在释放锁后面，会发生：

  1. 锁释放， lk->pcs[0] 跟 lk->cpu 未清除
  2. 另一个 CPU 尝试获取锁并成功，设置 lk->pcs[0] 跟 lk->cpu
  3. 当前 CPU 清除 lk->pcs[0] 跟 lk->cpu

从而导致锁的信息不正确