ОС реального времени в эмуляторе Mario, или Как устроены потоки

предыдущем посте ^[1] о потоках я привёл импровизированное сравнение^{1 [2]}:

Потоки^{2 [3]} — это просто состояния сохранения^{3 [4]} эмулятора^{4 [5]}, связанные с условием, при котором продолжается их выполнение.

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

Поэтому я добавил многопоточность в Super Mario Bros. для NES.

Сама система

Не будем ходить вокруг да около.

Что это такое

Мне стоит объясниться. То, что вы только что увидели — многопоточная эмуляция NES, где в качестве потоков используется игра Super Mario Bros.

Работает три «потока», каждый из которых является отдельным экземпляром игры. Время от времени эмулятор переключает «потоки», переходя к другому экземпляру игры.

Каждому «потоку» присвоена своя палитра, которая применяется, когда мы продолжаем соответствующий поток. Именно поэтому в видео цвета постоянно меняются.

Чуть больше конкретики…

5 ^[6]. Затем я создаю потоки^{6 [7]} и даю им соответствующее состояние сохранения, которое они удерживают.

Затем я запускаю планировщик потоков.

Задача планировщика проста:

• Каждые 160 кадров переключаться на новый поток.
  • В идеале — на следующий поток, в порядке ротации (1, 2, 3, 1, 2, 3, 1, …).
  • Пропускать потоки, которые уничтожены (KILLED), заблокированы (BLOCKED) (если только их нельзя разблокировать) или погружены в сон (SLEEPING) (если только не настало время их разбудить).
• Для переключения на следующий поток:
  • Сначала обновляем состояние сохранения текущего потока текущим состоянием игры.
  • Затем загружаем состояние сохранения нового потока.
  • Далее обновляем цветовую палитру игры, чтобы отразить поток, в котором мы находимся.

Это описывает то, что мы видим в первой части видео: каждый поток запускается одновременно (экран загрузки World 1-1) и время от времени переключаются разные «игры».

По сути, мы играем в три отдельные игры Mario Bros. «одновременно», но в любой момент времени активна только одна из них.

Не только квантование времени

На этом изображении показана полная карта World 1-1, где различными цветами закодированы описанные ниже особенности.

Квантование времени — это круто: мы выполняем три «конкурентные» игры Mario! Но это далеко не единственная концепция потоков, которую мы здесь покажем.

Я настроил игровой мир таким образом, чтобы определённые области или признаки активировали примитивы синхронизации (например, мьютекс); вы можете физически взаимодействовать с границами потоков.

Созданные мной примитивы синхронизации я объясню ниже, а пока краткое описание:

• Если Марио стоит на трёх блоках в начале уровне, то ни одна игра не запустится, пока он с них не сойдёт (отключённые прерывания).
• Одновременно в подуровне трубы может находиться только один Марио (мьютекс).
  • Если Марио войдёт в трубу, пока внутри находится другой Марио, то игра не продолжится, пока другой Марио не выйдет.
• Когда Марио касается флагштока, его игра приостанавливается, пока все остальные Марио не коснутся своих флагштоков (переменные условия).

▍ Отключённые прерывания

Областью с красным оттенком на карте обозначена часть мира, в которой прерывания отключены, а значит, планировщик потоков запускаться не может.

Когда Марио входит в красную область, его поток не теряет управления, пока он не покинет эту область, вне зависимости от того, что делают другие Марио.

▍ Мьютексы

Жёлтая область (её сложно заметить — это четвёртая труба слева; та, в которую можно опуститься) демонстрирует мьютекс: область мира игры, в которой одновременно может существовать только один Марио.

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

Однако если мьютексом владеет другой Марио (то есть он находится на подуровне трубы), то Марио, опускающийся в трубу, будет заблокирован, пока мьютекс не будет освобождён (другой Марио не выйдет из подуровня).

Все Марио вне подуровня не блокируются и могут продолжать выполнение.

▍ Переменные условия

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

▍ Сон

Каждый раз, когда Марио убивает врага, его поток уходит в сон на 300 кадров.

Это сложно понять по видео, но уходящий в сон поток необязательно возвращается вовремя; ему приходится ждать, пока планировщик потоков не решит в следующий раз запустить его.

