目录

1、并发设计的意义

2、并发设计数据结构的准则

2.1、数据结构线程安全的原理

2.2、实现真正的并发

1、并发设计的意义

  在最基本的层面&＃xff0c;为并发设计数据结构意味着多个线程可以同时使用此数据结构&＃xff0c;执行相同或不同的操作&＃xff0c;并且每个线程都有数据结构的一致性试图。

  不会丢失或破坏数据&＃xff0c;维持所有不变量&＃xff0c;并且没有不确定的竞争条件&＃xff0c;此种数据结构就被称为线程安全的。通常&＃xff0c;只有在特定的并发存取下&＃xff0c;一种数据类型才是安全的。

  实际上&＃xff0c;并发设计远远不只是为多个线程提供存取数据结构的并发机会。本质上&＃xff0c;互斥元提供的是互斥&＃xff0c;一次只允许一个线程获取互斥元的锁。一个互斥元通过明确阻止对它所保护数据进行并发存取来保护数据&＃xff0c;这被称为序列化&＃xff0c;即多个线程轮流存取互斥元保护的数据&＃xff0c;它们必须线性的而非并发地存取数据。

   核心思想是&＃xff1a;更小的保护区域&＃xff0c;更少的操作被序列化&＃xff0c;以及更高的并发潜能。

2、并发设计数据结构的准则

为并发存取设计数据结构时&＃xff0c;需要考虑两方面&＃xff1a;保证存取是安全的以及允许真正的并发存取

2.1、数据结构线程安全的原理

• 保证当前数据结构不变性被别的线程破坏时的状态不被别的任何线程看到&＃xff08;简单理解就是一个线程写的时候&＃xff0c;其余线程不能读也不能写&＃xff09;
• 注意避免数据接口接口所固有的竞争现象&＃xff0c;通过为完整操作提供函数&＃xff0c;而不是提供步骤
• 注意当出现例外时&＃xff0c;数据结构是怎样来保证不变性不被破坏的。
• 当使用数据结构时&＃xff0c;通过限制锁的范围和避免使用嵌套锁&＃xff0c;来降低产生死锁的机会

在考虑这些细节前&＃xff0c;先考虑使用数据结构时的限制条件也是很重要的&＃xff0c;如果一个函数通过特殊函数使用数据结构&＃xff0c;那么其他线程调用哪个函数是安全的&＃xff1f;

这是要考虑的关键性问题。大多数构造函数和析构函数需要以独占方式访问数据结构&＃xff0c;即需要使用者保证它们在构造函数完成前或者析构函数开始后没有被使用。

2.2、实现真正的并发

这个问题比较复杂&＃xff0c;我们可以从以下角度来切入

• 锁的范围能否被限定&＃xff0c;使得一个操作的一部分可以在锁外被执行&＃xff1f;
• 数据结构的不同部分能否被不同的互斥元保护&＃xff1f;
• 是否所有操作需要同样级别的保护&＃xff1f;
• 数据结构的一个小改变能否在不影响操作语义情况下提高并发性的机会&＃xff1f;

所有的问题都被一个想法所指导&＃xff1a;如何能够最小化必然发生的序列化&＃xff0c;并且能够最大限度地实现并发性&＃xff1f;