Многопоточность Linux. Mutex'ы

Плохой lockless, очень плохой lockless. Обеспечит кучу секеса и геморроя на тему «почему иногда очередь состоит из одного элемента» (hint: голова очереди меняется раньше, чем будет корректно установлен элемент next головы). Корректно это делается только через CAS.

Плохой lockless, очень плохой lockless. Обеспечит кучу секеса и геморроя на тему «почему иногда очередь состоит из одного элемента» (hint: голова очереди меняется раньше, чем будет корректно установлен элемент next головы).

Это desired behaviour, есличо. Никакого секса, читай код.

>Никакого секса, читай код.

Чего там читать, если push помещает в начало очереди элемент с next == NULL и только затем меняет next? Не нужно быть семи пядей во лбу, что увидеть тут race condition и догадаться к каким забавным эффектам это обязательно приведет.

next текущего элемента устанавливает следующий элемент. Читай код.

Кстати, писать асмом не зная, что для лока шины в SMP-системах нужен префикс lock тоже не есть хорошо. Специально для таких случаев, кстати, есть http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html.

Использование __sync_val_compare_and_swap оттуда корректно решает race condition, а также гарантированно позволяет коду собираться и корректно работать на i486+, x86_64 и некоторых других архитектурах, об атомарных операциях которых я недостаточно осведомлен, чтобы поименно их перечислить.

> Представь, что в лочном решении тред тоже заснул в push. Всё стало гораздо хуже: остальные треды висят на локе,

Не «висят», а блокированы на семафоре.

пока этот засранец не вернёт его.

И шансов гораздо больше, что засранец получит процессорное время.

Кстати, писать асмом не зная, что для лока шины в SMP-системах нужен префикс lock тоже не есть хорошо.

Это потому что ты ассемблер не знаешь и чего-то там в левых книжках выискиваешь, чтобы mv подъе..ть: «Ага! Хреноваятель ты этакий! Я сам не знаю, но вот в левой книжке что-то пишут!». Я на ассемблере с 11 лет пишу (а сейчас мне 28), поэтому подъе..ть меня в этой теме сложно. Хотя и можно.

hint: «Intel® 64 and IA-32 Architectures Software Developer's Manual.Volume 2B: Instruction Set Reference, N-Z», страница 4-492.

И шансов гораздо больше, что засранец получит процессорное время.

Это со всех сторон хуже. В моём варианте латентность низкая и предсказуемая, входные данные (скажем, на 10G) из-за тормозов очереди потеряться не могут.

>next текущего элемента устанавливает следующий элемент.

А не судьба было queue сразу last назвать? Или это такая специальная обфускация? Тогда уж и твой push — это append.

Кстати, смешные рейсы от этого никуда не денутся: свежедобавленный(е) элемент(ы) будут «не видны» из соседних потоков при «неправильном» порядке переключения между тредами: добавляешь один элемент, переключение происходит перед old->next = ptr и в соседней нитке снова push. В итоге получаем смешную вещь: элементы вроде как добавлены (две штуки), а вроде как и не видны. То есть, при возврате из qmem_push нет гарантии, что твой элемент лежит в очереди, поскольку он мог быть присоединен к элементу, на который в очереди еще нет ссылки.

А не судьба было queue сразу last назвать? Или это такая специальная обфускация? Тогда уж и твой push — это append.

Ну вот на это можешь жаловаться, имена я действительно дурацкие даю ;)

Кстати, смешные рейсы от этого никуда не денутся: свежедобавленный(е) элемент(ы) будут «не видны» из соседних потоков при «неправильном» порядке переключения между тредами: добавляешь один элемент, переключение происходит перед old->next = ptr и в соседней нитке снова push. В итоге получаем смешную вещь: элементы вроде как добавлены (две штуки), а вроде как и не видны.

Это by design. И какой же это рейс? За что рейс-то? Ни одна сволочь не меняет память, которую может поменять другая сволочь (про атомарность и кто локи на самом деле делает - обсудили выше по треду). Нет потенциальных мест для рейсов - нет самих рейсов.

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

На момент возврата из qmem_push нет гарантии, что в варианте с локами тред оттуда вернется даже в ближайшее время. При ста одновременно кладущих тредах в худшем случае придётся ждать 99/N_ядер переключений. А это очень нефигово так по тактам.

