Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.71/58: Рейтинг темы: голосов - 58, средняя оценка - 4.71
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524

Потоко-безопасная Очередь

05.04.2021, 20:16. Показов 12774. Ответов 106
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
... вырисовалась тема отсюда
Цитата Сообщение от zayats80888 Посмотреть сообщение
Хотя не сложно написать такую очередь(с раздельной блокировкой для "хвоста" и "головы") самостоятельно.
вот выполнила последнюю задачку отсюда - но не знаю, может лучше shared_mutex вместо просто mutex? правда на него unique_lock<shared_mutex> не ставится...
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
#include <iostream>
#include <thread>
#include <condition_variable>
#include  <mutex>
#include <chrono>
#include <queue>
 
using namespace std;
 
  bool bDone;
  mutex m;
  std::condition_variable cv;
 
int main() {
    int c = 0;
    bool done = false;
    queue<int> goods;
 
    thread producer([&]() {
        std::lock_guard<mutex> lock(m);
        for (int i = 0; i < 500; ++i) {            
            goods.push(i);
            c++;
            cv.notify_one();
        }
 
        done = true;
    });
 
    thread consumer([&]() {
        std::unique_lock<mutex> lock(m);
        while (!done) {
            while (!goods.empty()) {
                goods.pop();
                c--;
                while (!bDone) cv.wait(lock);
            }
        }
    });
 
    producer.join();
    consumer.join();
    cout << "Net: " << c << endl;
}
тут же не раздельная блокировка? - это FIFO, насколько понимаю...
а раздельная - вы, наверно, имеете ввиду для LIFO... наверно лучше на list выполнять?
sorry, что много вопросов - стою на распутье - даже в отдельную тему вынесла
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
05.04.2021, 20:16
Ответы с готовыми решениями:

Потоко-независимая очередь записывает 2е команды в одну ячейку. Почему ?
Доброго времени суток. Написал 2а приложения общяющихся между собой по TCP. Одно является сервером(планшет), второе клиент(windows). ...

Потоко-безопасный ObservableCollection с AddRange
Вообщем, я заполняю в нескольких потоках массив. на данный момент использую &quot;List&lt;ExpandoObject&gt; Вывод&quot; из-за...

Является ли boost::asio::tcp::acceptor потоко-безопасным ?
Мне сложно понять смысл того что написано в документации: ...

106
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
08.04.2021, 10:58
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от JeyCi Посмотреть сообщение
конечно, ужасно... ведь все советы применила с этой ветки...
Цитата Сообщение от JeyCi Посмотреть сообщение
thread producer([&]() {              
        for (int i = 0; i < 500; ++i) {
            std::lock_guard<mutex> lock(m);                  
            goods.push(i);
            c++;
cv.notify_one();

        }
        done = true;
        cv.notify_one();
    });
