Basic concurrency concepts

First of all, let's present the basic concepts of concurrency. You must understand these concepts to follow the rest of the book.

Concurrency versus parallelism

Concurrency and parallelism are very similar concepts. Different authors give different definitions for these concepts. The most accepted definition talks about concurrency as being when you have more than one task in a single processor with a single core. In this case, the operating system's task scheduler quickly switches from one task to another, so it seems that all the tasks run simultaneously. The same definition talks about parallelism as being when you have more than one task running simultaneously on different computers, processors, or cores inside a processor.

Another definition talks about concurrency being when you have more than one task (different tasks) that run simultaneously on your system. Yet another definition discusses parallelism as being when you have different instances of the same task that run simultaneously over different parts of a dataset.

The last definition talks about parallelism being when you have more than one task that runs simultaneously in your system and talks about concurrency as a way to explain the different techniques and mechanisms the programmer has to synchronize with the tasks and their access to shared resources.

As you can see, both concepts are very similar, and this similarity has increased with the development of multicore processors.

Synchronization

In concurrency, we can define synchronization as the coordination of two or more tasks to get the desired results. We have two kinds of synchronization:

• Control synchronization: When, for example, one task depends on the end of another task, the second task can't start before the first has finished
• Data access synchronization: When two or more tasks have access to a shared variable and only one of the tasks can access the variable

A concept closely related to synchronization is critical section. A critical section is a piece of code that can be only executed by one task at a time because of its access to a shared resource. Mutual exclusion is the mechanism used to guarantee this requirement and can be implemented in different ways.

Keep in mind that synchronization helps you avoid some errors you might have with concurrent tasks (they will be described later in this chapter), but it introduces some overhead to your algorithm. You have to calculate the number of tasks very carefully, which can be performed independently without intercommunication you will have in your parallel algorithm. It's the granularity of your concurrent algorithm. If you have a coarse-grained granularity (big tasks with low intercommunication), the overhead due to synchronization will be low. However, maybe you won't benefit from all the cores of your system. If you have a fine-grained granularity (small tasks with high intercommunication), the overhead due to synchronization will be high, and perhaps the throughput of your algorithm won't be good.

There are different mechanisms to get synchronization in a concurrent system. The most popular mechanisms from a theoretical point of view are:

• Semaphore: A semaphore is a mechanism that can be used to control the access to one or more units of a resource. It has a variable that stores the number of resources that can be used and two atomic operations to manage the value of the variable. A mutex (short for mutual exclusion) is a special kind of semaphore that can take only two values (resource is free and resource is busy), and only the process that sets the mutex to busy can release it. A mutex can help you to avoid race conditions by protecting a critical section.
• Monitor: A monitor is a mechanism to get mutual exclusion over a shared resource. It has a mutex, a condition variable, and two operations to wait for the condition and signal the condition. Once you signal the condition, only one of the tasks that are waiting for it continues with its execution.

The last concept related to synchronization you're going to learn in this chapter is thread safety. A piece of code (or a method or an object) is thread-safe if all the users of shared data are protected by synchronization mechanisms. A non-blocking, compare-and-swap (CAS) primitive of the data is immutable, so you can use that code in a concurrent application without any problems.

Immutable object

An immutable object is an object with a very special characteristic. You can't modify its visible state (the value of its attributes) after its initialization. If you want to modify an immutable object, you have to create a new one.

Its main advantage is that it is thread-safe. You can use it in concurrent applications without any problem.

An example of an immutable object is the String class in Java. When you assign a new value to a String object, you are creating a new one.

Atomic operations and variables

An atomic operation is a kind of operation that appears to occur instantaneously to the rest of the tasks of the program. In a concurrent application, you can implement an atomic operation with a critical section to the whole operation using a synchronization mechanism.

An atomic variable is a kind of variable that has atomic operations to set and get its value. You can implement an atomic variable using a synchronization mechanism or in a lock-free manner using CAS that doesn't need synchronization.

Shared memory versus message passing

Tasks can use two different methods to communicate with each other. The first one is shared memory and, normally, it is used when the tasks are running on the same computer. The tasks use the same memory area where they write and read values. To avoid problems, the access to this shared memory has to be in a critical section protected by a synchronization mechanism.

The other synchronization mechanism is message passing and, normally, it is used when the tasks are running on different computers. When tasks needs to communicate with another, it sends a message that follows a predefined protocol. This communication can be synchronous if the sender keeps it blocked waiting for a response or asynchronous if the sender continues with their execution after sending the message.