Нужна ли математика программистам? Этот вопрос любят жарко обсуждать на Reddit, Хабре и других площадках.

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

Лучшая, на наш взгляд, книга для ликбеза — совместное творение Эрика Лемана, Фрэнка Томсона Лейтона и Альберта Мейера (Eric Lehman, F. Thomson Leighton, Albert M. Meyer) под названием «Mathematics for Computer Science».

Не читали? Качайте по этой или альтернативной ссылкам.

Читали? И как вам?

Знаете что-то лучше? Напишите в комментариях.

#literature

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

#digest

Essense OS

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

Графический интерфейс Essense был явно вдохновлен старым интерфейсом Google Chrome и оконным менеджером Rio из операционной системы Plan 9. Программы в этой системе не запускаются в собственных отдельных окнах, а наследуют то окно, из которого они были запущены. Для отображения интерфейса программы в окне появляется отдельная вкладка. Вкладки приложений могут перемещаться между открытыми окнами.

В Essense уже есть несколько графических приложений: файловый менеджер, текстовый редактор, клиент IRC, эмулятор терминала. Есть и портированные компоненты, например GCC, позволяющий собирать Essense из самой себя.

Ядро системы тоже не отстает: реализован стек TCP/IP, блочный кеш, разделяемая память, планировщик, учитывающий инверсию приоритетов, аудио-микшер и подсистема совместимости с POSIX.

#digest

ToaruOS

Этот проект широко известен среди разработчиков ОС. ToaruOS разрабатывается одним человеком и в базовой сборке не содержит никаких внешних зависимостей. Все в системе было написано автором с нуля!

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

Автор (Klange) разработал множество родных для этой ОС приложений. Есть и менеджер пакетов, позволяющий доустанавливать портированные из Unix приложения по сети.

На базе ToaruOS первого апреля каждого года выпускается юмористическая сборка — PonyOS. Случайные посетители этого сайта оказываются ошарашенными: они не могут поверить, что кто-то потратил столько сил и времени, чтобы создать продвинутую ОС, построенную вокруг вселенной My Little Pony.

#digest

SerenityOS

Этот проект также хорошо известен сообществу.

Задумывая SerenityOS, Андреас Клинг вдохновлялся Unix системами и графическими интерфейсами начала 2000-х.

Некоторое время назад Андреас уволился с работы, чтобы посвятить себя разработке Serenity и система стала прогрессировать с невероятной скоростью.

Кроме довольно функционального ядра и оконного менеджера, автор вместе с сообществом разработал множество приложений с нуля, включая движок JavaScript, браузер, средства разработки, отладки и профилирования приложений!

Андреас ведет канал на YouTube, где периодически выкладывает отчеты о разработке системы или программирует в прямом эфире.

#digest

Visopsys

Достаточно старый проект, стартовавший в далеком 97 году.

Visopsys поддерживает графическое окружение благодаря графическому серверу, похожему на XOrg, интегрированному непосредственно в ядро. Ядро поддерживает 32-битные x86 системы, многозадачность, предоставляет средства работы с сетью и накопителями.

Автор Visopsys (Энди Маклаглин) реализовал множество приложений для своей системы: менеджер архивов, файловый менеджер, редактор шрифтов и изображений, сниффер сетевых пакетов, telnet-клиент, текстовый редактор, калькулятор и даже пакетный менеджер.

#digest

Особенности архитектуры процессоров ARM

Процессоры ARM работают с двумя типами памяти: normal memory и device memory. Задать тип памяти можно при помощи регистра MAIR (Memory Attribute Indirection Register) и группы из трех бит в записи таблицы страниц.

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

Во всем этом нет ничего удивительного, пока мы не сталкиваемся с конвейером процессора и спекулятивным исполнением. Процессор может пытаться спекулятивно исполнять код, выбирая его из памяти, любой памяти, которая не маркирована атрибутом XN (Execute Never). В том числе из device memory!

В документации ARM утверждают, что выборка инструкций из device memory приводит к непредсказуемому результату.

Описанное выше — не просто теория, приходилось сталкиваться с подобным поведением на практике: из-за забытого XN-бита в записях таблиц страниц контроллер прерываний иногда работал некорректно, переходя в непредсказуемые состояния. Виновником оказалась спекулятивная выборка из device memory.