Понятно, что моё решение - это trade-off, но его преимущества над локами с лихвой перекрывают недостатки.

>Я на ассемблере с 11 лет пишу (а сейчас мне 28), поэтому подъе..ть меня в этой теме сложно.

Чего тебя подъебывать? Ты же даже не знаешь, для 64-битных типов данных выравнивание адреса должно идти по 8-байтной границе. Причем ты как-то игнорируешь тот факт, что это в тех же интеловских мануалах написано.

Ну и вопрос на засыпку: в чем же состоит ошибка явного указания префикса lock перед xchg?

Чего тебя подъебывать? Ты же даже не знаешь, для 64-битных типов данных выравнивание адреса должно идти по 8-байтной границе. Причем ты как-то игнорируешь тот факт, что это в тех же интеловских мануалах написано.

Частично признаю, что надо было в мануал заглянуть. Хотя практический опыт говорит, что на феноме и нехалеме выравнивание на 8 против 4 для 64-битного целого никакой разницы не даёт. На core - да, есть разница. Но это нюанс данной архитектуры, а не общая черта для всех процессоров. Перечислять рекомендации по оптимизации, которые устарели вместе с процессорами, для которых они писались, можно до бесконечности.

Ну и вопрос на засыпку: в чем же состоит ошибка явного указания префикса lock перед xchg?

Я не говорил что это ошибка. Это ты сказал, что ошибка lock не использовать.

>За что рейс-то?

A race condition or race hazard is a flaw in an electronic system or process whereby the output and/or result of the process is unexpectedly and critically dependent on the sequence or timing of other events.

В данном случае самый что ни на есть рейс: если посреди одного push'а будет вызван другой, то на момент выхода из второго push'а существует вероятность того, что вновь добавленный в очередь элемент на самом деле в ней еще не находится. А появится он там только после того, как «проснется» нить первого push'а.

Переключение контекстов в Linux у нас вроде бы по умолчанию 100 раз в секунду происходит? Дано: 100 нитей, все lockless, переключение контекстов будет только «недобровольным» и если планировщик «уйдет» с push'ащей нити в «неподходящий попмент времени» (до того, как next уже предпоследнего элемента будет установлен в корректное значение), то все последующие элементы, добавляемые другими нитями в течинии следующей секунды не будут видны в очереди. Вроде ничего не напутал?

На момент возврата из qmem_push нет гарантии, что в варианте с локами тред оттуда вернется даже в ближайшее время.

В варианте с локами есть гораздо более клевая гарантия консистентности данных: на момент возврата из append гарантировано, что добавленный элемент находится в очереди.

При ста одновременно кладущих тредах в худшем случае придётся ждать 99/N_ядер переключений. А это очень нефигово так по тактам.

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

>Перечислять рекомендации по оптимизации, которые устарели вместе с процессорами, для которых они писались, можно до бесконечности.

Они не устарели, в официальном гайде по оптимизации от Intel до сих пор написано «выравнивать по 8-байтной границе».

Это ты сказал, что ошибка lock не использовать.

Я, кстати, искренне не знал, что для x* инструкций, работающих с памятью, протокол lock автоматически активируется.

В данном случае самый что ни на есть рейс: если посреди одного push'а будет вызван другой, то на момент выхода из второго push'а существует вероятность того, что вновь добавленный в очередь элемент на самом деле в ней еще не находится. А появится он там только после того, как «проснется» нить первого push'а.

Ну да! Тогда все параллельные вычисления - это один большой рейс :)

А где гарантия, что в момент времени t в лочном решении нужный элемент уже окажется в очереди? Не окажется, потому что «тред ещё висит на концептуально правильном локе».

Переключение контекстов в Linux у нас вроде бы по умолчанию 100 раз в секунду происходит? Дано: 100 нитей, все lockless, переключение контекстов будет только «недобровольным» и если планировщик «уйдет» с push'ащей нити в «неподходящий попмент времени» (до того, как next уже предпоследнего элемента будет установлен в корректное значение), то все последующие элементы, добавляемые другими нитями в течинии следующей секунды не будут видны в очереди. Вроде ничего не напутал?

