然而不幸地是在多处理器上这种实现不会达到互斥。当两个CPU同时对locked进行读取并且结果为0时,它们都会获得这个锁,而这就会违反互斥的性质。因此我们需要第5第6行的执行原子化。
由于锁的广泛使用,多核处理器通常会提供该原子指令。在RISC-V中为amoswap r, a,该指令会交换r和a的值。该指令是原子性的,其会通过特殊硬件来防止其他CPU在读写时使用该内存地址。
XV6的acquire使用可移植的C库函数__sync_lock_test_and_set,而其在底层是使用amoswap实现的。函数返回值是locked的旧值。acquire函数在循环中不停(自旋)调用swap直到其获得锁。每次循环将1swap到locked中,并判断旧值是否为0,为0就说明获取到了锁,同时swap也将locked设置为了1。如果旧值为1,说明其他CPU持有锁,而swap也并没有改变locked的值。
当获取到了锁,acquire就会为了调试而记录获取锁的CPU。lk->cpu域是被锁保护的并且必须在获取锁后才能被改变。
release函数则与acquire相反;该函数清空cpu域并释放锁。理论上释放只需要将locked域置0。而C语言标准运行编译器使用多存储指令来实现赋值,因此一条赋值语句可能不是原子的。因此,release使用C库函数__sync_lock_release来进行原子性赋值。该函数底层也是通过amoswap指令实现。
代码:使用锁XV6在许多地方都使用锁来避免竞争条件。kalloc和kfree是一个很好的例子。使用锁的一个难点是决定要使用多少锁以及每个锁要保护哪些数据和不变性。这里有几个基本原则:首先当一个变量在被一个CPU写入时,有其他CPU可以对其读写时,应该使用锁来避免两个操作重叠;第二,记住锁所保护的不变性,如果一个不变性涉及多个内存位置,则所有的位置都需要被一个单独的锁来保护,从而保证不变性。
上述只说了锁什么时候是必要的而没有锁什么时候是不必须的,而减少锁的数量对效率来说是很重要的,因为锁减少了并行。如果并行不是必须的,那么可以只使用一个线程从而不必考虑锁的问题。简单内核可以在多处理器上只使用一个锁,当进入内核态时获取锁,离开时释放锁(尽管系统调用如管道的读和wait将会产生问题)。很多单处理器系统使用这种方法来在多处理器上运行,有的时候被成为“大内核锁”。但是,这种方法破坏了并行性:一次只有一个CPU可以在内核中执行。如果内核要进行任何重计算任务,使用一系列的锁会更加高效,内核可以同时在多个CPU上运行。
作为粗粒度锁的例子,XV6的kalloc.c分配器只有一个被一个锁保护的空闲链表。如果多个进程在不同CPU上同时尝试申请页面,那么每一个都需要在acquire中自旋等待。自旋是在做无用功从而降低了性能。如果锁的争用浪费了大量时间,那么可能就要通过改变分配器的设计来提高性能,使用多个空闲链表,每个链表单独持有锁,从而允许真正的并行分配。
作为细粒度锁的例子,XV6对于每个文件都有一个单独的锁,因此操作不同文件的进程可以无需等待其他的文件的锁。文件锁模式的粒度可以变得更加的细,如果希望进程同时写相同文件的不同区域。总而言之,锁的粒度需要由性能度量以及锁的复杂性的考虑来决定。
XV6中使用的锁如下表所示:
lock Descriptionbcache.lock Protects allocation of block buffer cache entries
cons.lock Serializes access to console hardware, avoids intermixed output
ftable.lock Serializes allocation of a struct file in file table
icache.lock Protects allocation of inode cache entries
vdisk_lock Serializes access to disk hardware and queue of DMA descriptors
kmem.lock Serializes allocation of memory
log.lock Serializes operations on the transaction log
pipe’s pi->lock Serializes operations on each pipe
pid_lock Serializes increments of next_pid
proc’s p->lock Serializes changes to process’s state
tickslock Serializes operations on the ticks counter
inode’s ip->lock Serializes operations on each inode and its content
buf’s b->lock Serializes operations on each block buffer
死锁和锁顺序