Родная Библиотека Потоков POSIX для Linux

От себя: огромное спасибо девушке из Одессы TRIGGER2003 за огромную помощь с переводом и редактору saimhe за указанные недочеты и ошибки.

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

1 Первая реализация


Реализация LinuxThreads, которая сегодня является стандартной POSIX библиотекой потоков, основана на принципах, описанных разработчиками ядра во времена написания кода (1996). Основное предположение - что переключения контекста внутри связанных процессов достаточно быстры, чтобы обрабатывать каждый пользовательский поток одним потоком ядра. Процессы ядра могут иметь различные степени зависимостей. Спецификации потоков POSIX требуют совместного использования почти всех ресурсов.

В связи с отсутствием потоковых ABI (application binary interface - прим. ред.) для используемых архитектур, настоящая реализация не использует регистры потока. Вместо того расположение локальной памяти потока определяется фиксированной связью между указателем стека и позицией дескриптора потока.

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

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

2 Усовершенствования со временем


Код библиотеки потоков был значительно улучшен за последующие шесть лет. Усовершенствования происходили в двух частях: ABI и ядро.

Недавно внесённые расширения ABI позволяют использовать регистры потока или конструкции, которые могут работать подобно регистрам. Это было необходимым усовершенствованием, так как теперь определение местоположения локальных данных потока больше не является трудоёмкой операцией. Определить это местоположение необходимо почти для любой операции библиотеки потоков. Остальная часть runtime-ресурсов и пользовательских приложений также нуждается в этом.

Для некоторых архитектур изменения были просты. Некоторые имели резервированные для этих целей наборы регистров, у других были особые характеристики процессора, которые позволяют сохранять значения в контексте выполнения. Но таких архитектур было немного, остальные же не имели ни того, ни другого. Эти архитектуры все еще полагаются на методе вычисления позиции локальных данных потока, основанном на адресе стека. Кроме медленных вычислений, это также означает невозможность реализации (для этой архитектуры) API, которые позволяли бы программисту выбирать позицию и размер стека. Эти интерфейсы особенно важны, когда одновременно или последовательно используются множество потоков.

Стоит отметить решение, использованное для IA-32, из-за его нетривиальности; а так как эта архитектура несомненно является самой важной, это оказало влияние на проектирование библиотеки. В архитектуре IA-32, и так небогатой регистрами, есть два регистра, которые не были использованы в ABI: сегментные регистры %fs и %gs. Хотя непригодные для сохранения произвольных значений, они могут использоваться, чтобы обратиться к произвольным позициям виртуального адресного пространства процесса при помощи фиксированного смещения. Значение сегментного регистра используется, чтобы обратиться к некоторым структурам данных ядра, созданных для использования процессором, и которые содержат базовые адреса для каждого действительного индекса сегмента. С различными базовыми адресами можно обратиться к различным частям виртуального адресного пространства, используя то же самое смещение; это - именно то, что надо для доступа к локальным данным потока.

Проблема с этим подходом состоит в том, что сегментные регистры должны поддерживаться некоторыми структурами данных, используемыми процессором. Базовый адрес сегмента сохранен в таблице дескрипторов. Обращение к этим структурам данных ограничено самой операционной системой, а не пользовательским кодом; это означает, что операции по изменению дескрипторной таблицы будут медленными. Контекстное переключение между различными процессами также стало медленнее, так как дополнительные структуры данных должны быть перезагружены при каждом переключении контекста. Также ядро должно выделять память для таблицы, что может быть проблематично из-за архитектуры памяти, если число элементов становится большим - таблица должна находиться в постоянно отображенной области памяти, а это иногда труднодостижимо. Кроме того, число различных значений в сегментном регистре, а потому и число различных адресов, которые могут быть предоставлены, ограничено 8192.

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

