Как правильно сделать многопоточность в C ++?

Question

У меня есть довольно большой, динамический, разреженный матричный объектный класс, и я хочу сделать следующее: один поток для обработки размещения элементов в матрице, а другой - для чтения из матрицы.

Единственный раз, когда эти два будут конфликтовать, это когда они оба захотят получить доступ к одной и той же строке / столбцу в одно и то же время. Поэтому я решил, что простой блокировки мьютекса для каждой строки / столбца достаточно.

Теперь я впервые делаю потоки в C / C ++, и я бы хотел, так сказать, по книгам. У меня есть две проблемы.

1. Как мне создать эти темы? Это языковой вопрос больше всего на свете.
2. Как максимально эффективно реализовать саму блокировку? Я полагаю, что если есть конфликт, то запрашивающий поток разместит себя в строке и будет ждать освобождения ресурса. Тем не менее, как я могу реализовать это пробуждение? Я могу сделать цикл опроса области памяти, но это не элегантно. В идеале я считаю, что подход, основанный на прерываниях, был бы лучшим.

Answer 1

Если вы впервые делаете многопоточность, используйте библиотеку Boost.Threads. Его семантика (включая механизмы синхронизации) очень проста, и ваша реализация будет переносимой.

http://www.boost.org/doc/libs/1_42_0/doc/html/thread.html

Answer 2

Сам C ++ не предлагает никаких потоков. В Windows вы можете использовать CreateThread. В UNIX вы можете использовать потоки POSIX (pthreads).

Не должно быть необходимости реализовывать свои собственные примитивы параллелизма. Например, в Windows вы можете создать объект взаимного исключения, используя CreateMutex, и использовать WaitForSingleObject для ожидания его освобождения.

Answer 3

Прежде всего, вам не нужен мьютекс на столбец и один на строку. Если вы приобрели мьютекс для строки, вы заблокировали все ячейки в этой строке, поэтому не имеет значения, к какому столбцу вы обращаетесь. Или, если вы получаете блокировку для каждого столбца, вы заблокировали все ячейки в этих столбцах, независимо от того, какая строка. Таким образом, вы можете иметь мьютекс на таблицу, по одному на ячейку, по одному на строку или по одному на столбец. Но по одному на строку и по одному на столбец не имеет смысла.

Большинство примитивов синхронизации блокируют ваши потоки, и поток просто возобновляет работу, когда ресурс становится свободным, вам не нужно беспокоиться о сигнализации и пробуждении. Именно эта часть и делает для вас объект синхронизации, такой как мьютекс или критическая секция.

Особенности построения и использования примитивов синхронизации зависят от платформы. Как уже сообщали другие, есть кроссплатформенные библиотеки, которые вы можете использовать, но вы должны указать, на какую платформу вы ориентируетесь, по крайней мере, чтобы мы знали, какие библиотеки доступны.

Answer 4

Что касается вашего второго вопроса, о том, как сделать блокировку: перевод потока в спящий режим и его пробуждение будет осуществляться ОС, это не ваше беспокойство. Но есть проблема с вашей схемой.

Вы хотите заблокировать доступ к ячейке, только если ее строка И столбец заблокированы. То есть разрешить доступ, если строка ИЛИ столбец разблокирована. Обычно это не так, как работают замки. Кроме того, если строка была заблокирована, но вы все равно разрешили доступ (поскольку столбец был разблокирован), вы все равно хотите заблокировать ее «больше». Это означает, что вам понадобится больше, чем мьютекс.

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

• Увеличить счетчик атомов в строке.
• Если предыдущее значение атомного счетчика было равно нулю, строка разблокировалась. Доступ в порядке.
  • Увеличить переменную условия столбца. В идеале это не должно блокировать.
• Если счетчик строки был ненулевым, он был заблокирован. Может быть, блок на столбце.
  • Подождите, пока переменная условия столбца не станет равной нулю. Установите его в единицу, прежде чем отпустить мьютекс.