Более-менее, ничего. Только ты не учёл, что данные в треды-фидеры не с потолка сыпятся, поэтому они волей-неволей полезут в ядро. А если треду-фидеру ну совсем нечего делать, то он может и yield() сделать. И разница будет в том, что yield() - это явная передача контекста, контроллируемая программистом, а подвисание на локе - нет.

В варианте с локами есть гораздо более клевая гарантия консистентности данных: на момент возврата из append гарантировано, что добавленный элемент находится в очереди.

И что она гарантирует? Что его ридер сможет немедленно прочитать? Нет, ибо ридер повешается на локе. Можно легко провести замеры throughput и latency для обоих решений (как только idle или другая добрая душа напишет грамотную и единственно верную очередь на локах :), смерить рулеткой и определить, у кого длиннее.

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

Инструкция cmpxchg нужна для организации семафоров, она тут не в тему. Если ты считаешь по другому, то сделай lockless queue на cmpxchg.

Они не устарели, в официальном гайде по оптимизации от Intel до сих пор написано «выравнивать по 8-байтной границе».

Скоро исчезнет. Нехалему на вообще какое-либо выравнивание (в пределах строки кэша) не пофиг в пределах шума (десятые или сотые доли процента).

Я, кстати, искренне не знал, что для x* инструкций, работающих с памятью, протокол lock автоматически активируется.

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

Получается эдакий спинлок, зато с гарантией того, что по выходу из qmem_push элемент действительно находится в очереди.

void qmem_push(qmem_t **head, qmem_t *elt) // it's really push, not append
{
    elt->next = *head;
    while (1) {
        qmem_t *p;
        p = __sync_val_compare_and_swap(head, elt->next, elt);
        if (elt->next == p)
            break;
        elt->next = p;
        sched_yield();
    }
}

Назвать его lockless, правда, язык не поворачивается.

Получается эдакий спинлок, зато с гарантией того, что по выходу из qmem_push элемент действительно находится в очереди.

И что эта гарантия даёт, кроме потраченных тактов? :) Общий лок в параллельной системе - это бутылочное горлышко, на котором вся параллельность сериализуется. Можно, конечно, в фидерах замутить try_lock, накапливая данные для того светлого момента, когда лок таки захватится, чтобы сразу пачку данных засунуть в очередь, но чем это лучше и проще? Больше абстракций, больше кода, больше сложности.

> Общий лок в параллельной системе - это бутылочное горлышко, на котором вся параллельность сериализуется.

Ну хоть кто-то об этом вспомнил. По-моему, задачу топикстартера и решать-то не следует.

Ну хоть кто-то об этом вспомнил. По-моему, задачу топикстартера и решать-то не следует.

Ну вот, а я так старался :(

>И что эта гарантия даёт, кроме потраченных тактов?

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

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

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

Ну вот в лочном решении сто раз сделали chunk_free, чанки гарантированно лежат в очереди, ожидая перемещения в пул свободных, а памяти всё нет, т.к. ридер висит на локе. В чём разница? Рыбку-то всё равно съесть не получается, а вот на органе крепко сидишь, с локом.

>Ну вот в лочном решении сто раз сделали chunk_free, чанки гарантированно лежат в очереди, ожидая перемещения в пул свободных

Чего это они там ожидают? Они уже в очереди свободных чанков и любой желающий может их оттуда извлечь.

Чего это они там ожидают? Они уже в очереди свободных чанков и любой желающий может их оттуда извлечь.

Ещё лучше! И эти люди говорят, что программы на Лиспе медленно работают!

> вот смотри. у тебя consumer просто тупо жжет CPU ожидая !NULL.

Нет.

ну как же нет, если да.

Читает до конца (на момент чтения), и всё.

ага. а встретив этот конец, судорожно мечется в цикле, ожидая следующего push.

> я все понимаю, этот код демонстрационный. на практике нам понадобится sleep/wakeup,

У тебя проф.деформация, это тут точно не нужно =)

да ладно. мне не очень понятно, что значит «тут», но такой polling редко оправдан.

> контроль за переполнением (если consumer не успевает),

И что? Обычная очередь также взорвётся, если кладут больше, чем берут.

