Керування процесами й перепинами

Структура завдання і таблиця процесів

Кожному процесу в Linux динамічно виділяється структура struct task_struct. Максимальна кількість процесів, які можна створити в Linux, обмежена лише об'ємом наявної фізичної пам'яті і визначається за формулою (див. kernel/fork.c:fork_init()):

/*
 * За замовчуванням максимальна кількість підпроцесів встановлюється рівною
 * безпечній величині: структури підпроцесів можуть займати майже половину пам'яті
 */
max_threads = mempages / (THREAD_SIZE/PAGE_SIZE) / 2;

що на архітектурі IA32 зазвичай дорівнює num_physpages/4. Наприклад, на машині з 512 мегабайтів можна створити 32k підпроцесів. Це є значним вдосконаленням 4k-epsilon обмежень для старших (2.2 і раніше) ядер. Все ж це можна змінити у процесі роботи за допомогою KERN_MAX_THREADS sysctl(2), або просто використовуючи procfs-інтерфейс налагоджуваних параметрів ядра:

# cat /proc/sys/kernel/threads-max
32764
# echo 100000 > /proc/sys/kernel/threads-max
# cat /proc/sys/kernel/threads-max
100000
# gdb -q vmlinux /proc/kcore
Core was generated by `BOOT_IMAGE=240ac18 ro root=306 video=matrox:vesa:0x118'.
#0  0x0 in ?? ()
(gdb) p max_threads
$1 = 100000

Сукупність процесів у системі Linux представлено як набір структур struct task_struct, які пов'язуються двома способами:

як хеш-таблиця, хешована за PID, та
як кільцевий двонаправлений список із застосуванням вказівників p->next_task і p->prev_task.

Хеш-таблицю, що називається pidhash[], визначено у include/linux/sched.h:

 /* PID hashing. (shouldnt this be dynamic?) */
 #define PIDHASH_SZ (4096 >> 2)
 extern struct task_struct *pidhash[PIDHASH_SZ];

 #define pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

Завдання хешуються за їх значенням pid, а вищевказана хеш-функція повинна розподіляти завдання рівномірно у інтервалі від 0 до PID_MAX-1. Хеш-таблиця використовується для швидкого пошуку процесу за даним pid, з використанням вбудованої функції find_task_pid() з include/linux/sched.h:

static inline struct task_struct *find_task_by_pid(int pid)
{
        struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];

        for(p = *htable; p && p->pid != pid; p = p->pidhash_next)
                ;

        return p;
}

Процеси у кожному хеш-списку (тобто, хешовані за тією самою величиною) зв'язані за допомогою p->pidhash_next/pidhash_pprev, які використовуються у hash_pid() і unhash_pid() для внесення та видалення певного процесу у/з хеш-таблицю(і). Вони виконуються під захистом спін-блокування зчитування-запису tasklist_lock, що працює в режимі запису.

Кільцевий двонаправлений список, що використовує p->next_task/prev_task, підтримується так, щоб можна було легко переглянути всі процеси у системі. Цього досягають за допомогою макроса for_each_task() із include/linux/sched.h:

#define for_each_task(p) \
        for (p = &init_task ; (p = p->next_task) != &init_task ; )

При використанні for_each_task() необхідно щоб tasklist_lock був у режимі зчитування. Зауважте, що for_each_task() використовує init_task для позначення початку (та закінчення) списку - це гарантує безпеку, оскільки порожній підпроцес з pid=0 ніколи не припиняє роботи.

Модифікатори хеш-таблиці процесів і/або таблиці зв'язків процесів, а саме fork(), exit() і ptrace(), повинні використовувати tasklist_lock в режимі запису. Цікавіше те, що програми запису повинні також відключити переривання на місцевому процесорі. Для цого є серйозна причина: функція send_sigio() зчитує список процесів, а, отже, tasklist_lock працює в режимі читання і викликається з kill_fasync() у контексті переривання. Саме тому програми запису повинні відключати переривання, тоді як програмам зчитування це не потрібно.

Тепер, коли зрозуміло, як пов'язані структури task_struct, розгляньмо складові task_struct. Вони приблизно відповідають поєднанню складових Unix-структур «struct proc» і «struct user».

Інші версії Unix виділяли інформацію про стан процесу у частину, яка завжди повинна знаходитись резидентно у пам'яті (так звана «proc structure», яка включає стан процесу, інформацію про планування, тощо) та частину, яка потрібна лише тоді, коли процес виконується (так звана 'u зона', що включає таблицю дескрипторів файлів, інформацію про дискові квоти, тощо). Єдиною причиною такоє незграбної розробки було те, що пам'ять була дефіцитним ресурсом. Сучасні операційні системи (на даний час тільки Linux, але інші, наприклад FreeBSD, прогресують у цій сфері в напрямку Linux) не потребують такого розділення і, отже, постійно утримують стан процесу у резидентній структурі даних ядра.

Структура task_struct визначена у include/linux/sched.h і на даний час дорівнює 1680 байтам.

Поле стану оголощено наступним чином:

 volatile long state;    /* -1 невиконуваний, 0 виконуваний, >0 зупинений */

 #define TASK_RUNNING            0
 #define TASK_INTERRUPTIBLE      1
 #define TASK_UNINTERRUPTIBLE    2
 #define TASK_ZOMBIE             4
 #define TASK_STOPPED            8
 #define TASK_EXCLUSIVE          32

Чому TASK_EXCLUSIVE визначено як 32, а не 16? Тому що 16 було використано для TASK_SWAPPING і я забув перемістити TASK_EXCLUSIVE вище, коли я видалив усі посилання на TASK_SWAPPING (колись при розробці 2.3.x).

Специфікатор volatile у визначенні p->state означає, що його можна модифікувати асинхронно (з програми обробки переривань):

TASK_RUNNING: означає, що завдання «повинно бути» у черзі виконання. Причиною, через яку воно може не бути у черзі виконання є те, що позначення процесу як TASK_RUNNING і розміщення його у черзі на виконання не є неподільною операцією. Для того, щоб поглянути на чергу виконання завдань необхідно щоб спін-блокування runqueue_lock було ввімкнено у режимі зчитування. Якщо так зробити, то можна побачити, що всі завдання у черзі виконання перебувають у стані TASK_RUNNING. Проте, протилежне не є правильним з причини, поясненої вище. Подібно, драйвери можуть позначати себе (чи, радше, процес, в контексті якого вони працюють) як TASK_INTERRUPTIBLE (чи TASK_UNINTERRUPTIBLE), а тоді викликати schedule(), що видалятиме їх з черги на виконання (за умови, що немає сигналів що очікують обробки, і в цьому випадку процес залишиться у черзі на виконання).
TASK_INTERRUPTIBLE: означає, що завдання пребуває у «сплячому» режимі (призупинено), але може бути пробуджене сигналом чи таймером.
TASK_UNINTERRUPTIBLE: те саме що й TASK_INTERRUPTIBLE, за виключенням того, що завдання не можна пробудити.
TASK_ZOMBIE: завдання завершено, але його стан ще не вловив (wait()) батьківський процес (природній або за присвоюванням).
TASK_STOPPED: завдання зупинено, або по причині сигналів управління процесами, або через ptrace(2).
TASK_EXCLUSIVE: це не окремий стан, але може бути приєднаний логічною операцією АБО до TASK_INTERRUPTIBLE або TASK_UNINTERRUPTIBLE. Це означає, що коли це завдання знаходиться у сплячому режимі у черзі на виконання серед багатьох інших завдань, воно буде пробуджене одне, а не спричинить "галасливе стадо" проблем, пробуджуючи всі сплячі завдання.

Прапори завдання містять інформацію про стани процесу, які не є взаємовиключні:

 unsigned long flags;    /* процесні прапори, визначено нижче */
 /*
  * процесні прапори
  */
 #define PF_ALIGNWARN     0x00000001     /* вивести попередження про вирівнювання */
                                                                         /* ще не реалізовано, лише для 486*/
 #define PF_STARTING          0x00000002    /* створюється */
 #define PF_EXITING              0x00000004    /* припиняється */
 #define PF_FORKNOEXEC   0x00000040    /* сигнал fork, але не виконується */
 #define PF_SUPERPRIV         0x00000100    /* використовує привілеї супер-користувача */
 #define PF_DUMPCORE        0x00000200    /* вивантажена пам'ять */
 #define PF_SIGNALED          0x00000400     /* припинено сигналом */
 #define PF_MEMALLOC       0x00000800     /* виділення пам'яті */
 #define PF_VFORK                0x00001000     /* розбудити породжуючий процес у in mm_release */
 #define PF_USEDFPU            0x00100000     /* завдання використало математичний співпроцесор*/
                                                                          /* у цьому кванті (СМП)*/

Поля p->has_cpu, p->processor, p->counter, p->priority, p->policy та p->rt_priority стосуються планувальника і будуть розглянуті пізніше.

Поля p->mm і p->active_mm вказують відповідно на адресний простір процесу, описаний у структурі mm_struct, та на активний адресний простір, якщо у процеса немає справжнього простору (наприклад, підпроцеси ядра). Це допомагає мінімізувати операції з TLB-буфером при переключенні адресних просторів коли завдання видаляється з розкладу. Отже, в розклад вноситься підпроцес ядра (який немає p->mm), то його next->active_mm буде встановлено у prev->active_mm того завдання, яке було видалено з розкладу, що буде тим же що й prev->mm якщо prev->mm != NULL. Адресний простір може бути розділений між підпроцесами, якщо системному виклику ?clone(2) передано прапор CLONE_VM або за допомогою системного виклику vfork(2).

Поля p->exec_domain і p->personality стосуються індивідуальності завдання, тобто, способу поведінки певних системних викликів, що мають на меті емулювати «індивідуальність» інших реалізацій Unix.

Поле p->fs містить інформацію файлової системи, яка у Linux означає три види даних:

точка монтування і dentry кореневого каталогу,
альтернативні точка монтування і dentry кореневого каталогу,
точка монтування і dentry поточного робочого каталогу.

Ця структура також містить лічильник посилань, оскільки її можна розділяти між клонованими завданнями, якщо системному виклику ?clone(2) передано прапор CLONE_FS.

Поле p->files містить таблицю дескриптора файлу. Його також можна розділяти між завданнями, за умови, що CLONE_FILES зазначено у системному виклику clone(2).

Поле p->sig містить обробники сигналів і може бути розділене між клонованими завданнями, створеними за допомогою системного виклику ?clone(2) із зазначеним CLONE_SIGHAND.

Створення і припинення завдань та підпроцесів ядра

Різні книги про операційні системи подають різні визначення поняття «процес», починаючи від «екземпляр програми, що виконується» та закінчуючи «тим, що утворене системними викликами ?clone(2) або fork(2)». У Linux бувають три види процесів:

підпроцеси очікування (idle thread);
підпроцеси ядра;
завдання користувача.

Підпроцес очікування створюється під час компіляції для першого процесора; після цього він "вручну" створюється для кожного процесора за допомогою машинно-залежних викликів fork_by_hand() у arch/i386/kernel/smpboot.c, який вручну (на деяких архітектурах) розгортає системний виклик fork(2). Процеси очікування мають спільну структуру init_task, але різні структури сегменту стану завдання (TSS), що розміщені у масиві init_tss окремо для кожного процесора. В усіх процесів очікування pid = 0 і жоден інший процес не може мати цей же pid, тобто, використовувати прапор CLONE_PID для виклику ?clone(2).

Підпроцеси ядра створюються із використанням функції kernel_thread(), яка ініціалізує системний виклик ?clone(2) в режимі ядра. Підпроцеси ядра зазвичай не мають адресного простору користувача, тобто, p->mm = NULL, оскільки вони явно виконують exit_mm(), наприклад, через функцію daemonize(). Підпроцеси ядра завжди можуть прямо звертатися до адресного простору ядра. Їм виділяються номери pid у низькому діапазоні. Виконання на нульвому кільці привілеїв процесора (на x86) означає, що підпроцеси ядра володіють усіма привілеями вводу-виводу і не можуть бути вивантажені програмою-планувальником.

Завдання користувача створюються за допомогою системних викликів ?clone(2) або fork(2), які внутрішньо ініціалізують kernel/fork.c:do_fork().

Давайте розглянемо, що відбувається, коли процес користувача здійснює системний виклик fork(2). Хоча fork(2) є машинно-залежним через різні способи передачі стеку користувача та регістрів, сама функція do_fork(), що лежить в основі виклику і виконує цю роботу, є мобільною і розміщується у kernel/fork.c.

При цьому виконуються наступні кроки:

Місцева змінна retval приймає значення -ENOMEM, оскільки це величина, у яку повинен бути встановлений errno якщо fork(2) не зможе розмістити нову структуру завдання.
Якщо CLONE_PID встановлено у clone_flags то повертається помилка (-EPERM), при умові, що виклик здійснював не процес очікування (тільки під час завантаження). Отже, нормальні процеси користувача не можуть передавати CLONE_PID у ?clone(2) та очікувати успішного виконання. Для fork(2) це не важливо, оскільки clone_flags встановлено у SIFCHLD — це важливо тільки тоді, коли sys_clone() ініціалізує do_fork() і передає clone_flags із значення, запитаного із простору користувача.
Ініціалізується current->vfork_sem (пізніше очищається у породжених процесах). Він потрібен для sys_vfork() (системний виклик vfork(2) відповідає clone_flags = CLONE_VFORK|CLONE_VM|SIGCHLD), щоб перевести батьківський процес у сплячий режим доти, поки породжений процес не виконає mm_release(), наприклад, в результаті виконання іншої програми або завершення роботи (exec(), exit(2)).
Розміщується нова структура завдання за допомогою машинно-залежного макроса alloc_task_struct(). На машині типу x86 це лише gfp з приорітетом GFP_KERNEL. Це є основною причиною того, що системний виклик fork(2) може перебувати у сплячому стані. Якщо розміщення не відбулося, повертається -ENOMEM.
Усі значення із структури поточного процесу копіюються у нову структуру за допомогою структурного присвоєння p=current. Може його треба замінити memset-ом? Пізніше поля, які не повинні наслідуватись породженим процесом встановлюються у відповідні значення.
Вмикається загальне блокування ядра, оскільки в іншому випадку решта коду не буде повторно використовуваною.
Якщо батьківський процес використовує ресурси користувача, (концепція UID, Лінукс достатньо гнучкий щоб зробити це питанням, а не фактом), тоді перевірити чи користувач перевищив програмне обмеження RLIMIT_NPROC, і якщо так, то відмовити з -EAGAIN; якщо ні, то інкрементувати лічильник процесів даним uid p->user->count.
Якщо загальносистемна кількість завдань перевищує значення змінюваного параметра max_threads, то відмовити з -EAGAIN.
Якщо виконуваний двійковий файл належить до модульного домену виконання, то інкрементувати лічильник посилань відповідного модуля.
Якщо виконуваний двійковий файл належить до модульного двійкового формату, то інкрементувати лічильник посилань відповідного модуля.
Породжений процес позначається як «невиконаний» (p->did_exec = 0).
Породжений процес позначається як «невідвантажуваний» (p->swappable = 0).
Породжений процес переводиться у стан «неперервного сну», тобто, p->state = TASK_UNINTERRUPTIBLE (Чому це виконується? Я вважаю що це не потрібно — позбудьтеся цього, Лінус підтверджує, що в цьому немає потреби).
Встановлюються прапори p->flags породженого процесу відповідно до значення clone_flags; для простого виклику fork(2) це завжди p->flags = PF_FORKNOEXEC.
Встановлюється pid p->pid породженого процесу за допомогою швидкого алгоритму в kernel/fork.c:get_pid() (спін-блокування lastpid_lock може стати зайвим, оскільки get_pid() викликається завжди під захистом загального блокування ядра із from do_fork(); також видаліть аргумент прапорів у get_pid(), виправлення надіслано Алану 20/06/2000; відгук ߞ пізніше).
Решта коду у do_fork() ініціалізує решту структури породженого процесу. У самому кінці структура завдання поодженого процесу хешується у хеш-таблиці pidhash і породжений процес пробуджується (wake_up_process(p) встановлює p->state = TASK_RUNNING і вносить процес у чергу виконання, отже, нам не треба було встановлювати p->state у TASK_RUNNING раніше, у do_fork()). Цікавим є встановлення p->exit_signal у clone_flags та CSIGNAL, що для fork(2) означає SIGCHLD і встановлення p->pdeath_signal у 0. pdeath_signal використовується тоді, коли проце «забуває» батьківський процес-першоджерело (коли той «помирає») і може бути всатновленим/отриманим за допомогою команд PR_GET/SET_PDEATHSIG системного виклику ?prctl(2) (можна посперечатись, що спосіб повернення значення pdeath_signal через аргумент вказівника на простір користувача у ?prctl(2) є дещо нерозумним — mea culpa, після того, як Аднріес Броуер (Andries Brouwer) поновив довідкову сторінку manpage було вже занадто пізно виправляти).

Таким чином створюються завдання. Існує кілька способів завершення завдання:

виконання системного виклику exit(2);
отримання сигналу ліквідації;
примусова ліквідація за певних виняткових обставин;
виклик ?bdflush(2) з func = 1 (це залежить від версіїї Лінукса - для сумісності з старими дистрибутивами, у яких усе ще є рядок 'update' у /etc/inittab; тепер це виконується підпроцесом ядра kupdate).

Функції, що реалізують системні виклики у Лінуксі мають префікс sys, але зазвичай вони займаються лише перевіркою аргументів або машинно-залежними способами передачі певної інформації, а фактичну роботу виконують do -функції. Це саме стосується і sys_exit(), що викликає do_exit() для виконання роботи. Хоча, деякі частини ядра деколи інціалізують sys_exit(), тоді як вони повинні насправді викликати do_exit().

Функція do_exit() знаходиться у kernel/exit.c. Про do_exit() слід пам'ятати наступне:

Використовує глобальне блокування ядра (вмикає, але не вимикає).
Викликає schedule() по завершенні, щоніколи не повертає керування.
Переводить завдання у TASK_ZOMBIE.
Сповіщає будь-який породжений процес сигналом current->pdeath_signal, якщо не він не дорівнює 0.
Сповіщає породжуючий процес сигналом current->exit_signal, що зазвичай рівнозначно SIGCHLD.
Вивільняє ресурси виділені за допомогою fork, закриває відкриті файли, тощо.
На архітектурах, що використовують пасивне переключення матеметичного співпроцесора (IA64, MIPS, MIPS64) (видаліть аргумент 'flags' для SPARC, SPARC64), виконує все, що вимагає апаратне забезпечення для передачі володіння математичним співпроцесором, якщо той належить даному процесу, до "none".

Програма планування Лінукса

Завданням планувальника є регулювати доступ багатьох процесів до даного процесора. Програму планувальника реалізовано у «головному файлі ядра» kernel/sched.c. Відповідний файл заголовку include/linux/sched.h включено (явно чи неявно) майже у кожен файл вихідного коду ядра.

Поля структури завдання, що стосуються планувальника включають:

p->need_resched: це поле встановлюється якщо необхідно викликати schedule() при «наступній нагоді».
p->counter: кількість тактів системного годинника, що залишились до завершення кванту часу, виділеного планувальнику; декрементується таймером. Коли це поле стає рівним або нижче нуля, воно встановлюється у 0, а також встановлюється p->need_resched. Це також деколи називають «динамічним пріоритетом» процесу, оскільки він може самостійно змінюватись.
p->priority: статичний пріоритет процесу; змінюється лише через добре відомі системні виклики типу nice(2), POSIX.1b ?sched setparam(2) чи 4.4BSD/SVR4 ?setpriority(2).
p->rt_priority: пріоритет реального часу.
p->policy: політика планування; визначає, до якого класу планування належить завдання. Завдання можуть змінювати свій клас планування застосовуючи системний виклик ?sched setscheduler(2). Дійсними значеннями є SCHED_OTHER (традиційний процес у Юнікс), SCHED_FIFO (POSIX.1b процес FIFO реального часу) і SCHED_RR (циклічний процес реального часу стандарту POSIX). Також можна виконати операцію логічного додавання (АБО) SCHED_YIELD до будь-якої з цих величин, щоб позначити, що процес вирішив уступити процесор, наприклад, виконавши системний виклик ?sched yield(2). Процес реального часу FIFO продовжуватиметься поки: a) він не заблокує ввід-вивід b)явно уступить процесор або c) надійде пріоритетне переривання від іншого процесу реального часу з більшим значенням p->rt_priority. SCHED_RR - це те саме, що й SCHED_FIFO, за винятком того, що коли виділений йому час закінчується, він повертається у хвіст черги виконання.

Алгоритм планувальника простий, незважаючи на очевидну значну складність функції schedule(). Функція складна через те, що вона реалізує три алгоритми планування в одному а також через тонкощі мультипроцесорних систем.

Явно «непотрібні» безумовні переходи у schedule() використані там з метою згенерувати найкраще оптимізований (для i386) код. Також пам'ятайте, що планувальник (як більша частина ядра) було повністю переписано для версії 2.4, отже усе написане нижче не стосується версії ядра 2.2 чи старших.

Розгляньмо функцію детальніше:

Якщо current->active_mm = NULL, значить щось негаразд. Діючий процес, навіть підпроцес ядра (current->mm = NULL) завжди повинен мати дійсний p->active_mm.
Якщо у черзі виконання tq_scheduler знаходиться якесь завдання то обробити його. Черги завдань надають ядру механізм відкладення виконання функцій на пізніше. Ми ще розгланемо це у деталях.
Ініціалізувати локальні змінні prev та this_cpu для поточного завдання і поточного процесора відповідно.
Перевірити чи schedule() було викликано із програми обробки переривань (через помилку) і якщо так, то видати повідомлення про паніку.
Зняти глобальне блокування ядра.
Якщо є якесь завдання, що виконується через механізм програмних переривань, то виконати його.
Ініціалізувати локальний вказівник на struct schedule_data *sched_data, щоб він вказував на область даних планувальника для кожного процесора (вирівнюється до розміру рядка кешу для уникнення поперемінного зчитування рядка кешу), що містить величину TSC (стартовий код трансміттера) для last_schedule та вказівник на останню структуру запланованого завдання (sched_data використовується лише у багатопроцесорних системах, але чому init_idle() ініціалізує його і на однопроцесорних системах?).
Вмикається спін-блокування runqueue_lock. Зауважте, що ми використовуємо spin_lock_irq() тому, що у schedule() гарантовано дозволено переривання. Отже, коли розблоковується runqueue_lock, можна повторно дозволити їх замість зберігати/відновлювати eflags (варіант spin_lock_irqsave/restore).
Обробка станів процесів: якщо процес знаходиться у стані TASK_RUNNING, то пропустити його; якщо він у стані TASK_INTERRUPTIBLE і надходить сигнал для нього, то перевести його у стан TASK_RUNNING. В усіх інших випадках завдання видаляється з черги виконання.
next (найкращий кандидат на внесення у план) встановлюється на процес очікування даного процесора. Проте, придатність цього кандидата встановлюється у дуже низьке значення (-1000), з надією що є якийсь кращий кандидат.
Якщо попереднє (поточне) завдання знаходиться у стані TASK_RUNNING, тоді поточна придатність встановлюється у значення його придатності і завдання відмічається як кращий кандидат на планування ніж завдання очікування.
Переглядається черга виконання і придатність кожного процесу, який можна внести у план на даний процесор, порівнюється з поточною величиною; процес з найвищою придатністю отримує перемогу. Тепер треба прояснити поняття «можна внести у план на даний процесор»: на однопроцесорних системах кожен процес у черзі на виконання підходить для внесення у план; на симетричних мультипроцесорних машинах у план виконання для даного процесора можуть бути внесені тільки ті процеси, які зараз не виконуються на іншому процесорі. Придатність визначається функцією goodness(), яка робить придатність процесів реального час дуже високою (1000 + p->rt_priority); ця величина перевищує 1000, що ґарантує, що жоден процес SCHED_OTHER не зможе отримати перемогу. Отжне, вони суперничають лише з іншими процесами реального часу у яких може бути вище значення p->rt_priority. Функція придатності goodness() повертає 0 якщо виділений процесу квант часу (p->counter) закінчився. Для процесів не реального часу початкове значення придатності встановлюється у p->counter - у такий спосіб процес навряд чи здобуде процесор, якщо він уже розпоряджався ним певний час, тобто, інтерактивним процесам надається більш перевага, ніж жадібні до процесора цифроглоти (довготривалі обчислювальні процеси - прим. перекладача)). Машинно-залежна константа PROC_CHANGE_PENALTY намагається реалізувати принцип «близькості процесора» (тобто, надати превагу виконанню процесу на тому самому процесорі). Також вона надає мінамальну перевагу процесам, у яких mm квазує на поточне active_mm або процесам, які не мають адресного простору (користувача), тобто, підпроцесам ядра.
Якщо поточне значення придатності дорівнює нулю, то переглядається весь список процесів (не лише процеси у черзі виконання!) і наново обчислюються їхні динамічні пріоритети із застосуванням простого алгоритму:
```
recalculate:
    {
            struct task_struct *p;
            spin_unlock_irq(&runqueue_lock);
            read_lock(&tasklist_lock);
            for_each_task(p)
                    p->counter = (p->counter >> 1) + p->priority;
            read_unlock(&tasklist_lock);
            spin_lock_irq(&runqueue_lock);
    }
