Introduction to Concurrency

Introduction

---

This semester, I am taking parallel, concurrent, and distributed programming in college. It is currently Week 3 of the semester, and the course has been challenging. However, I want to take the time and record what I have learned in this series of blog posts on concurrency.

Thinking about Concurrency

---

Some time ago, in my operating systems class, I was asked the question what is the difference between concurrency and parallelism. At first, I really thought hard and couldn't really come up with a good answer. But after reading the book "The Art of Multiprocessor Programming," I believe a good answer to that is that parallelism is when multiple programs are run simultaneously in a multiprocessor system, and concurrency is the art of structuring your program such that different components of the program can be executed while another component of the program is in use.

With that out of the way, I believe a good start to learning concurrency is building a theoretical model of concurrent computations. For me, I like to think of concurrent programming as when there are individual concurrent threads that share a resource or object. This is possible because the concurrent threads exist and perform computations in a shared memory.

Properties of Concurrent Programs

---

With our model of concurrent computation, I think the next important thing to discuss is what properties are necessary for a program to be considered concurrent. This is important as it can help us better understand the nature of concurrency.

When reading the Art of Multiprocessor Programming book, they mentioned two important properties: correctness and verification. Correctness, otherwise known as the safety property, is the property that the given concurrent program will never do something it is not supposed to do. For example, in a non-computer example, a traffic light will never display green in all directions. This seems like an obviously important property, but one that is difficult to prove for concurrent programs since there are a vast number of permutations in which the concurrent threads may execute an operation on the shared object. In simpler terms, our concurrent threads can interleave.

The property of verification, also known as the liveness property, is concerned about ensuring that an objective of the concurrent program is eventually achieved. Notice that the word "eventually" is used here, which is meant to convey that while a concurrent program may have not achieved its desired objective now, it will some time in the future. A non-computer example for this might be that a traffic light will eventually turn green. This might seem obvious, but under the hood, it is actually somewhat more complicated. Consider the possibility of a traffic light that is currently red switching back and forth to orange. In other words, the traffic light, from when we last measured, is always switching between red and orange. However, since the traffic light is also green, one day in the future, even if it might not seem like it now, it will eventually turn green. In the same way, ensuring liveness in a concurrent programming is also rather complicated because of the different number of possible states our program can take.