Разработка ядра Linux [заметки]

1

Это решение было принято на саммите разработчиков ядра Linux (Linux Kernel Development Summit), который состоялся летом 2004 года в г. Оттава, Канада.

2

Как насчет версии System IV? Ходят слухи, что это внутренняя экспериментальная версия.

3

Да, конечно, не все, но многое представлено в виде файла. В современных операционных системах, таких как Plan9 (наследник Unix), практически все представляется в виде файлом.

4

Для тех, кому интересно, дискуссии по поводу отличия свободного кода от открытого доступна в Интернет по адресам http://www.fsf.org и http://www.opensource.org.

5

Вероятно, вам нужно прочесть лицензию GNU GPL, если вы еще не читали ее. В файле COPYING, в исходном коде ядра, есть копия этой лицензии. В Интернет лицензия доступна по адресу http://www.fsf.org.

6

Иными словами, заранее неизвестно, в какой момент времени это событие произойдет и в каком состоянии будет система в этот момент времени. — Прим. перев.

7

Стандарт ISO C99 — это последняя основная версия редакции стандарта ISO С. Редакция C99 содержит многочисленные улучшения предыдущей основной редакции этого стандарта. Стандарт ISO C99 вводит поименную инициализацию полей структур и тип complex.

8

Другая абстракция — это файл.

9

В ядре реализован системный вызов wait4(). В операционной системе Linux через библиотеку функций языка С доступны функции wait(), waitpid(), wait3() и wait4(). Все эти функции возвращают информацию о состоянии завершившегося процесса, хотя в несколько разной семантике.

10

Иногда в литературе по построению операционных систем этот список называется task array (массив задач). Поскольку в ядре Linux используется связанный список, а не статический массив, его называют task list.

11

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

12

Скрытый тип (opaque type) — это тип данных, физическое представление которого неизвестно или не существенно.

13

Именно из-за этого появляются наводящие ужас "неубиваемые" процессы, для которых команда ps(1) показывает значение состояния, равное D. Так как процесс не отвечает на сигналы, ему нельзя послать сигнал SIGKILL. Более того, завершать такой процесс было бы неразумно, так как этот процесс, скорее всего, выполняет какую-либо важную операцию и может удерживать семафор.

14

Отличным от контекста процесса является контекст прерывания, описанный в главе 6, "Прерывания и обработка прерываний". В контексте прерывания система работает не от имени процесса, а выполняет обработчик прерывания. С обработчиком прерывании не связан ни один процесс, поэтому и контекст процесса отсутствует.

15

Под exec() будем понимать любую функцию из семейства exec*(). В ядре реализован системный вызов execve(), на основе которого реализованы библиотечные функции execlp(), execle(), execv() и execvp().

16

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

17

В действительности уже сейчас есть заплаты для добавления такой функции в ОС Linux. Хотя, скорее всего, возможность совместного использования таблиц страниц в ядрах серии 2.6 реализована не будет, такая возможность может появиться в будущих версиях.

18

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

19

Обозначение O(1) — это пример обозначения "большого O". Практически, эта запись означает, что планировщик может выполнить все свои действии за постоянное время, независимо от объема входных данных. Полное объяснение того, что такое обозначение "большого O", приведено в приложении В, "Сложность алгоритмов".

20

Вместо термина timeslice (квант времени) иногда также используется quantum (квант) или processor slice. В ОС Linux применяется термин timeslice.

21

Может возникнуть вопрос: почему используется файл kernel/sched.c, а не заголовочный файл include/linux/sched.h? Потому что желательно абстрагироваться от реализации кода планировщика и обеспечить доступность для остального кода ядра только лишь некоторых интерфейсов.

22

Для аппаратной платформы x86 используется инструкция bsfl, а для платформы PPC — инструкция cntlzw.

23

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

24

IEEE, eye-triple-E (Институт инженеров по электротехнике и радиоэлектронике, Institute of Electrical and Electronics Engineers) является бесприбыльной профессиональной ассоциацией, действующей во многих технических областях и отвечающей за многие важные стандарты, такие как стандарт POSIX. Больше информации доступно по адресу: http://www.ieee.org.

25

