Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 www.iakovlev.org 

 
 

Роберт Лав , Разработка ядра Linux

1. Чем ядро Линукс отличается от классических ядер Unix ?

2. Что такое инкрементная заплата или патч ?

3. Где хранится конфигурация ядра ?

4. На какие типы делятся переменные в файле config ?

5. Какие утилиты настраивают конфигурацию ядра ?

6. Как инсталлировать ядро ?

7. Чем ядро отличается от обычных программ ?

8. Для чего нужны директивы likely и unlikely ?

9. Какова особенность стека для ядра ?

10. Для чего в ядре нужна синхронизация ?

11. task_struct ?

12. Где хранится task_struct ?

13. Для чего нужен макрос current ?

14. В каких состояниях может находиться процесс в пространстве ядра ?

15. Как можно манипулировать текущим состоянием процесса ?

16. Что такое контекст процесса ?

17. Какова иерархия процессов в ядре ?

18. Как выделяется память в функции fork ?

19. Как работает fork ?

20. Как работает vfork ?

21. Как работают kernel threads ?

22. Как происходит завершение процесса в ядре ?

23. Как удаляется дескриптор процесса ?

24. Как решается проблема зомби ?

Планировщик

25. Каких типов бывает многозадачность ?

26. Приоритеты процессов ?

27. Алгоритм шедулятора ?

28. Очереди выполнения ?

29. Массивы приоритетов ?

30. Пересчет квантов времени ?

31. Функция shedule() ?

32. Вычисление приоритетов и квантов времени ?

33. Остановка процесса в ядре ?

34. Балансировка нагрузки для много-процессорных систем ?

35. Вытеснение и переключение контекста ?

36. Preemption ?

37. Режим реального аремени ?

38. Системные вызовы для управления планировщиком ?

Системные вызовы / прерывания

39. Вызов syscall ?

40. Как происходит обработка системных вызовов ?

41. Макросы syscalln() ?

42. Обработчики прерываний ?

43. Регистрация обработчика прерываний ?

44. Создание нового обработчика прерываний ?

45. /pro/interrupts ?

Синхронизация ядра

46. Основы синхронизации ?

47. Атомарные операции ?

48. Спин-блокировки ?

49. Семафоры ?

50. Сравнение спин-блокировок и семафоров ?

51. BLK : Большая блокировка ядра ?

52. Секвентные - последовательные - блокировки ?

53. Барьеры ?

Таймеры

54. Системный таймер ?

55. Частота таймера HZ ?

56. Обработчик прерываний таймера ?

57. Абсолютное время ?

58. Динамические таймеры ?

Память

59. Страницы памяти ?

60. Зоны памяти ?

61. Выделение памяти ?

62. Функции kmalloc / kfree / vmalloc ?

63. Свободные ресурсы (free list) и slab layer ?

VFS

64. Обьекты VFS ?

65. Суперблок ?

66. Нода ?

67. Кеш dentry ?

68. Файл ?

Ответы

1.
 1. Ядро Linux поддерживает динамическую загрузку модулей ядра, хотя ядро
 Linux и является монолитным.
 2. Ядро Linux поддерживает симметричную многопроцессорную обработку (SMP).
 3. Ядро Linux является преемптивным. В отличие от традиционных вариантов
 ОС Unix, ядро Linux в состоянии вытеснить выполняющееся задание, даже
 если это задание работает в режиме ядра.
 4. В ядре Linux используется интересный подход для поддержки многопоточно-
 сти (threads): потоки ни чем не отличаются от обычных процессов.
 

2.

 patch — это основной язык общения. 
 Вы будете распространять ваши изменения исходного кода ядра в виде заплат
 и получать изменения кода от других разработчиков тоже в виде заплат. При дан-
 ном рассмотрении наиболее важными являются инкрементные заплаты (incremental
 patch), которые позволяют перейти от одной версии ядра к другой. Вместо того что-
 бы загружать большой архив ядра, можно просто применить инкрементную заплату
 и перейти от имеющейся версии к следующей. Это позволяет сэкономить время и
 пропускную способность каналов связи. Для того чтобы применить инкрементную
 заплату, находясь в каталоге дерева исходных кодов ядра, нужно просто выполнить
 следующую команду.
     $ patch -p1 < ../patch-х.у.z
 Обычно заплата для перехода на некоторую версию ядра должна применяться к
 предыдущей версии ядра.
 
 

3. в корневом файле config в каталоге ядра

 
 

4.

 1. логические - принимают 2 состояния - да , нет
 2. instate-переменные - с 3-мя состояниями : да , нет , модуль (обычно для драйверов)
 

5.

 В ядре поддерживается несколько инструментов, которые позволяют выполнять
 конфигурацию. Наиболее простой инструмент — это текстовая утилита командной
 строки:
     make config
 Эта утилита просматривает все параметры один за другим и интерактивно запра-
 шивает у пользователя, какое значение соответствующего параметра установить —
 yes, no или module {для переменной с тремя состояниями). Эта операция требует
 длительного времени, и если у вас не почасовая оплата, то лучше использовать утили-
 ту на основе интерфейса ncurses:
     make menuconfig
 или графическую утилиту на основе системы X11:
     make xconfig
 или еще более удобную графическую утилиту, основанную на библиотеке gtk+
     make gconfig
 Эти утилиты позволяют разделить все параметры по категориям, таким как
 Processor Features (Свойства процессора) и Network Devices (Сетевые устройства).
 Пользователи могут перемещаться по категориям и, конечно, изменять значения
 конфигурационных параметров. Команда
     $ make defconfig
 позволяет создать конфигурационный файл, который будет содержать параметры,
 используемые по умолчанию для текущей аппаратной платформы.
 После внесения изменений в конфигура-
 ционный файл или при использовании существующего конфигурационного файла
 для нового дерева каталогов исходного кода ядра, необходимо активизировать и об-
 новить конфигурацию с помощью команды:
     make oldconfig
 Кстати, перед сборкой ядра эту команду также необходимо выполнить. После того
 как конфигурация ядра выполнена, можно выполнить сборку с помощью команды:
     make
 
 

6. можно скопировать загружаемый образ ядра из файла arch/i386/boot/bzlmage в каталог /boot .

 Инсталляция модулей ядра автоматизирована и не зависит от аппаратной плат-
 формы. Просто нужно запустить следующую команду с правами пользователя root.
     $ make modules_install
 
 

7.

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

8.

 Компилятор gnu С имеет встроенные директивы, позволяющие оптимизировать
 различные ветви условных операторов, которые наиболее или наименее вероятны.
 Компилятор использует эти директивы для соответственной оптимизации кода.
 В ядре эти директивы заключаются в макросы likely ( ) и unlikely ( ) , которые
 легко использовать. Например, если используется оператор if следующего вида:
     if (foo) {
     /*..*/
     }
 то для того, чтобы отметить этот путь выполнения как маловероятный, необходимо
 указать:
     if (unllkely(ffoo)) {
     /*..*/
     }
 И наоборот, чтобы отметить этот путь выполнения как наиболее вероятный
     if (likely(foo)) {
     /*..*/
     }
 Эти директивы необходимо использовать только в случае, когда направление вет-
 вления с большой вероятностью известно априори или когда необходима оптимиза-
 ция какой-либо части кода за счет другой части. Важно помнить, что эти директивы
 дают увеличение производительности, когда направление ветвления предсказано
 правильно, однако приводят к потере производительности при неправильном пред-
 сказании.
 

9.

 Пользовательские программы могут "отдохнуть" вместе со своими тоннами ста-
 тически выделяемых переменных в стеке, включая структуры большого размера и
 многоэлементные массивы. Такое поведение является законным в режиме задачи,
 так как область стека пользовательских программ может динамически увеличиваться
 в размере (разработчики, которые писали программы под старые и не очень интел-
 лектуальные операционные системы, как, например, DOS, могут вспомнить то вре-
 мя, когда даже стек пользовательских программ имел фиксированный размер).
 Стек, доступный в режиме ядра, не является ни большим, ни динамически изме-
 няемым, он мал по объему и имеет фиксированный размер. Размер стека зависит от
 аппаратной платформы. Для платформы х86 размер стека может быть сконфигури-
 рован на этапе компиляции и быть равным 4 или 8 Кбайт. Исторически так сложи-
 лось, что размер стека ядра равен двум страницам памяти, что соответствует 8 Кбайт
 для 32-разрядных аппаратных платформ и 16 Кбайт — для 64-разрядных. Этот размер
 фиксирован. Каждый процесс получает свою область стека.
 Более подробное обсуждение использования стека в режиме ядра смотрите в сле-
 дующих главах.
 
 

10.

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

11.

 Ядро хранит информацию о всех процессах в двухсвязном списке, который на-
 зывается task list (список задач). Каждый элемент этого списка является дескрипто-
 ром процесса и имеет тип структуры struct task_struct, которая описана в файле
 include/linux/sched.h. Дескриптор процесса содержит всю информацию об
 определенном процессе.
 Структура task_struct — достаточно большая структура данных размером по-
 рядка 1,7 Кбайт на 32-разрядной машине. 
 
 

12. Для каждого процесса выделяется стек строго фиксированного размера. В конце этого стека лежит структура thread_info :

     struct thread_info {
     struct task_struct *task;
     ...
     };
 
 Элемент этой структуры task и является указателем на структуру task_struct
 

13. он указывает на текущий процесс , с которым работает ядро. Для платформы х86 значение параметра current вычисляется путем маскирования 13 младших бит указателя стека для получения адреса структуры thread_infо. Это мо- жет быть сделано с помощью функции current_thread_info (). Для других платформ структура может храниться в отдельном регистре.

 
 

14. Каждый процесс в системе гарантированно находится в одном из пяти различных состояний.

 • TASK_RUNNING— процесс готов к выполнению (runnable). Иными словами,
 либо процесс выполняется в данный момент, либо находится в одной из оче-
 редей процессов, ожидающих на выполнение (эти очереди, runqueue, обсуж-
 даются в главе 4. "Планирование выполнения процессов").
 • TASK_INTERRUPTIBLE — процесс приостановлен (находится в состоянии
 ожидания, sleeping), т.е. заблокирован в ожидании выполнения некоторого
 условия. Когда это условие выполнится, ядро переведет процесс в состояние
 TASK__RUNNING. Процесс также возобновляет выполнение (wake up) преждевре-
 менно при получении им сигнала.
 • TASK_UNNTERRUPTIBLE - аналогично TASK_INTERRUPTIBLE, за исключени-
 ем того, что процесс не возобновляет выполнение при получении сигнала.
 Используется в случае, когда процесс должен ожидать беспрерывно или когда
 ожидается, что некоторое событие может возникать достаточно часто. Так как
 задача в этом состоянии не отвечает на сигналы, TASK_UNINTERRUPTIBLE ис-
 пользуется менее часто, чем TASK_INTERRUPTIBLE6.
 • TASK_ZOMBIE — процесс завершен, однако порождающий его процесс еще не
 вызвал системный вызов wait4 ( ) . Дескриптор такого процесса должен оста-
 ваться доступным на случай, если родительскому процессу потребуется доступ
 к этому дескриптору. Когда родительский процесс вызывает функцию wait4 (),
 то такой дескриптор освобождается.
 • TASK_STOPPED — выполнение процесса остановлено. Задача не выполняется и
 не имеет право выполняться. Такое может случиться, если задача получает ка-
 кой-либо из сигналов SIGSTOP, SIGTSTP, SIGTTIN или SIGTTOU, а также если
 сигнал приходит в тот момент, когда процесс находится в состоянии отладки.
 
 

15.

 Исполняемому коду ядра часто необходимо изменять состояние процесса.
 Наиболее предпочтительно для Этого использовать функцию
     set_task_state(task, state);
 Вызов 
     set_current_ state(state) является синонимом к вызову 
     set_task_state(current, state).
 
 

16.

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

17.

 В операционной системе Linux существует четкая иерархия процессов. Все про-
 цессы являются потомками процесса init , значение идентификатора PID для кото-
 рого равно 1. Ядро запускает процесс init на последнем шаге процедуры загрузки
 системы. Процесс init , в свою очередь, читает системные файлы сценариев началь-
 ной загрузки (initscripts) и выполняет другие программы, что в конце концов заверша-
 ет процедуру загрузки системы.
  Каждый процесс в системе имеет всего один порождающий процесс. Кроме
 того, каждый процесс может иметь один или более порожденных процессов.
 Процессы, которые порождены одним и тем же родительским процессом, назы-
 ваются родственными (siblings). Информация о взаимосвязи между процессами хра-
 нится в дескрипторе процесса. Каждая структура task_struct содержит указатель
 на структуру task_struct родительского процесса, который называется parent,
 эта структура также имеет список порожденных процессов, который называется
 children. Следовательно, если известен текущий процесс (current), то для него
 можно определить дескриптор родительского процесса с помощью выражения:
     struct task_struct *task = current->parent;
 Аналогично можно выполнить цикл по процессам, порожденным от текущего
 процесса, с помощью кода:
     struct task_struct *task;
     struct list_head *list;
     list_for_each (list, scurrent->children) 
     {
         task = list_entry(list, struct task_struct, sibling);
         /* переменная task теперь указывает на один из процессов,
         порожденных текущим процессом */
     }
 
 Дескриптор процесса init — это статически выделенная структура данных с име-
 нем inittask . Хороший пример использования связей между всеми процессами —
 это приведенный ниже код, который всегда выполняется успешно.
     struct task_struct *task
     for (task = current; task ! = $init_task; task = task->parent)
     /* переменная task теперь указывает на процесс init */
 
 Конечно, проходя по иерархии процессов, можно перейти от одного процесса
 системы к другому. Иногда, однако, желательно выполнить цикл по всем процессам
 системы. Такая задача решается очень просто, так как список задач — это двухсвяз-
 ный список. Для того чтобы получить указатель на следующее задание из этого спи-
 ска, имея действительный указатель на дескриптор какого-либо процесса, можно ис-
 пользовать показанный ниже код:
     list_entry(task->tasks.next, struct task_struct, tasks)
 Получение указателя на предыдущее задание работает аналогично.
     list_entry (task->tasks.prev, struct task_struct, tasks)
 Дна указанных выше выражения доступны также в виде макросов next_task (task)
 (получить следующую задачу), prev_task (task) (получить предыдущую задачу).
 Наконец, макрос for_each_process (task) позволяет выполнить цикл по всему
 списку задач. На каждом шаге цикла переменная task указывает на следующую за-
 дачу из списка:
     struct task_struct *task;
     for_each_process(task) {
     /* просто печатается имя команды и идентификатор PID
     для каждой задачи */
     printk("%s[%d]\n", task->comm, task->pid);
     }
 
 