В чём смысл всего этого?

▍ Во-первых, это невероятно круто

7 ^[8]) выполнять более одной задачи одновременно и добавили к ней конкурентность, не меняя при этом базового движка (или CPU) и реализовав при этом концепцию «потоков».

Мы добавили в этот эмулятор потоки точно так же, как мы добавляем потоки в обычных CPU: хитро воспользовались механизмом, который позволяет нам А) сохранять текущее состояние машины и Б) загружать его обратно, если и когда нам это нужно. И для этого всего не нужно, чтобы сам эмулятор проектировался с учётом концепции «потоков».

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

▍ Но моя самая главная задача заключалась в том, сорвать покров загадочности

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

Если вы начинаете сегодня заниматься разработкой ПО, то вас обязательно забросит в заросли абстракций. В этих землях можно провести десятки лет: изучать новые фреймворки; осваивать новые стеки; бесконечно проводить исследования во всех направлениях, кроме загадочной глубины. В эту глубину идти не нужно. Никто не знает, что за этой преградой.

8 ^[9]. Мы не можем пользоваться роскошью применения этих слоёв в качестве незыблемого фундамента, даже не пытаясь проникнуть туда и просто веря, что он выдержит наш дом. Ну да, мы построили дом, нашу отрасль ценой в триллионы долларов, и она уверенно стоит. Но если фундамент развалится, то какой толк в доме? Когда фундамент обязан поменяться, то как мы внесём свой вклад в этот процесс, если знаем только, как строить поверх него? Как мы сможем точно рассуждать о новом фундаменте, ничего не зная о том, как был построен старый?

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

Сложность заключается в том, как обеспечить крайнюю эффективность работы потоков. Переключение контекстов? Это не особо сложно. Максимально оптимизировать их при помощи структур данных и алгоритмов? Обычно на этом фронте моя интуиция меня подводит — я не гуру computer science. Но для реализации базовых инноваций в потоках ничего из этого не требуется.

И это справедливо для практически всего подобного: всё это относительно простые идеи! Чтобы понять их, достаточно понять структуру и логическую последовательность; не требуется погружаться в сложную математику или алгоритмы, чтобы воспринять базовую идею. А поняв её, можно добавить её к своему фундаментальному пониманию; в скелете концепций появится новая кость, обогащая работу вверх по стеку совершенно непредсказуемым образом.

9 ^[10]. После того, как вы это сделаете, ваше восприятие любого другого фреймворка обогатится навсегда.

Прежде чем я создал эту систему, мне было сложно говорить о том, как реализовать мьютекс — раньше я этого никогда не делал! Моя реализация совершенно точно ужасна — это наивное, упрощённое решение, которое работает лишь благодаря тому, что ставки очень низки. Но это нормально: зато я могу увидеть следующие шаги. Способы, которыми можно совершенствоваться. Благодаря работе над этим (даже благодаря нахождению проблем, решения которых я пытаюсь избежать) мой мозг ^[11] неосознанно создаёт пути и связи между концепциями.

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

Как это сделано

Для начала мне надо было найти опенсорсный эмулятор NES и добавить эту функциональность непосредственно в его исходный код. Это было бы для меня достаточно необычным и впечатляющим процессом. Но затем я нашёл эмулятор FCEUX ^[12], имеющий систему плагинов Lua, через которую я мог реализовать всё необходимое мне. Ура.

Написав несколько сотен строк кода на Lua ^[13], я создал функциональный планировщик потоков с поддержкой мьютексов, переменных условий, маскирования прерываний, сна и так далее.

Я крайне рекомендую вам самостоятельно изучить код, но всё равно приведу некоторые объяснения.

▍ 0. Точим когти

Прежде, чем создавать планировщик потоков, нам нужно освоиться в окружении. Мы пишем Lua-плагин для эмулятора NES… какие возможности у нас есть?

К счастью, документация ^[14] оказалась достаточно полезной — мы уже видим, что у нас есть нужные инструменты:

1. Создание состояния сохранения (savestate.create()и savestate.save()).
   1. Так мы «сохраняем» поток, чтобы возобновить его позже.
2. Загрузка состояния сохранения (savestate.load()).
   1. Так мы возобновляем поток, ранее отправленный в сон.
