2.6 良性数据争用

为了获得更好的性能，某些多线程应用程序会特意允许数据争用。良性数据争用是指特意允许的数据争用，其存在不会影响程序正确性。以下示例将说明良性数据争用。

除了良性数据争用之外，有很大一类的应用程序允许数据争用，因为它们依赖于锁无关 (lock-free) 和等待无关 (wait-free) 算法，不过很难正确设计这些算法。线程分析器可以帮助确定这些应用程序中的数据争用位置。

2.6.1 用于查找质数的程序

prime_omp.c 中的线程通过执行函数 is_prime() 来检查某个整数是否为质数。

    16  int is_prime(int v)
    17  {
    18      int i;
    19      int bound = floor(sqrt(v)) + 1;
    20
    21      for (i = 2; i < bound; i++) {
    22          /* no need to check against known composites */
    23          if (!pflag[i])
    24              continue;
    25          if (v % i == 0) {
    26              pflag[v] = 0;
    27              return 0;
    28          }
    29      }
    30      return (v > 1);
    31  }

线程分析器会报告第 26 行中对 pflag[ ] 的写入与第 23 行中对 pflag[ ] 的读取之间存在数据争用。但是，此数据争用是良性的，因为它不会影响最终结果的正确性。在第 23 行，线程将检查对于给定的 i 值，pflag[i] 是否等于 0。如果 pflag[i] 等于 0，则表明 i 是已知的合数（换句话说，知道 i 不是质数）。因此，无需检查 v 是否可以被 i 整除；只需检查 v 是否可以被某个质数整除。因此，如果 pflag[i] 等于 0，该线程会继续处理 i 的下一个值。如果 pflag[i] 不等于 0 并且 v 可以被 i 整除，该线程会将 0 分配给 pflag[v] 以表明 v 不是质数。

从正确性方面来说，多个线程检查同一 pflag[ ] 元素并同时向其写入是可以的。pflag[ ] 元素的初始值为 1。当线程更新该元素时，它们会为该元素分配值 0。也就是说，这些线程会在该元素的同一内存字节的同一位中存储 0。在当前的体系结构中，可以放心地认为这些存储是原子操作。这意味着，某个线程读取该元素时，读取的值要么为 1，要么为 0。如果某个线程在给定的 pflag[ ] 元素（第 23 行）被分配值 0 之前对该元素进行检查，则该线程会执行第 25–28 行。在此期间，如果另一个线程也将 0 分配给同一 pflag[ ] 元素（第 26 行），最终结果不变。在本质上，这意味着第一个线程不必要地执行了第 25–28 行，但最终结果是相同的。

2.6.2 用于检验数组值类型的程序

一组线程同时调用 check_bad_array() 以检查数组 data_array 中是否存在任何“错误”元素。每个线程检查数组的不同部分。如果线程发现某个元素有错误，它会将全局共享变量 is_bad 的值设置为真。

20  volatile int is_bad = 0;
 ...

 100  /* 
 101   * Each thread checks its assigned portion of data_array, and sets 
 102   * the global flag is_bad to 1 once it finds a bad data element.
 103   */
 104  void check_bad_array(volatile data_t *data_array, unsigned int thread_id)    
 105  {
 106     int i;
 107     for (i=my_start(thread_id); i<my_end(thread_id); i++) {
 108          if (is_bad) 
 109              return;
 110          else {
 111              if (is_bad_element(data_array[i])) { 
 112                  is_bad = 1;
 113                  return;
 114              }
 115          }
 116     }
 117  }

第 108 行中对 is_bad 的读取与第 112 行中对 is_bad 的写入之间存在数据争用。但是，该数据争用不影响最终结果的正确性。

is_bad 的初始值为 0。当线程更新 is_bad 时，它们会为其分配值 1。也就是说，这些线程会在 is_bad 的同一内存字节的同一位中存储 1。在当前的体系结构中，可以放心地认为这些存储是原子操作。因此，某个线程读取 is_bad 时，读取的值要么为 0，要么为 1。如果某个线程在 is_bad（第 108 行）被分配值 1 之前对其进行检查，则该线程会继续执行 for 循环。在此期间，如果另一个线程也将值 1 分配给 is_bad（第 112 行），这并不会改变最终结果。这仅仅意味着该线程执行 for 循环的时间超出了必要时间。

2.6.3 使用双检锁的程序

单件可确保在整个程序中只有一个特定类型的对象存在。双检锁是在多线程应用程序中对单件进行初始化的一种常见的有效方法。以下代码将说明这样的实现。

 100 class Singleton {
 101     public:
 102     static Singleton* instance();
 103     ...
 104     private:
 105     static Singleton* ptr_instance;
 106 };
 ...

 200 Singleton* Singleton::ptr_instance = 0;
 ...

 300 Singleton* Singleton::instance() {
 301     Singleton *tmp = ptr_instance;
 302     memory_barrier();
 303     if (tmp == NULL) {
 304         Lock();
 305         if (ptr_instance == NULL) {
 306             tmp = new Singleton;
 307             memory_barrier();
 308             ptr_instance = tmp;
 309         }
 310         Unlock();
 311     }
 312     return tmp;
 313 }

ptr_instance的读取（第 301 行）特意未用锁进行保护。这样就可以通过检查来确定单件是否已经在多线程环境中进行有效实例化。请注意，第 301 行的读取与第 308 行的写入之间存在对变量 ptr_instance 的数据争用，但程序可正常工作。不过，编写允许数据争用的正确程序时，需要格外小心。例如，在上述双检锁代码中，第 302 行和第 307 行调用 memory_barrier() 的作用是确保按正确的顺序设置与读取单件和 ptr_instance。因此，所有线程将一致地读取它们。如果未使用内存屏障，此编程方法将失效。