[СИ] mmap-массив и синхронизация.

Работать будет, «чтением запись не испортишь».

Но у тебя много позже что-нибудь будет «отваливаться». Перед тем как двигаться дальше советую прочитать http://en.wikipedia.org/wiki/Futex.

При замене флажков на фьютексы на них можно будет ждать подобно events в mustdie.

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

А почему бы не использовать мьютексы или хотя бы простенький flock?

А не получится ли так.
sizeof(int)=2
процессор читает за раз 8 байт.
Два процесса пишут одновременно в соседние
байты этой восьмерки.
Один прочитал, изменил 2 байта, но не успел записать,
сохранил где-то в регистре.
В это время другой процесс делает то же самое с
соседними байтами и успевает записать их.
Потом первый процесс ранее сохраненное записывает
на тоже место (8 байт), вторая запись пропадает.

Вот блокировки и сведут к минимуму вероятности коллизий.

При замене флажков на фьютексы на них можно будет ждать подобно events в mustdie.

Может не стоит связываться с фьютексами. Работа с ними ИМХО должна быть только внутри системных библиотек и обычные пользовательские программы ничего не должны знать о них.

А поможет ли тут volatile?
И всего операций с массивом:
if(arr[i]==0)
arr[i]=1;
тут что должно быть volatile, разве что сам массив.

А какой окончательный ответ?
Отрицательный?

А не получится ли так.

Если ты не делаешь явных атомарных операций, то нельзя быть уверенным, что эти операции будут атомарными. //Всегда ваш К.О.

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

Вот ссылка

http://www.ibm.com/developerworks/linux/library/l-linux-synchronization.html

посмотри раздел Atomic operations. Сам я эти не пользовался, так что почитай внимательно, может оно тебе поможет.

А вообще, используй мьютексы. Самый простой путь.

> Может не стоит связываться с фьютексами. Работа с ними ИМХО должна быть только внутри системных библиотек и обычные пользовательские программы ничего не должны знать о них.

Отчасти согласен, но с другой стороны condition variables в posix часто не применимы. Например из сигналов нельзя пробудить поток через subj.

Поэтому я рассматриваю futexы как один из базовых примитивов, а condition variables как унаследованную кривизну.

я бы отдал каждому процессу не байт, а сразу целый блок, по размеру кратный блоку файловой систему. В главном процессе отображал сразу весь файл на чтение, а в дочерних/управляемых - только конретный блок закреплённый за процессом. А между процессами в таком случае можно обойтись сигналами :) без семафоров и блокировок

>Тест проходит хорошо. Везение. А как на самом деле?

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

volatile с т.з. абстрактного C environment безразличен, поскольку в этом коде за присваиванием следует sequence point. Это скорее защита от неправильной оптимизации компилятора.

Для нормального кода нужны механизмы блокировки. Кроме того, непонятно, что считает родительский процесс, если массивы в начале подсчета и в конце отличаются. То, что он насчитает 0 или n, не означает, что там в какой-либо момент было 0 или n единиц.

Из-за каой-то ерунды, из-за каких-то байтов,
рискованно, слишком рискованно.
А как было бы хорошо. Особенно не в этой
задаче, а в других.

Родительский процесс считает нагрузку сервера.
Разумеется, есть некоторая погрешность. Нагрузка
меняется непрерывно. Но уловить пики нагрузки
для размножения, наверно, можно. Усреднять.

Можете сделать другой костыль, например, «выдавать» текущие данные в shm-буфер по требованию. Т.е. клиент создает область разделяемой памяти, сообщает при помощи сигнала, очереди сообщений или иного способа ее идентификатор серверу, тот размещает данные и сообщает о готовности области. Но, ИМХО, это будет намного сложнее обычных блокировок.

> sizeof(int)=2

процессор читает за раз 8 байт.

Два процесса пишут одновременно в соседние

байты этой восьмерки.

все должно быть в порядке, или linux на этой архитектуре
работать не будет.

но в gcc подобные баги были. точнее, это было «by design».

на самом деле процессор читает/пишет cache line, это в
любом случае «много». hardware должно корректно разруливать
конфликты.

еще раз, я говорю только про архитектуры, поддерживаемые
linux.

>на самом деле процессор читает/пишет cache line, это в любом случае «много».

