concurrency control

It’s the ability to run multiple processes or threads at the same time. This requires careful memory management, that is, any application running on it’s own should not interfere with other applications. It’s easy when it’s all yours but it becomes a lot harder to share with others. Then you need to be able to run 2 pieces of code together and schedule these. So that they all get their fair share of time on the CPU.

There are other factors that come into play here, for example, when you receive input through something like a network device or a peripheral device like a mouse or keyboard. You have to stop what you were doing and deal with that input.

All modern operating systems allow multiple programs to run at the same time. This is called concurrency. A running program is known as a process. In fact modern operating systems even allow a single program to execute different routines at the same time or to put it another way, they allow a process to execute several threads of control at the same time.

If multiple threads are running and accessing shared state then it is possible that these threads will conflict with each other on the usage of said state and it becomes necessary to regulate each threads access to that state. This regulation is called concurrency control.

An simple example from database theory (any shared data will do, a database is not necessary) should make the above, perhaps somewhat abstract description clear. Let's assume that we have two processes using a database of information on bank accounts. The first process would like to transfer €10.-- from account A to account B. The second process would like to determine the total amount of money in accounts A and B.

Let's say the initial situation is as follows :

Balance Account A : €1000.--
Balance Account B : €500.--

Process 1 must execute a series of actions to transfer €10.-- from A to B

1. Read balance of account A from the database.
2. Subtract €10.-- from this balance and put the result in the database.
3. Read the balance of account B from the database.
3. Add €10.-- to this balance and put the result in the database.

Process 2 must also execute a series of actions to determine the total balance of accounts A and B.

1. Initialize a variable holding the total to zero.
2. Read the balance of account A from the database.
3. Add this balance to our variable.
4. Read the balance of account B from the database.
5. Add this balance to our variable.

Both process 1 and process 2 in isolation are clearly correct. However both processes are executing concurrently and we have no way of knowing precisely when which actions from which process will be executed, although we do know that the actions of each process will be executed in the order specified.

If all of the actions of process 1 are executed first and then all of the actions of process 2, we know that process 1 will leave the database in the following state.

Balance Account A : €990.--
Balance Account B : €510.--

Furthermore Process 2 will return the answer €1500.--

But it might be the case that these actions are executed as follows:

Process 1ReadBalanceA(1000)UpdateA(990)ReadBalanceB(500)UpdateB(510)Process 2Total:=0ReadBalanceA(990)Total:=Total+990(=990)ReadBalanceB(500)Total:=Total+500(=1490)$\begin{array}{}& \begin{array}{|cc|}\hline \mathbf{\text{Process 1}}& \mathbf{\text{Process 2}}\\ & \mathsf{T}\mathsf{o}\mathsf{t}\mathsf{a}\mathsf{l}\mathsf{:=}\mathsf{0}\\ \mathsf{R}\mathsf{e}\mathsf{a}\mathsf{d}\mathsf{B}\mathsf{a}\mathsf{l}\mathsf{a}\mathsf{n}\mathsf{c}\mathsf{e}\mathsf{A}\mathsf{(}\mathsf{1000}\mathsf{)}& \\ \mathsf{U}\mathsf{p}\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{e}\mathsf{A}\mathsf{(}\mathsf{990}\mathsf{)}& \\ & \mathsf{R}\mathsf{e}\mathsf{a}\mathsf{d}\mathsf{B}\mathsf{a}\mathsf{l}\mathsf{a}\mathsf{n}\mathsf{c}\mathsf{e}\mathsf{A}\mathsf{(}\mathsf{990}\mathsf{)}\\ & \mathsf{T}\mathsf{o}\mathsf{t}\mathsf{a}\mathsf{l}\mathsf{:=}\mathsf{T}\mathsf{o}\mathsf{t}\mathsf{a}\mathsf{l}\mathsf{+}\mathsf{990}\mathsf{(}\mathsf{=}\mathsf{990}\mathsf{)}\\ & \mathsf{R}\mathsf{e}\mathsf{a}\mathsf{d}\mathsf{B}\mathsf{a}\mathsf{l}\mathsf{a}\mathsf{n}\mathsf{c}\mathsf{e}\mathsf{B}\mathsf{(}\mathsf{500}\mathsf{)}\\ & \mathsf{T}\mathsf{o}\mathsf{t}\mathsf{a}\mathsf{l}\mathsf{:=}\mathsf{T}\mathsf{o}\mathsf{t}\mathsf{a}\mathsf{l}\mathsf{+}\mathsf{500}\mathsf{(}\mathsf{=}\mathsf{1490}\mathsf{)}\\ \mathsf{R}\mathsf{e}\mathsf{a}\mathsf{d}\mathsf{B}\mathsf{a}\mathsf{l}\mathsf{a}\mathsf{n}\mathsf{c}\mathsf{e}\mathsf{B}\mathsf{(}\mathsf{500}\mathsf{)}& \\ \mathsf{U}\mathsf{p}\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{e}\mathsf{B}\mathsf{(}\mathsf{510}\mathsf{)}\\ \hline\end{array}\end{array}$The end database state is correct, but the answer returned by process 2 is incorrect.

Concurrency control is all about ensuring that interleavings of actions from different processes are constrained so that executions such as the example above are avoided. Different techniques can be used to ensure this. There are however two fundamental techniques used : timestamping and locking. In the world of operating systems locking is most often used (usually in the form of a semaphore or spinlock). In the above example process 1 will lock account A while it is running, so that process 2 cannot read it and will have to wait until process 1 is finished, thereby ensuring that it does not see the value of 990 for account A until process 1 has also updated account B to 510.

I hope that this admittedly simple example clarifies the need for concurrency control.