Неблокирующие алгоритмы на C++, многопоточность - C++ - Ответ 14044588

@Ygg · 29.11.2019, 19:38

Чисто теоретически...
Например, нужно найти минимум.

Можно разбить массив на несколько частей (первая и вторая половины). Запустить для каждой части поток (два потока). В потоках найти минимумы по заданным частям (минимум первой половины и минимум второй половины). В конце выбрать минимум из полученных результатов каждого потока (минимальный из двух минимумов).

Как можно тут прикрутить атомарные операции?
В каждом потоке ищем не локальный минимум, а общий. Заводим атомарный минимум. Каждый поток сравнивает значение с ним и, если нужно, заносит в него новый минимум. Стрёмный какой-то вариант, но почему бы и нет...

Стрёмный, потому что на запись требуется несколько операций, а они уже не будут атомарными по своей природе, только если их завернуть в какой-нибудь мьютекс... или атомарный локер.

C++

atomic_int global_min; // атомарное значение, можем одновременно читать и записывать из разных потоков
int global_min_index; // не атомарное значение
 
// функция потока
void thread(int* array, int start, int stop)
{
  // цикл по заданным элементам
  for (int pos=start; pos<stop; pos++)
  {
    // сравнение с атомиком
    if (array[pos] < global_min)
    {
      // << lock ??? на запись нужно как-то заблокировать, что бы два потока не лезли одновременно
 
      // повторная проверка из-за возможности пересечения нескольких потоков
      // если какой-то поток уже внёс свои изменения, то нужно перепроверить минимум
      //  если всё ещё минимум, то обновить
      //  если минимум устарел, то ничего не делаем
      if (array[pos] < global_min)
      {
        global_min = array[pos];// запись в атомик
        global_min_index = pos;
      }
 
      // << unlock ???
    }
  }
}

Проще всё таки считать локальные минимумы, а потом свести результат по потокам в одну переменную. Можно сделать сведение с блокировкой на спинлоке, это типа и будет неблокирующий алгоритм.

С количеством проще, наверное имеется в виду количество элементов равных чему-то. Заводим атомарный счётчик и увеличиваем его из разных потоков.

С XOR не очень понятно. Можно попробовать воспользоваться fetch_xor для каждого элемента, но какой смысл? Проще опять же посчитать локальные XOR и потом объединить результат.

Вернуться к обсуждению:
Неблокирующие алгоритмы на C++, многопоточность C++

Следующий ответ

Другие темы раздела
C++ Изменение текста в чате Telegram Здравствуйте, есть ли бот или какие нибудь возможности менять цвет в чате (чтоб и у других пользователей оно отображалось, к примеру как __Привет__ = Привет ) ??? ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶ ̶̶ ̶ ̶ ̶ ̶ ̶ ̶... https://www.cyberforum.ru/ cpp/ thread2542246.html	C++ ЭЦП Эль Гамаля Доброго всем времени суток, написал прогу по по ЭЦП Эль-Гамаля, но что-то там не верно (оч грешу на значение переменной b) - есть знатоки? Памагити #include <iostream> #include <string> #include <cmath> using namespace std;
C++ Бинарное дерево слов из букв Нужно написать дерево, которое хранило бы в ячейках символы из слов, которые были добавлены. Задание звучит так: Хранение и распознавания слов на основе бинарного дерева. интерфейс основного класса должен содержать методы для добавления и распознавания указанного слова. Каждый узел дерева представляет собой объект, содержащий определенный символ, и ссылки на две ветви Left и Right. переход по... https://www.cyberforum.ru/ cpp/ thread2541920.html	C++ Имя класса, что наследует https://www.cyberforum.ru/ cpp/ thread2541905.html Если имеется код: Person* person = new Driver() То как я программно могу узнать имя класса Driver, имея только экземпляр person?
Доступ к адресам 0CF8h, CFCh Windows 10 C++ Поставлена задача написать на языке C/C++ Разработать программу формирования цикла опроса и идентификации устройств PCI, которая будет считывать два первых поля конфигурационного пространства - коды Vendor ID (производитель) и Device ID (устройство). Соответственно для чтения/записи в порт если не ошибаюсь нужно подключить драйвер GIVEIO, но не нашёл её для системы windows 10, а без него при...	C++ Организация экспертной системы Какова номенклатура товаров в магазине? Какова стоимость заданного товара в магазине? От каких поставщиков получают заданный тип товара? Сколько единиц данного товара находится на складе? https://www.cyberforum.ru/ cpp/ thread2541556.html
C++ Работа с базами данных Создать базу данных промтоварного магазина. https://www.cyberforum.ru/ cpp/ thread2541554.html	C++ Работа со списками Организовать ввод и формирование двух списков с проверкой целочисленного и вещественного. Найти их объединение. Упорядочить полученный список по возрастанию.
C++ Работа с текстами https://www.cyberforum.ru/ cpp/ thread2541549.html Организовать ввод строкового предложения и процедуру разделения его на отдельные слова. Удалить самое короткое слово.	C++ Написать код https://www.cyberforum.ru/ cpp/ thread2541547.html Вводить три числа и искать их среднее арифметическое, до тех пор пока оно не окажется равным 0
C++ Вычисление значения функции. Ошибки в написании вычислений Помогите решить задачку. Сам пишу её решение вроде всё правильно, но почему-то пишет ошибку. Если что версия VS 2008. Направьте на путь исправления ошибок или напишите своё решение, чтобы я из него сам понял, что у меня не так. 1 картинка - Задачка. 2 картинка - Мои ошибки. Вот мой код: #include "stdafx.h"	C++ квантовое шифрование https://www.cyberforum.ru/ cpp/ thread2541397.html Алиса хочет передать Бобу супер секретный код, содержащий 16 цифр, с помощью квантового шифрования. Если канал передачи данных, и детекторы Алисы и Боба идеальные, и Ева их не прослушивает, то сколько фотонов в среднем необходимо будет передавать Алисе для формирования надежного ключа? Считать, что теперь одна цифра кодируется не одним байтом, а минимально необходимым количеством бит.

	29.11.2019, 19:38