主要内容:
并发数据结构设计的意义
指导如何设计
实现为并发设计的数据结构
如果一种数据结构可以被多个线程所访问, 其要不就是绝对不变的(其值不会发生变化,
并且不需同步), 要不程序就要对数据结构进行正确的设计, 以确保其能在多线程环境下能够
(正确的)同步. 一种选择是使用独立的互斥量, 其可以锁住需要保护的数据, 另一种选择是设计一种能够并发访问的数据结构. 第一种使用互斥量, 在同一时间只有一个线程可以访问数据, 实际是一种串行的序列化访问. 显示的组织了多线程对数据结构的并发访问.
所以, 缩小保护区域, 减少序列化访问, 就能提高并发. 允许线程并发读取的数据结构并不少见, 而对数据结构的修改, 必须是单线程独立访问. 所以不可能完全实现并发, 只能让序列化访问最小化.
一, 基于锁的并发数据结构
基于锁的并发数据结构设计, 需要确保访问线程持有锁的时间最短. 都是在保证数据结构是线程安全的前提下. 在设计数据结构, 考虑以下问题:
锁的范围中的操作, 是否允许在所外执行?
数据结构中不同的区域是否能被不同的互斥量所保护?
所有操作都需要同级互斥量保护吗?
能否对数据结构进行简单的修改, 以增加并发访问的概率, 且不影响操作语义?
1, 使用锁实现一个线程安全的栈
- #include <exception>
- struct empty_stack: std::exception
- {
- const char* what() const throw();
- };
- template<typename T>
- class threadsafe_stack
- {
- private:
- std::stack<T> data;
- mutable std::mutex m;
- public:
- threadsafe_stack(){}
- threadsafe_stack(const threadsafe_stack& other)
- {
- std::lock_guard<std::mutex> lock(other.m);
- data=other.data;
- }
- threadsafe_stack& operator=(const threadsafe_stack&) = delete;
- void push(T new_value)
- {
- std::lock_guard<std::mutex> lock(m);
- data.push(std::move(new_value)); // 1
- }
- std::shared_ptr<T> pop()
- {
- std::lock_guard<std::mutex> lock(m);
- if(data.empty()) throw empty_stack(); // 2
- std::shared_ptr<T> const res(
- std::make_shared<T>(std::move(data.top()))); // 3
- data.pop(); // 4
- return res;
- }
- void pop(T& value)
- {
- std::lock_guard<std::mutex> lock(m);
- if(data.empty()) throw empty_stack();
- value=std::move(data.top()); // 5
- data.pop(); // 6
- }
- bool empty() const
- {
- std::lock_guard<std::mutex> lock(m);
- return data.empty();
- }
- };
线程安全队列 -- 使用锁和条件变量
线程安全队列 -- 使用细粒度锁和条件变量
(参考并发编程, 先占坑以后补上没有实战经验看不太懂)
二, 使用锁设计更加复杂的数据结构
编写一个使用锁的线程安全查询表
编写一个使用锁的线程安全链表
来源: http://www.bubuko.com/infodetail-2629994.html