Регулярная семантика - Regular semantics

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

Пример

Регулярная семантика слабее линеаризуемости. Рассмотрим пример, показанный ниже, где горизонтальная ось представляет время, а стрелки представляют интервал, в течение которого выполняется операция чтения или записи. Согласно определению обычного регистра, третье чтение должно возвращать 3, поскольку операция чтения не выполняется одновременно с какой-либо операцией записи. С другой стороны, второе чтение может возвращать 2 или 3, а первое чтение может возвращать либо 5, либо 2. Первое чтение может возвращать 3, а второе чтение может возвращать 2. Такое поведение не удовлетворяет атомарной семантике. Следовательно, регулярная семантика является более слабым свойством, чем атомарная семантика. С другой стороны, Лампорт доказал, что линеаризуемый регистр может быть реализован из регистров с безопасная семантика, которые слабее обычных регистров.

Безопасный регистр

Теорема от регулярности к атомарности

Однократное устройство чтения с несколькими считывающими устройствами (SWMR) атомарная семантика является регулярным регистром SWMR, если любая из его истории выполнения H удовлетворяет следующему свойству: r1 и r2 - любые два вызова чтения: (r1 → H r2) ⇒ ¬π (r2) → H π (r1)

Прежде чем мы перейдем к доказательству, сначала мы должны знать, что означает новая / старая инверсия. Как показано на рисунке ниже, посмотрев на выполнение, мы можем увидеть, что единственная разница между обычным и атомарным исполнением - это когда a = 0 и b = 1. В этом исполнении, когда мы рассматриваем два вызова чтения R .read () → a, за которым следует R.read () → b, наше первое значение (новое значение) равно a = 0, а второе значение (старое значение) - b = 1. На самом деле это главное различие между атомарностью и регулярностью.

Рисунок 1

Вышеупомянутая теорема утверждает, что обычный регистр с несколькими читателями с единственной записью без новой или старой инверсии является атомарным регистром. Глядя на рисунок, мы можем сказать, что при R.read () → a → H R.read () → band R.write (1) → H R.write (0) невозможно иметь π (R .read () → b) = R.write (1) и π (R.read () → a) = R.write (0), если выполнение является атомарным. Для доказательства приведенной выше теоремы сначала мы должны доказать, что регистр безопасен, затем мы должны показать, что регистр является регулярным, а затем, в конце, мы должны показать, что регистр не допускает новую / старую инверсию, которая доказывает атомарность. По определению атомарного регистра мы знаем, что атомарный регистр с несколькими читателями Single Writer является обычным и удовлетворяет свойству no new / oldinversion. Итак, нам нужно только показать, что обычный регистр без новой / старой инверсии является атомарным.

Мы знаем, что для любых двух вызовов чтения (r1 и r2), когда регистр является регулярным и нет новой / старой инверсии (r1 → H r2) ⇒sn (π (r1)) ≤ sn (π (r2)). Для любого выполнения (M) существует общий порядок (S), который включает в себя те же вызовы операций. Мы можем заявить, что S построен следующим образом: мы начинаем с общего порядка операций записи и вставляем операцию чтения следующим образом: сначала: операция чтения (r) вставляется после связанной операции записи (π (r)) Во-вторых: если две операции чтения (r1, r2) совпадают (sn (r1) = sn (r2)), то сначала вставьте операцию, которая начинается первой в выполнении. S включает в себя все вызовы операции M, из которых она следует, что S и M эквивалентны. Поскольку все операции упорядочены в соответствии с их порядковыми номерами, S - это немного общий порядок. Более того, этот общий порядок является выполнением M только добавляет порядок операций, которые перекрываются в M. Если нет перекрытия между операциями чтения и записи, нет никакой разницы между регулярностью и атомарностью. Наконец, мы можем заявить, что S является допустимым, поскольку каждая операция чтения получает последнее записанное значение, которое предшествует ей в общем порядке. Следовательно, соответствующая история линеаризуема. Поскольку это рассуждение не опирается на конкретную историю H, оно подразумевает, что регистр является атомарным. Поскольку атомарность (линеаризуемость) является локальным свойством, мы можем утверждать, что набор регулярных регистров SWMR ведет себя атомарно, как только каждый из них удовлетворяет свойству инверсии «нет нового / старого».

Рекомендации