Человек, имеющий одни часы, твердо знает, который час. Человек, имеющий несколько часов, ни в чём не уверен.
Закон Сегала

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

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

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

Требования на источники времени

Требования на устройства времени многочисленны и разнообразны.

• Известное и высокое разрешение. Определяется частотой осциллятора, используемого в составе устройства. Чем она выше, тем короче минимально измеримый интервал времени.
• Низкая задержка при чтении. Обращение к устройству-источнику времени само по себе не мгновенно, и к тому моменту, когда ответ от него доберётся до процессора, значение уже устареет. Кроме того, величина данной задержки может быть непостоянной, что будет вносить дополнительную неопределённость в считываемые значения. Порядок величины задержки определяется положением устройства-источника времени по отношению к читающему ядру: время, полученное с сетевого сервера синхронизации, запоздает гораздо больше, чем измерение, взятое со счётчика, расположенного в самом ядре.
• Наибольшая длительность интервала времени, который может быть измерен. Так как для представления показаний времени используются числа фиксированной ширины, существует возможность переполнения счётчика между двумя измерениями. Чем выше разрешение таймера, т.е. его частота, тем быстрее может переполниться регистр, хранящий время.
• Независимость от внешнего питания. Что произойдёт с содержимым регистров типичного устройства, если выключить питание системы? Чаще всего они потеряют свои значения и заполнятся «мусором», в лучшем случае — нулями. И всё же иногда хочется, чтобы течение времени отслеживалось и при выключенном компьютере. Для этого устройство времени может быть сделано энергонезависимым, т.е. попросту иметь собственную батарейку, ресурса которой хватает, чтобы переждать характерный период нахождения системы в выключенном состоянии.
• Монотонность изменения значений. Каждое следующее значение, полученное от таймера, должно быть строго больше всех предыдущих, за исключением случаев, когда происходит переполнение; однако этот случай может быть сигнализирован аппаратурой и обработан программно специальным способом. Отсутствие гарантий монотонности вынуждает пользователей таймера учитывать возможность возвращения отрицательных или нулевых длительностей для интервалов (например, нельзя без проверки делить на длину интервала времени — она может оказаться нулевой).
• Равномерность изменения значений. Если частота колебаний таймера изменяется в процессе, или он приостанавливает свою работу, например, при переходе в режим энергосбережения, то события, запланированные в предположении о его монотонности, могут случиться позже, чем ожидалось. Другая, присущая всем причина для неравномерности — чисто физическая нестабильность источника колебаний, связанная с температурными колебаниями, процессами деградации материала и тому подобными странными вещами.
• Согласованность с другими таймерами в системе. Если в компьютере имеется несколько устройств-источников времени, очень возможна ситуация, что их показания не будут соответствовать друг другу. И, даже будучи сверенными друг с другом в начале, они могут разойтись в процессе работы по многочисленным причинам, в том числе описанным выше.

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

Обзор таймеров в архитектуре PC

Источников времени в системе может быть несколько. Прикладные программы редко обращаются к каким-либо из них напрямую. Вместо этого используются всевозможные API, предлагаемые использованным языком программирования (например, C++11 < chrono >), средой исполнения (например, gettimeofday из POSIX или QueryPerformanceCounter на MS Windows), или даже системными вызовами используемой операционной системы.

Самой ОС также необходимо знать время и уметь отмерять его отрезки для планирования работы пользовательских потоков, учёта потреблённых ими ресурсов, профилировки производительности, управления энергопотреблением и т.п. При этом сама ОС работает напрямую с интерфейсами, предоставляемыми аппаратурой. Так как таймеров присутствует много, современные ОС умеют выбирать один «центрально» используемый в начале загрузки, исходя из своих представлений о «качестве» обнаруженных устройств (например, на некоторых системах часть таймеров может быть занесена в «чёрный список» из-за известных проблем в работе) или же настроек пользователя (параметр clocksource у ядра Linux и опции useplatformclock, tscsyncpolicy, disabledynamictick у BCDEDIT в Windows).
Опишу наиболее часто встречаемые устройства, являющиеся часами и таймерами в PC.

Общераспространённые

Часы реального времени (Real Time Clock, RTC) — источник текущей даты и времени для нужд ОС. Типичное разрешение этого таймера — одна секунда. Все системы, удовлетворяющие стандарту ACPI, имеют чип RTC, совместимый с Motorola MC146818, присутствовавшем в оригинальном IBM PC/AT с 1984 года. В современных системах RTC обычно интегрирован в набор системной логики южного моста на материнской плате (что означает довольно большую задержку при чтении). Энергонезависимость этого таймера обеспечивается специальной батарейкой. Принципы программирования RTC вызывают ностальгию по BCD-числам и проблеме Y2K.



