Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.90/40: Рейтинг темы: голосов - 40, средняя оценка - 4.90
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30

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

05.09.2015, 15:56. Показов 8422. Ответов 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
Ответ Создать тему
Новые блоги и статьи
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным?
anaschu 12.07.2026
Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .
сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию.
anaschu 12.07.2026
Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .
Сукцессия 26. Мат модель создана.
anaschu 12.07.2026
Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .
Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста".
Hrethgir 12.07.2026
Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок
anaschu 12.07.2026
# От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .
сукцессия 24. Промежуточное общее описание модели
anaschu 12.07.2026
Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .
сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры.
anaschu 12.07.2026
Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .
сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато
anaschu 11.07.2026
Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru