суббота, марта 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, который определяется конкретной подсистемой ядра и самим драйвером.

14 комментариев:

  1. Очень познавательно, спасибо! Люблю читать статьи об истории и развитии разного "компового" :) А про Linux в двойне :) Следующий шаг - описание всех опций при компиляции с подробным объяснением "что? куда? и откуда?" :)

    ОтветитьУдалить
  2. Анонимный3/13/2010 8:10 ДП

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

    ОтветитьУдалить
  3. Прекрасная статья. Правда, я не понимаю как всё это можно было рассказать за 10 минут. Слушатели наверное тупо ничего толком не поняли, а засыпали вопросами после :)

    ОтветитьУдалить
  4. Анонимный3/13/2010 10:38 ДП

    Мда, чтобы хотя бы понять, о чем тут речь, неплохо бы заранее прослушать курс "Операционные системы" совокупной длительностью около полутора суток.

    ОтветитьУдалить
  5. Отличное описание! Спасибо!

    ОтветитьУдалить
  6. модульность ничего не говорит о монолитности/микроядерности. Современное ядро модульное+монолитное, но система GNU/Linux - гибридная - часть системных сервисов (udev/fuse/dbus и др.) вынесены в юсерспейс.

    ОтветитьУдалить
  7. @smartly
    Я там пишу, что модульное ядро - это разновидность монолитного.

    udev и dbus не являются системными сервисами, это обычные пользовательские приложения, без них система вполне может работать (ну, флешки автомонтироваться не будут, так для этого можно другие приложения использовать). У FUSE промежуточный статус, про это я коротко упомянул.

    ОтветитьУдалить
  8. Portnov:
    1. Вот как раз не является модульное разновидностью монолитного. Модульное - просто возможность разбить программу на несколько кусков и подгружать по мере необходимости. Модульным может быть и микроядерное ядро (хотя смысла обычно нету)

    2. Система много без чего может работать. udev/dbus/fuse/cuse - это и есть пример, когда сервис выносится из ядра (как в микроядерных)

    ОтветитьУдалить
  9. Спасибо, был на семинаре в Магу, сейчас случайно увидел на руниксе. Очень качественный доклад.

    ОтветитьУдалить
  10. Анонимный3/18/2010 5:46 ДП

    Насчет "модульного" и "монолитного" осмелюсь высказать свое мнение, которое, надеюсь, поможет избежать терминологических споров, подобных возникшему в обсуждении данной статьи.
    Монолитным назовем ядро, все части которого работают в одном адресном пространстве и с одним и тем же (высшим) уровнем привилегий, следовательно, могут напрямую (без шлюзов вызова, программных прерываний, и спец. инструкций типа syscall\sysenter) обращаться к структурам данных друг друга и так же напрямую передавать друг другу управление. Соответственно, от некорректных манипуляций с данными и от неправильной передачи управления защита только одна - котроль качества исходного кода.
    В противоположность монолитному ядро микроядерной системы, состоящее из микроядра и загруженных в данный момент "серверов ОС" (или менеджеров, или администраторов, как их только не называют %-), работающих в изолированных адресных пространствах и защищенных друг от друга аппаратными средствами, назовем "композитным".
    Модульным назовем ядро, которое загружается из множества файлов и, что самое главное, поддерживает загрузку-выгрузку отдельных частей во время работы. Т.о. модульным может быть и монолитное ядро ОС. Что же касается микроядерной системы, то ей модульность присуща изначально (хотя ничто не мешает скомпоновать микроядро и серверы в один загружаемый файл и "отключить" возможность перезагрузки серверов. Зачем? Это другой вопрос).
    Соотв. термины "модульный" и "монолитный" станут независимыми и взаимодополняющими друг друга, что и поможет избежать споров из-за неверного, на мой взгляд, их противопоставления :)
    С уважением ко всем присутствующим :)

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

    ОтветитьУдалить
  12. Анонимный3/28/2010 7:21 ДП

    перепутаны нижние и верхние половины в обработчике прерываний:
    верхняя (hard irq) половина - выполняется с отключеннием аппаратных прерываний на текущем процессоре (за искл. non-maskable-interrupts - nmi, зависит от архитектуры). Чтобы не пропустить другие аппаратные прерывания должна выполняться быстро - обычно формируя задание для нижней (bottom-half aka soft-irq) половины, которая уже выполняется с разрешенными аппаратными прерываниями, но со все еще отключенным шедулером.

    Подробнее про блокировки между различными контекстами выполнения в ядре:

    http://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/index.html

    ОтветитьУдалить
  13. @Анонимный
    Оп-па. Натурально, перепуталось. Сейчас поправлю в тексте. Спасибо.

    ОтветитьУдалить