Изменения, внесённые при разработке ядра до версии 2.4, идут от стабилизации к функциональности, что позволяет использовать сегментные регистры IA-32, а также усовершенствовать системный вызов clone(), который используется для создания потоков. Эти изменения можно было использовать для устранения некоторых требований для потока-менеджера, а также обеспечить правильную семантику в отношении идентификатора процесса - в частности, то, что идентификатор процесса един для всех потоков.

Тем не менее, поток-менеджер не мог быть полностью устранён по ряду причин. Во-первых, освобождение памяти стека не может быть выполнено потоком, использующим эту память. Во-вторых, чтобы избежать зомби потоков ядра, завершившихся потоков надо дожидать при помощи wait().

Но пока эти проблемы и множество других не решены, не было сочтено нужным переписывать библиотеку потоков ради использования появившихся преимуществ.

3 Проблемы с существующей реализацией


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

* Само существование потока-менеджера вызывает проблемы. Если менеджера уничтожают, остаток процесса находится в состоянии, которое должно быть очищено вручную. С другой стороны, так как менеджер занимается созданием потоков и очисткой, он становится узким местом системы.
* Система сигналов серьёзно нарушена и не соответствует спецификации POSIX. Посылка сигналов на целый процесс не реализована.
* Использование сигналов для осуществления примитивов синхронизации вызывает огромные проблемы. Латентность операций высока. А и так сложная обработка сигналов в библиотеке потоков усложняется еще больше. Ложные пробуждения случаются постоянно, и их надо обходить. Кроме самой проблемы ложного пробуждения, это еще больше нагружает систему сигналов ядра.
* Также должен быть упомянут особый случай нарушения обработки сигналов - неправильная обработка сигналов SIGSTOP и SIGCONT. Так как ядро неправильно обрабатывает эти сигналы, пользователь, например, не сможет остановить многопоточный процесс (например, с помощью Control-Z в оболочках, поддерживающих задания). Только один поток будет остановлен. У отладчиков та же самая проблема.
* Каждый поток, имеющий отличный идентификатор процесса, вызовет проблемы совместимости с другими реализациями POSIX-потоков. Это частично сглажено тем, что сигналы и так не могут быть качественно использованы, но всё еще заметно.
* На IA-32 ограничение на количество потоков (8192, минус один для менеджера) может оказаться проблемой для некоторых людей. Хотя потоки в таких ситуациях часто неправильно используются, "неисправные" приложения, как известно, на других платформах всё-таки работают.

На стороне ядра также есть проблемы:

* Процессы с сотнями или тысячами потоков делают файловую систему /proc едва пригодной для использования. Каждый поток отображается как отдельный процесс.
* Проблемы с реализацией сигналов главным образом существуют из-за отсутствия поддержки со стороны ядра. Специальные сигналы, подобные SIGSTOP, должны быть обработаны ядром и для всех потоков.
* Злоупотребление сигналами для реализации примитивов синхронизации добавляет еще больше проблем. Для гарантии синхронизации сигналы - слишком тяжелый подход.


4 Цели новой реализации


Попытка залатать существующую реализацию - цель, не заслуживающая внимания. Всё построено вокруг ограничений ядра Linux в то время. Необходима полная перезапись. Цель состоит в совместимости с ABI (что не является недоступным благодаря способу, которым реализованы API потоков POSIX). Но всё еще есть возможность переосмыслить каждое решение, сделанное при проектировании. Правильные решения тождественны знанию требований реализации. Подобранные требования включают в себя:

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

Эффективное использование SMP Одна из основных целей использования потоков - обеспечить использование возможностей многопроцессорных систем. Разбивая работу на столько частей, сколько центральных процессоров, в идеале можно обеспечить линейный прирост скорости.

Низкие затраты на запуск Создание новых потоков должно иметь очень низкие затраты, чтобы создавать потоки даже для малых частей работы.

Низкая цена связи Программы, отлинкованные с библиотекой потока (прямо или косвенно), но не использующие потоки, не должны быть сильно затронуты этим.