При портировании достаточно старой версии библиотеки glib коллеги обнаружили, что autoconf генерирует невалидный код, который отвергается современным gcc.

Это ошибка компилятора или скрипта, генерирующего программу? Обратимся к стандарту👇

✔An integer constant expression96) shall have integer type and shall only have operands that are integer constants, enumeration constants, character constants, sizeof expressions whose results are integer constants, and floating constants that are the immediate operands of casts. Cast operators in an integer constant expression shall only convert arithmetic types to integer types, except as part of an operand to the sizeof operator.

✔An integer constant expression is used to specify the size of a bit-field member of a structure, the value of an enumeration constant, the size of an array, or the value of a case constant. Further constraints that apply to the integer constant expressions used in conditional-inclusion preprocessing directives are discussed in 6.10.1.

✔If the size is not present, the array type is an incomplete type. If the size is * instead of being an expression, the array type is a variable length array type of unspecified size, which can only be used in declarations with function prototype scope;122) such arrays are nonetheless complete types. If the size is an integer constant expression and the element type has a known constant size, the array type is not a variable length array type; otherwise, the array type is a variable length array type.

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

А вот и баг-репорт.

Компилятор был прав!😈

Хороший пример проектной документации, неожиданно переросшей во что-то большее — сайт проекта Qibec.

Qibec — это процессор, собранный из отдельных транзисторов. Он устроен очень просто и может выполнять всего одну инструкцию. Такие процессоры называют OISC (One Instruction Set Computer) или URISC (Ultimate Reduced Instruction Set Computer). Несмотря на простоту, Qibec может выполнять произвольные программы.

Чтобы объяснить, как функционирует процессор, авторы проекта документировали не только его внутреннее устройство, но постарались написать введение в булеву логику и основы работы логических схем. Например, они использовали аналогию с гидравлическими системами, чтобы объяснить, что такое разность потенциалов и сопротивление. Логические вентили также объяснены на примере гидравлики!

На сайте описаны все аспекты работы Qibec, выложены файлы прошивки, схемы и утилиты для отладки и программирования.

Посмотрите, как здорово выглядит Qibec в действии!

Мало кто, когда речь заходит о литературе про разработку компиляторов, вспоминает книгу «Compiler Design in C» Аллена Голуба (Allen Holub). А зря. У нее практический уклон и выбор языка программирования.

Здорово, что автор, рассказывая о подходах к лексическому и синтаксическому анализу, показывает как можно реализовать на C генераторы таких анализаторов. Да, в книге есть реализация аналога YACC с полным объяснением внутренностей.

Интересен и выбор языка, который генерирует компилятор в качестве выхлопа. Хотя лучше обойтись без спойлеров!

#literature

Помните ли вы игрушки из своего детства?

Пожалуй, одну точно помнят многие. Восьмибитную игровую приставку, пиратский клон Nintendo Entertainment System (NES), которая продавалась в России под брендом Dendy. О-о-о, сколько времени было проведено за теми незабываемыми играми!

Как работало то, что приносило нам столько радости в детстве? Как создавались игры для NES, каковы были ограничения платформы по ресурсам? Программисты, увлекающиеся ретро-платформами, пытаются разобраться в этом.

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

К счастью, сегодня появилось больше информации о внутренностях NES и играх для нее. Например, вот хорошая иллюстрированная книга (все еще незаконченная), которая раскрывает особенности архитектуры приставки и показывает, как создавать для нее простые игры на языке ассемблера.

#literature

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

Вот, откуда он вырос.

При недавнем осмотре кода ядра возник на первый взгляд несерьёзный вопрос: стоит ли проверять наличие инструкции cpuid прежде, чем начинать ею пользоваться?

С одной стороны, она присутствует в наборе инструкций, начиная с процессора Intel386, который вышел в 1985 году. И нам пока что не известен ни один случай, когда cpuid не была бы поддержана на процессоре архитектуры x86. Но ключевое слово здесь — «пока», потому что с другой стороны Intel Software Developers Manual в описании cpuid первым делом описывает способ проверки наличия данной инструкции. Сама проверка довольно простая — нужно проверить, что мы можем записать флаг ID в регистре xFLAGS.

