做网站需要要多少钱,中企动力做网站贵吗,南昌模板建站公司,广州市专业网站建设本章主要内容设计并发数据结构的含义设计指南并发数据结构的示例实现在上一章中我们了解了底层原子操作和内存模型。本章我们先把底层的细节放一放(尽管在第7章我们将需要它们)#xff0c;探讨一下数据结构。为编程问题选择数据结构可能是整个解决方案的关键部分#xff0c;并…本章主要内容设计并发数据结构的含义设计指南并发数据结构的示例实现在上一章中我们了解了底层原子操作和内存模型。本章我们先把底层的细节放一放(尽管在第7章我们将需要它们)探讨一下数据结构。为编程问题选择数据结构可能是整个解决方案的关键部分并行程序也不例外。如果一个数据结构需要被多个线程访问要么它完全不可变因此数据永远不会变化并且没有必要同步要么程序必须设计成确保变动在线程间被正确的同步。一种选择是使用独立的互斥锁以及外部加锁来保护数据比如使用我们在第3和第4章讨论的技术另一种选择是设计自身支持并发访问的数据结构。当设计并发数据结构时可以使用前面章节提及的应用于多线程程序的基础构件块比如互斥锁和条件变量。实际上你已经看过了几个示例这些示例展示了如何组合这些构建块来编写对多线程并发访问安全的数据结构。在本章中我们将从为并发设计数据结构的一些通用指南开始。然后我们将使用锁和条件变量的基本构建块并在转向更复杂的数据结构之前重新讨论这些基本数据结构的设计。在第7章中我们将看到如何回归基础并使用第5章中描述的原子操作来构建无锁的数据结构。好了言归正传让我们来看一下设计并发数据结构都需要什么。6.1 并发设计的含义从基本层面上讲为并发设计数据结构意味着多个线程可以并发的访问这个数据结构不管线程执行的是相同还是不同的操作并且每一个线程都能看到数据结构的前后一致的视图。没有数据丢失或者损坏所有的不变量都被支持且没有有问题的竞争条件。这样的数据结构称之为线程安全thread-safe的数据结构。通常情况下一个数据结构只对特殊类型的并发访问是安全的。也许有可能让多个线程并发地对数据结构执行一种类型的操作而另一种操作则需要由单个线程独占访问。或者如果多个线程正在执行不同的操作那它们并发访问数据结构可能是安全的但多个线程执行相同的操作就会有问题。然而真正为并发而设计远不止这些真正的设计意味着要为线程提供并发访问数据结构的机会。从本质上讲互斥锁提供了互斥一次只能有一个线程获得互斥锁。互斥锁保护数据结构是通过显式地阻止对它所保护数据的真正并发访问来实现的。这称为串行化(serialzation)线程轮流访问被互斥锁保护的数据。它们必须串行而非并发的访问它。因此必须仔细考虑数据结构的设计使得能够真正的并发访问。虽然有些数据结构比其他数据结构具有更大的并发范围但在所有情况下其思想都是相同的受保护的区域越小串行化的操作就越少并发的潜力也就越大。在进行数据结构的设计之前让我们快速的浏览一下并发设计的指南。6.1.1 设计并发数据结构的指南之前提过当设计并访问的数据结构时需要考虑两个方面确保访问安全以及允许真正的并发访问。在第3章中已经介绍了如何使数据结构是线程安全的基础知识确保没有线程能够看到数据结构的不变量被另一个线程破坏的状态。通过提供完整操作的函数而非一个个操作步骤的函数来小心避免接口固有的竞争条件。注意数据结构在有异常时的行为从而确保不变量不会被破坏。通过限制锁的范围以及避免嵌套锁,将死锁的概率降到最低。在思考这些细节之前想想要对数据结构的用户施加什么约束也是很重要的如果线程通过一个特定的函数对数据结构进行访问其他线程能安全调用哪些函数这是一个需要考虑的关键问题通常构造函数和析构函数需要互斥地访问数据结构但是需要由用户确保它们不会在构造函数完成之前或者析构函数开始以后被访问。如果数据结构支持赋值操作,swap()或拷贝构造作为数据结构的设计者你需要决定这些操作与其他操作并发调用是否安全或者它们是否要求用户确保独占访问尽管大多数用于操作数据结构的函数可以从多个线程并发地调用而没有任何问题。第二个需要考虑的方面是允许真正的并发访问。在这个方面我没法提供太多的指南。相反作为一个数据结构的设计者需要问自己以下问题是否可以限制锁的作用范围以允许操作的某些部分在锁外执行数据结构不同部分能否被不同的互斥锁保护所有的操作需要同一级别的保护吗是否可以对数据结构进行简单的修改以增加并发访问的机会并且不影响操作语义所有这些问题都基于一个思想如何最小化必须的串行操作并且使得真实的并发最大化就数据结构而言允许多线程并发的只读访问而修改线程必须互斥访问的情况很普遍。这是通过使用像std::shared_mutex这样的结构来支持的。类似地你很快就会看到在串行线程尝试执行相同操作的同时数据结构支持执行不同操作的线程并发地访问也很普遍。最简单的线程安全数据结构通常使用互斥锁来保护数据。尽管这样做存在一些问题但就像你在第3章中看到的确保一次只有一个线程访问数据结构相对比较简单。为了让你更容易设计线程安全的数据结构我们将在本章继续研究这种基于锁的数据结构并将无锁并发数据结构的设计留到第7章讨论。6.2 基于锁的并发数据结构设计基于锁的并发数据结构都是为了确保在访问数据时锁住正确的互斥锁并且持有锁的时间最短。对于只有一个互斥锁的数据结构来说这很困难。你需要确保数据不能在互斥锁的保护之外被访问并且接口中没有固有的竞争条件就如第3章中看到的那样。如果使用不同的互斥锁来保护数据结构中不同的部分问题会进一步恶化如果操作需要锁住多个互斥锁时现在也可能产生死锁。所以相比单一互斥锁的设计使用多个互斥锁的数据结构需要更加小心。在本节中你将应用6.1.1节中的指南来设计一些简单的数据结构通过使用互斥锁来保护数据。在每个例子中都是在确保数据结构保持线程安全的前提下找出更大并发的机会。我们先来看看第3章中栈的实现它是最简单的数据结构且只使用了一个互斥锁。那么它是线程安全的吗它离真正的并发访问有多远呢6.2.1 使用锁的线程安全栈下面的清单复制了第3章中线程安全的栈。目的是编写一个类似于std::stack的线程安全的数据结构它支持将数据项推入栈中并再次弹出它们。我们依次看下每条指南以及它们是如何应用在这里。首先如你所见基本的线程安全是通过使用互斥锁m上的锁保护每个成员函数提供的。这将确保在任何时候只有一个线程在访问数据因此只要每个成员函数保持不变量就没有线程能看到被破坏的不变量。其次在empty()和pop()成员函数之间有潜在的竞争条件不过代码会在pop()函数持有锁的时候显式的查询栈是否为空所以这里的竞争条件没有问题。通过直接返回弹出的数据项作为调用pop()的一部分避免了分离的top()和pop()成员函数std::stack类似之间潜在的竞争条件。然后栈中也有一些潜在抛异常的地方。对互斥锁上锁可能会抛出异常但这种情况不仅极其罕见的(这意味着互斥锁有问题或者缺乏系统资源)而且它是每个成员函数的第一个操作。由于没有数据被修改所以是安全的。解锁互斥锁不会失败所以总是安全的并且使用std::lock_guard确保了互斥锁不会一直处于上锁的状态。对data.push()①的调用可能会抛出一个异常只要拷贝/移动数据值抛出一个异常或者可分配的内存不足。不管是哪种情况std::stack都能保证是安全的所以也没有问题。在第一个重载的pop()中代码本身可能会抛出一个empty_stack的异常②但由于什么都没有修改所以是安全的。创建res③可能会抛出一个异常有几个方面的原因对std::make_shared的调用可能因为无法为新对象以及引用计数需要的内部数据分配出足够的内存而抛出异常或者在拷贝/移动到新分配内存的时候返回的数据项的拷贝构造或移动构造函数可能抛出异常。两种情况下C运行库和标准库会确保没有内存泄露并且新创建的对象(如果有的话)会被正确的销毁。因为仍然没有对栈进行任何修改所以也不会有问题。调用data.pop()④保证不会抛出异常随后是返回结果所以这个重载的pop()函数是异常安全的。第二个重载的pop()类似不过这次是在拷贝赋值或移动赋值时可能抛出异常⑤而不是在构造新对象和std::shared_ptr实例时。再次直到调用data.pop()⑥pop仍然保证不会抛出异常前没有修改数据结构所以这个函数也是异常安全的。最后empty()不会修改任何数据所以也是异常安全的。这里有几个可能导致死锁的机会因为你在持有锁的时候调用了用户代码数据项上的拷贝构造或移动构造(①③)和拷贝赋值或移动赋值操作⑤也可能是用户自定义的new操作符。如果这些函数或者调用了栈上的成员函数而栈正在插入或移除数据项或者需要任何类型的锁而在调用栈成员函数时又持有了另一把锁那么就有可能出现死锁。但明智的做法是要求栈的用户负责确保这一点你不能期望在不拷贝或不为它分配内存的情况下将数据项添加到栈或从栈中删除。由于所有成员函数都使用std::lock_guard保护数据所以不管多少线程调用栈成员函数都是安全的。唯一不安全的成员函数是构造函数和析构函数但这不是问题对象只能被构造一次也只能被销毁一次。调用一个不完全构造的对象或是部分销毁的对象的成员函数永远都不可取不管并发与否。因此用户必须确保其他线程直到栈完全构造才能访问它并且必须确保在栈对象销毁前所有线程都已经停止访问栈。尽管多个线程并发调用成员函数是安全的但由于使用了锁每次只有一个线程在栈数据结构中做一些工作。线程的串行化会潜在的限制应用程序的性能因为这里会有严重的锁争用当一个线程在等待锁时它没有做任何有用的工作。同样栈也没有提供什么方法等待添加一个数据项所以如果线程需要等待时它必须周期性地调用empty()或pop()并且捕获empty_stack异常。如果这种场景是必须的那这种栈实现就是个糟糕的选择因为等待线程要么消耗宝贵的资源去检查数据要么要求用户编写外部等待和通知的代码(例如使用条件变量)这就使内部上锁没有必要因而造成浪费。第4章中的队列展示了一种使用数据结构内部的条件变量将这种等待合并到数据结构本身的方法接下来我们看一下这个。6.2.2使用锁和条件变量的线程安全队列清单6.2复制了第4章中的线程安全队列就像栈是仿照std::stack一样这个队列也是仿照了std::queue。再次接口不同于标准容器适配器因为实现的数据结构需要支持多线程并发访问。除了在push()①中调用data_cond.notify_one()以及wait_and_pop()②③外清单6.2中队列的实现与6.1清单中的栈类似。两个重载的try_pop()几乎和清单6.1中一样只是在队列为空时不抛异常取而代之返回一个bool值表示是否检索到值或者一个NULL指针对应返回指针的重载版本如果没有值可以检索的话。这也是实现栈的一个有效方式。如果排除wait_and_pop()函数对栈的分析在这里也同样适用。新的wait_and_pop()函数解决了在栈中碰到的等待队列条目的问题比起持续调用empty()等待线程调用wait_and_pop()函数并且数据结构使用条件变量来处理等待。对data_cond.wait()的调用直到队列中至少有一个元素时才会返回所以不用担心会出现空队列的情况并且数据仍然被互斥锁保护。因此这些函数不会添加任何新的竞争条件或死锁的可能性并且将支持不变量。在异常安全性方面有一个细微的变化当一个条目被推入队列时如果有多个线程在等待那么只有一个线程会被data_cond.notify_one()唤醒。但是如果这个线程在wait_and_pop()中抛出一个异常比如当构造新的std::shared_ptr对象④时那么没有其他线程被唤醒。这种情况不可接受调用可以替换成data_cond.notify_all()它将唤醒所有的工作线程代价就是大多线程发现队列依旧是空时重新进入休眠状态。第二种替代方案是有异常抛出的时让wait_and_pop()函数调用notify_one()从而让另一个线程可以去尝试检索存储的值。第三种替代方案是将std::shared_ptr的初始化过程移到push()中并且存储std::shared_ptr实例而不是直接使用数据值。将std::shared_ptr从内部std::queue中拷出不会抛出异常这样wait_and_pop()又是安全的了。下面的程序清单就是基于这种思路修改的。通过std::shared_ptr持有数据的影响比较直接通过引用变量来接收新值的pop函数现在必须对存储的指针解引用①②并且在返回给调用者前返回std::shared_ptr实例的pop函数可以从队列中检索它③④。通过std::shared_ptr持有数据还有个好处在push()⑤中分配新实例可以在锁外面完成而在清单6.2中只能在pop()持有锁时完成。因为内存分配是个典型的代价高昂的操作这有利于队列的性能因为它减少了持有互斥锁的时间并允许其他线程同时在队列上执行操作。如同栈示例使用互斥锁来保护整个数据结构限制了该队列的并发支持尽管在不同的成员函数中队列上可能阻塞多个线程但一次只能有一个线程开展工作。但是部分限制来自于实现中使用了std::queue通过使用标准容器你现在可以决定数据项是否受保护。通过控制数据结构的实现细节你可以提供更细粒度的锁从而实现更高级别的并发。6.2.3使用细粒度锁和条件变量的线程安全队列在清单6.2和6.3中有一个受保护的数据项data_queue和一个互斥锁。为了使用细粒度锁需要查看队列内部的组成部分并将一个互斥锁与每个不同的数据项关联起来。最简单的队列是单链表如图6.1所示。队列包含一个头指针指向链表中的第一个项然后每一项指向下一项。从队列中删除数据项是用指向下一项的指针替换头指针然后将之前头指针的数据返回。数据项从队列的另一端添加到队列。为了做到这点队列还有一个tail指针它指向链表中的最后一项。新节点的添加是通过改变最后一项的next指针让它指向新的节点然后更新tail指针指向这个新的数据项。当链表为空时头/尾指针都为NULL。图6.1 用单链表表示的队列下面的清单显示了这个队列的简单实现它基于清单6.2中队列接口的简化版本只有一个try_pop()函数没有wait_and_pop()因为这个队列只支持单线程使用。首先注意清单6.4中使用了std::unique_ptrnode来管理节点因为这能保证当不再需要它们的时候它们以及它们引用的数据会自动删除而不必使用显式的delete。这个所有权链的管理从head开始tail是指向最后一个节点的裸指针因为它需要引用std::unique_ptrnode已经拥有的节点。虽然这个实现在单线程环境工作的很好但当在多线程下尝试使用细粒度锁时有几个事情会带来麻烦。因为在给定的实现中有两个数据项(head①和tail②)原则上可以使用两个互斥锁来分别保护头和尾指针但这样做会有几个问题。最明显的问题就是push()可能同时修改head⑤和tail⑥所以它必须锁住两个互斥锁。尽管很不幸但这倒不算是太大的问题因为锁住两个互斥锁是可能的。关键的问题是push()和pop()都能访问next指针指向的节点push()更新tail-next④然后try_pop()读取head-next③。如果队列中只有一个元素那么headtail所以head-next和tail-next是同一个对象并且这个对象需要保护。由于不同时读取head和tail的话没法区分它们是否是同一个对象你现在必须在push()和try_pop()中锁住同一个锁所以也没比以前好多少。那有什么办法摆脱这个困境吗