Бинарная совместимость Новая библиотека должна быть совместима на уровне двоичного кода с реализацией LinuxThreads. Некоторые семантические разногласия неизбежны, так как эта реализация не соответствует POSIX.

Аппаратная масштабируемость Реализация потоков должна работать достаточно хорошо с большим числом процессоров. Административные затраты не должны слишком возрастать с увеличением числа процессоров.

Программная масштабируемость Другое применение потоков - решить подпроблемы выполнения пользовательского приложения в отдельных контекстах. В Java потоки используются для реализации окружающей среды программирования, так как асинхронные операции не поддерживаются. А результат от этого тот самый: могут быть созданы огромные количества потоков. Новая реализация в идеале не должна иметь никаких установленных пределов на число потоков или других объектов.

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

Поддержка NUMA Один специальный класс будущих машин, представляющий интерес, основан на неоднородных архитектурах памяти (NUMA). Код, подобный библиотеке потоков, должен быть разработан с учетом этого, чтобы не упустить выгоды от использования потоков на машинах с такой архитектурой. Важна проектировка структур данных.

Интегрирование с C++ C++ определяет обработку исключений, которая автоматически очищает объекты контекста, теряющихся при возникновении исключения. Этому процессу подобна отмена потока, и разумно ожидать, что отмена также вызывает необходимые объектные деструкторы.

5 Принятые решения


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

5.1 1-к-1 против M-к-N


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

Второй вариант библиотеки с моделью M-к-N, где число потоков ядра и потоков пользовательского уровня не должно иметь установленной связи. Такая реализация планирует потоки пользовательского уровня на доступных потоках ядра. Поэтому в работе находятся два планировщика. И если они не будут сотрудничать, то сделанные ими решения могут значительно понизить быстродействие системы. За эти годы были предложены различные схемы реализации взаимодействия. Самая многообещающая и в большинстве используемая - это схема Активации Планировщика. Здесь же эти два планировщика работают в команде: планировщик пользовательского уровня может давать подсказки планировщику ядра, в то время как планировщик ядра уведомляет планировщика пользовательского уровня о своих решениях.

Разработчики ядра соглашались с тем, что модель M-к-N не вписывается в концепцию ядра Linux. Стоимость необходимой инфраструктуры слишком высока. Если позволить контекстное переключение в планировщике пользовательского уровня, то придется часто копировать содержание регистров пространства ядра.

Наконец, множество проблем, которые планировщик пользовательского уровня помогает предотвращать, не являются проблемами для ядра Linux. Огромные число потоков - не проблема, так как планировщик и другие подпрограммы ядра имеют постоянное время выполнения, O(1), в противоположность линейному времени относительно числа активных процессов и потоков.

Наконец, нельзя не учитывать затраты на реализацию дополнительного кода, необходимого для модели M-к-N. Особенно в отношении высокосложного кода, подобного библиотеке потоков, многое говорит в пользу чистой и тонкой реализации.

5.2 Обработка сигналов


Другая причина использования модели M-к-N состоит в упрощении обработки сигналов в ядре. Несмотря на то, что обработчик сигнала (а тем самим и факт, будет ли сигнал проигнорирован) является свойством процесса, потокам свойственны индивидуальные маски сигналов. При тысячах потоков на процесс ядро потенциально должно проверять маски сигналов каждого потока, чтобы определить, можно ли выдать сигнал. Если сохранять низкое число потоков ядра с помощью модели M-к-N, то эту работу можно выполнить на пользовательском уровне.

Однако обработка конечной выдачи сигнала на пользовательском уровне имеет несколько недостатков. Поток, который не ожидает данного сигнала, не должен уведомляться о его получении процессом. Сигнал может быть обнаружен, если для доставки сигнала используется стек потока и при этом поток получает ошибку EINTR от системного вызова. Первого можно избежать, используя дополнительный стек для доставки сигналов; с другой стороны, в распоряжении пользователя уже есть sigaltstack. Но оба трудно реализовать. Для предотвращения недопустимых EINTR, получаемых от системных вызовов, оболочки системных вызовов должны быть расширены, что приведёт к дополнительным накладным расходам для нормальных операций.