да я не о том. просто представь, что тебе понадобится счетчик элементов inflight. по любой причине, скажем, для статистики.

и придется делать atomic_inc. и, внезапно, у нас уже 2 lock'а на шину. и это уже проигрывает spinlock-based критической секции. (да, «проигрывает» требует уточнения).

Я не согласен. В жизни проблем от локов не меньше, чем от рейсов.

да кто спорит.

и эта. я же не говорю, что так делать не надо. я сам так делал, и тому остались позорные свидетельства.

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

консьюмер будет голодать в борьбе за мьютекс

а вот это нужно наблюдать на практике, или доказывать.

Реши проблему ТС на локах, покажи код.

не решу. я не понимаю что на самом деле ему нужно.

> что я слышу? ты, наконец, готов признать, что perl рулит???

Между си и перлом, если выбирать,

начал хорошо, да.

на чём написать лисп,

ахтунг. моньяки в треде!

> представь, что 1-ый thread исчерпал свой time slice в qmem_push()
> прямо перед «old->next = ptr;».
> ...
>
Представь, что в лочном решении тред тоже заснул в push.

(ну, спать-то он там не должен, но preemption может быть)

Всё стало гораздо хуже: остальные треды висят на локе,

это необязательно хуже. это зависит. я же написал: не утверждаю, что это _всегда_ неприемлемо (иногда так даже и лучше).

Жду твой код :)

да какой код? еще раз, проблемы ТС я не понимаю, и перечитывать это обсуждение я уже не буду.

я могу только сказать, как лично я бы написал твой hello-world. я бы _начал_ с чего-нибудь вроде

struct elt {
        struct elt *next;
        ...
};

struct elt *first, *last;

pthread_mutex_t mutex;
pthread_cond_t pushed;

void queue(struct elt *elt)
{
        pthread_mutex_lock(&mutex);
        if (!first)
                first = elt;
        if (last)
                last->next = elt;
        last = elt;
        pthread_cond_signal(&pushed);
        pthread_mutex_unlock(&mutex);
}

struct elt *dequeue_all()
{
        struct elt *ret;

        pthread_mutex_lock(&mutex);
        while (!first)
                pthread_cond_wait(&pushed, &mutex);

        ret = first;
        first = last = NULL;
        pthread_mutex_unlock(&mutex);

        return ret;
}

(небось, даже в glibc уже что-то готовое есть, не знаю)

и только потом, если обнаружится что это тормозит, я бы стал думать про lockless/rcu/etc.

ага. а встретив этот конец, судорожно мечется в цикле, ожидая следующего push.

Это пример потребления. Нормальный pop() за раз возвращает 0 или 1 элемент.

да ладно. мне не очень понятно, что значит «тут», но такой polling редко оправдан.

Нет поллинга. См. выше.

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

Я тут говорю только про проблему ТС: 100 тредов пишут, 1 читает. На другой случай будет другое решение.

и только потом, если обнаружится что это тормозит, я бы стал думать про lockless/rcu/etc.

100 фидеров и 1 ридер - будет при сколь-нибудь активном траффике.

> > ага. а встретив этот конец, судорожно мечется в цикле, ожидая

> следующего push.



Это пример потребления. Нормальный pop() за раз возвращает 0 или 1

элемент.

ну. и как мы без polling'а узнаем, когда pop() вернет элемент?

Нет поллинга. См. выше.

см выше ;)> я просто не согласен с тем, что так делать _всегда и безусловно_ лучше.

Я тут говорю только про проблему ТС: 100 тредов пишут, 1 читает.

На другой случай будет другое решение.

и как же xchg() это может решить? не понимаю.

100 фидеров и 1 ридер - будет при сколь-нибудь активном траффике.

если у нас возникает contention - мы уже проиграли, и вот
эту задачу надо решать. скажем, пусть они пишут не по одному
элементу, а пачками. или, заведем 10 очередей на 100 producers,
consumer читает все. или еще что-то.

и все равно я не понимаю условия (точнее, отказываюсь принимать
это за правильную задачу). с какого перепуга у нас должен быть
такой contention, что он становится узким местом в _реальном_
приложении? benchmark - это да.

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

ну, будет у тебя push() работать в 2 раза быстрее, чем если бы
мы spinlock использовали. и что? не панацея это.

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