И описание там неспроста...👇

Intel SDM описывает именно архитектуру x86, реализуемую Intel. То есть там описаны концептуальные вещи, свод правил, как должен работать ЦПУ. Если, допустим, по документации должно быть одно поведение, а на самом деле силикон ведет себя иначе — то это ситуация описывается в errata, а не исправляется мануал.

Из мануала следует тот факт, что архитектурно никто не обещает поддержку этой инструкции ни в одном из продуктов Intel на x86. Условный новый Intel Quark может кидать исключение #UD (undefined opcode) при попытке исполнения cpuid, что недопустимо, например, в том же загрузчике.

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

А теперь скажите еще раз: насколько, на ваш взгляд, далеко следует заходить в поддержке legacy? 😆

Наткнулись на познавательную статью 2002 года, оценивающую актуальность security evaluation, который учинили в 1974-ом году над ОС Multics.

Вкратце, старые операционки были более секурны даже без модных харденингов. А все из-за более строгих security default-ов и стека, растущего в правильном направлении (а значит, гудбай переполнение буфера на стеке и прощай ROP).

Сам отчет значительно длиннее его пост-анализа, но интересен с точки зрения формата и процедуры security evaluation тех лет.

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

Но так было не всегда: компьютеры изначально были заточены исключительно на английский язык и использовали стандартную кодировку ASCII (American Standard Code for Information Interchange). Если вы хотели использовать какой-либо национальный алфавит, приходилось прибегать к альтернативным кодовым страницам.

Таких 8-битовых кодовых страниц разработали великое множество, в том числе и для кириллических языков.

Для русского языка в мире Unix наиболее распространенной кодировкой была KOI8-R. Аббревиатура KOI означает буквально "Код Обмена Информацией".

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

Просто сравните.

В популярной одно время кодовой странице Windows-1251 коды кириллических строчных букв начинались с 0xE0 и далее располагались по алфавиту: 0xE0 соответствовал 'а', 0xE1 - 'б' и так далее.

В KOI8-R строчные кириллические буквы начинались с 'ю' под кодом 0xC0 и далее шли коды букв 'а', 'б', 'ц', 'д', 'е', 'ф' и других... Зачем такие сложности?

Пытливые читатели уже заметили, что последовательность букв в KOI8-R похожа по звучанию на последовательность букв в английском алфавите: a, b, c, d, e, f... И это не случайность.

Коды прописных латинских букв отличались от соответствующих им кодов строчных кириллических лишь на один бит: 0xC1 — 'а' (кириллическая), 0x41 — 'A' (латинская). В битовом представлении это 11000001 и 01000001.

Чем хороша эта особенность кодирования? На системах, которые умели работать только с семибитовыми кодировками, старший бит кода символа отбрасывался, поэтому русский текст в большинстве кодировок не мог быть отображен. Но выручала особенность кодирования кириллицы в KOI8-R: текст на таких системах отображался в фонетической транскрипции, только регистр букв инвертировался. "Привет, мир!" превращалось в "pRIVET, MIR!"

Кстати, особенности отображения текстов KOI8-R при просмотре в режиме других популярных кодовых страниц очень узнаваемы. А впечатлительные люди даже находят в этом мусоре из псевдографики тайный смысл!

#retro

Анатолий Шалыто — доктор технических наук, профессор ИТМО. Несмотря на возраст (родился в 1948 году), он ведет активную академическую жизнь. Во многом это объясняется его способностью к самомотивации.

Шалыто регулярно пишет короткие заметки, сподвигающие на большие свершения. Их он собирает в книгу «Заметки о мотивации». В ней уже 1111 страниц — хватит надолго.

#literature

Этот известный комикс XKCD повествует о методе генерации паролей, который называется pass phrases.

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

Короткие случайные пароли еще нужно запоминать, что непросто, особенно если вы используете разные пароли для разных сервисов. Но запомнить предложение, пусть и бессмысленное на первый взгляд, гораздо проще: просто постройте в голове картину, иллюстрирующую происходящее в этом предложении. Это и показывает комикс. 👇