Эдсгер Дейкстра про семафоры

[vak]

Взялся из любопытства заценить историческую статью Эдсгера Дейкстры, где он изобрёл семафоры. Называется "Over seinpalen" (PDF), на голландском. Статья не датирована, ориентировочно 1962 год. Оказалась странная вещь: никто её так и не перевёл на английский. Есть более поздние работы, а эта увы. Ну, я быстренько через Google translate набросал. Там надо будет кое-что повычистить на досуге, но и так уже неплохо.

"About semaphores"

Comments

[dmm]

!

[x86128]

Без хардвёра никуда. А как в современных ядрах принято атомики и семафоры делать? Куда там этот хардвёр спрятан?

[vak]

Делают специальные машинные команды для этого.

https://en.wikipedia.org/wiki/Load-link/store-conditional

[perdakot]

В Cortex-M0 ничего такого нет и тем не менее на RP2040 два ядра :) Я так понимаю, что там надо делать Peterson’s Solution.

[x86128]

А вот это уже интересно, но, кажется, что чисто в софтвере семафоры не сделать когда больше чем 1 процессор над общей памятью

[dijifi]

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

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

[perdakot]

Peterson’s Solution же.

https://en.wikipedia.org/wiki/Peterson%27s_algorithm

[x86128]

Спасибо за справочку!
Действительно такой алгоритм простой и понятный, но сработает только когда нет кешей у ядра и доступ к памяти осуществляется по одной шине (тогда в любом случае запросы будут сериализованны). В простом случае хватит простого арбитра доступа к памяти и слова volatile в тот сишный псевдокод.

[vak]

На RP2040 есть специальные хардверные спинлоки. Смотрите регистры SPINLOCK0…SPINLOCK31.

[perdakot]

Я до этого места не дочитал потому что у меня RP2040 нету.

[x86128]

Любопытно, посмотрю что там предлагается. Можно предположить, что это нечто похожее на то, что в статье Дейкстра предлагал.

[x86128]

Бегло посмотрел доку https://datasheets.raspberrypi.com/rp2040/rp2040-datasheet.pdf
Классная машинка, оказывается, этот RP2040 с точки зрения наворотов архитектуры

Даже есть очереди на восемь слотов: Inter-processor FIFOs (Mailboxes)
The SIO contains two FIFOs for passing data, messages or ordered events between the two cores. Each FIFO is 32 bits wide, and eight entries deep. One of the FIFOs can only be written by core 0, and read by core 1. The other can only be written by core 1, and read by core 0.

Там не только RP/M полетит :)

[vak]

Смотри главу 7 в описании RISC-V.

https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf

[x86128]

Спасибо! Почитаю. Используешь эти штуки и воспринимаешь как данность, а на самом деле там не просто, особенно когда всякие кеши появляются и память внешняя по отношению к ядру (RDMA, NUMA)

[vak]

Там действительно непросто. Эти команды LR и SC, они через всю иерархию памяти и кэшей простреливают. Над верификацией этого дела я в своё время в MIPS изрядно потрудился.

[dijifi]

Тут такой момент что в борьбе за эффективность простые вещи оказываются безумно сложными. Например: два процессора соединены шиной PCIe (один сидит на карте). главный процессор пишет, карточный в упор не видит.
Системщик: не работает!
Хардверщик: а ты прочитай назад.
Системщик: прочитал, совпадает, не работает!
Хардверщик: а ты кэши вытолкнул? И прочисти кэш чтобы на самом деле читало. И не забудь о барьерах, а то кэш можно вытолкнуть ещё до того как данные туда доедут. Ах да, у нас ещё writeback buffer, набей его нулями.
Системщик: работает, но ненадежно.
Хардверщик: А-а-а блин metal spin.

[x86128]

👀😱

[x86128]

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

[vak]

Может лет через 200 придумают более общий случай, а пока и так сойдёт. 😀

[prool]

Вроде был перевод на русский и издавался в сборнике под заголовком "Статьи с научного конгресса НАТО". Я тогда еще подумал, что НАТО не только агрессивный антикоммунистический блок, они еще и программированием занимаются.

Ключевые слова parbegin и parend - там Дийкстра ввел такое расширение Алгола-60 - операторные скобки, ограничивающие набор операторов, которые будут выполняться параллельно.

А что касается неделимых атомарных функций, так это классика низкоуровневого программирования

cli
код который нельзя прерывать
sti

и пусть весь мир подождет

[ichthuss]

Это только для однопроцессорных.

[vak]

Выше уже упомянули микроконтроллер RP2040. Хороший практический пример, где нужно синхронизовать два ядра Cortex-M0+. Простой блокировкой прерываний никак не выйдет.