Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Синхронизация процессов.  (Прочитано 20184 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« : 22-11-2010 06:55 » 

Обсуждение статьи: «Синхронизация процессов.»
« Последнее редактирование: 30-11-2010 17:07 от RXL » Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 24-11-2010 14:37 » 

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 26-11-2010 20:51 » 

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

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 27-11-2010 00:58 » 

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 27-11-2010 09:39 » 

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 без ОС в контроллерах обычно не применяют. Т.е. ценность его как примера не высока.
« Последнее редактирование: 27-11-2010 09:43 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #5 : 28-11-2010 20:12 » 

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 28-11-2010 20:36 » 

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

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 28-11-2010 21:28 » 

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

Не совсем.

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

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

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

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 28-11-2010 21:52 » 

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

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

PS этот механизм просто гарантирует передачу данных ОТ ОДНОГО обработчика прерывания К нескольким независимым процессам без всяких блокировок.
« Последнее редактирование: 29-11-2010 15:17 от Ochkarik » Записан

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 28-11-2010 22:08 » 

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

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


Добавлено через 1 минуту и 57 секунд:
Ochkarik, две атомарные операции для двух полей структуры данных дают неатомарность для всей структуры.
« Последнее редактирование: 28-11-2010 22:13 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #10 : 28-11-2010 23:06 » 

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

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

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 28-11-2010 23:13 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #12 : 28-11-2010 23:28 » 

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 25-01-2011 22:04 » 

Цитата: Dale
Условия Бернстайна являются достаточными, но не необходимыми для детерминированности набора последовательностей действий.
Что-то меня эта фраза коробит. Неточная формулировка.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #14 : 25-01-2011 22:10 » 

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #15 : 26-01-2011 15:31 » 

Dale,

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

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #16 : 26-01-2011 17:13 » 

Dale,

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

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

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

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

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

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

Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #17 : 27-01-2011 13:08 » 

Dale, да.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #18 : 27-01-2011 13:32 » 

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #19 : 27-01-2011 17:01 » 

Dale, да.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #20 : 27-01-2011 17:35 » 

Улыбаюсь
Таким кратким Dimka еще не был.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #21 : 28-01-2011 08:05 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines