DragonFly - модель легковесных потоков ядра

Оригинал: The Light Weight Kernel Threading Model
Перевод: Валерий Винник, 05.01.31

Модель легковесных потоков ядра

DragonFly основана на модели легковесных потоков (или нитей - threads) ядра (LWKT, Light Weight Kernel Threading, далее ЛПЯ). Каждому процессу в системе поставлен в соответствие отдельный поток, а большинство процессов только ядра - это фактически чистые потоки. Например, демон pageout (вытеснения страницы из ОЗУ) - это "голый" поток без контекста процесса.

Модель ЛПЯ имеет ряд отличительных особенностей, независимых от архитектуры. Эти особенности были разработаны для уменьшения конкуренции между процессорами.

1. У каждого процессора системы есть свой собственный, особый ЛПЯ-планировщик (sheduler). Потоки привязаны к своим процессорам изначально, и могут быть переданы на другой процессор при наступлении неких особых условий. Любая операция планирования ЛПЯ на конкретном процессоре выполняется только на этом процессоре. Это значит, что главный ЛПЯ-планировщик может планировать и отменять операции, переключаясь между потоками в домене процессоров без каких бы то ни было блокировок. Никаких блокировок многопроцессорной системы, ничего, кроме простого критического участка.

2. Потоки не будут перенаправляться с вытеснением на другой процессор, пока они выполняются в ядре; поток также не будет переноситься между процессорами во время блокировки. Планировщик юзерланда (userland scheduler) может переходить с одного потока, выполняющегося в пользовательском режиме (usermode), на другой. Потоки не будут переводиться с вытеснением в режим непрерывающихся потоков (non-interrupt thread). Если прерывающийся поток (interrupt thread) вытесняет текущий поток, то в момент, когда прерывающийся поток завершает своё выполнение или блокируется, вытесненный поток восстанавливается независимо от его положения в расписании планировщика. Например, поток может стать вытесненным после вызова lwkt_deschedule_self(), но это произойдёт раньше, чем он реально отключится. И это правильно, потому что управление будет возращено ему непосредственно после того, как прерывающийся поток завершит своё выполнение или блокируется.

3. Из того, что сказано в п.2, следует, что поток может кэшировать информацию, полученную посредством структуры получения основных данных по каждому процессору (the per-cpu globaldata structure), не испытывая необходимости блокироваться, и - если известно, что эта информация не была затронута прерываниями - не испытывая необходимости входить в критический участок. Это позволяет заводить отдельные кэши различной информации для каждого процессора практически без дополнительных служебных данных.

4. Процессор, который пытается планировать поток, принадлежащий другому процессору, будет посылать целевому процессору основанные на IPI сообщения, необходимые для выполнения текущей операции. Эти сообщения асинхронны по умолчанию, и хотя IPI могут обладать некой латентностью, они не обязательно пропускают циклы процессора "мимо ушей". Потоки могут заблокировать подобные операции входом в критический участок, что фактически и делает планировщик ЛПЯ. Вход в критический участок и выход из него считаются экономными операциями и не требуют ни блокировки, ни выполнения инструкций заблокированной магистрали.

5. Подсистема сообщений IPI работает с полными взаимными блокировками FIFO, скрещивая потоки (spinning) и обрабатывая поступающую часть очереди в ожидании высвобождения исходящей части очереди. Подсистема сообщений IPI специально не переключает потоки в этих условиях, что позволяет программе воспринимать её как неблокирующийся API, даже если некоторое скрещивание потоков может иногда происходить.

В дополнение к этим особенностям, модель ЛПЯ позволяет производить вытеснение FAST-прерываниями и вытеснение потоковыми прерываниями. FAST-прерывания могут вытеснять текущий поток, когда тот не находится в критическом участке. Потоковые прерывания также могут вытеснять текущий поток. Система ЛПЯ будет переключаться в режим потоковых прерываний, а потом - обратно в оригинальное состояние, когда потоковое прерывание блокируется либо завершает работу. Действие функций IPI очень похоже на действие FAST-прерываний и обладает такой же способностью кадрирования внутренних прерываний (trapframe capability). В DragonFly это в полной мере используется SYSTIMERS API для распределения прерываний hardclock() и statclock() между всеми процессорами.