Иначе в твоих потоках нет никакого смысла
1
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
09.04.2021, 19:29  [ТС]
Concurrency - Remember
честно говоря, видела страшилки, что ABA-problem возникает в producer-consumer архитектуре (используя CV и мьютекс)... оказывается, только для случаев lock-free... может, что-то неправильно запомнила?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
09.04.2021, 19:49
Цитата Сообщение от JeyCi Посмотреть сообщение
честно говоря, видела страшилки, что ABA-problem возникает в producer-consumer архитектуре (используя CV и мьютекс)... оказывается, только для случаев lock-free... может, что-то неправильно запомнила?
Правильно. Только в lock-free. Вернее в interlocked или spin-блокировках. Lock-free это более широкое понятие.
1
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
10.04.2021, 06:50  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Вернее в interlocked или spin-блокировках.
и всё же
Итак, иерархия реализации такова: mutex/cond/sema сделаны на базе спинлоков, спинлоки — на базе атомарных операций, предоставляемых процессором
- значит проблема может вылезти и в mutex'ах, и в cv?.. или разработчики последних в их реализацию уже заложили защиту от этой проблемы?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.04.2021, 08:25
Цитата Сообщение от JeyCi Посмотреть сообщение
- значит проблема может вылезти и в mutex'ах, и в cv?.. или разработчики последних в их реализацию уже заложили защиту от этой проблемы?
ABA проблема возникает при работе с lock-free списками, когда нужно без блокировки обращаться к значению указателя. У мьютексов и прочего ничего подобного нет, там память не выделяется.
1
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
10.04.2021, 10:56  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
при работе с lock-free списками
действительно, надо помнить
перед тем как реализовывать lock-free алгоритм необходим анализ используемых структур данных на предмет возможности параллельного доступа нескольких потоков одновременно. Вполне возможно, что именно в вашем случае (как, например, в случае со стеком) lock-free подход лишь добавит вам геморроя, не улучшая значительно быстродействия
код здесь
None of the multi-threaded stacks performed better than a single-threaded stack.
Добавлено через 1 час 14 минут
в общем, у меня такое ощущение, что главная проблема возникает, когда куча - одна, а ядер - несколько... => проблема в словах для железа- кто current, а кто next для тех или иных контейнеров... хотя проблема, конечно, глубже - успел или не успел write после того, как read... и начал кто-то другой read--modify-write или ещё не успел начать...
выходов предлагается много для решения этой проблемы - все с тяжёлой артиллерией (garbage collection, hazard pointers, чтобы универсально, а не только для DCAS архитектур)...
поэтому считаю, контейнеры U++ с индексированным доступом (индексы в данном случае - в качестве счётчика) - самыми удобными!.. никаких current-next, никаких искуственных счётчиков, только родные для контейнеров фреймворка, никакой путаницы, простота и безопасность... имхо!
p.s.
задачка на всякий случай... и ликбез
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.04.2021, 11:06
Цитата Сообщение от JeyCi Посмотреть сообщение
в общем, у меня такое ощущение, что главная проблема возникает, когда куча - одна, а ядер - несколько... => проблема в словах для железа- кто current, а кто next для тех или иных контейнеров... хотя проблема, конечно, глубже - успел или не успел write после того, как read... и начал кто-то другой read--modify-write или ещё не успел начать...
Нет не в этом. А в том, что при помощи interlocкеd/spin/lock-free-блокировок довольно сложно сделать транзакцию, т.е. выполнить действия над несколькими объектами/переменными (например, удалить элемент из односвязного списка), так, чтобы никто другой не смог вмешаться в эти действия.
С использованием мьютекса, например, это сделать легко.
0
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
10.04.2021, 19:36  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
при помощи interlocкеd/spin/lock-free-блокировок довольно сложно сделать транзакцию, т.е. выполнить действия над несколькими объектами/переменными (например, удалить элемент из односвязного списка), так, чтобы никто другой не смог вмешаться в эти действия.
да, в продолжение такой мысли по линку с задачки #66
Ну, в c++ только один подход - это использовать атомарные операции. Либо натив от платформы. Как глубоко вы бы ни делали проверки, то все равно самый низкий счётчик будет подвержен проблеме ABA, с очень малой вероятность, но подвержен.
- даже в ассемблер люди лезут, чтобы реализовать real atomicity in lock-free
There are lots of papers on writing lock free queues using assembly/compiler intrinsics to perform atomic operations but it's really difficult to get it working.
т.е. надо лезть ещё ниже, чем просто С (пример spinlock)
- значит блокировка надёжнее
(в любом случае в production не сдают код, работающий только на опр. процессорах - я про DCAS)

Добавлено через 14 минут
ссылка есть на C++
https__stackoverflow__com__/questions/849786/is-a-lock-wait-free-doubly-linked-list-possible/849837#849837

- всё начинать, наверно, вообще стоит с lock-free memory manager... чтобы эту lock-free спокойно прикручивать к контейнерам...
p.s.
Lock-Free_DoublyLinkedList - в общем, нелегко...
CAS-based algorithm

Добавлено через 3 минуты
A Fast General Purpose Lock-Free Queue for C++

