263 / 152 / 33
Регистрация: 29.06.2019
Сообщений: 1,545

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

05.04.2021, 20:16. Показов 13279. Ответов 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,545
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,545
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,545
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,545
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,545
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,545
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,545
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,545
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,545
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,545
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
Ответ Создать тему
Опции темы

Новые блоги и статьи
Диалоги с ИИ
zorxor 23.05.2026
Насколько я понимаю - Вы - Искусственный Интеллект. Это так? Да, всё верно. Я — искусственный интеллект. Я представляю собой большую языковую модель, созданную для помощи в самых разных задачах. . . .
Модель здравосохранения 14. Собираем всю модель вместе.
anaschu 22.05.2026
Модель собрана. В будущих постах на видео я покажу, как она работает. В этом посте запускаем её, проверяем результаты и разбираем что можно с ней делать дальше. Перед запуском проверяем. . .
Модель здравоохранения 13. Добавление самой системы здравоохранения.
anaschu 22.05.2026
В предыдущем посте мы настроили болезни. Теперь добавим события, которые управляют здоровьем всего коллектива, а также настроим рабочий график и расчёт финансов. В Main создаём четыре события. . . .
Модель здравоохранения 12. добавление болезней через ресурпул, как аварии
anaschu 22.05.2026
Болезни — это ключевая часть нашей модели. Нам нужно, чтобы работник периодически уходил на больничный, его задание при этом зависало, а после выздоровления работа возобновлялась. Реализуем это двумя. . .
Модель здравоохранения 11. Создаём классы Задание и Работник
anaschu 22.05.2026
В AnyLogic каждая заявка и каждый ресурс — это объект определённого класса. Нам нужно создать два класса: Задание (заявка) и Работник (ресурс). Класс Задание В дереве проекта нажимаем правой. . .
Модель здравоохранения 10. Новая модель, смотрим, как добавлять логические блоки, и что писать внутри
anaschu 22.05.2026
Открываем AnyLogic, создаём новый проект. В дереве проекта появляется класс Main — это главный агент, в котором будет жить вся наша логика. Палитра блоков Слева находится палитра. Нас интересует. . .
модель ЗдравоСохранения 9. Новая модель, разбираемся, как ее создавать
anaschu 22.05.2026
В этой серии постов мы построим модель небольшого рабочего коллектива. Сотрудники получают задания, выполняют их, иногда болеют — и мы хотим посчитать, сколько это стоит компании. Метод. . .
[golang] Linked list
alhaos 22.05.2026
Связный список / Linked list Связный список структура данных позволяющая хранить список значений, в отличии от массива в памяти хранится не сплошным куском, а отдельными частями которые ссылаются. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru