Mit6.828 Day24 HW7 xv6 locks

Mit6.828 Day24 HW7 xv6 locks

摘要: MIT6.828 HW7 xv6 locks

0x01 写在前面

照着schedule来看,今天需要完成两项任务:

1)阅读完xv6 book的locking章节;

2)完成HW7 xv6 locks。

这个HW完成后,就是Lab3 Part B的due了,话不多说,直接开搞。

0x02 Chapter4 Locking

Race conditions

条件竞争指的是多个进程(CPU、线程等)同时对一块数据进行读写时造成的数据的读取错误(读到的不是最终的值)或覆写错误(后来进程覆写了之前进程数据导致数据丢失)。

要实现互斥(mutual exclusion)

多种方法可以避免,xv6使用的是锁(lock)

在上锁和释放锁之前的代码区域被称为临界区(critical section)

上锁本质上保护的是数据结构中的不变量(invariants)

Code: Locks

自旋锁(spin-locks) 睡锁(sleep-locks)

x86通过循环调用xchg来实现自旋锁的原子性操作

acquire函数过后,会有一个特殊字段用以保存拿锁者的信息

release函数时acquire函数的逆操作,释放锁

Code: Using locks

什么时候用锁:

1)当一个数据能够同时被多个CPU读写时;

2)当一个不变量跟多个内存地址相关联时。

Deadlock and lock ordering

为了避免死锁,所有对锁的请求必须有着相同的顺序

xv6里面存在着许多锁顺序链

Interrupt handlers

中断可能导致死锁

xv6处理方法:当自旋锁被一个中断处理器使用时,禁用中断拿锁。

Instruction and memory ordering

这段说实话没有体会清楚

先mark一下,这节讲的其实是编译器在处理代码时为了提升效率而做的代码执行顺序的调换。但这可能导致上面的问题,为了处理这个问题,xv6使用_sync_synchronize()使得编译器和CPU不要重新对代码执行的顺序排序。

Sleep locks

睡锁是一种能够在上锁后放任CPU去做其他工作的锁

它允许中断使用

不允许中断处理器使用睡锁

不允许在自旋锁中使用睡锁

常用于文件系统中

Limitations of locks

Real World

对锁编程是困难的

0x03 Homework: xv6 locking

本次的HW会探索中断和锁之间的交互。

Dont do this

理解执行以下代码会发生什么:

1
2
3
4
struct spinlock lk;
initlock(&lk, "test lock");
acquire(&lk);
acquire(&lk);

首先,我们打开spinlock.c这个文件,得到两个函数的代码如下:

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
void
initlock(struct spinlock *lk, char *name)
{
lk->name = name;
lk->locked = 0;
lk->cpu = 0;
}

// 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);
}

可以看到,首先声明了spinlock结构体,然后初始化结构体名字为test lock,再后调用了两次acquire()函数。来看看acquire这个函数:

通过注释,我们可以将这段代码和刚刚所看的xv6 book中的知识串联起来。读完后我们可以对这段代码作出解释了:

在第一次调用acquire的时候分配到了lk锁,而后进入while循环,再次调用acquire请求lk锁时由于锁以及被分配而panic一个“acquire”并进入while循环。

Interrupts in ide.c

晕死,这小结原本是让我们在ide.c的iderw函数的acquire后调用sti()和在release前调用cli()。使用后开启的时候回panic,我开了十几次终于碰到了:

根据打印出来的eip路径结合kernel.asm可以很轻松地找到具体的调用panic路径

panic<-acquire<-ideintr<-trap<-iderw<-bread<-initlog<-trapret

可以发现,在执行iderw的时候由于在acquire后调用了sti()使得中断在自旋锁中被允许,而后trap()出现进入中断最后导致递归锁。

Interrupts in file.c

这里对file.c中的对应函数做相同的操作,但是不会panic。参考他人的原因如下:

file_table_lock保护的临界区足够短,时钟中断还来不及触发。如果在该临界区中加一段长时间的while循环,就会panic。

xv6 lock implementation

release()函数中,lk->pcs[0]和lk->cpu的清除工作必须在lk->locked置零前进行,这是因为如果在清除lk->locked之后清除,那么就会有一小段空隙,在这个空隙里调度到其他等待锁的程序,就会成功获得这个锁,然后设置lk->pcs[]和lk->cpu;此时再调度到原来的进程,原来的进程继续将lk->pcs[]和lk->cpu清除,就会导致出错。

0x03 总结

这次的HW没什么代码量,主要是理解锁机制。


评论