Реклама:

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

Семантику памяти можно рассматривать как контракт между программным и аппаратным обеспечением памяти [4]. Если программное обеспечение соглашается следовать определенным правилам, то память соглашается выдавать определенные результаты. Основная проблема здесь - сами правила, которые называются моделями состоятельности. Было предложено и разработано множество таких правил.

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

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

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

Секвенциальная состоятельность

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

Рассмотрим пример. Предположим, процессор 1 записывает значение 100 в слово х, а через 1 не процессор 2 записывает туда же значение 200. А теперь предположим, что через 1 не после начала второй операции записи (процесс записи еще не закончен) два других процессора, 3 и 4, считывают слово х по два раза (рис. 8.19).

Возможные варианты очередности шести событий представлены в табл. 8.4.

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

Рис. 8.19. Два процессора записывают, а другие два процессора считывают одно и то же слово из общей памяти

Таблица 8.4. Возможные варианты очередности событий согласно рис. 8.19

Вариант 1

Вариант 2

 

Вариант 3

 

Запись значения 100

Запись значения

Запись значения

Запись значения 200

Чтение значения

Чтение значения

 

процессором 3

 

процессором 4

 

Чтение значения 200

Запись значения

Запись значения

процессором 3

       

Чтение значения 200

Чтение значения

Чтение значения

процессором 3

процессором 4

 

процессором 3

 

Чтение значения 200

Чтение значения

Чтение значения

процессором 4

процессором 3

 

процессором 4

 

Чтение значения 200

Чтение значения

Чтение значения

процессором 4

процессором 4

 

процессором 3

 

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

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

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

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

Процессорная состоятельность - не слишком строгая модель, но зато ее легче реализовать на больших мультипроцессорах [78]. Она имеет два свойства:

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В, 2А, 2В, 1С, 2С, другие - 2А, 1А, 2В, 2С, 1В, 1С, третьи - еще какой-нибудь вариант. Единственное, что гарантируется абсолютно точно, - ни один процессор не увидит последовательность, в которой сначала выполняется операция 1В, а затем - 1А. Порядок, в котором выполняются обращения одного и того же процессора, остается одинаковым для всех наблюдателей.

Слабая состоятельность

В модели слабой состоятельности не гарантируется, что операции записи, произведенные одним процессором, будут восприниматься другими в том же порядке [59]. Один процессор может увидеть сначала операцию 1А, а потом 1В, другой - сначала 1В, потом 1А. Чтобы внести порядок в этот хаос, должны иметься переменные синхронизации памяти или поддерживаться операция синхронизации памяти. При синхронизации все незаконченные операции записи завершаются, и ни одна новая операция не может начаться, пока не будут завершены все предыдущие записи и не завершится сама синхронизация. Синхронизация приводит память в устойчивое состояние, когда не остается никаких незавершенных операций. Сами операции синхронизации являются секвенциально состоятельными, то есть если они инициируются несколькими процессорами, выбирается определенный порядок их выполнения, причем все процессоры воспринимают один и тот же порядок.

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

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

Рис. 8.20. В слабо состоятельной памяти периодически выполняются операции синхронизации

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

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

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

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

Вопрос о состоятельности памяти нельзя считать окончательно решенным. Исследователи до сих пор предлагают новые модели [35, 86].

Мультипроцессоры и мультикомпьютеры || Оглавление || UMA-мультипроцессоры в симметричных мультипроцессорных архитектурах