Embox
Компания
38,96
рейтинг
24 ноября 2014 в 20:59

Разработка → Многозадачность в ядре Linux: прерывания и tasklet’ы

Котейка и младшие братьяВ предыдущей своей статье я затронула тему многопоточности. В ней речь шла о базовых понятиях: о типах многозадачности, планировщике, стратегиях планирования, машине состояний потока и прочем.

На этот раз я хочу подойти к вопросу планирования с другой стороны. А именно, теперь я постараюсь рассказать про планирование не потоков, а их “младших братьев”. Так как статья получилась довольно объемной, в последний момент я решила разбить ее на несколько частей:
  1. Многозадачность в ядре Linux: прерывания и tasklet’ы
  2. Многозадачность в ядре Linux: workqueue
  3. Protothread и кооперативная многозадачность

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

Рассказывать я постараюсь подробно, описывая основное API и иногда углубляясь в особенности реализации, особо заостряя внимание на задаче планирования.

Прерывания и их обработка


Аппаратное прерывание (IRQ) — это внешнее асинхронное событие, которое поступает от аппаратуры, приостанавливает ход программы и передает управление процессору для обработки этого события. Обработка аппаратного прерывания происходит следующим образом:
  1. Приостанавливается текущий поток управления, сохраняется контекстная информация для возврата в поток.
  2. Выполняется функция-обработчик (ISR) в контексте отключенных аппаратных прерываний. Обработчик должен выполнить действия, необходимые для данного прерывания.
  3. Оборудованию сообщается, что прерывание обработано. Теперь оно сможет генерировать новые прерывания.
  4. Восстанавливается контекст для выхода из прерывания.

Функция-обработчик может быть достаточно большой, что непозволительно с учетом того, что выполняется она в контексте отключенных аппаратных прерываний. Поэтому придумали делить обработку прерываний на две части (в Linux они называются top-half и bottom-half):
  • Непосредственно ISR, которая вызывается при прерывании, выполняет только самую минимальную работу, которую невозможно отложить на потом: она собирает информацию о прерывании, необходимую для последующей обработки, как-то взаимодействует с аппаратурой, например, блокирует или очищает IRQ от устройства (спасибо jcmvbkbc и Zyoma за уточнение) и планирует вторую часть.
  • Вторая часть, где выполняется основная обработка, запускается уже в другом контексте процессора, где аппаратные прерывания разрешены. Вызов этой части обработчика будет совершен позже.

Так мы подошли к отложенной обработке прерываний. В 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
Embox
рейтинг 38,96
Компания прекратила активность на сайте

