LINUX.ORG.RU

Заблокировать часть массива с помощью mutex

 


0

2

Хочу реализовать кольцевой буфер на C. Структура должна быть потокобезопасной. Самый простой способ добиться этого - использовать mutex: если какой-то поток хочет записать данные в буфер, то он захватывает mutex, пишет данные и отпускает mutex. Если другой поток хочет прочитать данные - то он захватывает mutex, читает данные и отпускает mutex.

Плюсом такого подхода можно считать консистентность данных. Минусом - чрезмерные блокировки: допустим, я записываю данные с 1 по 5 элемент, а считать хочу с 7 по 10. По идее эти операции не конфликтуют и их можно делать без блокировки. Поэтому возникает вопрос: существуют ли какие-нибудь range mutex или типа того, которые позволяют заблокировать не весь массив с данными, а только его часть. Может быть имеет смысл сделать по mutex на каждый элемент массива? Или это только усугубит ситуацию?

Глянь в сторону rwmutex (один писатель, много читателей).

beastie ★★★★★
()

см. readers-writer locks (pthread_rwlock)

Iron_Bug ★★★★★
()

Может быть имеет смысл сделать по mutex на каждый элемент массива? Или это только усугубит ситуацию?

Усугубит.

Подумай в сторону мьютексов на блоки данных по диапазону N1..N2, N2+1..N3, ...

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

PPP328 ★★★★★
()

Иди бухай !!!! Какие нахер мутенсы адреса в массив складываеш возвратами от функций а в них мутекс лок и юнлок тоесть у тебя массив функций и каждая хранил адрес от маллока для массива ёпта я не пил два года мляяяяяяя я спасть мтиру мир с новым нгодом э

Deleted
()

Лор уже не торт. Ни один регистрант не спрашивает, что за задача вообще. Может ты из последовательного порта данные аж на 300 бод читаешь. Т.е. поток чтения 100500 триллионов раз в пикосекунду проверяет наличие данных. Переполнение в принципе невозможно. Но нет - давай лочить каждый элемент.

anonymous
()
Ответ на: комментарий от anonymous

Задача в продолжение вот этой темы: Проверка возвращаемого значения при Compare and Swap

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

Логика работы выглядит следующим образом.

Запись данных:

  1. посчитать куда писать данные
  2. записать новые границы данных (номер первого хранимого фрейма и последнего)
  3. записать сами данные

Чтение данных:

  1. посчитать откуда читать данные
  2. прочитать данные

При записи данных номер первого и последнего фреймов записываются в структуру, которая находится в массиве mTimeBoundsQueue. В классе CARingBuffer есть сам массив, а так же поле mTimeBoundsQueuePtr, которое позволяет определить номер текущего элемента массива с помощью вычисления остатка от деления mTimeBoundsQueuePtr на размер массива. Чтобы сделать запись в массив более надежной в структуре имеется поле mUpdateCounter, которое служит, своего рода контрольным числом элемента массива. Проверка работает следующим образом. При подсчете места, откуда нужно прочитать данные функция GetTimeBounds считывает текущий элемент массива mTimeBoundsQueue, заполняет поля startTime и endTime, после чего проверяет, что поле mUpdateCounter и номер текущего элемента массива совпадают (они не будут совпадать, если пока заполнялись поля startTime и endTime поток, читающий данные заснул, а поток пищущий данные успел понаписать новых элементов в массив mTimeBoundsQueue).

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

Верно ли я понимаю, что такое поведение возможно или я чего-то не учитываю?

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

Goganchic ★★
() автор топика

На самом деле можно сделать отдельные mutex на чтение и запись в кольцевой буфер, а указатели на элементы сделать volatile. При правильной реализаций будет потокобезопасно.

Например:

1. Заблокировать mutex чтения
2. Сравнить указатель на начало и конец данных, если равны, то ждать (либо busyloop, либо condition variables), либо вернуть ошибку (разлочив mutex)
3. Считать элемент, затем инкрементировать позицию начала (если достигнет конца, обнулить)
4. Перейти к шагу 2, если надо считать больше байт, иначе разлочить mutex
1. Заточить mutex записи
2. Убедиться, что в буфере есть место, сравнив правильно указатели на начало и конец, если места нет, то вернуть ошибку, либо ждать, пока условие изменится
3. Записать элемент, затем инкрементировать позицию записи (обнулить, если дойдет до конца)
4. Отпустить mutex

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

Если у тебя один читатель и один писатель, то оверхеда от блокировок не будет (ведь блокировка mutex всегда будет происходить мгновенно, потому что его никто не держит).

