Книга: Разработка ядра Linux
Сноски из книги
· #1Это решение было принято на саммите разработчиков ядра Linux (Linux Kernel Development Summit), который состоялся летом 2004 года в г. Оттава, Канада.
· #2Как насчет версии System IV? Ходят слухи, что это внутренняя экспериментальная версия.
· #3Да, конечно, не все, но многое представлено в виде файла. В современных операционных системах, таких как Plan9 (наследник Unix), практически все представляется в виде файлом.
· #4Для тех, кому интересно, дискуссии по поводу отличия свободного кода от открытого доступна в Интернет по адресам http://www.fsf.org
и http://www.opensource.org
.
Вероятно, вам нужно прочесть лицензию GNU GPL, если вы еще не читали ее. В файле COPYING, в исходном коде ядра, есть копия этой лицензии. В Интернет лицензия доступна по адресу http://www.fsf.org
.
Иными словами, заранее неизвестно, в какой момент времени это событие произойдет и в каком состоянии будет система в этот момент времени. — Прим. перев.
· #7Стандарт ISO C99 — это последняя основная версия редакции стандарта ISO С. Редакция C99 содержит многочисленные улучшения предыдущей основной редакции этого стандарта. Стандарт ISO C99 вводит поименную инициализацию полей структур и тип complex
.
Другая абстракция — это файл.
· #9В ядре реализован системный вызов wait4()
. В операционной системе Linux через библиотеку функций языка С доступны функции wait()
, waitpid()
, wait3()
и wait4()
. Все эти функции возвращают информацию о состоянии завершившегося процесса, хотя в несколько разной семантике.
Иногда в литературе по построению операционных систем этот список называется task array (массив задач). Поскольку в ядре Linux используется связанный список, а не статический массив, его называют task list.
· #11Причиной создания структуры thread_info
было не только наличие аппаратных платформ, обедненных регистрами процессора, но и то, что положение этой структуры позволяет достаточно просто рассчитывать смешения адресов для значений ее полей при использовании языка ассемблера.
Скрытый тип (opaque type) — это тип данных, физическое представление которого неизвестно или не существенно.
· #13Именно из-за этого появляются наводящие ужас "неубиваемые" процессы, для которых команда ps(1)
показывает значение состояния, равное D
. Так как процесс не отвечает на сигналы, ему нельзя послать сигнал SIGKILL
. Более того, завершать такой процесс было бы неразумно, так как этот процесс, скорее всего, выполняет какую-либо важную операцию и может удерживать семафор.
Отличным от контекста процесса является контекст прерывания, описанный в главе 6, "Прерывания и обработка прерываний". В контексте прерывания система работает не от имени процесса, а выполняет обработчик прерывания. С обработчиком прерывании не связан ни один процесс, поэтому и контекст процесса отсутствует.
· #15Под exec()
будем понимать любую функцию из семейства exec*()
. В ядре реализован системный вызов execve()
, на основе которого реализованы библиотечные функции execlp()
, execle()
, execv()
и execvp()
.
В действительности сейчас это работает не так, как хотелось бы, однако усилия прилагаются к тому, чтобы порожденный процесс запускался на выполнение первым.
· #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
? Потому что желательно абстрагироваться от реализации кода планировщика и обеспечить доступность для остального кода ядра только лишь некоторых интерфейсов.
Для аппаратной платформы x86 используется инструкция bsfl
, а для платформы PPC — инструкция cntlzw
.
Для аппаратной платформы x86 существует около 250 системных вызовов (для каждой аппаратной платформы разрешается определять свои уникальные системные вызовы). Хотя не для всех операционных систем опубликованы действительные системные вызовы, но по оценкам для некоторых операционных систем таких вызовов более тысячи.
· #24IEEE, eye-triple-E (Институт инженеров по электротехнике и радиоэлектронике, Institute of Electrical and Electronics Engineers) является бесприбыльной профессиональной ассоциацией, действующей во многих технических областях и отвечающей за многие важные стандарты, такие как стандарт POSIX. Больше информации доступно по адресу: http://www.ieee.org
.
Следует обратить внимание на слово "могут". Хотя почти все вызовы создают различные побочные эффекты (т.е. приводят к каким-либо изменениям в состоянии системы), тем не менее небольшое количество вызовов, как, например, вызов getpid()
, просто возвращают некоторые данные ядра.
Тип long
используется для совместимости с 64-разрядными платформами.
Может быть, интересно, почему вызов getpid()
возвращает поле tgid
, которое является идентификатором группы потоков (thread group ID)? Это делается потому, что дли обычных процессов значение параметра TGID
равно значению параметра PID
. При наличии нескольких потоков значение параметра TGID
одинаково дли всех потоков одной группы. Такая реализация дает возможность различным потокам вызывать функцию getpid()
и получать одинаковое значение параметра PID
.
Большая часть дальнейшего описания процесса обработки системных вызовов базируется на версии для аппаратной платформы 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.
Хотя, может быть, она и не такая страшная, какой ее иногда пытаются представить, вес же некоторые люди считают ее "воплощением дьявола" в ядре.
· #52Процессоры Intel x86 никогда не переопределяют порядок операций записи, т.е. выполняют запись всегда в указанном порядке. Тем не менее другие процессоры могут нести себя и по-другому,
· #53Если быть точными, то функции, которые управляются временем, также управляются и событиями. В этом случае событие соответствует ходу времени. В этой главе будут рассмотрены, в основном, события, управляемые временем,так как они встречаются очень часто и являются важными для ядра.
· #54Эмулятор платформы IA-64 имеет частоту 32 Гц. Настоящая машина платформы IA-64 имеет частоту 1024 Гц.
· #55Здесь имеется в виду не точность измерения, а точность в вычислительном плане. Точность измерения (в общенаучном смысле) — это статистическая мера повторяемости результата. В вычислительном (компьютерном) смысле точность — это количество значащих цифр, которые используются для представления того или другого значения.
· #56В связи с ограничениями аппаратной платформы и протокола NTP, значение переменной HZ не может быть произвольным. Для платформы x86 значения 100, 500 и 1000 работают хорошо.
· #57Необходима специальная функция, так как на 32-разрядных аппаратных платформах нельзя атомарно обращаться к двум машинным словам 64-разрядного значения, Специальная функция, перед тем как считать значение, блокирует счетчик импульсов системного таймера с помощью блокировки xtime_lock
.
ля некоторых аппаратных платформ функция sys_time()
не реализована, а вместо этого она эмулируется библиотекой функций языка С на основании вызова gettimeofday()
.
Другая причина состоит в том, что в ядрах старых версий (до 2.3) существовали статические таймеры. Такие таймеры создавались во время компиляции, а не во время выполнения. Они имели ограниченные возможности и из-за их отсутствия сейчас никто не огорчается.
· #60На самом деле, ни один подход не гарантирует, что время задержки будет точно равно указанному значению. Некоторые подходы обеспечивают задержки, очень близкие к точному значению, тем не менее все подходы гарантируют, что время ожидания будет, по крайней мере, не меньше, чем нужно. В некоторых случаях период ожидания получается существенно больше указанного.
· #61Некоторые некачественные устройства PCI также могут выполнять прямой доступ к памяти только к 24-битовом адресном пространстве. Но эти устройства работают не правильно.
· #62Это не имеет ничего общего с верхней памятью в операционной системе DOS.
· #63Данная функция может выделить памяти больше, чем указано, и нет никакой возможности узнать, на сколько больше! Поскольку в своей основе система выделения памяти в ядре базируется на страницах, некоторые запросы на выделение памяти могут округляться, чтобы хорошо вписываться е области доступной памяти. Ядро никогда не выделит меньше памяти, чем необходимо. Если ядро не в состоянии найти хотя бы указанное количество байтов, то операция завершится неудачно и функции возвратит значение NULL
.
Буфер 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 или несуществующий элемент каталога.
А также при захваченной блокировке dentry->d_lock
. — Примеч. перев.
Для создания потоков обычно указываются флаги CLONE_FILES
и CLONE_FS
, поэтому они совместно используют структуры files_struct
и fs_struct
. С другой стороны, для обычных процессов эти флаги не указываются, поэтому для каждого процесса существует своя информация о файловой системе и своя таблица открытых файлов.
Это ограничение является искусственным и в будущем оно может быть отменено. Тем не менее требование, чтобы размер блока был меньше или равен размеру страницы памяти, позволяет значительно упростить ядро.
· #76Это необходимо подчеркнуть особо. Системы, не имеющие таких функций или в которых эти функции плохо реализованы, будут иметь очень плохую производительность даже при небольшом количестве операций блочного ввода-вывода.
· #77Однако все же не желательно задерживать операции записи на неопределенное время. Запросы записи также должны немедленно отправляться на диск, но это не так критично, как в случае запросов чтения.
· #78Для deadline-планировщика операция вставки в начало запроса выполняется опционально. Обычно невыполнение вставки в начало запроса не приводит к проблемам, так как в большинстве случаев количество запросов, которые могут быть добавлены в начало, очень незначительно.
· #79Термин "BSS" сложился исторически и является достаточно старым. Он означает block started by symbol (блок, начинающийся с символа). Неинициализированные переменные в выполняемом файле не хранятся, поскольку с ними не связано никакого значения. Тем не менее стандарт языка С требует, чтобы неинициализированным переменным присваивалось определенное значение по умолчанию (обычно все заполняется нулями). Поэтому ядро загружает переменные (без их значений) из выполняемого файла в память и отображает в эту память нулевую страницу, тем самым переменным присваивается нулевое значение без необходимости зря тратить место в объектном файле на ненужную инициализацию.
· #80В более новых версиях библиотеки glibc функция malloc()
реализована через системный вызов mmap()
, а не через вызов brk()
.
Между дескриптором процесса, дескриптором памяти и соответствующими функциями существует тесная связь. Поэтому структура struct mm_struct
и определена в заголовочном файле sched.h
.
Утилита pmap(1)
печатает форматированный список областей памяти процесса. Результат ее вывода несколько более удобочитаем, чем информация, получаемая из файловой системы /proc
, но это одна и та же информация. Данная утилита включена в новые версии пакета procps
.
Начиная с ядра версии 2.6.11 таблицы страниц в ОС Linux для 64-разрядных аппаратных платформ стали 4-уровневыми, что позволяет в полном объеме использовать все виртуальное адресное пространство. Для 32-разрядных аппаратных платформ осталось 3 уровня, как и раньше. — Примеч. ред.
· #84Как было показано в главе 12," Виртуальная файловая система", операции страничного ввода-вывода непосредственно выполняются не системными вызовами read()
и write()
, а специфичными для файловых систем методами file->f_op->read()
и file->f_op->write()
.
Например, размер страницы физической памяти для аппаратной платформы 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()
. В следующем разделе рассказано, откуда произошло это название.
Если вас заинтересовала информация о файловой системе sysfs, то, вероятно, вам будет интересно также ознакомиться с HAL, hardware abstraction layer (уровень абстракции аппаратного обеспечения), информация о котором доступна по адресу http://hal.freedesktop.org/
. Подсистема HAL позволяет создать в оперативной памяти базу данных на основании информации файловой системы sysfs, объединяя вместе понятия классов, устройств и драйверов. На основании этих данных уровень HAL предоставляет API, которое позволяет разрабатывать более интеллектуальные программы.
Более подробную информацию о демоне D-BUS можно найти на сайте http://dbus.freedesktop.org/
.
Это нормальная ситуация при разработке ядра. Если что-либо должно быть сделано, то это должно быть сделано хорошо! Разработчики ядра неохотно переписывают большие участки кода даже во имя совершенства.
· #92Размер адресуемой памяти может быть меньше максимального значения машинного слова. Например, для 64-разрядных аппаратных платформ размер указателя ранен 64 бит, однако только 48 бит можно использовать для адресации. В дополнение к этому, общее количество физической памяти может быть больше максимального значения машинного слова, как, например, это имеет место при наличии расширения Intel PAE..
· #93За исключением размера типа char
, который всегда равен 8 бит.
На самом деле, для 64-разрядных аппаратных платформ, которые поддерживаются ОС Linux, размеры типов int
и long
не совпадают. Размер типа int равен 32 бит, а размер типа long
— 64 бит. Для хорошо знакомых 32-разрядных аппаратных платформ оба типа данных имеют размер 32 бит.
Если бы компилятор имел возможность изменять порядок следования нолей структуры данных, то любой существующий код, который уже использует эту структуру, мог бы испортить данные. В языке программирования С функции вычисляют положение полей просто путем введения смещений от начального адреса структуры в памяти.
· #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) или равны им.
- Предисловие
- Введение
- Об авторе
- От издательства
- Глава 1 Введение в ядро Linux
- Глава 2 Начальные сведения о ядре Linux
- Глава 3 Управление процессами
- Глава 4 Планирование выполнения процессов
- Глава 5 Системные вызовы
- Глава 6 Прерывания и обработка прерываний
- Глава 7 Обработка нижних половин и отложенные действия
- Глава 8 Введение в синхронизацию выполнения кода ядра
- Глава 9 Средства синхронизации в ядре
- Глава 10 Таймеры и управление временем
- Глава 11 Управление памятью
- Глава 12 Виртуальная файловая система
- Глава 13 Уровень блочного ввода-вывода
- Глава 14 Адресное пространство процесса
- Глава 15 Страничный кэш и обратная запись страниц
- Глава 16 Модули
- Глава 17 Объекты kobject и файловая система sysfs
- Глава 18 Отладка
- Глава 19 Переносимость
- Глава 20 Заплаты, разработка и сообщество
- Приложение А Связанные списки
- Приложение Б Генератор случайных чисел ядра
- Приложение В Сложность алгоритмов
- Приложение Г Библиография и список литературы
- Сноски из книги
- Содержание книги
- Популярные страницы