??双链表中每个节点都有一个指针指向列表中下一个节点,还有一个指针指向前一个节点。其中不变量就是节点A中指向“下一个”节点B的指针,还有前向指针。为了从列表中删除一个节点,其两边节点的指针都需要升级。当其中一边升级完成时,不变量就被破坏了,直到另一边也完成升级;在两边都完成升级后,不变量就又稳固了。从一个列表中删除一个节点的步骤如下
??图中b和c在相同的方向上指向和原来已经不一致了,这就破坏了不变量。线程间潜在问题就是修改共享数据,致使不变量遭到破坏。当不做些事来确保在这个过程中不会有其余线程进行访问的话,可能就有线程访问到刚刚删除一边的节点;这样的话,线程就读取到要删除节点的数据(由于只有一边的连接被修改,如图(b),所以不变量就被破坏。破坏不变量的后果是多样,当其余线程按从左往右的顺序来访问列表时,它将跳过被删除的节点。在一方面,如有第二个线程尝试删除图中右边的节点,那么可能会让数据结构产生永久性的损坏,使程序崩溃。无论结果如何,都是并行代码常见错误:条件竞争。
??并发中竞争条件的形成,取决于一个以上线程的相对执行顺序,每个线程都抢着完成自己的任务。大多数情况下,即便改变执行顺序,也是良性竞争,其结果可以接受。例如,有两个线程同时向一个解决队列中增加任务,由于系统提供的不变量保持不变,所以谁先谁后都不会有什么影响。当不变量遭到破坏时,才会产生条件竞争,比方双向链表删除链表中间的某一项。并发中对数据的条件竞争通常表示为恶性条件竞争,我们对不产生问题的良性条件竞争不感兴趣。 C++ 标准中也定义了数据竞争这个术语,一种特殊的条件竞争:并发的去修改一个独立对象,数据竞争是(可怕的)未定义行为的原因。
??恶性条件竞争通常发生于完成对多于一个的数据块的修改时,由于操作要访问两个独立的数据块,独立的指令将会对数据块将进行修改,并且其中一个线程可能正在进行时,另一个线程就对数据块进行了访问。由于出现的概率太低,条件竞争很难查找,也很难复现。
??处理恶性条件竞争,最简单的办法就是对数据结构采用某种保护机制,确保只有进行修改的线程才能看到不变量被破坏时的中间状态。从其余访问线程的角度来看,修改不是已经完成了,就是还没开始。
??另一个选择是对数据结构和不变量的设计进行修改,修改完的结构必需能完成一系列不可分割的变化,也就是保证每个不变量保持稳固的状态,这就是所谓的无锁编程。不过,这种方式很难得到正确的结果。
??另一种解决条件竞争的方式是,使用事务的方式去解决数据结构的升级(这里的"解决"就好像对数据库进行升级一样)。所需的少量数据和读取都存储在事务日志中,而后将之前的操作合为一步,再进行提交。当数据结构被另一个线程修改后,或者解决已经重启的情况下,提交就会无法进行,这称作为“软件事务内存”。理论研究中,这是一个很热门的研究领域。
??保护共享数据结构的最基本的方式,是使用C++标准库提供的互斥量。