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

Приветствую. Сегодня поговорим обо всём понемногу. Введём в нашу наработку 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 в расшифровке аббревиатуры.

В этом топике вы найдете немного ностальгии, каплю гнева и килограмм реверс-инжиниринга. Посвящается тем, кто знаком с программой «Звукозапись» не понаслышке :)

Когда небо было голубее, Солнце светило ярче, а Интернет был таким недоступным… Короче, в далеком детстве мне почему-то полюбилась стандартная программа «Звукозапись» из Windows 98. Не глядя на минимальную функциональность, я даже умудрялся делать в ней простейшие «ремиксы» ей же записанных мелодий из игр.

Шли годы. Железо становилось мощнее, а ОС функциональнее. Но «Звукозапись» не менялась. Даже в Windows XP она оставалась такой же, как и тогда. Пришло время обновить железо. 3 гигабайта оперативной памяти — раньше и мечтать о таком не приходилось. Этого уж точно должно хватить всем! Так и было, пока дело не дошло до той самой «Звукозаписи». После попытки записать небольшой звук программа невозмутимо возразила, что ей недостаточно оперативной памяти.