Неспекулятивное распределенное разрешение конфликтов для протокола когерентности кэш-памяти

Неспекулятивное распределенное разрешение конфликтов для протокола когерентности кэш-памяти

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

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

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

На Фиг.1a-1e показана концептуальная иллюстрация конфликтной ситуации в многоузловой системе. Узлы 110, 120 и 130 являются одноранговыми узлами, которые могут хранить копию запрашиваемых данных (например, строку кэша) в кэш-памяти. Базовый узел 140 является для запрашиваемых данных базовым (H) узлом. В примере по Фиг. с 1а по 1e одноранговые узлы 110 и 120 хранят недостоверную копию или не хранят вообще никакой копии запрашиваемых данных, а одноранговый узел 130 хранит измененную копию запрашиваемых данных, которая не была перезаписана в память. Базовый узел хранит в памяти первоначальную копию данных или измененные варианты данных, если изменения перезаписаны в память.

Как показано на Фиг.1a, одноранговый узел 120, чтобы запросить копию блока данных, например строку кэша, передает сообщение "Запрос Данных" (Data Request). Сообщение "Запрос Данных" передают одноранговому узлу 110 и одноранговому узлу 130. Однако сообщение "Запрос Данных" к одноранговому узлу 130 задерживают. Задержка может быть вызвана, например, нехваткой доступной полосы пропускания, буферизацией и т.д.

Одноранговый узел 110 отвечает на сообщение "Запрос Данных" однорангового узла 120 сообщением "Отсутствие Достоверной Копии" (No Valid Copy), которое указывает одноранговому узлу 120 на то, что одноранговый узел 110 не имеет достоверной копии запрашиваемых данных. Через некоторое время после передачи одноранговым узлом 120 сообщения "Запрос Данных" одноранговый узел 110, как показано на Фиг.1c, передает сообщение "Запрос Данных" одноранговым узлам 120 и 130, запрашивая те же данные, которые запрашивал одноранговый узел 120.

Одноранговый узел 120 отправляет одноранговому узлу 110 в ответ на сообщение "Запрос Данных" сообщение "Отсутствие Достоверной Копии". Одноранговый узел 130 отправляет запрашиваемые данные одноранговому узлу 110. Копия данных, если таковая имеется, поддерживаемая одноранговым узлом 130, помечена как недостоверная, а копия данных, сохраненная одноранговым узлом 110, помечена как Измененная.

Через некоторое время после того, как одноранговый узел 130 ответил на "Запрос Данных" однорангового узла 110 и пометил копию данных как недостоверную, как достоверное одноранговый узел 130, как показано на Фиг.1c, принимает задержанное сообщение "Запрос Данных" от однорангового узла 120. В ответ на сообщение "Запрос Данных" одноранговый узел 130 отправляет сообщение "Отсутствие Достоверной Копии" одноранговому узлу 120. Необходимо отметить, что состояние данных, хранимых одноранговым узлом 130, изменено со времени первоначального сообщения "Запрос Данных" ко времени ответа однорангового узла 130 на сообщение "Запрос Данных".

Поскольку одноранговые узлы 110 и 130 отвечают на сообщение "Запрос Данных" однорангового узла 120 сообщениями "Отсутствие Достоверной Копии", одноранговый узел 120, не обнаружив ни одной достоверной кэшированной копии запрашиваемых данных, запрашивает копию данных у базового узла 140. Таким образом, как показано на Фиг.1d, одноранговый узел передает сообщение "Чтение" (Read) базовому узлу 140. Базовый узел 140 извлекает запрашиваемые данные из памяти и отправляет данные одноранговому узлу 120. Одноранговый узел 120 затем сохраняет запрошенные данные в Исключительном (Exclusive) состоянии.

Как показано на Фиг.1e, последовательность сообщений, показанная на Фиг.с 1а по 1e, приводит в результате к существованию двух несовместимых копий строки данных. В приведенном примере одноранговый узел 110 хранит копию данных в Измененном состоянии, а одноранговый узел 120 хранит копию данных в Исключительном состоянии. Однако копия, сохраненная одноранговым узлом 120, не является исключительной по отношению к одноранговому узлу 120. Таким образом, в многоузловых системах при некоторых обстоятельствах могут возникать несовместимые копии данных, если не обеспечен механизм для разрешения конфликтов кэша.

Перечень фигур чертежей

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

Фиг. с 1a по 1e - концептуальные представления состояния конфликта в многоузловой системе.

Фиг.2a и 2b - концептуальные представления запроса совместно используемой кэшированной строки.

Фиг.3а и 3b - концептуальные представления запроса совместно используемой некэшированной строки.

Фиг. с 4a по 4f - концептуальные представления трехсторонних конфликтующих запросов совместно используемой строки.

Фиг. с 5a по 5g - концептуальные представления трехсторонних конфликтующих запросов совместно используемой строки.

Фиг.6 - блок-схема одного из вариантов выполнения узла.

Фиг.7 - один из вариантов выполнения многопроцессорной системы.

Подробное описание изобретения

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

Сообщения Запроса

Следующие сообщения являются запросами данных/действия от запрашиваемого узла. Эти сообщения являются широковещательными ко всем узлам системы.

Считать Строку (Port Read Line, PRL): Это запрос копии сегмента данных, такого как, например, строка кэша.

Считать Недостоверную Строку (Port Read Invalidate Line, PRIL): Это запрос копии сегмента данных, в случае если копия данных узла-поставщика является недостоверной. Это сообщение может также упоминаться как "запрос на вступление во владение".

Записать строку (Port Write Line, PWL): Это сообщение инициирует запись данных (например, измененной строки кэша) в память. Это сообщение может также упоминаться как "замещение испорченных данных".

Пометить строку как Недостоверную (Port Invalidate Line, PIL): Это сообщение вызывает изменение состояния намеченных данных c состояния Совместного Использования на Исключительное состояние.

Записать Строку и пометить как Недостоверную (Port Write Invalidate Line, PWIL): Это сообщение инициирует запись данных в память и делает целевую копию данных недостоверной.

Ответные сообщения

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

Подтверждение Недостоверного Состояния (Invalid State Acknowledgement, IACK): Это сообщение является ответом на запрос (PRL, PRIL, PIL, PWIL), когда узел, отправляющий ответ, имеет недостоверную копию запрашиваемых данных или вообще не имеет копии запрашиваемых данных.

Подтверждение Состояния Совместного Использования (Shared State Acknowledgement, SACK): Это сообщение является ответом на запрос PRL, когда на узле, отправляющем ответ, имеется копия запрашиваемых данных в состоянии Совместного Использования.

Подтверждение Приема Данных (Acknowledgement of Data Received, DACK): Это сообщение подтверждает прием запрашиваемых данных. Это сообщение отправляет базовый узел, когда базовый узел принимает сообщение CNCL. Целевым узлом для сообщения DACK является узел пересылки, включенный в сообщение CNCL. Узел, принимающий переданные данные или данные памяти базового узла, не отвечает отправляющему узлу.

Конфликт(CNFL): Это сообщение указывает на то, что имеется одновременно обрабатываемый запрос на запрашиваемую строку кэша.

Данные [Конфликты] (Data): Это сообщение используется для пересылки данных и списков конфликтов, если таковые имеются. Список конфликтов пуст, если данные пересланы или если базовый узел отправляет данные из памяти первому владельцу. При передаче данных отправляющий узел присоединяет список конфликтов. Принимающий узел использует список для отправки ответов CNFL на соответствующие запросы, сохраненные в буфере.

Сообщения на базовый узел

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

Чтение [Конфликты](READ): Это сообщение запрашивает данные от базового узла и перечисляет конфликты, если таковые существуют. Это сообщение отправляется после того, как одноранговым узлом приняты все ответы, если ни одно из принятых сообщений не было сообщением DATA.

Отмена (Конфликты)(CNCL): Это сообщение отправляется базовому узлу в ответ на обращение к кэшу в Одноранговом узле и перечисляет все конфликты, если таковые существуют. Это сообщение отменяет операцию выборки с упреждением, выполняемую базовым узлом.

Сообщения от базового узла

Эти сообщения отправляются базовым узлом на Одноранговые и/или Запрашивающие узлы.

Данные(DATA): Это сообщение включает в себя запрашиваемые данные и может указывать состояние данных (M/E/F), которые должны быть использованы Запрашивающим узлом.