KivApple ★★★★★
()
Последнее исправление: KivApple (всего исправлений: 5)
Ответ на: комментарий от Goganchic

хочу запилить свой кольцевой буфер и думаю как лучше это сделать

Есть как минимум 3 подхода к таким задачам:

  • Использовать примитивы синхронизации операционной системы (pthread например) - простой, надежный, но не самый производительный вариант
  • Использовать атомарные операции (есть не только CAS, но и атомарное сложение/вычитание/некоторые битовые операции) - это требует более вдумчивого проектирования, но в некоторых случаях может быть быстрее кода с ОС-локами. Нужно иметь в виду что такие алгоритмы хоть и называются «lock-free», на самом деле делают lock на шине данных для обновления атомарной переменной
  • Использовать тот факт, что многие платформы (x32/x64 и как минимум некоторые ARM) обновляют правильно выровненные небольшие куски памяти (8/16/32/64 бита) атомарно. То есть, если один поток что-то записывает в 64-битное целое (выровненное по границе 64 бит), то остальные потоки (через время, когда синхронизируются кеши или после принудительного HW memory barrier-a) увидят это значение именно так, как оно писалось. Такой подход требует еще более аккуратного проектирования, но можно делать настоящие «wait-free» алгоритмы без локов

Теоретически можно комбинировать подходы, но на практике как правило вы чем-то ограничены. Готовые реализации и размышления гуглятся по «lock-free ring buffer», «wait-free ring buffer» и т.п.

Deleted
()

Делай по rw мьютексу на слот.

pon4ik ★★★★★
()
Ответ на: комментарий от KivApple

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

deep-purple ★★★★★
()
Ответ на: комментарий от Deleted

Использовать тот факт, что многие платформы (x32/x64 и как минимум некоторые ARM) обновляют правильно выровненные небольшие куски памяти (8/16/32/64 бита) атомарно.

Для этого лучше использовать ключевое слово _Atomic - https://en.cppreference.com/w/c/language/atomic

SZT ★★★★★
()
Ответ на: комментарий от SZT

Для этого лучше использовать ключевое слово _Atomic

Не, это не про ту атомарность. Этот _Atomic говорит компилятору о том, что операции с этой переменной будут с префиксом LOCK (или что-то вроде того). Это не всегда приемлемо. Если несколько вычислительных ядер пытаются одновременно что-то делать с такой «атомарной» переменной, они будут ждать друг друга, производительность может просесть.

У Intel есть такие гарантии:

8.1.1 Guaranteed Atomic Operations

The Intel486 processor (and newer processors since) guarantees that the following basic memory operations will always be carried out atomically:

  • Reading or writing a byte
  • Reading or writing a word aligned on a 16-bit boundary
  • Reading or writing a doubleword aligned on a 32-bit boundary

The Pentium processor (and newer processors since) guarantees that the following additional memory operations will always be carried out atomically:

  • Reading or writing a quadword aligned on a 64-bit boundary
  • 16-bit accesses to uncached memory locations that fit within a 32-bit data bus

У ARM64 тоже есть похожие гарантии, но армов разных много, не факт что это распространяется на все.

Это только о записи в память (не об атомарной модификации). Но наверное можно придумать wait-free алгоритм кольцевого буфера(по крайней мере single producer/multiple consumers), которому этих гарантий будет достаточно.

Deleted
()
Ответ на: комментарий от Deleted

У Intel есть такие гарантии:

Это гарантии для конкретных процессоров конкретной архитектуры. А если говорить вообще(т.е. задача стоит написать переносимый между разными архитектурами код на Си), _Atomic как раз нужен.

Если требуется сделать только под какую-то конкретную архитектуру, это можно еще решить ассемблерной вставкой или либой на ассемблере.

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

если говорить вообще, а не о конкретных архитектурах, С и С++ не позволяют использовать lock-free в силу отсутствия lock-free операций в стандартных библиотеках, или я не прав?

next_time ★★★★★
()
Ответ на: комментарий от next_time

при чём тут стандартные библиотеки? это архитектурозависимые вещи.

Iron_Bug ★★★★★
()
Ответ на: комментарий от next_time

Если говорить об _Atomic то это никакая не библиотека, это фича языка (стандарта), и компилятор (реализация стандарта) может не поддерживать этот _Atomic, а может и поддерживать:

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

Atomic type specifiers shall not be used if the implementation does not support atomic types (see 6.10.8.3)

SZT ★★★★★
()
Ответ на: комментарий от SZT

C99, да ещё и conditional feature that implementations need not support

такое себе для написания переносимого кода, ну будем считать, что вы правы

next_time ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.