Есть две альтернативы для сценария выдачи сигналов:

* Сигналы посылаются выделенному потоку, который не выполняет никакого пользовательского кода (или как минимум не имеет кода, который не желал бы получать все возможные сигналы). Недостатки - затраты на дополнительный поток и, что более важно, преобразование сигналов в последовательную форму. Из последнего следует, что даже если выделенный сигнальный поток распределяет обработку сигналов к другим потокам, сначала все сигналы направляются сквозь сигнальный поток. Это противоречит целям (но не словам) модели сигналов POSIX, которая позволяет параллельную обработку сигналов. Если есть проблема со временем срабатывания на сигнал, приложение могло бы создать несколько потоков с единственной целью обработки сигналов. Это было бы решением при использовании сигнального потока.
* Сигналы можно предоставлять пользовательскому уровню и другими средствами. Вместо того, чтобы использовать обработчик сигналов, используется отдельный upcall-механизм (позволяющий ядру вызывать функции пользовательского уровня - прим. ред.). Это использовалось бы в реализации, основанной на Активации Планировщика. Затраты - увеличение сложности в ядре, которое должно реализовать второй механизм выдачи сигналов, а также эмуляция части функциональных возможностей сигналов пользовательским уровнем. Например, если все потоки заблокировались на вызове read и сигнал собирается разбудить один поток, возвращая ему EINTR, всё должно продолжать работать.

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

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

5.3 Да или нет вспомогательному потоку-менеджеру


В старой библиотеке потоков для всех видов внутренних работ использовался так называемый поток-менеджер. Поток-менеджер никогда не выполняет пользовательский код. Вместо этого все другие потоки посылают запросы на подобии, 'создать новый поток', которые централизованно и последовательно выполнялись потоком-менеджером. Это было необходимо, чтобы помочь реализовать правильную семантику при множестве проблем:

* Для того, чтобы быть способным реагировать на фатальные сигналы и уничтожить весь процесс, создатель потока должен постоянно наблюдать за всеми дочерними потоками. Это невозможно, кроме как в выделённом потоке, в случае если ядро не берёт на себя это задание.
* Освобождение памяти, используемой как стек, должно произойти после того, как поток завершён. Поэтому поток сам не может сделать этого.
* Надо поджидать уничтожающихся потоков при помощи wait, дабы избежать превращения их в зомби.
* Если основной поток вызывает pthread_exit, процесс не уничтожается; основной поток уходит в слип, и задача менеджера в том, чтобы пробудить его при уничтожении процесса.
* В некоторых ситуациях потоку надо помочь при обработке семафоров.
* Для освобождения локальных данных потоков нужно пересмотреть все потоки, а это лучше сделать при помощи менеджера.

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

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

5.4 Список всех потоков


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

Список также использовался для реализации функции pthread_key_delete. Если ключ удален вызовом pthread_key_delete и используется повторно, когда последующий вызов pthread_key_create возвращает тот же самый ключ, реализация должна удостовериться, что значение, связанное с ключом для всех потоков, равна NULL. Старая реализация достигала этого, активно очищая слоты с ответственными за потоки структурами данных во время удаления ключа.

Это - не единственный способ реализации. Если нужно избежать списка потоков (или его пересмотра), то тогда должна быть возможность определить, нужен ли вызов деструктора или нет. Один из способов реализации этого - использование счетчиков поколений. Каждый ключ для хранилища потоков и памяти, выделенной для них в структурах данных потоков, имеет такой счетчик. При выделении ключ получает увеличенное значение счетчика поколений, и это новое значение сохраняется в структурах данных потока. Удаление ключа заставляет счетчик поколении снова увеличиться. Если поток завершается, то деструкторы будут выполняться только для потоков, у которых счетчик поколения соответствует счетчику в структуре данных потока. Так удаление ключа становится простой операцией приращения.

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

