Как стать автором
Обновить

Комментарии 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}
      {
      }


Да и вообще в общем случае завернуть её в атомик не получится по той же самой причине.
Во первых не у меня, а у Саттера на одном из слайдов (сейчас даже не вспомню в каком из видео о прогрессе в работе над C++20 он этот код показывал).

Во вторых если мы говорим о 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 нигде не используется по значению. Мы всегда оперируем указателем на этот тип. Детали реализации по-определению скрыты от пользователя и он не должен делать каких-либо предположений на этот счет. Как следствие, гораздо удобнее объявить его как прозрачную структуру чтобы упростить себе жизнь внутри реализации.
Впрочем, если pthread_t сам по себе — это указатель на структуру, код выше вполне валиден т.к. арифметических операций над ним не производится но лишь присваивание или сравнение на равенство. Хотя выглядит все равно подозрительно.

Вот сразу из вашей-же ссылки на исходники BSD:


typedef struct  pthread         *pthread_t

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


Если конечно очень хочется занудствовать, то найдите ссылки на исходники с ОС, где pthread_t не указатель или интегральный тип.

А, вспомнил, что мне показалось таким неправильным в попытке запихнуть pthread_t куда-либо включая атомик. Даже если вы не проводите над ними арифметических операций, даже сравнивать два потока нужно не абы как но через pthread_equal()

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.
Основная проблема с UB, это то что Thread ID может быть инвалидным, именно тогда UB. pthread_self() всегда гарантируемо и предсказуемо вернёт одно и тот-же значение для того-же самого потока. Даже если pthread_t это указатель на структуру, то pthread_self() всегда вернёт один и тот-же адрес. unlock() может подвиснуть если заблокировавший мьютекс поток умер, не разблокировав его. Но тут уже неважно кто сравнивает значения pthread_t.

Т.е. с практической точки зрения, всё прекрасно будет работать, с вышеупомянутой оговоркой.

Хотя, как я уже заметил в самой статье, — эти костыли просто плохо, предоставляемое системной лучше.
НЛО прилетело и опубликовало эту надпись здесь
Системный семафор построен на спинлоках или на обычных мьютексах

./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 завязаны. Но я думаю вы по тому-же алгоритму, что я привёл выше без труда реализуете тест и получите свои результаты.

битая ссылка на LAppS (ithub вместо github)

Lock-free mutex невозможен, ведь задача мьютекса — блокировать. Для того, чтобы алгоритм назывался Lock-free, недостаточно добавить в него спинлок на атомике! Должно выполняться еще одно условие: любой провал спинлока означает, что другой поток успешно продвинулся.


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


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

Я с вами полностью согласен. Более того в приведённом семафоре (в отличии от мьютекса), это условие выполняется. Там как минимум 7-мь потоков параллельно в состоянии получить значение семафора(т.к. post() многократно быстрее). Однако, в событийно ориентированной системе, ждать приходится. Применимость чистого lock-free для моих кейсов вообще сомнительная и это просто эксперименты.
Нет, для семафора оно тоже в общем виде не выполняется. Потому что у него тоже есть достижимое состояние когда вызов lock будет ждать прихода другого потока неопределенно долго (а если оно недостижимо — то этот семафор нафиг не нужен).

И чтобы не жечь под нагрузкой процессор впустую — надо бы вместо nanosleep откатываться на обычное решение с mutex и condition variable.
А вы статью не внимательно читали. nanosleep, как-раз и не зжёт процессор. А семафоры в LAppS используются что-бы ждать событий. Из за латентности сетевого стека, кол-во операций post() в реальной системе (а не в синтезе), всегда медленнее операций чтения.

И не нужен 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;
       }
    }
  }
};

То результаты печальные:


  1. терминация потока ожидающего на подобном семафоре приводит к UB.
  2. производительность:

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
Аварийный останов

т.е. хуже.

Э… зачем вы делаете mCond.wait в post? Почему не notify_one? Зачем вы делаете mCond.wait в wait безусловно? Наконец, куда делись ваши атомики? Я же предлагал использовать это решение вместо nanosleep, а не вместо всего вашего алгоритма…
Вы правы в post() совершенно не нужно делать: mCond.wait(lk,[this]{++counter; return true;});
Там как-бы итак мьютекс эксклюзивно локируется. Заменил на ++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

