Синхронизация процессов.

[Dale]

Обсуждение статьи: «Синхронизация процессов.»

[Dale]

Очередное введение опять разрослось на целую статью, задачи синхронизации снова уезжают в следующую тему.

В этой части ставлю точку. Обсуждаем.

[Ochkarik]

Dale, немного не в тему простых процессоров, но я бы упомянул, что обычные операции Test-and-Set или Swap на многопроцессорных системах не всегда атомарны. на x86 для этого необходим дополнительных префикс lock.
чтобы однозначно не ассоциировать ВСЕ одиночные инструкции процессора как атомарные примитивы.

[Dale]

Да, нужно будет как-то вплести в тему, что наличие нескольких ядер может дополнительно усложнить проблему.

Может, потому что, насколько я помню, в некоторых архитектурах вроде IBM 360/370/... подобные операции были атомарны при любых конфигурациях.

[RXL]

LOCK не всегда применим и не всегда нужен. Цитирую мануал P5:

Префикс LOCK функционирует только со следующими командами:
* BTS, BTR, BTC - mem, reg/mem
* XCHG - reg, mem или mem, reg
* ADD, OR, ADC, SBB, AND, SUB, XOR - mem, reg/imm
* NOT, NEG, INC, DEC - mem
* CMPXCHG, XADD

Команда XCHG всегда устанавливает LOCK# (внешний сигнал), несмотря на присутствие или отсутствие префикса LOCK.

Т.е. XCHG, начиная с 80386, абсолютно атомарная операция.
Но вот только x86 без ОС в контроллерах обычно не применяют. Т.е. ценность его как примера не высока.

[RXL]

Тема статьи о микроконтроллерах? Тогда при чем тут многоядерность?

Кстати, скажем, есть кольцевой буфер для передачи данных с/на последовательный порт, с которым работает основная задача и задача на прерывании от передатчика/приемника. Если они будут использовать взаимные блокировки, то что делать обработчику прерывания, когда он столкнется с блокировкой? Ждать ему нечего - только завершать прерывание, но повторно прерывание может не придти.

[Ochkarik]

RXL, просто пример.
другой пример - семейство  BlackFin  от AnalogDevices из топовой линейки. так же содержит два ядра. и это ни капли не процессор для ОС. 
правда в его ассемблере я не силен, точно сказать не могу, что там с атомарностью операций...копать надо)

[Dale]

Тема статьи о микроконтроллерах? Тогда при чем тут многоядерность?

Не совсем.

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

Кстати, скажем, есть кольцевой буфер для передачи данных с/на последовательный порт, с которым работает основная задача и задача на прерывании от передатчика/приемника. Если они будут использовать взаимные блокировки, то что делать обработчику прерывания, когда он столкнется с блокировкой? Ждать ему нечего - только завершать прерывание, но повторно прерывание может не придти.

Вот, например, такие варианты навскидку:

• Если это система реального времени и критическая секция основной задачи сделана максимально короткой, можно попросту при входе в нее запрещать прерывания от UART, а при выходе восстанавливать разрешение. Тогда возникшее прерывание заведомо не упрется в блокировку.
  Достоинства: максимальная простота и компактность.
  Недостатки: задерживать обработку прерывания может быть не всегда допустимо.
• Подпрограмма обработки прерывания, упершаяся в заблокированный буфер, не завершается, а ставится планировщиком в очередь к заблокированному ресурсу, причем с приоритетом выше, чем у основной задачи. Как только основная задача покидает критическую секцию, происходит перепланирование, в результате которого более приоритетная задача обработки прерывания продолжает работу.
  Достоинства: пожалуй, самое корректное из предложенных решений.
  Недостатки: высокие накладные расходы, необходимость наличия ОС с приоритетным планированием.
• Подпрограмма обработки прерывания, упершаяся в блокировку, завершается, предварительно сохранив состояние. У нее есть дополнительная точка входа как в подпрограмму для завершения отложенной обработки. При выходе из критической секции основная программа вызывает эту подпрограмму завершения. Разумеется, если прерывания в этот момент не было, подпрограмма завершения попросту возвращает управление обратно.
  Достоинства: умеренная сложность, своевременная реакция на прерывание.
  Недостатки: основная программа должна учитывать наличие подпрограммы обработки прерываний и не забывать после каждого выхода из критической секции вызывать подпрограмму завершения. Два процесса оказываются слишком сильно связаны.

