- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
#include <iostream>
#include <memory>
#include <mutex>
#include <condition_variable>
#include <atomic>
typedef ::std::unique_lock<::std::mutex> TLock;
using namespace std;
template<typename T>
class TQueueElement
{
public:
T _data;
std::shared_ptr<TQueueElement<T> > _prev;
mutable ::std::mutex _lockElem;
public:
TQueueElement(T data):_data(data),_prev(nullptr){};
virtual ~TQueueElement(){};
};
template<typename T>
class TQueue
{
private:
mutable ::std::mutex _lockHead;
mutable ::std::mutex _lockTail;
::std::condition_variable _pushToQueue;
std::atomic<bool> _isEmpty;
std::shared_ptr<TQueueElement<T> > _tail;
std::shared_ptr<TQueueElement<T> > _head;
public:
TQueue():_lockHead(),_isEmpty(true){};
virtual ~TQueue(){};
///получаем элемент из очереди
T pop()
{
TLock lock(_lockTail);//блокируем все получения из очереди
if (_tail==nullptr)
{_isEmpty=true; _pushToQueue.wait(lock,[this](){return !_isEmpty;});} //если очередь пуста ожидаем пока в ней чтото появиться
{
TLock lockTail(_tail->_lockElem); //блокируем последний элемент в очереди возможно к нему попробуют обратиться во время запихивания в очередь
auto data=_tail->_data;
_tail=_tail->_prev;
return data;
}
}
void push(T data)
{
auto el=std::shared_ptr<TQueueElement<T> >(new TQueueElement<T>(data));//заранее создаем элемент очереди
TLock lock(_lockHead);
if (_isEmpty)//если очередь пуста говорим что наш элемент пока первый и последний
{
_head=el;
_tail=el;
_isEmpty=false;
_pushToQueue.notify_all();
}else//если очередь не пуста
{
{
TLock lockHead(_head->_lockElem); //блокируем голову от возможного обращения с хвоста
_head->_prev=el; //выставляем ссылку на новую голову у старой
}
_head=el;//выставляем новую голову
}
}
};
int main() {
TQueue<int> q;
q.push(7);
q.pop();
// your code goes here
return 0;
}
Follow us!
Кажется поправил.
- сразу после создания isEmpty == true, tail == nullptr;
- первый тред входит в pop, берет lockTail, видит nullptr в tail;
- второй тред входит в push, берет lockHead, видит true в isEmpty;
- первый тред ждет lockHead
- второй тред ждет lockTail
Получается разблокировав lockHead до wait я избавлюсь от проблемы?
Вот к примеру: http://www.boost.org/doc/libs/1_55_0/doc/html/lockfree.html
Relacy Race Detector
Ну-ну.
Хотя что подразумевать под "просто" - придумать и главное доказать корректность изобретенного алгоритма, вряд ли. А реализовать чужое, передрав псевдокод - это сравнительно просто.
В крестах еще ABA вылазит, в мусоросборных языках с этим чуть проще.
> просто
Если у тебя будет ровно один производитель и ровно один потребитель, то да. И то там блокировку на переполнения кольцевого буфера надо.
Не надо. Притом что у него связная очередь, а не на буфере.
http://www.csie.nctu.edu.tw/~tlhuang/Papers/ICPADS00.pdf
То, что можно сложно и без лока, я в курсе.
Я борманду ответил про "просто". Смотря что - реализовывать чужое или придумывать своё, или вообще "просто" - имелось ввиду без лочек.
Для связных существует Michael & Scott.
http://www.computer.org/csdl/proceedings/icpads/2000/0568/00/05680470.pdf
Люди, зачем вам const в языке, если у вас столько способов его снять ? :)