В предыдущей своей статье я затронула тему многопоточности. В ней речь шла о базовых понятиях: о типах многозадачности, планировщике, стратегиях планирования, машине состояний потока и прочем.
На этот раз я хочу подойти к вопросу планирования с другой стороны. А именно, теперь я постараюсь рассказать про планирование не потоков, а их “младших братьев”. Так как статья получилась довольно объемной, в последний момент я решила разбить ее на несколько частей:
- Многозадачность в ядре Linux: прерывания и tasklet’ы
- Многозадачность в ядре Linux: workqueue
- Protothread и кооперативная многозадачность
В третьей части я также попробую сравнить все эти, на первый взгляд, разные сущности и извлечь какие-нибудь полезные идеи. А через некоторое время я расскажу про то, как нам удалось применить эти идеи на практике в проекте Embox, и про то, как мы запускали на маленькой платке нашу ОС с почти полноценной многозадачностью.
Рассказывать я постараюсь подробно, описывая основное API и иногда углубляясь в особенности реализации, особо заостряя внимание на задаче планирования.
Прерывания и их обработка
Аппаратное прерывание (IRQ) — это внешнее асинхронное событие, которое поступает от аппаратуры, приостанавливает ход программы и передает управление процессору для обработки этого события. Обработка аппаратного прерывания происходит следующим образом:
- Приостанавливается текущий поток управления, сохраняется контекстная информация для возврата в поток.
- Выполняется функция-обработчик (ISR) в контексте отключенных аппаратных прерываний. Обработчик должен выполнить действия, необходимые для данного прерывания.
- Оборудованию сообщается, что прерывание обработано. Теперь оно сможет генерировать новые прерывания.
- Восстанавливается контекст для выхода из прерывания.
Функция-обработчик может быть достаточно большой, что непозволительно с учетом того, что выполняется она в контексте отключенных аппаратных прерываний. Поэтому придумали делить обработку прерываний на две части (в Linux они называются top-half и bottom-half):
- Непосредственно ISR, которая вызывается при прерывании, выполняет только самую минимальную работу, которую невозможно отложить на потом: она собирает информацию о прерывании, необходимую для последующей обработки, как-то взаимодействует с аппаратурой и планирует вторую часть.
- Вторая часть, где выполняется основная обработка, запускается уже в другом контексте процессора, где аппаратные прерывания разрешены. Вызов этой части обработчика будет совершен позже.
Так мы подошли к отложенной обработке прерываний. В Linux для этих целей используются tasklet и workqueue.
Tasklet
Если коротко, то tasklet — это что-то вроде очень маленького потока, у которого нет ни своего стека, ни контекста. Такие “потоки” отрабатывают быстро и полностью. Основные особенности tasklet’ов:
- tasklet’ы атомарны, так что из них нельзя использовать sleep() и такие примитивы синхронизации, как мьютексы, семафоры и прочее. Но, например, spinlock (крутящуюся блокировку) использовать можно;
- вызываются в более “мягком” контексте, чем ISR. В этом контексте разрешены аппаратные прерывания, которые вытесняют tasklet’ы на время исполнения ISR. В ядре Linux этот контекст зовется softirq, и помимо запуска tasklet’ов, он используется еще несколькими подсистемами;
- tasklet исполняется на том же ядре, что и планирует его. А точнее, успело запланировать его первым, вызвав softirq, обработчики которого всегда привязаны к вызывающему ядру;
- разные tasklet’ы могут выполняться параллельно, но при этом сам с собой он одновременно не вызывается, поскольку исполняется только на одном ядре, первым запланировавшим его исполнение;
- tasklet’ы выполняются по принципу невытесняющего планирования, один за другим, в порядке очереди. Можно планировать с двумя разными приоритетами: normal и high.
Заглянем же теперь “под капот” и посмотрим, как они работают. Во-первых, сама структура tasklet (определяемая в <linux/interrupt.h>):
struct tasklet_struct
{
struct tasklet_struct *next; /* Следующий tasklet в очереди на планирование */
unsigned long state; /* TASKLET_STATE_SCHED или TASKLET_STATE_RUN */
atomic_t count; /* Отвечает за то, активирован tasklet или нет */
void (*func)(unsigned long); /* Основная функция tasklet’а */
unsigned long data; /* Параметр, с которым запускается func */
};
Прежде, чем пользоваться tasklet’ом, его сначала нужно инициализировать:
/* По умолчанию tasklet активирован */
void tasklet_init(struct tasklet_struct *t, void (*func)(unsigned long), unsigned long data);
DECLARE_TASKLET(name, func, data);
DECLARE_TASKLET_DISABLED(name, func, data); /* деактивированный tasklet */
Планируются tasklet’ы просто: tasklet помещается в одну из двух очередей в зависимости от приоритета. Очереди организованы как односвязные списки. Причем, у каждого CPU эти очереди свои. Делается это с помощью функций:
void tasklet_schedule(struct tasklet_struct *t); /* с нормальным приоритетом */
void tasklet_hi_schedule(struct tasklet_struct *t); /* с высоким приоритетом */
void tasklet_hi_schedule_first(struct tasklet_struct *t); /* вне очереди */
Когда tasklet запланирован, ему выставляется состояние TASKLET_STATE_SCHED, и он добавляется в очередь. Пока он находится в этом состоянии, запланировать его еще раз не получится — в этом случае просто ничего не произойдет. Tasklet не может находиться сразу в нескольких местах в очереди на планирование, которая организуется через поле next структуры tasklet_struct. Это, впрочем, справедливо для любых списков, связанных через поле объекта, как, например, <linux/list.h>.
На время исполнения tasklet’у присваивается состояние TASKLET_STATE_RUN. Кстати, из очереди tasklet достается перед своим исполнением, а состояние TASKLET_STATE_SCHED снимается, то есть, его можно запланировать снова во время его исполнения. Это может сделать как он сам, так и, к примеру, прерывание на другом ядре. В последнем случае, правда, вызван он будет только после того, как он закончит свое исполнение на первом ядре.
Довольно интересно, что tasklet можно активировать и деактивировать, причем рекурсивно. За это отвечают следующие функции:
void tasklet_disable_nosync(struct tasklet_struct *t); /* деактивация */
void tasklet_disable(struct tasklet_struct *t); /* с ожиданием завершения работы tasklet’а */
void tasklet_enable(struct tasklet_struct *t); /* активация */
Если tasklet деактивирован, его по-прежнему можно добавить в очередь на планирование, но исполняться на процессоре он не будет до тех пор, пока не будет вновь активирован. Причем, если tasklet был деактивирован несколько раз, то он должен быть ровно столько же раз активирован, поле count в структуре как раз для этого.
А еще tasklet’ы можно убивать. Вот так:
void tasklet_kill(struct tasklet_struct *t);
Причем, убит он будет только после того, как tasklet исполнится, если он уже запланирован. Если вдруг tasklet планирует сам себя, то нужно перед вызовом этой функции не забыть запретить ему это делать — это на совести программиста.
Интереснее всего функции, которые играют роль планировщика:
static void tasklet_action(struct softirq_action *a);
static void tasklet_hi_action(struct softirq_action *a);
Так как они практически одинаковые, то нет смысла приводить код обеих функций. Но вот на одну из них стоит взглянуть, чтобы разобраться поподробнее:
static void tasklet_action(struct softirq_action *a)
{
struct tasklet_struct *list;
local_irq_disable();
list = __this_cpu_read(tasklet_vec.head);
__this_cpu_write(tasklet_vec.head, NULL);
__this_cpu_write(tasklet_vec.tail, &__get_cpu_var(tasklet_vec).head);
local_irq_enable();
while (list) {
struct tasklet_struct *t = list;
list = list->next;
if (tasklet_trylock(t)) {
if (!atomic_read(&t->count)) {
if (!test_and_clear_bit(TASKLET_STATE_SCHED, &t->state))
BUG();
t->func(t->data);
tasklet_unlock(t);
continue;
}
tasklet_unlock(t);
}
local_irq_disable();
t->next = NULL;
*__this_cpu_read(tasklet_vec.tail) = t;
__this_cpu_write(tasklet_vec.tail, &(t->next));
__raise_softirq_irqoff(TASKLET_SOFTIRQ);
local_irq_enable();
}
}
Обратите внимание на вызов функций tasklet_trylock() и tasklet_lock(). tasklet_trylock() выставляет tasklet’у состояние TASKLET_STATE_RUN и тем самым блокирует tasklet, что предотвращает исполнение одного и того же tasklet’а на разных CPU.
Эти функции-планировщики, по сути, реализуют кооперативную многозадачность, которую я подробно рассматривала в своей статье. Функции регистрируются как обработчики softirq, который инициируется при планировании tasklet’ов.
Реализацию всех вышеописанных функций можно посмотреть в файлах include/linux/interrupt.h и kernel/softirq.c.
Продолжение следует
В следующей части я расскажу о гораздо более мощном механизме — workqueue, который также часто используется для отложенной обработки прерываний.
P.S. На правах рекламы. Ещё я хочу пригласить всех, кому интересен наш проект, на встречу, организованную codefreeze.ru (анонс на хабре). На ней можно будет пообщаться вживую, задать интересующие вопросы главному злодею abondarev и покритиковать в лицо, в конце концов :)
Автор: LifeV
