The definition of Sequential Consistency
The precise definition of Sequential Consistency comes from Leslie Lamport (we’ll talk about him a lot later).
He originally defined the consistency model of multi-CPU parallel computing based on shared memory, but it can also be extended to distributed systems. In fact, multi-CPU parallel computing can also be considered as distributed systems.
The definition of a model is
the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program
In a distributed system, it means that no matter how the system is running, the result is as if all operations on all nodes are run in some sequential order, but operations from the same node remain in the order specified in the node.
An example of Sequential Consistency
Leslie Lamport is saying things that are difficult and consistent, but let’s look at a couple of examples. In the figure, the physical time is represented from left to right, W(a) represents the write data A, and R(a) represents the read data A.
As can be seen, neither of these two systems is perfect, but their models can be regarded as Sequential Consistency, because they can always be justified by the following transformations, that is, the Sequential order that meets the definition can be found.
Sequential Consistency and hardware
One might ask, isn’t it obvious to keep the order of operations in the same process? As a matter of fact, with the development of hardware technology, especially multi-core and multi-CPU technology, one CPU core process may not be able to observe the operation sequence of another core process.
In the paper, Leslie Lamport gives the example of a mutually exclusive algorithm that requires two processes not to execute the critical section method at the same time, and the initial values of a and B are 0. Normally, at most one process executes the critical section method.
The execution sequence of process 1 is as follows:
a = 1
if (b! = 0) {
Critical section method
}
The execution sequence of process 2 is as follows:
b = 1
if (a! = 0) {
Critical section method
}
When this program runs on a multi-core CPU machine, it is possible for two processes to enter the critical region at the same time. Why is that?
Let’s take a look at the architecture of a modern CPU
A CPU typically has multiple cores, each with its own L1 cache and L2 cache, along with the Load Buffer and Store Buffer. At write time, the processor will probably just write the data to the Store Buffer, and then write it back to the cache, or maybe write it back to memory after a while. Similarly, data read by one core may have been modified by another core, but it doesn’t know it.
Therefore, the assignment of a and B by the above process may not be perceived by the other process.
To ensure Sequential Consistency, Leslie Lamport lays out two requirements in his paper:
Each processor issues memory requests in the order specified by its program
Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.
But satisfying Sequential Consistency at the hardware layer is a huge loss of efficiency, so these tasks are typically left to the upper software developers.