Добавлено через 3 часа 54 минуты
САМОЕ ИНТЕРЕСНОЕ:
мне этот пример кажется более понятным, чем про обедающих философов (видя название 2го, я не дочитывала его до конца, всё время откладывая на потом) - то ли дело нормальная постановка вопроса:
Сценарий: отдых в горах
Процесс А и процесс Б решили провести отпуск в горах. Для этого им необходима машина и лыжи(ресурсы). Есть возможность отдолжить только одни лыжи и одну машину. Если процесс получит машину и лыжи, то отправится в отпуск, а другой процесс будет ждать его возвращения, чтобы получить лыжи и машину. Если же один процесс получит лыжи, а другой машину, то оба будут ждать недостающего снаряжения и никто(никогда) не поедет в отпуск. Возникает взаимоблокировка(deadlock), когда каждый процесс ждет освобождения ресурса используемого другим процессом.
- сразу становится понятен Deadlock
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.04.2021, 19:40
Цитата Сообщение от JeyCi Посмотреть сообщение
- сразу становится понятен Deadlock
Цитата Сообщение от JeyCi Посмотреть сообщение
Если же один процесс получит лыжи, а другой машину
Стою на процессе
Я в лыжи обутый,
То ли лыжи не едут
То ли дедлок....
0
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
10.04.2021, 20:25  [ТС]
вот всё-таки интересно, можно ли на лыжах с машиной применить др. подход?
another high-level approach to concurrent programming called the "Actor" model. A major difference between the Actor model and the Isolated Sections model is that there are no data races possible in the Actor model because it does not allow for any form of shared variables.
- если кто применял, опишите please, например, концепцию или алгоритм... - действительно ли нормальная альтернатива конкурентности?
я бы даже предположила, что можно лыжи, машину и юзеров выделить в отдельные классы и лямбдами менять их State - в общем и целом...
но с моделью ещё надо разобраться... параллельность судьбы лыж и машины будут под большим вопросом (т.е. лыжи и машина не будут существовать во времени совместно)

Добавлено через 23 минуты
... ладно, отложим пока лыжи,
назрела более серьёзная проблема этой ветки
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
done = true;
cv.notify_one();
Even if you make dataReady an atomic, it must be modified under the mutex; if not the modification to the waiting thread may be published, but not correctly synchronised. This race condition may cause a deadlock
Добавлено через 26 секунд
Цитата Сообщение от zayats80888 Посмотреть сообщение
Подумайте, а что если consumer запустится раньше producer.
вот даже ответ нашла - перед What's next? - это надо знать, а не думать над этим (как "обедающие философы")
Let me assume the notification is sent while the condition variable condVar is in the wait expression but not in the waiting state. This means the execution of the thread is in the source snippet in the line with the comment time window ( line 1). The result is that the notification is lost. Afterwards, the thread goes back in the waiting state and presumably sleeps forever.
Добавлено через 2 минуты
- вот поэтому producer и consumer и работают с одним(!) мьютексом и consumer в состоянии wait - будет ждать... имхо... лыжи
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.04.2021, 20:29
Цитата Сообщение от JeyCi Посмотреть сообщение
... ладно, отложим пока лыжи,
назрела более серьёзная проблема этой ветки
Сообщение от oleg-m1973
done = true;
cv.notify_one();
Здесь нужно, чтобы мьютекс, который ожидает cv, был заблокирован перед вызовом cv.notify_one(). Можно даже вот так
C++
1
2
3
4
done = true;
mx.lock();
mx.unlock();
cv.notify_one();
C++
1
2
3
4
std::unique_lock lock(mx);
....
while (!done)
    cv.wait(lock);
0
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
10.04.2021, 20:36  [ТС]
там мьютекс m - думаю, всё на одном надо делать, чтобы producer и consumer и их действия были логично упорядочены
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.04.2021, 21:35
Цитата Сообщение от JeyCi Посмотреть сообщение
там мьютекс m - думаю, всё на одном надо делать, чтобы producer и consumer и их действия были логично упорядочены
Правильно думаешь. Надо делать на одном, как я тебе и показывал.
0
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
12.04.2021, 09:11  [ТС]
всё-таки проектирование параллельности - тоже надо уметь рисовать в UML - чтобы потом не забыть структуру кода и не вчитываться в него снова ...
какой-то UML Online Editor

Добавлено через 9 минут
и кстати, банально - Two models for concurrent programming... а то я что-то с Actor'ами задумалась -- а ведь у меня так и было до знакомства с shared_memory

Добавлено через 2 минуты
самый развёрнутый Multithreading and concurrency - много примеров...

