Comments 42
Как говорится в священном писании:
Issue 6
IEEE Std 1003.1-2001/Cor 2-2004, item XBD/TC2/D6/26 is applied, adding pthread_t to the list of types that are not required to be arithmetic types, thus allowing pthread_t to be defined as a structure.
откуда следует, что pthread_t — это не обязательно арифметический тип. Это может быть и прозрачная структура. Как следствие, попытка инициализировать её нулем некорректна.
class mutex
{
private:
std::atomic<pthread_t> mLock;
public:
explicit mutex():mLock{0}
{
}
Да и вообще в общем случае завернуть её в атомик не получится по той же самой причине.
Во вторых если мы говорим о Linux в первую очередь, то pthread_t это unsigned long int.
В третьих, сомневаюсь, что этот элемент (XBD/TC2/D6/26), в какой-либо распространнённой ОС применяется. Я-бы предположил, что в целях совместимости pthread_t в большинстве систем останется арифметическим, либо может быть имплементирован как указатель на структуру (что оставлят его арифметическим).
Но это не отменяет вашей правоты, и для каждой ОС нужно будет убедиться, что pthread_t арифметический.
Нет, ну если у самого Саттера то конечно да. Это весомый аргумент.
> Во вторых если мы говорим о Linux в первую очередь, то pthread_t это unsigned long int.
Как там было выше…
========
NB: Всё обсуждаемое касается разработки на C++ под Linux, но может быть применимо ко всем POSIX.1-2008 совместимым системaм (с оглядкой на конкретную реализацию).
========
Все-так скорее «Все обсуждаемое применимо сугубо для Linux и не применимо к остальным POSIX совместимым платформам» т.к. вы делаете фундаментальные допущения, которые верны и то с оговорками только для Linux.
> В третьих, сомневаюсь, что этот элемент (XBD/TC2/D6/26), в какой-либо распространнённой ОС применяется. Я-бы предположил, что в целях совместимости pthread_t в большинстве систем останется арифметическим, либо может быть имплементирован как указатель на структуру (что оставлят его арифметическим).
Неверное предположение. Первое, что приходит в голову — *BSD. Второе — почти уверен что QNX. Третье — скорее всего остальные *NIX. Сугубо для проформы:
github.com/freebsd/freebsd/blob/master/sys/sys/_pthreadtypes.h
Просто потому, что pthread_t нигде не используется по значению. Мы всегда оперируем указателем на этот тип. Детали реализации по-определению скрыты от пользователя и он не должен делать каких-либо предположений на этот счет. Как следствие, гораздо удобнее объявить его как прозрачную структуру чтобы упростить себе жизнь внутри реализации.
Вот сразу из вашей-же ссылки на исходники BSD:
typedef struct pthread *pthread_t
На этом вопрос можно считать закрытым, т.к. никто в здравом уме не будет ломать совместимость систем.
Если конечно очень хочется занудствовать, то найдите ссылки на исходники с ОС, где pthread_t не указатель или интегральный тип.
pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_equal.html#
Все остальное UB. Как эксперимент на попробовать здесь и сейчас — согласен, забавно. Но как тенденция — навряд ли.
PS: Если уж мы говорим за «на Linux» то он, родимый, по этому поводу в своем мане говорит, что:
NOTES
The pthread_equal() function is necessary because thread IDs should be considered opaque: there is no portable way for applications to directly compare two pthread_t values.
Т.е. с практической точки зрения, всё прекрасно будет работать, с вышеупомянутой оговоркой.
Хотя, как я уже заметил в самой статье, — эти костыли просто плохо, предоставляемое системной лучше.
Системный семафор построен на спинлоках или на обычных мьютексах
./kernel/locking/rwsem-spinlock.c
Но в glibc (см. sem_waitcommon.c) используются как атомарные операции (попытка получить без блокировки: __new_sem_wait_fast (struct new_sem sem, int definitive_result)), так и атомарные + ожидание по времени (__new_sem_wait_slow (struct new_sem sem, const struct timespec *abstime)) в do_futex_wait (sem, abstime).
Вообще семафор имеет среди прочего интерфейс sem_timedwait, что намекает на необходимость использования ожидания по времени в том числе.
Так вот вот это ожидание с квотой времени, которое не поднимается до уровня userland очень классно экономит ресурсы. Т.к. с каждым nanosleep в userland мы проваливаемся до ядра там наш поток перепланируют, потом мы просыпаемся, потом понимаем что нужно ждать ещё и опять спим. Вобщем это результат с lock-free, вполне нормально объясняет.
Вот так ...
Алгоритм тестов простой, запускается N потоков, каждый из этих потоков ожидает на одном и том-же семафоре, в случае срабатывания семафора, инкрементирует аттрибут wake для данного потока. В деструкторе печать значения wake.
В основном потоке, после старта N-ждущих, получаем срез времени (старт), запускаем sem_post() на М итераций, получаем срез времени (стоп), принудительно останавливаем все потоки (получая печать результатов wakes на экран), и выводим результат стоп-старт в милисeкундах для M итераций sem_post().
Боюсь мои исходники вам не пригодятся, т.к. они жёстко на библиотеки LAppS завязаны. Но я думаю вы по тому-же алгоритму, что я привёл выше без труда реализуете тест и получите свои результаты.
Lock-free mutex невозможен, ведь задача мьютекса — блокировать. Для того, чтобы алгоритм назывался Lock-free, недостаточно добавить в него спинлок на атомике! Должно выполняться еще одно условие: любой провал спинлока означает, что другой поток успешно продвинулся.
Более слабое условие звучит так: если системный планировщик почему-то решит, что только один поток достоин получать процессорное время, то этому самому потоку ничего не должно помешать. Разумеется, в ситуации с мьютексом не выполняется даже это.
Поэтому и вся затея со сведением мьютекса исключительно к спин-локам обречена на провал, независимо от того как ее пытаются обозвать и обосновать.
И чтобы не жечь под нагрузкой процессор впустую — надо бы вместо nanosleep откатываться на обычное решение с mutex и condition variable.
И не нужен mutex с condition_variable, т.к. они ни чем не лучше POSIX семафоров. А вышеприведённая имплементация не хуже mutex с condition_variable. По крайней мере на моих тестах.
А вы статью не внимательно читали. nanosleep, как-раз и не зжёт процессор.
Но все равно процессорное время тратится впустую.
А вышеприведённая имплементация не хуже mutex с condition_variable. По крайней мере на моих тестах.
Ну нет, вышеприведенная реализация — как раз хуже чем mutex с condition_variable. По крайней мере, в ситуации когда все потоки сделали wait, и никто не делает post (чему эта ситуация соответствует — высокой нагрузке или простою — зависит от того как семафор используется). Возможно, этой ситуации просто нет в ваших тестах.
int nanosleep(const struct timespec rqtp, struct timespec rmtp);
Но все равно процессорное время тратится впустую.
Нет, оно отдаётся другим потокам.
man nanosleep(3)
int nanosleep(const struct timespec *rqtp, struct timespec *rmtp);
Description
The nanosleep() function shall cause the current thread to be suspended from execution until either the time interval specified by the rqtp argument has elapsed or a signal is delivered to the calling thread, and its action is to invoke a signal-catching function or to terminate the process.
Это кстати и отвечает на вторую часть вашего коментария. И по тестам, нагрузка на ЦП при использовании nanosleep, мало чем отличается от системной реализации, т.к. там также семафор который должен быть заблокирован, будет отправлен в сон, а также переложен в конец очереди.
В пустую тратится не то время про которое вы подумали, а время в течении которого переключаются контексты плюс время на проверку условия цикла.
Да. Об этом я и в статье написал. По моему с condition_variable будет экономнее только если использовать notify_one(), a если notify_all(), то даже хуже. ведь там и на блокировке мьютекса контекст переключается и на вызов к wait() и на notify. Вообще нужно считать и тестировать. Потестирую сейчас пожалуй. И сообщу.
Протестировал. Если вас устроит такая поделка на condition_variable вместо семафора:
class SemEmuCond
{
private:
std::mutex mMutex;
std::condition_variable mCond;
size_t counter;
public:
SemEmuCond():mMutex(),mCond(),counter(0){}
void post()
{
std::unique_lock<std::mutex> lk(mMutex);
mCond.wait(lk,[this]{++counter; return true;});
mCond.notify_all();
}
void wait()
{
while(1)
{
std::unique_lock<std::mutex> lk(mMutex);
mCond.wait(lk);
if(counter>0)
{
--counter;
break;
}
}
}
};
То результаты печальные:
- терминация потока ожидающего на подобном семафоре приводит к UB.
- производительность:
Started 4 EmuCond threads waiting on a semaphore
CondEmu semaphores test. 10000000 of posts for 4 waiting threads have taken 5349 miliseconds
CondEmu semaphores test. Post latency: 0.5349ns
По потокам проблема, см п. 1
20 threads:
CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 12529 miliseconds
CondEmu semaphores test. Post latency: 1.2529ns
Thread(EmuCond) wakes: 353156
terminate called without an active exception
Аварийный останов
т.е. хуже.
Там как-бы итак мьютекс эксклюзивно локируется. Заменил на ++counter;
Результат:
Started 20 EmuCond threads waiting on a semaphore
CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 12106 miliseconds
CondEmu semaphores test. Post latency: 1.2106ns
Т.е. выигрышь 5% относительно предыдущего.
notify_one() — плохо, т.к. будить будет последовательно, а если post() быстрее потребления и аппаратных потоков в системе например 4-е, то при пробуждении 3 консамера должны суметь декрементировать семафор практически одновременно.
Как подтверждение результат с notify_one():
Started 20 EmuCond threads waiting on a semaphore
CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 22821 miliseconds
CondEmu semaphores test. Post latency: 2.2821ns
> Наконец, куда делись ваши атомики? Я же предлагал использовать это решение вместо nanosleep
Вы хотите использовать только нотификацию condition_variable для ожидания события? Дошло.
Фигня получилась. Тут тебе и мьютекс, тут тебе и атомики тут и кондишн-вар, я пока делал понял, что фигня будет. Как результат:
… 10000000 of posts for 20 waiting threads have taken 12704 milisecond
Post latency: 1.2704ns
Т.е это вообще не вариант, а учитывая что потоки произвольно теперь убивать нельзя пока они на кондиш-не ждут, то вообще но-гоу.
Во втором и третьем кейсах, я так понимаю, вся lua-часть выполняется в один поток, и где-то крутится цикл ожидания событий? В таком случае lock-free невозможен, опять-таки, исходя из задачи.
Во втором и третьем кейсах, я так понимаю, вся lua-часть выполняется в один поток, и где-то крутится цикл ожидания событий? В таком случае lock-free невозможен, опять-таки, исходя из задачи.
Нет не верно. Потоков Lua может быть столько сколько инстансов каждого сервера выполняется. Поступление событий по сети (в моих условиях), заведомо медленнее чем их обработка в потоках lua (парадокс, но на echo тестах это так). И простое отключение iptables производительность сервера увеличивает на 30%… вот как…
«Любой провал спинлока означает, что другой поток успешно продвинулся» — точнее, другой поток получил лок. Это deadlock freedom, самое слабое условие алгоритмов с блокировками.
«если системный планировщик почему-то решит, что только один поток достоин получать процессорное время, то этому самому потоку ничего не должно помешать» — это obstruction freedom, самое слабое условие lock-free алгоритмов. Это условие, кстати, сильнее deadlock freedom.
Сведение мьютекса исключительно к спин-локам в теории проблем не вызывает, т.к. спин-лок — одна из возможных реализаций мьютекса. Редко когда эффективная, это да.
А собственно смысл lock-free не в том, что мы никогда не ждём. Он в том, что в алгоритме не должно быть критических секций. То есть мьютексов/спинлоков не должно быть в принципе.
«Любой провал спинлока означает, что другой поток успешно продвинулся» — точнее, другой поток получил лок. Это deadlock freedom, самое слабое условие алгоритмов с блокировками.
Нет, deadlock freedom требует чтобы хоть какой-нибудь поток в конечном счете (Whatever the time T… then there is a time T' > T at which ...) успешно получил лок. А я писал о том, что происходит за одну итерацию, это и есть требование lock freedom.
Сведение мьютекса исключительно к спин-локам в теории проблем не вызывает, т.к. спин-лок — одна из возможных реализаций мьютекса/
Сведение мьютекса исключительно к спин-локам проблем, может быть, и не вызывает — но не позволяет мьютексу называться lock-free.
Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.
Когда операция — это получение блокировки через спинлок, провал операции — это провал спинлока.
Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.
Ну так я именно это и написал же. С чем вы спорите?
Должно выполняться еще одно условие
Как бы подразумевается, что как-то это условие сделать, и мьютекс становится lock-free. Хотя на самом деле единственный способ получить lock-free это выкинуть все мьютексы вообще.
вся затея со сведением мьютекса исключительно к спин-локам обречена на провал
Лучше было бы «вся затея с получением lock-free мьютекса», потому что сводить мьютекс к его реализации на спин-локах нам ничто не мешает, а заменять первые на вторые может даже оказаться полезно.
Вопрос в том, какие потоки, из уже ожидающих, пробудятся в случае когда ресурсы семафора снова станут доступны
А тут также как и в системной реализации, какой поток CFQ пробудит первым, тот и получит преимущество, а в среднем шансы у них действительно равные. POSIX многоядерности OS не специфицирует кстати, поэтому параллельного пробуждения планировщиком также не существует и кто-то становится «первым среди равных».
На системном семафоре у всех потоков 500000 +- 3000 сообщений. Практически поровну.
На вашем есть «удачливый» поток с 600000 сообщениями, и пара «неудачников» с 450000 — разница на треть.
Посмотрите плиз в этот комментарий, там пояснено почему вам эти исходники ничего не дадут и описан алгоритм теста. Напишите свои, это на пол часа работы.
А вы не думали использовать wait-free алгоритмы? Например, передачу сообщений между потоками можно делать через циклический буфер с двумя указателями. Каждый перемещает свой указатель, не ожидая других. Чтение чужого указателя и перемещение своего разделяем барьерами памяти — это гарантирует, что один другой не обгонит. Если надо надо слать многим потокам или принимать из разных мест — создаём по такому буферу на каждую пару и шлём через раунд-робин. Если хотим записать, а все буферы переполнены — либо подвисаем в ожидании, либо делаем что-то ещё. И наоборот, если хотим получить, а буферы пусты, то либо подвисаем, либо делаем что-то ещё. Вот тут я описываю использование горутин и каналов реализованных по этим принципам. А тут можно глянуть исходники.
«Lock-free, or not lock-free, that is the question» или «Здоровый сон хуже горькой редьки»