Информатика · объяснение и практика
История общего регистра: найдите последовательный порядок внутри интервалов операций
Проверить линеаризуемость короткой истории чтений и записей регистра, сохраняя порядок неперекрывающихся операций и последовательную спецификацию.

В теме Операционные системы и память: углубление · Учебная карта
Главная мысль
Линеаризуемость требует разместить каждую завершённую операцию в одной точке между её вызовом и ответом. Полученный порядок должен соответствовать последовательной спецификации объекта и сохранять реальный порядок операций, которые не перекрывались во времени.
Метод и постановка
Запишите для каждой операции момент вызова, момент ответа, аргумент и возвращённое значение. Один журнал начала запросов не задаёт полную историю. Для регистра спецификация проста: запись заменяет значение, а чтение возвращает значение последней предшествующей записи либо начальное значение, если записей ещё не было.
Постройте обязательные отношения порядка. Если ответ одной операции был получен до вызова другой, первая должна стоять раньше в любой линеаризации. Перекрывающиеся операции можно упорядочить по-разному, если это допускают их интервалы и результаты. Затем ищите последовательный порядок, удовлетворяющий всем обязательным отношениям и всем возвращённым значениям. Для короткой истории достаточно явного перебора допустимых порядков, а не предположения, что сервер обрабатывает запросы по времени поступления.
Проверка и границы вывода
Проверка относится к конкретному объекту и его спецификации. Для очереди или счётчика условия возврата будут другими, хотя правило реального времени сохранится. История из нескольких независимо проверяемых объектов имеет полезные композиционные свойства, но их нельзя подменять произвольной транзакционной атомарностью группы операций.
Неполные операции требуют аккуратной модели: некоторые незавершённые вызовы можно дополнить ответами или исключить в соответствии с определением истории. Нельзя просто объявлять их завершёнными с удобным результатом без указания такого дополнения. Линеаризуемость также не гарантирует, что каждый вызов когда-нибудь завершится: это свойство допустимых результатов, а завершение относится к живости. В отчёте полезно предъявить конкретный последовательный порядок для положительного случая и короткий несовместимый набор требований для отрицательного.
Пример
Регистр сначала равен нулю. Запись единицы длится от времени 1 до 4, чтение длится от 2 до 3 и возвращает ноль. Эти операции перекрываются; чтение можно поставить перед записью, и история допустима.
Если второе чтение начинается в момент 5 и возвращает ноль без промежуточных записей, история недопустима. Завершившаяся к моменту 4 запись обязана предшествовать этому чтению, которое должно было вернуть единицу.
От чтения к действию
А теперь — вы
Частые вопросы
Перекрывающиеся операции обязаны следовать порядку вызовов?
Нет. Можно выбрать любой допустимый порядок, согласованный с интервалами и спецификацией.
Линеаризуемость обещает завершение?
Нет. Живость требует отдельного свойства и отдельного доказательства.
Углублённый разбор
Линеаризуемая очередь и порядок FIFO
Для очереди недостаточно найти порядок операций, совместимый с реальным временем. Этот порядок обязан также соблюдать FIFO: каждый успешный dequeue удаляет самое раннее ещё не удалённое помещение, а не произвольный ранее встречавшийся элемент.
Перед началом: Интервальная история; Последовательная FIFO очередь.
Спецификация связывает несколько возвращённых значений
Пусть очередь изначально пуста, enqueue добавляет элемент в хвост, а успешный dequeue возвращает и удаляет голову. Возвращаемые значения разных dequeue связаны одним состоянием очереди. Проверка «элемент когда-то добавляли» слишком слаба: она разрешила бы повторно удалить тот же экземпляр либо выдать поздний элемент раньше находящегося перед ним.
Реальный порядок требует A<B, если ответ A получен раньше вызова B. Перекрывающиеся операции могут занять любой совместимый порядок. Но это разрешение не отменяет FIFO. Для короткой истории удобно перебрать линейные расширения обязательного порядка и проиграть каждое на обычной последовательной очереди. При первом неверном возврате кандидат отбрасывается.
Завершение помещения не определяет его место в очереди
Операция может линеаризоваться задолго до собственного ответа. Поэтому сортировка enqueue по времени завершения способна дать неправильный порядок элементов. Аналогично сортировка по началу игнорирует допустимое переставление перекрывающихся операций. Линеаризация выбирает место внутри интервала, удовлетворяющее всем ответам истории одновременно.
Если значения уникальны, результаты последовательных dequeue часто восстанавливают относительный порядок соответствующих enqueue. При повторяющихся значениях нужны отдельные идентичности экземпляров или аккуратный перебор возможных соответствий: одинаковые буквы не означают один и тот же элемент. Для доказательства нарушения следует предъявить несовместимые ограничения, а не просто неудобный порядок одного перебора.
Положительный свидетель проверяет и интервалы, и FIFO
Найдя последовательный порядок, назначьте возрастающие точки внутри интервалов либо проверьте известное условие реального предшествования для интервальной истории. Затем выпишите состояния очереди после каждого шага. Это показывает, почему все возвращённые значения допустимы. Наличие допустимого порядка подтверждает данную историю, но не все исполнения реализации.
Пустой ответ dequeue требует отдельной спецификации: некоторые модели блокируются на пустой очереди, другие возвращают специальное значение EMPTY. В данной задаче используются только успешные удаления из непустой очереди. Поэтому нельзя добавлять неописанное пустое удаление для исправления неудобного порядка: оно изменило бы наблюдаемую историю и контракт объекта.
Длинное помещение между двумя короткими
Условие. Заданы enqueue A(a)=[0,8], B(b)=[1,3], C(c)=[4,5], затем dequeue D₁→b=[6,7], D₂→a=[9,10], D₃→c=[11,12]. Очередь первоначально пуста. Найдите линеаризацию.
- Реальное время требует B<C<D₁<D₂<D₃ и A<D₂. Операция A перекрывает B,C,D₁, поэтому её место ещё не задано этими отношениями.
- Возвраты b,a,c требуют порядка помещений B,A,C. Иначе FIFO либо поставит a перед b, либо c перед a.
- Порядок B,A,C,D₁,D₂,D₃ удовлетворяет обоим требованиям. Можно выбрать точки 2;3,5;4,5;6,5;9,5;11,5 внутри соответствующих интервалов.
- Состояния после помещений равны [b],[b,a],[b,a,c], а после удалений [a,c],[c],[] соответственно. Все возвращённые значения совпадают с историей.
Ответ. История линеаризуема в порядке B,A,C,D₁,D₂,D₃.
Проверка. Перебор всех 720 порядков шести операций с фильтрацией реального времени и проигрыванием FIFO находит единственный допустимый порядок.
Где легко ошибиться. Сортировка по ответам не заменяет линеаризацию: длинное помещение A завершилось поздно, но должно оказаться между B и C внутри своего интервала.
Проверьте понимание
Вопросы к этой главе
Почему A нельзя поставить после D₁?
Хотя интервалы это разрешают локально, C завершилась до D₁. Тогда c стояла бы перед поздним a, что противоречит возвратам a затем c.
Уникальность порядка обязательна?
Нет. Линеаризуемость требует хотя бы один допустимый порядок. В других историях перекрывающиеся операции могут оставаться переставляемыми без изменения наблюдаемых ответов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Herlihy and Wing: Linearizability, §2
Прочитаны complete(H), расширение истории ответами в §2.2 и последовательная спецификация очереди. Примеры с тремя помещениями и fetch-add созданы самостоятельно; численные интервалы и результаты не взяты из статьи.
Незавершённые операции в истории линеаризуемости
Незавершённый вызов мог уже изменить объект, хотя клиент ещё не получил ответ. Для проверки линеаризуемости нужно явно выбрать, какие такие вызовы дополнить ответами, а какие оставить вне завершённой части истории.
Перед началом: Неполная история операций; Атомарный fetch-add.
Дополнение добавляет ответы, а не меняет прошлые события
В определении допускается приписать в конец истории ответы к части ожидающих вызовов. Затем из расширенной истории берётся завершённая часть; остальные ожидающие вызовы не включаются в последовательный свидетель. Все уже наблюдённые вызовы и ответы сохраняются. Нельзя переписать существующий возврат или придумать вызов, которого в истории не было.
Выбор дополнения должен удовлетворять последовательной спецификации. Если ожидающий fetch-add(5) включён в историю, он действительно прибавляет пять и возвращает прежнее значение счётчика. Нельзя назначить ему любой удобный ответ. Приписанный поздний ответ позволяет точке действия находиться раньше, внутри длинного интервала между исходным вызовом и добавленным ответом.
Удаление всех ожидающих вызовов может потерять наблюдаемый эффект
Пусть чтение уже вернуло значение, которое мог создать только ожидающий вызов. Если механически удалить этот вызов, завершённая история окажется незаконной. Правильная проверка рассматривает также дополнение соответствующим ответом. Это отражает потерю ответа или задержку клиента, а не обязательный откат операции при отсутствии подтверждения.
Обратная ошибка — включить все ожидающие вызовы без проверки. Не каждый набор результатов совместим с уже завершёнными чтениями и реальным временем. Достаточно существования одного допустимого расширения; задача не требует доказать, что каждый возможный ответ ожидающей операции годится. Возможные расширения описывают неопределённость наблюдения, а не разрешение реализации нарушать свой контракт.
Свойство безопасности не обещает завершить вызов
Дополнение является частью математического свидетельства истории. Оно не утверждает, что реальная система обязательно пришлёт этот ответ в будущем. Завершение, отсутствие голодания и гарантии прогресса изучаются отдельно. Можно иметь допустимую конечную историю, в которой клиент навсегда ждёт ответ уже совершившейся операции.
В тесте полезно перебрать подмножества ожидающих вызовов, допустимые результаты их завершения и последовательные порядки. Для конечного примера со счётчиком значения ответов выводятся из состояния при проигрывании, поэтому не нужен бесконечный перебор целых чисел. После нахождения свидетеля нужно записать и включённые вызовы, и отброшенные: один порядок без этой информации оставляет важную часть проверки скрытой.
Чтение увидело ожидающее прибавление
Условие. Счётчик первоначально ноль. Процесс A вызывает fetch-add(5) в момент 0 и ответа пока нет. Другой процесс выполняет read→5 на [1,2]. Третий вызывает fetch-add(7) в момент 3 без ответа. История заканчивается после этих событий.
- Если удалить оба ожидающих прибавления, единственное чтение должно было бы вернуть начальный нуль. Такой завершённый фрагмент незаконен.
- Дополним первый fetch-add ответом 0 в конце истории и не будем дополнять второй. Последовательный свидетель имеет вид add5→0,read→5.
- Точка первого прибавления может лежать между моментами 0 и 1, а чтения — внутри [1,2]. Поздний приписанный ответ первому вызову этому не мешает.
- Второе прибавление можно также дополнить ответом 5 и поставить после чтения: получится конечное значение 12. Оба расширения допустимы; для положительной проверки достаточно первого.
Ответ. История линеаризуема, если учесть ожидающий add5; его согласованный ответ равен нулю.
Проверка. Перебор включаемых подмножеств и порядков выводит ответы fetch-add из текущего состояния: без add5 чтение 5 невозможно, с ним найден явный свидетель.
Где легко ошибиться. Отсутствие ответа не означает отсутствия эффекта. Дополнение должно быть явно предъявлено и проверено по спецификации, а не использовано как свободный выбор результатов.
Проверьте понимание
Вопросы к этой главе
Можно исключить завершённую операцию?
Нет. Обсуждаемое удаление относится только к вызовам, остающимся незавершёнными после выбранного расширения. Наблюдённый ответ обязательно сохраняется.
Дополнение доказывает доступность сервиса?
Нет. Оно устанавливает совместимость уже наблюдённой истории с атомарной спецификацией. Реальное получение ответа каждым клиентом относится к отдельной гарантии живости.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Herlihy and Wing: Linearizability, §2
Прочитаны complete(H), расширение истории ответами в §2.2 и последовательная спецификация очереди. Примеры с тремя помещениями и fetch-add созданы самостоятельно; численные интервалы и результаты не взяты из статьи.
Двойной сбор чтений и атомарный снимок регистров
Последовательное чтение нескольких атомарных регистров не обязательно даёт их совместное состояние. Два совпавших сбора становятся сертификатом снимка, если вместе со значениями читаются неповторяющиеся версии. Без версий возврат прежних значений может скрыть изменения между чтениями.
Перед началом: Атомарный регистр; Линеаризуемость.
Сбор значений не является одним атомарным действием
Пусть каждый компонент имеет одного писателя, а пара (значение,версия) читается и записывается атомарно. Версия строго увеличивается при каждой записи и в нашей модели не переполняется. Collect читает все компоненты последовательно. Возвращённый вектор может сочетать раннее значение первого регистра с поздним значением последнего, хотя такой комбинации одновременно никогда не существовало.
Простой snapshot повторяет collect до двух подряд одинаковых векторов полных пар. После совпадения возвращаются значения. Равенство только полезных данных недостаточно: писатель мог изменить 0 на1 и вернуть 0 между чтениями. Увеличение версии при обеих записях позволяет отличить это возвращение от отсутствия действий. Атомарность самой пары исключает смешивание нового значения со старой версией внутри одного чтения.
Общий промежуток даёт точку линеаризации
Для каждого компонента его одинаковые версии в двух сборах означают отсутствие записей между соответствующими чтениями. Все чтения первого collect закончились прежде начала второго. Возьмём любую точку между концом первого сбора и началом второго: она лежит внутри каждого из этих интервалов неподвижности. Значит все возвращаемые значения действительно существовали вместе в этой точке.
Это доказательство безопасности возвращённого результата, а не гарантия его получения за ограниченное число собственных шагов. Активный писатель может менять хотя бы одну версию между каждой парой сборов. Тогда читатель будет снова пробовать бесконечно. Для wait-free снимков нужны дополнительные идеи, например помощь писателей, но нельзя приписывать их простому двойному сбору.
Повтор полезных значений может скрывать невозможный вектор
Для двух регистров x,y рассмотрим только реальные состояния (0,1),(1,1),(1,0). Читатель успевает взять x=0 из первого и y=0 из третьего, получая несуществовавший вектор (0,0). Писатели могут вернуть систему к (0,1) и повторить ту же уловку. Два одинаковых результата ещё ничего не доказывают, пока счётчики изменений не включены в сравнение. Проверять нужно историю настоящих совместных состояний, а не отдельно законность каждого чтения.
Два ложных одинаковых сбора
Условие. Начало: x=(0,0), y=(1,0), вторые координаты — версии. Читатель дважды читает x, затем y. Перед каждым чтением y писатели меняют x на1, затем y на0. Между сборами они меняют y на1, затем x на0. Все записи увеличивают свою версию на1. Что дают сборы?
- Первый collect читает x=(0,0). После записей x=(1,1), y=(0,1) он читает y=(0,1). Полезный вектор равен (0,0).
- Между сборами появляются состояния (1,1), затем (0,1): версии y и x становятся 2. Одновременного состояния (0,0) не было.
- Второй collect читает x=(0,2), затем после очередных записей y=(0,3). Полезный вектор снова (0,0), но обе полные пары отличаются от первого collect.
- Алгоритм со сравниванием версий обязан продолжить. Если записи прекратятся в итоговом (1,0), два следующих одинаковых полных сбора подтвердят именно этот существующий вектор.
Ответ. Сравнение одних значений ошибочно приняло бы (0,0). Версии различают два сбора и не разрешают такой возврат.
Проверка. Независимый журнал совместных значений содержит только (0,1),(1,1),(1,0). Вычисленные полные результаты: ((0,0),(0,1)) и ((0,2),(0,3)). Их неравенство непосредственно проверяет отказ преждевременного завершения.
Где легко ошибиться. Не объявляйте простой двойной collect wait-free и не разрешайте незамеченное переполнение версий. Оба изменения убирают конкретную предпосылку доказанного результата.
Проверьте понимание
Вопросы к этой главе
Можно ли писателям одновременно менять разные компоненты?
Да. Каждый компонент должен иметь корректную атомарную пару и не повторяющуюся версию. Доказательство использует интервалы между его чтениями, а общий промежуток существует благодаря последовательности двух полных сборов.
Если писатели остановились, снимок всё-таки завершится?
Да, после прекращения записей два последующих полных сбора совпадут. Это полезное условное завершение, но wait-free требует конечного числа собственных шагов независимо от непрерывной активности остальных процессов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- James Aspnes: Atomic Snapshots, §2
Прочитан раздел о двух одинаковых collects с sequence numbers и отсутствии гарантии завершения простого алгоритма. Страница предупреждает о повреждённых формулах; используемый аргумент интервала дан в читаемом тексте и независимо доказан. Helping-алгоритм Afek здесь не реализуется.
Публикация hazard pointer защищает освобождение памяти
Атомарное чтение адреса не сохраняет жизнь узла по этому адресу. Hazard pointer публикует намерение пользоваться узлом, а повторная проверка корневого указателя закрывает гонку с удалением. Освобождение отделяется от исключения из структуры и происходит только после проверки опубликованных защит.
Перед началом: Указатель и время жизни; Атомарные чтения.
Удалить из списка и освободить память — разные события
Поток может прочитать head=A, затем остановиться до обращения к A.next. Другой поток уберёт A из структуры и освободит память. Когда первый продолжит, даже обычное чтение поля станет недопустимым. CAS с версией головы может обнаружить устаревшую модификацию позже, но не делает уже совершённое чтение освобождённой памяти безопасным.
В абстрактной модели все перечисленные атомарные действия последовательно согласованы. У каждого читателя есть собственный атомарный слот HP, доступный сканирующим потокам. Читатель берёт p=head, публикует HP=p и снова читает head. Лишь при равенстве он вправе обращаться к полям узла; при несовпадении очищает слот и повторяет попытку. Защита сохраняется непрерывно до последнего обращения к узлу.
Повторная проверка закрывает промежуток до публикации
Удаляющий поток сначала исключает узел из общедоступной структуры и помещает его в список retired. Позднее он читает hazard-слоты и освобождает только retired-узлы, адреса которых не найдены. Важно, что узел не должен снова стать доступным через прежнюю ссылку в нашем учебном сценарии: ниже адреса не переиспользуются и голова не возвращается к удалённому A.
Если успешная повторная проверка читателя была раньше удаления, HP уже опубликован и непрерывно остаётся равным A до завершения доступа. Поэтому последующий скан не разрешит преждевременное освобождение. Если удаление и скан опередили публикацию, повторная проверка увидит новую голову и запретит разыменование. Само хранение численного адреса в HP ещё не является чтением полей узла и не воскресает освобождённый объект.
Правильное время жизни не заменяет правильность структуры
После последнего доступа читатель очищает HP, и следующий скан может освободить задержанный узел. Замерший читатель способен продлить жизнь защищённому узлу; удаляющий поток не должен ждать снятия защиты, удерживая общий замок. Конкретные оценки памяти зависят от числа слотов и политики сканирования. Это отдельная задача от того, корректно ли обновлены связи списка или соблюдена абстрактная семантика очереди.
Для реального языка со слабой памятью недостаточно буквально перенести этот псевдокод с произвольными relaxed-операциями: публикация, повторная проверка и скан требуют доказанного порядка видимости. Здесь проверяется последовательная модель, а не набор инструкций конкретной архитектуры. Также нельзя автоматически объявлять решёнными все варианты ABA только потому, что освобождение теперь отложено.
Публикация, опоздавшая к скану
Условие. Начально head=A, HP пуст. T₁ сохраняет адрес A и останавливается. T₂ меняет head на B, помещает A в retired, видит пустой HP и освобождает A. Затем T₁ публикует HP=A и повторно читает голову. Адреса не переиспользуются. Что ему разрешено?
- Первое чтение T₁ дало только адрес. Поля A ещё не читались, поэтому до остановки обращения к освобождённой памяти не было.
- Во время скана T₂ защита отсутствовала, а A уже удалён из структуры. Поэтому в заданной модели его освобождение допустимо.
- После публикации T₁ повторная проверка возвращает B, которое не равно сохранённому A. Попытка должна отказаться от разыменования A, очистить HP и начать заново.
- Для сравнения: если HP=A и успешная проверка были опубликованы до удаления, скан обязан сохранить A в retired. Его можно освободить только после последнего доступа T₁, очистки слота и нового скана.
Ответ. T₁ обязан повторить попытку без чтения полей A. Поздняя публикация адреса не восстанавливает время жизни узла.
Проверка. Перебор взаимных порядков публикации, повторной проверки, удаления и скана показывает: либо защита видна при скане, либо проверка отвергает устаревший адрес. Контрольный вариант без повторной проверки допускает чтение уже освобождённого A.
Где легко ошибиться. Не разыменовывайте p между первым чтением head и успешной повторной проверкой. Публикация защиты и проверка достижимости должны предшествовать первому доступу к полям.
Проверьте понимание
Вопросы к этой главе
Почему одного опубликованного HP недостаточно?
Его могли записать уже после удаления и освобождения узла. Повторная проверка корневой ссылки различает эту ситуацию в заданной модели без возврата старого адреса. Только совместный протокол даёт право начать доступ.
Нужно ли атомарно снимать весь массив hazard-слотов?
Для непрерывно защищённого узла достаточно, что скан корректно прочитает его защищающий слот после удаления. Одновременный снимок всех слотов не является условием этого простого доказательства; модель видимости отдельных атомарных чтений должна быть указана.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Maged M. Michael: Hazard Pointers, §1–3
Прочитаны непрерывная защита до удаления, retire list, scan и повторная проверка достижимости перед разыменованием. Здесь явно задана абстрактная последовательная согласованность, не готовая реализация C++ с memory_order. Гарантии всего алгоритма структуры данных из защиты времени жизни не выводятся.
Последовательная согласованность двух регистров и цикл порядка программы
Каждый регистр по отдельности может иметь допустимый порядок чтений и записей, а совместная история всё равно не допускает последовательного объяснения. Причина — связи между операциями одного процесса. Построим цикл этих требований для двух регистров и проверим результат перебором всех допустимых чередований.
Перед началом: Атомарное чтение и запись регистра; Порядок операций процесса и ориентированный цикл.
Один общий порядок для всех регистров
Последовательная согласованность, или SC, требует существования единого полного порядка всех операций. Он сохраняет порядок программы каждого процесса, а чтение получает последнюю предшествующую запись в свой регистр либо начальное значение. Реальное время между разными процессами отдельно не фиксируется. Поэтому SC слабее линеаризуемости, но всё же связывает операции над разными объектами внутри одного процесса.
Рассмотрим начальные x=y=0. Процесс P сначала записывает x=1, затем читает y в a. Процесс Q сначала записывает y=1, затем читает x в b. Других записей нет. Даже без часов и длительностей известно Wx<Ry по программе P и Wy<Rx по программе Q. Эти две связи нельзя выбросить, анализируя каждый регистр изолированно.
Чтения начальных нулей замыкают цикл
Предположим a=b=0. Поскольку единственная неначальная запись в y устанавливает 1, чтение Ry=0 должно предшествовать Wy в общем порядке. Аналогично Rx=0 должно предшествовать Wx. Вместе с программными связями получаем Wx<Ry<Wy<Rx<Wx. Строгий полный порядок не содержит циклов, следовательно, такой результат не является SC.
При проекции только на x допустим локальный порядок Rx=0, затем Wx=1; при проекции только на y — Ry=0, затем Wy=1. Обе отдельные проекции согласованы, но склеить их с порядками программ нельзя. Это контрпример композиционности SC. Он отличается от проверки одного регистра: ошибка обнаруживается именно на пересечении объектных историй и процессных зависимостей.
Что показывает и чего не показывает литмус-тест
Четыре операции имеют шесть чередований, сохраняющих две программные пары. Ни одно не даёт два нуля; возможны пары(a, b)=(0,1), (1,0), (1,1). Перебор маленькой модели полезен как независимая проверка циклового аргумента. Он не заменяет определения памяти для реального языка: перенос такого теста на обычные неатомарные переменные может нарушать правила самого языка.
Доказательство запрещает конкретный результат в модели SC, а не любой исход конкурентного исполнения. Получение одного нуля допустимо: один процесс может успеть прочитать второй регистр до чужой записи. Аппаратные модели с буферами записи способны допускать другие результаты, но из этого не следует, что каждая отдельная операция неатомарна. Атомарность одного обращения и глобальная согласованность порядка — разные свойства.
Две локально допустимые истории без общего порядка
Условие. При x=y=0 выполняются P: Wx(1), Ry→a и Q: Wy(1), Rx→b. Проверьте возможность a=b=0 при SC и перечислите все возможные пары результатов.
- Программный порядок требует Wx<Ry и Wy<Rx.
- Для a=0 необходимо Ry<Wy; для b=0 необходимо Rx<Wx, потому что иных ненулевых записей в каждый регистр нет.
- Соединение требований даёт цикл Wx<Ry<Wy<Rx<Wx. Следовательно, пара(0,0) невозможна в SC.
- Перебор шести чередований пар P, Q даёт только(0,1), (1,0), (1,1). На каждой отдельной проекции пара нулей выглядела допустимой, но общего порядка не существует.
Ответ. SC запрещает(0,0); остальные три булевы пары достижимы. Согласованности отдельных регистров недостаточно.
Проверка. Чередование Wx, Ry, Wy, Rx даёт(0,1), обратное по процессам —(1,0), а Wx, Wy, Ry, Rx —(1,1). Эти свидетели вместе с циклом исчерпывают четыре возможные пары.
Где легко ошибиться. Не проверяйте общую память только по отдельным регистрам, теряя порядок программы между обращениями к разным объектам.
Проверьте понимание
Вопросы к этой главе
SC обязана сохранять реальное время между процессами?
Нет. Она сохраняет порядок каждого процесса; линеаризуемость дополнительно учитывает предшествование завершённой операции последующему вызову другого процесса.
Один нулевой результат тоже запрещён?
Нет. Первое чтение может предшествовать чужой записи. Запрещена именно совместная пара нулей, которая замыкает цикл общих требований.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Lamport1979: sequential consistency
Определение общего последовательного порядка. Здесь отдельно построены цикл объектных и процессных связей и полный конечный перебор результатов.
Seqlock проверяет чтение версии до и после данных
Читатель может успеть взять новый x и старый y между двумя записями. Счётчик последовательности не запрещает такую попытку, но не разрешает вернуть её результат. Покажем, почему нужны два одинаковых чётных значения и почему эта проверка не устраняет гонку данных в произвольном коде языка.
Перед началом: Атомарное чтение и последовательный порядок; Снимок нескольких значений.
Нечётность отмечает незавершённое обновление
Абстрактная последовательная согласованность, атомарные чтения полей, сериализованные писатели и не переполняющийся счётчик. Это не готовая реализация на слабой памяти C++.
Перед изменением полезных полей писатель увеличивает счётчик seq на единицу: из чётного он становится нечётным. Закончив все поля, писатель увеличивает его ещё раз. Несколько писателей должны быть сериализованы отдельно. Сам seqcount этого не обеспечивает: два перекрывшихся входа могли бы ошибочно сделать счётчик чётным посреди работы.
Читатель сначала берёт s₁=seq. При нечётном s₁ он не принимает попытку. При чётном копирует все необходимые поля в локальные переменные и снова читает s₂. Результат возвращается только при s₁=s₂ и чётности. Иначе повторяются и счётчик, и всё копирование; нельзя оставить ранний x от отвергнутой попытки.
Равенство версий даёт интервал неподвижности
В объявленном общем порядке каждый писатель меняет seq до и после полей. Если между двумя чтениями чётного seq произошло хотя бы начало или окончание записи, не повторяющийся счётчик уже отличался бы. Принятая попытка, следовательно, не пересекла запись. Её локальные значения существовали совместно внутри этого интервала.
Предположение об отсутствии переполнения существенно. Если счётчик обернулся к прежнему числу за время долгого чтения, числовое равенство уже не доказывает неподвижность. В реальной реализации нужны условия, исключающие такой сценарий в её диапазоне времени и частоте записей. Малый учебный счётчик по модулю два сертификатом не является.
Проверка не делает запрещённую операцию законной задним числом
В C++ одновременная запись и чтение обычного неатомарного поля без требуемой синхронизации может быть гонкой данных. Даже если читатель позже выбросит результат, уже выполненная операция не перестаёт нарушать модель языка. Приведённое доказательство использует атомарные поля и последовательную согласованность; перенос на другой порядок памяти требует отдельного доказательства.
Также нельзя безопасно пройти по указателю на освобождённый объект и надеяться заметить изменение seq после доступа. Время жизни памяти защищается иным протоколом. При непрерывных писателях читатель способен повторять попытки без конца: безопасность принятого снимка не равна wait-free завершению. В ядре Linux дополнительно учитываются вытеснение и контексты прерываний.
Смешанный снимок обнаруживается, повтор получает пару
Условие. Начально seq=0,x=0,y=0. Читатель берёт seq=0. Писатель ставит seq=1 и x=1. Читатель копирует x=1,y=0. Затем писатель ставит y=1,seq=2. Читатель повторно читает seq. Разрешён ли результат и что даст попытка после прекращения записей?
- Первое значение s₁=0 чётное, поэтому попытка начала копирование. Промежуточная пара (1,0) возможна во время обновления, но не должна возвращаться как согласованное завершённое состояние.
- Повторное чтение даёт s₂=2. Хотя оно тоже чётно, 2≠0, поэтому попытка отвергается. Одной чётности последнего числа недостаточно.
- Новая попытка читает s₁=2, затем x=1,y=1, после чего s₂=2. Записей между чтениями нет; оба условия выполнены.
- Возвращается (1,1). Если следующий писатель начал бы работу до второго чтения счётчика, попытка снова должна была бы повториться.
Ответ. Первую пару (1,0) вернуть нельзя. После прекращения записей принимается новая пара (1,1) при счётчиках 2 и 2.
Проверка. Перебор всех взаимных порядков четырёх действий писателя и четырёх чтений с сохранением порядка каждого участника подтверждает: каждая принятая пара соответствует состоянию вне незавершённого обновления.
Где легко ошибиться. Не заменяйте условие «одинаковый чётный счётчик до и после» одной проверкой чётности. Не разыменовывайте потенциально освобождённые указатели внутри отвергаемой попытки.
Проверьте понимание
Вопросы к этой главе
Кто сериализует двух писателей?
Отдельная блокировка или другой доказанный механизм. В Linux seqlock объединяет счётчик с блокировкой писателей; голый seqcount сам по себе её не содержит.
Почему не возвращать неповреждённое поле x после неудачи?
Задача требует согласованного набора, а не отдельных когда-то прочитанных значений. Новая попытка должна заново собрать весь результат под своим подтверждённым интервалом.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Linux Kernel: sequence counters and sequential locks
Прочитаны введение, seqcount и read/retry: чётность, сериализация писателей, ограничения указателей и контекста. Собственный атомарный SC-журнал не выдаётся за переносимую неатомарную реализацию.
Эпохи освобождения памяти требуют выхода всех старых читателей
Hazard pointer защищает конкретный адрес. Эпохальная защита действует иначе: объявляется интервал операции, внутри которого поток может обращаться к старым узлам. На журнале двух читателей определим момент безопасного освобождения и покажем, почему один остановившийся участник способен удерживать много памяти.
Перед началом: Удаление узла и время жизни памяти; Публикация состояния потока.
Перед первым доступом объявляется эпоха операции
Учебная эпохальная модель с последовательной согласованностью, монотонными номерами без переполнения и запретом сохранять доступные указатели после выхода из защищённой операции.
Глобальная эпоха возрастает. У потока есть атомарный слот: «неактивен» либо номер эпохи его текущей защищённой операции. Учебный вход читает глобальный номер e, публикует активный e, проверяет, что глобальный номер не изменился, и лишь после успешной проверки загружает общедоступный указатель. При несовпадении вход повторяется без обращения к полям узлов.
После последнего доступа поток отмечает себя неактивным. Нельзя вынести указатель наружу и затем читать его в следующей операции: между ними мог завершиться период ожидания и память могла быть освобождена. Начальное чтение эпохи, публикация и проверка — часть протокола, а не необязательная диагностика. Здесь предполагается корректная структура, где новый читатель после удаления уже не получает узел из живой общедоступной ссылки.
Узел ждёт окончания всех достаточно старых операций
Удаляющий сначала исключает узел из структуры, затем помещает его в retired с номером текущей эпохи E. Достаточное условие освобождения в этой абстракции: каждый поток либо неактивен, либо объявил эпоху строго больше E. Активный номер, равный E, тоже задерживает освобождение: его владелец мог увидеть узел до удаления.
Старый читатель, получивший узел до удаления, обязан непрерывно сохранять своё объявление до последнего доступа. Он либо виден сканированию как достаточно старый, либо уже завершил доступ. Читатель, который войдёт после проверки неактивного слота, загрузит общедоступную ссылку уже после удаления и старый узел не получит. Для реальной слабой памяти эти отношения нужно обеспечить доказанными барьерами; одних произвольных relaxed-операций недостаточно.
Ожидается группа операций, а не публикация каждого адреса
Пусть R₁ активен в эпохе 7, R₂ — в 8. Узел A удалён в 7. Даже если известно, что R₁ сейчас читает совершенно другой объект, общий эпохальный сертификат этого не различает. Он консервативно оставляет A в памяти до выхода R₁. После выхода R₁ активный R₂ с номером 8 уже не мешает освободить A.
Так уменьшается число публикаций при длинном обходе, но ухудшается изоляция задержек. Замерший участник может удерживать все последующие удалённые объекты, а не один адрес. Поэтому прогресс структуры и ограниченность очереди retired доказываются раздельно. Конкретные трёхэпохальные реализации используют циклические корзины и правила продвижения; наша проверка полного монотонного номера не заменяет их механическим сравнением остатков.
Разные удаления имеют разные ожидающие эпохи
Условие. Узел A удалён в эпохе 7, B — в 8. Слоты: R₁=active7, R₂=active8, R₃=inactive. Затем R₁ выходит; позже выходит R₂. На каждом шаге определите допустимое освобождение по объявленному критерию.
- Сначала R₁=7 не больше обеих эпох удаления, поэтому не разрешено освобождать ни A, ни B. Наличие более нового R₂ само по себе ничего не меняет.
- После выхода R₁ остаётся R₂=8. Для A условие 8>7 выполнено, а неактивные слоты не ограничивают проверку: A можно освободить.
- Для B условие 8>8 ложно. Равенство означает возможный старый доступ в той же эпохе, поэтому B остаётся в retired.
- После выхода R₂ все слоты неактивны, и B тоже разрешено освободить. Если R₁ никогда не вышел бы, оба объекта продолжали бы ждать без верхней границы по времени.
Ответ. Сначала ничего; после выхода R₁ только A; после выхода R₂ также B.
Проверка. Независимо строятся множества препятствий: для A сначала {R₁}, для B {R₁,R₂}; затем соответственно ∅ и {R₂}; наконец оба пусты. Это эквивалентно сравнению каждого активного номера с эпохой удаления.
Где легко ошибиться. Не освобождайте объект при равенстве активной эпохи и эпохи удаления. Не путайте отсутствие объявленного конкретного адреса с отсутствием потенциального старого читателя.
Проверьте понимание
Вопросы к этой главе
Это тот же протокол, что hazard pointers?
Нет. Здесь защищается весь интервал операции с набором возможных адресов. Hazard pointers публикуют конкретные адреса и имеют другой профиль задержки освобождения.
Можно ли считать неответивший поток неактивным по тайм-ауту?
Нет. Он может возобновиться с сохранённым указателем. Для безопасного принудительного вывода из эпохи нужен дополнительный протокол, который запрещает последующий старый доступ; время ожидания само по себе этого не доказывает.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Trevor Brown: epoch-based reclamation
Прочитаны вводное описание EBR и раздел Epochs о quiescent/grace period и остановившемся участнике. Здесь отдельно задана учебная монотонная модель, а не заявлена реализация трёх корзин или DEBRA+.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Конфликтный граф транзакций: цикл запрещает перестановку в последовательное расписание
Построить граф предшествования операций транзакций и проверить конфликтную сериализуемость по наличию цикла, отделяя её от более общих критериев эквивалентности.
Открыть темуСогласованный снимок не защищает ограничение между разными строками
Построить аномалию write skew при изоляции снимка и показать, почему отсутствие одновременной записи одной строки не обеспечивает сериализуемость.
Открыть темуCAP начинается с точных определений ответа и согласованности при разрыве связи
Разобрать невозможность одновременно гарантировать линеаризуемый регистр и доступность на обеих сторонах сетевого разделения в асинхронной модели.
Открыть тему