В случае естественного выравнивания указателей. ;)

>В случае естественного выравнивания указателей. ;)

Либо неестественного, но чтобы не совсем уж неестественного. ;)

> А как на самом деле?

На самом деле так и происходит.

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

Убедись, что дочерние процессы никогда не попытаются этого сделать.

Кроме того, родительский процесс _никогда_ не будет располагать верной информацией о состоянии всего массива.

Если это приемлемо, никакого риска нет.

> volatile с т.з. абстрактного C environment безразличен

Это скорее защита от неправильной оптимизации компилятора.

и это тоже. а вообще см http://gcc.gnu.org/wiki/Atomic/GCCMM/DataRaces
в частности, «This needs to be enforced in GCC».

это как раз недавно обсуждалось с gcc team где-то, но я
не помню где. может даже и offlist.

> В случае естественного выравнивания указателей. ;)

да, конечно, само собой. без natural alignment и говорить
не о чем.

>и это тоже. а вообще см http://gcc.gnu.org/wiki/Atomic/GCCMM/DataRaces

в частности, «This needs to be enforced in GCC».

Спасибо, почитаю.

да, конечно, само собой. без natural alignment и говорить не о чем.

Тут просто припомнились всякие ужасти из начала 2000-х вроде: arch/alpha/kernel/traps.c: do_entUna(). :-) Хотя, конечно, и без такого нюансов хватает.

Когда я говорил о других задачах, то имел в виду
вот что. Я вспомнил.

Возможно ли такое:
Всё наоборот.
Один главный процесс пишет. Другие только читают.
Без синхронизации.

Главный
arr[i]=0; или arr[i]=1;

Другие
if(arr[i] == 0)

Это сработает?

>Это сработает?

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

Если интересно, о модели доступа к разделяемой памяти в linux можно почитать в Documentation/memory-barriers.txt

Вот схема. Тема: «Многопоточность Linux. Mutex'ы»
Многопоточность Linux. Mutex'ы (комментарий)

Один главный процесс и 100 рабочих.
Главный должен без очереди получать блокировку.
Эта схема основана на том, что главный в любой момент
может установить сhlock = 1; Без синхронизации.
Рабочий процесс, взявший внешнюю блокировку m2,
и завидев этот флаг, подвисает на вспомогательном m3.
Давая тем самым главному возможность получить внутреннюю m1.

Это не полное решение задачи. Очередность рабочих на
усмотрение системы. Зато как просто.

char volatile chlock=0;  //--- глобальная ---

    //--- child ---

    lock(m2);        //--- вошли во внутренний двор (по одному) ---
    if(chlock != 0){ //--- а не заявил ли о себе главный? ---
        lock(m3);    //--- если да, то ждем освобождения ---
        unlock(m3);
    }
    lock(m1);
    //--- ... ---
    unlock(m1);
    unlock(m2);

    //--- parent ---

    lock(m3);         //--- заряжаем мутекс для блокировки дочернего ---
    сhlock = 1;       //--- заявляем о себе ---
    lock(m1);
    //--- ... ---
    unlock(m1);
    сhlock = 0;
    unlock(m3);

Вот эту задачу я имел ввиду.