Если подумать еще, наверняка найдутся варианты получше.

[Ochkarik]

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

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

PS этот механизм просто гарантирует передачу данных ОТ ОДНОГО обработчика прерывания К нескольким независимым процессам без всяких блокировок.

[RXL]

По п.3: когда-то пытался писать драйвер для Linux 2.2 и там был похожий механизм. Наверно это самый простой способ выйти из положения. Но Linux не является RT ОС.

13 лет назад, при первом знакомстве с 8051, я использовал еще один способ: двойная буферизация — один большой буфер и один малый (на 1-2 передачи). Программа пишет в малый буфер, но если он полон или занят, то пишет в большой. Если малый пуст, а в большом есть данные, то они перемещаются в малый. На момент работы с малым буфером прерывания запрещаются. Обработчик прерывания работает читает из малого буфера и если он пуст, то лезет в большой. Суть этого в том, что время записи в буфер много меньше, чем периодичность прерываний и программы не пересекаются. Конечно, в сравнении с п.3, это сложный и менее надежный вариант.


Добавлено через 1 минуту и 57 секунд:
Ochkarik, две атомарные операции для двух полей структуры данных дают неатомарность для всей структуры.

[Dale]

Dale, на самом деле, наверное стоит отдельно рассмотреть несимметричную блокировку чтения и записи (кажется ее RWLock называют)... когда один процесс только пишет, второй - только читает. или когда несколько только читающих...

А я на самом деле плавно к этому дело и веду. Дело в том, что классическая задача "производитель-потребитель" наиболее просто решается через сопрограммы, поскольку там без всяких планировщиков управление поочередно передается от производителя к потребителю и обратно. Поэтому достаточно буфера на один элемент, он заведомо не переполнится. А эта задача мне весьма интересна в плане программирования микроконтроллеров, поскольку позволяет гибко построить цепочку из слабосвязанных звеньев обработки (связь только через буферный элемент). И все это с минимальными накладными расходами.

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

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

[RXL]

Dale, прежде всего — представляет ли это интерес для тебя? Потому как лично мне интересно было бы раз взглянуть — вряд ли будешь стараться только ради этого раза. А за других мне сказать сложно. Во всяком случае, схема была бы красивым дополнением. И хотя бы фрагмент программы.

[Dale]

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

[Dimka]

Условия Бернстайна являются достаточными, но не необходимыми для детерминированности набора последовательностей действий.

Что-то меня эта фраза коробит. Неточная формулировка.

[Dale]

Неточная или непонятная?

[Dimka]

Dale,

Если выполняются условия Бернстайна, то есть детерминированность. Если не выполняются, то детерминированность может быть, а может и не быть.

Условия => Детерминированность

И это как раз наоборот: детерминированность достаточна. но не необходима для условий Бернстайна; а условия Бернстайна необходимы, но недостаточны для детерминированности.

[Dale]

Dale,

Если выполняются условия Бернстайна, то есть детерминированность.

Правильно. Все наборы, удовлетворяющие условиям Бернстайна, заведомо детерминированы (достаточность).

Если не выполняются, то детерминированность может быть, а может и не быть.

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

И это как раз наоборот: детерминированность достаточна. но не необходима для условий Бернстайна; а условия Бернстайна необходимы, но недостаточны для детерминированности.

А это уже неправильно. Условия Бернстайна дают нам множество невзаимодействующих процессов, которое детерминировано, но не слишком интересно для практических применений. Они (условия) достаточны, но не необходимы, ибо бывают еще и взаимодействующие детерминированные процессы.

[Dimka]

Dale, да.

P.S. И у нас тут было потрачено много минут на обсуждение этого момента

[Dale]

"У вас" - это где? В коллективе разбирали?

Да, бывает порой, что на таких вещах "клинит"... Пока не нарисуешь наглядно - не осознаешь. Ну или общепризнанная в таких случаях панацея - поллитра

[Dimka]

Dale, да.

[Sla]

Таким кратким Dimka еще не был.

[Dimka]

Sla, длинно было в IRL, о чём упомянуто выше . Ну раз уж так настаиваешь: в Википедии по этому поводу что-то странное написано применительно к импликации.