5.5 Примитивы синхронизации


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

К счастью, несколько новых функциональных возможностей были добавлены к ядру для реализации всех видов примитивов синхронизации. Это футексы [Futex]. Основной принцип прост, но достаточно мощен, чтобы адаптироваться ко всем видам использования. Вызывающие программы могут быть блокированы в ядре и могут быть пробуждены или явно, в результате прерывания, или по таймауту.

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

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

5.6 Распределение памяти


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

* Необходимые блоки памяти объединены, т.е. структуры данных потоков и локальная память потока помещены в стек. Пригодный для использования стек выстраивает вниз (или вверх в случае направленного вверх стека) память, необходимую для обоих. В локальной памяти потока ABI, определенный в ELF gABI, требует только одной дополнительной структуры данных - DTV (Динамический Вектор Потока). Память, необходимая для этого, может изменяться и поэтому не может быть распределена статически во время запуска потока.
* Обработка памяти, особенно перераспределение, происходит медленно. Поэтому сокращение времени на обработку может быть достигнуто, если полного перераспределения удастся избежать. Если блоки памяти не освобождаются непосредственно во время остановки потока, но вместо этого задерживаются, то именно это и происходит. Применение munmap к кадру стека приводит к дорогостоящим операциям TLB, например, на IA-32 это вызывает глобальный сброс TLB на диск, который может быть ретранслирован к другим процессорам. Следовательно, кэширование стековых кадров - ключевой шаг к высокой производительности создания и завершения потоков. Другое преимущество в том, что в момент завершения потока некоторая часть информации в потоковом дескрипторе остаётся в состоянии, пригодном к использованию, поэтому и не нуждается в реинициализации при повторном использовании дескриптора. Особенно на 32-разрядных машинах с их ограниченным адресным пространством невозможно сохранять неограниченное количество памяти для повторного использования. Необходим максимальный размер кэша памяти. Это - переменная настройка, которая на 64-битных машинах может иметь достаточно большое значение, чтобы никогда его не превысить.

Эта схема отлично работает в большинстве случаев, так как потоки в одном процессе часто имеют очень ограниченное число различных размеров стека.
Единственный недостаток этой схемы состоит в том, что хендл потока является просто указателем на дескриптор потока и поэтому последовательно созданные потоки получают тот же хендл. Это может скрыть ошибки и привести к странным результатам. Если это действительно становится проблемой, то при выделении дескриптора потока можно переключится в режим отладки, что позволит избежать повторного получения того же хендла. Здесь не о чем беспокоится при стандартных условиях выполнения.

6 Усовершенствование ядра


Даже ранние разрабатываемые версии ядра Linux 2.5.x не обеспечивали всех функциональных возможностей, необходимых для хорошей реализации потоков. Следующие изменения были добавлены в официальную версию ядра. Все эти изменения были сделаны в августе и сентябре 2002 Инго Молнаром (Ingo Molnar) как часть этого проекта. Проектирование функциональных возможностей ядра и библиотеки потоков всё время было совместным, чтобы гарантировать оптимальные интерфейсы между этими двумя компонентами.

