Пользователь
0,1
рейтинг
11 января в 09:56

Разработка → К вопросу о таймерах в ОСРВ (Выводы) из песочницы

imageВ кратце опишу содержание статьи:

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

Пример: 1 мин 20 сек, считываем минуты. Происходит прерывание, которое длится 50 секунд, минуты инкременируются —
2 мин 10 сек, считывам секунды.

Получаем время: 1:10 (1 мин 10 сек), такое время мы могли получить только после путешествия во времени назад, потому что измерения мы начали в 1:20, а результат получили в 2:10. Следует отметить, что убежать вперёд при такой последовательности считывания мы не сможем (как утверждал автор), поскольку с чтением мы отстаём на разряде минут, а это всегда больше всех секунд, помещающихся в соотвествующем разряде (отставание на минуту это минус минута, а секунды они только с плюсом и не больше минуты).

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

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

Как можно быть уверенным, что известные секунды соответствуют нужной минуте? Только лишь надеясь, что мы всё сделали очень быстро и нам повезло, поэтому прерывания между чтением минут, секунд, а потом опять минут (проверочное чтение), не было или оно было молниеносным, и минута истечь не успела. Проверяется это легко: проверочное чтение минут должно дать то же значение. Только вот дело в том, что в худшем случае мы будем бесконечно пытаться получить такое стечение обстоятельств, и результат никогда не получим.

Выход был придуман в оригинальной статье такой: мы только один раз проверяем, и если минута изменилась, то предпологаем, что изменилась она вот только что, а значит есть ещё целых 59 секунд чтобы быстренько прочесть ещё раз минуты и секунды, и вуа ля — мы в дамках. На практике такой приём будет работать довольно неплохо, но в теории это вообще не решение проблемы, потому что никакие 59 секунд нам не гарантированны (мы тут же можем получить прерывание на все 70), да и чтение секунд и минут у нас опять же, в общем случае, разбивается этим же злодеянием. Но статистически — да, вероятность неправильных данных мы резко снизили с помощью такой эвристики.

В комментариях автора направили на путь истинный, и он весьма прост. Мы слишком абстрагировались от того, что собственно нужно и пытаемся решить некую сферическую проблему синхронизации, которая, по сути не требует решения.

Объяснюсь: мы запускаем функцию, чтобы узнать «сколько сейчас время», если нам отвечают быстро, то нас могут интересовать секунды, если мгновенно — мы сможем использовать и миллисекунды в практических целях и т.п. Если же нам отвечают в течении часа, то совершенно не важно, сколько там миллисекунд, время «сейчас» мы не сможем измерить точнее чем час, но как было указанно выше — путешествия во времени, тем не менее, не допустимы.

Поэтому напрашивается очень простой алгоритм:

Прочитали минуты, прочитали секунды, проверочное чтение минут, если всё в норме, то возвращаем результат. Если же минуты изменились, то текущее время n минут и 00 секунд или позже, но не более чем на 59 секунд, а скорее всего это считанные секунды, потому что как и в эвристике автора, мы должны находиться в окрестности перехода одной минуты в другую. Наша же задача состоит в том, чтобы как можно быстрее вернуть этот результат (n минут 00 секунд), любая попытка новой синхронизации, чтения или проверки может закончиться (а в худшем случае — должна закончиться) прерыванием работы, и безотносительно методов получения мы сразу же отдаляемся от текущего времени и ухудшаем любое следующее значение, каким бы точным, относительно момента синхронизации, оно не было.

Таким образом, возврат 00 секунд будет даже точнее, чем реально прочитанное значение (мы не тратим время на чтение секунд и на дальнейшие проверки), ведь мы хотим получить время «сейчас», а не время когда удалось синхронизироваться. Фактически, нам подходит любое время, взятое наугад, главное чтобы оно было в интервале времени работы функции, а сам функция работала как можно меньше. Это как раз та эвристика, которая позволяет сделать очень точное предположение, и оно точно ложится в интервал работы функции.

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

Ну и, конечно, мы испортили статистическое распределение секунд, сделав 00 более вероятным, поэтому что-то вроде Randomize может давать побочные эффекты.
@VaalKIA
карма
2,0
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (2)

  • +1
    От автора оригинально поста:
    (мы не тратим время на чтение секунд и на дальнейшие проверки
    Мы не тратим время только на чтение секунд, потому что дальнейших проверок нет.
    Мой первый вариант (который я не помещал в статью) предусматривал возвращение именно 0, поскольку любое значение от 0 до текущего значения счетчика является валидным в том смысле, что не дает прошлого либо будущего, но потом было придумано повторное чтение счетчика. Да, это займет время чуть большее, чем просто сделать 0, но точность при повторном чтении все-таки лучше, а проигрыш в исполнении я принял несущественным.
    Если у нас действительно сильно нагруженная система, то, конечно, особой разницы нет, а вот если прерывание не было фатально длинным (не привело к многократному прокручиванию старших разрядов), то тогда разница есть.
    А вообще то, спасибо, Вы подробно описали ситуации, от которых мы и убегаем, я больше сосредотачивался на коде, а вот описания явно не хватало.
  • 0
    Согласен полностью, что задача получения времени очень сильно зависит от юз кейса. К тому же никто не отменяет того, что современные микроконтроллеры или SoC'и содержат в камне модуль RTC(не уверен, что на всех камнях он именно так называется), который как раз независимо от нагрузки центрального ядра сам ведёт подсчёт секунд, миллисекунд, минут и т.д. и выдаёт уже основной программе, либо другой интегрированной схеме время в атомарном виде.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.