ну. и как мы без polling'а узнаем, когда pop() вернет элемент?

При пустой очереди pop() возвращает пустоту. Ему не нужно знать, когда там что-то появится. Нет элементов в очереди, значит, нет.

и как же xchg() это может решить? не понимаю.

Хотя бы тем, что ридер в этом contention не участвует. Да и лок на уровне ядра и на уровне аппаратуры - это две разные вещи.

ну, будет у тебя push() работать в 2 раза быстрее,

вот же гад, таки заставил меня писать код...

и даже не в два. а если еще spinlock оптимизировать, убрать оттуда relax, то разница еще меньше будет.

#define _GNU_SOURCE
#include <stdio.h>
#include <pthread.h>
#include <assert.h>
#include <unistd.h>
#include <sched.h>

#define xchg(ptr, x)						\
({								\
	__typeof(*(ptr)) __x = (x);				\
	volatile long *__ptr = (volatile void*)(ptr);		\
								\
	asm volatile("xchgq %0,%1"				\
		     : "=r" (__x), "+m" (*__ptr)		\
		     : "0" (__x)				\
		     : "memory");				\
})

pthread_barrier_t		tsync;
static volatile int		tstop;

static volatile long		g_data;
static pthread_spinlock_t	g_lock;

struct targ {
	int	cpu;

	long	nr_xchg;
	long	nr_lock;
};

static inline void set_cpu(int cpu)
{
	long mask = 1 << cpu;
	assert(sched_setaffinity(0, sizeof(long), (void*)&mask) == 0);
}

void *tfunc(void *arg)
{
	struct targ *targ = arg;

	set_cpu(targ->cpu);

	pthread_barrier_wait(&tsync);
	while (!tstop) {
		xchg(&g_data, 0);
		++targ->nr_xchg;
	}
	pthread_barrier_wait(&tsync);

	pthread_barrier_wait(&tsync);
	while (!tstop) {
		pthread_spin_lock(&g_lock);
		g_data = 0;
		pthread_spin_unlock(&g_lock);
		targ->nr_lock++;
	}
	pthread_barrier_wait(&tsync);

	return NULL;
}

#define NR_THREADS	2

int main(void)
{
	struct targ targ[NR_THREADS] = {};
	long nr_xchg = 0, nr_lock = 0;
	int i;

	pthread_barrier_init(&tsync, NULL, NR_THREADS + 1);
	pthread_spin_init(&g_lock, 0);

	for (i = 0; i < NR_THREADS; ++i) {
		pthread_t thr;

		targ[i].cpu = i;

		assert(pthread_create(&thr, NULL, tfunc, targ + i) == 0);
	}

	for (i = 0; i < 2; ++i) {
		tstop = 0;
		pthread_barrier_wait(&tsync);
		sleep(3);
		tstop = 1;
		pthread_barrier_wait(&tsync);
	}

	for (i = 0; i < NR_THREADS; ++i) {
		nr_xchg += targ[i].nr_xchg;
		nr_lock += targ[i].nr_lock;

		printf("t %d: xchg=%ld lock=%ld\n", i,
			targ[i].nr_xchg, targ[i].nr_lock);
	}

	printf("sum: xchg=%ld lock=%ld\n", nr_xchg, nr_lock);

	return 0;
}

> > ну. и как мы без polling'а узнаем, когда pop() вернет элемент?

При пустой очереди pop() возвращает пустоту. Ему не нужно знать,

ему не нужно, это понятно. я спрашивал, как caller может
узнать, что имеет смысл вызвать pop().

> и как же xchg() это может решить? не понимаю.



Хотя бы тем, что ридер в этом contention не участвует.

и много он добавит к contention, устроенному фидерами?

ему не нужно, это понятно. я спрашивал, как caller может

узнать, что имеет смысл вызвать pop().

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

и много он добавит к contention, устроенному фидерами?

Ну вот почему ты всё шиворот на выворот ставишь? :) Нужно задавать вопрос так: «Много ли 100 фидеров добавят контеншена одному ридеру?» То, что 100 фидеров между собой толкаются - это хрен с ним, кто-нибудь в очередь, да пишет. А вот что ридер участвует в этой толкотне - это абзац.