3. Чтение памяти из ОЗУ игры (memory.readbyte()).
   1. Так мы понимаем, на каком уровне находится игрок, его координаты внутри уровня и так далее.
   2. Чтобы понять, где находятся самые важные биты ОЗУ игры, мы используем полезный документ ^[15].
4. Отрисовка текста на экране (gui.drawtext()).
   1. Так мы забиваем большую часть экрана непонятной информацией.
5. Управление выполнением кадров в эмуляторе (emu.frameadvance()).
   1. Наш код на Lua должен вызывать эту функцию, когда должен выполниться кадр игры.
      1. Это позволяет нам выполнять всё необходимое между кадрами.

Вот и всё, что нам нужно!

Давайте начнём с базового «пустого» скрипта, который функционально идентичен полному отсутствию скрипта:

while true do
    emu.advanceframe()
end

▍ 1. Определяем, когда игрок запускает игру

Мы хотим вмешаться и запустить многопоточность только тогда, когда игрок начал игру.

Я не знаю, какое решение лучше всего, поэтому просто решил подключиться к адресам памяти GAME_MODE (0x0770) и PRE_LEVEL_SCREEN_SHOWING (0x0757). Когда каждое из значений равно 1, мы знаем, что игра запущена и отображает экран перед уровнем. На мой взгляд, это подходящее место, чтобы вмешаться.

Вот, как это выглядит:

function initiate()
    emu.frameadvance()

    if not emu.emulating() then
        return
    end

    local gameMode = memory.readbyte(0x0770)
    local preLevelScreen = memory.readbyte(0x0757)

    if gameMode ~= 1 or preLevelScreen ~= 1 then
        return
    end

    initiated = true
end

function loop()
    emu.frameadvance()
end

while true do
    if not initiated then
        initiate()
    else
        loop()
    end
end

Код работает, но пока ничего не делает

▍ 2. Запускаем многопоточность

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

Помните: потоки — это всего лишь «снимки» (снэпшоты) состояния и условие, при котором они должны продолжиться.

Пока мы не будем обращать внимание на это «должны продолжиться», и целиком сосредоточимся на квантовании времени.

Итак, вот, что нам понадобится:

• Список потоков.
  • Каждый из них имеет:
    • ID.
    • Состояние сохранения.
• Понятие «текущего потока».
• Способ переключения с «текущего потока» на какой-то другой поток.
• Таймер, отслеживающий, когда мы должны переключать потоки.

Вот полная реализация квантования времени:

THREAD_SWITCH_FREQUENCY = 100
NUM_THREADS = 3

local threads = {}
local curThreadIndex = nil
local curFrame = 0
local lastSwitchedThreads = 0

local initiated = false

function shouldRunScheduler()
    return (curFrame - lastSwitchedThreads) >= THREAD_SWITCH_FREQUENCY
end

function threadScheduler()
    local newThreadIndex = curThreadIndex + 1

    if newThreadIndex > NUM_THREADS then
        newThreadIndex = 1
    end

    local oldThread = threads[curThreadIndex]
    local newThread = threads[newThreadIndex]

    savestate.save(oldThread.saveState)
    savestate.load(newThread.saveState)

    curThreadIndex = newThreadIndex
end

function initiate()
    emu.frameadvance()

    if not emu.emulating() then
        return
    end

    local gameMode = memory.readbyte(0x0770)
    local preLevelScreen = memory.readbyte(0x0757)

    if gameMode ~= 1 or preLevelScreen ~= 1 then
        return
    end
    
    for i = 1, NUM_THREADS do
        local thread = {}
        thread.id = i
        thread.saveState = savestate.create()

        savestate.save(thread.saveState)
        table.insert(threads, thread)
    end

    initiated = true
    curThreadIndex = 1
    threadScheduler()
end

function loop()
    emu.frameadvance()

    if shouldRunScheduler() then
        threadScheduler()
        lastSwitchedThreads = curFrame
    end
end

while true do
    curFrame = curFrame + 1

    if not initiated then
        initiate()
    else
        loop()
    end
end

Это работает! Запустите World 1-1, и вы начнёте переключаться между тремя потоками, полностью теряя всё удовольствие от процесса игры.

