La semántica regular es un modelo de consistencia del hardware de una computadora . Describe un tipo de garantía proporcionada por un registro de procesador que es compartido por varios núcleos de procesador en una máquina paralela o en una red de computadoras que trabajan juntas. La semántica regular se define para una variable con un solo escritor pero múltiples lectores. Estas semánticas son más fuertes que la semántica segura pero más débiles que la semántica atómica : garantizan que existe un orden total para las operaciones de escritura consistente con el tiempo real y que las operaciones de lectura devuelven el valor de la última escritura completada antes de que comience la lectura, o el de una de las escrituras que son concurrentes con la lectura.
La semántica regular es más débil que la linealizabilidad . Considere el ejemplo que se muestra a continuación, donde el eje horizontal representa el tiempo y las flechas representan el intervalo durante el cual tiene lugar una operación de lectura o escritura. Según la definición de un registro regular, la primera lectura puede devolver 5 o 2, y lo mismo puede hacer la segunda lectura. La primera lectura podría devolver 2 y la segunda lectura podría devolver 5 (también conocido como una inversión nueva/vieja). Este comportamiento no satisfaría la semántica atómica . Por lo tanto, la semántica regular es una propiedad más débil que la semántica atómica. Por otro lado, Leslie Lamport demostró que un registro linealizable puede implementarse a partir de registros con semántica segura , que son más débiles que los registros regulares. [1]
Una semántica atómica de un solo escritor y lector múltiple (SWMR) es un registro regular SWMR si alguno de sus historiales de ejecución H satisface la siguiente propiedad: r1 y r2 son dos invocaciones de lectura cualesquiera: (r1 →H r2) ⇒ ¬π(r2) →H π(r1)
Antes de entrar en la demostración, primero se debe entender qué significa la inversión nueva/antigua. Como se muestra en la imagen a continuación, al observar la ejecución se puede ver que la única diferencia entre una ejecución regular y una ejecución atómica es cuando a = 0 y b = 1. En esta ejecución, al considerar las dos invocaciones de lectura R.read() → a seguidas de R.read() → b, nuestro primer valor (valor nuevo) es a = 0 mientras que el segundo valor (valor antiguo) es b = 1. Esta es en realidad la principal diferencia entre atomicidad y regularidad.
El teorema anterior establece que un registro regular de múltiples lectores y un solo escritor sin inversión nueva o antigua es un registro atómico. A partir de él, R.read() → a → H R.read() → b y R.write(1) → H R.write(0), no es posible tener π (R.read() → b) = R.write(1) y π (R.read() → a) = R.write(0) si la ejecución es atómica. Para probar el teorema anterior, primero debe probarse que el registro es seguro, regular y que no permite la inversión nueva/antigua, lo que prueba la atomicidad. Por la definición del registro atómico, un registro atómico de múltiples lectores y un solo escritor es regular y satisface la propiedad de no inversión nueva/antigua. Entonces, la única prueba requerida es mostrar que un registro regular sin inversión nueva/antigua es atómico.
Además, para dos invocaciones de lectura cualesquiera (r1 y r2) cuando el registro es regular y no hay inversión nueva/vieja (r1 →H r2) ⇒sn(π(r1)) ≤ sn(π(r2)). Para cualquier ejecución (M) hay un orden total (S) que incluye las mismas invocaciones de operación. Se puede afirmar que S se construye de la siguiente manera: comenzando desde el orden total en las operaciones de escritura y las operaciones de lectura que se insertan de la siguiente manera: primero: la operación de lectura (r) se inserta después de la operación de escritura asociada (π(r)). Segundo: si dos operaciones de lectura (r1,r2) tienen el mismo (sn(r1)=sn(r2)) entonces primero se inserta la operación que comienza primero en la ejecución. S incluye todas las invocaciones de operación de M, de lo que se deduce que S y M son equivalentes. Dado que todas las operaciones se ordenan en función de sus números de secuencia, es ligeramente un orden total. Además, este orden total es una ejecución de M solo agrega un orden en las operaciones que se superponen en M. Si no hay superposición entre una operación de lectura y una de escritura, no hay diferencia entre la regularidad y la atomicidad. Finalmente, se puede afirmar que S es legal ya que cada operación de lectura obtiene el último valor escrito que viene antes de ella en el orden total. Por lo tanto, el historial correspondiente es linealizable. Dado que este razonamiento no se basa en un historial particular H, implica que el registro es atómico. Dado que la atomicidad (linealizabilidad) es una propiedad local, se puede afirmar que un conjunto de registros regulares SWMR se comportan atómicamente tan pronto como cada uno de ellos satisface la propiedad de no inversión nueva/vieja.