Следует обратить внимание на слово "могут". Хотя почти все вызовы создают различные побочные эффекты (т.е. приводят к каким-либо изменениям в состоянии системы), тем не менее небольшое количество вызовов, как, например, вызов getpid(), просто возвращают некоторые данные ядра.

26

Тип long используется для совместимости с 64-разрядными платформами.

27

Может быть, интересно, почему вызов getpid() возвращает поле tgid, которое является идентификатором группы потоков (thread group ID)? Это делается потому, что дли обычных процессов значение параметра TGID равно значению параметра PID. При наличии нескольких потоков значение параметра TGID одинаково дли всех потоков одной группы. Такая реализация дает возможность различным потокам вызывать функцию getpid() и получать одинаковое значение параметра PID.

28

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

29

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

30

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

31

Какой-нибудь процесс выполняется всегда. Если не выполняется никакой процесс, то выполняется холостая задача (idle task).

32

После прочтения главы 10, "Таймеры и управление временем", можно ли сказать, сколько времени (в единицах HZ) машина работала без перегрузки исходя из числа прерываний таймера?

33

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

34

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

35

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

36

Они не имеют ничего общего с понятием task (задача). Их следует понимать как простые в использовании отложенные прерывания (softirq).

37

Большинство драйверов использует для обработки своих нижних половин механизм тасклетов. Тасклеты построены на механизме softirq, как это будет показано ниже.

38

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

39

Это еще один пример плохой терминологии. Почему отложенные прерывания (softirq) генерируются (rise), а тасклеты (tasklet) планируются (schedule)? Кто знает? Оба термина означают, что обработчики нижних половин помечаются как ожидающие на выполнение и в скором времени будут выполнены.

40

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

41

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

42

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

43

Термин поток выполнения подразумевает любой выполняющийся код. Это включает, например, задание в ядре, обработчик прерывания или поток пространства ядра. В этой главе поток выполнения сокращенно называется просто поток. Следует помнить, что этот термин подразумевает любой выполняющийся код.

44

Иными словами, "вращаются" (spin) в замкнутом цикле, ожидая на освобождение блокировки.

45

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

46

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

47

Сейчас это требование становится еще более важным, так как ядро является преемптивным. Время, в течение которого удерживаются блокировки, эквивалентно времени задержки (латентности) системного планировщика.

48

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

49

Как будет показано дальше, несколько процессов могут при необходимости одновременно удерживать один семафор.

50

Доктор Дейкстра (1930–2002 г.) один из самых талантливых ученых за всю (конечно, не очень долгую) историю существования вычислительной техники как области науки. Его многочисленные труды включают работы но проектированию операционных систем и по теории алгоритмов, сюда же входит концепция семафоров. Он родился в городе Роттердам, Нидерланды, и преподавал в университете штата Техас в течение 15 лет. Тем не менее, он был бы не очень доволен большим количеством директив GOTO в ядре Linux.

51

Хотя, может быть, она и не такая страшная, какой ее иногда пытаются представить, вес же некоторые люди считают ее "воплощением дьявола" в ядре.

52

Процессоры Intel x86 никогда не переопределяют порядок операций записи, т.е. выполняют запись всегда в указанном порядке. Тем не менее другие процессоры могут нести себя и по-другому,

53

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

54

Эмулятор платформы IA-64 имеет частоту 32 Гц. Настоящая машина платформы IA-64 имеет частоту 1024 Гц.

55

Здесь имеется в виду не точность измерения, а точность в вычислительном плане. Точность измерения (в общенаучном смысле) — это статистическая мера повторяемости результата. В вычислительном (компьютерном) смысле точность — это количество значащих цифр, которые используются для представления того или другого значения.

56

В связи с ограничениями аппаратной платформы и протокола NTP, значение переменной HZ не может быть произвольным. Для платформы x86 значения 100, 500 и 1000 работают хорошо.

57

Необходима специальная функция, так как на 32-разрядных аппаратных платформах нельзя атомарно обращаться к двум машинным словам 64-разрядного значения, Специальная функция, перед тем как считать значение, блокирует счетчик импульсов системного таймера с помощью блокировки xtime_lock.

58

