Файл: Tannenbaum.pdf

Мультипроцессоры с памятью совместного использования 593

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

 SMP (Symmetric Multiprocessor — симмет-

ричный мультипроцессор).

 Ниже мы будем говорить именно о таком типе систем.

Семантика памяти

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

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

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

Семантику памяти можно рассматривать как контракт между программным

обеспечением и аппаратным обеспечением памяти [3]. Если программное обеспе-
чение соглашается следовать определенным правилам, то память соглашается вы-

давать определенные результаты. Основная проблема здесь — каковы должны быть
правила. Эти правила называются

 моделями согласованности.

 Было предложено

и разработано множество таких правил.

Предположим, что процессор 0 записывает значение 1 в какое-то слово памяти,

а немного позже процессор 1 записывает значение 2 в то же самое слово. Процес-
сор 2 считывает это слово и получает значение 1. Должен ли владелец компьютера
обратиться после этого в мастерскую? Это зависит от того, что обещано в контракте.

Строгая согласованность

Самая простая модель —

 строгая согласованность.

 В такой модели при любом счи-

тывании из адреса х всегда возвращается значение самой последней записи в х.

Программистам очень нравится эта модель, но ее можно реализовать на практике
только следующим образом: должен быть один модуль памяти, который просто
обслуживает все запросы по мере поступления (первым поступил — первым обра-

ботан), без кэш-памяти и без дублирования данных. К несчастью, это очень сильно
замедляет работу памяти.

Согласованность по последовательности

Следующая модель называется

 согласованностью по последовательности [79].

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

5 9 4 Глава 8. Архитектуры компьютеров параллельного действия

Рассмотрим один пример. Предположим, что процессор 1 записывает значение

100 в слово х, а через 1 не процессор 2 записывает значение 200 в слово х. А теперь

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

щихся к этому рисунку. В первом из них процессор 3 получает значения (20Q, 200),
и процессор 4 получает значения (200, 200). Во втором они получают (100, 200) и
(200,200) соответственно. В третьем они получают (100,100) и (200,100) соответ-
ственно. Все эти варианты допустимы, как и некоторые другие, которые мы здесь
не показали.

Процессор

\

2

Запись

значения 100'

1

Запись

значения 200

Считывание

слова 2х

X

дважды

3

Считывание

слова 2х

дважды

4

Рис. 8.15.

 Два процессора записывают, а другие два процессора

считывают одно и то же слово из общей памяти

В листингах 8.1—8.3 представлены возможные варианты двух записей и четы-

рех чтений.

Листинг8.1. Крис. 8.15 (а)

W100
W200

R3=200
R3=200
R4=200

R4=200

Листинг 8.2. К рис. 8.15 (б)

W100

R3=100

W200

R4=200

R3=200

R4=200

Л и с т и н г 8 . 3 . Крис. 8.15 (в)

W200

R4=200

W100

R3=100

R4=100

R3=100

Мультипроцессоры с памятью совместного использования 595

Согласованная по последовательности память никогда не позволит процессо-

ру 3 получить значение (100, 200), если процессор 4 получил (200, 100). Если бы
это произошло, с точки зрения процессора 3 это бы означало, что запись значения

100 процессором 1 завершилась раньше записи значения 200, которую осуществ-

ляет процессор 2. Это вполне возможно. Но с точки зрения процессора 4 это также
значит, что запись процессором 2 числа 200 завершилась до записи процессо-
ром 1 числа 100. Сам по себе такой результат тоже возможен, но он противоречит
первому результату. Согласованность по последовательности гарантирует единый
глобальный порядок записей, который виден всем процессорам. Если процес-
сор 3 видит, что первым было записано значение 100, то процессор 4 должен ви-
деть тот же порядок.

Согласованность по последовательности очень полезна. Если несколько собы-

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

Процессорная согласованность

Процессорная согласованность

 [48] — более проигрышная модель, но зато ее лег-

че реализовать на больших мультипроцессорах. Она имеет два свойства:

1. Все процессоры воспринимают записи любого процессора в том порядке,

в котором они начинаются.

2. Все процессоры видят записи в любое слово памяти в том же порядке, в ко-

тором они происходят.

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

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

дел значение 1В, а затем значение 1А. Второй пункт нужен, чтобы каждое слово

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

Даже при таких ограничениях у разработчика есть много возможностей. Посмот-

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

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

другие — второй порядок, а третьи — иной третий порядок. Единственное, что

гарантируется абсолютно точно, — ни один процессор не увидит последователь-
ность, в которой сначала идет 1В, а затем 1А.

5 9 6 Глава 8. Архитектуры компьютеров параллельного действия

Слабая согласованность

В следующей модели, слабой согласованности, записи, произведенные одним про-
цессором, воспринимаются по порядку [33]. Один процессор может увидеть 1А до

1 В, а другой — 1А после 1 В. Чтобы внести порядок в этот хаос, в памяти содержат-

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

При слабой согласованности время разделяется на последовательные периоды,

разграниченные моментами синхронизации (рис. 8.16). Никакого определенного
порядка для 1А и 1В не гарантируется, и разные процессоры могут воспринимать
эти две записи в разном порядке, то есть один процессор может сначала видеть 1 А,
а затем 1В, а другой процессор может сначала видеть 1В, а затем 1 А. Такая ситуа-
ция допустима. Однако все процессоры видят сначала 1В, а затем 1С, поскольку
первая операция синхронизации требует, чтобы сначала завершились записи 1 А,

1В и 2А, и только после этого начались записи 1С, 2В, ЗА или ЗВ. Таким образом,

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

Запись

Процессор А 1А 1В

Процессор В 2А

Процессор С

Момент синхронизации

1С

2В

ЗА

ЗВ

1D 1Е

2С

ЗС

1F

2D

Время

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

время на последовательные периоды

Свободная согласованность

Слабая согласованность — не очень эффективный метод, поскольку он требует

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

Мультипроцессоры с памятью совместного использования 597

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

В этой модели операция синхронизации разделяется на две разные операции.

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

завершена, пока не закончатся все ранее начатые записи. Более того, новые опера-
ции памяти могут начинаться сразу же.

Когда начинается следующая операция acqui re, производится проверка, все ли

предыдущие операции rel ease завершены. Если нет, то операция acqui re задержи-
вается до тех пор, пока они все не будут сделаны (а все записи должны быть завер-
шены перед тем, как завершатся все операции release). Таким образом, если следу-
ющая операция acquire появляется через достаточно длительный промежуток

времени после последней операции rel ease, ей не нужно ждать, и она может войти
в критическую область без задержки. Если операция acquire появляется через не-
большой промежуток времени после операции release, эта операция acquire (и все
команды, которые следуют за ней) будет задержана до завершения всех операций

release. Это гарантирует, что все переменные в критической области будут обнов-

лены. Такая схема немного сложнее, чем слабая согласованность, но она имеет су-

щественное преимущество: здесь не нужно задерживать выполнение команд так

часто, как в слабой согласованности.

Архитектуры UMA SMP с шинной организацией

В основе самых простых мультипроцессоров лежит одна шина, как показано на

рис. 8.17,

 а.

 Два или более процессоров и один или несколько модулей памяти ис-

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

Если шина занята, процессор просто ждет, когда она освободится. С этой раз-

работкой связана одна проблема. При наличии двух или трех процессоров доступ
к шине вполне управляем; при наличии 32 и 64 процессоров возникают трудности.

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

Чтобы разрешить эту проблему, нужно добавить кэш-память к каждому про-

цессору, как показано на рис. 8.17,

 б.

 Кэш-память может находиться внутри мик-

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