Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30

Потокобезопасная очередь: критика реализации

05.09.2015, 15:56. Показов 8431. Ответов 25

Студворк — интернет-сервис помощи студентам
Прочитал третью часть
"Уильямс Э. "Параллельное программирование на С++ в действии. Практика разработки многопоточных программ" - 2012"
увидел там пример реализации потокобезопасной очереди, но к своему удивлению пример реализации основан на блокировании всей очереди.
Погуглив увидел те же примеры с блокированием всего контейнера.

Ранее я смотрел лекториум

Собственно вероятно можно реализовать с блокировками более оптимальным образом не блокирую "всё".

Накатал такую реализацию:
C++
1
2
3
4
5
6
7
8
9
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <thread>
#include <mutex>
using namespace  std;
 
template <typename T>
struct LockableNode
{
   T data;
   LockableNode<T>* next;
 
   // for std::lock_guard & std::lock
   void lock()  { m_.lock();   }
   void unlock(){ m_.unlock(); }
 
   LockableNode(T data=T(),LockableNode<T>* next=0)
       :data(data),next(next)
   { }
 
   private:
    mutex m_;
};
 
template <typename T>
class Queue
{
   public:
      Queue();
      ~Queue();
 
      void push(T e);
      bool pop(T& e);
      //T popAndWait();
 
      void clear();
 
   private:
      void unsynchronizedClear();
 
      typedef LockableNode<T> NodeType;
      typedef std::lock_guard<NodeType> NodeGuard;
      typedef NodeType* NodePtr;
 
      NodePtr fictiveHead_;
      NodePtr fictiveTail_;
};
 
template <typename T>
Queue<T>::Queue()
   :fictiveHead_(new LockableNode<T>()),
    fictiveTail_(new LockableNode<T>())
{}
 
 
template <typename T>
void Queue<T>::unsynchronizedClear()
{
  for(NodePtr ptr= fictiveHead_->next;
      ptr;
      fictiveHead_->next= ptr->next)
  {
    delete ptr;
  }
  fictiveHead_->next= fictiveTail_->next= 0;
}
 
template <typename T>
void Queue<T>::clear()
{
  lock(*fictiveHead_,*fictiveTail_);
  unsynchronizedClear();
}
 
 
template <typename T>
Queue<T>::~Queue()
{
  unsynchronizedClear();
  delete fictiveHead_;
  delete fictiveTail_;
}
 
 
template <typename T>
void Queue<T>::push(T e)
{  
  NodePtr newNode=  new LockableNode<T>(e);
  NodeGuard tailGuard(*fictiveTail_);
 
  if(fictiveTail_->next) // has real Node
  {
    NodeGuard lastGuard(*fictiveTail_->next);
    NodePtr   last=  fictiveTail_->next;
    last->next =     fictiveTail_->next = newNode;
  }
  else  // if empty
  {
    NodeGuard headGuard(*fictiveHead_);
    fictiveHead_->next = fictiveTail_->next = newNode;
  }
}
 
template <typename T>
bool Queue<T>::pop(T& e)
{
  NodeGuard headGuard(*fictiveHead_);
  if(fictiveHead_->next)
  {
    NodeGuard firstGuard(*(fictiveHead_->next));
    NodePtr   first= fictiveHead_->next;
 
    if(first->next)
    {
      fictiveHead_->next = first->next;
    }
    else // one real Node
    {
      NodeGuard tailGuard(*fictiveTail_);
      fictiveHead_->next= fictiveTail_->next= 0; // queue will be empty
    }
 
    e= first->data;
    delete first;
    return true;
 }
  else
      return false;
}
 
 
//template <typename T>
//T Queue<T>::popAndWait()
//{
 
//}
 
 
void fillQ(Queue<string>& sq)
{
   for(int i=0; i<50 ; ++i)
   {
      this_thread::sleep_for(chrono::milliseconds(rand()%500));
      sq.push(to_string(i));
   }
}
//-------------------------------------------------------------------------
 
int main()
{
  srand(time(0));
  {
    Queue<string> sq;
    thread th(&fillQ,ref(sq));
 
    for(;;)
    {
      string s;
      if(sq.pop(s))
        cout<< s <<endl;
      else
      {
        cout<< "-" <<endl;
        this_thread::sleep_for(chrono::milliseconds(rand()%500));
      }
    }
 
    th.join();
  }
    cout<<"done!"<<endl;
    return 0;
}




Но не уверен что сделал все провильно, а так же у меня дилема насчет реализацией popAndWait() метода.

Возможно кто-то подскажет ссылки или лит-ру на эту тему?
Ну или кто-то укажет на ошибки в моем коде?
2
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
05.09.2015, 15:56
Ответы с готовыми решениями:

Создать очередь вещественных значений, для реализации используя односвязные списки
Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления() и удаления() элемента...

Отделение интерфейса от реализации класса: компиляция кода реализации
Доброго времени суток, У меня возникла проблема с отделением интерфейса от реализации класса. Допустим, у меня есть три файла: 1....

Потокобезопасная очередь
Необходимо очередь, которая удовлетворяет следующим условиям: 1. Потокобезопасная (N писателей и один читатель) 2. Должна быть без...

25
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
05.09.2015, 19:26  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Убежденный Посмотреть сообщение
Правда, они далеко не
всеми CPU поддерживаются...
Ну вот в этом и проблема.
Хотелось реализацию на STL/BOOST.
0
Ушел с форума
Эксперт С++
 Аватар для Убежденный
