Прежде чем отправиться в приятное путешествие PA

PA — это совершенно новый вид тренировки

Мы сравниваем разные задания/эксперименты/задачи по следующим аспектам:

Основные принципы	План действий	Риск корректности	Примеры
Изложено	Ясно	В основном верно	Школьная лабораторная по физике
Изложено	Ясно	Может пойти не так	Задания по программированию
Изложено	Нужно разбираться	В основном верно	Математические доказательства / задачи на проектирование алгоритмов
Изложено	Нужно разбираться	Может пойти не так	PA, OSlab
Нужно исследовать	Нужно разбираться	Может пойти не так	Реальная задача в индустрии / академии

Конечная цель PA — глубже понять, как программы работают на компьютерах, построив простую и полную компьютерную систему. В отличие от заданий по программированию вроде «рекурсивно реализовать Ханойские башни», компьютерные системы гораздо сложнее Ханойских башен. Это значит, что тренировки в стиле заданий по программированию недостаточно, чтобы выполнить PA, и единственный способ выполнить PA — пытаться понять и освоить каждую деталь компьютерной системы, шаг за шагом.

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

Это может быть беспрецедентный для вас способ тренировки, поэтому вам нужно принять новый вызов с новым отношением.

Правильный способ делать PA — начните сегодня, не ленитесь (это миска куриного супа; когда в будущем почувствуете себя потерянным, вернитесь сюда и прочитайте)

Перечислим некоторые ошибки.

• Если возникла проблема, попробуйте чинить вслепую, может, пройдёт.
• Если вслепую починить не получается, плакать ассистенту (TA), чтобы он решил проблему за вас.
• Не хотите тратить время и силы, следуя How-To-Ask-Questions-The-Smart-Way и Stop-Ask-Questions-The-Stupid-Ways.
• Эту функцию/файл/команду не понять, всё равно не я писал, забей
• Лучше уютно тратить жизнь в Baidu, чем быстро решить проблему через Google.
• Вопросы в синем блоке не считаются, можно не читать.
• Всё равно на большой этап есть месяц, начну на последней неделе, ещё успею.

Если вы примете подход выше, вы, возможно, очень быстро выполните раннее содержание эксперимента, но ценой отказа от возможностей тренировки. По мере продвижения эксперимента вы почувствуете, что PA становится для вас всё большим вызовом.

Правильно делать так:

• Больше думайте, почему
  • Начать с проблемы, чтобы понять систему, — тоже хороший метод
• Решайте проблемы самостоятельно.
  • Даже если это починка глупого бага, вы узнаете больше, чем думаете.
  • Другими словами, если вы решите опираться на других, вы упустите больше возможностей, чем осознаёте
• Пытайтесь понять каждую деталь
  • когда дело доходит до починки багов, эти детали — мощный инструмент в ваших руках
  • Другими словами, когда вы теряетесь, крутя баг, это потому что вы не понимаете детали
• Делать вещи правильными инструментами
  • Это наука экономии времени, а не лень
• Читайте хендауты. Там много пасхалок.
  • В хендаутах много «не ко времени» подсказок, и некоторые из них нужно прочитать больше одного раза, чтобы понять.
  • Ещё один вопрос в синем блоке может сэкономить вам несколько дней починки багов.
• Заканчивайте вовремя, не откладывайте
  • Чтобы у вас было время сделать всё перечисленное выше

На самом деле эти практики — самая существенная тренировка в PA, и такая тренировка уже началась в PA0: PA0 заставляет ставить машину с нуля, чтобы вы набирали опыт, решая маленькие проблемы, который можно использовать для больших; одновременно это распространяет исходную веру «я могу самостоятельно решать проблемы через STFW и RTFM», и эта вера помогает развеять страх неизвестного.

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

Что такое NEMU?

Цель PA — реализовать NEMU, упрощённый полносистемный эмулятор. Но что такое эмулятор?

В детстве вы, вероятно, играли в NES, Super Mario, Tanks, Contra... Вы ещё помните их графику? (Надеюсь, между нами нет поколенческого разрыва...) Со временем машины NES на рынке почти не найти. Пока вы расстраиваетесь, появление эмуляторов пробудило детские воспоминания. Эмулятор NES может симулировать для вас все игры NES. С ним это как будто у вас настоящая NES, и вы можете играть в любимые игры NES. Мы портировали проект эмулятора NES FCEUX, который вы уже клонировали в PA0. Удивительно, что в эпоху после NES вы снова можете пережить детские дни в этом эмуляторе!

Разве вы не собираетесь поиграть?

Мы предоставили ROM некоторых игр для тестирования здесь (может понадобиться доступ из кампусной сети); прочитайте и следуйте fceux-am/README.md, чтобы запустить Super Mario во всплывающем окне

Вы также можете положить другие ROM-файлы, полученные через STFW, чтобы запускать другие игры.

Проверьте экран, кнопки и звук

Во время запуска игры нужно проверить, что вы видите экран, реагируете на нажатия кнопок и слышите звук. Super Mario не играет звук на начальном экране, но будет играть звук, когда вы войдёте на уровень. Если звука нет, это повлияет на необязательную часть PA, но не на оценку; однако если экран отображается неправильно, это может повлиять на обязательную часть PA, поэтому ищите решение самостоятельно.

Чтобы проверить кнопки, нужно клонировать новый подпроект am-kernels, в котором есть тестовые программы:

cd ics2023
bash init.sh am-kernels

Затем запустите одну из программ теста кнопок.

cd am-kernels/tests/am-tests
make ARCH=native mainargs=k run

После запуска всплывёт новое окно; нажмите клавишу в новом окне, и вы увидите, что программа выводит в терминал соответствующую информацию о клавише: имя клавиши, код клавиатуры и состояние клавиши. Если выходная информация о клавише не совпадает с нажатой, ищите решение самостоятельно (ключевые слова вроде "SDL keystroke" и т.д.). Некоторые пользователи предполагают, что проблема может быть связана с проблемой совместимости китайского метода ввода, для справки.

Мне кажется, компиляция немного медленная?

Программа make по умолчанию использует один поток, чтобы компилировать все файлы последовательно, а у FCEUX очень много исходных файлов, так что вы можете ждать до десяти секунд, пока компиляция завершится. Но сейчас CPU многоядерные и многопоточные, так что не использовать эту вычислительную мощность — пустая трата. Чтобы ускорить компиляцию, мы можем заставить make создать несколько потоков и компилировать файлы параллельно.

Для этого сначала запросите, сколько CPU в вашей системе, командой lscpu. Затем запускайте make с параметром -j?, где ? — число CPU, которое вы запросили. Например, -j4 значит создать 4 потока для параллельной компиляции; если число CPU в системе больше или равно 4, операционная система может запланировать эти 4 потока на 4 CPU одновременно и получить ускорение; однако если в системе только 2 CPU, операционная система сможет запланировать максимум 2 потока на 2 CPU одновременно, и эффект ускорения будет похож на -j2.

Чтобы увидеть, как ускорение компиляции влияет на вас, можете добавить команду time перед командой компиляции: она посчитает время выполнения следующих за ней команд, так что вам нужно смотреть колонку total. Можете очистить все результаты через make clean, затем перекомпилировать и посчитать время, сравнивая однопоточную компиляцию с многопоточной; также можете пробовать разное число потоков и сравнивать ускорения.

Всё ещё слишком медленно?

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

Такой инструмент действительно есть! Он называется ccache.

apt-get install ccache

Если вы прочитаете руководство ccache через man, увидите, что ccache — это compiler cache. cache — термин из компьютерной области, и вы изучите его в последующем курсе ICS.

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

which gcc

По умолчанию она выводит /usr/bin/gcc, то есть когда вы запускаете gcc, на самом деле выполняется /usr/bin/gcc. Как упражнение в RTFM вам нужно прочитать содержимое man ccache и согласно руководству задать переменную окружения в файле .bashrc. Если настройка верна и действует, снова выполните which gcc, и вы увидите, что вывод стал /usr/lib/ccache/gcc. Если вы не знаете про переменные окружения и .bashrc, STFW.

Теперь пора испытать эффект ccache. Сначала make clean, чтобы очистить результат, затем перекомпилируйте и посчитайте время. Вы заметите, что на этот раз чуть дольше, чем раньше, потому что ccache тратит время на сохранение целевого файла вдобавок к обычной компиляции. Если снова очистить результаты, перекомпилировать и посчитать время, вы увидите, что вторая компиляция гораздо быстрее! Это значит, что ccache действительно ускоряет процесс, пропуская полностью повторяющуюся компиляцию. Если использовать вместе с многопоточной компиляцией, компиляцию можно ускорить ещё сильнее!

В процессе разработки проекта иногда действительно нужен fresh build после make clean результатов компиляции. На поздних этапах PA вы можете много раз компилировать библиотеки из сотен файлов, и в этих случаях ccache сильно экономит время компиляции и тем самым повышает эффективность проекта.

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

На самом деле NEMU делает нечто похожее! Он симулирует аппаратный мир, в котором можно выполнять программы. Другими словами, в PA вы будете писать программу, которая выполняет другие программы! Чтобы лучше понять функциональность NEMU, вот что можно сделать

• Запускать программы Hello World в GNU/Linux.
• Играть в Super Mario в GNU/Linux через эмулятор NES.
• Запускать программу Hello World через NEMU в GNU/Linux.

Сравните эти три сценария.

                         +---------------------+  +---------------------+
                         |     Super Mario     |  |    "Hello World"    |
                         +---------------------+  +---------------------+
                         |    Simulated NES    |  |      Simulated      |
                         |       hardware      |  |       hardware      |
+---------------------+  +---------------------+  +---------------------+
|    "Hello World"    |  |     NES Emulator    |  |        NEMU         |
+---------------------+  +---------------------+  +---------------------+
|      GNU/Linux      |  |      GNU/Linux      |  |      GNU/Linux      |
+---------------------+  +---------------------+  +---------------------+
|    Real hardware    |  |    Real hardware    |  |    Real hardware    |
+---------------------+  +---------------------+  +---------------------+
          (a)                      (b)                     (c)

Рисунок (a) иллюстрирует сценарий «Hello World в GNU/Linux». Операционная система GNU/Linux работает напрямую на реальном компьютерном железе, абстрагирует нижележащее компьютерное железо и предоставляет интерфейсы и сервисы пользовательским программам верхнего уровня. Когда программа Hello World выводит информацию, ей нужен интерфейс, предоставленный операционной системой, поэтому Hello World работает не напрямую на реальном железе, а на операционной системе (в данном случае GNU/Linux).

Рисунок (b) показывает «игру в Super Mario на эмуляторе NES в GNU/Linux». Для GNU/Linux эмулятор NES, работающий на нём, не более чем пользовательская программа, как и Hello World выше. Удивительное в том, что эмулятор NES отвечает за симуляцию полного набора железа NES, на котором может работать Super Mario. То, что Super Mario не может отличить, работает ли он на реальном железе NES или на симулированном, — это повязка на глаза «эмулятора».

Рисунок (c) иллюстрирует «Hello World в GNU/Linux через NEMU». Для GNU/Linux NEMU, работающий на нём, — просто пользовательская программа, как Hello World выше. Однако NEMU отвечает за эмуляцию набора компьютерного железа, на котором могут работать программы. На самом деле рисунок выше даёт только базовое понимание NEMU, больше деталей будет добавлено в последующих PA.

Что такое NEMU?

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

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

Аналогично NEMU — симулированная компьютерная система: базовые функции физического компьютера в NEMU реализованы через программу. Симулировать компьютерную систему не так трудно, как вы думаете. Компьютер можно мыслить как набор аппаратных компонентов, которые помогают друг другу «запускать программу». В NEMU каждый аппаратный компонент моделируется связанным с программой объектом данных: переменной, массивом, структурой и т.д.; а операции над этими компонентами моделируются операциями над соответствующими объектами данных. Например, NEMU использует массив для симуляции памяти, так что чтение или запись в этот массив эквивалентны чтению или записи в память.

Процесс реализации NEMU можно мыслить как разработку приложения Alipay. Разница в том, что у Alipay функциональность настоящего банкомата, она для транзакций, а у NEMU — функциональность физической компьютерной системы, она для выполнения программ. Поэтому мы говорим, что NEMU — программа, которая выполняет другие программы.

Мощь NEMU вас удивит! Он не только может запускать маленькие программы вроде Hello World, но позже в PA вы сможете запустить классическую RPG Chinese Paladin(круто! %>_<%). Если вы выполните всё необязательное программирование, вы даже сможете запустить современную текстовую приключенческую игру CLANNAD в NEMU! После PA ваши знания о программировании с курса программирования перевернутся: вы почувствуете, что компьютеры больше не таинственный чёрный ящик, и даже можете обнаружить, что создать собственный компьютер уже не за пределами досягаемости!

Выберите своего персонажа

Новая возможность — несколько главных линий

У PA есть свойство нескольких главных линий. Конкретно, вам нужно начать с одной из трёх x86 / mips32 / riscv32(64) архитектур набора команд (ISA), чтобы осуществить мечту «создать свой компьютер».

Но какую бы ISA вы ни выбрали, вы в итоге осознаете механику «железо и ПО работают вместе, чтобы поддерживать выполнение программы»: так называемый tradeoff — просто решение, оставить что-то железу или ПО. Однако у каждой из трёх ISA свои особенности, и уровень сложности разных глав показан в таблице ниже (5 звёзд — легко, 1 звезда — трудно).

	x86	mips32	riscv32(64)
PA1 - Простой отладчик	Не очень связано с выбором ISA
PA2 - Компьютерные системы фон Неймана
PA3 - Системы пакетной обработки
PA4 - Разделение времени, многозадачность

Что такое ISA?

Большинство учебников скажут что-то вроде «ISA — интерфейс между ПО и железом», но для тех из вас, кто ещё не понимает, как ПО и железо работают вместе, слово «интерфейс» всё ещё слишком абстрактно.

Чтобы понять ISA, возьмём пример из жизни: винт и гайка — два обычных предмета, которые нужно спаривать. Дан винт — нужно найти гайку той же размерной спецификации, и наоборот.

В компьютерном мире похоже: компьютеры (или железо) разных архитектур — как винты разных размеров, программы (или ПО) разных архитектур — как гайки разных размеров, и если программа должна работать на компьютере конкретной архитектуры, программа и компьютер должны соответствовать одному набору спецификаций.

Поэтому суть ISA — нечто вроде такой спецификации. Так что ISA существует не как аппаратная схема и не как программный код, а как руководство со спецификациями.

Подобно производству гаек и болтов, компьютерное железо строится по руководству спецификации ISA, а программы пишутся (или порождаются) по руководству спецификации ISA. Что внутри спецификации ISA, как построить компьютер, соответствующий спецификации, и как программа должна соблюдать спецификацию, чтобы работать на компьютере, — ответ на эти вопросы есть одна из целей выполнения PA.

Как мне выбрать?

Если идёте за знакомым, берите x86: теоретические занятия ICS в основном крутятся вокруг x86. Но вы, вероятно, умрёте от сложности инструкций x86, и конечная производительность x86 на самом деле недостаточно высока, чтобы плавно показать игру.

Если идёте за простотой, берите riscv32, и вы поймёте, что значит «элегантный дизайн ISA». Из-за простоты riscv32 вы легко получите почти вдвое большую производительность, чем у x86.

Если дальше собираетесь проектировать аппаратный процессор riscv64, берите riscv64, и вы увидите, как DiffTest поможет резко повысить эффективность аппаратной разработки и избавиться от нудной отладки по осциллограммам (waveform).

Если хотите раздвинуть границы, берите mips32: по сравнению с двумя выше, mips32 требует гораздо больше деталей, чтобы правильно построить полную компьютерную систему. Поэтому mips32 только для тех, кто любит вызов, или для тех, кто делает второй проход.

Однако какую бы ISA вы ни выбрали, одно общее — это RTFM, потому что ISA по сути руководство со спецификациями. Также сама программа NEMU — x86 (точнее x64) и не меняется в зависимости от выбранной ISA, меняется только компьютер, эмулируемый в NEMU.

Если вы студент, зачисленный на эту программу (Основы компьютерных систем), у вас нет выбора!

Вы должны выбрать riscv32, иначе ваш код не будет корректно работать при сдаче на OJ. Мы просим вас так сделать, потому что

• riscv модульный, и выбор riscv32 предполагает реализацию очень малого числа инструкций.
• Вы уже изучали riscv32 на курсе «Цифровая логика и устройство компьютера» во втором семестре, так что riscv32 вам будет привычнее, чем другие ISA.
• инфраструктура каркасного кода лучше поддерживает riscv.

Все эти причины помогут вам более гладко выполнить PA, чтобы можно было уделить больше времени финалу.

Для удобства хендаут будет использовать $ISA, чтобы обозначать выбранную вами ISA: например, для nemu/src/isa/$ISA/reg.c, если вы выбрали x86, это будет обозначать nemu/src/isa/x86/reg.c; если вы выбрали riscv32 — nemu/src/isa/riscv32/reg.c. Если хендаут явно не говорит иное, $ISA всегда указывает выбранную вами ISA, а не четыре символа $ISA.

Каркасный код NEMU использует riscv32 как ISA по умолчанию; если хотите выбрать другую ISA, выполните make menuconfig в каталоге проекта NEMU, затем переключитесь на выбранную ISA в меню Base ISA, сохраните конфигурацию и выйдите из меню.

Наконец, вам нужно забрать пакет новичка — связанные с ISA руководства по выживанию (некоторые руководства, не связанные с ISA, можно найти на домашней странице хендаутов.

ISA	Пакет новичка
x86	Intel 80386 Programmer's Reference Manual (简称i386手册) (PDF)(HTML) System V ABI for i386
mips32	MIPS32 Architecture For Programmers (Volume I, Volume II, Volume III) System V ABI for mips32
riscv32(64)	The RISC-V Instruction Set Manual (Volume I, Volume II) ABI for riscv

riscv32 и riscv64

На самом деле различия между riscv32 и riscv64 настолько малы, что их руководства ISA одинаковы. Поэтому большая часть описаний в хендаутах для riscv32 применима и к riscv64. Там, где описания не применимы к riscv64, мы добавили дополнительную информацию. Поэтому если вы выбрали riscv64, можете опираться на хендаут riscv32, если в нём нет дополнительных сведений про riscv64.

Чего вы ждёте?

Давайте начнём это захватывающее путешествие!

Будьте квалифицированным CS-ером!

Помимо конечной цели показать, как программа выполняется в компьютере, PA добавил много научных принципов. PA пытается создавать сценарии, чтобы вы осознали важность этих принципов, а это также обязательно для квалифицированного CS-ера. Если вы смотрите на PA лишь как на большую программную миссию, мы считаем, что вы ошибаетесь.

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

Записывайте свои эксперименты каждый день

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

Мы верим, что когда вы вернётесь к этим записям после PA, вы поймёте, что это ценное достояние для вас.