理解xv6——4.9 真实世界（播放真实世界）

Concurrency primitives and parallel programming are active areas of research, because programming with locks is still challenging. It is best to use locks as the base for higher-level constructs like synchronized queues, although xv6 does not do this. If you program with locks, it is wise to use a tool that attempts to identify race conditions, because it is easy to miss an invariant that requires a lock.

并发原语和并行编程一直是研究的活跃领域，因为用锁编程仍然具有挑战性。最好在高级别的结构中使用锁，如同步队列，尽管xv6没有这样做。如果你的程序需要锁，明智的做法是使用一个可以试图确定竞态条件的工具，因为很容易错过需要锁的不变量。

most operating systems support POSIX threads (Pthreads), which allow a user process to have several threads running concurrently on different processors. Pthreads has support for user-level locks, barriers, etc. Supporting Pthreads requires support from the operating system.

For example, it should be the case that if one pthread blocks in a system call, another pthread of the same process should be able to run on that processor. As another example, if a pthread changes its process’s address space (e.g., grow or shrink it), the kernel must arrange that other processors that run threads of the same process update their hardware page tables to reflect the change in the address space.

On the x86, this involves shooting down the Translation Look-aside Buffer (TLB) of other processors using inter-processor interrupts (IPIs).

大多数操作系统支持POSIX线程（Pthreads），其允许用户进程具有在不同处理器上同时运行若干线程。Pthreads支持用户级锁、屏障等。支持Pthreads需要操作系统的支持。

例如，如果一个pthread在系统调用中阻塞，同一进程的另一个pthread应该能够在该处理器上运行。作为另一示例，如果pthread改变其进程的地址空间（例如，增长或收缩它），内核必须安排运行同一进程的线程的其他处理器更新它们的硬件页表以反映地址空间的变化。

在x86上，这涉及到使用处理器间中断（IPI）关闭其他处理器的页表缓冲区（TLB）。

It is possible to implement locks without atomic instructions, but it is expensive, and most operating systems use atomic instructions.不使用原子指令也可以实现锁，但代价很高，而且大多数操作系统都使用原子指令。

Locks can be expensive if many processors try to acquire the same lock at the same time. If one processor has a lock cached in its local cache, and another processor must acquire the lock, then the atomic instruction to update the cache line that holds the lock must move the line from the one processor’s cache to the other processor’s cache, and perhaps invalidate any other copies of the cache line. Fetching a cache line from another processor’s cache can be orders of magnitude more expensive than fetching a line from a local cache.

如果许多处理器试图同时获取同一个锁，那么锁的开销可能会很大。如果一个处理器在其本地高速缓存中高速缓存有锁，并且另一个处理器必须获取该锁，则更新持有该锁的该高速缓存行的原子指令必须将该行从一个处理器的高速缓存移动到另一个处理器的高速缓存，并且可能使该该高速缓存行的任何其他副本无效。从另一个处理器的高速缓存中获取高速缓存行可能比从本地高速缓存中获取行要昂贵几个数量级。

To avoid the expenses associated with locks, many operating systems use lock-free data structures and algorithms. For example, it is possible to implement a linked list like the one in the beginning of the chapter that requires no locks during list searches, and one atomic instruction to insert an item in a list.

Lock-free programming is more complicated, however, than programming locks; for example, one must worry about instruction and memory reordering. Programming with locks is already hard, so xv6 avoids the additional complexity of lock-free programming.

为了避免与锁相关的开销，许多操作系统使用无锁数据结构和算法。例如，可以实现一个类似于本章开头的链表，它在列表搜索期间不需要锁，只需要一个原子指令就可以在列表中插入一个项。然而，无锁编程比锁编程更复杂;例如，必须考虑指令和内存的重新排序。使用锁编程已经很困难了，所以xv6避免了无锁编程的额外复杂性。