Синхронизация мультипроцессоров

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

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

Основой любого практического мьютекс-протокола является специальная команда процессора, позволяющая провести проверку и установку значения за одну неделимую операцию. На рис. 2.16 был показан пример использования команды TSL (Test and Set Lock — проверить и установить блокировку) при реализации критических областей.

Было рассмотрено, что эта команда считывает слово памяти в регистр процессора. Одновременно она записывает 1 (или другое ненулевое значение) в слово памяти. Конечно, для выполнения операций чтения из памяти и записи в память требуются два цикла обращения к шине. На однопроцессорной машине команда ТБЬ работает так, как и ожидалось, поскольку команда процессора не может быть прервана на полпути.

А теперь подумаем, что может произойти на мультипроцессоре. На рис. 8.10 показано наихудшее из возможных развитие ситуации, где в качестве блокиратора используется слово памяти по адресу 1000, имеющее начальное значение 0. На шаге 1 центральный процессор 1 считывает слово и получает значение 0. На шаге 2, перед тем как у процессора 1 появится возможность переписать значение слова на 1, на сцену выходит центральный процессор 2 и также считывает это слово, получая значение 0. На шаге 3 центральный процессор 1 записывает в это слово значение 1. На шаге 4 центральный процессор 2 также записывает значение 1 в это слово. Оба процессора получили в результате работы команды ТБЬ значение 0, поэтому теперь они оба имеют доступ к критической области и взаимного исключения не происходит.

Рис. 8.10. Если шина не может быть заблокирована, команда TSL потерпит неудачу. Этими четырьмя шагами показана последовательность событий, демонстрирующая неудачное стечение обстоятельств


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

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

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

Проблема в том, что кэши работают с блоками по 32 или 64 байта.

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

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

Другой способ уменьшения потока передаваемых по шине данных заключается в применении широко известного алгоритма двоичной экспоненциальной задержки (binary exponential backoff), используемого в сетях Ethernet (Anderson, 1990). Вместо постоянного опроса, как на рис. 2.17, между опросами может быть вставлен цикл задержки. Сначала задержка составляет одну команду. Если блокировка еще не освободилась, задержка удваивается и составляет две команды, затем четыре и так далее до достижения некоторого максимума. Низкий максимум приводит к быстрому отклику при освобождении блокировки, но заставляет тратить впустую циклы обращения к шине на челночные передачи данных кэша. Высокий максимум сокращает челночные передачи данных кэша за счет замедленной реакции на освобождение блокировки. Двоичная экспоненциальная задержка может использоваться совместно с простым чтением, предваряющим выполнение команды TSL, или без него.

Более интересная идея заключается в том, чтобы предоставить для проверки каждому центральному процессору, желающему захватить мьютекс, собственную переменную блокировки (рис. 8.11) (Mellor-Crummey and Scott, 1991). Во избежание конфликтов она должна быть помещена в блок кэша, не используемый ни для чего другого. Алгоритм работает за счет того, что центральный процессор, не сумевший получить блокировку, получает переменную блокировки и присоединяется к концу списка центральных процессоров, ожидающих освобождения блокировки. Когда центральный процессор, удерживающий блокировку, покидает критическую область, он освобождает ту частную переменную блокировки, которую первый по списку центральный процессор тестирует в своем собственном кэше. Затем в критическую область входит этот центральный процессор. Завершив свою работу, он освобождает переменную блокировку, используемую его последователем, и т. д. При всей сложности этого протокола (связанной с тем, что нужно не допустить одновременного присоединения двух центральных процессоров к концу списка) он работает эффективно и без зависаний. Подробности можно узнать из упомянутой ранее статьи.

Рис. 8.11. Использование нескольких переменных блокировки, чтобы избежать челночной передачи данных кэша


<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Синхронизация мультипроцессоров:

  1. Синхронизация
  2. СТИМУЛЯЦИЯ ТРИГГЕРНАЯ
  3. ТЕТА-РИТМ
  4. ПСИХОФИЗИОЛОГИЯ ПОРАЖЕНИЙ ЛОКАЛЬНЫХ МОЗГА ГОЛОВНОГО
  5. Наставление Александру
  6. Крайон, как нам практически пользоваться этим кодом?
  7. М.Руссинович, Д.Соломон. Внутреннее устройство Microsoft Windows (главы 1–4), 2005
  8. Сефера: Крайон, для чего все эти существа прибыли вместе с нами из Атлантиды? Для чего слияние рас прошлого и настоящего (или будущего)?
  9. 2) Глаза Учителя
  10. Послание Ане Немцовой
  11. Технология социальной работы
  12. О врагах наших
  13. 3.4.1. Устранение ауральных травм, вызванных ауральными сущностями
  14. 5) Слияние с Мастером
  15. Наставления Мастеру Сефере