Linux Kernel (Ядро линукса) (часть 1)

Структуры данных для динамических таймеров

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

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

Основной структурой данных для динамических таймеров является процессорная переменная по имени tvec bases. Она состоит из nr cpus элементов, по одному на каждый процессор в системе. Каждый элемент является структурой tvec base t, которая содержит все данные, необходимые для работы с динамическими таймерами, привязанными к соответствующему процессору:
typedef struct tvec_t_base_s { spinlock_t lock;
unsigned long timer_jiffies;
struct timer_list running_timer;
tvec_root_t tvl;
tvec_t tv2;
tvec_t tv3;
tvec_t tv4;
tvec_t tv5;
} tvec_base_t;
Поле tvl является структурой типа tvec root t, которая включает в себя массив vec из 256 элементов list head, т. е. из списков динамических таймеров. Это поле содержит все динамические таймеры, время которых истечет в ближайшие 255 тиков, если таковые имеются.

Поля tv2, tv3 и tv4 являются структурами типа tvec t, каждая из которых включает в себя массив vec из 64 элементов list head. Эти списки содержат все динамические таймеры, время которых истечет в ближайшие 214—1, 220-1 и 226-1 тиков соответственно.

Поле tv5 идентично предыдущим, но у него последний элемент массива vec является списком динамических таймеров с очень большими значениями в полях expires. Этот список никогда не пополняется таймерами из других массивов. Поле timer jiffies представляет ближайшее время срабатывания динамических таймеров, которое подлежит отслеживанию. Если оно совпадает со значением jiffies, значит, никакого скопления незавершенных заданий или функций отложенного выполнения не наблюдается. Если же оно меньше jiffies, значит, необходимо обработать списки динамических таймеров, время которых истекло на предыдущих тиков. Это поле инициализируется значением jiffies при запуске системы и увеличивается только функцией run_timer_softirq(), описанной в следующем разделе. Обратите внимание, что поле timer jiffies может очень сильно отстать от значения jiffies, если функции, обрабатывающие динамические таймеры, не выполнялись долгое время (например, из-за того, что они были отключены, или было выполнено много обработчиков прерываний).
В многопроцессорных системах поле running timer указывает на структуру timer iist, содержащую динамические таймеры, с которыми в данный момент имеет дело локальный процессор.