Programmable Interval Timer (PIT) 8253 или 8254 от Intel — стандартный счётчик и таймер, имеющийся в PC с самого начала существования этой платформы (1981 год). Как и RTC, изначально был отдельной микросхемой, а ныне является частью системной логики. Довольно интересное устройство, содержащее три таймера (хотя последние два всегда были зарезервированы под задачи обновления ОЗУ и работу PC-спикера соответственно) и позволяющее запрограммировать их в различные режимы: периодические прерывания, однократное (one-shot) прерывание по таймауту, меандр и т.д.

Первый канал PIT до сих пор может использоваться ОС как источник прерываний для работы вытесняющего планировщика задач. Однако по современным меркам он не очень удобен в работе: низкая частота осциллятора 1193181,8 Гц (странное значение — это историческое наследие от частоты развёртки NTSC), ширина счётчика всего 16 бит (частое переполнение) при ширине регистров статуса и команд всего в восемь бит (т.е. приходится передавать или читать значение по частям), да и доступ к регистрам через медленный и негибкий механизм PIO (команды IN/OUT процессора).

Local APIC (advanced programmable interrupt controller), встроенный во все современные процессоры Intel (начиная с архитектуры P54C) и который в своём составе имеет ещё и таймер. Более того, каждый логический процессор имеет свой собственный LAPIC, что может быть удобно для выполнения работы, локальной для текущего ядра, без необходимости управления ресурсами. Однако, данное устройство не имеет фиксированной известной частоты; последняя скорее привязана к частоте ядра. Поэтому перед использованием программе необходимо её вычислить (калибровать), а для этого нужно дополнительное референсное устройство. Режимы, поддерживаемые LAPIC: однократное прерывание, периодические прерывание, и период, определяемый TSC.

Таймер в составе ACPI, почему-то называемый Performance Monitoring Timer (PMTIMER) — ещё одно устройство, которое поддерживается всеми системами, реализующими стандарт ACPI, с 1996 года. Данный таймер имеет частоту 3.579545 МГц, ширина регистра-счётчика может быть 24 или 32 бита. Сам таймер всегда активен при включенном питании системы и не зависит от режима работы центрального процессора.

High Precision Event Timer (HPET) — устройство, созданное как замена устаревшему PIT. Согласно стандарту, HPET должен содержать осциллятор, работающий с фиксированной частотой по крайней мере в 10 МГц, величину которой можно программно прочитать из его статусного регистра, и монотонно увеличивающий значение счётчик шириной в 64 бита. Также он должен содержать минимум три компаратора шириной в 32 или 64 бита, которые и используются для генерации прерываний по истечении запрограммированных периодов времени. Как и PIT, он способен работать в периодическом режиме или в режиме однократного прерывания. При этом метод его программирования (MMIO вместо PIO) удобнее и быстрее, чем у PIT, что вместе с повышенным разрешением, позволяет задавать интервалы более точно и с меньшей задержкой. Требуемая стабильность генератора равна 0,05% для интервалов длиннее 1 мс и 0,2% для промежутков короче 100 мкс; много это или мало — зависит от приложений.

Несмотря на то, что HPET уже давно присутствует в PC (с 2005 года), операционные системы не торопятся начать его использовать. Частично это вызвано не самым удобным способом задания интервалов с помощью возрастающего счётчика вместо убывающего — из-за немгновенности операций существует риск «не успеть» и задать событие в прошлом. Зачастую ОС используют таймер из APIC или PMTIMER, или же функциональность TSC, использующую такты процессора в качестве источника времени.

Трудная судьба инструкции RDTSC

История TSC достаточно интересна и поучительна, чтобы остановиться на ней подольше.
Сама идея очень прозрачная — использовать в качестве источника времени сам процессор, а точнее его тактовый генератор. Текущий номер такта сохраняется в регистре TSC (timestamp counter).
С помощью TSC можно как узнавать время от начала работы, так и замерять интервалы времени с помощью двух чтений. TSC также работает как будильник в связке с APIC в режиме TSC deadline.

• RDTSC (Read TimeStamp Counter — прочесть метку времени) появилась в Intel® Pentium™. Она записывает в пару регистров EDX:EAX 64-битное число тактов, прошедших с момента последнего включения питания/перезагрузки текущего ядра процессора. В отличие от всех ранее описанных устройств, которые доступны только привилегированному коду, RDTSC по умолчанию может исполняться на любом уровне привилегий (хотя ОС может динамически отключить поддержку RDTSC в пользовательском режиме, и тогда она будет вызывать исключение).
  
