Вот две строки, я гений, прочь сомненья
Даешь восторги, лавры и цветы…

Данный пост посвящен довольно таки старой задаче о считывании таймера, с которой лично я ознакомился в книге Джека Гансли (The Art of Designing Embedded Systems (Second Edition), (2008) by Jack Ganssle) в которой рассматривается борьба с гонками в асинхронных устройства. Сформулирована проблема и показаны 4 способа ее решения (2 неправильных и 2 правильных), рассмотрены их недостатки, в общем, добротная работа в стиле Джека (я к нему отношусь очень хорошо). К сожалению, на мой взгляд, даже работающие решения не имели должной степени элегантности, но более красивое долго не приходило в голову, а вчера неожиданно осенило. Так что я считаю себя вправе изложить данную проблему в ее историческом контексте, поскольку сам придумал очень элегантное решение (сам себя не похвалишь, весь день ходишь как оплеванный).

Формулируем задачу: у нас имеется аппаратный счетчик, который засинхронизирован от некоторой сиcтемной частоты и может быть использован для измерения времени. Однако, в силу аппаратных ограничения, его вместимости недостаточно для формирования продолжительных промежутков времени, поэтому создается программное расширение разрядности счетчика. Реализуется оно следующим образом — при переполнении счетчика происходит прерывание и подпрограмма обработки прерывания модифицирует некую глобальную переменную, которая совокупно с самим счетчиком образует расширенный счетчик времени, что-нибудь вроде

unsigned int High;  interrupt TimerOv(void) {    High++; }

Тогда получение текущего времени мы может написать следующим образом

 unsigned long int GetTimer(void) {     return (High<<sizeof(int))+ ReadReg(TimerCounter); }

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

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

Попробуем другое очевидное решение — запретить на время считывания прерывания и мы получаем

 unsigned long int GetTimer(void) {     DisableInt();    unsigned long Tmp=(High<<sizeof(int))+ ReadReg(TimerCounter);    EnableInt();    return Tmp; }

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

Возможная модификация данного решения приводит к следующему коду

 unsigned long int GetTimer(void) {     DisableInt();    unsigned long TmpH=High;    if (TimerOvBit()) TmpH++;    TmpH=(TmpH<<sizeof(int))+ ReadReg(TimerCounter);    EnableInt();    return Tmp; }

Вот это первое правильное решение, обратим внимание на то, что мы сначала анализируем бит переполнения, а потом читаем счетчик, обратный порядок был бы неверен. У этого решения есть недостатки: 1) мы все-таки запрещаем прерывания, 2) нам потребуется дополнительный аппаратный бит и нужно о нем позаботиться в обслуживании прерывания, 3) мы сделали определенные предположения о модификации старшей части. Существуют ли другие решения?

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

 unsigned long int GetTimer(void) {     unsigned long TmpH,TmpL;    do {        TmpH=High;        TmpL= ReadReg(TimerCounter);    while (TmpH!=High);    return (TmpH<<sizeof(int))+TmpL; }

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

И вот тут придумана небольшая модификация данного алгоритма, а именно

 unsigned long int GetTimer(void) {     unsigned long TmpH,TmpL;    TmpH=High;    TmpL= ReadReg(TimerCounter);    if (TmpH!=High) TmpL= ReadReg(TimerCounter);    return (TmpH<<sizeof(int))+TmpL; }

Это третье верное решение и мне оно, как автору, нравится больше всего. Мы не запрещаем прерывания, не требуем ничего от аппаратуры, не делаем никаких предположений, получаем всегда верный результат, то есть 1) никогда не получим значения расширенного таймера, предшествующее моменту входа в процедуру и 2) никогда не получим значение, следующее за моментом выхода из процедуры, имеем совершенно предсказуемое поведение и все это практически бесплатно. Конечно, если у нас высоконагруженная система, то мы можем на выходе получить время, существенно меньшее времени выхода из процедуры, но это свойственно в той же мере и двум другим верным способам. Если же нам действительно нужно текущее значение времени с минимальным отклонением, то мы должны всю обработку проводить с запрещенными прерываниями, и это явно не наш случай.

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

И в заключение еще один интересный момент. Нас не интересует время, как таковое, обычно мы используем текущее время для того, чтобы выставить относительно него некоторый момент в будущем, и по достижении него что-либо сделать. Так вот, по Вашему мнению, являются ли следующие две строки эквивалентными?

 unsigned long TmpWait;    TmpWait=GetTimer()+SomeDelay;    while (TmpWait > GetTimer()) ; /* первая строка */     while ((TmpWait - GetTimer()) > 0) ; /*вторая строка */ }

Эти строки неэквивалентны при определенных условиях и интересно рассмотреть, почему. Заинтересовавшихся отправлю к Linux руководствам, ищите вблизи термина jiffies.

ссылка на оригинал статьи http://geektimes.ru/post/268040/