
   \chapter{Concurrency revisited}   
    \label{CH:LOCK2}     

同时获得良好的并行性能、并发性下的正确性以及可理解的代码是内核设计中的一大挑战。直接使用锁是实现正确性的最佳途径，但并不总是可行。本章重点介绍 xv6 被迫以相关方式使用锁的示例，以及 xv6 使用类似锁的技术但不使用锁的示例。  

   \section{锁模式  }     

缓存的项目通常很难锁定。例如，文件系统的块缓存    \lineref{kernel/bio.c:/^struct/}    存储最多  {    \tt    NBUF   }  磁盘块的副本。给定的磁盘块在缓存中至多有一个副本至关重要；否则，不同的进程可能会对本应是同一块的不同副本进行冲突的更改。每个缓存块都存储在  {    \tt    结构体 buf   }  中
    \lineref{kernel/buf.h:1}    。  {    \tt    结构体 buf   }  有一个锁定字段，有助于确保一次只有一个进程使用给定的磁盘块。但是，该锁还不够：如果缓存中根本不存在某个块，并且两个进程想要同时使用它怎么办？没有  {    \tt    结构体 buf   } （因为该块尚未缓存），因此没有什么可以锁定。 Xv6 通过将附加锁 (  {    \tt    bcache.lock   }  ) 与缓存块的身份集相关联来处理这种情况。需要检查块是否已缓存（例如  {    \tt    bget   }     \lineref{kernel/bio.c:/^bget/}    ）或更改缓存块集的代码必须保存  {    \tt    bcache.lock   }  ；在该代码找到所需的块和  {    \tt    结构体 buf   }  后，它可以释放  {    \tt    bcache.lock   }  并仅锁定特定块。这是一种常见模式：一组项目一把锁，每个项目一把锁。

通常，获取锁的同一函数也会释放它。但更精确的看待事物的方法是，在必须表现为原子的序列开始时获取锁，并在该序列结束时释放锁。如果序列在不同的函数、不同的线程或不同的 CPU 上开始和结束，则锁获取和释放必须执行相同的操作。锁的作用是强制其他用途等待，而不是将一条数据固定到特定的代理。一个例子是  {    \tt    yield   }  中的  {    \tt    acquire   } 
   \lineref{kernel/proc.c:/^yield/}    ，在调度线程中释放，而不是在获取过程中释放。另一个例子是
  {    \tt    acquiresleep   }   {    \tt    ilock   }     \lineref{kernel/fs.c:/^ilock/}    ；这段代码经常在读磁盘时休眠；它可能会在不同的CPU上唤醒，这意味着锁可能会在不同的CPU上获取和释放。  

释放受嵌入在对象中的锁保护的对象是一件微妙的事情，因为拥有锁并不足以保证释放是正确的。当其他线程在  {    \tt    acquire   }  中等待使用该对象时，就会出现问题；释放对象会隐式释放嵌入的锁，这将导致等待线程发生故障。一种解决方案是跟踪存在多少个对该对象的引用，以便仅在最后一个引用消失时才释放该对象。参见  {    \tt    pipeclose   } 
 以    \lineref{kernel/pipe.c:/^pipeclose/}    为例；
  {    \tt    pi->readopen   }  和  {    \tt    pi->writeopen   }  跟踪管道是否有文件描述符引用它。  

