作业地址
锁的实现
锁的结构
阅读 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;
在释放锁前面的原因:
若在释放锁后面,会发生:
- 锁释放,
lk->pcs[0]
跟 lk->cpu
未清除
- 另一个 CPU 尝试获取锁并成功,设置
lk->pcs[0]
跟 lk->cpu
- 当前 CPU 清除
lk->pcs[0]
跟 lk->cpu
从而导致锁的信息不正确