18.

 Традиционно при выполнении функции fork() делался дубликат всех ресурсов
 родительского процесса и передавался порожденному. Такой подход достаточно
 наивный и неэффективный. В операционной системе Linux вызов fork () реализо-
 ван с использованием механизма копирования при записи (copy-on-write) страниц памяти.
 Технология копирования при записи (copy-on-write, COW) позволяет отложить или
 вообще предотвратить копирование данных. Вместо создания дубликата адресного
 пространства процесса родительский и порожденный процессы могут совместно ис-
 пользовать одну и ту же копию адресного пространства. Однако при этом данные
 помечаются особым образом, и если вдруг один из процессов начинает изменять
 данные, то создается дубликат данных, и каждый процесс получает уникальную ко-
 пию данных. Следовательно, дубликаты ресурсов создаются только тогда, когда в
 эти ресурсы осуществляется запись, а до того момента они используются совместно
 в режиме только для чтения (read-only). Такая техника позволяет задержать копи-
 рование каждой страницы памяти до того момента, пока в эту страницу памяти не
 будет осуществляться запись. В случае, если в страницы памяти никогда не делается
 запись, как, например, при вызове функции exec () сразу после вызова fork (), то
 эти страницы никогда и не копируются. Единственные накладные расходы, которые
 вносит вызов функции fork ( ) , — это копирование таблиц страниц родительского
 процесса и создание дескриптора порожденного процесса. Данная оптимизация пре-
 дотвращает ненужное копирование большого количества данных (размер адресного
 пространства часто может быть более 10 Мбайт), так как процесс после разветвле-
 ния в большинстве случаев сразу же начинает выполнять новый исполняемый образ.
 Эта оптимизация очень важна, потому чти идеология операционной системы Unix
 предусматривает быстрое выполнение процессов.
 
 

19.

 В операционной системе Linux функция fork () реализована через системный
 вызов clone () . Этот системный вызов может принимать в качестве аргументов
 набор флагов, определяющих, какие ресурсы должны быть общими (если вообще
 должны) у родительского и порожденного процессов. Далее в разделе "Реализация
 потоков в ядре Linux" об этих флагах рассказано более подробно. 
 f o r k ( ) вызывает системную функцию clone () с
 соответствующими флагами. В свою очередь системный вызов clone () вызывает
 функцию ядра do_fork ().
 Основную массу работы по разветвлению процесса выполняет функция do_f ork (),
 которая определена в файле kernel/fork.с. Эта функция, в свою очередь, вызыва-
 ет функцию copy_pracess () и запускает новый процесс на выполнение. Ниже опи-
 сана та интересная работа, которую выполняет функция copy_process ().
 • Вызывается функция dup_task_struct (), которая создает стек ядра, струк-
 туры thread_info и task_struct для нового процесса, причем все значения
 указанных структур данных идентичны для порождающего и порожденного
 процессов. На этом этапе дескрипторы родительского и порожденного про-
 цессов идентичны.
 • Проверяется, не произойдет ли при создании нового процесса переполнение
 лимита на количество процессов для данного пользователя.
 • Теперь необходимо сделать порожденный процесс отличным от родительско-
 го. При этом различные поля дескриптора порожденного процесса очищаются
 или устанавливаются в начальные значения. Большое количество данных де-
 скриптора процесса является совместно используемым.
 • Далее состояние порожденного процесса устанавливается в значение TASK_
 UNINTERRUPTIBLE, чтобы гарантировать, что порожденный процесс не будет
 выполняться.
 • Из функции copy_process () вызывается функция copy_f lags (), которая об-
 новляет значение поля flags структуры task struct. При этом сбрасывается
 флаг PF_SUPERPRIV, который определяет, имеет ли процесс права суперполь-
 зователя. Флаг PF_FORKNOEXEC, который указывает на то, что процесс не вы-
 звал функцию exec (), — устанавливается.
 • Вызывается функция get_pid () , которая назначает новое значение иденти-
 фикатора PID для новой задачи.
 • В зависимости от значений флагов, переданных в функцию clone (), осущест-
 вляется копирование или совместное использование открытых файлов, инфор-
 мации о файловой системе, обработчиков сигналов, адресного пространства
 процесса и пространства имен (namespace). Обычно эти ресурсы совместно ис-
 пользуются потоками одного процесса. В противном случае они будут уникаль-
 ными и будут копироваться на этом этапе.
 • Происходит разделение оставшейся части кванта времени между родитель-
 ским и порожденным процессами (это более подробно обсуждается в главе 4,
 "Планирование выполнения процессов").
 • Наконец, происходит окончательная зачистка структур данных и возвращается
 указатель на новый порожденный процесс.
 Далее происходит возврат в функцию do_fork () . Если возврат из функции
 copy_process () происходит успешно, то новый порожденный процесс возобновля-
 ет выполнение. Порожденный процесс намеренно запускается на выполнение рань-
 ше родительского.
 
 

20.

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

21.

 Часто в ядре полезно выполнить некоторые операции в фоновом режиме. В ядре
 такая возможность реализована с помощью потоков пространства ядра (kernel thread) —
 обычных процессов, которые выполняются исключительно в пространстве ядра.
 Наиболее существенным отличием между потоками пространства ядра и обычными
 процессами является то, что потоки в пространстве ядра не имеют адресного про-
 странства (значение указателя mm для них равно NULL). Эти потоки работают только
 в пространстве ядра, и их контекст не переключается в пространство пользователя.
 Тем не менее потоки в пространстве ядра планируются и вытесняются так же, как и
 обычные процессы.
  В ядре Linux потоки пространства ядра выполняют определенные задания,
 наиболее часто используемые, — это pdflush и ksoftirq. Эти потоки создаются при за-
 грузке системы другими потоками пространства ядра. В действительности поток в
 пространстве ядра может быть создан только другим потоком, работающим в про-
 странстве ядра. Интерфейс для запуска нового потока в пространстве ядра из уже
 существующего потока следующий:
     int kernel_thread(int (*fn) (void * ) , void * arg, unsigned long flags)
 Новая задача создается с помощью обычного системного вызова clone () с соот-
 ветствующими значениями флагов, указанными в параметре flags. При возврате из
 системного вызова родительский поток режима ядра завершается и возвращает ука-
 затель на структуру t a s k _ s t r u c t порожденного процесса. Порожденный процесс
 выполняет функцию, адрес которой указан в параметре fn, в качестве аргумента
 этой функции передается параметр arg. Для указания обычных флагов потоков про-
 странства ядра существует флаг CLONE_KERNEL, который объединяет в себе флаги
 CLONE_FS, CLONE_FILES и CLONE_SIGHAND, так как большинство потоков простран-
 ства ядра должны указывать эти флаги в параметре flags.
 Чаще всего поток пространства ядра продолжает выполнять свою функцию вечно
 (или, по крайней мере, до перегрузки системы, но когда она произойдет в случае ОС
 Linux- неизвестно). Функция потока обычно содержит замкнутый цикл, в котором
 поток пространства ядра по необходимости возобновляет выполнение, исполняет
 свои обязанности и снова переходит в приостановленное состояние.
 
 

22.

 Когда процесс завершается, ядро должно освободить ресурсы, занятые процессом,
 и оповестить процесс, который является родительским для завершившегося, о том,
 что его порожденный процесс, к сожалению, "умер".
 Обычно уничтожение процесса происходит тогда, когда процесс вызывает си-
 стемный вызов e x i t () явно или неявно при выходе из главной функции программы
 (компилятор языка С помещает вызов функции e x i t () после возврата из функции
 main ()). Процесс также может быть завершен непроизвольно. Это происходит, ког-
 да процесс получает сигнал или возникает исключительная ситуация, которую про-
 цесс не может обработать или проигнорировать. Независимо от того, каким обра-
 зом процесс завершается, основную массу работы выполняет функция doexec (), а
 именно указанные далее операции.
 • Устанавливается флаг PF_EXITING в поле flags структуры task struct.
 • Вызывается функция del_timer_sync (), чтобы удалить все таймеры ядра.
 После выхода из этой функции гарантируется, что нет никаких ожидающих
 таймеров и никакой обработчик таймера не выполняется.
 • Если включена возможность учета системных ресурсов, занятых процессами
 (BSD process accounting), то вызывается функция acct_process () для записи
 информации об учете ресурсов, которые использовались процессом.
 • Вызывается функция __exit_mm() для освобождения структуры mm_struct,
 занятой процессом. Если эта структура не используется больше ни одним про-
 цессом (другими словами, не является разделяемой), то она освобождается со-
 всем.
 • Вызывается функция exit_sem (). Если процесс находится в очереди ожида-
 ния на освобождение семафора подсистемы IPC, то в этой функции процесс
 удаляется из этой очереди.
 • Вызываются функции __exit_files (), __exit_fs () , exit_namespace () и
 exit_signals () для уменьшения счетчика ссылок на объекты, которые от-
 вечают файловым дескрипторам, данным по файловой системе, пространству
 имен и обработчикам сигналов соответственно. Если счетчик ссылок какого-
 либо объекта достигает значения, равного нулю, то соответствующий объект
 больше не используется никаким процессом и удаляется.
 • Устанавливается код завершения задания, который хранится в поле e x i t c o d e
 структуры task struct. Значение этого кода передается как аргумент функ-
 ции exit () или задается тем механизмом ядра, из-за которого процесс завер-
 шается.
 • Вызывается функция e x i t n o t i f у (), которая отправляет сигналы родитель-
 скому процессу завершающегося задания и назначает новый родительский про-
 цесс (reparent) для всех порожденных завершающимся заданием процессов,
 этим процессом становится или какой-либо один поток из группы потоков за-
 вершающегося процесса, или процесс i n i t . Состояние завершающегося про-
 цесса устанавливается в значение TASK_ZOMBIE.
 • Вызывается функция schedule () для переключения на новый процесс (см. гла-
 ву 4, "Планирование выполнения процессов"). Поскольку процесс в состоянии
 TASK_ZOMBIE никогда не планируется на выполнение, этот код является по-
 следним, который выполняется завершающимся процессом.
 Исходный код функции do_exit () описан в файле kernel/exit.с.
 К этому моменту освобождены все объекты, занятые задачей (если они использу-
 ются только этой задачей). Задача больше не может выполняться (действительно, у
 нее больше нет адресного пространства, в котором она может выполняться), а кро-
 ме того, состояние задачи — TASK_ZOMBIE. Единственные области памяти, которые
 теперь занимает процесс, — это стек режима ядра и слябовый объект, соответствен-
 но содержащие структуры thread_inf о и task_struct.
 
 

23.

 После возврата из функции do_exit () дескриптор завершенного процесса все
 еще существует в системе, но процесс находится в состоянии TASK_ZOMBIE и не мо-
 жет выполняться. Как уже рассказывалось выше, это позволяет системе получить
 информацию о порожденном процессе после его завершения. Следовательно, завер-
 шение процесса и удаление его дескриптора происходят в разные моменты времени.
 После того как родительский процесс получил информацию о завершенном порож-
 денном процессе, структура task_struct порожденного процесса освобождается.
 Семейство функций wait () реализовано через единственный (и достаточно
 сложный) системный вызов wait4 (). Стандартное поведение этой функции — при-
 остановить выполнение вызывающей задачи до тех пор, пока один из ее порожден-
 ных процессов не завершится. При этом возвращается идентификатор PID завершен-
 ного порожденного процесса. В дополнение к этому, в данную функцию передается
 указатель на область памяти, которая после возврата из функции будет содержать
 код завершения завершившегося порожденного процесса.
 Когда приходит время окончательно освободить дескриптор процесса, вызывает-
 ся функция release_task (), которая выполняет указанные ниже операции.
 • Вызывается функция free_uid () для декремента счетчика ссылок на инфор-
 мацию о пользователе процесса. В системе Linux поддерживается кэш с инфор-
 мацией о каждом пользователе, в частности сколько процессов и открытых
 файлов имеет пользователь. Если счетчик ссылок достигает значения нуль, то
 пользователь больше не имеет запущенных процессов и открытых файлов, в
 результате кэш уничтожается.
 • Вызывается функция unhash_process () для удаления процесса из хеш-табли-
 цы идентификаторов процессов pidhash и удаления задачи из списка задач.
 • Если задача была в состоянии трассировки (ptrace), то родительским для нее
 снова назначается первоначальный родительский процесс и задача удаляется
 из списка задач, которые находятся в состоянии трассировки (pirate) данным
 процессом.
 • В конце концов вызывается функция put_task_struct () для освобождения
 страниц памяти, содержащих стек ядра процесса и структуру thread_infо, a
 также освобождается слябовый кэш, содержащий структуру task_struct.
 На данном этапе дескриптор процесса, а также все ресурсы, которые принадле-
 жали только этому процессу, освобождены.
     
 

24.

 Если родительский процесс завершается до того, как завершаются вес его потом-
 ки, то должен существовать какой-нибудь механизм назначения нового родительского
 процесса для порожденных, иначе процессы, у которых нет родительского, навсегда
 останутся в состоянии зомби, что будет зря расходовать системную память. Решение
 этой проблемы было указано выше: новым родительским процессом становится или
 какой-либо один поток из группы потоков завершившегося родительского процес
 са, или процесс i n i t . При выполнении функции do_exit () вызывается функция
 notify_parent (), которая в свою очередь вызывает f o r g e t _ o r i g i n a l parent ()
 для осуществления переназначения родительского процесса (reparent), как показано
 ниже.
     struct task_struct *р, *reaper = father;
     struct list_head *list;
     if (father->exit_signal != -1)
     reaper = prev_thread(reaper);
     else
     reaper = child_reaper;
     if (reaper == father)
     reaper = child_reaper;
 Этот программный код присваивает переменной reaper указатель на другое зада
 ние в группе потоков данного процесса. Если в этой группе потоков нет другого за-
 дания, то переменной reaper присваивается значение переменной child_reaper,
 которая содержит указатель на процесс i n i t . Теперь, когда найден подходящий ро-
 дительский процесс, нужно найти все порожденные процессы и установить для них
 полученное значение родительского процесса, как показано ниже.
     list_for_each(list, &father->children) {
     р = list_entry(list, struct task_struct, sibling);
     reparent_thread(p, reaper, child_reaper);
     }
     list_for_each (list, sfather->ptrace__children) {
     p = list_entry(list, struct task:_struct, ptrace_list);
     reparent_thread(p, reaper, child_reaper);
     }
 В этом программном коде организован цикл по двум спискам: по списку порож-
 денных процессов child list и по списку порожденных процессов, находящихся в со-
 стоянии трассировки другими процессами ptraced child list. Основная причина, по
 которой используется именно два списка, достаточно интересна (эта новая особен-
 ность появилась в ядрах серии 2.6). Когда задача находится в состоянии ptrace, для
 нее временно назначается родительским тот процесс, который осуществляет от-
 ладку (debugging). Когда завершается истинный родительский процесс для такого
 задания, то для такой дочерней задачи также нужно осуществить переназначение
 родительского процесса. В ядрах более ранних версий это приводило к необходимо-
 сти организации цикла по всем заданиям системы для поиска порожденных процессов.
 Решение проблемы, как было указано выше, — это поддержка отдельного списка для
 порожденных процессов, которые находятся в состоянии трассировки, что уменыша-
 ет число операций поиска: происходит переход от поиска порожденных процессов
 по всему списку задач к поиску только по двум спискам с достаточно малым числом
 элементов.
 Когда для процессов переназначение родительского процесса прошло успешно,
 больше нет риска, что какой-либо процесс навсегда останется в состоянии зомби.
 Процесс Init периодически вызывает функцию wait () для всех своих порожден-
 ных процессов и, соответственно, удаляет все зомби-процессы, назначенные ему.
     
 

25.

 1. кооперативная
    процесс сам принимает решение о снятии полномочий на выполнение -
    передаче управления (yielding)
 2. вытесняющая (preemptive) - linux
    Процесс вытеснения процесса - preemption
    Малое время задержки - low latency
    Высокая производительность - throughput
 
 Период времени , в течение которого процесс может выполняться , называется квантом времени -
 timeslice, который может динамически меняться от 20 до 100 мс. 
    Когда истекает квант времени процесса, считается, что процесс потерял право
 выполняться. Процесс, у которого нет кванта времени, не имеет права выполнять-
 ся до того момента, пока все другие процессы не используют свой квант времени.
 Когда это случится, то у всех процессов будет значение оставшегося кванта времени,
 равное нулю. В этот момент значения квантов времени для всех процессов пересчи-
 тываются. В планировщике ОС Linux используется интересный алгоритм для обра-
 ботки ситуации, когда все процессы использовали свой квант времени. Этот алго-
 ритм будет рассмотрен далее.
 
 
 

26.

 В операционной системе Linux используется планировщик с динамическим управ-
 лением по приоритетам (dynamic priority-based), который основан на такой же идее.
 Основной принцип состоит в том, что вначале устанавливается некоторое началь-
 ное значение приоритета, а затем планировщик может динамически уменьшать или
 увеличивать это значение приоритета для выполнения своих задач. Например, ясно,
 что процесс, который тратит много времени на выполнение операций ввода-вывода,
 ограничен скоростью ввода-вывода. В операционной системе Linux такие процессы
 получают более высокое значение динамического приоритета. С другой стороны,
 процесс, который постоянно полностью использует свое значение кванта време-
 ни, — это процесс, ограниченный скоростью процессора. Такие процессы получают
 меньшее значение динамического приоритета.
  В ядре Linux используется два различных диапазона приоритетов. Первый — это
 параметр nice, который может принимать значения в диапазоне от -20 до 19, по
 умолчанию значение этого параметра равно 0. Большее значение параметра nice со-
 ответствует меньшему значению приоритета — необходимо быть более тактичным к
 другим процессам системы (пicе— англ. тактичный, хороший). Процессы с меньшим
 значением параметра nice (большим значением приоритета) выполняются раньше
 процессов с большим значением niie (меньшим приоритетом). Значение параметра
 nice позволяет также определить, насколько продолжительный квант времени полу-
 чит процесс. Процесс со значением параметра nice равным -20 получит квант вре-
 мени самой большой длительности, в то время как процесс со значением параметра
 nice равным 19 получит наименьшее значение кванта времени. Использование пара-
 метра nice — это стандартный способ указания приоритетов процессов для всех Unix-
 подобных операционных систем.
  Второй диапазон значений приоритетов— это приоритеты реального времени
 (real-time priority), которые будут рассмотрены ниже. По умолчанию диапазон зна-
 чений этого параметра лежит от 0 до 99. Все процессы реального времени имеют
 более высокий приоритет по сравнению с обычными процессами. В операционной
 системе Linux приоритеты реального времени реализованы в соответствии со стан-
 дартом POSIX. В большинстве современных Unix-систем они реализованы по анало-
 гичной схеме.
 
 

27.

    Программный код планировщика операционной системы Linux содержится в
 файле kernel / sched.c . 
 Новый планировщик разрабатывался для того, чтобы удовлетворять указанным ниже требованиям.
    • Должен быть реализован полноценный О(1) -планировщик. Любой алгоритм,
      использованный в новом планировщике, должен завершать свою работу за по-
      стоянный период времени, независимо от числа выполняющихся процессов и
      других обстоятельств.
    • Должна обеспечиваться хорошая масштабируемость для SMP-систем. Каждый
      процессор должен иметь свои индивидуальные элементы блокировок и свою
      индивидуальную очередь выполнения.
    • Должна быть реализована улучшенная SMP-привязка (SMP affinity). Задания,
      для выполнения на каждом процессоре многопроцессорной системы, должны
      быть распределены правильным образом, и, по возможности, выполнение этих
      задач должно продолжаться на одном и том же процессоре. Осуществлять ми-
      грацию заданий с одного процессора на другой необходимо только для умень-
      шения дисбаланса между размерами очередей выполнения всех процессоров.
    • Должна быть обеспечена хорошая производительность для интерактивных
      приложений. Даже при значительной загрузке система должна иметь хорошую
      реакцию и немедленно планировать выполнение интерактивных задач.
    • Должна быть обеспечена равнодоступность ресурсов (fairness). Ни один про-
      цесс не должен ощущать нехватку квантов времени за допустимый период.
      Кроме того, ни один процесс не должен получить недопустимо большое значе-
 •  Должна быть обеспечена оптимизация для наиболее распространенного слу-
   чая, когда число готовых к выполнению процессов равно 1-2, но в то же время
   должно обеспечиваться хорошее масштабирование и на случай большого числа
   процессоров, на которых выполняется большое число процессов.
 
 

28.

       Основная структура данных планировщика — это очередь выполнения (runqueue).
 Очередь выполнения определена в файле kernel/sched.c 3 в виде структуры
 s t r u c t runqueue. Она представляет собой список готовых к выполнению процес-
 сов для данного процессора.
      Для каждого процессора определяется своя очередь выполнения. Каждый гото-
 вый к выполнению процесс может находиться в одной и только в одной очереди
 выполнения. Кроме этого, очередь выполнения содержит информацию, необходи-
 мую для планирования выполнения на данном процессоре. Следовательно, очередь
 выполнения — это действительно основная структура данных планировщика для каж-
 дого процессора. 
     struct runqueue {
         spinlock_t lock; /* спин-блокировка для защиты этой очереди выполнения*/
         unsigned long nr_rinning; /* количество задач, готовых к выполнению */
         unsigned long nr_switches;     /* количество переключений контекста */
         unsigned long expired timestamp; /* время последнего обмена массивами*/
         unsigned long nr_uninterruptible; /* количество заданий в состоянии
                                             непрерываемого ожидания */
         ...
         };
 
    Поскольку очередь выполнения — это основная структура данных планировщи-
 ка, существует группа макросов, которые используются для доступа к определенным
 очередям выполнения. Макрос cpu_rq (processor) возвращает указатель на оче-
 редь выполнения, связанную с процессором, имеющим заданный номер. Аналогично
 макрос this_rq () возвращает указатель на очередь, связанную с текущим процессо-
 ром. И наконец, макрос task_rq(task) возвращает указатель на очередь, в которой
 находится соответствующее задание.
 
    Перед тем как производить манипуляции с очередью выполнения, ее необходимо
 заблокировать (блокировки подробно рассматриваются в главе 8, "Введение в синхро-
 низацию выполнения кода ядра"). Так как очередь выполнения уникальна для каждо-
 го процессора, процессору редко необходимо блокировать очередь выполнения дру-
 гого процессора (однако, как будет показано далее, такое все же иногда случается).
 Блокировка очереди выполнения позволяет запретить внесение любых изменений
 в структуру данных очереди, пока процессор, удерживающий блокировку, выполня-
 ет операции чтения или записи полей этой структуры. Наиболее часто встречается
 ситуация, когда необходимо заблокировать очередь выполнения, в которой выпол-
 няется текущее задание. В этом случае используются функции tapk_rq_lock () и
 task_rq_unlock(), как показано ниже.
    struct runqueue *rq;
    unsigned long flags;
    rq = task_rq_lock(task, &flags);
     /* здесь можно производить манипуляции с очередью выполнения */
    task_rq_unlock (rq, &flags);
 
 
 
 

29.

    Каждая очередь выполнения содержит два массива приоритетов (priority arrays): ак-
 тинный и истекший. Массивы приоритетов определены в файле k e r n e l / s c h e d . c
 в виде описания s t r u c t p r i o _ a r r a y . Массивы приоритетов — это структуры дан-
 ных, которые обеспечивают 0(1)-планирование. Каждый массив приоритетов содер-
 жит для каждого значения приоритета одну очередь процессов, готовых к выполне-
 нию. Массив приоритетов также содержит битовую маску приоритетов (priority bitmap),
 используемую для эффективного поиска готового к выполнению задания, у которого
 значение приоритета является наибольшим в системе.
    struct prio_array (
          int nr_active;                                 /* количество заданий */
          unsigned long bitmap[BITMAP_SIZE]; /* битовая маска приоритетов */
          struct list head queue[MAX_PRIO];/* очереди приоритетов */
     };
    Константа MAX_PRIO — это количество уровней приоритета в системе. По умолча-
 нию значение этой константы равно 140. Таким образом, для каждого значения при-
 оритета выделена одна структура s t r u c t l i s t _ h e a d . Константа BITMAP_SIZE — это
 размер массива переменных, каждый элемент которого имеет тип unsigned long.
 Каждый бит этого массива соответствует одному действительному значению приори-
 тета. В случае 140 уровней приоритетов и при использовании 32-разрядных машин-
 ных слов, значение константы BITMAP_SIZE равно 5. Таким образом, поле bitmap —
 это массив из пяти элементов, который имеет длину 160 бит.
     Все массивы приоритетов содержат поле b i t m a p , каждый бит этого поля соот-
 ветствует одному значению приоритета в системе. В самом начале значения всех
 битов равны 0. Когда задача с определенным приоритетом становится готовой к вы-
 полнению (то есть значение статуса этой задачи становится равным TASK_RUNNING),
 соответствующий этому приоритету бит поля b i t m a p устанавливается в значение 1.
 Например, если задача с приоритетом, равным 7, готова к выполнению, то устанав-
 ливается бит номер 7. Нахождение задания с самым высоким приоритетом в системе
 сводится только лишь к нахождению самого первого установленного бита в битовой
 маске. Так как количество приоритетов неизменно, то время, которое необходимо
 затратить на эту операцию поиска, постоянно и не зависит от количества процес-
 сов, выполняющихся в системе. Более того, для каждой поддерживаемой аппарат-
 ной платформы в ОС Linux должен быть реализован быстрый алгоритм поиска перво-
 го установленного бита (find first set) для проведения быстрого поиска в битовой маске.
 Эта функция называется s c h e d _ f i n d _ f i r s t _ b i t ( ) . Для многих аппаратных плат-
 форм существует машинная инструкция нахождения первого установленного бита в
 заданном машинном слове4. Для таких систем нахождение первого установленного
 бита является тривиальной операций и сводится к выполнению этой инструкции не-
 сколько раз.
    Каждый массив приоритетов также содержит массив очередей, представленных
 структурами struct list_head . Этот массив называется queue. Каждому значению
 приоритета соответствует своя очередь. Очереди реализованы в виде связанных
 списков, и каждому значению приоритета соответствует список всех процессов си-
 стемы, готовых к выполнению, имеющих это значение приоритета и находящихся
 в очереди выполнения данного процессора. Нахождение задания, которое будет вы-
 полняться следующим, является простой задачей и сводится к выбору следующего
 элемента из списка. Все задания с одинаковым приоритетом планируются на выпол-
 нение циклически.
 
 

30.

     Во многих операционных системах (включая и более старые версии ОС Linux)
 используется прямой метод для пересчета значения кванта времени каждого зада-
 ния, когда все эти значения достигают нуля.
  В планировщике применяется два массива приоритетов для
 каждого процессора: активный (active) и истекший (expired). Активный массив при-
 оритетов содержит очередь, в которую включены все задания соответствующей
 очереди выполнения, для которых еще не иссяк квант времени. Истекший массив
 приоритетов содержит все задания соответствующей очереди, которые израсходо-
 вали свой квант времени. Когда значение кванта времени для какого-либо задания
 становится равным нулю, то перед тем, как поместить это задание в истекший мас-
 сив приоритетов, для него вычисляется новое значение кванта времени. Пересчет
 значений кванта времени для всех процессов проводится с помощью перестановки
 активного и истекшего массивов местами. Так как на массивы ссылаются с помощью
 указателей, то переключение между ними будет выполняться так же быстро, как и
 перестановка двух указателей местами. Показанный ниже код выполняется в функ-
 ции schedule ().
    struct prio_array array = rq->active;
    if (!array->nr_active) {
          rq->active = rq->expired;
          rq->expired = array;
    }
    Упомянутая перестановка и есть ключевым, моментом O(1)-планировщика. Вместо
 того чтобы все время пересчитывать значение приоритета и кванта времени для
 каждого процесса, О(1)-планировщик выполняет простую двухшаговую перестанов-
 ку массивов. Такая реализация позволяет решить указанные выше проблемы.
 
 

31.

    Все действия по выбору следующего задания на исполнение и переключение на
 выполнение этого задания реализованы в виде функции schedule (). Эта функция
 вызывается явно кодом ядра при переходе в приостановленное состояние (sleep), a
 также в случае когда какое-либо задание вытесняется. Функция schedule () выпол-
 няется независимо каждым процессором. Следовательно, каждый процессор само-
 стоятельно принимает решение о том, какой процесс выполнять следующим.
    Функция schedule () достаточно проста, учитывая характер тех действий, кото-
 рые она выполняет. Следующий код позволяет определить задачу с наивысшим при-
 оритетом.
    struct task_struct *prev, *next;
    struct list_head *queue;
    struct prio_array *array;
    int idx;
    prev = current;
    array = rq->active;
    idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list__entry(queue->next, struct task struct, run_ist);
    Вначале осуществляется поиск в битовой маске активного массива приоритетов
 для нахождения номера самого первого установленного бита. Этот бит соответству-
 ет готовой к выполнению задаче с наивысшим приоритетом. Далее планировщик
 выбирает первое задание из списка заданий, которое соответствует найденному зна-
 чению приоритета. Это и есть задача с наивысшим значением приоритета в систе-
 ме, и эту задачу планировщик будет запускать на выполнение. 
    Если полученные значения переменных prev и next не равны друг другу, то для
 выполнения выбирается новое задание (next). При этом для переключения с за-
 дания, на которое указывает переменная prev, на задание, соответствующее пере-
 менной next, вызывается функция context_switch (), зависящая от аппаратной
 платформы. Переключение контекста будет рассмотрено в одном из следующих раз-
 делов.
  
  
 

32.

      Процессы имеют начальное значение приоритета, которое называется nice. Это
 значение может лежать в диапазоне от -20 до 19, по умолчанию используется зна-
 чение 0. Значение 19 соответствует наиболее низкому приоритету, а значение -20 —
 наиболее высокому. Значение параметра nice хранится в поле s t a t i c _ p r i o струк-
 туры t a s k _ s t r u c t процесса. Это значение называется статическим приоритетом,
 потому что оно не изменяется планировщиком и остается таким, каким его указал
 пользователь. Планировщик свои решения основывает на динамическом приорите-
 те, которое хранится в поле prio. Динамический приоритет вычисляется как функ-
 ция статического приоритета и интерактивности задания.
     Функция effective_prio () возвращает значение динамического приоритета за-
 дачи. Эта функция исходит из значения параметра пicе для данной задачи и вычисля-
 ет для этого значения надбавку или штраф в диапазоне от -5 до 5, в зависимости от
 интерактивности задачи. Например, задание с высокой интерактивностью, которое
 имеет значение параметра nice, равное 10, может иметь динамический приоритет,
 равный 5. И наоборот, программа со значением параметра nice, равным 10, которая
 достаточно активно использует процессор, может иметь динамический приоритет,
 равный 12. Задачи, которые обладают умеренной интерактивностью, не получают
 ни надбавки, ни штрафа, и их динамический приоритет совпадает со значением па-
 раметра nice.
   В ядре Linux предусмотрен изменяемый показатель того, 
 как соотносится время, которое процесс проводит в приостановлен-
 ном состоянии, со временем, которое процесс проводит в состоянии готовности
 к выполнению. Значение этого показателя хранится в поле sleep_avg структуры
 t a s k _ s t r u c t . Диапазон значений этого показателя лежит от нуля до значения
 MAX_SLEEP_AVG, которое по умолчанию равно 10 мс. Когда задача становится гото-
 вой к выполнению после приостановленного состояния, значение поля sleep_avg
 увеличивается на значение времени, которое процесс провел в приостановленном
 состоянии, пока значение sleep_avg не достигнет MAX_SLEEP_AVG. Когда задача
 выполняется, то в течение каждого импульса таймера (timer tick) значение этой пе-
 ременной уменьшается, пока оно не достигнет значения 0.
 
  Тип задания                   Значение параметра nice        Продолжительность кванта времени
  Вновь созданное            То же, что и у родителя         Половина от родителя
  Минимальный приоритет       +19                          5 мс (MIN_TIMESUCE)
  Приоритет по умолчанию       0=100 мс                    (DEF_TIMESLICE)
  Максимальный приоритет      -20                           800 мс (MAX_TIMESLICE)
 
 

33.

     Приостановленное состояние задачи (состояние ожидания, заблокированное
 состояние, sleeping, blocked) представляет собой специальное состояние задачи, в ко-
 тором задание не выполняется. Это является очень важным, так как в противном
 случае планировщик выбирал бы на выполнение задания, которые не "хотят" вы-
 полняться, или, хуже того, состояние ожидания должно было бы быть реализовано
 в виде цикла, занимающего время процессора. Задачи могут переходить в приоста-
 новленное состояние по нескольким причинам, но в любом случае— в ожидании
 наступления некоторого события. Событием может быть ожидание наступления
 некоторого момента времени, ожидание следующей порции данных при файловом
 вводе-ныводе или другое событие в аппаратном обеспечении. Задача также может
 переходить в приостановленное состояние непроизвольным образом, когда она
 пытается захватить семафор в режиме ядра (эта ситуация рассмотрена в главе 9,
 "Средства синхронизации в ядре"). Обычная причина перехода в приостановленное
 состояние — это выполнение операций файлового ввода-вывода, например задание
 вызывает функцию r e a d () для файла, который необходимо считать с диска. Еще
 один пример— задача может ожидать на ввод данных с клавиатуры. В любом случае
 ядро ведет себя одинаково: задача помечает себя как находящуюся в приостанов-
 ленном состоянии, помещает себя в очередь ожидания (wail queue), удаляет себя из
 очереди выполнения и вызывает функцию s c h e d u l e d для выбора нового процесса
 на выполнение. Возврат к выполнению (wake up) происходит в обратном порядке:
 задача помечает себя как готовую к выполнению, удаляет себя из очереди ожидания
 и помепгает себя в очередь выполнения.
     Как указывалось в предыдущей главе, с приостановленным состоянием связаны два
 значения поля состояния процесса: TASK_INTERRUPTIBLE и TASK_UNINTERRUPTIBLE.
 Они отличаются только тем, что в состоянии TASK_UNINTERRUPTIBLE задача игно-
 рирует сигналы, в то время как задачи в состоянии TASK_INTERRUPTIBLE возвраща-
 ются к выполнению преждевременно и обрабатывают пришедший сигнал. Оба типа
 задач, находящихся в приостановленном состоянии, помещаются в очередь ожида-
 ния, ожидают наступления некоторого события и не готовы к выполнению.
    Приостановленное состояние обрабатывается с помощью очередей ожидания
 (wait queue). Очередь ожидания— это просто список процессов, которые ожидают
 наступления некоторого события. Очереди ожидания в ядре представляются с по-
 мощью типа данных wait_queue_head_t. Они могут быть созданы статически с по-
 мощью макроса DECLARE_WAIT_QUEUE_HEAD () или выделены динамически с после-
 дующей инициализацией с помощью функции i n i t _ w a i t q u e u e _ h e a d (). Процессы
 помещают себя в очередь ожидания и устанавливают себя в приостановленное со-
 стояние. Когда происходит событие, связанное с очередью ожидания, процессы, на-
 ходящиеся в этой очереди, возвращаются к выполнению. Важно реализовать пере-
 ход в приостановленное состояние и возврат к выполнению правильно, так чтобы
 избежать конкуренции за ресурсы (race).
 
 

34.

     Как уже рассказывалось ранее, планировщик операционной системы Linux ре-
 ализует отдельные очереди выполнения и блокировки для каждого процессора в
 симметричной многопроцессорной системе. Это означает, что каждый процессор
 поддерживает свой список процессов и выполняет алгоритм планирования только
 для заданий из этого списка. Система планирования, таким образом, является уни-
 кальной для каждого процессора. Тогда каким же образом планировщик обеспечива-
 ет какую-либо глобальную стратегию планирования для многопроцессорных систем?
 Что будет, если нарушится балансировка очередей выполнения, скажем, в очереди
 выполнения одного процессора будет находиться пять процессов, а в очереди дру-
 гого — всего один? Решение этой проблемы выполняется системой балансировки на-
 грузки, которая работает с целью гарантировать, что все очереди выполнения будут
 сбалансированными. Система балансировки нагрузки сравнивает очередь выполне-
 ния текущего процессора с другими очередями выполнения в системе.
     Система балансировки нагрузки реализована в файле kernel / sched.с в виде
 функции load_balance (). Эта функция вызывается в двух случаях. Она вызывается
 функцией schedule (), когда текущая очередь выполнения пуста. Она также вызы-
 вается по таймеру с периодом в 1 мс, когда система не загружена, и каждые 200 мс
 в другом случае. В однопроцессорной системе функция load_balance() не вызыва-
 ется никогда, в действительности она даже не компилируется в исполняемый образ
 ядра, питому что в системе только одна очередь выполнения и никакой балансиров-
 ки не нужно.
  
 

35.

    Переключение контекста — это переключение от одной, готовой к выпол-
 нению задачи к другой. Это переключение производится с помощью функции
 context_switch(), определенной в файле kernel/sched.с. Данная функция вы-
 зывается функцией schedule (), когда новый процесс выбирается для выполнения.
 При этом выполняются следующие шаги.
    • Вызывается функция switch_mm (), которая определена в файле include/asm/
      mmu_context.h и предназначена для переключения от виртуальной памяти
      старого процесса к виртуальной памяти нового процесса.
    • Вызывается функция switch_to () , определенная в файле include/asm/
      system.h, для переключения от состояния процессора предыдущего процесса
      к состоянию процессора нового процесса. Эта процедура включает восстанов-
      ление информации стека ядра и регистров процессора.
    Ядро должно иметь информацию о том, когда вызывать функцию schedule ().
 Если эта функция будет вызываться только тогда, когда программный код вызывает
 ее явно, то пользовательские программы могут выполняться неопределенное время.
 Поэтому ядро поддерживает флаг need_resched для того, чтобы сигнализировать,
 необходимо ли вызывать функцию schedule () (табл. 4.2). Этот флаг устанавлива-
 ется функцией schediiler_tick (), когда процесс истрачивает свой квант времени,
 и функцией try_to_wake_up (), когда процесс с приоритетом более высоким, чем
 у текущего процесса, возвращается к выполнению. Ядро проверяет значение этого
 флага, и если он установлен, то вызывается функция schedule () для переключения
 на новый процесс. Этот флаг является сообщением ядру о том, что планировщик
 должен быть активизирован по возможности раньше, потому что другой процесс
 должен начать выполнение.
 
 

36.

    Вытеснение пространства пользователя (user preemption) происходит в тот мо-
 мент, когда ядро собирается возвратить управление режиму пользователя, при этом
 устанавливается флаг need_resched и, соответственно, активизируется планиров-
 щик. Когда ядро возвращает управление в пространство пользователя, то оно нахо-
 дится в безопасном и "спокойном" состоянии. Другими словами, если продолжение
 выполнения текущего задания является безопасным, то безопасным будет также и
 выбор нового задания для выполнения. Поэтому когда ядро готовится возвратить
 управление в режим пользователя или при возврате из прерывания или после си-
 стемного вызова, происходит проверка флага need_resched. Если этот флаг уста-
 новлен, то активизируется планировщик И выбирает новый, более подходящий
 процесс для исполнения. Как процедура возврата из прерывания, так и процедура
 возврата из системного вызова являются зависимыми от аппаратной платформы и
 обычно реализуются на языке ассемблера в файле entry.S (этот файл, кроме кода
 входа в режим ядра, также содержит и код выхода из режима ядра). Если коротко,
 то вытеснение пространства пользователя может произойти в следующих случаях.
    • При возврате в пространство пользователя из системного вызова.
    • При возврате в пространство пользователя из обработчика прерывания.
 
    Ядро операционной системы Linux, в отличие от ядер большинства вариантов
 ОС Unix, является полностью преемптивным (вытесняемым, preemptible). В непре-
 емптивных ядрах код ядра выполняется до завершения. Иными словами, планиров-
 щик не может осуществить планирование для выполнения другого задания, пока
 какое-либо задание выполняется в пространстве ядра — код ядра планируется на вы-
 полнение кооперативно, а не посредством вытеснения. Код ядра выполняется до тех
 пор, пока он не завершится (возвратит управление в пространство пользователя)
 или пока явно не заблокируется. С появлением серии ядер 2.6, ядро Linux стало пре-
 емптивным: теперь есть возможность вытеснить задание в любой момент, конечно,
 пока ядро находится в состоянии, когда безопасно производить перепланирование
 выполнения.
    В таком случае когда же безопасно производить перепланирование? Ядро способ-
 но вытеснить задание, работающее в пространстве ядра, когда это задание не удер-
 живает блокировку. Иными словами, блокировки используются в качестве маркеров
 тех областей, в которые задание не может быть вытеснено. Ядро рассчитано на мно-
 гопроцессорность (SMP-safe), поэтому если блокировка не удерживается, то код ядра
 является реентерабельным и его вытеснять безопасно.
 
 

37.

      Операционная система Linux обеспечивает две стратегии планирования в режи-
 ме реального времени (real-lime): SCHED_FIFO и SCHED_RR. Стратегия планирования
 SCHED_OTHER является обычной стратегией планирования, т.е. стратегий планирова-
 ния не в режиме реального времени. Стратегия SCHED_FIFO обеспечивает простой
 алгоритм планирования по идеологии "первым вошел — первым обслужен" (first-in
 first-out, FIFO) без квантов времени. Готовое к выполнению задание со стратегией
 планирования SCHED_FIFO всегда будет планироваться на выполнение перед всеми
 заданиями со стратегией планирования SCHED_OTHER. Когда задание со стратегией
 SCHED_FIFO становится готовым к выполнению, то оно будет продолжать выпол-
 няться до тех пор, пока не заблокируется или пока явно не отдаст управление. Две
 или более задач с одинаковым приоритетом, имеющие стратегию планирования
 SCHED_FIFO, будут планироваться на выполнение по круговому алгоритму (round-
 robin). Если задание, имеющее стратегию планирования SCHED_FIFO, является гото-
 вым к выполнению, то все задачи с более низким приоритетом не могут выполнять-
 ся до тех пор, пока это задание не завершится.
    Стратегия SCHED_RR аналогична стратегии SCHED_FIFO, за исключением того,
 что процесс может выполняться только до тех пор, пока не израсходует предопре-
 деленный ему квант времени. Таким образом, стратегия SCHED_RR — это стратегия
 SCHED_FIFO с квантами времени, т.е. круговой алгоритм планирования (round-robin)
 реального времени. Когда истекает квант времени процесса со стратегией планиро-
 вания SCHED_RR, то другие процессы с таким же приоритетом планируются по кру-
 говому алгоритму. Квант времени используется только для того, чтобы переплани-
 ровать выполнение заданий с таким же приоритетом. Так же как в случае стратегии
 SCHED_FIFO, процесс с более высоким приоритетом сразу же вытесняет процессы с
 более низким приоритетом, а процесс с более низким приоритетом никогда не смо-
 жет вытеснить процесс со стратегией планирования SCHED_RR, даже если у послед-
 него истек квант времени.
    Стратегии планирования реального времени в операционной системе Linux обе-
 спечивают так называемый мягкий режим реального времени (soft real-time). Мягкий
 режим реального времени обозначает, что ядро пытается планировать выполнение
 пользовательских программ в границах допустимых временных сроков, но не всегда
 гарантирует выполнение этой задачи. В противоположность этому операционные
 системы с жестким режимом реального времени (hard real-time) всегда гарантируют
 выполнение всех требований по планированию выполнения процессов в заданных
 пределах. 
    Приоритеты реального времени лежат в диапазоне от 1 до MAX_RT_PRIO минус 1,
 По умолчанию значение константы MAX_RT_PRIO равно 100, поэтому диапазон зна-
 чений приоритетов реального времени по умолчанию составляет от 1 до 99. Это
 пространство приоритетов объединяется с пространством значений параметра nice
 для стратегии планирования SCHED_OTHER, которое соответствует диапазону прио-
 ритетов от значения MAX_RT_PRIO до значения (MAX_RT_PRIO+40). По умолчанию
 это означает, что диапазон значений параметра nice от -20 до +19 взаимно однознач-
 но отображается в диапазон значений приоритетов от 100 до 139.
 
 
 

38.

     Операционная система Linux предоставляет семейство системных вызовов для
 управления параметрами планировщика. Эти системные вызовы позволяют мани-
 пулировать приоритетом процесса, стратегией планирования и процессорной при-
 вязкой, а также предоставляют механизм, с помощью которого можно явно передать
 процессор (yield) в использование другим заданиям.
     nice ()                    Установить значение параметра nice
     schedsetscheduler     ()  Установить стратегию планирования
     sched_getscheduler    ()   Получить стратегию планирования
     sched_setparam ()         Установить значение приоритета реального времени
     sched_getparam ()         Получить значение приоритета реального времени
     sched_get_priority_max () Получить максимальное значение приоритета реального времени
     Eched_get_priority_min () Получить минимальное значение приоритета реального времени
     sched_rr_get_interval ()   Получить продолжительность кванта времени
     sched_setaffinity()       Установить процессорную привязку
     sched_getaffinity    ()   Получить процессорную привязку
     sched_yield ()            Временно передать процессор другим заданиям
 
 
 
 

39.

     Системные вызовы (часто называемые syscall в ОС Linux) обычно реализуются в
 виде вызова функции. Для них могут быть определены один или более аргументов
 (inputs), которые могут приводить к тем или иным побочным эффектам 3 , например
 к записи данных в файл или к копированию некоторых данных в область памяти, на
 которую указывает переданный указатель. Системные вызовы также имеют возвра-
 щаемое значение типа long 4 , которое указывает на успешность выполнения опера-
 ции или на возникшие ошибки. Обычно, но не всегда, возвращение отрицательного
 значения указывает на то, что произошла ошибка. Возвращение нулевого значения
 обычно (но не всегда) указывает на успешность выполнения операции. Системные
 вызовы ОС Unix в случае ошибки записывают специальный код ошибки в глобаль-
 ную переменную errno . Значение этой переменной может быть переведено в удобо-
 читаемую формy с помощью библиотечной функции perror ().
    Каждому системному вызову операционной системы Linux присваивается номер
 системного вызова (syscall number). Этот уникальный номер используется для обращения
 к определенному системному вызову. Когда процесс выполняет системный вызов из
 пространства пользователя, процесс не обращается к системному вызову по имени.
    Номер системного вызова является важным атрибутом. Однажды назначенный
 номер не должен меняться никогда, иначе это нарушит работу уже скомпилирован-
 ных прикладных программ. Если системный вызов удаляется, то соответствующий
 номер не может использоваться повторно. В операционной системе Linux предусмо-
 трен так называемый "не реализованный" ("not implemented") системный вызов —
 функция sys_ni_syscall(), которая не делает ничего, кроме того, что возвращает
 значение, равное -ENOSYS, — код ошибки, соответствующий неправильному систем-
 ному вызову. Эта функция служит для "затыкания дыр" в случае такого редкого со-
 бытии, как удаление системного вызова.
    Ядро поддерживает список зарегистрированных системных вызовов в таблице
 системных вызовов. Эта таблица хранится в памяти, на которую указывает перемен-
 ная sys_call_table . Данная таблица зависит от аппаратной платформы и обычно
 определяется в файле entry.S . В таблице системных вызовов каждому уникальному
 номеру системного вызова назначается существующая функция syscall .
 
 

40.

       Таким механизмом, который может подать сигнал ядру, является программное
 прерывание: создается исключительная ситуация (exception) и система переключа-
 ется в режим ядра для выполнения обработчика этой исключительной ситуации.
 Обработчик исключительной ситуации в данном случае и является обработчиком си-
 стемного вызова (system call handler). Для аппаратной платформы х8б это программ-
 ное прерывание определено как машинная инструкция i n t $0x80. Она приводит
 в действие механизм переключения в режим ядра и выполнение вектора исключи-
 тельной ситуации с номером 128, который является обработчиком системных вы-
 зовов. Обработчик системных вызовов— это функция с очень подходящим именем
 system_call (). Данная функция зависима от аппаратной платформы и определена
 в файле entry.S . В новых процессорах появилась такая новая функция, как sysent-
 er. Эта функция обеспечивает более быстрый и специализированный способ входа в
 ядро для выполнения системного вызова, чем использование инструкции программ-
 ного прерывания — i n t . Поддержка такой функции была быстро добавлена в ядро.
 Независимо от того, каким образом выполняется системный вызов, основным явля-
 ется то, что пространство пользователя вызывает исключительную ситуацию, или
 прерывание, чтобы вызвать переход в ядро.
 
 

41.

     ОС Linux предоставляет набор макросов-оболочек для доступа к си-
 стемным вызовам. Они позволяют установить содержимое регистров и выполнить
 машинную инструкцию int 50x80. Эти макросы имеют имя syscalln ( ) , где п —
 число от нуля до шести. Это число соответствует числу параметров, которые долж-
 ны передаваться в системный вызов, так как макросу необходима информация о том,
 сколько ожидается параметров, и соответственно, нужно записать эти параметры в
 регистры процессора. Например, рассмотрим системный вызов open (), который
 определен следующим образом.
    long open(const char "filename, int flags, int model
    Макрос для вызова этой системной функции будет выглядеть так.
    #define NR_open 5
    _syscall3(long, NR_open, const char *, filename, int, flags, int, mode)
 
    После этого приложение может просто вызывать функцию open ( ) .
    Каждый макрос принимает 2 + 2*n параметров. Первый параметр соответствует
 типу возвращаемого значения системного вызова. Второй параметр — имя систем-
 ного вызова. После этого следуют тип и имя каждого параметра в том же поряд-
 
 

42.

     Функция, которую выполняет ядро в ответ на определенное прерывание, называ-
 ется обработчиком прерывания (interrupt handler) и л и подпрограммой обслуживания преры-
 вания (interrupt service routine). Каждому устройству, которое генерирует прерывания,
 соответствует свой обработчик прерывания. Например, одна функция обрабатывает
 прерывание от системного таймера, а другая — прерывания, сгенерированные клави-
 атурой. Обработчик прерывания для какого-либо устройства является частью драйве-
 ра этого устройства — кода ядра, который управляет устройством.
     В операционной системе Linux обработчики прерываний — это обычные функ-
 ции, написанные на языке программирования С. Они должны соответствовать
 определенному прототипу, чтобы ядро могло стандартным образом принимать ин-
 формацию об обработчике, а в остальном— это обычные функции. Единственное,
 что отличает обработчики прерываний от других функций ядра, — это то, что они
 вызываются ядром в ответ на прерывание и выполняются в специальном контексте,
 именуемом контекстом прерывания (interrupt context), который будет рассмотрен да-
 лее.
   Ясно, что два указанных требования о том, что обработчик прерывания должен
 выполняться быстро и, в дополнение к этому, выполнять много работы, являются
 противоречивыми. В связи с конфликтными требованиями, обработчик прерываний
 разбивается на две части, или половины. Обработчик прерывания является верхней
 половиной (top half)— он выполняется сразу после приема прерывания и выполняет
 работу, критичную к задержкам во времени, такую как отправка подтверждения о
 получении прерывания или сброс аппаратного устройства. Работа, которую можно
 выполнить позже, откладывается до выполнения нижней (или основной) половины
 (bottom half). Нижняя половина обрабатывается позже, в более удобное время, когда
 все прерывания разрешены. Достаточно часто нижняя половина выполняется сразу
 же после возврата из обработчика прерывания.
 
 

43.

      Ответственность за обработчики прерываний лежит на драйверах устройств, ко-
 торые управляют определенным типом аппаратного обеспечения. С каждым устрой-
 ством связан драйвер, и если устройство использует прерывания (а большинство ис-
 пользует), то драйвер должен выполнить регистрацию обработчика прерывания.
     Драйвер может зарегистрировать обработчик прерывания для обработки задан-
 ной линии с помощью следующей функции.
     /* request_irq: выделить заданную линию прерывания */
     int request_irq(unsigned int irq,
                      irqreturn_t (*handler)(int, void *, struct pt_regs *),
                      unsigned long irqflags,
                      const char * devname,
                      void *dev_id);
     Первый параметр, irq, указывает назначаемый номер прерывания. Для некото-
 рых устройств, таких как, например, обычные устройства персонального компьюте-
 ра, таймер и клавиатура, это значение, как правило, жестко закреплено. Для боль-
 шинства других устройств это значение определяется путем проверки (probing) или
 другим динамическим способом.
     Второй параметр, handler, — это указатель на функцию обработчика прерыва-
 ния, которая обслуживает данное прерывание. Эта функция вызывается, когда в
 операционную систему приходит прерывание. Следует обратить внимание на специ-
 фический прототип функции-обработчика. Она принимает три параметра и возвра-
 щает значение типа irqreturn_t . Ниже в этой главе мы более подробно обсудим
 эту функцию.
    Третий параметр, irqflags , может быть равным нулю или содержать битовую
 маску с одним или несколькими следующими флагами.
    Четвертый параметр, devname, — это ASCII-строка, которая описывает, какое
 устройство связано с прерыванием. Например, для прерывания клавиатуры персо-
 нального компьютера это значение равно "keyboard". Текстовые имена устройств
 применяются для взаимодействия с пользователями с помощью интерфейсов
 /proc/irq и /proc/interrupts, которые вскоре будут рассмотрены.
    Пятый параметр, d e v i d , в основном, применяется для совместно используемых
 линий запросов на прерывания. Когда обработчик прерывания освобождается (опи-
 сано ниже), параметр dev_id обеспечивает уникальный идентификатор (cookie), ко-
 торый позволяет удалять только необходимый обработчик линии прерывания. 
    В случае успеха функция request_irq () возвращает нуль. Возврат ненулевого
 значения указывает на то, что произошла ошибка и указанный обработчик преры-
 вания не был зарегистрирован. Наиболее часто встречающийся код ошибки — это
 значение -EBUSY, что указывает на то, что данная линия запроса на прерывание
 уже занята (и или при текущем вызове, или при первом вызове не был указан флаг
 SA_SHIRQ).
  Для освобождения линии прерывания необходимо вызвать функцию
     void free_irq(unsigned int irq, void *dev_id)
 
 

44.

      Следующее описание является типичным для обработчика прерывания.
     static irqreturn_t intr_handler (int irq, void *dev_id, struct pt_regs *regs)
     Заметим, что оно должно соответствовать аргументу, который передается в функ-
 цию request_irq (). Первый параметр, irq, — это численное значение номера пре-
 рывания, которое обслуживается обработчиком. Сейчас этот параметр практически
 не используется, кроме разве что при печати сообщений. Для версий ядра, меньших
 2.0, не было параметра dev_id, поэтому параметр i r q использовался, чтобы разли-
 чать устройства, которые обслуживаются одним драйвером, и поэтому используют
 один и тот же обработчик прерываний (как пример можно рассмотреть компьютер
 с несколькими контроллерами жесткого диска одного типа).
     Второй параметр, dev_id, — это указатель, равный значению, которое было пе-
 редано в функцию request_irq () при регистрации обработчика прерывания. Если
 значение этого параметра является уникальным, что необходимо для поддержки со-
 вместно используемых прерываний, то его можно использовать как идентификатор
 для того, чтобы отличать друг от друга различные устройства, которые потенциаль-
 но могут использовать один обработчик. В связи с тем, что структура (контекст)
 устройства (device structure) является как уникальной, так и, возможно, полезной
 при использовании в обработчике, обычно в качестве параметра dev_id передают
 указатель на эту структуру.
 
 

45.

       Файловая система procfs— это виртуальная файловая система, которая существует
 только в памяти ядра и обычно монтируется на каталог /ргос. Чтение или запись
 файлов на файловой системе procfs приводит к вызовам функций ядра, которые
 имитируют чтение или запись обычных файлов. Важный пример— это файл /ргос/
 i n t e r r u p t s , который содержит статистику, связанную с прерываниями в системе,
 Ниже приведен пример вывода из этого файла на однопроцессорном персональном
 компьютере.
               CPU0
        0: 3602371         XT-PIC    timer
        1: 3048            XT-PIC     i8042
        2: 0               XT-PIC    cascade
    Первая колонка содержит названия линий прерывания. В показанной системе
 присутствуют линии прерываний с номерами 0-2, 4, 5, 12 и 15. Линии, для которых
 не инсталлирован обработчик, не показываются. Вторая колонка — это количество
 запросов на прерывания с данным номером. В действительности такая колонка яв-
 ляется отдельной для каждого процессора, но в данной машине только один про-
 цессор.
    Как легко видеть, обработчик прерываний таймера получил 3.602.3712 за-
 прос на прерывание, в то время как обработчик прерываний звукового адаптера
 (EMU10K1) не получил ни одного прерывания (это говорит о том, что он не исполь-
 зовался с того момента, как машина была загружена). Третья колонка— это кон-
 троллер прерываний, который обслуживает данное прерывание. Значение XT-PIC
 соответствует программируемому контроллеру прерываний PC (PC programmable
 interrupt controller). Для систем с устройством I/О APIC для большинства преры-
 ваний в качестве контроллера прерываний будет указано значение IO-APIC-level
 или IO-APIC-edge. И наконец, последняя колонка— это устройство, которое связа-
 но с прерыванием. Имя устройства указывается в параметре dev_name при вызове
 функции request_irq () , как обсуждалось ранее. Если прерывание используется со-
 вместно, как в случае прерывания номер 4 в этом примере, то перечисляются все
 устройства, зарегистрированные на данной линии прерывания.
 
 

46

    Ветки кода, которые получают доступ к совместно используемыми данным и ма-
 нипулируют ими, называются критическими участками (critical region). Обычно не-
 безопасно нескольким потокам выполнения одновременно обращаться к одному и
 тому же ресурсу.
  Если два потока выполнения одновременно
 находятся в критическом участке, то это— ошибка в программе. Если такое вдруг
 случается, то такая ситуация называется состоянием, конкуренции за ресурс (состояние
 "гонок", race condition).
  Обеспечение гарантии того, что конкуренции не будет и, следовательно, 
 что состояний конкуренции за ресурсы возникнуть не может, называется синхронизацией.
  Тип параллелизма, когда два события происходят не одновременно, а накладываются
 друг на друга, как будто они происходят в один момент времени, называется псевдо-
 параллелизмом (pseudo-concurrency).
    На машине с симметричной многопроцессорностью два процесса могут действи-
 тельно выполнять критические участки в один и тот же момент времени. Это назы-
 вается истинным, параллелизмом (true concurrency). 
 
  В ядре причины параллельного выполнения кода следующие.
    • Прерывания. Прерывания могут возникать асинхронно, практически в любой
      момент времени, прерывая код, который выполняется в данный момент.
    • Отлаженные прерывания и тасклеты. Ядро может выполнять обработчики softirq
      и тасклеты практически в любой момент времени и прерывать код, который
      выполняется в данный момент времени.
    • Преемптивностъ ядра. Так как ядро является вытесняемым, то одно задание, ко-
      торое работает в режиме ядра, может вытеснить другое задание, тоже работа-
      ющее в пространстве ядра.
     • Переход в состояние ожидания и синхронизация с пространством пользователя.
     Задание, работающее в пространстве ядра, может переходить в состояние ожида-
     ния, что вызывает активизацию планировщика и выполнение нового процесса.
     • Симметричная многопроцессорность. Два или больше процессоров могут выпол-
     нять код в один и тот же момент времени.
    Код, который безопасно выполнять параллельно с обработчиком прерывания, на-
 зывается безопасным при прерываниях (iterrupt-safe). Код, который содержит защиту
 от конкурентного доступа к ресурсам при симметричной многопроцессорной обра-
 ботке, называется безопасным при SMP-обработке (SMP-safe). 
 Код, который имеет защиту от конкурентного доступа к ресурсам при вытеснении кода ядра, 
 называется безопасным при вытеснения (preempt-safe). 
    Взаимоблокировка (тупиковая ситуация, deadlock) — это состояние, при котором
 каждый поток ожидает на освобождение одного из ресурсов, а все ресурсы при этом
 захвачены. Потоки будут ожидать друг друга, и они никогда не смогут освободить
 захваченные ресурсы. Поэтому ни один из потоков не сможет продолжать выполне-
 ние, что означает наличие взаимоблокировки.
 
 
 
 
 

47

    Атомарные операции (atomic operations) предоставляют инструкции, которые
 выполняются атомарно, — т.е. не прерываясь. Так же как и атом вначале считался
 неделимой частицей, атомарные операции являются неделимыми инструкциями.
 Например, как было показано в предыдущей главе, операция атомарного инкремен-
 та позволяет считывать из памяти и увеличивать на единицу значение переменной
 за один неделимый и непрерывный шаг. В отличие от состояния конкуренции за ре-
 сурс, которая обсуждалась в предыдущей главе, результат выполнения такой опера-
 ции всегда один и тот же, например, как показано в следующем примере (допустим,
 что значение переменной i вначале равно 7).
    Поток 1                        Поток 2
    инкремент i (7->8)             инкремент i (8->9)
    Результирующее значение 9 — правильное. Параллельное выполнение двух атомар-
 ных операций с одной и той же переменной невозможно никогда. Таким образом, для
 такой операции инкремента состояние конкуренции за ресурс возникнуть не может.
    Ядро предоставляет два набора интерфейсов для выполнения атомарных опе-
 раций: один — для работы с целыми числами, а другой — для работы с отдельными
 битами. Эти интерфейсы реализованы для всех аппаратных платформ, которые под-
 держиваются операционной системой Linux. 
    Средства выполнения атомарных операций с целыми числами работают с типом
 данных atomic_t . Вместо того, чтобы использовать функции, которые работают
 непосредственно с типом данных int языка С, по ряду причин используется спе-
 циальный тип данных. Во-первых, функции, которые выполняют атомарные опера-
 ции, принимают только аргументы типа atomic_t , это гарантирует, что атомарные
 операции выполняются только с данными этого специального типа. В то же время
 это также гарантирует, что данные этого типа не смогут передаваться в другие функ-
 ции, которые не выполняют атомарных операций. Действительно, ничего хорошего
 не будет от таких атомарных операций, которые иногда атомарные, а иногда— нет.
 Следующий момент— использование типа atomic_t позволяет гарантировать, что
 компилятор (по ошибке, но для повышения эффективности) не будет оптимизи-
 ровать операции обращения к атомарным переменным. Важно, чтобы атомарные
 операции получали правильное значение адреса переменной в памяти, а не адреса
 временных копий. И наконец, за типом atomic_t скрываются различия между реа-
 лизациями для различных аппаратных платформ.
      Наиболее частое использование атомарных целочисленных операций — это
 инкремент счетчиков. Защищать один счетчик с помощью сложной системы бло-
 кировок — это глупо, поэтому разработчики используют вызовы atomic_int () и
 atomic_d e c ( ) , которые значительно быстрее. Еще одно использование атомарных
 целочисленных операций — это атомарное выполнение операции с проверкой ре-
 зультата. Наиболее распространенный пример — это атомарные декремент и про-
 верка результата, с помощью функции
       int atomic_dec_and_test(atomic_t *v)
 
 

48

     Наиболее часто используемый тип блокировки в ядре Linux - это спин-блокировки
 (spin lock). Спин-блокировка — это блокировка, которую может удерживать не более
 чем один поток выполнения. Если поток выполнения пытается захватить блокиров-
 ку, которая находится в состоянии конфликта (contended), т.е. уже захвачена, поток
 начинает выполнять постоянную циклическую проверку (busy loop) — "вращаться"
 (spin), ожидая на освобождение блокировки. Если блокировка не находится в со-
 стоянии конфликта при захвате, то поток может сразу же захватить блокировку и
 продолжить выполнение. Циклическая проверка предотвращает ситуацию, в кото-
 рой более одного потока одновременно может находиться в критическом участке.
 Следует заметить, что одна и та же блокировка может использоваться в нескольких
 разных местах кода, и при этом всегда будет гарантирована защита и синхронизация
 при доступе, например, к какой-нибудь структуре данных.
  Рассмотрим пример использования спин-блокировок.
    spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
    spin_lock (&mr_lock);
    /* критический участок ... */
    spin_unlock(&mr_lock);
 
    Ядро предоставляет интерфейс, который удобным способом позволяет запретить
 прерывания и захватить блокировку. Использовать его можно следующим образом.
    spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
    unsigned long flags;
    spin_lock_irqsave(&mr_lock,            flags);
    /* критический участок ... */
    spin_unlock_irqre_store(&rnr_lock,             flags);
    Подпрограмма spin_lock_irqsave () сохраняет текущее состояние системы
 прерываний, запрещает прерывания и захватывает указанную блокировку. Функция
 spin_unlock_irqrestore (), наоборот, освобождает указанную блокировку и вос-
 станавливает предыдущее состояние системы прерываний. Таким образом, если пре-
 рывания были запрещены, показанный код не разрешит их по ошибке. Заметим, что
 переменная flags передается по значению. Это потому, что указанные функции ча-
 стично выполнены в виде макросов.
 
    Если точно известно, что прерывания разрешены, то нет необходимости восста-
 навливать предыдущее состояние системы прерываний. Можно просто разрешить
 прерывания при освобождении блокировки. В этом случае оптимальным будет ис-
 пользование функций spin_lock_irq() и spin_unlock_irq().
    spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
    spin_lock_irq(&mr_lock);
    /* критический участок .. */
    spin_unlock_irq(&mr_lock);
 
 

49

    В операционной системе Linux семафоры (semaphore) — это блокировки, кото-
 рые переводят процессы в состояние ожидания. Когда задание пытается захватить
 семафор, который уже удерживается, семафор помещает это задание в очередь ожи-
 дания (wait queue) и переводит это задание в состояние ожидания (sleep). Когда про-
 цессы3, которые удерживают семафор, освобождают блокировку, одно из заданий
 очереди ожидания возвращается к выполнению и может захватить семафор.
 • Так как задания, которые конфликтуют при захвате блокировки, переводятся в
   состояние ожидания и в этом состоянии ждут, пока блокировка не будет осво-
   бождена, семафоры хорошо подходят для блокировок, которые могут удержи-
   ваться в течение длительного времени.
 • С другой стороны, семафоры не оптимальны для блокировок, которые удер-
   живаются в течение очень короткого периода времени, так как накладные за-
   траты на перевод процессов в состояние ожидания могут "перевесить" время,
   в течение которого удерживается блокировка.
 • Так как поток выполнения во время конфликта при захвате блокировки нахо-
   дится в состоянии ожидания, то семафоры можно захватывать только в кон-
   тексте процесса. Контекст прерывания планировщиком не управляется.
 • При удержании семафора (хотя разработчик может и не очень хотеть этого)
   процесс может переходить в состояние ожидания. Это не может привести к
   тупиковой ситуации, когда другой процесс попытается захватить блокировку
   (он просто переходит в состояние ожидания, что в конце концов дает возмож-
   ность выполняться первому процессу).
 • При захвате семафора нельзя удерживать спин-блокировку, поскольку процесс
   может переходить в состояние ожидания, ожидая на освобождение семафора,
   а при удержании спин-блокировки в состояние ожидания переходить нельзя.
 
    Эти факты подчеркивают особенности использования семафоров по сравнению
 со спин-блокировками. В большинстве случаев выбор решения, использовать или
 не использовать семафоры, прост. Если код должен переходить в состояние ожида-
 ния, что очень часто возникает при необходимости синхронизации с пространством
 пользователя, семафоры — единственное решение. Использовать семафоры всегда
 проще, даже если в них нет строгой необходимости, так как они предоставляют гиб-
 кость, связанную с переходом процессов в состояние ожидания. Если же возникает
 необходимость выбора между семафорами и спид-блокировками, то решение должно
 основываться на времени удержания блокировки. В идеале, все блокировки необхо-
 димо удерживать, по возможности, в течение наиболее короткого времени. При ис-
 пользовании семафоров, однако, допустимы более длительные периоды удержания
 блокировок. В дополнение ко всему, семафоры не запрещают преемптивность ядра,
 и, следовательно, код, который удерживает семафор, может быть вытеснен. Это
 означает, что семафоры не оказывают вредного влияния на задержки (латентность)
 планировщика.
     Последняя полезная функция семафоров — это то, что они позволяют иметь лю-
 бое количество потоков, которые одновременно удерживают семафор. В то время
 как спин-блокировки позволяют удерживать блокировку только одному заданию в
 любой момент времени, количество заданий, которым разрешено одновременно
 удерживать семафор, может быть задано при декларации семафора. Это значение на-
 зывается счетчиком использования (usage count) или просто счетчиком (count). Наиболее
 часто встречается ситуация, когда разрешенное количество потоков, которые од-
 новременно могут удерживать семафор, равно одному, как и для спин-блокировок.
 В таком случае счетчик использования равен единице и семафоры называются бинар-
 ными семафорами (binary semaphore) (потому что он может удерживаться только одним
 заданием или совсем никем не удерживаться) или взаимоисключающими блокировками
 (mutex, мьютекс) (потому что он гарантирует взаимоисключающий доступ —mutual ex-
 clusion). Кроме того, счетчику при инициализации может быть присвоено значение,
 большее единицы. В этом случае семафор называется счетным семафором (counting
 semaphore, семафор-счетчик), и он допускает количество потоков, которые одновре-
 менно удерживают блокировку, не большее чем значение счетчика использования.
 Семафоры-счетчики не используются для обеспечения взаимоисключающего досту-
 па, так как они позволяют нескольким потокам выполнения одновременно находить-
 ся в критическом участке. Вместо этого они используются для установки лимитов в
 определенном коде. В ядре они используются мало. Если вы используете семафор,
 то, скорее всего, вы используете взаимоисключающую блокировку (семафор со счет-
 чиком, равным единице).
 
 

50

 
  Что следует использовать: семафоры или спин-блокировки
 
  Требование                                  Рекомендуемый тип блокировки
  Блокировка с малыми накладными затрата-        Спин-блокировки более предпочтительны
  ми (low overhead)
 
  Малое время удержания блокировки               Спин-блокировки более предпочтительны
 
  Длительное время удержания блокировки           Семафоры более предпочтительны
 
  Необходимо использовать блокировку в            Необходима спин-блокировка
  контексте прерывания
 
  Необходимо переходить в состояние ожи-          Необходимо использовать семафоры
  дания (steep) при захваченной блокировке
 
 

51

  Большая блокировка ядра (Big Kernel Lock, BKL) — 
 это глобальная спин-блокировка, которая была создана специ-
 ально для того, чтобы облегчить переход от первоначальной реализации SMP n опе-
 рационной системе Linux к мелкоструктурным блокировкам. Блокировка BKL имеет
 следующие интересные свойства.
    • Во время удержания BKL можно переходить в состояние ожидания. Блокировка
      автоматически освобождается, когда задание переходит в состояние ожидания,
      и снова захватывается, когда задание планируется на выполнение. Конечно,
      это не означает, что безопасно переходить в состояние ожидания при удержа-
      нии BKL, просто это можно делать и это не приведет к взаимоблокировке.
    • Блокировка BKL рекурсивна. Один процесс может захватывать эту блокировку
      несколько раз подряд, и это не приведет к самоблокировке, как в случае обыч-
      ных спин-блокировок.
    • Блокировка BKL может использоваться только в контексте процесса.
    • Блокировка BKL — это от лукавого.
  
  Блокировка BKL была введена для того, чтобы упростить переход к
 мелкоструктурным блокировкам. Во времена 2.2 она оказала большую помощь, а сегод-
 ня она приводит к ухудшению масштабируемости5.
    Использовать блокировку BKL не рекомендуется. На самом деле, новый код ни-
 когда не должен использовать BKL. Однако эта блокировка все еще достаточно ин-
 тенсивно используется в некоторых частях ядра. 
  Функция lock_kernel () позволяет захватить блокировку, а функ-
 ция unlock_kernel () — освободить блокировку. 
 
 
 

52

     Секвентная блокировка (seq lock) — это новый тип блокировки, который появил-
 ся в ядрах серии 2.6. Эти блокировки предоставляют очень простой механизм чте-
 ния и записи совместно используемых данных. Работа таких блокировок основана
 на счетчике последовательности событий. Перед записью рассматриваемых данных
 захватывается спин-блокировка, и значение счетчика увеличивается на единицу.
 После записи данных значение счетчика снова увеличивается на единицу, и спин-
 блокировка освобождается, давая возможность записи другим потокам. Перед чте-
 нием и после чтения данных проверяется значение счетчика. Если два полученных
 значения одинаковы, то во время чтения данных новый акт записи не начинался,
 Если к тому же оба эти значения четные, то к моменту начала чтения акт записи
 был закончен (при захвате блокировки на запись значение счетчика становится не-
 четным, а перед освобождением — снова четным, так как изначальное значение счет-
 чика равно нулю).
    Определение секвентной блокировки можно записать следующим образом.
    seqlock_t mr_seq_lock = SEQLOCK_UNLOCKED;
    Участок кода, который осуществляет запись, может выглядеть следующим образом.
    write_seqlock(&mr_seq_lock);
    /* блокировка захвачена на запись ... */
    write_sequnlock(&mr_seq_lock);
 
 

53

     Рассмотрим следующий код.
    а = 1;
    Ь = 2;
    На некоторых процессорах запись нового значения в область памяти, занимае-
 мую переменной b, может выполниться до того, как будет записано новое значение
 в область памяти переменной а. Компилятор может выполнить такую перестановку
 статически и внести в файл объектного кода, что значение переменной b должно
 быть установлено перед переменной a. 
    Функция rmb () позволяет установить барьер чтения памяти (read memory barrier).
 Она гарантирует, что никакие операции чтения памяти, которые выполняются перед
 вызовом функции rmb (), не будут переставлены местами с операциями, которые вы-
 полняются после этого вызова. Иными словами, все операции чтения, которые ука-
 заны до этого вызова, будут выполнены перед этим вызовом, а все операции чтения,
 которые указаны после этого вызова никогда не будут выполняться перед ним.
    Функция wmb () позволяет установить барьер записи памяти (write barrier). Она
 работает так же, как и функция rmb (), но не с операциями чтения, а с операциями
 записи — гарантируется, что операции записи, которые находятся по разные сторо-
 ны барьера, никогда не будут переставлены местами друг с другом.
 Функция rnb () позволяет создать барьер на чтение и запись. 
    Функция barrier() предотвращает возможность оптимизации компилятором
 операций считывания и записи данных, если эти операции находятся по разные
 стороны от вызова данной функции (т.е. запрещает изменение порядка операций).
 
 
 

54

 Системный таймер — это программируемое аппаратное устройство, которое генери-
 рует аппаратное прерывание с фиксированной частотой. Обработчик этого преры-
 вания, который называется прерыванием таймера (timer interrupt), обновляет значение
 системного времени и выполняет периодические действия. 
     Кроме того, в этой главе будут рассмотрены динамические таймеры (dynamic timers) —
 средства, позволяющие планировать события, которые выполняются один раз, по-
 сле того как истек некоторый интервал времени. Например, драйвер накопителя на
 гибких магнитных дисках использует таймер, чтобы остановить двигатель дисково-
 да, если дисковод неактивен в течение некоторого периода времени. В ядре можно
 динамически создавать и ликвидировать таймеры. 
  Для того чтобы получать информацию о времени и управлять си-
 стемным временем, ядро должно взаимодействовать с системным аппаратным обе-
 спечением. Аппаратное обеспечение предоставляет системный таймер, который
 используется ядром для измерения времени. Системный таймер работает от элек-
 тронного эталона времени, такого как цифровые электронные часы или тактовый
 генератор процессора. Интервал времени системного таймера периодически исте-
 кает (еще говорят таймер срабатывает— hitting, popping) с определенной запрограм-
 мированной частотой. Эта частота называется частотой импульсов таймера, (tick rate).
 Когда срабатывает системный таймер, он генерирует прерывание, которое ядро об-
 рабатывает с помощью специального обработчика прерывания.
    Так как в ядре есть информация о запрограммированной частоте следования им-
 пульсов таймера, ядро может вычислить интервал времени между двумя успешными
 прерываниями таймера. Этот интервал называется временной отметкой или импуль-
 сом таймера (tick) и в секундах равен единице, деленной на частоту импульсов. Как будет
 показано дальше, именно таким способом ядро отслеживает абсолютное время (wall
 time) и время работы системы (uptime). Абсолютное время— это фактическое время
 дня, которое наиболее важно для пользовательских приложений. Ядро отслеживает
 это время просто потому, что оно контролирует прерывание таймера. В ядре есть
 семейство системных вызовов, которое позволяет пользовательским приложениям
 получать информацию о дате и времени дня. 
    Прерывание таймера очень важно для управления работой всей операционной
 системы. Большое количество функций ядра действуют и завершаются в соответ-
 ствии с ходом времени. Следующие действия периодически выполняются систем-
 ным таймером.
    • Обновление значения времени работы системы (uptime).
    • Обновление значения абсолютного времени (time of day).
    • Для SMP-систем выполняется проверка балансировки очередей выполнения
      планировщика, и если они не сбалансированы, то их необходимо сбалансировать
     • Проверка, не израсходовал ли текущий процесс свой квант времени, и если
     израсходовал, то выполнятся планирование выполнения нового процесса (как
     это было рассказано в главе 4).
    Часы реального времени (real-time clock, RTC) представляют собой энергонеза-
 висимое устройство для сохранения системного времени. Устройство RTC продол-
 жает отслеживать время, даже когда система отключена, благодаря небольшой бата-
 рее, которая обычно находится на системной плате. Для аппаратной платформы PC
 устройство RTC интегриронано в КМОП-микросхему BIOS. При этом используется
 общая батарея и для работы устройства RTC и для сохранения установок BIOS.
   Для аппаратной платформы х86 главный системный таймер — это программируе-
 мый интервальный таймер (programmable interval timer, PIT). Таймер PIT существует
 на всех машинах платформы PC. Co времен операционной системы DOS он исполь-
 зуется для управления прерываниями. Ядро программирует таймер PIT при загруз-
 ке, для того чтобы периодически генерировать прерывание номер нуль с частотой
 HZ. Этот таймер— простое устройство с ограниченными возможностями, но, тем не
 менее, хорошо выполняющее свою работу. Другие эталоны времени для аппаратной
 платформы х86 включают таймер APIC (Advanced Programmable Interrupt Controller,
 расширенный программируемый контроллер прерываний) и счетчик отметок време-
 ни (TSC, Time Stamp Counter).
 
 
 
 
 

55

     Частота системного таймера (частота импульсов, tick rate) программируется при
 загрузке системы на основании параметра ядра НZ, который определен с помощью
 директивы препроцессора. Значение параметра HZ отличается для различных под-
 держиваемых аппаратных платформ. На самом деле, для некоторых аппаратных
 платформ значение параметра HZ отличается даже для разных типов машин.
    Данный параметр ядра определен в файле < asm/param.h>. Частота системного
 таймера равна значению параметра HZ, период таймера равен 1/HZ. Например, в
 файле include/asm-i386/param.h для аппаратной платформы i386 этот параметр
 определен следующим образом.
    #define HZ 1000 /* internal kernel time frequency */
    Поэтому для аппаратной платформы i368 прерывание таймера генерируется с
 частотой 1000 Гц, т.е. 1000 раз в секунду (каждую тысячную долю секунды или одну
 миллисекунду). Для большинства других аппаратных платформ значение частоты
 системного таймера равно 100 Гц. Да и для i386 в версии до 2.5 он тоже был 100 герц.
    Глобальная переменная jiffies содержит количество импульсов системного
 таймера, которые были получены со времени загрузки системы. При загрузке ядро
 устанавливает значение этого параметра в нуль и он увеличивается на единицу при
 каждом прерывании системного таймера. Так как в секунду возникает HZ прерыва-
 ний системного таймера, то за секунду значение переменной jiffies увеличивается
 на HZ. Время работы системы (uptime) поэтому равно jiffies / H Z секунд.
       Переменная jiffies исторически всегда представлялась с помощью типа
 unsigned long и, следовательно, имеет длину 32 бит для 32-разрядных аппаратных
 платформ и 64 бит для 64-разрядных. В случае 32-разрядного значения переменной
 jiffies и частоты появления временных отметок 100 раз в секунду, переполнение
 этой переменной будет происходить примерно каждые 497 дней, что является впол-
 не возможным событием. 
 
 
 
 
 
 

56

  Обработчик прерываний таймера разбит на две части: часть, зависимую от
 аппаратной платформы, и независимую часть.
    Подпрограмма, которая зависит от аппаратной платформы, регистрируется в ка-
 честве обработчика прерываний системного таймера и выполняется, когда срабаты-
 вает системный таймер. 
    Аппаратно-независимая функция do_timer () выполняет значительно больше
 действий.
      void do_timer(struct pt_regs *regs)
      {
         jiffies_64++;
         update_process_times(user_mode(regs));
         update_times();
      }
      Макрос user_mode () просматривает состояние регистров процессора, regs , и
 возвращает значение 1, если прерывание таймера возникло в пространстве пользо-
 вателя, и значение 0— если в пространстве ядра. Это позволяет функции update_
 process_times  учесть, что за время между предыдущим и данным импульсами
 системного таймера процесс выполнялся в режиме задачи или в режиме ядра.
  Всё это происходит каждые 1/HZ секунд, т.е. 1000 раз в секунду на машине типа PC.
 
 

57

     Текущее значение абсолютного времени (time of day, wall time, время дня) опреде-
 лено в файле kernel/timer.с следующим образом.
    struct timespec xtime;
    Структура данных timespec определена в файле  в следующем
 виде.
    struct timespec {
              time_t tv_sec; /* seconds */
              long tv_nsec; /* nanoseconds */
              };
    Поле xtime.tv_sec содержит количество секунд, которые прошли с 1 января
 1970 года (UTC, Universal Coordinated Time, всеобщее скоординированное время).
 Указанная дата называется epoch (начало эпохи). В большинстве Unix-подобных опе-
 рационных систем счет времени ведется с начала эпохи. В поле xtime.tv_nsec хра-
 нится количество наносекунд, которые прошли в последней секунде.
    Чтение или запись переменной xtime требует захвата блокировки xtime_lock.
 Это блокировка — не обычная спин-блокировка, а секвентпая блокировка.
    Для обновления значения переменной xtime необходимо захватить секвентную
 блокировку на запись следующим образом.
    write_seqlock(&xtime_lock);
    /* обновить значение переменной xtime ... */
    write_sequnlock(&xtime_lock);
    Главный пользовательский интерфейс для получения значения абсолютного вре-
 мени — это системный вызов gettimeofday().
    Системный вызов settimeofday() позволяет установить абсолютное время в
 указанное значение. Для того чтобы его выполнить, процесс должен иметь возмож-
 ность использования CAP_SYS_TIME.
    Если не считать обновления переменной xtime, то ядро не так часто использует
 абсолютное время, как пространство пользователя. Одно важное исключение— это
 код файловых систем, который хранят в индексах файлов значения моментов време-
 ни доступа к файлам.
 
 

58 Таймеры (timers), или, как их еще иногда называют, динамические таймеры, или таймеры ядра, необходимы для управления ходом времени в ядре. Коду ядра часто необходимо откладывать выполнение некоторых функций на более позднее время. Таймеры представлены с помощью структур timer_list.

 Первый шаг в создании таймера — это его объявление в следующем виде.
     struct timer_list my_timer;
    Далее должны быть инициализированы поля структуры, которые предназначены
 для внутреннего использования. Это делается с помощью вспомогательной функции
 перед вызовом любых функций, которые работают с таймером.
    init_timer(&my_timer);
    Далее необходимо заполнить все остальные поля структуры, например, следующим образом.
    my_timer.expires = jiffies + delay; /* интервал времени таймера закончится через delay импульсов */
    my_timer.data = 0; /* в функцию-обработчик Судет передан параметр,
                       равный нулю */
    my_timer.function = my_function; /* функция, которая будет выполнена,
                                 когда интервал времени таймера истечет */
    Значение поля my_timer.expires указывает время ожидания в импульсах си-
 стемного таймера (необходимо указывать абсолютное количество импульсов). Когда
 текущее значение переменной jiffies становится большим или равным значению
 поля my_timer.expires , вызывается функция-обработчик my_timer.function 
 с параметром my_timer.data . Как видно из описания структуры timer_list , функ-
 ция-обработчик должна соответствовать следующему прототипу.
    void my_timer_function(unsigned long data);
 Последняя операция — это активизация таймера.
     add_timer(&my_timer);
    Иногда может потребоваться изменить момент времени срабатывания таймера,
 который уже активизирован. В ядре реализована функция mod_timer (), которая по-
 зволяет изменить момент времени срабатывания активного таймера.
    mod_timer(&my_timer, jiffies + new_delay); /* установка нового времени
                                                     срабатывания */
    Для того чтобы деактивизировать таймер до момента его срабатывания, необхо-
 димо использовать функцию del_timer () следующим образом.
    del_timer(&my_timer);
 
 
 
 
   
 

59 Ядро сопоставляет каждой странице физической памяти в системе структуру struct page.

    struct page {
           page_flags_t              flags;
           atomic_t                  _count;
           atornic_t                  _mapcount;
           unsigned long             private;
           struct address_space       *mapping;
           pgoff_t                   index;
           struct list_head          lru;
           void                       *virtual;
    };
    Рассмотрим самые важные поля этой структуры. Поле flags содержит состоя-
 ние страницы. Это поле включает следующую информацию: является ли страни-
 ца измененной (dirty) или заблокированной (locked) в памяти. Значение каждого
 флага представлено одним битом, поэтому всего может быть до 32 разных флагов.
 Значения флагов определены в файле < linux/page-flags.h>.
    Поле _count содержит счетчик использования страницы — т.е. сколько на эту
 страницу имеется ссылок. Когда это значение равно нулю, это значит, что никто не
 использует страницу, и она становится доступной для использования при новом вы-
 делении памяти. Код ядра не должен явно проверять значение этого поля, вместо
 этого необходимо использовать функцию page_count () , которая принимает ука-
 затель на структуру page в качестве единственного параметра. Хотя в случае неза-
 нятой страницы памяти значение счетчика _count может быть отрицательным (во
 внутреннем представлении), функция page_count () возвращает значение нуль для
 незанятой страницы памяти и положительное значение — для страницы, которая в
 данный момент используется. Страница может использоваться страничным кэшем
 (в таком случае ноле mapping указывает на объект типа address_space, который
 связан с данной страницей памяти), может использоваться в качестве частных дан-
 ных (на которые в таком случае указывает поле private) или отображаться в табли-
 цу страниц процесса.
    Поле virtual — это виртуальный адрес страницы. Обычно это просто адрес
 данной страницы в виртуальной памяти ядра. Некоторая часть памяти (называемая
 областью верхней памяти, high memory) не отображается в адресное пространство
 ядра (т.е. не входит в него постоянно). В этом случае значение данного поля равно
 NULL и страница при необходимости должна отображаться динамически. Верхняя
 память будет рассмотрена в одном из следующих разделов.
    Наиболее важный момент, который необходимо понять, это то, что структура
 page связана со страницами физической, а не виртуальной памяти. 
 Назначение этой структуры — описывать область физической памяти, а не данных,
 которые в ней содержатся.
    Ядро использует рассматриваемую структуру данных для отслеживания всех стра-
 ниц физической памяти в системе, так как ядру необходима информация о том, сво-
 бодна ли страница (т.е. соответствующая область физической памяти никому не вы-
 делена). Если страница не свободна, то ядро должно иметь информацию о том, чему
 принадлежит эта страница. Возможные обладатели: процесс пространства пользова-
 теля, данные в динамически выделенной памяти в пространстве ядра, статический
 код ядра, страничный кэш (page cache) и т.д.
    Разработчики часто удивляются, что для каждой физической страницы в системе
 создается экземпляр данной структуры. Они думают: "Как много для этого использу-
 ется памяти!" Давайте посмотрим, насколько плохо (или хорошо) расходуется адрес-
 ное пространство для хранения информации о страницах памяти. Размер структуры 
 struct page равен 40 байт. Допустим, что система имеет страницы размером
 1 Кбайт, а объем физической памяти равен 128 Мбайт. Тогда все структуры раде в
 системе займут немного больше 1 Мбайт памяти — не очень большая плата за воз-
 можность управления всеми страницами физической памяти.
 
 
 

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

    В связи с этими ограничениями, в операционной системе Linux выделяют три
 зоны памяти.
    • Z0NE_DMA. Содержит страницы, которые совместимы с режимом DMA.
    • ZONE_NORMAL. Содержит страницы памяти, которые отображаются в адресные
      пространства обычным образом.
    • ZONE_HIGHMEM. Содержит "верхнюю память", состоящую из страниц, которые
      не могут постоянно отображаться в адресное пространство ядра.
 
  Устройства ISA не могут выполнять операции DMA в полном 32-разрядном простран-
 стве адресов, так как устройства ISA могут обращаться только к первым 16 Мбайт
 физической памяти. Следовательно, зона ZONE_DMA для платформы х8б содержит
 только страницы памяти с физическими адресами в диапазоне 0-16 Мбайт.
     Аналогично используется и зона ZONE_HIGHMEM. To, что аппаратная платформа
 может отображать и чего она не может отображать в адресное пространство ядра,
 отличается для разных аппаратных платформ. Для платформы х86 зона ZONE_
 HIGHMEM— это вся память, адреса которой лежат выше отметки 896 Мбайт. Для
 других аппаратных платформ зона ZONE_HIGHMEM пуста, так как вся память может
 непосредственно отображаться. Память, которая содержится в зоне ZONE_HIGHMEM,
 называется верхней памятью (high memory). Вся остальная память в системе называет-
 ся нижней памятью (low memory).
    Зона ZONE_NORMAL обычно содержит все, что не попало в две предыдущие зоны
 памяти. Для аппаратной платформы х86, например, зона ZONE_NORMAL содержит
 всю физическую память от 16 до 896 Мбайт. Для других, более удачных аппаратных
 платформ, SONE_NORMAL— это вся доступная память. В табл. 11.1 приведен список
 зон для аппаратной платформы х86.
     Каждая зона представлена с помощью структуры struct zone.
 

61 Ядро предоставляет один низкоуровневый интерфейс для выделения памяти и несколько интер- фейсов для доступа к ней. Все эти интерфейсы выделяют память в объеме, кратном размеру страницы, и определены в файле < linux/gfp.h> . Основная функция вы- деления памяти следующая.

    struct page * alloc_pages(unsigned int gfp_mask, unsigned int order)
  
    Данная функция позволяет выделить 2 в степени order смежных страниц
 (один непрерывный участок) физической памяти и возвращает указатель на структу-
 ру page, которая соответствует первой выделенной странице памяти. В случае ошиб-
 ки возвращается значение NULL. Параметр gfp_mask будет рассмотрен несколько
 позже. Полученную страницу памяти можно конвертировать в ее логический адрес с
 помощью следующей функции.
    void * page_address(struct page *page)
 
    Если необходима всего одна страница памяти, то для этой цели определены сле-
 дующие функции-оболочки, которые позволяют уменьшить количество работы по
 набору кода программы.
    struct page * alloc_page(unsigned int gfp_mask)
    unsigned long __get_free_page(unsigned int gfp_mask)
 
 
 

62 Функция kmalloc () работает аналогично функции mallос () пространства поль- зователя, за исключением того, что добавляется еще один параметр flags. Функция kmalloc () — это простой интерфейс для выделения в ядре участков памяти разме- ром в заданное количество байтов. Если необходимы смежные страницы физиче- ской памяти, особенно когда их количество близко целой степени двойки, то ранее рассмотренные интерфейсы могут оказаться лучшим выбором. Однако для большин- ства операций выделения памяти в ядре функция kmalloc () — наиболее предпочти- тельный интерфейс.

    Рассматриваемая функция определена в файле < linux/slab.h> следующим об-
 разом.
    void * kmalloc(size_t size, int flags)
  
    Данная функция возвращает указатель на участок памяти, который имеет размер
 хотя бы size байт3. Выделенный участок памяти содержит физически смежные стра-
 ницы. В случае ошибки функция возвращает значение NULL. Выделение памяти в
 ядре заканчивается успешно, только если доступно достаточное количество памяти.
 Поэтому после вызова функции kmalloc () всегда необходимо проверять возвраща-
 емое значение на равенство значению NULL и соответственным образом обрабаты-
 вать ошибку.
 
    Рассмотрим пример. Допустим, нам необходимо выделить достаточно памяти для
 того, чтобы в ней можно было разместить некоторую воображаемую структуру dog.
    struct dog *ptr;
    ptr = kmalloc (sizeof (struct dog), GFP_KERNEL);
    if (!ptr)
              /* здесь обработать ошибку ... */
 
    Обратной к функции kmalloc () является функция k f r e e (), которая определена
 в файле < linux/slab.h > следующим образом.
    void kfree(const void *ptr)
 
    Функция vmalloc () работает аналогично функции kmalloc ( ) , за исключением
 того, что она выделяет страницы памяти, которые только виртуально смежные и
 необязательно смежные физически. Точно так же работают и функции выделения
 памяти в пространстве пользователя: страницы памяти, которые выделяются с по-
 мощью функции malloc ( ) , япляются смежными в виртуальном адресном простран-
 стве процесса, но нет никакой гарантии, что они смежные в физической оператив-
 ной памяти. Функция kmalloc () отличается тем, что гарантирует, что страницы
 памяти будут физически (и виртуально) смежными. Функция vmalloc () гарантирует
 только, что страницы будут смежными в виртуальном адресном пространстве ядра.
 Это реализуется путем выделения потенциально несмежных участков физической
 памяти и "исправления" таблиц страниц, чтобы отобразить эту физическую память
 в непрерывный участок логического адресного пространства.
 
 

63 Выделение и освобождение структур данных — это одна из наиболее частых опе- раций, которые выполняются в любом ядре. Для того чтобы облегчить процедуру частого выделения и освобождения данных при программировании, вводятся списки свободных ресурсов (free list). Список свободных ресурсов содержит некоторый набор уже выделенных структур данных. Когда коду необходим новый экземпляр структу- ры данных, он может взять одну структуру из списка свободных ресурсов, вместо того чтобы выделять необходимый объем памяти и заполнять его данными соот- ветствующей структуры. Позже, когда структура данных больше не нужна, она снова возвращается в список свободных ресурсов, вместо того чтобы освобождать память. В этом смысле список свободных ресурсов представляет собой кэш объектов, в кото- ром хранятся объекты одного определенного, часто используемого типа.

    Одна из наибольших проблем, связанных со списком свободных ресурсов в ядре,
 это то, что над ними нет никакого централизованного контроля. Когда ощущается
 недостаток свободной памяти, нет никакой возможности взаимодействовать меж-
 ду ядром и всеми списками свободных ресурсов, которые в такой ситуации долж-
 ны уменьшить размер своего кэша, чтобы освободить память. В ядре нет никакой
 информации о случайно созданных списках свободных ресурсов. Для исправления
 положения и для универсальности кода ядро предоставляет уровень слябового рас-
 пределения памяти (slab layer), который также называется просто слябовым распре-
 делителем памяти (slab allocator). Уровень слябового распределения памяти выпол-
 няет функции общего уровня кэширования структур данных.
 
 Уровень слябового распределения памяти служит для достижения следующих целей.
 • Часто используемые структуры данных, скорее всего, будут часто выделяться и
   освобождаться, поэтому их следует кэшировать.
 • Частые операции выделения и освобождения памяти могут привести к фраг-
   ментации памяти (к невозможности найти большие участки физически одно-
   родной памяти). Для предотвращения этого, кэшированные списки свободных
   ресурсов организованы непрерывным образом в физической памяти. Так как
   структуры данных возвращаются снова в список свободных ресурсов, то в ре-
   зультате никакой фрагментации не возникает.
 • Список свободных ресурсов обеспечивает улучшенную производительность
   при частых выделениях и освобождениях объектов, так как освобожденные
   объекты сразу же готовы для нового выделения.
 • Если распределитель памяти может использовать дополнительную инфор-
   мацию, такую как размер объекта, размер страницы памяти и общий размер
   кэша, то появляется возможность принимать в критических ситуациях более
   интеллектуальные решения.
 
      Уровень слябового распределения памяти делит объекты па группы, которые на-
 зываются кэшами (cache). Разные кэши используются для хранения объектов различ-
 ных типов. Для каждого типа объектов существует свой уникальный кэш. Например,
 один кэш используется для дескрипторов процессов (список свободных структур
 s t r u c t t a s k _ s t r u c t ) , а другой— для индексов файловых систем ( s t r u c t inode).
 Интересно, что интерфейс krnalloc () построен на базе уровня слябового распреде-
 ления памяти и использует семейство кэшей общего назначения.
      Далее кэши делятся на слябы (буквально slab — однородная плитка, отсюда и на-
 звание всей подсистемы). Слябы занимают одну или несколько физически смежных
 страниц памяти. Обычно сляб занимает только одну страницу памяти. Каждый кэш
 может содержать несколько слябов.
 
 

64

     Виртуальная файловая система (VFS) объектно-ориентированна 3 . Общая файло-
 вая модель представлена набором структур данных. Эти структуры данных очень
 похожи на объекты. Так как ядро программируется строго на языке С, то, при от-
 сутствии возможностей прямой поддержки парадигм ООП в языке программирова-
 ния, структуры данных представляются структурами языка С. Структуры содержат
 как указатели на элементы данных, так и указатели на функции, которые работают
 с этими данными.
    Существуют следующие четыре основных типа объектов VFS.
    • Объект суперблок (superblock), который представляет определенную смонтирован-
       ную файловую систему.
    • Объект файловый индекс (inode), который представляет определенный файл.
    • Объект элемент каталога (dentry), который представляет определенный элемент
       каталога.
    • Объект файл (file), который представляет открытый файл, связанный с процес-
       сом.
 
    Следует обратить внимание, что поскольку подсистема VFS рассматривает катало-
 ги как обычные файлы, то не существует специальных объектов для каталогов. Как
 рассказывалось ранее, объект dentry представляет компонент пути, который может
 содержать обычный файл. Другими словами, dentry — это не то же самое, что ката-
 лог, а каталог — это то же, что и файл. 
 
 Существуют следующие типы операций.
 • Объект super_operations (операции с суперблоком файловой системы) со-
   держит методы, которые ядро может вызывать для определенной файловой
   системы, как, например, read_inode () или sync_fs ().
 • Объект i n o d e o p e r a t i o n s (операции с файловыми индексами) содержит ме-
   тоды, которые ядро может вызывать для определенного файла, как, например,
   c r e a t e d или l i n k ().
 • Объект d e n t r y _ o p e r a t i o n s (операции с элементами каталогов) содержит
   методы, которые ядро может вызывать для определенного элемента каталога,
   как, например, d_compare () или d_delete ().
 • Объект f ile_operations (операции с файлами) содержит методы, которые про-
   цесс может вызывать для открытого файла, как например, read () и wri te ().
 
  Каждая зарегистрированная файловая система представлена структурой 
     file_system_type.
 
  Каждый процесс имеет три структуры, которые описывают файловую
 систему и файлы, связанные с процессом. Это структуры 
     file_struct
     fs_struct
     namespace
 
 
 
 
 

65

     Объект суперблок должен быть реализован для каждой файловой системы. Он ис-
 пользуется для хранения информации, которая описывает определенную файловую
 систему. Этот объект обычно соответствует суперблоку (superblock) или управляющему
 блоку (control block) файловой системы, который хранится в специальном секторе дис-
 ка (отсюда и имя объекта). 
 
    Объект суперблак представляется с помощью структуры  super_block, ко-
 торая определена в файле < linux/fs.h>. Она выглядит следующим образом (ком-
 ментарии описывают назначение каждого поля).
    struct super_block {
     struct list_head         s_list;         /* список всех суперблоков */
     dev_t                     s_dev;         /* идентификатор */
     unsigned long        s_blocksize;        /* размер блока в байтах */
     unsigned long            s_old_blocksize; /*старый размер блока в байтах*/
     unsigned char            s_blocksize_bits; /* размер блока в битах */
     unsigned char            s_dirt;        /*флаг того, что суперблок изменен*/
     ...
 
    Код для создания, управления и ликвидации объектов суперблок находится в файле 
 fs/super.с . Объект суперблок создается и инициализируется в функции alloc_super (). 
 Эта функция вызывается при монтировании файловой системы, которая
 считывает суперблок файловой системы с диска и заполняет поля объекта суперблок.
 
    Наиболее важный элемент суперблока — это поле s_op, которое является указа-
 телем на таблицу операций суперблока. Таблица операций суперблока представле-
 на с помощью структуры  super_operations, которая определена в файле
 < linux/fs.h>. Она выглядит следующим образом.
    struct super_operations {
             struct inode *(*alloc_inode) (struct super_block *sb);
             void (*destroy_inode) (struct inode * ) ;
             void (*read_inode) (struct inode * ) ;
             ...
 
    Каждое поле этой структуры представляет собой указатель на функцию, которая
 работает с объектом суперблок. Операции суперблока выполняют низкоуровневые
 действия с файловой системой и ее файловыми индексами.
 
    Когда для файловой системы необходимо выполнить операции с суперблоком, то
 выполняется разыменование указателя на суперблок, и далее получается указатель
 на необходимый метод. Например, если файловой системе необходимо записать су-
 перблок, то вызывается следующая функция.
    sb->s_op->write_super(sb);
 
 
 

66

    Объект inode содержит всю информацию, которая необходима ядру для манип
 ляций с файлами и каталогами. В файловых системах в стиле Unix вся информаци
 просто считывается из дисковых индексов и помещается в объект inode подсист
 мы VFS. Если файловые системы не имеют индексов, то эту информацию необход
 мо получить из других дисковых структур.
    Объект индекса файла представляется с помощью структуры  inode, к
 торая определена в файле < linux/fs.h>. Эта структура с комментариями, описыв
 ющими назначение каждого поля, имеет следующий вид.
    struct inode {
     struct hlist_node      i_hash;    /* хешированный список */
     struct list_head       i_list;    /* связанный список индексов */
     struct list_head       i_dentry;  /* связанный список объектов dentry */
     ...
 
      Так же как и в случае операций суперблока, важным является поле inode_operations , 
 в котором описаны функции файловой системы, которые могут быть вы-
 званы подсистемой VFS для объекта файлового индекса. Как и для суперблока, опе-
 рации с файловыми индексами могут быть вызваны следующим образом.
       i->i_op->truncate(i)
 
 
 
 

67

  Ядро кэширует объекты в кэше элементов каталога, который называют dcache.
     Кэш объектов dentry состоит из трех частей.
     • Список "используемых" объектов dentry, которые связаны с определенным
       файловым индексом (поле i_dentry объекта inode). Поскольку указанный
       файловый индекс может иметь несколько ссылок, то ему может соответсвовать
       несколько объектов dentry, а следовательно используется связанный список.
     • Двухсвязный список неиспользуемых и негативных объектов dentry "с наи-
       более поздним использованием" (last recently used, LRU). Вставки элементов
       в этот список отсортированы по времени, поэтому элементы, которые нахо-
       дятся в начале списка, — самые новые. Когда ядро должно удалить элементы
       каталогов для освобождения памяти, то эти элементы берутся из конца списка.
    • Хеш-таблица и хеш-функция, которые позволяют быстро преобразовать задан-
      ный путь в объект dentry.
 
    Указанная хеш-таблица представлена с помощью массива dentry_hashtable .
 Каждый элемент массива — это указатель на список тех объектов dentry, которые
 соответствуют одному ключу. Размер этого массива зависит от объема физической
 памяти в системе.
  
 

68

   Файловый объект представляется с помощью структуры  file , которая
 определена в файле < linux/fs.h> . Рассмотрим поля этой структуры с комментари-
 ями, которые описывают назначение каждого поля.
    struct file {
     struct list_head          f_list;            /* список объектов file*/
     struct dentry             *f_dentry; /* связанный объект dentry */
     struct vfsmount           *f_vfsmnt; /* связанная смонтированная
     ...
 
   Методы работы с файловым объектом хранятся в структуре file_operations и
 определены в файле < linux/fs.h> следующим образом.
    struct file_operations {
           struct module *owner;
           loff_t (*llseek) (struct file *, loff_t, int);
           ssize_t (*read) (struct file *, char *, size_t, loff_t *);
           ssize_t (*aio_read) (struct kiocb *, char *, size_t, loff_t);
           ssize_t (*write) (struct file *, const char *, size_t, loff_t * ) ;
             ...