• RDMSR [0x10] — чтение модель-специфичного регистра (MSR) IA32_TIMESTAMP_COUNTER также возвращает текущее TSC. Данная инструкция допускается только в привилегированном режиме, и некоторые ОС активно используют именно её для чтения TSC (хотя лично мне непонятно, почему). Полезное свойство состоит в том, что через MSR значение TSC можно не только читать, но и изменять, используя инструкцию WRMSR.
• RDTSCP — Наличие её можно установить, проверив соответствующий лист CPUID. О двух её отличиях от RDTSC будет сказано чуть ниже.

Что ж, TSC — вполне естественная штука с простой логикой и простым сценарием использования, которая должна обладать многими полезными свойствами: высокое разрешение (один такт ЦПУ), низкая задержка при чтении (десятки тактов), редкие переполнения (64-битного счётчика должно хватать минимум на 10 лет), монотонность чтений (ведь счётчик всегда увеличивает своё значение), равномерность (процессор всегда работает), согласованность с другими таймерами (при старте системы можно выставить нужное значение записью в MSR).
Разве что-то могло пойти не так? На пути к успешному использованию TSC в качестве основного средства измерения времени в PC встала последующая эволюция процессоров. Новые возможности, появившиеся в процессорах после Pentium, «испортили» RDTSC и много лет мешали использовать её как основной таймер в популярных ОС. Так, в 2006 году один из Linux-разработчиков Ingo Molnar писал:

Мы наблюдали, что в течение 10 лет ни одной реализации gettimeofday, основанной на TSC и работающей в общем случае, не было написано (а я написал первую версию для Pentium, так что и я в этом повинен), и что лучше мы обойдёмся без неё.

We just observed that in the past 10 years no generally working TSC-based gettimeofday was written (and i wrote the first version of it for the Pentium, so the blame is on me too), and that we might be better off without it.

Отмечу, что со временем в архитектуру IA-32 вносились коррективы, устранявшие проявившиеся недостатки, и в настоящий момент TSC может (пока опять не сломали) быть использован в том качестве, в котором он задумывался.

• Внеочередное исполнение (Out of Order Execution, OoO). Начиная с Intel® Pentium™ Pro (1995 г.), процессор может исполнять машинные инструкции в порядке, отличном от использованного в программе, или даже параллельно (если они не зависят друг от друга). Это означает, что исполнение RDTSC может быть задержано или, наоборот, выполнено раньше, чем того требует последовательный программный порядок. Из-за этого, например, невозможно понять, сколько каких инструкций исполнилось между двумя вызовами RDTSC — нельзя надёжно измерить длительность участка кода. В результате не гарантируется монотонность показаний.
  RDTSC не является инструкцией, сериализующей поток исполнения. Поэтому обычно используется «забор» из сериализующих команд вокруг неё, например, CPUID. Это, конечно, не выглядит очень изящно. В последующих обновлениях архитектуры появилась RDTSCP — инструкция, частично сериализующая поток исполнения, поэтому она не нуждается в дополнительных барьерах. У неё есть ещё одно хорошее свойство, но о нём чуть позже.
• Управление энергопотреблением. Значение TSC увеличиваетсся каждый такт процессора. Всегда ли такт имеет один и тот же период, и всегда ли следующий такт следует сразу за предыдущим? Для Intel® Pentium™ это выполнялось. Для современных процессоров ответы на оба вопроса отрицательные. Процессор довольно значительную долю времени может быть приостановлен для экономии энергии (C-состояния). Исполняя инструкции, он может использовать динамическое изменение частоты для экономии энергии (P-состояния) или наоборот, для максимизации производительности (Turbo-состояния). Из этого следует, что просто счётчик тактов не будет обладать ни равномерностью, ни согласованностью.
  И для этой проблемы было представлено (начиная с Nehalem) решение в виде т.н. invariant TSC, темп изменения которого не зависит от C- и P-состояний отдельных ядер.