ля некоторых аппаратных платформ функция sys_time() не реализована, а вместо этого она эмулируется библиотекой функций языка С на основании вызова gettimeofday().

59

Другая причина состоит в том, что в ядрах старых версий (до 2.3) существовали статические таймеры. Такие таймеры создавались во время компиляции, а не во время выполнения. Они имели ограниченные возможности и из-за их отсутствия сейчас никто не огорчается.

60

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

61

Некоторые некачественные устройства PCI также могут выполнять прямой доступ к памяти только к 24-битовом адресном пространстве. Но эти устройства работают не правильно.

62

Это не имеет ничего общего с верхней памятью в операционной системе DOS.

63

Данная функция может выделить памяти больше, чем указано, и нет никакой возможности узнать, на сколько больше! Поскольку в своей основе система выделения памяти в ядре базируется на страницах, некоторые запросы на выделение памяти могут округляться, чтобы хорошо вписываться е области доступной памяти. Ядро никогда не выделит меньше памяти, чем необходимо. Если ядро не в состоянии найти хотя бы указанное количество байтов, то операция завершится неудачно и функции возвратит значение NULL.

64

Буфер TLB (translation lookside buffer или буфер быстрого преобразования адреса) — это аппаратный буфер памяти, который используется в большинстве аппаратных платформ для кэширования отображений виртуальных адресов памяти в физические адреса. Этот буфер позволяет существенно повысить производительность системы, так как большинство операций доступа к памяти выполняются с использованием виртуальной адресации.

65

И позже документированы в работе Bonwirk J. "The Slab Allocator: An Object-Caching Kernel Memory Allocator," USENIX, 1994.

66

РАЕ — Physical Address Extension (расширение физической адресации). Эта функция процессоров x86 позволяет физически адресовать до 36 разрядов (64 Гбайт) памяти, несмотря на то что размер виртуального адресного пространства соответствует только 32 бит.

67

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

68

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

69

Часто многие этого не замечают и даже отрицают, но тем не менее в ядре много примеров объектно-ориентированного программирования. Хотя разработчики ядра и сторонятся языка C++ и других явно объектно-ориентированных языков программировании (ООП), иногда очень полезно мыслить в терминах объектов. Подсистема VFS — это хороший пример того, как просто и эффективно объектно-ориентированное программирование реализуется на языке С, в котором нет объектно-ориентированных конструкций.

70

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

71

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

72

Это название несколько сбивает с толку. В таких объектах нет ничего негативного или отрицательного. Более удачным было бы, наверное, название invalid dentry или несуществующий элемент каталога.

73

А также при захваченной блокировке dentry->d_lock. — Примеч. перев.

74

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

75

Это ограничение является искусственным и в будущем оно может быть отменено. Тем не менее требование, чтобы размер блока был меньше или равен размеру страницы памяти, позволяет значительно упростить ядро.

76

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

77

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

78

Для deadline-планировщика операция вставки в начало запроса выполняется опционально. Обычно невыполнение вставки в начало запроса не приводит к проблемам, так как в большинстве случаев количество запросов, которые могут быть добавлены в начало, очень незначительно.

79

Термин "BSS" сложился исторически и является достаточно старым. Он означает block started by symbol (блок, начинающийся с символа). Неинициализированные переменные в выполняемом файле не хранятся, поскольку с ними не связано никакого значения. Тем не менее стандарт языка С требует, чтобы неинициализированным переменным присваивалось определенное значение по умолчанию (обычно все заполняется нулями). Поэтому ядро загружает переменные (без их значений) из выполняемого файла в память и отображает в эту память нулевую страницу, тем самым переменным присваивается нулевое значение без необходимости зря тратить место в объектном файле на ненужную инициализацию.

80

В более новых версиях библиотеки glibc функция malloc() реализована через системный вызов mmap(), а не через вызов brk().

81

Между дескриптором процесса, дескриптором памяти и соответствующими функциями существует тесная связь. Поэтому структура struct mm_struct и определена в заголовочном файле sched.h.

82

Утилита pmap(1) печатает форматированный список областей памяти процесса. Результат ее вывода несколько более удобочитаем, чем информация, получаемая из файловой системы /proc, но это одна и та же информация. Данная утилита включена в новые версии пакета procps.