Подтверждение (ACK): Это сообщение указывает, что запрашиваемые данные были отправлены Запрашивающему узлу. После отправки базовым узлом сообщения ACK текущий период является завершенным.

Передача (XFR): Это сообщение предписывает принимающему узлу отправлять данные узлу, указанному в сообщении. Базовый узел отправляет это сообщение текущему владельцу запрашиваемых данных, если базовый узел информирован относительно состояния конфликта, требующего, чтобы текущий владелец данных передал данные целевому узлу. Вместо сообщения XFR передается сообщение XFRI, если базовый узел определяет, что нерешенным конфликтующим запросом является сообщение PRIL или PWIL, что означает, что текущий владелец должен обозначить строку как недостоверную при инициировании передачи данных. В одном варианте выполнения первый узел за период, который отправит сообщение CNCL, является текущим владельцем. Период в данном контексте - это период между первым запросом данных и разрешением всех конфликтов запросов данных. Если базовый узел отправляет данные в узел из памяти, то этот узел является текущим владельцем. Отправка сообщения XFR/XFRI предписывает целевому узлу стать текущим владельцем. В одном варианте выполнения целевой узел выбран из списка конфликтов, предоставленного базовому узлу в сообщении READ или CNCL. Целевые узлы выбраны из узлов, от которых базовый узел принял сообщение READ. Таким образом, если базовый узел считает узел А текущим владельцем строки кэша, так как узел А отправил базовому узлу сообщение CNCL(B, C), базовый узел ждет приема сообщения READ от узлов В или С, чтобы послать сообщение XFR/XFRI на узел А, чтобы предписать узлу А переслать данные узлу (B или C), который отправил сообщение READ. Базовый узел затем ждет отправки от третьего узла сообщения READ перед отправкой сообщения XFR/XFRI, предписывающего третьему узлу послать данные.

Краткое описание протокола MESIF

Есть две основных схемы обеспечения когерентности кэша, схема наблюдения (теперь часто называемая Симметричной Многопроцессорной обработкой (SMP)) и схема каталогов (часто называемая Распределенная Совместно Используемая Память (DSM)). Фундаментальное различие между ними состоит в размещении и доступе к метаинформации, то есть информации о том, где хранятся копии строки кэша.

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

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

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

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

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

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

Основной протокол MESIF включает в себя широковещательную передачу первоначального запроса ко всем одноранговым узлам, так же как и к базовому узлу. Если копия кэширована в состоянии E, F или М, то это включено в ответ. Затем базовому узлу отправляют второе сообщение, информирующее его о том, что запрос был удовлетворен. Если запрошенная строка некэшированная или если существуют только копии в S-состоянии, второй запрос, отправленный базовому узлу, используется для подтверждения предыдущего запроса, данные по которому базовый узел, возможно, к этому времени выбрал из своей памяти. В любом случае базовый узел должен ответить на второй запрос (и на первый, хотя они иногда могут объединяться) для обеспечения синхронизации и разрешения конфликтов. Необходимо отметить, что базовый узел может иметь один или более кэшей, так что он может ответить на первоначальный запрос точно так же, как любой другой узел.

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

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

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

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

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

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

Краткое описание неспекулятивного распределенного разрешения конфликтов

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

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

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

В одном варианте выполнения распределенное разрешение конфликтов, описанное здесь, является частью протокола кэша, упоминаемого как протокол MESIF, в котором с кэшированной копией строки кэша ассоциировано одно из пяти состояний (Измененное (M) состояние, Исключительное (Е) состояние, состояние совместного использования (S), Недостоверное (I) состояние, состояние пересылки (F)). В одном варианте выполнения период молчания после всех ответов на запрос, пока не было принято сообщение подтверждения от базового узла, обеспечивает осведомленность всех конфликтующих узлов о конфликтах, в которые вовлечены эти узлы. Период молчания не ограничивает использование данных в кэше, но действительно предотвращает распространение данных в другие кэши.

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