```

Слід пам'ятати, що перед перерахунком вимикається runqueue_lock. Причина в тому, що ми переглядаємо весь список процесів; це може тривати довгий період часу, під час якого на іншому процесорі може бути викликано schedule() і вибрано процес із придатністю, достатньою для того процесора, тоді як на даному процесорі виконується перерахунок. Ну добре, правду кажучи, це трохи суперечливо, оскільки поки (на даному процесорі) вибирається поцес з найкращою придатністю на іншому процесорі schedule() може в цей час перераховувати динамічні пріоритети.

З цього моменту чітко зрозуміло, що next вказує на завдання, яке треба занести у план виконання, отже, next->has_cpu приймає значення 1, а next->processor - this_cpu. Тепер можна зняти блокування runqueue_lock.
Якщо знову відбувається переключення на те саме завдання (next=prev), тоді можна просто повторно ввімкнути глобальне блокування ядра і повернути керування, тобто, пропустити все, що стосується апаратного рівня (регістри, стек, тощо) та віртуальної пам'яті (переключення таблиці сторінок, перерахунок active_mm, тощо).
Макрос switch_to() є апаратно-залежним. На архітертурі i386 він займається: a) керуванням математичним співпроцесором, b) керуванням таблицею LDT, c)перезавантаженням сегментних регістрів, d)керуванням сегментом стану завдання (TSS) та e)перезавантаженням регістрів налагодження.

Реалізація зв'язаного списку Linux

Перед тим як перейти до огляду реалізації черг очікування необхідно ознайомитись з реалізацією стандартних двонаправлених списків у Linux. Черги очікування (як і все решта в Linux) надуживають їх і на жаргоні вони називаються "list.h-реалізацією", оскільки найважливішим файлом є include/linux/list.h.

Тут фундаментальною структурою даних є list_head:

struct list_head {
        struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
        (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

#define list_entry(ptr, type, member) \
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)

Перші три макроси призначені для ініціалізації порожнього списку, для чого вказівники next та prev вказують на сам список. Із синтаксичних обмежень мови C є очевидним де і який застосовувати. LIST_HEAD_INIT(), наприклад, можна використати для ініціалізації елемента структури при оголошенні, другий можна використати для ініціалізуючих оголошень статичних змінних і третій можна використати всередині функцій.

Макрос list_entry() дає доступ до окремих елементів списку, наприклад (із fs/file_table.c:fs_may_remount_ro()):

struct super_block {
   ...
   struct list_head s_files;
   ...
} *sb = &some_super_block;

struct file {
   ...
   struct list_head f_list;
   ...
} *file;

struct list_head *p;

for (p = sb->s_files.next; p != &sb->s_files; p = p->next) {
     struct file *file = list_entry(p, struct file, f_list);
     do something to 'file'
}

Хорошим прикладом є використання макросу list_for_each() у планувальнику, де ми проглядаємо список очікування виконання, шукаючи процес з найвищою придатністю:

static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;

list_for_each(tmp, &runqueue_head) {
    p = list_entry(tmp, struct task_struct, run_list);
    if (can_schedule(p)) {
        int weight = goodness(p, this_cpu, prev->active_mm);
        if (weight > c)
            c = weight, next = p;
    }
}

Тут p->run_list оголошено як структуру list_head run_list у межах task_struct і служить він засобом прив'язки по списку. Видалення і додавання елементів (в голову або у хвіст списку) виконується макросами list_del(), list_add(), list_add_tail(). Приклади, подані нижче демонструють додавання та видалення завдання із черги виконання:

static inline void del_from_runqueue(struct task_struct * p)
{
        nr_running--;
        list_del(&p->run_list);
        p->run_list.next = NULL;
}

static inline void add_to_runqueue(struct task_struct * p)
{
        list_add(&p->run_list, &runqueue_head);
        nr_running++;
}

static inline void move_last_runqueue(struct task_struct * p)
{
        list_del(&p->run_list);
        list_add_tail(&p->run_list, &runqueue_head);
}

static inline void move_first_runqueue(struct task_struct * p)
{
        list_del(&p->run_list);
        list_add(&p->run_list, &runqueue_head);
}

Черги очікування

Коли процес передає ядру запит на виконання чогось, що зараз не може бути виконано, але може бути виконано пізніше, процес переводиться у «сплячий» режим і пробуджується коли з'являється можливість виконати запит. Одним з механізмів ядра, що застосовується для цього, називається «чергою очікування».

Реалізація Linux дозволяє використовувати семантику пробудження із застосуванням прапору TASK_EXCLUSIVE. При роботі з чергами очікування можна використати добре відому чергу, а потім застосувати sleep_on/sleep_on_timeout/interruptible_sleep_on/interruptible_sleep_on_timeout, або визначити свою власну чергу очікування і застосувати add/remove_wait_queue, щоб внести або видалити завдання з неї, та wake_up / wake_up_interruptible для пробудження в потрібний момент.

Прикладом використання першого варіанту роботи з чергами очікування є взаємодія між менеджером пам'яті (у mm/page_alloc.c:__alloc_pages()) та демоном ядра kswapd (у mm/vmscan.c:kswap()) за допомогою черги очікування kswapd_wait, оголошеної у mm/vmscan.c; демон kswapd перебуває у сплячому режимі у цій черзі і пробуджуєтьсятоді, коли менеджерові пам'яті необхідно вивільнити деякі сторінки.

Прикладом використання автономних черг очікування є взаємодія між процесом користувача, який подає запит на дані за допомогою системного виклику read(2), та ядром, що працює в контексті переривання для надання даних. Обробник переривань може бути реалізований наступним чином (спрощений варіант drivers/char/rtc_interrupt()):

static DECLARE_WAIT_QUEUE_HEAD(rtc_wait);

void rtc_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
        spin_lock(&rtc_lock);      
        rtc_irq_data = CMOS_READ(RTC_INTR_FLAGS);
        spin_unlock(&rtc_lock);    
        wake_up_interruptible(&rtc_wait);
}

Отже, обробник переривань отримує дані зчитуючи їх із певного порту вводу-виводу (макрос CMOS_READ() перетворюється у пару outb/inb), а тоді побуджуються всі процеси, що знаходяться у призупиненому стані в черзі очікування rtc_wait.

Системний виклик read(2) можна реалізувати наступним чином:

ssize_t rtc_read(struct file file, char *buf, size_t count, loff_t *ppos)
{
        DECLARE_WAITQUEUE(wait, current);
        unsigned long data;
        ssize_t retval;

        add_wait_queue(&rtc_wait, &wait);
        current->state = TASK_INTERRUPTIBLE;
        do {
                spin_lock_irq(&rtc_lock);
                data = rtc_irq_data;
                rtc_irq_data = 0;
                spin_unlock_irq(&rtc_lock);

                if (data != 0)
                        break;

                if (file->f_flags & O_NONBLOCK) {
                        retval = -EAGAIN;
                        goto out;
                }
                if (signal_pending(current)) {
                        retval = -ERESTARTSYS;
                        goto out;
                }
                schedule();
        } while(1);
        retval = put_user(data, (unsigned long *)buf); 
        if (!retval)
                retval = sizeof(unsigned long);

out:
        current->state = TASK_RUNNING;
        remove_wait_queue(&rtc_wait, &wait);
        return retval;
}

У rtc_read() виконуються наступні дії:

Оголошується елемент черги очікування, що вказує на контекст поточного процесу.
Цей елемент додається до черги очікування rtc_wait.
Поточний контекст позначається як TASK_INTERRUPTIBLE, що означає, що його не буде повторно включено у план після наступної призупинки.
Перевіряється, чи є доступні дані; якщо є, то відбувається переривання, дані копіюються у буфер користувача, процес позначається як TASK_RUNNING, видаляється із черги очікування та повертається керування.
Якщо даних ще немає, то перевіряється, чи користувач зазначив неблокуючий ввід-вивід, і якщо так, то виконання припиняється з сигналом EAGAIN (що рівнозначно EWOULDBLOCK).
Також перевіряється, чи немає сигналів, що очікують обробки, і якщо так, то "вищим рівням" відправляється запит на повторення системного виклику при необхідності. Під «необхідністю» маються на увазі деталі розмішення сигналу, як зазначено у системному виклику ?sigaction(2).
Потім завдання «вимикається», тобто, переходить в сплячий режим, поки обробник переривань не пробудить процес. Якщо процес не позначено як TASK_INTERRUPTIBLE, то планувальник міг би внести процес у план виконання ще до того як дані стануть доступні, спричинюючи цим зайву обробку.

Також варто зазначити, що застосовуючи черги очікування досить легко реалізувати системний виклик ?poll(2):

static unsigned int rtc_poll(struct file *file, poll_table *wait)
{
        unsigned long l;

        poll_wait(file, &rtc_wait, wait);

        spin_lock_irq(&rtc_lock);
        l = rtc_irq_data;
        spin_unlock_irq(&rtc_lock);

        if (l != 0)
                return POLLIN | POLLRDNORM;
        return 0;
}

Вся робота виконується апаратно-незалежною функцією poll_wait(), яка здійснює необхідні маніпуляції з чергою очікування; все що треба зробити — це вказати їй чергу очікування, яка пробуджується апаратно-залежним обробником переривань.

Таймери ядра

А тепер звернімо увагу на таймери ядра. Вони застосовуються для призначення виконання певної функції (що називається «обробник таймера») у зазначений час в майбутньому. Основною структурою даних є timer_list, яку оголошено в include/linux/timer.h:

struct timer_list {
        struct list_head list;
        unsigned long expires;
        unsigned long data;
        void (*function)(unsigned long);
        volatile int running;
};

Поле list призначено для прив'язки до внутрішнього списку, захищеного спін-блокуванням timerlist_lock. Поле expires містить значення кількості тіків системного таймера, що залишились до виклику обробника функції з data, преданим як параметр. Поле running використовується у багатопроцесорних системах для перевірки чи обробник таймера зараз виконується на іншому процесорі.

Функції add_timer() і del_timer() додають і видаляють даний таймер у/з списку. Коли час таймера вичерпано, він видаляється автоматично. Перед використанням таймера він ПОВИНЕН бути проініціалізованим за допомогою функції init_timer(). І перед додаванням його в список треба встановити значення полів function та expires.

Базові половини

Деколи обґрунтованим є поділ об'єму роботи, яка виконуватиметься у межах обробника переривань, на негайну роботу (наприклад підтвердження переривання, обновлення статистики, тощо) та роботу, яку можна відкласти на майбутнє, коли буде дозволено переривання (наприклад певна пост-обробка даних, пробудження процесів, які очікують ці дані, тощо).

Базові половини — це найстаріший механізм відтермінованого виконання завдань ядра, який був доступний ще у Linux 1.x. У Linux 2.0 було додано новий механізм, що називається «черги завдань», який буде темою обговорення наступної секції.

Базові половини упорядковуються глобальним спін-блокуванням global_bh_lock, тобто, у кожен момент часу на одному процесорі може бути лише одна базова половина. Проте, при спробі виконати обробник, якщо global_bh_lock є недоступним, базова половина маркується (тобто, планується) на виконання - отже, обробка може продовжуватись, на відміну від зайнятого циклу у global_bh_lock.

В загальному може бути зареєстровано лише 32 базові половини. Базовими половинами маніпулюють наступні функції (усі експотровано у модулі):

void init_bh(int nr, void (*routine)(void)): розміщує вказівник на обробник базової половини, вказаний аргументом routine в полі пам'яті nr. Дане поле пам'яті повинно бути зазначеним у include/linux/interrupt.h у формі XXXX_BH, наприклад, TIMER_BH or TQUEUE_BH. Зазвичай, підпрограма ініціалізації підсистеми (init_module() для модудів) розміщує необхідну базову половину, використовуючи дану функцію.
void remove_bh(int nr): виконує функції, протилежні init_bh(), тобто, видаляє базову половину, встановлену у поле пам'яті nr. Ця функція не здійснює перевірки на наявність помилок, отже, наприклад, remove_bh(32) призведе до виклику panic/oops. Як правило, процедура очистки підсистеми (cleanup_module() для модулів) використовує цю функцію для вивільнення поля пам'яті, яке можна використати пізніше для інших підсистем. (А чи не краще було б занести у список /proc/bottom_halves усі зареєстровані в системі базові половини? Очевидно, що global_bh_lock повинен бути в режимі зчитування/запису).
void mark_bh(int nr): маркує базову половину у полі пам'яті nr на виконання. Зазвичай, обробник переривань позначатиме свою базову половину (звідси й назва!) на виконання у "безпечніший час".

Базові половини — це глобально заблоковані тасклети, отже, питання «коли виконуються обробники базових половин?» насправді означає «коли виконуються тасклети?». Відповідь: a) при кожному виклику schedule() та b) при кожному поверненні з переривання чи системного виклику в entry.S (отже, варіант з schedule() не дуже оригінальний - це все одно, що додати ще одне дуже-дуже повільне переривання; а чому б взагалі не позбутись мітки handle_softirq у schedule()?).

Черги завдань

Черги завдань можна уявити собі як динамічне розширення до старих базових половин. Фактично, у вихідному коді вони часом трактуються як «нові» базові половини. Якщо бути детальнішим, то старі базові половини, розглянуті в попередній секції, мають такі обмеження:

Обмежена їхня кількість (32).
Кожна базова половина може бути асоційована лише з однією функцією обробки.
Базові половини вживаються з ввімкненим спін-блокуванням, а отже, не можуть блокувати.

Отже, застосовуючи черги завдань, можна пов'язувати будь-яку кількість функцій та виконувати їх одну за одною пізніше. Нова черга завдань створюється за допомогою макроса DECLARE_TASK_QUEUE(), а нове завдання вноситься в неї функцією queue_task(). Тоді чергу завдань можна обробити, використовуючи run_task_queue(). Замість створення своєї власної черги завдань (і потреби вручну користуватись нею), ви можете використати одну з наперед визначених черг завдань Лінукса, які застосовуються у добре відомих ситуаціях:

tq_timer: черга завдянь таймера; виконується при кожному перериванні таймера та при вивільненні tty-пристрою (закритті або вивільненні напіввідкритого термінального пристрою). Оскільки обробник таймера працює в контексті переривання, то завдання tq_timer також виконуються у контексті переривання і, отже, не можуть блокувати.
tq_scheduler: черга завдань планувальника; використовується планувальником (а також при закриванні tty-пристроїв, подібно до tq_timer). Оскільки планувальник виконується у контексті процесу, який повторно вноситься у план виконання, завдання у tq_scheduler можуть виконувати будь-що, тобто, блокувати, використовувати дані із контексту процесу (але навіщо їм це?), тощо.
tq_immediate: насправді це базова половина IMMEDIATE_BH, отже, драйвери можуть використовувати queue_task(task, &tq_immediate), а потім mark_bh(IMMEDIATE_BH) для застосування у контексті переривання.
tq_disk: використовуться при низькорівневому доступі до блочних пристроїв (та RAID) для, власне, початку запитів. Ця черга завдань експортується у модулі, але не повинна використовуватись, за винятком спеціальних завдань, для яких вона була створена.

Якщо драйвер не використовує власну чергу завдань, у нього немає потреби викликати run_tasks_queues() для обробки черги, за винятком обставин, пояснених нижче.

Причина використання черг завданнь tq_timer/tq_scheduler не лише в звичайних ситуяціях, але й у інших місцях (закривання tty-пристрою є лише одним з прикладів), стає зрозумілою якщо пригадати, що драйвер може планувати завдання у черзі, і ці завдання мають смисл лише тоді, коли певний екземпляр пристрою все ще дійсний - що зазвичай означає доти, доки програма не закриє його.Отже, драйвер може потребувати викликати run_task_queue() для очистки завдань, поставлених ним (і не тільки ним) у чергу, оскільки дозвіл виконати їх пізніше може не мати смислу - наприклад, коли відповідні структури даних були вивільнені або повторно використані іншим екземпляром. З цієї причини можна зустріти run_task_queue() у tq_timer і tq_scheduler у місцях, що нє перериваннями таймера чи schedule() відповідно.

Тасклети

Ще не готово. Буде в наступній редакції.

Програмні IRQ

Ще не готово. Буде в наступній редакції.

Як реалізовано системні виклики на архітектурі i386?

У Лінуксі існує два механізми для реалізації системних викликів:

вентилі lcall7/lcall27;
програмне переривання int 0x80.

Програми, написані для Лінукса, використовують int 0x80, тоді як виконавчі програми із інших версій Юнікса (Solaris, UnixWare 7, тощо) використовують механізм lcall7. Назва 'lcall7' історично є оманливою, тому що вона також включає lcall27 (наприклад, Solaris/x86), але функція обробника називається lcall7_func.

Коли завантажується система викликається функція arch/i386/kernel/traps.c:trap_init(), яка встановлює таблицю дескрипторів переривань (IDT) так, що вектор 0x80 (тип 15, dpl 3) вказує на адресу входу в system_call із arch/i386/kernel/entry.S.

Коли програма простору користувача здійснює системний виклик, аргументи передаються через регістри і програма виконує команду «int 0x80». Це створює переривання в режимі ядра і процесор переходить до вхідної точки system_call у entry.S. Виконуються наступні кроки:

Збереження регістрів.
Встановлення DS та ES на KERNEL_DS, щоб усі посилання на дані (та додаткові сегменти) були в адресному просторі ядра.
Якщо значення EAX є більшим ніж NR_syscalls (на даний час 256), перервати виконання з сигналом помилки ENOSYS.
Якщо завдання виконуєтьсяу межах програми трасування ptrace (tsk->ptrace & PF_TRACESYS), то виконується спеціальна обробка. Це зроблено для підтримки програм типу strace (аналог truss(1) із системи Unix System V, Release 4) чи налагоджувача.
Виклик sys_call_table+4*(syscall_number із EAX). Цю таблицю ініціалізовано у тому ж файлі (arch/i386/kernel/entry.S), щоб вона вказувала на окремі обробники системних викликів, які у Лінуксі (зазвичай) мають префікс sys_, наприклад, sys_open, sys_exit, тощо. Ці C-обробники системних переривань знайдуть свої аргументи у стеку, куди їх було записано за допомогою SAVE_ALL.
Вхід у «гілку алгоритму повернення з системного виклику». Це окремий ідентифікатор, оскільки він використовується не лише перериванням int 0x80 але також lcall7 і lcall27. Це стосується обробки тасклетів (включаючи базові половини), перевірки, чи потрібен schedule() (tsk->need_resched != 0), перевірки, чи є сигнали, що очікують обробки, і якщо так, то їхньої обробки.

Linux підтримує до 6 аргументів системних викликів. Вони передаються через EBX, ECX, EDX, ESI, EDI (також тимчасово використовується EBP, дивись _syscall6() у asm-i386/unistd.h). Номер системного виклику передається через EAX.

Неподільні операції

Існує два типи неподільних операцій: bitmaps (бітові матриці) і atomic_t. Bitmaps дуже зручні для підтримки концепції «виділених» або «вільних» одиниць із деякої великої колекції, де кожна одиниця ідентифікується певним числом, наприклад, вільні іноди або вільні блоки. Вони також широко застосовуються для простого блокування, наприклад, для надання виключного доступу для відкриття пристрою. Прикладом цього є код у arch/i386/kernel/microcode.c:

/*
 *  Біти у microcode_status. (31 біт простору для майбутнього розширення)
 */
#define MICROCODE_IS_OPEN       0       /* set if device is in use */

static unsigned long microcode_status;

Немає потреби ініціалізувати microcode_status у 0, оскільки блок, що починається з символу, обнулюється у Linux явно.

/*
 * Тут у open/close примусово обмежується кількість користувачів до одного в кожен момент часу.
 */
static int microcode_open(struct inode *inode, struct file *file)
{
        if (!capable(CAP_SYS_RAWIO))
                return -EPERM;

        /* one at a time, please */
        if (test_and_set_bit(MICROCODE_IS_OPEN, &microcode_status))
                return -EBUSY;

        MOD_INC_USE_COUNT;
        return 0;
}

Існують такі операції над бітовими матрицями:

void set_bit(int nr, volatile void *addr): встановити біт nr у бітовій матриці, вказаній у addr.
void clear_bit(int nr, volatile void *addr): очистити біт nr у бітовій матриці, вказаній у addr.
void change_bit(int nr, volatile void *addr): перемикнути біт nr (якщо встановлено - очистити, якщо очищено — встановити) у бітовій матриці, вказаній у addr.
int test_and_set_bit(int nr, volatile void *addr): нероздільна операція, що встановлює біт nr і повертає попереднє значення біту.
int test_and_clear_bit(int nr, volatile void *addr): нероздільна операція, що очищає біт nr і повертає попереднє значення біту.
int test_and_change_bit(int nr, volatile void *addr): нероздільна операція, що перемикає біт nr і повертає попереднє значення біту.

Ці операції використовують макрос LOCK_PREFIX, який у багатопроцесорних ядрах є еквівалентом префіксу інструкції блокування шини та ігнорується на однопроцесорній платформі. Це гарантує неподільність доступу у багатопроцесорному середовищі.

Деколи маніпуляції з бітами є незручними, але натомість нам треба виконати арифметичні операції — додавати, віднімати, інкрементувати і декрементувати. Типовими випадками є лічильники посилань (наприклад, для інодів). Такі можливості надають тип даних atomic_t та наступні операції:

atomic_read(&v): зчитати значення змінної v типу atomic_t.
atomic_set(&v, i): присвоїти значення значення цілого i змінній v типу atomic_t.
void atomic_add(int i, volatile atomic_t *v): додати ціле i до значення змінної v типу atomic_t.
void atomic_sub(int i, volatile atomic_t *v): відняти ціле i від значення змінної v типу atomic_t.
int atomic_sub_and_test(int i, volatile atomic_t *v): відняти ціле i від змінної v типу atomic_t; повернути 1, якщо нове значення дорівнює 0, в іншому випадку повернути 0.
void atomic_inc(volatile atomic_t *v): інкрементувати значення на 1.
void atomic_dec(volatile atomic_t *v): декрементувати значення на 1.
int atomic_dec_and_test(volatile atomic_t *v): декрементувати значення; повернути 1, якщо нове значення дорівнює 0, в іншому випадку повернути 0.
int atomic_inc_and_test(volatile atomic_t *v): інкрементувати значення; повернути 1, якщо нове значення дорівнює 0, в іншому випадку повернути 0.
int atomic_add_negative(int i, volatile atomic_t *v): додати значення i до значення v і повернути 1, якщо результат негативний. Повернути 0, якщо результат рівний або більший 0. Ця операція використовується для реалізації семафорів.

Спін-блокування, спін-блокування зчитування/запису та спін-блокування типу Big-Reader

З перших днів існування Linux (початок 90-х минулого століття), розробники стикались з класичною проблемою доступу до даних, розділених між різними типами контекстів (процес користувача проти контексту переривання) та різними екземплярами одного контексту з багатьох процесорів.

Підтримку багатопроцесорності було додано в Linux 1.3.42 15-го листопада 1995 (оригінальне доповнення для версії 1.3.37 випустили у жовтні цього ж року).

Якщо критична частина коду може виконуватьсь у контексті будь-якого процесу чи в контексті переривання, то для захисту його на однопроцесорних системах застосовують команди cli/sti наступним чином:

unsigned long flags;

save_flags(flags);
cli();
/* critical code */
restore_flags(flags);

Якщо це проходить на однопроцесорних системах, то, очевидно, що це не допоможе на багатопроцесорних системах, оскільки та сама послідовність коду може виконуватись одночасно на іншому процесорі, і в той час як cli() забезпечує захист від «перегонів» з контекстом переривання на кожному процесорі окремо, то немає жодного захисту від перегонів контекстів, що виконуються на різних процесорах. Саме для цього застосовується спін-блокування.

Існують три типи спін-блокування: vanilla (основний), зчитування-запису та спін-блокування типу big-reader. Спін-блокування зчитування-запису слід використовуватитоді, коли працюють багато програм зчитування і незначна кількість програм запису. Прикладом може бути доступ до списку зареєстрованих файлових систем (див. fs/super.c). Список захищено за допомогою спін-блокування зчитування-запису file_systems_lock, оскільки виключний доступ потрібний лише при реєстрації/дереєстрації файлової системи, але будь-який процес може читати файл /proc/filesystems чи використовувати системний виклик ?sysfs(2) для примусового сканування списку file_systems. Саме цим зумовлена практичність використання спін-блокування зчитування-запису. Використання даного типу блокування дозволяє мати багато програм зчитування, але тільки одну програму запису в кожен момент часу, причому, зчитування стає неможливим у момент запису. До речі, було б добре, якби нові програми зчитування не отримували право на блокування, якщо таке право потрібне в даний момент програмі запису, тобто, якби Лінукс міг коректно працювати з проблемою потенційного "зависання" програми запису через численні програми зчитування. Це б означало, що програми зчитування примусово блокувались би, якщо програма запису намагається здійснити блокування. На даний час це не є головним, а також не ясно чи варто це виправляти - аргументом проти є те, що програми зчитування, як правило, вмикають блокування на дуже корокий відрізок часу, отже, чи повинні вони насправді «зависати», поки програма запису здійснює блокування на потенційно довший час?

Спін-блокування типу big-reader є різновидом спін-блокування зчитування-запису, значно оптимізованого для дуже швидкого доступу при зчитуванні за рахунок сповільнення доступу на запис. Кількість спін-блокувань типу big-reader обмежена — на даний час лише два, один з яких використовується виключно на архітектурі SPARC64 (глобальний IRQ), а інший застосовується для роботи з мережею. В усіх інших випадках, коли модель доступу не вписується в жоден з цих сценаріїв, слід застосовувати базове спін-блокування. Не можна блокувати, якщо використовується будь-яке з спін-блокувань.

Спін-блокування бувають трьох типів: просте, irq() та bh().

Просте spin_lock()/spin_unlock(): якщо відомо, що переривання завжди відключено, або відсутня конкуренція з контекстом переривання (наприклад, з обробника переривань), тоді можна використовувати цей тип. Він не впливає на стан переривання на даному процесорі.
spin_lock_irq()/spin_unlock_irq(): якщо відомо, що переривання завжди ввімкнено, тоді можна застосувати цей тип, який просто відмикає (при блокуванні) та знову вмикає (при розблокуванні) переривання на даному процесорі. Наприклад, rtc_read() використовує spin_lock_irq(&rtc_lock) (переривання завжди ввімкнено у межах read()), тоді як rtc_interrupt() використовує spin_lock(&rtc_lock) (переривання завжди вимкнуто у межах обробника переривань). Зауважте, що rtc_read() використовує spin_lock_irq(), а не загальніший spin_lock_irqsave(), оскільки при вході у будь-який системний виклик переривання завжди вмикаються.
spin_lock_irqsave()/spin_unlock_irqrestore(): найсильніша форма, яку використовують, коли стан переривань невідомий, але якщо переривання мають значення взагалі, тобто, немає смислу використовувати їх, ящо обробники переривань не виконують жодного критичного коду.

Причиною того, що не можна використати простий spin_lock() при наявній конкуренції з обробниками переривань є те, що якщо при використанні spin_lock() на той самий процесор надійде переривання, він очікуватиме блокування безконечно: перерваний ініціатор блокування не продовжить роботу, поки обробник переривання не поверне керування.

Найчастіше спін-блокування використовується при доступі до структури даних, розділеної між контекстом процесу користувача та обробниками переривань:

spinlock_t my_lock = SPIN_LOCK_UNLOCKED;

my_ioctl()
{
        spin_lock_irq(&my_lock);
        /* critical section */
        spin_unlock_irq(&my_lock);
}

my_irq_handler()
{
        spin_lock(&lock);
        /* critical section */
        spin_unlock(&lock);
}

У цьому прикладі варто звернути увагу на наступне:

Контекст процесу, представлений тут як типовий метод драйвера - ioctl() (аргументи виклику та значення, що повертаються, опущено для спрощення), повинен використоввувати spin_lock_irq(), оскільки відомо, що переривання завжди ввімкнено під час виконання методу ioctl().
Контекст переривання, представлений тут як my_irq_handler() (знову аргументи опущено для простоти) може використовувати простий spin_lock(), оскільки переривання відключено в межах обробника переривань.

Семафори та семафори зчитування-запису

Інколи, під час доступу до розділеної структури даних необхідно виконати операції, які можуть блокувати, наприклад, копіювання даних у простір користувача. Блокуючий примітив, призначений для таких сценаріїв у Linux називається семафором. Існує два типи семафорів: базовий та семафор зчитування-запису. Залежно від початкового значення семафору вони можуть використовуватись або для взаємного виключення (початкове значення 1), або для забезпечення складнішого типу доступу.

Семафори зчитування-запису відрізняються від базових семафорів так само, як і спін-блокування зчитування-запису відрізняється від базового спін-блокування: допустимими є кілька програм зчитування в кожен момент часу, але тільки одна програма запису; також при роботі програми запису заборонено доступ на зчитування, тобто, програма запису блокує всі програми зчитування і нові програми зчитування здійснюють блокування, коли програма запису очікує.

Також базові семафори можна переривати — для цього просто використовують операції down/up_interruptible() замість простих down()/up() і перевіряють значення, що повертається з down_interruptible(): воно відрізнятиметься від нуля, якщо операцію було перервано.

Застосування семафорів для взаємного виключення є ідеальним в ситуаціях, коли критична секція коду може викликати за посиланням невідомі функції, зареєстровані іншими підсистемами/модулями, тобто, програма, яка здійснює виклик, не знає наперед, блокує функція чи ні.

Простий приклад використання семафорів є в kernel/sys.c, в реалізації системних викликів ?gethostname(2)/?sethostname(2).

asmlinkage long sys_sethostname(char *name, int len)
{
        int errno;

        if (!capable(CAP_SYS_ADMIN))
                return -EPERM;
        if (len < 0 || len > __NEW_UTS_LEN)
                return -EINVAL;
        down_write(&uts_sem);
        errno = -EFAULT;
        if (!copy_from_user(system_utsname.nodename, name, len)) {
                system_utsname.nodename[len] = 0;
                errno = 0;
        }
        up_write(&uts_sem);
        return errno;
}

asmlinkage long sys_gethostname(char *name, int len)
{
        int i, errno;

        if (len < 0)
                return -EINVAL;
        down_read(&uts_sem);
        i = 1 + strlen(system_utsname.nodename);
        if (i > len)
                i = len;
        errno = 0;
        if (copy_to_user(name, system_utsname.nodename, i))
                errno = -EFAULT;
        up_read(&uts_sem);
        return errno;
}

У цьому прикладі слід зауважити наступне:

Функції можуть блокувати під час копіювання даних з/у простір користувача у copy_from_user() / copy_to_user(). Отже, вони не можуть використовувати тут спін-блокування жодного типу.
Вибрано тип семафору читання-запису як протилежний до базового, оскільки можливі численні одночасні запити ?gethostname(2), які не обов'язково будуть взаємно виключними.

Хоча реалізація семафорів та семафорів зчитування-запису у Лінуксі є дуже складною, можна уявити собі такі сценарії, які ще не реалізовано, наприклад, немає концепції семафорів зчитування-запису, які можна переривати. Очевидно, це через те, що немає реальних ситуацій, які вимагають таких екзотичних особливостей даних примітивів.

Підтримка ядром завантаження модулів

Лінукс є монолітною операційною системою і незважаючи на всю цю сучасну метушню з деякими «перевагами», які нібито надають операційні системи, що грунтуються на мікроядерній архітектурі, правдою залишається те, що (цитуючи самого Лінуса Торвальдса):

«... передача повідомлення як фундаментальна процедура операційної системи є лише вправлянням у комп'ютерній мастурбації. Вона може здаватись доброю, але насправді не робить нічого.»

Отже, Linux є і завжди буде ґрунтуватись на монолітній моделі, що означає, що всі підсистеми виконуються у тому ж режимі з однаковими привілеями та розділяють той самий простір адрес; зв'язок між ними досягається за допомогою звичайних засобів виклику функцій мови С.

Проте, хоча розділення функцій ядра на окремі «процеси», як це робиться у мікроядрах, однозначно не найкращий варіант, розділення їх на динамічно завантажувані при потребі модулі ядра є бажаним за певних обставин (наприклад, у машинах з малим об'ємом пам'яті або для інсталяції ядер, які в іншому випадку моуть містити драйвери автотестування шини ISA, які є взаємовиключними). Рішення щодо включення підтримки завантажуваних модулів у ядро приймається під час компіляції й визначається опцією CONFIG_MODULES. Підтримка автозавантаження модулів через механізм request_module() є окремою опцією компіляції (CONFIG_KMOD).

У Лінуксі у вигляді завантажуваних модулів можна реалізувати наступні функції:

Різноманітні драйвери символьних та блочних пристроїв.
Порядок обслуговування термінальної лінії.
Віртуальні (звичайні) файли в /proc та у devfs (наприклад, /dev/cpu/microcode проти /dev/misc/microcode).
Файли двійкового формату (наприклад, ELF, aout, тощо).
Домени виконання (тобто, Лінукс, UnixWare7, Solaris та інші).
Файлові системи.
Міжпроцесний зв'язок IPC, притаманний System V.

Деякі речі у Лінуксі не можна реалізувати у вигляді модулів (мабуть тому, що немає сенсу робити їх у вигляді модулів):

Алгоритми планування.
Керування віртуальною пам'яттю.
Буферний кеш, сторінковий кеш та інші види кешів.

Для полегшення завантаження модулів у Лінуксі створено кілька системних викликів:

caddr_t create_module(const char *name, size_t size): виділяє size байтів застосовуючи vmalloc() і розміщує структуру модуля на початку виділеного простору. Потім цей новий модуль прив'язується до списку, позначеного як module_list. Цей системний виклик може здійснити лише процес з CAP_SYS_MODULE; усім іншим буде повернуто EPERM.
long init_module(const char name, struct module image): завантажує переміщуваний образ модуля та активізує підпрограму ініціалізації модуля. Тільки процес з CAP_SYS_MODULE може здійснити цей системний виклик. Усім іншим буде повернуто EPERM.
long delete_module(const char *name): намагається вивантажити модуль. Якщо name = NULL, то робиться спроба вивантажити всі невикористовувані модулі.
long query_module(const char name, int which, void buf, size_t bufsize, size_t *ret): повертає інформацію про модуль (або про всі модулі).

Доступний користувачу командний інтерфейс складається з:

insmod: вставити один модуль;
modprobe: вставити модуль, включаючи всі модулі від яких він залежить;
rmmod: видалити модуль;
modinfo: вивести деяку інформацію про модуль, наприклад, автора, опис, параметри що їх сприймає модуль, тощо.

Крім можливості завантажувати модулі вручну використовуючи insmod або modprobe, існує можливість вставки модуля ядром автоматично, коли виникає потреба у певних функціях. Для цього у ядра є функція request_module(name), яка експортується у модулі, щоб модулі також могли завантажувати інші модулі. request_module(name) створює в межах ядра підпроцес, який виконує команду простору користувача modprobe -s -k module_name, застосовуючи стандартний інтерфейс ядра exec_usermodehelper() (який також експортується у модулі). Функція повертає 0 при успішному завершенні, проте, зазвичай, не варто перевіряти код, повернений із request_module(). Натомість, існує програмна ідіома:

if (check_some_feature() == NULL)
    request_module(module);
if (check_some_feature() == NULL)
    return -ENODEV;

Наприклад, цей код виконується у fs/block_dev.c:get_blkfops() для завантаження модуля block-major-N, коли здійснюється спроба відкрити блочний пристрій з найвищим значенням N. Очевидно, що немає модуля з ім'ям block-major-N (розробники Linux для своїх модулів вибирають лише практичні імена), але він вказує на правильне ім'я модуля, застосовуючи файл /etc/modules.conf. Проте, для більшості добре відомих номерів major (та інших типів модулів), команди modprobe/insmod знають, який реальний модуль завантажувати без потреби явного оголошення псевдоніма у /etc/modules.conf.

Хороший приклад завантаження модуля можна знайти у системному виклику ?mount(2). Цей виклик приймає тип файлової системи як рядок, який згодом fs/super.c:do_mount() передає до fs/super.c:get_fs_type():

static struct file_system_type *get_fs_type(const char *name)
{
        struct file_system_type *fs;

        read_lock(&file_systems_lock);
        fs = *(find_filesystem(name));
        if (fs && !try_inc_mod_count(fs->owner))
                fs = NULL;
        read_unlock(&file_systems_lock);
        if (!fs && (request_module(name) == 0)) {
                read_lock(&file_systems_lock);
                fs = *(find_filesystem(name));
                if (fs && !try_inc_mod_count(fs->owner))
                        fs = NULL;
                read_unlock(&file_systems_lock);
        }
        return fs;
}

Щодо цієї функції варто зауважити наступне:

Спершу здійснюється спроба знайти файлову систему з даним ім'ям серед уже зереєстрованих файлових систем. Це виконується під захистом file_systems_lock, ввімкненого в режимі зчитування (оскільки ми не змінюємо список зареєстрованих файлових систем).
Якщо таку систему знайдено, то здійснюється спроба отримати новий вказівник на неї, інкрементуючи лічильник посилань модуля. Для статично зв'язаних файлових систем або для для модулів, які не знищуються зараз завжди повертається 1. Якщо try_inc_mod_count() повертає 0, то ми вважаємо це помилкою - наприклад, якщо модуль є, але він знищується; це все одно, що його там зовсім немає.
Відмикається file_systems_lock, оскільки наступна дія (request_module()) є блокуючою операцією, і, отже, ми не можемо виконувати її під захистом спін-блокування. По-суті, у цьому частковому випадку, нам би все одно довелось відключити file_systems_lock, навіть якщо б request_module() був неблокуючим і завантаження модуля виконувалось неподільно у тому ж контексті. Пояснюється це тим, що функція ініціалізації модуля намагатиметься викликати register_filesystem(), що ввімкне те саме спін-блокування file_systems_lock в режимі запису.
Якщо спроба завантаження завершилась успішно, то вмикається спін-блокування file_systems_lock і виконується спроба розмістити щойно зареєстровану файлову систему в списку. Зауважте, що це не зовсім правильно, оскільки існує принципова можливість того, що помилка у команді modprobe спричинить аварійне вивантаження вмісту пам'яті ядра після успішного завантаження потрібного модуля, і в цьому випадку request_module() зазнає збою, навіть якщо нову файлову систему буде зареєстровано, а get_fs_type() все-таки не знайде її.
Якщо файлову систему знайдено і можна отримати посилання на неї, то функція повертає це посилання. В іншому випадку повертається NULL.

Коли модуль завантажено в ядро, він може звертатися до будь-яких символів, експортованих ядром або іншими завантаженими модулями як public, використовуючи макрос EXPORT_SYMBOL(). Якщо модуль використовує символи із іншого модуля, він позначається як такий, що залежить від цього іншого модуля під час перерахування залежностей, що досягається виконанням команди depmod -a при завантаженні (наприклад, після встановлення нового ядра).

Як правило, необхідно узгоджувати набір модулів з версією використовуваного ними інтерфейсу ядра, що у Лінуксі просто означає «версією ядра», оскільки взагалі не існує спеціального механізму визначення версій інтерфейсу ядра. Проте існує обмежений механізм, що називається «контроль версій модулів» або CONFIG_MODVERSIONS, що дозволяє уникнути перекомпіляції модулів при переході до нового ядра. У цьому випадку таблиця символів ядра обробляється по-різному для внутрішнього доступу і для доступу з модулів. Елементи публічної (тобто експортованої) частини таблиці символів будуються за допомогою 32-бітної контрольної суми C-оголошення. Отже, для того щоб отримати символ, що використовується модулем під час завантаження, завантажувач повинен відповідно представити повне відображення символу, включаючи контрольну суму; він відмовить у завантажуванні модуля якшщо ці символи відрізняються. Ця перевірка відбувається лише тоді, коли і ядро і модуль скомпільовано з підтримкою контролю версій модулів. Якщо хоча б один із них використовує оригінальні символьні імена, завантажувач просто намагається поставити у відповідність версію ядра, оголошену модулем, версії експортованій ядром, і відмовляє у завантаженні, якщо вони різняться.