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

В своём предыдущем посте о потоках я привёл импровизированное сравнение¹:

Потоки² — это просто состояния сохранения³ эмулятора⁴, связанные с условием, при котором продолжается их выполнение.

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

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

Сама система

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

Что это такое

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

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

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

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

Когда запускается World 1-1, начинается «многопоточность». В частности мой скрипт создаёт три состояния сохранения, каждое из которых описывает текущее состояние игры⁵. Затем я создаю потоки⁶ и даю им соответствующее состояние сохранения, которое они удерживают.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

▍ Мьютексы

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

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

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

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

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

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

▍ Сон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изучать фреймворки фронтенда полезно. На такой работе можно заработать миллиарды долларов! Но ничто не даст вам понимания концепции фреймворков фронтенда в той же степени, как создание собственного фреймворка⁹. После того, как вы это сделаете, ваше восприятие любого другого фреймворка обогатится навсегда.

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

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

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

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

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

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

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

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

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

1. Создание состояния сохранения (savestate.create()и savestate.save()).
   1. Так мы «сохраняем» поток, чтобы возобновить его позже.
2. Загрузка состояния сохранения (savestate.load()).
   1. Так мы возобновляем поток, ранее отправленный в сон.
3. Чтение памяти из ОЗУ игры (memory.readbyte()).
   1. Так мы понимаем, на каком уровне находится игрок, его координаты внутри уровня и так далее.
   2. Чтобы понять, где находятся самые важные биты ОЗУ игры, мы используем полезный документ.
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¹⁰. Нажмите на ссылку в статье и скачайте неподписанный исполняемый файл. Давайте.

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

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

В-пятых, откройте 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), но её может обрабатывать (в примитивном виде) планировщик потоков.

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

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

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

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

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

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

Заключение

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

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

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

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

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

Примечания

1. Я ещё наобещал всякого о том, каким будет следующий пост. Простите, я нарушил эти обещания.↩

2. Которые используются в многопоточности и в hyperthreading.↩

3. В этом контексте эмуляторы — это программы, позволяющие играть в консольные игры (NES, SNES, GameBoy, Xbox, PlayStation и так далее) на компьютере.↩

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

4. Состояние сохранения (save state) в эмуляторе (например, в том, в котором я играю в игру для NES Super Mario Bros.) — это файл, содержащий копию памяти, регистров CPU и так далее эмулируемого оборудования консоли.↩

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

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

5. Так как все три состояния сохранения создаются в одно время, во всех них хранится одно и то же исходное состояние игры.↩

6. «Поток» в этом контексте — это очень простой объект Lua, создаваемый моим кодом.↩

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

7. Или отказом?↩

8. Я уже довольно давно размышляю об этой идее — «цемент ещё не застыл», поэтому, наверно, стоит развернуть её в этом примечании.↩

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

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

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

9. К слову, ничто не позволит вам так ощутить опыт неудачи, как попытки популяризировать собственный доморощенный JavaScript-фреймворк.↩

10. Если вы работаете на Mac, но не знаете, что такое «homebrew», то здесь у вас возникнут проблемы.↩

11. Мой планировщик потоков вылетит, если все потоки одновременно уснут.↩

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

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

Telegram-канал со скидками, розыгрышами призов и новостями IT 💻