Фиг.2a и 2b являются концептуальными представлениями запроса совместно использованной кэшированной строки. Связанная с различными сообщениями по Фиг.2a и 2b нумерация (например, 1. PRIL, 7. IACK), с целью объяснения примера конфликта обеспечивает приблизительное упорядочение. Точные временные соотношения связей, изображенных на Фиг.2a и 2b, а также и в других приведенных примерах (то есть Фиг.3a-3f), не требуются.

Как показано на Фиг.2a, одноранговый узел 210 передает сообщение PRIL одноранговым узлам 220 и 230 и базовому узлу 240. Одноранговый узел 210 также мог бы запросить тот же блок данных, используя сообщение PRL, в каковом случае одноранговый узел 230 в ответ на сообщение запроса не пометил бы свою копию как недостоверную. Одноранговый узел 220 отвечает на сообщение PRIL сообщением IACK, указывающим на то, что одноранговый узел 220 не может предоставить достоверную копию запрашиваемых данных. Одноранговый узел 220 показан изначально содержащим копию запрашиваемых данных в состоянии S, которая является достоверной копией данных, но не является копией, которая может быть предоставлена в ответ на запрос копии данных.

Так как сообщение PRIL запрашивает копию данных и предписывает всем другим копиям пометить как недостоверные оставшиеся копии данных, одноранговый узел 220 переводит свою копию данных из S-состояния в I-состояние. Поскольку одноранговый узел 230 содержит копию запрошенных данных в F-состоянии (единственная достоверная копия, которая должна быть предоставлена запрашивающему узлу), одноранговый узел 230 предоставляет одноранговому узлу 210 копию запрашиваемых данных. Одноранговый узел 230 также переводит свою копию запрашиваемых данных в I-состояние. Одноранговый узел 210 сохраняет запрошенные данные в E-состоянии. В качестве альтернативы одноранговый узел 210 хранит запрошенные данные в F-состоянии.

Как показано на Фиг.2b, в ответ на прием запрашиваемых данных от однорангового узла 230 одноранговый узел 210 отправляет базовому узлу 240 сообщение CNCL(230)(), которое предписывает базовому узлу 240 отменить извлечение запрашиваемых данных из памяти (или отменить передачу данных, если они уже извлечены). Сообщение CNCL(230)() также указывает базовому узлу 240 на то, что копия запрашиваемых данных была принята от однорангового узла 230 и что одноранговый узел 210 не обнаружил никаких конфликтов, запрашивая данные сообщением PRIL.

В ответ на сообщение CNCL(230)() от однорангового узла 210 базовый узел 240 передает сообщение ACK одноранговому узлу 210 и сообщение DACK одноранговому узлу 230. Сообщение ACK указывает одноранговому узлу 210 на то, что базовый узел 240 подтверждает прием сообщения CNCL(230)(). Сообщение DACK от однорангового узла 240 одноранговому узлу 230 подтверждает прием данных одноранговым узлом 210 и завершает процесс запроса данных одноранговым узлом 210.

Фиг.3а и 3b являются концептуальными представлениями запроса совместно используемой некэшированной строки. Как показано на Фиг.3а, одноранговый узел 210 для запроса копии блока данных передает сообщение PRIL. Поскольку одноранговые узлы 220 и 230 не хранят достоверную копию запрашиваемых данных, узлы 220 и 230 отвечают сообщением IACK.

Как изображено на Фиг.3b, так как одноранговый узел 210 принял сообщение IACK от всех одноранговых узлов, одноранговый узел 210 отправляет базовому узлу 240 сообщение READ(), которое запрашивает копию предварительно запрошенных данных, которые были извлечены из памяти базовым узлом 240. Сообщение READ() также указывает базовому узла 240 на то, что одноранговый узел 210 не обнаружил никаких конфликтов с сообщением PRIL. Базовый узел 240 предоставляет копию запрашиваемых данных с помощью сообщения DataE. В одном варианте выполнения базовый узел 240 также включает сообщение ACK в сообщение DataE (то есть в один и тот же пакет сообщений). В альтернативном варианте выполнения сообщения DataE и ACK передают отдельно.