> if(chlock != 0){ //--- а не заявил ли о себе главный? ---

lock(m3); //--- если да, то ждем освобождения ---

unlock(m3);

не, это racy. я не уверен, что я вообще идею понял, но
m2 как будто не имеет смысла совсем.

chlock может быть уже изменен parent'ом, но child этого
еще не видит. это нужно проверять под m3.

другое дело, что и вреда особого не будет, все равно оба
берут m1.

так что я запутался.

можно поднять приоритет главному процессу и ипользовать
pi futex (я забыл, как это в libpthread называется).

m2 вот для чего:
на m1 висит не более одного процесса.
А если все встанут в очередь на m1,
то к нему не пробиться.
А так главный дождал пока один отработает
и получает блокировку.

а m3 чтоб завидевшему флаг было на чем повисеть

> m2 вот для чего:

да я понял. а смысл? если сhlock = 1 то главный процесс
(игнорируя «details») уже взял m1, или спит в ожидании.

в обоих случаях можно спокойно спать на lock(m1).

еще раз, я игнорирую всяческие in-between случаи, напр
главный выставил сhlock = 1 но еще не вызвал lock(m1).

А если все встанут в очередь на m1,

он же fair.

> > А если все встанут в очередь на m1,

он же fair.

стоп! я, похоже, соврал... потом посмотрю.

Спит в ожидании.
и рабочий заснет в ожидании на m1.
и кто первый получит блокировку не известно.
А вслед за этим рабочим придет другой и третий.
Там в теме сначала и писали, что очередность
не известна. Главный тогда будет конкурировать
с рабочим.
А так пока он не снимет m3, новые рабочие не
пройдут.

Вот если убрать этот if(), то вслед за снятием
блокировок m1 и m2, туда проскочит кто-то из рабочих
и повиснет на m1, конкурент. А главный за это время
еще не успеет получить блокировку.

> > он же fair.

стоп! я, похоже, соврал... потом посмотрю.

нет, похоже pthread_mutex это, все-таки FIFO. mostly.
но утверждать с уверенностью не буду, не хочу сейчас
разбираться с этим кодом в glibc.

> и рабочий заснет в ожидании на m1.

и кто первый получит блокировку не известно.

еще раз. если mutex не FIFO - тогда конечно. но
pthread_mutex, по моему fair (в linux).

> Микросекунды не в счет.

Если микросеунды не в счет, что тода в счет? Зачем нужна вся эта акробатика, особенно с несколькими мютексами? Расходы на несколько мютексов в случае конфликта съедят весь выигрыш от большей параллельности.

> Вот если убрать этот if()

А главный за это время

еще не успеет получить блокировку.

это возможно. но это возможно и c этим if().
я же писал, эта проверка racy.

> это возможно. но это возможно и c этим if().

я же писал, эта проверка racy.

хотя я, наверное, не понял, что ты подразумеваешь
под «еще не успеет получить блокировку.».

Подразумеваю, что главный как висел, так пока еще и висит.
А к нему присоединится рабочий, и вместе будут висеть.
И кто первый получит блокировку не известно.

А почему флаг не будет виден? Пусть один еще не увидел
и проскочил, но следующие увидят.

tailgunner
Так уж вышло от начальной задачи перешли к другой.

> Подразумеваю, что главный как висел, так пока еще и висит.

А к нему присоединится рабочий, и вместе будут висеть.

И кто первый получит блокировку не известно.

эта... я ведь уже несколько раз написал про fairness/FIFO ;)

насколько я понимаю, по умолчанию pthread_mutex is fifo.
по крайней мере «почти», не уверен про «lucky bastard»/etc.
правда, я не уверен на 100%.

это значит, что в linux подобная оптимизация смысла не имеет.

Я вот сошлюсь на ответы в той теме других людей.
У dave**** четыре звездочки.

А если после дочернего потока обе блокировка
возьмет другой дочерний, и главный поток
опять останется заблокированным?
dave****
----------------------------------------

Спасибо! Я думал об этом)
Т.е.: дочерний поток держит 2 мьютекса (m1 и m2).
В это время «главный поток» находится в состоянии
блокирования и ждет своего m1. После завершения
работы дочерний поток
1) Освобождает m1
2) Освобождает m2
Следующий дочерний поток
3) Захватывает m2
4) Пытается захватить m1

Разве время, которое прошло от 1) до 3) гарантирует нам,
что «главный поток» захватит m1?
nitroxolyne
------------------------------------

Согласен с товарищем dave. Время на освобождение ресурса
дочерним потоком не дает гарантий захвата ресурса «главным потоком»
nitroxolyne

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

> Я вот сошлюсь на ответы в той теме других людей.

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

У dave**** четыре звездочки.

у меня (только что посчитал) тоже ;) не обращай на эту
пузомерку внимания.

посмотрел, частично даже вспомнил.

в ядре futex реализован как fifo для SCHED_OTHER tasks,
иначе по rt_priority. там простой plist в futex_hash_bucket.

в glibc, вроде бы (не хочу действительно читать этот код),
по default никакой отсебятины в этом смысле.

может быть, fastpath и не fair (lucky bastard), просто не
могу сейчас понять, но это в любом случае маловероятно.

только это... про user-space я не 100% уверен, но почти.