16481 / 7444 / 1187
Регистрация: 02.05.2013
Сообщений: 11,616
Записей в блоге: 1
05.09.2015, 19:31
Здесь уже побывал ?

Boost.Lockfree
http://www.boost.org/doc/libs/... kfree.html
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
05.09.2015, 20:01  [ТС]
Да видел, но хотелось бы видеть "ручную" реализацию на "приметивах С++".

Добавлено через 23 минуты
Нашел:
http://blog.lse.epita.fr/artic... swap-.html
http://stackoverflow.com/quest... free-stack
http://stackoverflow.com/quest... -operation

Т.е нужно сооружать нечто вроде
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
struct PointerPair
{
    T* first;
    T* second;
};
 
 
int main()
{
   std::atomic< PointerPair<int> > pp;
   std::cout<<std::boolalpha<< pp.is_lock_free() <<std::endl;
 
   return 0;
}
+ проверять отрабатывают ли корректно CAS операции на этой платформе.
0
19501 / 10106 / 2461
Регистрация: 30.01.2014
Сообщений: 17,825
05.09.2015, 20:20
Цитата Сообщение от Avazart Посмотреть сообщение
хотелось бы видеть "ручную" реализацию
Как вариант:
http://www.1024cores.net/home/... tmah-bonus
0
 Аватар для ASCII
99 / 70 / 13
Регистрация: 15.12.2013
Сообщений: 463
16.06.2016, 06:14
Цитата Сообщение от ct0r Посмотреть сообщение
Вообще я советую читать Уильямса всего лишь как некий гайд по С++ реализации, когда уже есть хорошая база в многопоточности. Потому что само многопоточное программирование книжка описывает слабенько.
Спустя полгода...

А что посоветуете читать вместо него, желательно на русском?
PS. По мне, так довольно понятно объясняет многие вещи... Разумеется новичку над чем-то придется ломать голову часами, но после этого хороший эффект)
0
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
16.06.2016, 16:00
Цитата Сообщение от ASCII Посмотреть сообщение
А что посоветуете читать вместо него, желательно на русском?
Не вместо него, а в дополнение. И не на русском конечно же.
Книга называется The Art of Multiprocessor Programming.
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
16.06.2016, 16:00

Потокобезопасная очередь
нужна потокобезопасная очередь с ожиданием и отказами. очередь должна быть с ограничением по размеру. видел реализацию на...

Помогите найти ошибки в реализации класса «Очередь»
Класс «Очередь». Методы: добавление элемента, удаление элемента, удаление из очереди всех элементов, равных заданному значению. начал...

Используя модуль для реализации дека целых чисел, реализовать очередь на базе дека
Уважаемые программисты!Очень нужна Ваша помощь: (помогите решить, разобраться или хотябы просто объяснить алгоритм, с чего начинать, как...

Потокобезопасная коллекция
Здравствуйте, у меня следующая проблема: есть пользовательский класс Book, а также потокобезопасная коллекция BlockingCollection объектов...

Ява потокобезопасная переменная
Помогите пожалуйста с теорией потоко-безопасных переменных! Основы знаю(для Делфи учил), но на практике (в яве) еще не применял... ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
26
Ответ Создать тему
Опции темы

Новые блоги и статьи
ИИ и человечность
kumehtar 21.07.2026
Забавно, что общаясь с ИИ, я замечаю, насколько он высказывается умно, и насколько верит в людей. Он умеет прощать. Он знает как отвечать не обесценивая опыт других людей, даже если сам не верит. Он. . .
Нейтральные знания ..., ... чистая наука. Пока что-то проходит модерацию на Хабре, стоит развить мысль ...
Hrethgir 20.07.2026
К таким радикальным взглядам я конечно в той публикации не приходил, но чтобы скоротать вечер, решил углубиться немного. 1. Почему показания термометра заряжены целью? Цель заложена в самом. . .
Установка нескольких штампов электронной подписи в строго определенных местах файла docx
ВладимирСамохин 19.07.2026
(В!) Работа с Электронной подписью - это неотъемлемая часть современного документооборота. Но что делать, если нужно поставить несколько штампов электронной подписи в строго определенных местах. . .
сукцессия 35. Научная статья о проделанной работе
anaschu 19.07.2026
Написал в формате латекс и пдф
Вангую, что это не пройдёт модерацию, и на неделе я запущу свой сервер.
Hrethgir 19.07.2026
Эта публикация сейчас в песочнице и ждёт приглашения. https:/ / habr. com/ ru/ sandbox/ 295048/ По ссылке 403. Не очень информативно такую ссылку постить. Запись от Usaga размещена Сегодня в 06:46 . . .
сукцессия 33. открытые вопросы от клауде
anaschu 19.07.2026
"Что накопилось за эту часть А — тринадцать правок, из которых шесть пришли из ваших вопросов и каждая оказалась реальной ошибкой, а не калибровкой: односторонний симбиоз, отсутствующий листопад,. . .
32 сукцессия
anaschu 19.07.2026
сукцессия 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не «подкручивает» сходимость —. . .
сукцессия 31: модель микоризы - это модель ещё нескольких явлений, социальных и экономических
anaschu 18.07.2026
Теория «Всего»: апдейт v1. 1. 2 — 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru