OS/8 (Левашев Иван, ИТМО '2020)

Материал из CSC Wiki
Версия от 04:51, 20 октября 2018; Octagram.name (обсуждение | вклад) (Компоненты)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Операционная система Восемь

Автор: Левашев Иван

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

Предположительно, хорошее описание сути

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

Несмотря на то, что это веб, типичный веб-разработчик не подходит. Чувствовать боль и знать, как вылечиться — не одно и то же. То инопланетное нагромождение, которое сформировалось в HTML5, это развитие теми, кто чувствовал боль, и, ужаленный, метался. А OS/8 — это проект того, кто жил без боли в серверной разработке, и хочет так же, чего бы это ни стоило. Ожидается, что всё же стоить это будет не так уж много.

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

Компоненты

По плану написать:

  • транслятор Си -> Си
  • трамплин WebAssembly
  • планировщик
  • портировать (не написать новый!) высокоуровневый язык программирования

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

По идее, если взять программу, написанную с POSIX Threads, она должна в получившейся системе заработать. Но поскольку Си для веб-разработки — это достаточно сурово с точки зрения плодить ошибки, предлагается также портировать более высокоуровневый язык программирования, и это Ада. Там сложнее делать ошибки, там POSIX Threads обёрнуты в синтаксические конструкции языка, там можно через RAII управлять ресурсами, и есть generic, есть на них библиотеки контейнеров. Есть транслятор AdaMagic из языка Ada в язык C, он закрытый, но его RTL в исходных кодах, вот нужно, переработав RTL, портировать Аду. AdaMagic, трамплинизатор, EmScripten, всё вместе должно работать в сборе.

У разных мудрецов как-то так интересно получается, что если проверять целостность памяти не надо, один язык программирования (условный C++), если надо, то другой (условная Java). А если потоки зелёные, ой, всё, это же надо опять целый новый язык программирования городить (условный Go). В языке Ада проверки включаются и отключаются флагами транслятора. Не надо два разных языка. Для сертифицируемости есть профили типа Ravenscar, для верификации — подмножество SPARK, а ведь, казалось бы, столько соблазнительных возможностей намудрить ещё пару-тройку новых языков программирования. Симметрии между обычными и зелёными потоками пока не удавалось в полной мере достичь ни на Аде, ни даже на C, но препятствий к этому нет, и надо это на примере показать. В рамках проекта это нужно, наконец, сделать для Си, и, чтоб был пример более высокоуровневого языка, для Ады, потому что кому-то и входной язык CPC может показаться C.

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

Аналоги трамплинизатора

  • Заброшенный Asyncify в EmScripten. Вообще не гарантируется, что нормально работает. Преобразоваие, судя по документации, не 1:1, а с раздуванием, и это оптимально после того, как оттранслировано, но неоптимально с точки зрения загрузки по сети. Хочется 1:1.
  • Continuation Passing C: Почитать 1, почитать 2
  • μC++.

CPC было тяжело запустить. Раздобыл на Windows Ocaml, собрал им ocamllib, вот они работают, а CPC падает хоть в native, хоть в bytecode. Как вообще Ocaml может падать, что за бред? Неприятно. Раздобыл на каком-то сайте Ocaml3 для Win32, он сходу не заработал, его бинарно патчить надо было. Долго прорываясь с боем, всё же удалось заставить CPC работать. Если это не починит спец по Ocaml, то уже из-за одного этого с ним тяжело работать.

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

В CPC преобразуемые функции помечаются, то есть, по принципу белого списка преобразование. Надо, чтоб, наоборот, преобразовывалось всё. По вышеуказанным причинам CPC был неспособен преобразовывать «всё», надо что-то более мощное, чем CPC.

CPC разбивает функции на несколько функций (слишком буквальное понимание продолжений). А надо, чтоб оставалась одна функция вида while switch.

CPC работает поверх libev (или libevent?), и его не прерывают, а в WebAssembly бывают trap, которые надо уметь переживать. Это надо держать в уме изначально. Все переменные, которые может увидеть обработчик исключений, не могут быть локальными с точки зрения WebAssembly. Они должны быть на искусственном стеке. Обработчик — это в том числе деструктор, а их ожидается много. Для простоты можно вообще всё в памяти размещать. Это радикально отличается от того, как работает CPC.

CPC не поддерживает ни setjmp()/longjmp(), ни исключения.

Можно ли привести CPC к желаемому виду, большой вопрос. Представляется, что проще переписать.

μC++ штука доволно древняя (1991), и синтаксис там другой. Если в CPC трансформируемые функции от обычных отличаются наличием ключевого слова, то в μC++ это синтаксически вообще не функции, а классы. И там, в классах, специальный метод режется на части. Поскольку в оригинальном синтаксисе это класс, то к нему можно возвращаться через разные входы, что соответствует в коде механизму, похожему на accept в адских рандеву. И есть Cormonitor, корутина, защищённая монитором, чтоб войти можно было не более, чем из одной задачи. Для полноты упомянуть можно, но в проекте требуется инструмент, устроенный иначе.

Рандеву

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

Рандеву можно вызывать между обычными потоками, а между обычным потоком и зелёным — мог бы быть частный случай. Это отличается от выраженно асимметричной семантики вычисления чего-либо в зелёнопоточном коде с блокированием обычного потока. С точки зрения модели, данной в PDF (в самом низу), в разделе «Задача о дуальных мониторах», более стройной является абстракция, когда есть процесора как будто бы разных типов (один Intel, другой ARM), они не могут непосредственно вызывать код друг от друга, но у них общая память, они могут стартовать задачи друг на друге, они могут пользоваться одними и теми же примитивами синхронизации, и поверх этих примитивов может быть реализовано рандеву, и это то, что на самом деле бы хотелось, потому что сложно устроеные зелёные потоки могут сложно взаимодействовать друг с другом и с обычными потоками, с разными примитивами синхронизации. В такой модели об этом сравнительно просто рассуждать, там все способы синхронизации обычные, проверенные временем.

Понимая, что процессора, на самом деле, не разные, а просто в одном случае это обычные потоки, а в другом случае зелёные, можно срезать путь. Действительно, обычный поток может временно превратиться в дополнительный процессор для зелёных потоков, но тогда, наверное, ему бы следовало быть каким-то специализированным, выполнять то, что нужно для того, чтобы разблокироваться, и не выполнять лишнего, но как понять в общем случае, что нужно, а что нет? В тех системах, где такие срезы пути реализованы, зелёный поток предполагается однопоточным. Либо предполагается, что зелёный поток запускает другие потоки, связанные только с ним, и делает wait на них, то есть, все они должны завершиться. А что, если из зелёного потока нужно взаимодействовать с ранее созданными объектами, защищёнными мониторами. Например, есть онлайн API, которые лучше работают в пакетном режиме, и нужно как-то собрать какое-то количество запросов в пакет, отправить пакет, получить ответы, раздать всем ответы. Это можно сделать на зелёных потоках, но тогда запускаемый из обычного потока зелёный поток не изолирован от других потоков, обычных и зелёных, и его результат зависит от них. По механизму, аналогичному борьбе с инверсией приоритетов, можно было бы по блокировке мьютексов отслеживать, какие зелёные потоки важны для завершения задачи, ради которой обычный поток превратился в дополнительный процессор для зелёных потоков, но подход этот ограничен, вот с семафорами, например, не очень понятно.

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

Оба среза пути следует воспринимать как оптимизации базовой модели. А базовая модель — это, ещё раз, два типа процессоров, общая память. Оптимизации привносят усложения. Например, если использовать сразу оба типа среза, то обычный поток может превратиться в дополнительный процессор, и на этом дополнительном процессоре может быть запущена функция для обычного потока, и пока она работает, станет возможно разблокировать обычный поток, но поскольку линейный стек забит, возвратить управление не получится. Это пример того, как оптимизации, срезающие путь, привносят усложнения, которые кому-то придётся разрулить.

Поэтому, в отличие от других систем (привет котлиновскому runBlocking и многим другим), не всему, что просится быть реализованым, нужно давать зелёный свет, и предлагается к подобным срезам пути относиться болезненно. Предлагается к асимметрии относиться болезненно. Веб-обозреватель, к сожалению, не вполне даст это сделать, срезы придётся иметь, но мотивировать разработчиков ими пользоваться не надо.

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

Также в тему: Возражения против принятия Coroutines с await в C++17. Там вводятся подходы await и fibers. Модель в этом проекте не await и не fibers. Больше похоже на fibers, но fibers мёртвые, им нужно передавать управление (в терминах WinAPI они себя действительно так ведут), чтоб они жили, в то время, как в проекте должны быть threads (нити, потоки), живые сами по себе. Исследовать другие возможности есть, кому, но, предположительно, живыми потоками управлять проще, и поэтому в обычных потоках они и используются в основном, а не fibers, хотя такой инструмент тоже есть. Это только в зелёных потоках вместо привычных инструментов всякие мудрецы постоянно норовят дать разработчикам что-нибудь этакое, не такое, как в обычных потоках. То каналы с сообщениями, то обещания, то акторов.

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

Идеальный кандидат

Идеальный кандидат на участие в практике знает хотя бы какой-нибудь ассемблер, знает Си, знает POSIX Threads. В Java и .NET примитивы синхронизации те же, что в POSIX Threads, так что тоже сойдёт. Чтоб писать на Аде, надо ещё RAII и умные указатели понимать, остальному более-менее можно переобучить.

Конечно, могут быть и на базе OS/8 свои проекты (другие языки программирования?), там на своё усмотрение.

Реальная проблема

Нет научного руководителя

Название

Внезапно, не только IBM называет свои OS циферками. Надо разрешить конфликт. Следующее после 8 число Фибоначчи 13 вроде бы не занято. Ещё идеи названия?

Чтиво

Это то, что на данный момент написано по теме

Файл:OS8.pdf