▍ 3. Пишем код остальной части планировщика потоков

Думаю, на этом стоит перестать рассказывать о подробностях реализации.

Пока у нас есть только функция, способная по запросу переключать потоки, но остальные части добавить будет не так сложно:

• Приоритеты потоков.
• Сон.
• Блокировка ресурсов (мьютексы, семафоры и так далее).
• Всё то, что вам заблагорассудится!.

Я рекомендую вам самостоятельно попробовать весь код (ссылка приведена выше)!

Как его попробовать

Для начала приобретите легальную копию ROM Super Mario Bros. для NES. В этом я вам помогать не буду.

FCEUX ^{[12]10 [16]}. Нажмите на ссылку в статье и скачайте неподписанный исполняемый файл. Давайте.

В-третьих, скачайте скрипт на Lua ^[13] и сохраните его на компьютер.

В-четвёртых, прочитайте скрипт и убедитесь, что я не пытаюсь вас заставить хитростью скачать зловреда.

В-пятых, откройте FCEUX. Нажмите на File → Load Lua Script. Нажмите на Browse, затем найдите сохранённый файл Lua. Нажмите на Load, а затем на Start.

В-шестых, нажмите на File → Open ROM. Найдите скачанный файл ROM.

В-седьмых, сыграйте в игру. Возможно, вам понадобится настроить управление в Options → Input Config.

В-восьмых, заметьте, что постоянное переключение между тремя экземплярами Super Mario Bros. — неприятный процесс, да он и не должен быть таковым.

Двигаемся дальше

▍ Взаимные блокировки

На самом деле, я не создавал ситуацию, в которой может возникнуть истинная взаимная блокировка (A удерживает X, B удерживает Y, A пытается получить Y, пока B пытается получить X), но её может обрабатывать (в примитивном виде) планировщик потоков.

11 ^[17], планировщик потоков прекращает игру и показывает сообщение об ошибке.

Ситуация наподобие взаимной блокировки может возникнуть, когда каждый Марио ожидает мьютекса для опускания в трубу, а Марио внутри трубы умирает. На самом деле это повисший мьютекс, но давайте называть его взаимной блокировкой (deadlock).

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

▍ «Истинная» конкурентность

Что, если планировщик потоков будет работать гораздо чаще?

ПРЕДУПРЕЖДЕНИЕ: наверно, это видео может вызвать эпилептический припадок.

Заключение

Этот планировщик нельзя назвать хорошим.

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

Нравится, потому что я смог создать нечто (то, что когда-то считал магией) примерно в трёхстах строках на Lua. Раньше я такого никогда не делал! Тем не менее, вот он, мой собственный планировщик потоков в самой неожиданной и забавной из сред. Возможно, это станет моим аналогом запуска DOOM — я буду превращать каждую видеоигру в потоки. А может, и нет.

Это один из тех проектов, каждый аспект которых доставляет удовольствие. Как безумно было видеть впервые его работу! Честно говоря, я отчасти не верил, что он когда-нибудь заработает.

Надеюсь, он научил вас тому, что такое потоки.

Примечания

↩ ^[17]

↩ ^[18]

↩ ^[19]

Они делают это благодаря эмуляции оборудования консоли, выполняя для этого кучу сложных операций.

↩ ^[20]

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

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

↩ ^[21]

↩ ^[22]

Я создаю не поток реальной операционной системы, а структуру данных потока, похожую на ту структуру данных, которую создаёт ваша ОС, когда вы «создаёте поток». Это не просто тонкая обёртка вокруг потоков ОС, а реальная реализация потоков с нуля.

↩ ^[23]

↩ ^[24]

Мы строим слишком жадно и забираемся слишком высоко, пренебрегая отдельными знаниями, которые мы, современные профессионалы, не должны забывать, убеждая себя, что они нам не нужны. Это неправильно.

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

Но потоки? UTF-8? Код стандартных библиотек? Они не относятся к этой категории.

↩ ^[25]

↩ ^[26]

↩ ^[27]

Для решения этой задачи многие ОС используют удобный трюк: выделенную «пустую задачу» (idle task), имеющую самый низкий приоритет и выполняемую, когда не может выполняться ни один из остальных потоков.

Этот трюк я не реализовал.