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

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

Прочитал статью «Основы MPI для «чайников»» и понял, что статья новичка способна отпугнуть.

Теория

Начнем с начала

Первое время не было единого стандарта (API) для параллельных вычислений и программистам приходилось писать для каждого кластера архитектурно-специфический код. Но, как известно, программисты люди рациональные и быстро было решено организовать стандарты (самые известные — MPI, OpenMP).

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

Основные принципы и пример

В качестве примера будет использоваться расчет экспоненты (e). Один из вариантов ее нахождения — ряд Тейлора:
e^x=∑((x^n)/n!), где суммирование происходит от n=0 до бесконечности.

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

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

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

Вашему вниманию предлагается описание системных вызовов микроядерной операционной системы Хамелеон 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'а.
Первой проблемой с которой столкнется желающий программировать на низком уровне — как же загрузить свой код?