Телекоммуникационный портал GateWay

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

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

Симметричная многопроцессорная обработка (SMP) впервые появилась в FreeBSD 5.0 и потребовала добавления новых SMP синхронизации, чтобы устранить предположения об однопроцессорной системе, внутренне присущие ядру FreeBSD 4.0 [Schimmel, 1994]. Некоторые подсистемы в ядре FreeBSD 5.2 еще не были переведены на симметричную многопроцессорную обработку и до сих пор защищаются всеобщей блокировкой. Однако большая часть интенсивно использующихся частей ядра была выведена из-под всеобщей блокировки, включая многое из системы виртуальной памяти, сетевого стека и файловой системы.

В табл. показана иерархия блокировок, которая необходима для поддержки симметричной многопроцессорности. Столбец ожидания в табл. показывает, может ли блокировка этого типа удерживаться, когда поток входит в состояние сна. На самом нижнем уровне аппаратное обеспечение должно предоставить инструкцию сблокированной с памятью проверки и установки (test-and-set). Инструкция проверки и установки должна обеспечить выполнение для ячейки памяти двух операций - чтения существующего значения, за которой следует запись нового значения - без возможности для любого другого процессора прочесть или записать в эту ячейку памяти между этими двумя операциями. Некоторые архитектуры поддерживают более сложные версии инструкции проверки и установки. Например, PC предоставляет инструкцию сблокированного с памятью сравнения и обмена.

Циклические блокировки (spin locks) строятся на основе инструкции проверки и установки. Для блокировки резервируется ячейка памяти с нулевым значением, указывающим, что блокировка свободна, а значение «один» указывает, что блокировка занята. Значение блокировки проверяется, и она безусловно получает единичное значение. Если проверяемое значение равно нулю, блокировка была успешно получена, и поток может продолжить свою работу. Если значение равно единице, блокировку удерживает какой-то другой поток, поэтому поток должен осуществлять цикл проверки-и-установки до тех пор, пока поток, владеющий блокировкой (и работающий на другом процессоре), не сменит ее значение на ноль, показывая тем самым, что он закончил работу с ней. Циклические блокировки используются в качестве лишь кратковременных блокировок - например, для защиты списка при добавлении в него или удалении из него элемента.

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

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

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

Блокировки высшего уровня предотвращают создание потоками тупиков (deadlocks) при блокировании нескольких ресурсов. Предположим, двум потокам, А и В, требуется исключительный доступ к двум ресурсам, R\ и R2, для выполнения некоторой операции, как показано на рис.. Если поток А получил Ry, а поток В пытается получить R2, тупик возникнет, когда поток А попытается получить R2, а поток В попытается получить Л]. Чтобы избежать тупиков, FreeBSD 5.2 поддерживает частичное упорядочение всех блокировок. Два правила для частичного упорядочения следующие.

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

· Поток может получить лишь блокировку в классе с большим номером, чем класс с наибольшим номером, блокировка на который у потока уже есть.

На рис. поток А содержит L и может запросить R2, поскольку R1 и R2 в различных классах и R2 в классе с большим номером, чем L. Однако поток В должен освободить R2 до запроса L, поскольку R2 в классе с большим номером, чем R1. Таким образом, поток А сможет получить R2, когда он будет освобожден потоком В. После того, как поток А завершит работу и освободит L| и R2, поток В сможет получить обе эти блокировки и выполняться до завершения, не создавая тупик.

Рис. 4.4. Частичное упорядочение ресурсов

Исторически члены класса и упорядочение были плохо документированы и необязательны. Были обнаружены нарушения, когда потоки создали бы тупики, и был проведен тщательный анализ для выяснения того, какое упорядочение было нарушено. С возрастанием числа разработчиков и ростом ядра специальный метод для поддержания частичного упорядочения блокировок стал непригодным. К ядру был добавлен модуль доказательств (witness module), чтобы установить и привести в исполнение частичное упорядочение блокировок. Модуль доказательств отслеживает блокировки, полученные и освобожденные каждым потоком. Он также отслеживает порядок, в котором получаются блокировки друг относительно друга. Каждый раз при получении блокировки модуль доказательств использует эти два списка для проверки того, что блокировка не запрашивается в неправильном порядке. Если обнаружено нарушение порядка блокировки, в консоль выводится сообщение, подробно описывающее использованные блокировки и данные места. Модуль доказательств проверяет также, что при запросе ожидающей блокировки или добровольном переходе в состояние сна не удерживаются циклические блокировки.

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