Системное программирование *

Здоровья всем читателям!

Вашему вниманию предлагается описание системных вызовов микроядерной операционной системы Хамелеон aka Xameleon. Мой хамелеончик ещё не вылупился из своего яйца и пока набирается сил в виртуальной машине. Но ему очень одиноко и маленькая ящерица желает поближе познакомиться с жителями Хабра.

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

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

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

Речь пойдёт о точках повторной обработки (reparse points), идентификаторах объектов (object id) и о других типах данных, которые может содержать файл помимо своего основного содержимого.

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

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

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

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

Для того, чтобы писать операционку, нужно разбираться во многих деталях. Вот давайте я вас немного просвещу, (но давайте договоримся, что маны вы будете читать сами, чтобы было о чём побеседовать).
Честно говоря, на просторах сети есть туча тучная материалов по PM, да и ileyи pehat несколько рассказали об этом режиме, но меня попросили всё равно описать в общих рамках его. Сейчас кратко выдам теорию (вообще то специально для этого Intel маны писала), потом начнём писать код.

Следуя совету хабрапублики, пробую новый вариант перевода термина "lock-free"

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

В общей переменной теперь нужны два служебных бита: вдобавок к флагу захвата, как в прошлом примере, — флаг «поручена новая работа»; а если порученная работа сложная, то кроме флага, нужно будет где-то хранить ещё и её параметры. Например, в общей переменной можно хранить указатель на (выравненный в памяти) объект с параметрами, а в свободных младших битах указателя — два названных флага.

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

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

На написание этого поста меня подтолкнуло то, что посты iley прекратились, а хабралюди всё же хотели посты по осьдеву. Оговорюсь сразу, я сам изучаю и пишу небольшую ось, но изучаю, так что продвигаться будем вместе. Я собираюсь рассмотреть написание систем под защищённый режим для IA-32, рассказать о:
1) Проектировании;
2) Отладке;
3) Работе с графикой;
4) Работе с дисками;
5) Memory management;
6) Task management;
Возможно о чём-нибудь ещё, если это будет востребовано.

(Тот факт, что русского перевода понятию «lock-free» в литературе ещё не устоялось, — нисколько меня не убеждает, что такого перевода не должно быть.)

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

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;

 // если значение параметра не изменилось с прошлого раза,
 // воспользуемся готовым результатом
 if (n == nLast) return fLastIsPrime;

 // вычислим и запомним новый результат
 nLast = n;
 fLastIsPrime = slow_IsPrime(n);
 return fLastIsPrime;
}

Само собой, этот код потоконебезопасен: если один поток находится внутри вызова slow_IsPrime(), то другой поток, вызвавший IsPrime(), застанет значения переменных nLast и fLastIsPrime несоответствующими одно другому.

Простое решение — заключить код в критическую секцию; но простота идёт в ущерб производительности: если, скажем, nLast = 5, fLastIsPrime = TRUE, и два потока одновременно вызывают IsPrime(5), то совершенно ни к чему им выстраиваться в очередь: ничего не мешает им одновременно воспользоваться кэшированным значением.

Посмотрим, как можно реализовать наш кэш беззамочно.

Реализованное нами в прошлый раз атомарное умножение является примером более общей модели, которую Реймонд назвал «сделай, запиши,(попытайся снова)».

for (;;) {
 // берём начальное значение общей переменной,
 // которую мы собираемся изменять
 oldValue = sharedVariable;

 ... берём начальные значения других параметров ...

 newValue = ... вычисляем новое значение, используя
                oldValue и копии остальных параметров ...

 // вместо Xxx может быть Acquire, Release, или ничего
 if (InterlockedCompareExchangeXxx(
            &sharedVariable,
            newValue, oldValue) == oldValue) {
  break; // запись удалась
 }

 ... удаляем newValue ...

} // попытаемся снова

Мы вычисляем новое значение, и затем вызовом InterlockedCompareExchange записываем его в общую переменную только в том случае, если её значение не изменялось. Если оно изменилось, значит другой поток нас опередил; в этом случае попытаемся выполнить операцию по-новой, с самого начала, — в надежде, что в следующий раз никто нас не «подрежет».

Реймонд Чен написал занятную серию блогпостов о беззамочной синхронизации. Мне бы хотелось опубликовать эти заметки и для хаброчитателей. Данный пост — введение в серию, скомпилированное из трёх старых постов Чена.

1. Ленивая инициализация встроенными средствами C++
2. Беззамочная синхронизация
3. Беззамочная потоко-безопасная ленивая инициализация

Ленивая инициализация встроенными средствами C++

Инициализация статических локальных переменных в C++ непотокобезопасна, причём намеренно!

Спецификацией установлено, что статические локальные переменные (в отличие от глобальных) инициализируются при первом выполнении блока кода, в котором они объявлены.

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

int ComputeSomething()
{
  static int cachedResult = ComputeSomethingSlowly();
  return cachedResult;
}

(Примерно такой код советуют в популярном C++ FAQ, чтобы не зависеть от выбранного компилятором порядка инициализации глобальных статических переменных.)

Возникла задача: у нас есть компилятор собственного языка программирования, которым мы компилируем некоторый диалект бейсика в исходник на C.

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

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

Несложная задача. Только есть одно «но». Количество исходников, которые планируется использовать как эталонные — около 15 тысяч файлов, суммарным объемом чуть меньше гига (для удобства они завернуты в один TAR). Подобный «прогон» может быть весьма долгим. И есть естественное желание сделать тест максимально быстрым, используя многопроцессорную машину, ибо задача прекрасно распараллеливается.

Как вариант — можно сделать Makefile и запускать его с ключом "-j" в GNU Make. Но если написать специализированную многопоточную программу, то можно достичь лучшей производительности.

Здравствуйте, читатели Хабрахабр!

Это завершение поста начатого вот здесь.

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

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

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

Лёгкость написания серверов для xinetd привлекательна, это действительно просто: пишем на любом языке простой скрипт, который работает с stdin и stdout (в простейшем случае это обычный REPL) и получаем одновременно консольную утилиту и сетевой сервер в одном флаконе.
После одной минуты на правку конфига xinetd получаем работающий сервер, к которому можно подключаться telnet-ом или netcat-ом и видеть результат на консоли.

Вооруженные жидким азотом оверклокеры неоднократно показывали, что современные чипы могут стабильно работать на частотах в разы выше номинальных, обеспечивая соответствующий рост производительности. Тем не менее, прогресс в области «гонки гигагерц» остановился давно и надежно. Первый «Pentium 4» с частотой больше 3 ГГц появился в далеком 2002 году, почти 10 лет назад. За прошедшие годы нормы техпроцессов уменьшились со 180 до 32 нм, но даже это не позволило существенно поднять штатные рабочие частоты. Все упирается в огромное тепловыделение элементов цифровой логики.

В основе «проблемы тепловыделения» лежит глубокая связь между информационной и термодинамической энтропией, а также второе начало термодинамики, запрещающее уменьшение общей энтропии замкнутой системы. Любое вычисление, уменьшающее энтропию информационную, обязано приводить к увеличению энтропии термодинамической, то есть к выделению тепла. Рольф Ландауэр в 1961 году показал [pdf], что уничтожение одного бита информации должно приводить к выделению не менее k∙T∙ln 2 джоулей энергии, где k – постоянная Больцмана и T – температура системы. Само по себе эта энергия невелика: для T=300K она составляет всего 0.017 эВ на бит, но в пересчете на процессор в целом суммарная энергия вырастает уже до величин порядка одного Джоуля за каждую секунду работы, то есть порядка одного Ватта [Компьютерра №538]. На практике этот теоретический минимум умножается на ненулевое сопротивление и прочие неидеальности реальных полупроводников. В результате мы получаем процессоры, которые по тепловыделению обгоняют утюги.

Не так давно решил чуть получше изучить архитектуру IA-32. А что лучше всего для запоминания? Конечно же практика. Но программируя в ОС мы врядли получим самый низкий уровень доступ к железу без помех. Поэтому для этих целей будем писать собственное подобие операционной системы. То есть проще говоря будем выполнять свой код, сразу после загрузки BIOS'а.
Первой проблемой с которой столкнется желающий программировать на низком уровне — как же загрузить свой код?

Любой программист хоть раз заглядывавший в отладчик знаком с понятием точки останова (aka бряк, breakpoint). Казалось бы нет ничего проще, чем поставить точку останова пара кликов мышкой в графическом интерфейсе или команда в консоли отладчика, но не всегда жизнь системного программиста столь проста и иногда возникает необходимость выставлять точки останова автоматически — изнутри самой программы.

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

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

Тот самый репортаж про BolgenOS и её автора Дениса Попова (quadregus).

Случилось так, что пришлось мне писать с нуля драйвер для usb дисплея под windows. Имея возможность — расскажу о деталях столь занимательного процесса.

USB – это simple

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