For the past two years, I have been focused on Distributed Computing, and I feel pretty comfortable explaining ideas on this topic (at least, I think). So I start with a simple problem for complete strangers to the topic.
For years, Intel, AMD, Apple and … market their products with the number of CPU cores. But the question is, do multiple processes have more computational power than a single processor? If we run a sequential algorithm in a multi-core CPU, then what’s the difference? Processes need to talk to each other somehow to solve a problem faster. And for processes to talk, we need to share data structures between them. Let’s start with the simplest one, Registers. A Register stores some value and supports two operations, Read and Write(v). Read returns the value of the register and Write(v) assigns v to the register. Current CPUs give us Multi Reader Multi Writer registers, which means multiple processes can read and write on the register simultaneously.
Let’s see if we can build a naive object from MRMW registers. An Increment object stores an integer and supports Read and Increment operations. Read returns the value stored in the object, and Increment increments the object’s value by 1. Can we implement an increment object from an MRMW register to share between some processes? Note that we cannot make any assumption on the order of the steps done by the processes, as they are done with different speeds on different processors.
Let’s construct an increment object like this:
shared Register R
Read():
v= R.Read()
return v
Increment():
v= R.Read()
R.write(v+1)
It’s not hard to see when only one process is doing Reads and Increments; the created object works fine. But what if there were two processors invoking Increment at the same time? The following execution is an example where P2 does its steps after P1 finishes its steps.
I is initaly 0.- P1: 0= R.read.
- P1: R.write(1)
- P2: 1= R.read
- P2: R.write(2)
I becomes 2
Now consider an execution where P1 and P2 have interleaving steps.
I is initaly 0.- P1: 0= R.read.
- P2: 0= R.read
- P1: R.write(1)
- P2: R.write(1)
I becomes 1
After P1 and P2 finished their increments, the value stored is 1, which was supposed be 2; as there were two Increments invoked. So this implementation did not work, but is there an implementation of an increment object that can be shared between 2 processes properly? I will answer this question in this chain of posts next. The short answer is NO, here is the link if you want to know the answer before the next post is published.