Подсистема IPI для работы с сообщениями

Модель ЛПЯ для коммуникации между процессорами использует систему асинхронной обработки сообщений. В первом приближении, вы просто делаете вызов, передавая процессору ссылку на функцию и аргумент данных, которые процессор обрабатывает асинхронно. А так как это асинхронная модель, вызывающая программа не ждёт синхронного выполнения, что значительно повышает эффективность, а служебные данные целевого процессора примерно равняются прерыванию.

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

Подсистема IPI широко используется не менее чем в полудюжине основных ЛПЯ-подсистем, включая попроцессорное планирование потоков, slab allocator и работу с сообщениями. Поскольку система IPI родная для DragonFly, она не требует и не использует механизм Big Giant Lock (как во FreeBSD). Поэтому все функции, основанные на IPI, должны быть МР-безопасны (и они таковыми являются).

Основанная на IPI подсистема синхронизации процессоров

Модель ЛПЯ использует генерализованный, аппаратно-независимый API синхронизации процессоров. Этот API может использоваться для перевода целевых процессоров в известное состояние, пока ведётся работа с чувствительной структурой данных. Описываемый интерфейс применяется для взаимодействия с обновлением страничных таблиц (pagetable) блока управления памятью (MMU). Например, небезопасно проверять и очищать модифицирующий бит в графе страничной таблицы, а потом удалять эту графу, даже сохранив необходимую блокировку. Это потому, что процесс юзерланда, выполняющийся на другом процессоре, может захватывать и изменять эту таблицу, из-за чего возникнет соревнование между отчётами (writeback) буфера быстрого преобразования адреса (TLB) на целевом процессоре и вашими попытками очистить графу страничной таблицы. Оптимальным решением будет заблаговременно перевести все процессоры, которые могут посылать отчёты в графу страничной таблицы (т.е. все процессоры в маске pm_active pmap'а) в известное состояние, провести модификацию, после чего освободить процессоры с запросом объявить недействительным их TLB.

API, которое используется в DragonFly, свободно от взаимных блокировок. Разрешена синхронизация нескольких процессоров так, чтобы они работали параллельно, что распространяется на все потоки на весь период синхронизации. Несмотря на такое проявление гибкости, интерфейс синхронизации процессоров работает в контролируемой среде, поэтому функции обратного вызова (callback) стремятся работать аналогично таковым, используемым в подсистеме IPI обработки сообщений.

Маркер последовательности

Маркер последовательности (serializing token) могут иметь одновременно несколько потоков. Если поток имеет маркер последовательности, то уже никакой другой поток с таким же маркером не будет выполняться в то же самое время.

Поток может нести любое число маркеров последовательности.

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

Теоретически нет неразрешимых проблем со взаимной блокировкой в случае применения механизма маркеров последовательности. Тем не менее, при первоначальном употреблении могут возникнуть обратимые блокировки (livelock) из-за существования нескольких одинаковых маркеров на разных потоках.

Применение маркеров последовательности может также служить защитой потоков от вытеснения прерываниями, стремящимися получить тот же маркер. Этот эффект несколько отличается от механизма Big Giant Lock (также известной под названием МР-блокировки), которая не разделяет (interlock) прерывания на том же самом процессоре. Подчеркнём, что атомарность маркера сохраняется в условиях вытеснения, даже если вытеснение предполагает временное переключение на другой поток. Для того, чтобы сохранить атомарность маркера, нет необходимости входить на уровень spl() либо в критический участок.

Наличие маркера последовательности не обеспечивает невозможности возникновения вытесняющих прерываний, хотя и может заставить некоторые из них блокироваться с перепланированием (block-reschedule). Обеспоточенные прерывания подсистем FAST и IPI для работы с сообщениями не могут использовать маркеры, так как не имеют контекста потока, в котором могли бы работать. Вместо этого, названные подсистемы разделяются блокировками (interlocked) посредством использования критических участков.

Обновлено: 12.03.2015