суббота, марта 20, 2010

LiveMath III

Это продолжение к стародавнему посту: http://iportnov.blogspot.com/2007/09/livemath-livecd.html.

К сожалению, редко оказывается достаточно времени, чтобы собрать свежую версию LiveMath. Однако же вот, собрал. В этот раз LiveMath основан на Ubuntu 9.10 (Karmic) с добавлениями из Ubuntu Lucid и "Ubuntu Scientific Remix". LiveMath III содержит (среди прочего):

Системы компьютерной алгебры:
Maxima (http://maxima.sourceforge.net) - полнофункциональная система аналитических вычислений;
Fricas (http://fricas.sourceforge.net) - мощная система компьютерной алгебры;
YaCas (http://yacas.sourceforge.net) - еще одна система компьютерной алгебры;
PARI/GP (http://pari.math.u-bordeaux.fr/) - широко используемая компьютерно-алгебраическая система, разработанная для быстрых вычислений в теории чисел (факторизации, алгебраическая теория чисел, эллиптические кривые...);
GAP (http://www.gap-system.org/) - свободно распространяемый, открытый и расширяемый программный комплекс для применения в области вычислительной дискретной математики, в частности, теории групп;
Mathomatic (http://www.mathomatic.org/) - переносимая, универсальная программа, которая может решать, упрощать, группировать, дифференцировать, интегрировать и сравнивать алгебраические выражения;

Системы автоматизации доказательств:

ACL2 (http://www.cs.utexas.edu/users/moore/acl2/) - язык программирования для моделирования компьютерных систем и средство, помогающее доказывать свойства этих моделей;
Coq (http://coq.inria.fr/) - система автоматизированного построения доказательств, с помощью которой, кроме всего прочего, была решена проблема четырех красок;
Также Prover9/Mace4 и некоторые другие;

Системы численных вычислений:

SciLab (http://www.scilab.org/) - пакет научных программ для численных вычислений, предоставляющий мощное открытое окружение для инженерных и научных расчетов;
GNU Octave (http://www.octave.org/) - язык высокого уровня, предназначенный для выполнения математических вычислений;
FreeMat (http://freemat.sourceforge.net/) - свободная среда для быстрой разработки, научного прототипирования и обработки данных, имеет интерфейс и синтаксис языка, подобные MatLab;
Yorick (http://yorick.sourceforge.net/) - компактная программная среда, предназначенная для комплексного решения научно-инженерных вычислительных задач;

Образовательные программы:
Kig (http://edu.kde.org/kig/), Carmetal, DrGeo, GeoGebra - интерактивная геометрия;
KAlgebra;
Инструменты построения графиков - kmplot, gnuplot;

Обработка и визуализация данных:
Mayavi2 (http://code.enthought.com/projects/mayavi/#Mayavi2) - открытый пакет научной 2D и 3D визуализации данных;
OpenDX (http://www.opendx.org/) - программное средство для анализа данных в графическом виде, визуализации научных данных;
GGobi (http://www.ggobi.org/) - среда визуализации многомерных данных;
LabPlot (http://labplot.sourceforge.net/) - программа для анализа и визуализации различных данных;
QtiPlot - позиционируется как замена для Microcal Origin - программа для несложной статистической обработки данных, построения всяческих графиков;
Grace6 (http://plasma-gate.weizmann.ac.il/Grace/) - программа для подготовки двумерных графиков по численным данным;
PAW (http://cern.ch/paw/) - интерактивная программа анализа и графического представления результатов. Может применяться для анализа большого и очень большого объёма данных;
ROOT (http://cern.ch/root/) - наследник PAW, интерактивная система обработки и визуализации очень больших объёмов научных данных;
GNU R (http://r-project.org/) - мощный язык статистических вычислений, используемый профессиональными статистиками;
GRETL (http://gretl.sourceforge.net/) - система эконометрического анализа;

Научные редакторы:
TeXLive - полноценный дистрибутив TeX;
TeXmacs (http://texmacs.org) - текстовый редактор для набора математических и прочих научных текстов, также позволяет включать в документ сессии Axiom, Maxima, Octave, SciLab и других систем компьютерной математики;
Kile (http://kile.sourceforge.net/) - интегрированная среда подготовки документов с помощью TeX;
Texmaker (http://www.xm1math.net/texmaker/) - интегрированная оболочка для LaTeX;

Также LiveMath III содержит среду Gnome 2.28, OpenOffice.org 3.1, Gnumeric. Для "больших" систем (ROOT, PAW, R, Octave) включена значительная часть имеющихся в репозиториях Ubuntu пакетов. Для многих изначально "консольных" систем включены GUI-обёртки, для некоторых по несколько, на выбор. К большинству программ есть документация. Возможна установка системы на жёсткий диск с помощью стандартного установщика Ubuntu.

UPD. Полный список установленных пакетов: http://iportnov.ru/files/LiveMath.packages.txt

К сожалению, у меня нет времени, чтобы тестировать все эти программы. То, что я протестировал - работает. Багрепорты принимаются в комментариях или на e-mail portnov at bk dot ru, но мгновенного исправления не обещаю.

LiveMath сделан с помощью Ubuntu Construction Kit (http://uck.sourceforge.net/), так что каждый, в принципе, может сделать себе нечто подобное. Вероятно, это окажется проще, чем качать моё изделие.

Взять можно здесь: http://portnov.homelinux.net/LiveMath%20III.iso (размер образа - 2Gb), может быть удобнее окажется торрент: http://iportnov.ru/files/LiveMath%20III.iso.torrent (честно говоря, не знаю, заработает ли). У меня сейчас нет хостинга, на котором я бы мог размещать большие ISO-образы. Так что учтите, что portnov.homelinux.net - это мой домашний сервер, обычно бывает включён примерно с 8:00 до 22:00 MSK, суперскоростей не обещаю. Если кому-то позарез нужно скачать в другое время - пишите, так уж и быть, оставлю включённым на ночь :)

суббота, марта 13, 2010

Ядро Linux за 10 минут (обзор)


Это конспект доклада для семинара, проведённого нашей LUG совместно с университетом.


У меня, натурально, было 10 минут, поэтому изложение — галопом по европам, многое упрощено, многое упущено.


Немного истории

Относительно подробную историю создания ядра Linux можно найти в известной книге Линуса Торвальдса «Just for fun». Нас из неё интересуют следующие факты:

  • Ядро создал в 1991 году студент университета Хельсинки Линус Торвальдс;

  • В качестве платформы он использовал ОС Minix, написанную его преподавателем Эндрю Таненбаумом, запущенную на персональном компьютере с процессором Intel 80386;

  • В качестве примера для подражания он использовал ОС семейства Unix, а в качестве путеводителя — сначала стандарт POSIX, а затем просто исходные коды программ из комплекта GNU (bash, gcc и пр).

Эти факты в значительной мере определили пути развития ядра в дальнейшем, их следствия заметны и в современном ядре.

В частности, известно, что Unix-системы в своё время разделились на два лагеря: потомки UNIX System V Release 4 (семейство SVR4) против потомков Berkley Software Distribution v4.2 (BSD4.2). Linux по большей части принадлежит к первому семейству, но заимствует некоторые существенные идеи из второго.

Ядро в цифрах

  • Около 30 тыс. файлов
  • Около 8 млн. строк кода (не считая комментариев)
  • Репозиторий занимает около 1 Гб
  • linux-2.6.33.tar.bz2: 63 Mb
  • patch-2.6.33.bz2: 10Mb, около 1.7 млн изменённых строк
  • Около 6000 человек, чей код есть в ядре

Об архитектуре ядра

Все (или почти все) процессоры, которыми когда-либо интересовались производители Unix-подобных ОС, имеют аппаратную поддержку разделения привелегий. Один код может всё (в т.ч. общаться напрямую с оборудованием), другой — почти ничего. Традиционно говорят о «режиме ядра» (kernel land) и «режиме пользователя» (user land). Различные архитектуры ядер ОС различаются прежде всего подходом к ответу на вопрос: какие части кода ОС должны выполняться в kernel land, а какие — в user land? Дело в том, что у подавляющего большинства процессоров переключение между двумя режимами занимает существенное время. Выделяют следующие подходы:

  • Традиционный: монолитное ядро. Весь код ядра компилируется в один большой бинарный файл. Всё ядро исполняется в режиме ядра;

  • Противоположный, новаторский: микроядро. В режиме ядра выполняются только самые необходимые части, всё остальное — в режиме пользователя;

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

  • И, конечно, всевозможные варианты гибридных архитектур.

Ядро Linux начиналось как монолитное (глядя на существовавшие тогда Unix-ы). Современное Linux-ядро модульное. По сравнению с микроядром монолитное (или модульное) ядро обеспечивает существенно бо́льшую производительность, но предъявляет существенно более жёсткие требования к качеству кода различных компонентов. Так, в системе с микроядром «рухнувший» драйвер ФС будет перезапущен без ущерба для работы системы; рухнувший драйвер ФС в монолитном ядре — это Kernel panic и останов системы.

Подсистемы ядра Linux

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

: linux-kernel-big.png

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

: linux-kernel-simple.png

Системные вызовы

Уровень системных вызовов — это наиболее близкая к прикладному программисту часть ядра Linux. Системные вызовы предоставляют интерфейс, используемый прикладными программами — это API ядра. Большинство системных вызовов Linux взяты из стандарта POSIX, однако есть и специфичные для Linux системные вызовы.

Здесь стоит отметить некоторую разницу в подходе к проектированию API ядра в Unix-системах с одной стороны и в Windows[NT] и других идеологических потомках VMS с другой. Дизайнеры Unix предпочитают предоставить десять системных вызовов с одним параметром вместо одного системного вызова с двадцатью параметрами. Классический пример — создание процесса. В Windows функция для создания процесса — CreateProcess() — принимает 10 аргументов, из которых 5 — структуры. В противоположность этому, Unix-системы предоставляют два системных вызова (fork() и exec()), первый — вообще без параметров, второй — с тремя параметрами.

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

Управление памятью

Ядро Linux использует в качестве минимальной единицы памяти страницу. Размер страницы может зависеть от оборудования; на x86 это 4Кб. Для хранения информации о странице физической памяти (её физический адрес, принадлежность, режим использования и пр) используется специальная структура page размером в 40 байт.

Ядро использует возможности современных процессоров для организации виртуальной памяти. Благодаря манипуляциям с каталогами страниц виртуальной памяти, каждый процесс получает адресное пространство размером в 4Гб (на 32х-разрядных архитектурах). Часть этого пространства доступна процессу только на чтение или исполнение: туда отображаются интерфейсы ядра.

Существенно, что процесс, работающий в пространстве пользователя, в большинстве случаев «не знает», где находятся его данные: в ОЗУ или в файле подкачки. Процесс может попросить у системы выделить ему память именно в ОЗУ, но система не обязана удовлетворять такую просьбу.

Управление процессами

Ядро Linux было многозадачным буквально с первого дня. К настоящему моменту оно имеет довольно хорошую поддержку вытесняющей многозадачности.

В истории было известно два типа многозадачности:

Корпоративная многозадачность.

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

Вытесняющая многозадачность.

Ядро ОС выделяет каждому процессу определённый квант процессорного времени и «насильно» передаёт управление другому процессу по истечении этого кванта. Это создаёт накладные расходы на переключение режимов процессора и расчёт приоритетов, но повышает надёжность и производительность.

Переключение процессов в linux может производиться по наступлению двух событий: аппаратного прерывания или прерывания от таймера. Частота прерываний таймера устанавливается при компиляции ядра в диапазоне от 100Гц до 1000Гц. Аппаратные прерывания возникают чуть ли не чаще: достаточно двинуть мышку или нажать кнопку на клавиатуре, да и внутренние устройства компьютера генерируют прерывания. Начиная с версии 2.6.23, появилась возможность собрать ядро, не использующее переключение процессов по таймеру. Это позволяет снизить энергопотребление в режиме простоя компьютера.

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

Кроме многозадачности в режиме пользователя, ядро Linux использует многозадачность в режиме ядра: само ядро многопоточно.

Традиционные ядра Unix-систем имели следующую… ну если не проблему, то особенность: само ядро не было вытесняемым. Пример: процесс /usr/bin/cat хочет открыть файл /media/cdrom/file.txt и использует для этого системный вызов open(). Управление передаётся ядру. Ядро обнаруживает, что файл расположен на CD-диске и начинает инициализацию привода (раскручивание диска и пр). Это занимает существенное время. Всё это время управление не передаётся пользовательским процессам, т.к. планировщик не активен в то время, когда выполняется код ядра. Все пользовательские процессы ждут завершения этого вызова open().

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

Сетевая подсистема

Сетевая подсистема ядра ОС, теоретически, почти вся может выполняться в пространстве пользователя: для таких операций, как формирование пакетов TCP/IP, никакие привелегии не нужны. Однако в современных ОС, тем более применяемых на высоконагруженных серверах, от всего сетевого стека — всей цепочки от формирования пакетов до работы непосредственно с сетевым адаптером — требуется максимальная производительность. Сетевой подсистеме, работающей в пространстве пользователя, пришлось бы постоянно обращаться к ядру для общения с сетевым оборудованием, а это повлекло бы весьма существенные накладные расходы.

Сетевая подсистема Linux обеспечивает следующую функциональность:

  • Абстракцию сокетов;

  • Стеки сетевых протоколов (TCP/IP, UDP/IP, IPX/SPX, AppleTalk и мн. др);

  • Маршрутизацию (routing);

  • Пакетный фильтр (модуль Netfilter);

  • Абстракцию сетевых интерфейсов.

В различных Unix-системах использовалось два различных прикладных интерфейса, обеспечивающих доступ к функциональности сетевой подсистемы: Transport Layer Interface (TLI) из SVR4 и sockets (сокеты) из BSD. Интерфейс TLI, с одной стороны, тесно завязан на подсистему STREAMS, отсутствующую в ядре Linux, а с другой — не совместим с интерфейсом сокетов. Поэтому в Linux используется интерфейс сокетов, взятый из семейства BSD.

Файловая система

Виртуальная файловая система (VFS)

С точки зрения приложений, в Unix-подобных ОС существует только одна файловая система. Она представляет собой дерево директорий, растущее из «корня». Приложениям, в большинстве случаев, не интересно, на каком носителе находятся данные файлов; они могут находиться на жёстком диске, оптическом диске, флеш-носителе или вообще на другом компьютере и другом континенте. Эта абстракция и реализующая её подсистема называется виртуальной файловой системой (VFS).

Стоит заметить, что VFS в ядре Linux реализована с учётом идей из ООП. Например, ядро рассматривает набор структур inode, каждая из которых содержит (среди прочего):

  • Данные из on-disk inode (права доступа, размер файла и др);

  • Указатель на структуру, описывающую драйвер ФС, к которой принадлежит данный inode;

  • Указатель на струкруру операций с inode, которая, в свою очередь, содержит указатели на функции для создания inode, изменения его атрибутов и т.д., реализованные в конкретном драйвере ФС.

Аналогично устроены структуры ядра, описывающие другие сущности ФС — суперблок, элемент каталога, файл.

Драйверы ФС

Драйверы ФС, как можно заметить из диаграммы, относятся к гораздо более высокому уровню, чем драйверы устройств. Это связано с тем, что драйверы ФС не общаются ни с какими устройствами. Драйвер файловой системы лишь реализует функции, предоставляемые им через интерфейс VFS. При этом данные пишутся и читаются в/из страницы памяти; какие из них и когда будут записаны на носитель — решает более низкий уровень. Тот факт, что драйверы ФС в Linux не общаются с оборудованием, позволил реализовать специальный драйвер FUSE, который делегирует функциональность драйвера ФС в модули, исполняемые в пространстве пользователя.

Страничный кэш

Эта подсистема ядра оперирует страницами виртуальной памяти, организованными в виде базисного дерева (radix tree). Когда происходит чтение данных с носителя, данные читаются в выделяемую в кэше страницу, и страница остаётся в кэше, а драйвер ФС читает из неё данные. Драйвер ФС пишет данные в страницы памяти, находящиеся в кэше. При этом эти страницы помечаются как «грязные» (dirty). Специальный поток ядра, pdflush, регулярно обходит кэш и формирует запросы на запись грязных страниц. Записанная на носитель грязная страница вновь помечается как чистая.

Уровень блочного ввода-вывода

Эта подсистема ядра оперирует очередями (queues), состоящими из структур bio. Каждая такая структура описывает одну операцию ввода-вывода (условно говоря, запрос вида «записать вот эти данные в блоки ##141-142 устройства /dev/hda1»). Для каждого процесса, осуществляющего ввод-вывод, формируется своя очередь. Из этого множества очередей создаётся одна очередь запросов к драйверу каждого устройства.

Планировщик ввода-вывода

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

  • Сортировка: планировщик старается ставить подряд запросы, обращающиеся к находящимся близко секторам диска;

  • Объединение: если в результате сортировки рядом оказались несколько запросов, обращающихся к последовательно расположенным секторам, их нужно объединить в один запрос.

В современном ядре доступно несколько планировщиков: Anticipatory, Deadline, CFQ, noop. Существует версия ядра от Con Kolivas с ещё одним планировщиком — BFQ. Планировщики могут выбираться при компиляции ядра либо при его запуске.

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

Обработка прерываний

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

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

В ядре Linux в результате любого аппаратного прерывания управление передаётся в функцию do_IRQ(). Эта функция использует отдельную таблицу зарегистрированных в ядре обработчиков прерываний, чтобы определить, куда передавать управление дальше.

Чтобы обеспечить минимальное время работы в контексте прерывания, в ядре Linux используется разделение обработчиков на верхние и нижние половины. Верхняя половина — это функция, которая регистрируется драйвером устройства в качестве обработчика определённого прерывания. Она выполняет только ту работу, которая безусловно должна быть выполнена немедленно. Затем она регистрирует другую функцию (свою нижнюю половину) и возвращает управление. Планировщик задач передаст управление зарегистрированной верхней половине, как только это будет возможно. При этом в большинстве случаев управление передаётся нижней половине сразу после завершения работы верхней половины. Но при этом нижняя половина работает как обычный поток ядра, и может быть прервана в любой момент, а потому она имеет право исполняться сколь угодно долго.

В качестве примера можно рассмотреть обработчик прерывания от сетевой карты, сообщающего, что принят ethernet-пакет. Этот обработчик обязан сделать две вещи:

  • Взять пакет из буфера сетевой карты и сигнализировать сетевой карте, что пакет получен операционной системой. Это нужно сделать немедленно по получении прерывания, через милисекунду в буфере будут уже совсем другие данные;

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

Соответственно, первое выполняет верхняя половина обработчика, а второе — нижняя.

Драйвера устройств

Большинство драйверов устройств обычно компилируются в виде модулей ядра. Драйвер устройства получает запросы с двух сторон:

  • От устройства — через зарегистрированные драйвером обработчики прерываний;

  • От различных частей ядра — через API, который определяется конкретной подсистемой ядра и самим драйвером.