* Поддержка произвольного числа потоковых областей данных на IA-32 и x86-64 через появившийся системный вызов TLS (thread local storage - прим. ред.). Этот системный вызов позволяет распределить один или более элементов в GDT (Глобальная Таблица Дескрипторов, структура данных центрального процессора), которые могут быть использованы для обращения к памяти с выбранным смещением. Это является эффективной заменой регистра потока. GDT одна на каждый CPU, а упомянутые допольнительные элементы в ней - уникальны для отдельного потока и обновляются планировщиком. Это исправление позволило реализовать модель потоков 1-к-1 без ограничения числа потоков, в отличие от предыдущего метода (через LDT - таблица локальных дескрипторов, структура данных центрального процессора), где число потоков процесса было ограничено 8192. Для достижения максимальной масштабируемости без этого нового системного вызова, была бы необходима реализация модели M-к-N.
* Системный вызов clone был расширен, чтобы оптимизировать создание новых потоков и облегчить завершение потоков без помощи другого потока (поток-менеджер выполнял эту задачу в предыдущей реализации). В новой реализации ядро сохраняет в указанном месте памяти ID нового потока, если установлен флаг CLONE_PARENT_SETTID, и/или очищает ту же самую ячейку памяти после завершения потока, если установлен флаг CLONE_CLEARTID. Это может быть использовано на пользовательском уровне управления памятью для распознания неиспользованных блоков памяти. Это также помогает управлению памятью пользовательского уровня, не требуя от ядра знания каких-либо подробностей. Кроме того, ядро выполняет пробуждение футекса по идентификатору потока. Эта особенность используется в реализации pthread_join. Другое важное изменение - поддержка загрузки регистра потока, защищенной от сигналов. Так как сигналы могут прибыть в любое время, любой из них должен быть заблокирован во время запроса clone, или новый поток должен стартовать уже с загруженным регистром потока. Последнее является еще одним расширением реализации clone, в форме флага CLONE_TLS. Точная форма передаваемого ядру параметра зависит от архитектуры.
* Обработка сигналов POSIX для многопоточных процессов теперь осуществляется в ядре. Сигналы, посланные процессу, теперь доставляются одному из доступных потоков процесса. Фатальные сигналы уничтожают весь процесс. Сигналы остановки и продолжения воздействуют на весь процесс; это дает возможность управления заданиями для многопоточных процессов (пропущена в старой реализации). Также поддерживается общедоступное ожидание обработки сигналов.
* Введен второй вариант системного вызова exit: exit_group. Старый системный вызов завершал текущий поток. Новый системный вызов завершает весь процесс. В то же самое время реализация обработки exit была значительно улучшена. Необходимое на остановку процесса со множеством потоков время теперь занимает только часть времени, необходимого раньше. Запуск и остановка образца с 100 000 потоков прежде занимали 15 минут, теперь только 2 секунды.
* Системный вызов exec теперь снабжает созданный процесс идентификатором родительского процесса. Все остальные потоки процесса завершаются прежде, чем получает управление новый образ процесса.
* Об использовании ресурсов (CPU, "стенное" время, отсутствиe страниц и т.д.) сообщается всему процессу-родителю, а не только начальному потоку.
* Обновление каталога /proc было изменено так, чтобы исключить все потоки, кроме начального. Начальный поток представляет процесс. Это - необходимая мера, так как иначе тысячи или десятки тысяч потоков, которые процесс может создать, в лучшем случае замедляли бы использование /proc.
* Поддержка отдельных потоков, которых не ожидают, должна быть выполнена присоединяющимся потоком; присоединение осуществляется пробуждением футекса, которое выполняется ядром во время выхода из потока.
* Ядро сохраняет начальный поток, пока все потоки не завершатся. Это гарантирует видимость процесса в /proc, а также получение сигнала.
* Ядро было расширено для обработки произвольного числа потоков. Пространство PID было расширено до 2 миллиардов потоков на IA-32, и масштабируемость многопоточных рабочих нагрузок была значительно улучшена. Файловая система /proc изменена так, чтобы поддерживать более чем 64k процессов.
* Способ выполнения ядром сигналов завершения потока дает возможность pthread_join возвратиться после того, как дочерний поток стал действительно мертвым. То есть, все деструкторы TSD выполнились и стек может быть повторно использован, что важно, если стек был распределен пользователем.


7 Результаты


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

Время создания и уничтожения потока измерено просто как время создания и уничтожения потоков при различных условиях. Конечно, с переменным числом потоков, существующих одновременно. Если достигнуто максимальное число параллельных потоков, то программа ждет уничтожения потока для создания нового. Это сохраняет требования к ресурсам на управляемом уровне. По возможности создается несколько новых потоков; точное число - вторая переменная в испытательном ряде.