Комментарии (31)

  • +21
    Крайне неожиданно видеть женский род в прошедшем времени в статьях про Linux. Но, здорово. Так держать.
  • –14
    Я хочу от Вас детей =)
    • +7
      Лучше бы по сути что-нибудь написали, статья то на черезвычайно редкую тему, материал на вес золота.
      Я прямо сейчас не могу читать к сожалению, пометил на будущее
    • +16
  • +5
    Спасибо, крайне интересно.
    Очень напоминает книгу «Недокументированные возможности Win 2k» Свена Шрайбера.
    Она была кладезем информации в свое время.
  • +3
    Огромное спасибо за статью!
  • НЛО прилетело и опубликовало эту надпись здесь
    • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Да, ещё: ну почему они называются 'bottom' и 'top'? (Я про прерывания) Я всё время путаюсь, какой из них «настоящий», а какой softirq.
    • +3
      почему они называются 'bottom' и 'top'

      Подозреваю, что это связано с текущим уровнем запрета прерываний: если уровень высокий (прерывания запрещены) — это top half, если уровень низкий (прерывания разрешены) — это bottom half.

      Я всё время путаюсь, какой из них «настоящий», а какой softirq

      В ядре есть примитивы синхронизации со словом _bh (spin_lock_bh, например), но нет ни одного со словом _th, вместо этого используется _irq (spin_lock_irq, например).
      • +2
        По поводу происхождения названия bottom half, вроде история была такая, что механизм отложенной обработки под изначальным названием softirq (тогда еще не было tasklet'ов) первым решил преминуть Теодор Тсо, а Линус заявил что не примет в ядро то, что имеет название softirq, поэтому Тед решил назвать механизм отложенной обработки иначе и придумал термины top и bottom, в соответствии с логикой которую Вы описали выше.
      • 0
        Спасибо. В таком виде оно логично звучит.
    • +5
      Выше уже предложили версию, но у меня есть подозрение, что все проще.
      Когда мы говорим про верх и низ страницы, мы говорим top и bottom. Если представить, что мы функцию поделим на две части, то верхняя, что будет исполняться раньше, — это top, а нижняя — bottom.
      • +4
        Объяснение выше мне понравилось, ваше — нет. Потому что исходя из «low level details» чем ближе к железу, тем ниже, то есть обработчик «самого важного» должен быть bottom-half.
  • +3
    Как же так, топик про tasklet-ы в ядре Linux, а здесь забыли упомянуть эпичную фразу про «плохую водку» из документации %)
    The name 'tasklet' is misleading: they have nothing to do with 'tasks', and probably more to do with some bad vodka Alexey Kuznetsov had at the time.


    Вообще документация к ядру меня в своё время очень порадовала, написано людьми для людей.
    • +2
      В разделе Tasklet, в тегэ abbr (наведите на слово tasklet, подчеркнутое и выделенное полужирным).
    • +6
      На самом деле не забыли, если вы наведете на слово tasklet, то во всплывающей подсказке увидите именно эту цитату. Своего рода пасхалка :)

      Читать ядро Linux и правда очень приятно.
      • +1
        Код ядра во многих местах пасхалка. Когда переписывал драйвер одной сетевой железки с 1.х на 2.х прямо плакал от того, что коду-то подевались смешные комменты, веселые локальные переменные. Мне кажется именно тогда, процент форфан дядь начал разбавляться корпоративными профи. Так что колическтво веселых пасхалок начало падать, и заменяться скрытыми бэкдорами.
        • 0
          Про бэкдоры поподробней?
          • 0
            А что там подробнее — смотрите на секюрити патчи. Затронутый исходный код иногда выглядит подозрительно. Как-то за пивом был спор о статических анализаторах — тогда и наслушался о подобных случаях.
            • 0
              Впервые слышу о намеках, что «корпоративные профи» (а не какой-то там NSA) делают бэкдоры в коде Linux'а, поэтому и спросил, может есть ссылки что кого-то конкретно «поймали».
              • 0
                Я с 2001 не интересуюсь этой темой. Но в драйвере синхронного ван адаптера одной российской фирмы не было проверок поступающих данных как класса. То есть с другой стороны можно было сформировать не правильный поток и взломать систему. Не думаю, что это было сделано специально — но…
  • –1
    spinlock (крутящуюся блокировку)
    И вокруг чего она крутится? :-) Это всё же циклическая блокировка. Как вариант — взаимная блокировка.
    • +3
      вокруг чего она крутится

      Вокруг проверки условия, что текущему процессору можно выполнять свою работу.

      Как вариант — взаимная блокировка.

      Взаимная блокировка (deadlock) — это совсем другая ситуация.
    • 0
      Если погуглить, то такой перевод тоже встречается, по-моему, именно его я впервые в университете и услышала.
      Но укажу тогда в скобочках и этот вариант, раз вопросы возникают.
  • +2
    В этом контексте разрешены аппаратные прерывания, которые вытесняют tasklet’ы на время исполнения ISR

    Как они вытесняются, если у них нет стека и контекста? Или имеется ввиду работа «между» тасклетами?
    • +3
      Аппаратные прерывания асинхронны, они могут произойти в любой момент, в том числе в середине tasklet'а, и ISR, соответственно, обрабатывается сразу же.
      Своего собственного стека у них нет, но на каком-то стеке они все же должны исполняться, так что после обработки ISR есть, какой контекст восстанавливать. В Linux (как минимум в x86), например, перед началом обработки softirq происходит переключение на специально выделенный стек.
  • +6
    Отлично написано, спасибо. «Ядро Linux. Описание процесса разработки» Р. Лава помогает разобраться с темой.
    На мой взгляд, стоит также упомянуть о том, что минимальная необходимая логика внутри обработчика в top-half должна содержать ответ устройству о полученном прерывании, это must have всегда.
    • +3
      минимальная необходимая логика внутри обработчика в top-half должна содержать ответ устройству о полученном прерывании, это must have всегда

      Правильнее было бы сказать, что top half должен либо заблокировать, либо очистить IRQ от устройства, чтобы не быть вызванным повторно после разрешения прерываний после возврата из ISR. Как именно это будет сделано — зависит от устройства. Кроме того, при использовании threaded-обработчиков прерываний даже этого можно не делать явно: threaded-часть обработчика будет выполняться с заблокированным IRQ автоматически.
      • 0
        Спасибо за комментарии, это и подразумевалось под
        как-то взаимодействует с аппаратурой

        В статье уточнила.
  • 0
    Пару интересных моментов всё же в цикле статей не учли. Какие методы вызова softirq есть в Linux, что делает ksoftirqd и чем отличаются обычные обработчики прерываний от threaded irq, а также очень тонкий момент высвобождения ресурсов прерывания и tasklet'а при их использовании в коде.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка