Введение

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

История

Безопасная семантика была впервые определена Лесли Лэмпортом в 1985 году. Она была формально определена в работе Лэмпорта "О межпроцессном взаимодействии" в 1986 году. Безопасный регистр был реализован во многих распределённых системах.

Описание

Безопасная семантика определяется для переменной с одним записывающим и несколькими читающими (SWMR). Регистр SWMR считается безопасным, если каждая операция чтения удовлетворяет следующим свойствам:

Операция чтения, не пересекающаяся с операцией записи, возвращает значение, записанное последней операцией записи. Операция чтения, пересекающаяся с операцией записи, может вернуть любое значение в допустимом диапазоне значений регистра (например, 0, 1, 2). В частности, при одновременном выполнении операций чтения и записи, чтение может вернуть значение, которое еще не было записано. Возвращаемое значение должно лишь принадлежать области определения регистра. Бинарный безопасный регистр можно рассматривать как модель мерцающего бита. Каким бы ни был предыдущий значение регистра, оно может мерцать до завершения записи. Следовательно, чтение, пересекающееся с записью, может вернуть 0 или 1. Churn – это добавление и удаление серверов из распределенной системы. Baldoni et al. показали, что ни один регистр не может обладать более строгим свойством регулярной семантики в синхронной системе при непрерывном churn. Однако безопасный регистр может быть реализован при непрерывном churn в несинхронной системе. Клиентские системы содержат конечное, произвольное число процессов, отвечающих за чтение и запись в серверную систему. Однако серверная система должна обеспечивать корректное выполнение операций чтения и записи.

Читать

Алгоритм чтения – это базовая версия объединения. Отличие заключается в механизме широковещательной рассылки, используемом операцией чтения. Клиент (cw) отправляет сообщение в систему, и как только сервер получает запрос, он отправляет ответное сообщение клиенту. Как только клиент получает достаточно ответов (n f j), он прекращает отправлять запросы.

Напиши .

Клиент (cw) отправляет запрос в систему в несколько этапов и ждет, пока не получит два подтверждения (ack). (sn = порядковый номер)

Причина получения двух подтверждений – предотвращение сбоев в системе. Когда процесс отправляет подтверждение (ack), он может завершиться через одну миллисекунду. Следовательно, клиент не получает подтверждения. Корректность безопасного регистра (если чтение не пересекается с записью, возвращается последнее записанное значение) была доказана на основе системы кворумов. Пусть заданы две системы кворумов (Qw, Qr), где Qw обозначает серверы, знающие последнее значение, а Qr – значения ответов на чтение. Размер каждого кворума равен n f j. Для доказательства корректности безопасного регистра необходимо доказать, что B – это количество византийских отказов. Доказательство: красная область обозначает (Qw∩Qr)\B, а синяя область – Qr∩B. Исходя из предположения о размере каждого кворума (n f j), красный регион содержит n 3f 2j активных серверов. Следовательно, строго больше, чем f.