• Многопроцессорность и многоядерность. В системе с несколькими потоками, ядрами или процессорами у каждого из логических процессоров будет свой TSC. Это создаёт не одну, а целых две сложности.
  Во-первых, значения, возвращаемые RDTSC на различных логических процессорах, могут оказаться сдвинутыми из-за неодновременности моментов инициализации ядер. Более того, из-за неустранимого дрейфа частот отдельных таймеров эта разница могла непредсказуемым образом флуктуировать в процессе работы.
  Во-вторых, перестаёт работать возможность надёжно измерять время в пользовательских приложениях. Без дополнительных ухищрений вроде прописывания affinity в любой момент программа может быть вытеснена с одного процессора и затем продолжена на другом. Если процесс, желающий измерить длительность между двумя событиями, в процессе работы был перемещён ОС с одного ядра на другое, два чтения RDTSC, выполненные им, не будут связаны.
  Для компенсации первой проблемы в последних поколениях процессоров для TSC заводится единый источник сигнала. Показания TSC со всех ядер при этом должны быть одинаковыми.
  Для устранения второго недостатка RDTSCP обладает ещё одним свойством, позволяющим пользовательскому приложению детектировать миграцию в процессе измерения интервала времени. Кроме значения TSC в EDX:EAX она возвращает значение отдельного модель-специфичного регистра IA32_TSC_AUX в ECX. Обе записи происходят атомарно, т.е. TSC и TSC_AUX всегда берутся с одного логического процессора. В начале работы ОС должна выставить уникальные значения TSC_AUX на всех процессорах системы. Совпадение считанных ECX для двух вызовов RDTSCP гарантирует, что они были выполнены на одном процессоре; в противном случае на разницу двух TSC полагаться нельзя, и измерение следует повторить. Вообще этот механизм может иметь и другие применения; например, с помощью него можно оповещать приложение не только о факте миграции, но и просто о вытеснении, также способном исказить результаты измерений времени. Вместо прикладных программ могут выступать и «привилегированные»: гипервизор Xen использует данный механизм для нотификации DomU систем о миграции между машинами.

В качестве ещё одной «недоделки» в первых реализациях TSC выступал тот факт, что не на всех процессорах была возможность записи во все 64 бита TSC — в регистр попадали лишь младшие 32, а старшие обнулялись. Это проблема тоже была впоследствии устранена.

Прочие устройства

Выше я описал наиболее часто распространённые и используемые устройства по определению времени. Конечно же, конкретные системы могут иметь дополнительные устройства, уникальные для процессора, интегрированной логики или даже в форме специализированных периферийных устройств (например, сверхточные атомные часы). Степень их доступности из программ зависит от того, существует ли драйвер для конкретного устройства в выбранной ОС. Так, пробежавшись по исходникам Linux, я нашёл как минимум ещё два поддерживаемых источника времени для сборок x86: устройство NatSemi SCx200 в системах AMD Geode, и Cyclone для систем IBM x440. К сожалению, в Интернете не очень много документации по ним.


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

• PowerPC. Спецификации для 32- и 64-битных систем постулируют наличие регистра TB (time base) шириной в 64 бита, доступного на чтение пользовательским приложениям и на чтение/запись из супервизора. Изменения TB должны монотонно не убывать и не обязаны быть равномерными, а их частота зависит от реализации. Также из режима супервизора доступен 32-битный регистр DEC (decrementer), позволяющий программировать прерывание через промежуток времени. Его значение убывает до нуля с той же самой частотой, с которой возрастает TB.
• ARM. В целом наличие средств измерения времени сильно зависит от выбранного семейства. На архитектуре ARM11 регистр CCNT может быть использован для чтения текущего номера такта; однако ширина его всего 32 бита, что означает переполнение примерно каждые 10 секунд на системе с частотой в 400 МГц. На системах Cortex M3 присутствует устройство Systick шириной 24 бита, а скорость его изменения специфицируется значением из регистра TENMS.
• Intel ® IA-64 (Itanium). На данных системах в качестве счётчика тактов используется 64-битный регистр ar.itc (interval time counter). Для программирования периодов времени может использоваться набор регистров cr.itm (interval timer match), cr.itv (interval timer vector). Первый задаёт значение ITC, при котором сгенерируется прерывание, а второй определяет его номер.
• SPARC v9. Архитектура подразумевает наличие 63-битного регистра TICK. Последний 64-й бит этого регистра контролирует, разрешено ли непривилегированному приложению читать время.

Заключение

Я надеюсь, что из этой заметки стало понятно, что работа со временем внутри компьютера на системном уровне на самом деле далека от тривиальной. Требования к устройствам, поставляющим время, зависят от решаемой задачи, и не всегда легко найти полностью подходящий вариант. При этом сами устройства зачастую содержат «архитектурные особенности», способные сломать голову несчастному программисту.
Однако это всё архитектурная присказка к симуляционной сказке. На самом деле мне хотелось рассказать о том, как можно моделировать весь этот зоопарк устройств. В следующей статье я опишу, как проявляется капризная природа времени при создании виртуальных окружений — симуляторов и мониторов виртуальных машин. Спасибо за внимание!