В предыдущей статье я рассмотрел существующие в платформе PC источники времени, их особенности, недостатки и историю. Теперь, вооружённые этим знанием, мы можем рассмотреть, как эти устройства могут быть представлены внутри виртуального окружения — полноплатформенного программного симулятора или системной виртуальной машины, т.е. программной среды, позволяющей запускать внутри себя операционную систему.
В этой статье мы разберём различные способы представления времени внутри моделей, подходы к имитации работы таймеров, возможности аппаратного ускорения при виртуализации, а также трудности согласования течения времени внутри моделируемых окружений.
Под симуляторами и виртуальными машинами будут подразумеваться такие программы, как Bochs, KVM/Qemu, Vmware ESX, Oracle Virtualbox, Wind River Simics, Microsoft HyperV и т.д. Они позволяют загружать внутри себя немодифицированные операционные системы. Соответственно внутри модели компьютера должны содержаться модели отдельных устройств: процессоров, памяти, плат расширений, устройств ввода/вывода и т.д., а также, конечно же, часов, секундомеров и будильников.
Как и в предыдущей статье, начнём обсуждение с требований, предъявляемых к понятию «время» внутри симуляторов и виртуальных машин.
Два важных свойства «правильной» симуляции.
1. Представление состояния некоторой реальной системы и её компонент с некоторой наперёд выбранной точностью. Течение времени в модели может быть приближённым и довольно сильно отличаться от реальности.
2. Допустимая в реальности эволюция состояния внутри модели.
Для этого железно должна работать причинно-следственная связь. За исключением, пожалуй, каких-то совсем экзотических систем, эволюция моделируемой системы должна правильно упорядочивать связанные события. Желающим глубже изучить этот очень непростой вопрос порекомендую начинать с работ Лесли Лампорта [2] или аналогичных статей по распределённым алгоритмам.
Это покажется странным, но остальные условия на виртуальное время не являются столь же универсальными; однако рассмотрим их.
Условие строгой монотонности течения времени. Чаще всего виртуальное время не должно убывать с течением физического времени. Как показал мой опыт, подход «мы тут на минуточку уменьшим время» обычно ведёт к жуткой путанице при отладке и является признаком плохого дизайна.
В ряде не совсем типичных, но всё же практически важных случаев виртуальное время должно двигаться вспять: при откате состояния оптимистичных параллельных моделей, или при обратном исполнении.
Наконец, сложные компьютерные системы (и их модели) бывают распределёнными. Для них требование единых общих часов может быть избыточно строгим — части такой системы должны уметь нормально работать, имея лишь ограниченную локальную информацию о времени. В них глобальное время становится «векторной» величиной. Как известно, векторы довольно сложно сравнивать по принципу «больше-меньше».
Условие соответствия симулируемого времени реальному чаще всего избыточно. Как показала моя практика, подразумевать какую-либо корреляцию между ними вредно для проектировщика симулятора, так как это создаёт необоснованные ожидания и мешает создать корректную или быструю модель. Самый простой пример: виртуальную машину всегда можно поставить на паузу; при этом время внутри неё остановится, реальное время мы пока что остановить не в силах.
Более интересный пример. При работе симуляции темп изменения симулируемого времени может динамически меняться. Оно может быть как медленнее реального, так и значительно быстрее. В самом деле, симулятор часто выполняет программно (затрачивая на это больше времени) то, что в реальности делается в «железе». Обратная ситуация возможна, например, когда гостевая система сама по себе гораздо «медленнее» хозяйской: моделируя 1 МГц микроконтроллер на 3 ГГц микропроцессоре, вполне можно гонять код его прошивки в десятки раз быстрее реальности. Ещё пример: если симулятор детектирует бездействие моделируемой системы (ожидание ресурсов или ввода, энергосберегающий режим), то он может продвинуть её время скачком вперёд, тем самым опередив реальность (см. «симуляция, управляемая событиями» ниже).
Важный частный случай: если симуляция подразумевает интерактивное взаимодействие с ней человека или, например, сетевое взаимодействие, то слишком высокая скорость ей противопоказана. Пример из жизни: приглашение login на Unix-системах сперва спрашивает имя, а затем пароль. Если после ввода имени программа не получает пароль некоторое время, она возвращается к вводу логина (видимо, это мера безопасности для случаев, если пользователя отвлекли при вводе пароля). При симуляции виртуальное время между вводом имени и ожиданием пароля может пролететь очень быстро, за долю реальной секунды — ведь гость бездействует! В результате несчастный человек не успевает залогиниться в ВМ ни с первой попытки, ни с пятой. Чтобы совсем испортить ему жизнь, через три секунды экран моделируемой системы чернеет — включается хранитель экрана, ведь для гостевой системы в бездействии прошёл уже час!
Конечно, это легко лечится введением «режима реального времени», когда сам симулятор делает паузы в своей работе, тем самым притормаживая течение времени в госте до среднего значения «секунда за секунду».
В обратную сторону, увы, это не работает. Если на каком-то вычислительно-сложном участке работы гостя симулятор успевает за одну реальную секунду продвинуть виртуальное время всего лишь на несколько миллисекунд, пользователь это заметит: «FPS упал». Компенсировать это уменьшением степени детализации, скорее всего, не получится: из загрузки ОС старт процессов не выкинешь, из программы-архиватора часть алгоритма не опустишь.
Первая идея, которая приходит на ум, когда надо промоделировать протекание некоторого процесса: выбрать достаточно маленький интервал за базовую неделимую единицу времени. Затем продвигать виртуальное время такими вот маленькими шагами, на каждом симулируя все изменения в системе, случившиеся за протекший интервал времени. Идея такого способа — изкурса вычматов практики моделирования аналоговых процессов и непрерывных во времени функций на дискретных ЭВМ.
Такой вид симуляции с фиксированным шагом (англ. time-stepped simulation) достаточно прост и наиболее гармонично сочетается со сценариями, когда на каждом шаге симуляции действительно есть какие-то события. Например, это верно для потактовых моделей цифровых устройств — при моделировании конвейера центрального процессора и сопутствующих узлов. В реальности на каждом фронте сигнала тактового генератора состояние регистров, очередей, счётчиков изменяются. Такая модель может быть сгенерирована инструментами, принимающими на вход описания на языках проектирования аппаратуры, таких как SystemVerilog или VHDL.
Однако в более верхнеуровневых моделях, таких как функциональные симуляторы и виртуальные машины, ситуация с событиями несколько иная. Такие программы оперируют моделями целых устройств (таймерами, дисками, сетевыми картами и т.д.) и транзакциями между ними. Именно транзакции, а не внутренние процессы, вызывают большую часть изменений в состояниях такой системы (моделировать которые — первоочередная задача симулятора), и при этом они асинхронны и не привязаны к какому-либо такту с фиксированной длиной. Симуляция с фиксированным шагом будет работать и для них, однако при этом окажется, что на большинстве шагов делать будет нечего — никаких видимых событий происходить не будет.
Более правильный подход для таких систем — поменять сущности ролями. Привязать продвижение виртуального времени к событиям, происходящим в симуляции. Этот подход естественным образом называется симуляция, управляемая событиями (англ. event driven simulation) [1].
Как организовать симуляцию в этом подходе? Необходимо завести единую очередь событий, в которой будут храниться запланированные, но ещё не свершившиеся события, отсортированные по близости к текущему моменту. Для этого вместе с каждым событием хранится метка времени (англ. time stamp).
Симуляция при этом происходит так: выбирается самое ранее из событий очереди, его эффекты симулируются. Значение виртуального времени при этом выставляется равным его метке времени.
Пример №1: моделирование периодического таймера. В подходе симуляции с фиксированным шагом нам пришлось бы хранить счётчик тактов внутри модели устройства и увеличивать его на каждом шаге. При этом для конфигурации с периодом, например, в тысячу тактов, 999 шагов симуляции из 1000 не имели бы никакого внешнего проявления. В подходе с управлением событиями моделируется лишь внешний эффект работы таймера — прерывания. Так как таймер периодический, то обработка каждого такого события порождает новое — запланированное в будущем через интервал времени. Симулируемое время продвигается «скачками» — ведь между событиями в очереди ничего нет!
Пример №2: при запросе данных от некоторого устройства оно отвечает не мгновенно, а с некоторой задержкой. Модель с фиксированным шагом потребовала бы отслеживать эту задержку внутри устройства, непрозрачно для симулятора. А так мы можем запланировать отклик через нужное время в очереди и, если между текущим моментом времени и откликом больше нет никаких событий, он будет обработан уже на следующем шаге.
Эти два примера можно обобщить на множество устройств, работающих параллельно в одной симуляции. Благодаря тому, что используется общая очередь, события будут обрабатываться в правильном порядке (согласно возрастанию меток времени), причинно-следственные отношения будут выдержаны.
Хочу подчеркнуть концептуальное отличие между симуляцией с фиксированным шагом и симуляцией, управляемой событиями. В первой за временем должны следить индивидуальные устройства, так как оно продвигается процессами, происходящими внутри них. Во втором случае устройства моделируются «чёрными ящиками» без темпорального состояния, а все течение времени централизованно управляется симуляцией.
Некоторые свойства симуляции, управляемой событиями.
1. Скорость её исполнения обратно пропорциональна плотности событий в очереди, а также средней вычислительной сложности отдельных событий. Если их очень мало и расстояние между ними велико, то симулируемое время будет значительно опережать реальное. В вырожденном случае, когда очередь пуста, виртуальное время должно принять бесконечно большое значение, что не очень удобно. На практике при работающей гостевой ОС этого не произойдёт, но вот если от модели «отключить питание», все таймеры внутри неё остановятся, и событий действительно не будет. В разных симуляторах эта ситуация обрабатывается по-разному: можно поставить симуляцию на паузу или вообще выйти из программы; можно всегда иметь минимум одно «мнимое» событие в очереди, выполняющее какую-нибудь служебную работу.
2. В случаях, когда события случаются часто, на каждом такте, и их много, симуляция, управляемая событиями, становится неудобной формой представления модели. В такой ситуации модель с фиксированным шагом более адекватно соответствует структуре системы.
3. Случается и так, что в одной симуляции должны присутствовать модели разных типов: например, центральные процессоры удобнее представлять как самостоятельно изменяющие собственное состояние на каждом шаге (т.н. симуляция, управляемая исполнением, англ. execution-driven simulation), а вот всяческую периферию удобнее моделировать, вынося события в очередь. В таком случае ничего не остаётся, как объединить оба класса моделей и научить их работать совместно. Действительно, между событиями в очереди достаточно много «места», так почему бы не заполнить их отрезками работы моделей, управляемых исполнением?
Кстати, этот подход имеет ещё одну приятную особенность с точки зрения производительности полной модели. Так как промежутки между событиями очереди обычно довольно большие — десятки и сотни тысяч тактов, то исполняющая модель процессора может довольно хорошо разогнаться на них, используя улучшенные техники симуляции, например, аппаратную поддержку виртуализации в форме Intel VT-x.
От чисто алгоритмических основ, реализуемых на любом языке программирования на любой архитектуре, перейдём теперь к вопросу представления времени в аппаратно-ускоренной симуляции (виртуализации) на основе расширений архитектуры Intel IA-32.
Кратко напомню о том, как это работает. В архитектуру ЦПУ вводятся отдельные режимы гипервизора (монитора) и гостя. В режиме гостя программы могут выполнять почти все (в том числе многие привилегированные) машинные инструкции напрямую, без необходимости какого-либо программного вмешательства. Однако операции, способные нарушить изоляцию гостя, вызывают выход в режим гипервизора, который проверяет допустимость совершения действия, симулирует его эффекты и возвращает управление обратно в режим гостя, для которого это происходит незаметно.
В теории такие переходы между гостем и монитором происходят редко, а всё остальное время гостевой код исполняется напрямую на аппаратуре с максимальной скоростью. На практике от создателя такого симулятора/виртуальной машины требуется определённое мастерство, чтобы обеспечить корректность и скорость работы монитора.
В предыдущей секции ход виртуального времени внутри модели был полностью подконтролен симулятору — именно в нём так или иначе продвигалось значение переменной, хранящей число прошедших секунд. В случае аппаратно-ускоренного симулятора для представления времени внутри моделей используется время физическое. Более того, отдельные виртуальные машины (ВМ) теперь делят общий ресурс — физическое время — с друг другом и управляющим ими супервизором — монитором ВМ. В таких условиях управлять временным хозяйством, как будет показано дальше, становится сложнее. С данной проблемой так или иначе пришлось иметь дело всем создателям виртуальных машин: KVM [3], ESX [4], Xen [5], VirtualBox [6].
Разберём две основные функции монитора по работе с реальным и виртуальным временем.
Нельзя позволять гостю по своей прихоти подвесить всю хозяйскую систему, зайдя, например, в бесконечный цикл с выключенными прерываниями, или же просто использовать непропорционально большую долю времени, не давая работать другим ВМ на той же системе.
Аналогичная задача стоит перед обычными ОС по отношению к прикладным программам. Как известно, решается она с помощью прерываний от таймера, которые вытесняют любую прикладную программу обратно в ОС. Похожие механизмы доступны и для мониторов.
Вспомним, что работа самого монитора может занимать значительное время, в течение которого гость не исполняется, и поэтому виртуальное время последнего не должно продвигаться. Опять же, если на одной системе одновременно запущено несколько ВМ, каждая из них будет получать время на исполнение небольшими отрезками.
На следующем рисунке приведён пример чередующегося исполнения двух ВМ, переключаемых с помощью монитора.
В реальности прошло времени: t_host = t1_1 + t_mon1 + t2_1 + t_mon2 + t_1_2 + t_mon3 + t_2_2 + t_mon4 + t1_3 + t_mon5 + t2_3
Время, которое прошло в первой ВМ: t_ВМ1 = t1_1 + t1_2 + t1_3
Время для второй ВМ: t_ВМ2 = t2_1 _ t2_2 + t2_3
В задачу монитора при этом входит учёт (скорее, сокрытие) всего «потерянного» для отдельных ВМ времени. Соответственно все события гостевой ОС, такие как прерывания от таймеров, должны сдвигаться так, чтобы происходить в правильные моменты именно виртуального времени.
Следует отметить, что требование скрывать реальное время не является абсолютным — в ряде сценариев использования виртуальных машин (в т.ч. при паравиртуализации) удобнее всегда сообщать физическое время, не пряча работу монитора. Но в этом случае гостевая ОС должна учитывать тот факт, что в её работе могут присутствовать неконтролируемые паузы.
Как и реальная система, система гостевая может периодически обращаться ко всему зоопарку устройств, предоставляющих время и описанных в предыдущей заметке: RTC, PIT, APIC timer, ACPI PM-timer, HPET, TSC. Первые пять из этого списка — внешние к ЦПУ устройства, поэтому и подходы к их виртуализации похожи.
Работа с периферийными устройствами идёт через программирование их регистров. Регистры же доступны или через пространство портов (PIO, programmable input/output), тогда используются инструкции IN/OUT, или по заданным адресам физической памяти (MMIO, memory-mapped input/output), и тогда работа с ними ведётся обыкновенными инструкциями MOV. В обоих случаях технология VT-x позволяет настраивать, что будет происходить при попытках обращений к устройствам изнутри ВМ — выход в монитор или же обыкновенный доступ.
В первом случае в задачи монитора входит эмуляция взаимодействия с программной моделью соответствующего устройства, в точности так, как это было бы и в чисто программных решениях, не использующих аппаратное ускорение. При этом длительность обработки каждого доступа может быть больше, чем при обращении к реальному устройству. Однако почти всегда частота обращений к регистрам таймеров невелика, поэтому накладные расходы от виртуализации приемлемо малые. На практике я встречал одно исключение — некоторые ОС, обнаружив в системе HPET, начинают очень часто и настойчиво его читать. Это вызывает заметное замедление симуляции.
Конечно, хотелось бы разрешить прямой доступ к таймерам, однако на практике это редко когда возможно. Во-первых, реальное устройство-таймер может уже использоваться монитором для собственных нужд, а позволять гостю вмешиваться в работу монитора недопустимо. Во-вторых, один реальный таймер нельзя разделить на части, а ведь в одной системе может быть несколько ВМ, и каждой нужна своя копия устройства.
Как было упомянуто в предыдущей моей заметке, real-time clock (RTC) является энергонезависимым устройством — даже когда питание компьютера выключено, устройство хранит текущую дату и время. Это создаёт небольшую особенность при моделировании RTC: какую дату/время оно должно возвращать после цикла выключения/включения ВМ? Одно из решений — просто копировать значение текущего времени хозяйской системы. В принципе оно удобно, если все остальные изменения энергонезависимых хранилищ (жёстких дисков, SSD, flash, NVRAM и т.п.) внутри гостя делаются «необратимым» образом, то есть сразу фиксируются в конфигурации ВМ. Однако часто ВМ используются в режиме старта с неизменяемого образа диска; при этом все записи сохраняются во временный файл, который после выключения ВМ по умолчанию теряется. Это полезно в тех случаях, когда требуются полностью повторяемые запуски симуляции, скажем, для регрессионного тестирования. В таком случае синхронизация моделируемого RTC с настоящим вредна. Типичная ситуация: стартует гостевой Linux, и вместо быстрого перехода к многопользовательскому режиму начинает длительное сканирование (fsck) на ошибки! Происходит это из-за того, что в файловой системе на образе диска сохраняется время последней проверки. Перед монтированием ФС Linux проверяет, как давно она совершалась последний раз, и, если значение времени из RTC значительно отличается от того, которое было использовано при создании образа, то на всякий случай запускает проверку. Конечно, можно выключить данную функциональность с помощью tunefs, однако мало кто вспоминает об этом при создании образа.
Похожая ерунда будет, например, происходить с программой make, если из-за ошибки в значении RTC все даты у файлов на моделируемой ФС окажутся в будущем.
Перейдём теперь к вопросу виртуализации TSC (англ. time-stamp counter). В отличие от остальных устройств-таймеров этот счётчик находится непосредственно на процессоре, и доступ к нему идёт через инструкции RDTSC, RDTSCP и RDMSR[IA32_TSC].
Как и в случае с другими таймерами, существует два подхода к виртуализации TSC — это перехват всех обращений c последующей чисто программной эмуляцией, или же разрешение прямого чтения значения, основанного на TSC, в госте.
В архитектуре VT-x за поведение RDTSC внутри режима гостя отвечает бит «RDTSC exiting» контрольной структуры VMCS, а за поведение RDTSCP — другой бит, «RDTSCP enable». То есть обе инструкции (а также RDMSR[IA32_TSC], трактуемый как вариант RDTSC), могут быть перехвачены и программно проэмулированы. Этот метод довольно медленный: просто чтение TSC занимает десяток циклов, тогда как полный цикл выхода из гостя в монитор, эмуляция и возвращение обратно — это тысячи циклов. Для ряда сценариев, которые не используют RDTSC часто, эффект замедления от эмуляции незаметен. Однако другие сценарии могут пытаться «узнать время» с помощью RDTSC каждые несколько сотен инструкций (зачем это им — отдельный вопрос), что, конечно же, приводит к замедлению.
В случае, когда прямое исполнение соответствующих инструкций по чтению TSC разрешено, монитор может задать смещение возвращаемого значения относительно реального с помощью поля «TSC offset» VMCS и тем самым компенсировать время, в течение которого каждый гость был заморожен. При этом гость будет получать значение TSC + TSC_OFFSET.
К сожалению, прямое исполнение RDTSC(P) несёт в себе множество неудобных моментов. Один из них состоит в невозможности (или, по крайней мере, чрезвычайной сложности) фиксации точного момента, когда заканчивает работу монитор и начинает гость — ведь TSC «тикает» постоянно, а процессы переходов между режимами процессора немгновенны и имеют неизвестную переменную длительность. Возникает некая пограничная зона, для которой непонятно, к какому из «миров» приписать проведённые в ней такты. В результате очень трудно понять, какие значения TSC мог видеть гость, и это создаёт ошибку в несколько тысяч тактов на одно переключение «гость-монитор-гость». Такая ошибка может довольно быстро накапливаться и проявляться очень странным образом.
Вторая проблема существенна для мониторов ВМ в облачных окружениях [5]. Хотя с помощью TSC_OFFSET мы и можем задать первоначальное значение для TSC при входе в режим гостя, темп изменения TSC после этого невозможно изменить. Это создаст проблемы при горячей миграции запущенной гостевой ОС с одной хозяйской машины на другую с иным значением частоты TSC. Так как калибровка таймеров обычно проводится только при первоначальной загрузке, после такого перемещения гостевая ОС будет неправильно планировать события.
В результате можно сказать, что современное состояние технологии аппаратно ускоренной виртуализации не содержит методов для эффективной (в устоявшейся терминологии) виртуализации счётчика TSC. Или реальность так или иначе «протискивается» в виртуальное окружение, или всё работает очень медленно. Конечно, далеко не все приложения настолько чувствительны, чтобы сломаться внутри гостя при прямом исполнении RDTSC(P). Особенно если писать программы так, чтобы они учитывали возможность запуска внутри симулятора. И всё же многие решения для виртуализации перешли к использованию программной эмуляции TSC по умолчанию — хоть оно и медленнее, но зато надёжнее. Пользователь должен самостоятельно включить режим прямого исполнения, если TSC создаёт проблемы с производительностью, и если он готов исследовать странные падения, связанные с иным течением времени, в своих сценариях.
Кратко упомяну некоторые другие аспекты, связанные с понятием времени внутри симуляции. Наверное, стоит отложить более подробный рассказ о них на будущее, но и совсем обойти вниманием в этой заметке нельзя.
Задачи слежения за, измерения и учёта времени всегда были нетривиальными в науке и технике. Область программной разработки не является исключением. Я надеюсь, что мне удалось показать её с неожиданной или просто интересной позиции создателя симуляторов вычислительных систем.
От того, как организовано течение виртуального времени, зависит скорость работы и точность представления симулятора, а также совместимость её с другими программными симуляторами.
При проектировании новой или расширении существующей программной среды для моделирования вычислительных устройств вопрос о способе представления виртуального времени должен являться первоочередным. Нельзя откладывать его или надеяться, что «переиспользуем реальное время, как-нибудь заработает». Я несколько раз наблюдал, как пренебрежение этим вопросом при сопряжении двух симуляторов, по-разному управляющих временем, приводило к ненадёжным или медленно функционирующим результатам.
Спасибо за внимание и пусть время в ваших моделях всегда течёт предсказуемым образом!
В этой статье мы разберём различные способы представления времени внутри моделей, подходы к имитации работы таймеров, возможности аппаратного ускорения при виртуализации, а также трудности согласования течения времени внутри моделируемых окружений.
Под симуляторами и виртуальными машинами будут подразумеваться такие программы, как Bochs, KVM/Qemu, Vmware ESX, Oracle Virtualbox, Wind River Simics, Microsoft HyperV и т.д. Они позволяют загружать внутри себя немодифицированные операционные системы. Соответственно внутри модели компьютера должны содержаться модели отдельных устройств: процессоров, памяти, плат расширений, устройств ввода/вывода и т.д., а также, конечно же, часов, секундомеров и будильников.
Требования
Как и в предыдущей статье, начнём обсуждение с требований, предъявляемых к понятию «время» внутри симуляторов и виртуальных машин.
...
Здесь был длинный околофилософский опус о свойствах времени в модели и повторяемости исходов параллельных программ, но он был сокращён, дабы пощадить читателя.
Два важных свойства «правильной» симуляции.
1. Представление состояния некоторой реальной системы и её компонент с некоторой наперёд выбранной точностью. Течение времени в модели может быть приближённым и довольно сильно отличаться от реальности.
2. Допустимая в реальности эволюция состояния внутри модели.
Для этого железно должна работать причинно-следственная связь. За исключением, пожалуй, каких-то совсем экзотических систем, эволюция моделируемой системы должна правильно упорядочивать связанные события. Желающим глубже изучить этот очень непростой вопрос порекомендую начинать с работ Лесли Лампорта [2] или аналогичных статей по распределённым алгоритмам.
Это покажется странным, но остальные условия на виртуальное время не являются столь же универсальными; однако рассмотрим их.
Условие строгой монотонности течения времени. Чаще всего виртуальное время не должно убывать с течением физического времени. Как показал мой опыт, подход «мы тут на минуточку уменьшим время» обычно ведёт к жуткой путанице при отладке и является признаком плохого дизайна.
В ряде не совсем типичных, но всё же практически важных случаев виртуальное время должно двигаться вспять: при откате состояния оптимистичных параллельных моделей, или при обратном исполнении.
Наконец, сложные компьютерные системы (и их модели) бывают распределёнными. Для них требование единых общих часов может быть избыточно строгим — части такой системы должны уметь нормально работать, имея лишь ограниченную локальную информацию о времени. В них глобальное время становится «векторной» величиной. Как известно, векторы довольно сложно сравнивать по принципу «больше-меньше».
Условие соответствия симулируемого времени реальному чаще всего избыточно. Как показала моя практика, подразумевать какую-либо корреляцию между ними вредно для проектировщика симулятора, так как это создаёт необоснованные ожидания и мешает создать корректную или быструю модель. Самый простой пример: виртуальную машину всегда можно поставить на паузу; при этом время внутри неё остановится, реальное время мы пока что остановить не в силах.
Более интересный пример. При работе симуляции темп изменения симулируемого времени может динамически меняться. Оно может быть как медленнее реального, так и значительно быстрее. В самом деле, симулятор часто выполняет программно (затрачивая на это больше времени) то, что в реальности делается в «железе». Обратная ситуация возможна, например, когда гостевая система сама по себе гораздо «медленнее» хозяйской: моделируя 1 МГц микроконтроллер на 3 ГГц микропроцессоре, вполне можно гонять код его прошивки в десятки раз быстрее реальности. Ещё пример: если симулятор детектирует бездействие моделируемой системы (ожидание ресурсов или ввода, энергосберегающий режим), то он может продвинуть её время скачком вперёд, тем самым опередив реальность (см. «симуляция, управляемая событиями» ниже).
Важный частный случай: если симуляция подразумевает интерактивное взаимодействие с ней человека или, например, сетевое взаимодействие, то слишком высокая скорость ей противопоказана. Пример из жизни: приглашение login на Unix-системах сперва спрашивает имя, а затем пароль. Если после ввода имени программа не получает пароль некоторое время, она возвращается к вводу логина (видимо, это мера безопасности для случаев, если пользователя отвлекли при вводе пароля). При симуляции виртуальное время между вводом имени и ожиданием пароля может пролететь очень быстро, за долю реальной секунды — ведь гость бездействует! В результате несчастный человек не успевает залогиниться в ВМ ни с первой попытки, ни с пятой. Чтобы совсем испортить ему жизнь, через три секунды экран моделируемой системы чернеет — включается хранитель экрана, ведь для гостевой системы в бездействии прошёл уже час!
Конечно, это легко лечится введением «режима реального времени», когда сам симулятор делает паузы в своей работе, тем самым притормаживая течение времени в госте до среднего значения «секунда за секунду».
В обратную сторону, увы, это не работает. Если на каком-то вычислительно-сложном участке работы гостя симулятор успевает за одну реальную секунду продвинуть виртуальное время всего лишь на несколько миллисекунд, пользователь это заметит: «FPS упал». Компенсировать это уменьшением степени детализации, скорее всего, не получится: из загрузки ОС старт процессов не выкинешь, из программы-архиватора часть алгоритма не опустишь.
Программное моделирование
Первая идея, которая приходит на ум, когда надо промоделировать протекание некоторого процесса: выбрать достаточно маленький интервал за базовую неделимую единицу времени. Затем продвигать виртуальное время такими вот маленькими шагами, на каждом симулируя все изменения в системе, случившиеся за протекший интервал времени. Идея такого способа — из
Такой вид симуляции с фиксированным шагом (англ. time-stepped simulation) достаточно прост и наиболее гармонично сочетается со сценариями, когда на каждом шаге симуляции действительно есть какие-то события. Например, это верно для потактовых моделей цифровых устройств — при моделировании конвейера центрального процессора и сопутствующих узлов. В реальности на каждом фронте сигнала тактового генератора состояние регистров, очередей, счётчиков изменяются. Такая модель может быть сгенерирована инструментами, принимающими на вход описания на языках проектирования аппаратуры, таких как SystemVerilog или VHDL.
Однако в более верхнеуровневых моделях, таких как функциональные симуляторы и виртуальные машины, ситуация с событиями несколько иная. Такие программы оперируют моделями целых устройств (таймерами, дисками, сетевыми картами и т.д.) и транзакциями между ними. Именно транзакции, а не внутренние процессы, вызывают большую часть изменений в состояниях такой системы (моделировать которые — первоочередная задача симулятора), и при этом они асинхронны и не привязаны к какому-либо такту с фиксированной длиной. Симуляция с фиксированным шагом будет работать и для них, однако при этом окажется, что на большинстве шагов делать будет нечего — никаких видимых событий происходить не будет.
Более правильный подход для таких систем — поменять сущности ролями. Привязать продвижение виртуального времени к событиям, происходящим в симуляции. Этот подход естественным образом называется симуляция, управляемая событиями (англ. event driven simulation) [1].
Как организовать симуляцию в этом подходе? Необходимо завести единую очередь событий, в которой будут храниться запланированные, но ещё не свершившиеся события, отсортированные по близости к текущему моменту. Для этого вместе с каждым событием хранится метка времени (англ. time stamp).
Симуляция при этом происходит так: выбирается самое ранее из событий очереди, его эффекты симулируются. Значение виртуального времени при этом выставляется равным его метке времени.
Пример №1: моделирование периодического таймера. В подходе симуляции с фиксированным шагом нам пришлось бы хранить счётчик тактов внутри модели устройства и увеличивать его на каждом шаге. При этом для конфигурации с периодом, например, в тысячу тактов, 999 шагов симуляции из 1000 не имели бы никакого внешнего проявления. В подходе с управлением событиями моделируется лишь внешний эффект работы таймера — прерывания. Так как таймер периодический, то обработка каждого такого события порождает новое — запланированное в будущем через интервал времени. Симулируемое время продвигается «скачками» — ведь между событиями в очереди ничего нет!
Пример №2: при запросе данных от некоторого устройства оно отвечает не мгновенно, а с некоторой задержкой. Модель с фиксированным шагом потребовала бы отслеживать эту задержку внутри устройства, непрозрачно для симулятора. А так мы можем запланировать отклик через нужное время в очереди и, если между текущим моментом времени и откликом больше нет никаких событий, он будет обработан уже на следующем шаге.
Эти два примера можно обобщить на множество устройств, работающих параллельно в одной симуляции. Благодаря тому, что используется общая очередь, события будут обрабатываться в правильном порядке (согласно возрастанию меток времени), причинно-следственные отношения будут выдержаны.
Хочу подчеркнуть концептуальное отличие между симуляцией с фиксированным шагом и симуляцией, управляемой событиями. В первой за временем должны следить индивидуальные устройства, так как оно продвигается процессами, происходящими внутри них. Во втором случае устройства моделируются «чёрными ящиками» без темпорального состояния, а все течение времени централизованно управляется симуляцией.
Аналогия из мира ОС
Я прослеживаю здесь некоторую аналогию с методами планирования задач в ОС. Классический подход — это использование периодического (с частотой HZ от 100 до 1000 Гц) прерывания таймера для вытеснения текущего процесса, возвращения в ОС, которая проверяет, требуется ли выполнить какую-либо служебную работу. Как оказалось, большинство таких прерываний не нужны — ОС просыпается только для того, чтобы понять, что делать нечего. Ясно, что это неоптимальное поведение, особенно учитывая, что частые пробуждения процессора не позволяют ему перейти в глубокий энергосберегающий режим. В т.н. tickless ядрах ОС подход другой — прерывания устанавливаются ровно на тот момент, когда требуется выполнить следующую порцию системной работы.
Некоторые свойства симуляции, управляемой событиями.
1. Скорость её исполнения обратно пропорциональна плотности событий в очереди, а также средней вычислительной сложности отдельных событий. Если их очень мало и расстояние между ними велико, то симулируемое время будет значительно опережать реальное. В вырожденном случае, когда очередь пуста, виртуальное время должно принять бесконечно большое значение, что не очень удобно. На практике при работающей гостевой ОС этого не произойдёт, но вот если от модели «отключить питание», все таймеры внутри неё остановятся, и событий действительно не будет. В разных симуляторах эта ситуация обрабатывается по-разному: можно поставить симуляцию на паузу или вообще выйти из программы; можно всегда иметь минимум одно «мнимое» событие в очереди, выполняющее какую-нибудь служебную работу.
2. В случаях, когда события случаются часто, на каждом такте, и их много, симуляция, управляемая событиями, становится неудобной формой представления модели. В такой ситуации модель с фиксированным шагом более адекватно соответствует структуре системы.
3. Случается и так, что в одной симуляции должны присутствовать модели разных типов: например, центральные процессоры удобнее представлять как самостоятельно изменяющие собственное состояние на каждом шаге (т.н. симуляция, управляемая исполнением, англ. execution-driven simulation), а вот всяческую периферию удобнее моделировать, вынося события в очередь. В таком случае ничего не остаётся, как объединить оба класса моделей и научить их работать совместно. Действительно, между событиями в очереди достаточно много «места», так почему бы не заполнить их отрезками работы моделей, управляемых исполнением?
Кстати, этот подход имеет ещё одну приятную особенность с точки зрения производительности полной модели. Так как промежутки между событиями очереди обычно довольно большие — десятки и сотни тысяч тактов, то исполняющая модель процессора может довольно хорошо разогнаться на них, используя улучшенные техники симуляции, например, аппаратную поддержку виртуализации в форме Intel VT-x.
Аппаратно ускоренная виртуализация
От чисто алгоритмических основ, реализуемых на любом языке программирования на любой архитектуре, перейдём теперь к вопросу представления времени в аппаратно-ускоренной симуляции (виртуализации) на основе расширений архитектуры Intel IA-32.
Кратко напомню о том, как это работает. В архитектуру ЦПУ вводятся отдельные режимы гипервизора (монитора) и гостя. В режиме гостя программы могут выполнять почти все (в том числе многие привилегированные) машинные инструкции напрямую, без необходимости какого-либо программного вмешательства. Однако операции, способные нарушить изоляцию гостя, вызывают выход в режим гипервизора, который проверяет допустимость совершения действия, симулирует его эффекты и возвращает управление обратно в режим гостя, для которого это происходит незаметно.
В теории такие переходы между гостем и монитором происходят редко, а всё остальное время гостевой код исполняется напрямую на аппаратуре с максимальной скоростью. На практике от создателя такого симулятора/виртуальной машины требуется определённое мастерство, чтобы обеспечить корректность и скорость работы монитора.
В предыдущей секции ход виртуального времени внутри модели был полностью подконтролен симулятору — именно в нём так или иначе продвигалось значение переменной, хранящей число прошедших секунд. В случае аппаратно-ускоренного симулятора для представления времени внутри моделей используется время физическое. Более того, отдельные виртуальные машины (ВМ) теперь делят общий ресурс — физическое время — с друг другом и управляющим ими супервизором — монитором ВМ. В таких условиях управлять временным хозяйством, как будет показано дальше, становится сложнее. С данной проблемой так или иначе пришлось иметь дело всем создателям виртуальных машин: KVM [3], ESX [4], Xen [5], VirtualBox [6].
Разберём две основные функции монитора по работе с реальным и виртуальным временем.
Ограничение длительности интервалов пребывания системы в режиме гостя
Нельзя позволять гостю по своей прихоти подвесить всю хозяйскую систему, зайдя, например, в бесконечный цикл с выключенными прерываниями, или же просто использовать непропорционально большую долю времени, не давая работать другим ВМ на той же системе.
Аналогичная задача стоит перед обычными ОС по отношению к прикладным программам. Как известно, решается она с помощью прерываний от таймера, которые вытесняют любую прикладную программу обратно в ОС. Похожие механизмы доступны и для мониторов.
- Использование хозяйского таймера для ограничения времени нахождения процессора в режиме гостя. При правильном программировании контрольных структур VMCS гостевая ОС не сможет проигнорировать внешние прерывания, даже если замаскировала их внутри себя, и событие таймера вызовет переход в монитор.
- В последних ревизиях VT-x появилась новая функциональность, именуемая Preemption Timer. Это новый счётчик, работающей с периодом, кратным TSC процессора. Его значение начинает уменьшаться при переходе в режим гостя. По достижении нуля происходит обратный выход в монитор. В целом Preemption Timer имеет большую точность и упрощает дизайн монитора, так как оставляет обычный таймер для остальных задач.
- Интересный подход заключается в использовании счётчиков производительности, в частности счётчиков инструкций и тактов. Их можно запрограммировать так, что при их переполнении будет вызываться прерывание. Это позволяет ограничивать (и измерять) не только время работы гостя, но и число исполненных инструкций, что бывает удобно при построении симуляторов.
Отслеживание, сколько на самом деле прошло времени внутри каждого гостя
Вспомним, что работа самого монитора может занимать значительное время, в течение которого гость не исполняется, и поэтому виртуальное время последнего не должно продвигаться. Опять же, если на одной системе одновременно запущено несколько ВМ, каждая из них будет получать время на исполнение небольшими отрезками.
На следующем рисунке приведён пример чередующегося исполнения двух ВМ, переключаемых с помощью монитора.
В реальности прошло времени: t_host = t1_1 + t_mon1 + t2_1 + t_mon2 + t_1_2 + t_mon3 + t_2_2 + t_mon4 + t1_3 + t_mon5 + t2_3
Время, которое прошло в первой ВМ: t_ВМ1 = t1_1 + t1_2 + t1_3
Время для второй ВМ: t_ВМ2 = t2_1 _ t2_2 + t2_3
В задачу монитора при этом входит учёт (скорее, сокрытие) всего «потерянного» для отдельных ВМ времени. Соответственно все события гостевой ОС, такие как прерывания от таймеров, должны сдвигаться так, чтобы происходить в правильные моменты именно виртуального времени.
Следует отметить, что требование скрывать реальное время не является абсолютным — в ряде сценариев использования виртуальных машин (в т.ч. при паравиртуализации) удобнее всегда сообщать физическое время, не пряча работу монитора. Но в этом случае гостевая ОС должна учитывать тот факт, что в её работе могут присутствовать неконтролируемые паузы.
Виртуализация устройств-таймеров
Как и реальная система, система гостевая может периодически обращаться ко всему зоопарку устройств, предоставляющих время и описанных в предыдущей заметке: RTC, PIT, APIC timer, ACPI PM-timer, HPET, TSC. Первые пять из этого списка — внешние к ЦПУ устройства, поэтому и подходы к их виртуализации похожи.
Работа с периферийными устройствами идёт через программирование их регистров. Регистры же доступны или через пространство портов (PIO, programmable input/output), тогда используются инструкции IN/OUT, или по заданным адресам физической памяти (MMIO, memory-mapped input/output), и тогда работа с ними ведётся обыкновенными инструкциями MOV. В обоих случаях технология VT-x позволяет настраивать, что будет происходить при попытках обращений к устройствам изнутри ВМ — выход в монитор или же обыкновенный доступ.
В первом случае в задачи монитора входит эмуляция взаимодействия с программной моделью соответствующего устройства, в точности так, как это было бы и в чисто программных решениях, не использующих аппаратное ускорение. При этом длительность обработки каждого доступа может быть больше, чем при обращении к реальному устройству. Однако почти всегда частота обращений к регистрам таймеров невелика, поэтому накладные расходы от виртуализации приемлемо малые. На практике я встречал одно исключение — некоторые ОС, обнаружив в системе HPET, начинают очень часто и настойчиво его читать. Это вызывает заметное замедление симуляции.
Конечно, хотелось бы разрешить прямой доступ к таймерам, однако на практике это редко когда возможно. Во-первых, реальное устройство-таймер может уже использоваться монитором для собственных нужд, а позволять гостю вмешиваться в работу монитора недопустимо. Во-вторых, один реальный таймер нельзя разделить на части, а ведь в одной системе может быть несколько ВМ, и каждой нужна своя копия устройства.
Виртуализация RTC
Как было упомянуто в предыдущей моей заметке, real-time clock (RTC) является энергонезависимым устройством — даже когда питание компьютера выключено, устройство хранит текущую дату и время. Это создаёт небольшую особенность при моделировании RTC: какую дату/время оно должно возвращать после цикла выключения/включения ВМ? Одно из решений — просто копировать значение текущего времени хозяйской системы. В принципе оно удобно, если все остальные изменения энергонезависимых хранилищ (жёстких дисков, SSD, flash, NVRAM и т.п.) внутри гостя делаются «необратимым» образом, то есть сразу фиксируются в конфигурации ВМ. Однако часто ВМ используются в режиме старта с неизменяемого образа диска; при этом все записи сохраняются во временный файл, который после выключения ВМ по умолчанию теряется. Это полезно в тех случаях, когда требуются полностью повторяемые запуски симуляции, скажем, для регрессионного тестирования. В таком случае синхронизация моделируемого RTC с настоящим вредна. Типичная ситуация: стартует гостевой Linux, и вместо быстрого перехода к многопользовательскому режиму начинает длительное сканирование (fsck) на ошибки! Происходит это из-за того, что в файловой системе на образе диска сохраняется время последней проверки. Перед монтированием ФС Linux проверяет, как давно она совершалась последний раз, и, если значение времени из RTC значительно отличается от того, которое было использовано при создании образа, то на всякий случай запускает проверку. Конечно, можно выключить данную функциональность с помощью tunefs, однако мало кто вспоминает об этом при создании образа.
Похожая ерунда будет, например, происходить с программой make, если из-за ошибки в значении RTC все даты у файлов на моделируемой ФС окажутся в будущем.
Виртуализация TSC
Перейдём теперь к вопросу виртуализации TSC (англ. time-stamp counter). В отличие от остальных устройств-таймеров этот счётчик находится непосредственно на процессоре, и доступ к нему идёт через инструкции RDTSC, RDTSCP и RDMSR[IA32_TSC].
Как и в случае с другими таймерами, существует два подхода к виртуализации TSC — это перехват всех обращений c последующей чисто программной эмуляцией, или же разрешение прямого чтения значения, основанного на TSC, в госте.
В архитектуре VT-x за поведение RDTSC внутри режима гостя отвечает бит «RDTSC exiting» контрольной структуры VMCS, а за поведение RDTSCP — другой бит, «RDTSCP enable». То есть обе инструкции (а также RDMSR[IA32_TSC], трактуемый как вариант RDTSC), могут быть перехвачены и программно проэмулированы. Этот метод довольно медленный: просто чтение TSC занимает десяток циклов, тогда как полный цикл выхода из гостя в монитор, эмуляция и возвращение обратно — это тысячи циклов. Для ряда сценариев, которые не используют RDTSC часто, эффект замедления от эмуляции незаметен. Однако другие сценарии могут пытаться «узнать время» с помощью RDTSC каждые несколько сотен инструкций (зачем это им — отдельный вопрос), что, конечно же, приводит к замедлению.
В случае, когда прямое исполнение соответствующих инструкций по чтению TSC разрешено, монитор может задать смещение возвращаемого значения относительно реального с помощью поля «TSC offset» VMCS и тем самым компенсировать время, в течение которого каждый гость был заморожен. При этом гость будет получать значение TSC + TSC_OFFSET.
К сожалению, прямое исполнение RDTSC(P) несёт в себе множество неудобных моментов. Один из них состоит в невозможности (или, по крайней мере, чрезвычайной сложности) фиксации точного момента, когда заканчивает работу монитор и начинает гость — ведь TSC «тикает» постоянно, а процессы переходов между режимами процессора немгновенны и имеют неизвестную переменную длительность. Возникает некая пограничная зона, для которой непонятно, к какому из «миров» приписать проведённые в ней такты. В результате очень трудно понять, какие значения TSC мог видеть гость, и это создаёт ошибку в несколько тысяч тактов на одно переключение «гость-монитор-гость». Такая ошибка может довольно быстро накапливаться и проявляться очень странным образом.
Моя борьба c TSC
Я пытался недавно реализовать хитрую схему, манипулирующую как хозяйским, так и гостевым TSC. Мне удалось понизить ошибку в измерении гостевого времени до сотен тактов, однако при этом начало «плыть» TSC-время хозяйской ОС, что совсем не здорово, особенно на многопроцессорных системах. Пришлось отказаться от моей хитрой схемы. На самом деле для нормальной реализации не хватает «атомарно-мгновенного» обмена значениями TSC гостя и хозяина.
Вторая проблема существенна для мониторов ВМ в облачных окружениях [5]. Хотя с помощью TSC_OFFSET мы и можем задать первоначальное значение для TSC при входе в режим гостя, темп изменения TSC после этого невозможно изменить. Это создаст проблемы при горячей миграции запущенной гостевой ОС с одной хозяйской машины на другую с иным значением частоты TSC. Так как калибровка таймеров обычно проводится только при первоначальной загрузке, после такого перемещения гостевая ОС будет неправильно планировать события.
В результате можно сказать, что современное состояние технологии аппаратно ускоренной виртуализации не содержит методов для эффективной (в устоявшейся терминологии) виртуализации счётчика TSC. Или реальность так или иначе «протискивается» в виртуальное окружение, или всё работает очень медленно. Конечно, далеко не все приложения настолько чувствительны, чтобы сломаться внутри гостя при прямом исполнении RDTSC(P). Особенно если писать программы так, чтобы они учитывали возможность запуска внутри симулятора. И всё же многие решения для виртуализации перешли к использованию программной эмуляции TSC по умолчанию — хоть оно и медленнее, но зато надёжнее. Пользователь должен самостоятельно включить режим прямого исполнения, если TSC создаёт проблемы с производительностью, и если он готов исследовать странные падения, связанные с иным течением времени, в своих сценариях.
Прочие вопросы
Кратко упомяну некоторые другие аспекты, связанные с понятием времени внутри симуляции. Наверное, стоит отложить более подробный рассказ о них на будущее, но и совсем обойти вниманием в этой заметке нельзя.
- Повторяемость (детерминизм) симуляции и возможность обращения времени. Эти связанные свойства симуляции (и симулятора) крайне полезны при отладке гостевых программ. Чисто программное моделирование (без использования аппаратного ускорения) легко допускает написание моделей с такими свойствами. Использование аппаратного ускорения TSC, наоборот, вносит неопределённость течения времени с реального процессора внутрь виртуальности. При этом такое влияние очень трудно скомпенсировать: одни и те же процессы внутри модели могут занимать немного разное время в разных прогонах программы, что проявится в различиях возвращаемых RDTSC значений. При этом мы не можем ни контролировать вызовы, ни даже узнать о том, что они случились — никакой нотификации в архитектуре не предусмотрено.
- Время во многоядерных гостях и на многопроцессорных хозяйских системах. Про построение параллельных моделей параллельных систем я писал в цикле постов: 1, 2, 3, и 4. Рекомендую книгу [1] тем, кому интересен данный вопрос.
- Измерение производительности программ, запущенных внутри симулятора/виртуальной машины. Очень интересный вопрос, требующий отдельного исследования. Действительно, из-за наличия двух временных осей (реальной и виртуальной) возникает множество вопросов: какие метрики производительности измерять, следует ли учитывать время работы монитора при изучении гостя, как обеспечить эффективный доступ к счётчикам производительности и что они должны считать и т.д. Непростым отношениям виртуализации и профилировки приложений посвящён пост.
Заключение
Задачи слежения за, измерения и учёта времени всегда были нетривиальными в науке и технике. Область программной разработки не является исключением. Я надеюсь, что мне удалось показать её с неожиданной или просто интересной позиции создателя симуляторов вычислительных систем.
От того, как организовано течение виртуального времени, зависит скорость работы и точность представления симулятора, а также совместимость её с другими программными симуляторами.
При проектировании новой или расширении существующей программной среды для моделирования вычислительных устройств вопрос о способе представления виртуального времени должен являться первоочередным. Нельзя откладывать его или надеяться, что «переиспользуем реальное время, как-нибудь заработает». Я несколько раз наблюдал, как пренебрежение этим вопросом при сопряжении двух симуляторов, по-разному управляющих временем, приводило к ненадёжным или медленно функционирующим результатам.
Спасибо за внимание и пусть время в ваших моделях всегда течёт предсказуемым образом!
Литература
- Richard M. Fujimoto. Parallel and Distributed Simulation Systems. 1st Ed. New York, NY, USA: John Wiley & Sons, Inc., 2000. ISBN 0471183830.
- Leslie Lamport. Time, clocks, and the ordering of events in a distributed system // Communications of the ACM 21 (7)- 1978 — pp. 558–565. research.microsoft.com/users/lamport/pubs/time-clocks.pdf
- Zachary Amsden. Timekeeping Virtualization for X86-Based Architectures. www.kernel.org/doc/Documentation/virtual/kvm/timekeeping.txt
- Vmware Inc. Timekeeping in VMware Virtual Machines. www.vmware.com/files/pdf/Timekeeping-In-VirtualMachines.pdf
- Dan Magenheimer. TSC_MODE HOW-TO. xenbits.xen.org/docs/4.3-testing/misc/tscmode.txt
- virtualbox.org End user forums. Disable rdtsc emulation. forums.virtualbox.org/viewtopic.php?f=1&t=60980