通常人们会看到对一组相关项的读写序列周围的锁；这些锁确保其他线程只能看到已完成的更新序列（只要它们也锁定）。如果更新是对单个共享变量的简单写入，那么情况又如何呢？例如，
    \texttt{setkilled}    和    \texttt{killed}   
    \lineref{kernel/proc.c:/^setkilled/}    锁定其简单用途
    \lstinline{p->killed}    。如果没有锁，一个线程可以写
    \lstinline{p->killed}    同时另一个线程读取它。这是一个    \indextextx{race}    ，C 语言规范表示竞赛会产生    \indextext{undefined behavior}    ，这意味着程序可能会崩溃或产生不正确的结果    \footnote{   \url{https://en.cppreference.com/w/c/language/memory_model}    中的“线程和数据竞争”  }    。锁可以防止竞争并避免未定义的行为。  

竞争可能破坏程序的原因之一是，如果没有锁或等效结构，编译器可能会生成以与原始 C 代码完全不同的方式读取和写入内存的机器代码。例如，线程调用的机器码
    \texttt{killed}    可以将    \lstinline{p->killed}    复制到寄存器并仅读取该缓存值；这意味着线程可能永远不会看到任何写入
    \lstinline{p->killed}    。锁可以防止此类缓存。  

   \section{类似锁的模式  }     

在许多地方，xv6 以类似锁的方式使用引用计数或标志来指示对象已分配且不应释放或重复使用。进程的  {    \tt    p->state   }  以这种方式起作用， {    \tt    file   }  、  {    \tt    inode   }  和  {    \tt    buf   }  结构中的引用计数也是如此。虽然在每种情况下锁都会保护标志或引用计数，但后者可以防止对象过早释放。  

文件系统使用 {    \tt    struct inode   } 引用计数作为一种可由多个进程持有的共享锁，以避免代码使用普通锁时出现的死锁。例如， {    \tt    namex   }     \lineref{kernel/fs.c}{652}    中的循环依次锁定每个路径名组件指定的目录。但是，  {    \tt    namex   }  必须在循环结束时释放每个锁，因为如果它持有多个锁，如果路径名包含点（例如  {    \tt    a/./b   }  ），它可能会与自身发生死锁。它还可能因涉及目录和  {    \tt    ..   }  的并发查找而死锁。正如 Chapter~\ref{CH:FS}    所解释的，解决方案是循环将目录 inode 传递到下一次迭代，其引用计数递增，但不锁定。  

某些数据项在不同时间受到不同机制的保护，并且有时可能通过 xv6 代码的结构而不是通过显式锁来隐式地防止并发访问。例如，当物理页空闲时，它受到    \texttt{kmem.lock}    的保护
\lineref{kernel/kalloc.c:/^. kmem;/}    。如果该页随后分配为管道    \lineref{kernel/pipe.c:/^pipealloc/}    ，则它会受到不同锁（嵌入式    \lstinline{pi->lock}    ）的保护。如果该页被重新分配给新进程的用户内存，则它根本不受锁保护。相反，分配器不会将该页面分配给任何其他进程（直到它被释放），这一事实可以保护它免受并发访问。新进程内存的所有权很复杂：首先父进程在  {    \tt    分叉   }  中分配和操作它，然后子进程使用它，并且（子进程退出后）父进程再次拥有内存并将其传递给  {    \tt    kfree   }  。这里有两个教训：数据对象可以在其生命周期的不同点以不同的方式防止并发，并且保护可以采取隐式结构而不是显式锁的形式。  

最后一个类似锁的示例是需要禁用对  {    \tt    mycpu()   }     \lineref{kernel/proc.c:/^myproc/}    调用的中断。禁用中断会导致调用代码相对于计时器中断而言是原子的，这可能会强制进行上下文切换，从而将进程移动到不同的 CPU。  

   \section{根本没有锁  }     

有一些地方 xv6 完全不加锁地共享可变数据。其中之一是自旋锁的实现，尽管人们可以将 RISC-V 原子指令视为依赖于硬件中实现的锁。另一个是 {    \tt    main.c   } 中的 {    \tt    started   } 变量
\lineref{kernel/main.c:/^volatile/}     ，用于防止其他 CPU 运行，直到 CPU 0 完成初始化 xv6； {    \tt    volatile   }  确保编译器实际生成加载和存储指令。  

Xv6 包含一个 CPU 或线程写入一些数据，而另一个 CPU 或线程读取数据的情况，但没有专门用于保护该数据的特定锁。例如，在  {    \tt    fork   }  中，父进程写入子进程的用户内存页面，而子进程（不同的线程，可能位于不同的 CPU 上）读取这些页面； nolock 显式保护这些页面。严格来说，这不是一个锁定问题，因为子进程直到父进程完成写入后才开始执行。这是一个潜在的内存排序问题（请参阅第    \ref{CH:LOCK}    章），因为如果没有内存屏障，就没有理由期望一个 CPU 看到另一个 CPU 的写入。但是，由于父进程释放锁，而子进程在启动时获取锁，因此  {    \tt    acquire   }  和  {    \tt    release   }  中的内存屏障确保子进程的 CPU 可以看到父进程的写入。  

   \section{并行性  }     

锁定主要是为了正确性而抑制并行性。由于性能也很重要，因此内核设计者通常必须考虑如何以既实现正确性又允许并行性的方式使用锁。虽然 xv6 不是针对高性能而系统设计的，但仍然值得考虑哪些 xv6 操作可以并行执行，以及哪些操作可能会发生锁冲突。  

xv6 中的管道是相当好的并行性的一个例子。每个管道都有自己的锁，这样不同的进程可以在不同的CPU上并行读写不同的管道。然而，对于给定的管道，写入者和读取者必须等待对方释放锁；他们不能同时读/写同一个管道。还有一种情况是，从空管道读取（或向满管道写入）必须阻塞，但这不是由于锁定方案造成的。  

上下文切换是一个更复杂的例子。两个内核线程（各自在自己的 CPU 上执行）可以同时调用  {    \tt    yield   }  、  {    \tt    sched   }  和  {    \tt    swtch   }  ，并且这些调用将并行执行。线程各自持有一个锁，但它们是不同的锁，因此它们不必互相等待。然而，一旦进入  {    \tt    scheduler   }  ，两个 CPU 在搜索进程表（即  {    \tt    RUNNABLE   }  ）时可能会发生锁冲突。也就是说，xv6 很可能在上下文切换期间从多个 CPU 中获得性能优势，但可能没有那么多。  

另一个示例是从不同 CPU 上的不同进程并发调用  {    \tt    fork   } 。对于  {    \tt    pid\_lock   }  和  {    \tt    kmem.lock   }  ，以及在进程表中搜索  {    \tt    UNUSED   }  进程所需的每进程锁，这些调用可能必须相互等待。另一方面，两个分叉进程可以完全并行地复制用户内存页面和格式化页表页面。  

上述每个示例中的锁定方案在某些情况下都会牺牲并行性能。在每种情况下，都可以使用更精细的设计来获得更多的并行性。是否值得取决于细节：相关操作被调用的频率、代码在持有竞争锁的情况下花费了多长时间、有多少个 CPU 可能同时运行冲突的操作、代码的其他部分是否是更具限制性的瓶颈。很难猜测给定的锁定方案是否会导致性能问题，或者新的设计是否明显更好，因此通常需要对实际工作负载进行测量。  

   \section{练习  }     

   \begin{enumerate}


   \item   修改 xv6 的管道实现，以允许对同一管道的读取和写入在不同内核上并行进行。   \item   修改xv6的   \texttt{scheduler()}   以减少不同核心同时寻找可运行进程时的锁争用。   \item   消除 xv6 的    \texttt{fork()}    中的一些序列化。  \end{enumerate}     