83

Начиная с ядра версии 2.6.11 таблицы страниц в ОС Linux для 64-разрядных аппаратных платформ стали 4-уровневыми, что позволяет в полном объеме использовать все виртуальное адресное пространство. Для 32-разрядных аппаратных платформ осталось 3 уровня, как и раньше. — Примеч. ред.

84

Как было показано в главе 12," Виртуальная файловая система", операции страничного ввода-вывода непосредственно выполняются не системными вызовами read() и write(), а специфичными для файловых систем методами file->f_op->read() и file->f_op->write().

85

Например, размер страницы физической памяти для аппаратной платформы x86 равен 4 Кбайт, в то время как размер дискового блока для большинства устройств и файловых систем равен 512 байт. Следовательно, в одной странице памяти может храниться 8 блоков. Блоки не обязательно должны быть смежными, так как один файл может быть физически "разбросанным" по диску.

86

Реализация ядра основана на базисном дереве поиска по приоритетам, предложенном в работе Edward M. McCreight, опубликованной в журнале SIAM Journal of Computing, May 1985, vol. 14. №2, P. 257–276.

87

Слово "gang" не является жаргонным. Этот термин часто используется в компьютерных науках, чтобы указать группу чего-либо, что может выполняться параллельно.

88

Да, название функции не совсем верное. Должно было бы быть wakeup_pdflush(). В следующем разделе рассказано, откуда произошло это название.

89

Если вас заинтересовала информация о файловой системе sysfs, то, вероятно, вам будет интересно также ознакомиться с HAL, hardware abstraction layer (уровень абстракции аппаратного обеспечения), информация о котором доступна по адресу http://hal.freedesktop.org/. Подсистема HAL позволяет создать в оперативной памяти базу данных на основании информации файловой системы sysfs, объединяя вместе понятия классов, устройств и драйверов. На основании этих данных уровень HAL предоставляет API, которое позволяет разрабатывать более интеллектуальные программы.

90

Более подробную информацию о демоне D-BUS можно найти на сайте http://dbus.freedesktop.org/.

91

Это нормальная ситуация при разработке ядра. Если что-либо должно быть сделано, то это должно быть сделано хорошо! Разработчики ядра неохотно переписывают большие участки кода даже во имя совершенства.

92

Размер адресуемой памяти может быть меньше максимального значения машинного слова. Например, для 64-разрядных аппаратных платформ размер указателя ранен 64 бит, однако только 48 бит можно использовать для адресации. В дополнение к этому, общее количество физической памяти может быть больше максимального значения машинного слова, как, например, это имеет место при наличии расширения Intel PAE..

93

За исключением размера типа char, который всегда равен 8 бит.

94

На самом деле, для 64-разрядных аппаратных платформ, которые поддерживаются ОС Linux, размеры типов int и long не совпадают. Размер типа int равен 32 бит, а размер типа long — 64 бит. Для хорошо знакомых 32-разрядных аппаратных платформ оба типа данных имеют размер 32 бит.

95

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

96

Брайан У. Керниган, Деннис M. Ритчи, Язык программирования С, 2-е изд. Пер. с англ. — M.: Издат. дом "Вильямс", 2005.

97

Вопросы сложности алгоритмов рассматриваются в приложении В.

98

Клод Шеннон (30 апреля 1916–24 февраля 2001) работал инженером в компании Bell Labs. В его наиболее известной работе Математическая теории связи, опубликованной в 1948 году, впервые были разработаны основы информационной теории и было введено понятие энтропии Шеннона. Шеннон также любил кататься на одноколесном велосипеде.

99

Джон фон Нейман (28 декабря 1903–8 февраля 1957) работал в Институте специальных исследований в Принстоне (Institute for Advanced Study; Princeton). Он внес большой вклад в математические, экономические и компьютерные науки. Среди наиболее значительных его разработок — теория игр, фон-неймановские алгебры и фон-неймановская проблема узких мест.

100

Если интересно, то нижняя граница описывается с помощью обозначения большого-омега. Определение аналогично определению множества большого-О, за исключением того, что значения функции g(x) должны быть меньше значений функции f(x) или равны им.