• Когда вы закончите с доступом:
• Уменьшите условную переменную (не забудьте заблокировать ее) и дайте ей сигнал разбудить другие обращения, если она стала нулевой.
• Атомно уменьшить счетчик строк.

Это включает в себя небольшую сложную работу, но общее количество ресурсов блокировки в целом довольно мало. Кто-нибудь еще может сделать лучше (или найти контрпример к моей схеме)?

Также обратите внимание, что разбиение матрицы на строки и столбцы несколько произвольно. Если по этой схеме происходит слишком много конфликтов, вам, вероятно, следует разделить строки на половины (например).

Answer 5

Быстрая идея, выберите одну из доступных реализаций std :: threads , а затем рассмотрите std :: async и std::future и связанные с ними инструменты.

Answer 6

Томас накрыл библиотеку потоков. Единственная причина, по которой вы захотите связываться с обработчиками прерываний, это отсутствие у вас ОС. В противном случае используйте то, что ОС предоставляет вам для управления потоками.

В связи с блокировкой я бы предупредил вас о том, чтобы не застрять. Вы хотите заблокировать по строкам и столбцам, поэтому каждая строка и каждый столбец должен иметь свой собственный мьютекс. (На самом деле, блокировка чтения / записи была бы намного лучше для производительности, но вы должны быть еще более осторожны в отношении взаимоблокировок и условий гонки.)

Убедитесь, что вы всегда приобретаете и отпускаете замки в согласованном порядке; Вы не хотите, чтобы поток блокировал строку N, а затем блокировал блокирующий столбец K, а затем поток, который заблокировал столбец K, решает заблокировать строку N и блокирует, давая вам два заблокированных потока, и ничего не происходит (например, противостояние пистолета Джона У) .

Answer 7

Начните с форсированных потоков.

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

Если это вообще возможно, было бы лучше выяснить, как распределить ответственность за части матрицы на конкретные потоки. Снятие блокировки для каждого доступа к соте будет довольно узким местом.

Answer 8

вы уверены, что хотите матрицу, то, что вы описываете, звучит как очередь. Блокировка очереди довольно проста: когда кто-либо читает или пишет, он получает эксклюзивную блокировку (через pthread_mutex). (Не пользуйтесь блокировками чтения и записи и т. Д., Если вы действительно не знаете, что у вас проблемы с перфорированием)

конечно, прерывания не нужны

Answer 9

Я могу ответить на первую часть довольно просто - это зависит от вашей платформы. Если вы используете Win32 API, взгляните на функцию http://msdn.microsoft.com/en-us/library/ms682453%28VS.85%29.aspx «CreateThread» и ознакомьтесь с примерами. Книга, которую я прочитал о многопоточности в Windows, была такой: http://www.amazon.co.uk/Windows-PRO-Developer-Jeffrey-Wintellect-Christophe/dp/0735624240, которая охватывает не только многопоточность с CreateThread и другой опцией BeginThread, но также блокировки и семафоны и т. Д.

Если вы используете Linux, вам понадобятся потоки POSIX через функцию pthread, см. http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html в качестве примера.

Пример кода для pthreads выглядит следующим образом - будьте осторожны, я оставил функциональность для создания нескольких потоков из одной и той же функции, то есть для вызова массива переменных pthread_t. Вам это может не понадобиться.

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <malloc.h>

void *thread_function(void *arg) 
{
        /* DO SOME STUFF */

        /* Exit Thread */
    pthread_exit();
}

int main(int argc, char** argv)
{
        /* variables */
        int retval = 0;
        /* array of thread handles */
    pthread_t* thread_handle = (pthread_t*) calloc(1, sizeof(pthread_t));;

        /* create function - fork() for threads */
    retval = pthread_create(&thread_handle[0], NULL, thread_function, NULL);

        /* DO SOME STUFF */

        /* join - wait for thread to finish */ 
        pthread_join(thread_handle[0], NULL); 

    return EXIT_SUCCESS;
}

Компилировать с gcc filename -o fileexe -lpthread

Answer 10

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