Т.е это вообще не вариант, а учитывая что потоки произвольно теперь убивать нельзя пока они на кондиш-не ждут, то вообще но-гоу.
То есть с атомиками получилось столько же, сколько и без них, и это все — медленнее чем с нанослипом? А вы точно атомики снаружи мьютекса менали? :-)
Да точно. На самом деле всё ещё проще. Попробуйте сами. Это-же элементарно.
По поводу же применимости lock-free для ваших кейсов — тут все просто. В первом кейсе lock-free должны были применять авторы LibreSSL, а не вы.

Во втором и третьем кейсах, я так понимаю, вся 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 freedom описать. Только тогда стоит написать «провал операции» как более абстрактное, или вообще «хотя бы один поток выполнит операцию при любых действиях других потоков» — в вашем определении забыт случай с 1 потоком :-)

Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.

Когда операция — это получение блокировки через спинлок, провал операции — это провал спинлока.


Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.

Ну так я именно это и написал же. С чем вы спорите?

Наверное, с неудачной формулировкой.
Должно выполняться еще одно условие

Как бы подразумевается, что как-то это условие сделать, и мьютекс становится lock-free. Хотя на самом деле единственный способ получить lock-free это выкинуть все мьютексы вообще.
вся затея со сведением мьютекса исключительно к спин-локам обречена на провал

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

Так все правильно же. Достаточно выполнить невыполнимое условие — и мьютекс станет lock-free :-)

Если занудствовать дальше, то у автора получился «не честный» семафор, так как «настоящий» семафор должен гарантировать равный шанс для каждого ждущего потока при доступе к ресурсу, а тут уже простым счетчиком не ограничишься. Придется городить lock-free список ждущих потоков и т.д. Глядишь и скорость выровнится, по сравнению со стандартным семафором. А так — да, срезать углы можно, но надо понимать за счет чего.
Неверно. Если счётчик больше числа потоков консамеров, то выполнится параллельно столько потоков сколько система поддерживает (на самом деле каждый из них попытается выполнить атомарный декремент одного и того-же значения, что их всё равно выстроит в очередь). Более того посмотрите на код glibc там так-же при невозможности декрементировать счётчик поток уводится в сон (см комментарии выше), и также используются атомарные операции декремента. Вобщем этот семафор ничем не хуже системного, ровно с теми-же шансами на выполнение. Но суть статьи не в этом, а в том, что всё это от лукавого.
Я представляю как работает семафор и, не много, не об этом. Представьте что счетчик ресурсов исчерпан (нуль) и в этот момент еще 10 потоков пытаются захватить ресурс. Ясно что все они буду ждать пока ресурс не появится. Вопрос в том, какие потоки, из уже ожидающих, пробудятся в случае когда ресурсы семафора снова станут доступны. Хорошая реализация семафора должна пробуждать потоки гарантируя, в среднем, каждому ожидающему потоку равную возможность получить ресурс.
Вопрос в том, какие потоки, из уже ожидающих, пробудятся в случае когда ресурсы семафора снова станут доступны


А тут также как и в системной реализации, какой поток CFQ пробудит первым, тот и получит преимущество, а в среднем шансы у них действительно равные. POSIX многоядерности OS не специфицирует кстати, поэтому параллельного пробуждения планировщиком также не существует и кто-то становится «первым среди равных».
Не совсем с теми же.
На системном семафоре у всех потоков 500000 +- 3000 сообщений. Практически поровну.
На вашем есть «удачливый» поток с 600000 сообщениями, и пара «неудачников» с 450000 — разница на треть.
А тут как раз просто. Этот фокус элементарен, в этом тесте (см пояснения выше), некоторые потоки довольно долго вообще в сон не уходят, т.к. post() многократно быстрее чем wait(). Ведь 20 потоков ждут, каки-е то спят, а какие-то молотят, так вот преимущество у тех потоков, у которых квота процессорного времени не истекла, но вы их посчитайте, — 7 потоков с изначальным преимуществом (Core i7).
А можно ссылку на код с тестами?

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

А вы не думали использовать wait-free алгоритмы? Например, передачу сообщений между потоками можно делать через циклический буфер с двумя указателями. Каждый перемещает свой указатель, не ожидая других. Чтение чужого указателя и перемещение своего разделяем барьерами памяти — это гарантирует, что один другой не обгонит. Если надо надо слать многим потокам или принимать из разных мест — создаём по такому буферу на каждую пару и шлём через раунд-робин. Если хотим записать, а все буферы переполнены — либо подвисаем в ожидании, либо делаем что-то ещё. И наоборот, если хотим получить, а буферы пусты, то либо подвисаем, либо делаем что-то ещё. Вот тут я описываю использование горутин и каналов реализованных по этим принципам. А тут можно глянуть исходники.

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