Алгоритм испытания:

в каждом потоке верхнего уровня, которых от 1 до 20, создать от 1 до 10 дочерних.

Мы повторяли операцию создания потока 100 000 раз - это было нужно только для измерения тестового времени, и не следует путать это с более ранними испытаниями по алгоритму 'запуск 100 000 параллельных потоков сразу'.

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

Мы подводим итоги результатов теста, в двух таблицах. В обоих случаях мы сглаживаем одно измерение матрицы функцией минимума.

Рисунок 1 показывает результаты для различного числа потоков верхнего уровня, создающих потоки, которые мы фактически считаем. Используется минимальное время выполнения для всех запусков с различным числом потоков, работающих параллельно.

Как мы можем видеть, NGPT (next generation POSIX threading - прим. ред.) стало вдвое быстрей и поэтому действительно является существенным усовершенствованием LinuxThreads. Процесс создания потока в LinuxThreads был сложным и медленным. Удивительно, что разница для NPTL (native POSIX thread library - прим. ред.) является настолько большой, в четыре раза.

Вторая сводка выглядит похоже. Рисунок 2 показывает минимальное необходимое время для некоторого количества дочерних потоков. Время определяется оптимальным числом потоков, используемых каждым потоком верхнего уровня.

На этой диаграмме мы видим эффект масштабируемости. Если слишком много потоков параллельно пробуют создать еще больше потоков, то все реализации страдают от этого, одни больше, другие меньше.

Состязательная обработка.


Рисунок 3 показывает время выполнения программы, которая создает 32 потока и переменное число критических секций, к которым потоки пробуют получить доступ (всего 50 000 попыток) [csfast]. Чем меньше критических секций, тем выше вероятность конкуренции.

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

Результаты для двух версий ядра показывают:

* Времена для NPTL значительно ниже, чем для LinuxThreads;
* В ядре 2.4.20-2.21 имеется планировщик, изменённый для обработки новых ситуаций, создаваемых частым использованием футексов. Подобные изменения будут сделаны для разрабатываемого ядра 2.5. По сообщению от разработчиков, эта настройка планировщика ядра и необходима, и дает существенную прибыль. Нет никакой причины полагать, что код в версиях 2.4.20-2.21 оптимален;
* Можно увидеть ожидаемое асимптотическое поведение.

Производительность при создании и уничтожении потоков

Рисунок 1: изменение числа потоков верхнего уровня

Производительность при создании и уничтожении потоков

Рисунок 2: изменение числа совместно действующих дочерних потоков

Производительность csfast5a


Количество критических секций

Рисунок 3: обработка состязательных блокировок

8 Остающиеся вопросы


Остаётся несколько вопросов, прежде чем будет достигнута 100 % совместимость с POSIX. Изменения будут зависеть от того, как хорошо решение вписывается в реализацию ядра Linux.
Семейства системных вызовов setuid и setgid должны воздействовать на весь процесс, а не только на начальный поток.
Уровень nice является свойством всего процесса и после корректировки должно воздействовать на все потоки процесса.
Предел использования CPU, который может быть выбран с помощью setrlimit, ограничивает совместное время, потраченное всеми потоками в процессе.
Поддержка реального времени в библиотеке главным образом отсутствует. Системные вызовы для выбора параметров планирования доступны, но они не дают никакого эффекта. Причина для этого состоит в том, что большая часть ядра не следует правилам планирования в реальном масштабе времени. Пробуждение одного из потоков, ожидающего футекс, не выполняется по приоритету ожидания.
Есть дополнительные места, где ядро упускает адекватную поддержку реального времени. По этой причине текущая реализация не замедлена поддержкой чего-либо, что не может быть достигнуто.
Новая библиотека содержит множество мест с настраиваемыми переменными. В реальных ситуациях следует разумно определить их значения по умолчанию.