Добавлено через 7 минут
Цитата Сообщение от zayats80888 Посмотреть сообщение
пользуйтесь готовыми решениями(библиотечными, а не портянками с сайтов и форумов).
Concurrent queue – C++11 - встречаются простые и лаконичные примеры для знакомства с темой (по названию этой ветки)
0
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
12.04.2021, 21:38  [ТС]
а если попробовать сделать на Семафоре Thread-safe Queue, то надо будет использовать и Семафор и Мьютекс??
C++
1
2
3
4
5
6
7
8
9
10
11
12
  sem_wait(&empty);
  pthread_mutex_lock(&mutex);
  int iMsg = InsertItem(item);
  
  if(iMsg == -1){
   printf("Error Inserting Item \n");
  }else
  {
   printf("Produced Item :: %d  Thread No :: %d\n", item , *((int *)Param));
  }
  pthread_mutex_unlock(&mutex);
  sem_post(&full);
одного семафора будет мало?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
12.04.2021, 21:42
Цитата Сообщение от JeyCi Посмотреть сообщение
а если попробовать сделать на Семафоре Thread-safe Queue, то надо будет использовать и Семафор и Мьютекс??
Ну да. Семафор для контроля количества элементов в очереди, мьютекс, собственно, для синхронизации операции с очередью
1
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
12.04.2021, 22:48  [ТС]
в общем создаётся ощущение, что эти потоки хорошо для Аудио-Видео контента... ну и для сложных мат. расчётов... иначе и message'ами ОК (как, банковские АТМ часто описываются)...
и как справедливо отметил TRam_ по моей ветке:
Цитата Сообщение от TRam_ Посмотреть сообщение
Не до конца понятно, что тут в очередях предполагается сделать, но если нужно "получить однопоточное исполнение для двух потоков..."
что и рассмотрели по ветке... настоящая же многопоточность обладает свойством "недетерминированного поведения" (т.е., действительно, в разнобой)...
повторюсь, cv для Win7 и выше -- тут всё сводится к NT kernel - интересная статья 2003 г. c выводом для Win32 - про все подводные камни и фиаско попытки сделать cv на семафоре
it has a fundamental performance problem: there are necessarily two context switches in each call of Signal, because the signalling thread must wait for the signalled thread to call h.V() before the signalling thread can continue.
Добавлено через 1 минуту
как и ваше предупреждение здесь
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
12.04.2021, 22:57
Цитата Сообщение от JeyCi Посмотреть сообщение
в общем создаётся ощущение, что эти потоки хорошо для Аудио-Видео контента... ну и для сложных мат. расчётов... иначе и message'ами ОК (как, банковские АТМ часто описываются)...
Нет. Потоки, это хорошо для эффективного использования ресурсов процессора/компьютера. Круг задач при этом очень широкий. Лично я даже не припомню, когда последний раз мне приходилось решать чисто однопоточную задачу. Какой смысла работать с одним потоком, когда сегодня даже на самом дохлом телефоне минимум четыре ядра.
0
263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,524
12.04.2021, 22:57  [ТС]
когда лочить не приходится, то да... поэтому и разделяем бизнес-логику по потокам... а ожидание на cv, да ещё если очередь многомилионная, а ядра всего 4, - всё равно кушает время за счёт switch-context
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
12.04.2021, 23:08
Цитата Сообщение от JeyCi Посмотреть сообщение
когда лочить не приходится, то да... поэтому и разделяем бизнес-логику по потокам... а ожидание на cv, да ещё если очередь многомилионная, а ядра всего 4, - всё равно кушает время за счёт switch-context
Нет. Это всего лишь означает, что программу писал сапожник. Для таких вещей надо чётко контролировать, что именно ты делаешь, ну и худо-бедно представлять, как работает процессор, который ты программируешь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
12.04.2021, 23:08
Помогаю со студенческими работами здесь

Сформировать односвязную очередь из элементов, которые входят в очередь Q1, но не входят в очередь Q2
Составить программу обработки динамической структуры данных: сформировать односвязную очередь Q из элементов, которые входят в очередь Q1,...

Не безопасная форма
Привет, пользуюсь менеджером паролей Lastpass, и мне интересно, что такое не безопасная форма? У разработчика спрашивал, но он объяснил что...

Безопасная работа
_http://www.webpark . ru/comments.php?id=45545

Безопасная регистрация
Всем привет. Вот я собственно попытался сделать систему регистрации, в PHP пока еще не особо силен, только понемногу начинаю учится. ...

Безопасная авторизация
Здравствуйте! Есть приложение клиент, которое обращается к wcf сервису, чтобы то произвело какие то действия. Клиент написан под...


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

Или воспользуйтесь поиском по форуму:
80
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru