elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
JPoint 2016: Слайды и ссылки
elizarov

JPoint Logo Большое спасибо организаторам конференции JPoint 2016. Конференция получилась отличная, хорошая подборка докладов. Слайды моего доклада "Wait for your fortune without blocking" я уже выложил здесь.

JPoint Student Day тоже получился ничего, хотя и народу было не очень много. Cлайды с доклада "Многопоточное Программирование — Теория и Практика" выложены здесь.

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


  • 1
А как реализуется парковка? С помощью операции sleep или какая-то другая магия? Бегать по кругу в цикле хоть формально и lock-free, но, неформально большая бяка.


На Linux park реализован (в случае когда нужно действительно усыпить поток) через pthread_mutex_trylock+pthread_cond_wait (то есть на самом деле там внутри блокировочка) а на Windows через event объект и WaitForSingleObject на нем (то есть реально без блокировки).

А бегать по кругу не только формально lock-free, но и на практике wait-free. То есть не просте не бяка, а очень даже наоборот супер. http://research.microsoft.com/pubs/209106/paper.pdf

На практике, однако, в CAS-retry цикле считать сколько раз прокрутитились и если долго крутимся, то какую-нибудь случайную задержку начинать втыкать.

The WaitForSingleObject function checks the current state of the specified object. If the object's state is nonsignaled, the calling thread enters the wait state until the object is signaled or the time-out interval elapses.

Это thread sleep или я что-то опять не понимаю?

>А бегать по кругу не только формально lock-free, но и на практике wait-free. То есть не просте не бяка, а очень даже наоборот супер. http://research.microsoft.com/pubs/209106/paper.pdf


К сожалению, тут слишком много буков, чтобы как-то быстро оценить эффект. Ну, будем надеяться.

>На практике, однако, в CAS-retry цикле считать сколько раз прокрутитились и если долго крутимся, то какую-нибудь случайную задержку начинать втыкать.

Это makes sense :-)

Любопытно, конечно, насколько это все реализуемо для более сложных операций вроде той же очереди. На моей памяти, lock-free copy-on-write строки в GCC годами не могли корректно реализовать. А очередь, возможно, посложнее будет. Ну, будем надеяться, что, когда-нибудь, сделают хорошие стандартные библиотеки. На очереди вон 96-ти ядерные процессоры. Понятно, что текущие мьютексы рано или поздно станут камнем преткновения. Вопрос когда.

Это не thread sleep, но ОС забирает контекст у потока до наступления события, чтобы впустую не жечь CPU.

Всё давно придумано, в том числе очереди. Есть вагон библиотек, в том числе стандартных. В Java, например, ConcurrentLinkedQueue реализует уже ставший классическим алгоритм очереди без блокировки Майкла-Скота https://www.research.ibm.com/people/m/michael/podc-1996.pdf Он очень хорошо масштабируется. На 100500 ядрах, конечно, не взлетит, но когда ядер очень уже много, то писать гарантированно FIFO очереди вообще вредно. Придумана масса почти-FIFO очередей и других трюков, котрые отлично масштабируются.

За ссылочки большое спасибо!

По поводу thread sleep, я подозреваю, что мы говорим об одном и этом же. И в Линуксе и в Виндоуз это, скорее всего, реализовано примерно одинаково, только функции по-разному называются.

По поводу масштабирования: пока, вроде бы, речь идет о десятках ядер. Миллион ядер нам явно пока не светит.

Ну бывают уже системы и с сотнями ядер (а точнее -- hardware threads), но тут надо учесть, что все эти ядра редко уже прямо-таки одновременно долбятся в одну и туже общую структуру данных (занимаются чем-нибудь еще полезным), поэтому существенных проблем с масштабируемостью обычных lock-free структур данных пока не наблюдается. Ну разве что счетчики чего-нибудь, что часто происходит во многих потоках одновременно, может оказаться накладно просто так вот взять и увеличивать из множества потоков одновременно, поэтому там всякие ухищрения уже и на практике приходится делать. См. например стандартный Java класс LongAdder: https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/LongAdder.html

Edited at 2016-04-28 08:42 am (UTC)

Сотни ядер, как мне кажется, не должны вызывать больших проблем, по-крайней мере, на такой простой задаче, как увеличение счетчика. А почему именно эти проблемы возникают? Я помню, что на старых архитектурах, была какая-то неприятность с кешами. Что-то вроде того, что они сбрасывались. При этом, несмотря на то, что самая операция вроде CAS занимала очень мало времени, последствия довольно серьезные.

Для всех атомарных RMW (Read-Modify-Write) операций типа CAS то ядро, которое выполняет операцию, должно захватить соответсвтвую кэш-линейку в эксклюзивный доступ (M или E), о чем, через протокол когерентности кэша (обычно на основе MESI https://en.wikipedia.org/wiki/MESI_protocol протокола) оно сообщает об этом всем другим ядрам (если до этого не владело этой линейкой эсклюзивно).

В современных процах это всё оптимизированно, так что когда следующее ядро сразу вдруг захочет сделать какую-нибудь атомарную операцию над этой же линейкой, то оно получит данные напрямую от ядра, которое до этого держало данные у себя. Это всё быстрей чем заход до памяти и обратно, но все-равно всё это общение занимает существенное время. Так что какой-нибудь CAS или даже LOCK ADD из сотни ядер одновременно в одну и туже кэш-линейку памяти получается не очень быстро. А счетчики какие-нибудь мы иногда хотим очень быстро увеличить, в том числе из множества ядер, вот и приходится ухищряться.

Привет!
Спасибо за выступление, было интересно!

Всегда пожалуйста.

  • 1
?

Log in

No account? Create an account