На Фиг. с 4a по 4f показано концептуальное представление трехсторонних конфликтующих запросов на совместно используемую кэшированную строку. Как изображено на Фиг.4a, одноранговый узел 210 отправляет сообщение PRL одноранговым узлам 220 и 230 и базовому узлу 240. Сообщение PRL, предназначенное базовому узлу 240, по каким-либо причинам задержано, например, из-за задержки времени ожидания в системе 200. Так как ни одноранговый узел 220, ни одноранговый узел 230 в ответ на сообщение PRL не может предоставить достоверную копию запрашиваемых данных, одноранговый узел 220 и одноранговый узел 230 отправляют одноранговому узлу 210 сообщения IACK.

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

Как показано на Фиг.4b, через некоторое время после приема одноранговым узлом 220 от однорангового узла 210 сообщения PRL, и прежде чем базовый узел 240 принимает сообщение PRL от однорангового узла 210, одноранговый узел 220 передает сообщение PRIL, запрашивая тот же самый блок данных. Одноранговый узел 220 передает сообщение PRIL одноранговым узлам 210 и 230 и базовому узлу 240; однако сообщение PRIL, предназначенное одноранговому узлу 210, задержано. Одноранговый узел 230 и базовый узел 240 отвечают на сообщение PRIL однорангового узла 220 сообщениями IACK.

Как показано на Фиг.4c, одноранговый узел 230 впоследствии передает сообщение PRIL одноранговым узлам 210 и 220 и базовому узлу 240. Базовый узел 240 отвечает на сообщение PRIL сообщением IACK, указывающим на то, что на базовом узле 240 отсутствует достоверная копия запрашиваемых данных. Одноранговый узел 210 отвечает на сообщение PRIL однорангового узла 230 сообщением CNFL, указывающим на то, что одноранговый узел 210 имеет конфликт с сообщением PRIL, принятым от однорангового узла 230.

Одноранговый узел 220 отвечает на сообщение PRIL однорангового узла 230 сообщением CNFLI, указывающим на то, что одноранговый узел 220 имеет конфликт с сообщением PRIL, принятым от однорангового узла 230. Сообщение CNFLI указывает на то, что конфликтным сообщением однорангового узла 220 является сообщение PRIL, требующее признания копии данных недостоверной. Сообщение CNFL однорангового узла 210 указывает на то, что конфликтным сообщением однорангового узла 210 является сообщение PRL, не требующее признания копии данных недостоверной.

Как показано на Фиг.4d, после приема базовым узлом 240 задержанного сообщения PRL однорангового узла 210 базовый узел 240 отвечает сообщением IACK, указывающим на то, что на базовом узле 240 отсутствует достоверная копия запрашиваемых данных.

В ответ на прием сообщения CNFL от однорангового узла 210 и сообщения CNFLI от однорангового узла 220, одноранговый узел 230 передает базовому узлу 240 сообщение READ(210, 220*). Сообщение READ(210, 220*) запрашивает копию данных из памяти, управляемой базовым узлом 240. Сообщение READ(210, 220*) также указывает на то, что запрос данных однорангового узла 230 конфликтует с запросами одноранговых узлов 210 и 220 и что запрос однорангового узла 220 требует признания копии данных недостоверной (как обозначено звездочкой). Поскольку одноранговый узел 230 первым из узлов с конфликтующими запросами отправил сообщение READ базовому узлу 240, одноранговый узел 230 является первым одноранговым узлом, принявшим копию запрашиваемых данных, и текущим владельцем запрашиваемых данных.

В ответ на сообщение READ(210, 220*) базовый узел предоставляет одноранговому узлу 230 запрашиваемые данные в сообщении DataE. Сообщение DataE предписывает одноранговому узлу 230 сохранить данные в состоянии E. В качестве альтернативы могли быть использованы другие сообщения данных (например, DataF, DataS). Базовый узел 240 для ответа на последующие сообщения READ/CNCL одноранговых узлов 210 и 220 поддерживает список конфликтов, предоставленный одноранговым узлом 230.

Как показано на Фиг.4e, в ответ на сообщение IACK от базового узла 240 одноранговый узел 210 передает базовому узлу 240 сообщение READ(230*). Сообщение READ не указывает на конфликт с сообщением PRIL однорангового узла 220, потому что одноранговый узел 210 пока еще не принял это сообщение PRIL. Если бы одноранговый узел 210 принял сообщение PRIL от однорангового узла 220, то сообщение READ указало бы на конфликт с одноранговым узлом 220.

