XV6学习(10)锁

在包括XV6的绝大部分操作系统都是多个任务交错执行的。交错的一个原因是多核硬件:多核计算机的多个CPU核心独立执行计算,如XV6的RISC-V处理器。多个CPU核心共享物理内存,XV6利用这种共享来维护所有核心都会读写的数据结构。而这种共享会导致一个CPU在读取某数据结构时,可能有另一个CPU正在对此数据进行更新;或者多个CPU同时更新同一个数据。如果不对这种并行访问进行小心的设计,就可能会导致错误的结果产生或者损坏数据。即使是单核处理器,内核也可能会在多个线程之间进行切换,导致它们交错运行。最后,如果中断在错误的时间发生,设备中断处理程序也可能会对数据造成损坏。并发一词就是指由于多核并行、线程切换或中断,导致多个指令流交错执行。

内核中充满了被并发访问的数据。如两个CPU可以同时调用kalloc,从而同时从空闲链表的中弹出空闲页。内核设计者必须允许大量并发,因为并发可以提高系统的性能和响应速度。然而,系统设计者需要耗费很多精力来保证并发的正确性。有很多种方法可以写出正确的代码,其中有一些比其他更容易推理。针对并发的正确性以及支持它们的抽象的策略被称为并发控制技术。

XV6基于不用的情况使用了多种并发控制技术,并且还有更多技术可以使用。其中一个广泛使用的技术就是锁。锁可以提供互斥性,保证同一时间只有一个CPU能够持有锁。如果程序员将共享数据与锁进行关联,在代码使用这些数据时就必须持有相应的锁,这样就可以保证同一时间只有一个CPU能使用该数据。尽管锁是一种容易理解的并发控制机制,但锁的缺点是其会降低性能,因为锁将并发操作串行化。

竞争条件

假如两个进程在不同的CPU上同时调用wait函数释放子进程内存,导致在每个CPU上,内核都会调用kfree来释放子进程的页面。内核维护了一个空闲页面链表,kalloc会pop一个页面,而kfree会push一个页面。为了最佳的性能,我们希望两个父进程的kfree能够并行执行而不需要等待另一个,但是在XV6的kfree实现中是不正确的。

一种竞争条件是指一个内存位置被并发访问,并且至少一个访问是写入。竞争通常是bug的信号,要么更新发生丢失,要么读取到不完整的数据更新。竞争的结果取决于两个CPU执行的实际时间以及对内存的操作如何被内存系统排序,这些会使得竞争导致的bug难以复现和调试。例如插入print语句来调试可能会改变执行的时间从而使得竞争消失。

struct element *list = 0; struct lock listlock; void push(int data) { struct element *l; l = malloc(sizeof *l); l->data = data; acquire(&listlock); l->next = list; list = l; release(&listlock); }

当我们说锁保护了数据,实际的意思是锁保护了应用在数据上的一系列不变性。一个操作的正确性取决于操作开始时的不变性是否正确。操作可能会暂时违反不变性,但必须在在操作结束前恢复其不变性。例如对于链表,不变性时指头指针指向第一个元素,且每一个元素的next域指向下一个元素。push操作的l->next = list会暂时破坏其不变性,使得头指针并不是指向第一个元素。竞争条件发生因为在另一个CPU上的操作依赖于不变性,而这被暂时破坏了。锁的使用可以保证在数据结构上一次只有一个CPU在临界区执行,因此不会有CPU在不变性被破坏时执行操作。

可以认为锁将并发的临界区串行化使其一次只能执行一个,从而保护了不变性。也可以认为被锁保护的临界区对于其他临界区来说是原子性的,因此每一个都只能看见一系列先前临界区的完整修改,而永远不会看见部分修改。

尽管锁的正确使用可以使错误代码变正确,但锁也限制了性能。例如当两个进程同时调用kfree,锁会将两个调用串行化,将它们在不同的CPU上运行就不会获得收益。在内核设计中一个大的挑战就是避免锁争用。XV6在这方面做的很少,但是复杂的内核会通过特殊的方法组织数据结构和算法来避免锁争用。例如内核会为每个内核维护一个独立的空闲内存链表,只有当当前CPU的链表为空时才会去请求其他CPU的链表来获取空闲内存。而其他的争用可能需要更加复杂的设计。

锁的位置同样对性能影响很大。例如在push中可以将acquire放在更加前面,但这就会降低性能,因为malloc的调用也被串行化。

代码:锁

XV6中有两种锁:自旋锁和睡眠锁。自旋锁定义为struct spinlock,最重要的域就是locked,1代表被持有而0代表未被持有。理论上xv6可以通过下列代码来上锁:

void acquire(struct spinlock *lk) // does not work! { for(;;) { if(lk->locked == 0) { lk->locked = 1; break; } } }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpyzgp.html