В ответ на сообщение READ(230*) базовый узел 240 отправляет одноранговому узлу 230 сообщение XFRI(210), предписывающее одноранговому узлу 230 отправлять запрашиваемые данные одноранговому узлу 210. Сообщение XFRI также указывает одноранговому узлу 230 на то, что конфликтующее сообщение однорангового узла, который еще не принял данные (одноранговый узел 220), требует после отправки данных одноранговому узлу 210 признания данных недостоверными.

Одноранговый узел 230 отправляет запрашиваемые данные одноранговому узлу 210 в сообщении DataE(220), которое предписывает одноранговому узлу 210 сохранить запрашиваемые данные в состоянии E, и информирует одноранговый узел 210 о том, что запросное сообщение, возможно, конфликтует с сообщением однорангового узла 220. Одноранговый узел 230 обнаружил конфликт с сообщением однорангового узла 220. До того как одноранговый узел 210 примет запрашиваемые данные, принимают задержанное сообщение PRIL от однорангового узла 220.

Поскольку одноранговый узел 210 уже доставил свой список конфликтов на базовый узел 240 и не принял запрашиваемые данные от однорангового узла 230, одноранговый узел 210 сохраняет в буфере сообщение PRIL, принятое от однорангового узла 220. В ответ на прием сообщения DATA от однорангового узла 230, имеющего конфликт с одноранговым узлом 220, одноранговый узел 210 отправляет сообщение CNFL, указывающее на то, что одноранговый узел 210 имеет конфликт с сообщением PRIL однорангового узла 220.

Как показано на Фиг.4f, в ответ на сообщение CNFL от однорангового узла 210 одноранговый узел 230 отправляет сообщение READ(210, 230*) базовому узлу 240, указывающее на наличие конфликта с сообщением PRL однорангового узла 210 и с сообщением PRIL однорангового узла 230. Базовый узел 240 отвечает на сообщение READ(210, 230*) сообщением ACK одноранговому узлу 220 и сообщением XFRI(220) одноранговому узлу 210. Одноранговый узел 210 отправляет запрашиваемые данные одноранговому узлу 220 в сообщении DataE(230). Одноранговый узел 220 предварительно определил наличие конфликта с одноранговым узлом 230. Доставка сообщения ACK одноранговому узлу 220 указывает на отсутствие дальнейших конфликтов с сообщением PRIL однорангового узла 220.

Фиг. с 5a по 5g являются концептуальными представлениями трехсторонних конфликтующих запросов на некэшированную строку данных. Как показано на Фиг.5a, одноранговый узел 210 для запроса блока данных отправляет сообщение PRIL одноранговым узлам 220 и 230 и базовому узлу 240. Доставка сообщения PRIL базовому узлу 240 задержана. Вскоре после отправки сообщения PRIL одноранговым узлом 210 одноранговый узел 220 отправляет сообщение PRIL, запрашивающее копию того же самого блока данных, одноранговым узлам 210 и 230 и базовому узлу 240.

Как изображено на Фиг.5b, одноранговый узел 230 отвечает на сообщение PRIL однорангового узла 210 сообщением IACK. Одноранговый узел 230 указывает на задержку во время обработки его ответа на сообщение PRIL однорангового узла 220. Одноранговый узел 210 отвечает на сообщение PRIL однорангового узла 220 сообщением CNFLI. Точно так же одноранговый узел 220 отвечает на сообщение PRIL от однорангового узла 210 сообщением CNFLI.

Как изображено на Фиг.5c, до приема узлами 210 и 220 копии запрашиваемых данных одноранговый узел 230 отправляет сообщение PRIL одноранговым узлам 210 и 220 и базовому узлу 240. Одноранговые узлы 210 и 220 отвечают на сообщение PRIL от однорангового узла 230 сообщениями CNFLI. Из-за задержки обработки сообщения PRIL однорангового узла 220 одноранговый узел 230 отправляет одноранговому узлу 220 вместо сообщения IACK сообщение CNFLI, чтобы указать на наличие конфликта с недавно сгенерированным одноранговым узлом 230 запросом на тот же самый блок данных.

Как изображено на Фиг.5d,