Notes on the problem of concurrent computing 101

The problem

In concurrent applications , one of the problems to resolve is the synchronized access of a critical section typically accessing a shared resource.

Examples of this could be:

• In memory counters.
• Files.
• Access of resources in data bases.

This problem can be reduced to the analysis in how the critical section is accessed and synchronized.

We will start with definitions.

Critical section

Critical section is any piece of code that has the possibility of being executed concurrently by more than one thread of the application and exposes any shared data or resources used by the application for access.

Parallel vs Concurrent

• A concurrent program is that which can be decomposed into constituent parts and each part can be executed out of order or in partial order without affecting the final outcome.
• A parallel application is one which necessarily has the ability to execute multiple programs at the same time.

Synchronous vs Asynchronous

• Synchronous execution refers to line-by-line execution of code. If a function is invoked, the program execution waits until the function call is completed
• Asynchronous (or async) execution refers to execution that doesn’t block when invoking subroutines. The Wikipedia definition: Asynchronous programming is a means of parallel programming in which a unit of work runs separately from the main application thread and notifies the calling thread of its completion, failure or progress. An asynchronous program doesn’t wait for a task to complete and can move on to the next task.

Problems when designing concurrent programs.

From educative.io Java Multithreading for Senior Engineering Interviews

1. Usually very hard to find/debug bugs, for example https://github.blog/2021-03-18-how-we-found-and-fixed-a-rare-race-condition-in-our-session-handling/ , this of course causes Higher cost of code maintenance since the code inherently becomes harder to reason about
2. Increased utilization of system resources. Creation of each thread consumes additional memory, CPU cycles for book-keeping and waste of time in context switches — with current processors this could be considered neglectable.
3. Programs may experience slowdown as coordination amongst threads comes at a price. Acquiring and releasing locks adds to program execution time. Threads fighting over acquiring locks cause lock contention.

On my own ,

1. Developers tend to model programs after a sequential execution , often ignoring , the problems that concurrent programs could bring.
2. The popularity of Web Services, where resources get accessed in a multi threaded environment and most commonly a distributed computing system.

Usually very hard to find bugs? Can you spot the bug below?

Some common problems with critical sections

DeadLock . Deadlocks occur when two or more threads aren’t able to make any progress because the resource required by the first thread is held by the second and the required resources by the second thread is held by the first.

Live-Lock. A live-lock occurs when two threads continuously react in response to the actions by the other thread without making any real progress.

Liveness Is the Ability of a program or an application to execute in a timely manner is called liveness. If a program experiences a deadlock then it’s not exhibiting liveness.

What approaches do we have to resolve the problems of concurrent access to a critical section?

Mutual exclusion ! First resolved by Edsger W. Dijkstra

What are the basic data structures to handle mutual exclusion?

• Mutex as the name hints implies mutual exclusion. A mutex is used to guard shared data such as a linked-list, an array or any primitive type. A mutex allows only a single thread to access a resource or critical section.
• Semaphore, on the other hand, is used for limiting access to a collection of resources. Semaphores can also be used for signaling among threads. This is an important distinction as it allows threads to cooperatively work towards completing a task. A mutex, on the other hand, is strictly limited to serializing access to shared state among competing threads. A semaphore can potentially act as a mutex if the permits it can give out is set to 1. However, the most important difference between the two is that in case of a mutex the same thread must call acquire and subsequent release on the mutex whereas in case of a binary semaphore, different threads can call acquire and release on the semaphore. The pthreads library documentation states this in the pthread_mutex_unlock() method’s description.
• Monitor, a monitor is made up of a mutex and one or more condition variables. A single monitor can have multiple condition variables but not vice versa. Theoretically, another way to think about a monitor is to consider it as an entity having two queues or sets where threads can be placed. One is the entry set and the other is the wait set. Practically, in Java each object is a monitor and implicitly has a lock and is a condition variable too. You can think of a monitor as a mutex with a wait set. Monitors allow threads to exercise mutual exclusion as well as cooperation by allowing them to wait and signal on conditions.

In summary ,

• Mutex is owned by a thread, whereas a semaphore has no concept of ownership.
• A monitor and a semaphore are interchangeable and theoretically, one can be constructed out of the other or one can be reduced to the other. However, monitors take care of atomically acquiring the necessary locks whereas, with semaphores, the onus of appropriately acquiring and releasing locks is on the developer, which can be error-prone.

Java concurrency control mechanisms

Java’s util.concurrent package provides several classes and language constructs that can be used for solving everyday concurrency problems and should always be preferred than reinventing the wheel.

• Synchronization using synchronized
• Synchronization using Synchronizers classes
• volatile variables . The volatile concept is specific to Java. Its easier to understand volatile, if you understand the problem it solves. If you have a variable say a counter that is being worked on by a thread, it is possible the thread keeps a copy of the counter variable in the CPU cache and manipulates it rather than writing to the main memory.. The JVM will decide when to update the main memory with the value of the counter, even though other threads may read the value of the counter from the main memory and may end up reading a stale value.
• Guarded blocks with wait and notify .
• High Level Concurrency Objects - Locks, some specialized examples (apart from java.util.concurrent.locks.Lock):

1. ReentrantLock — . Allowing a thread to acquire the same lock more than once enables reentrant synchronization. This describes a situation where synchronized code, directly or indirectly, invokes a method that also contains synchronized code, and both sets of code use the same lock. Without reentrant synchronization, synchronized code would have to take many additional precautions to avoid having a thread cause itself to block.
2. Fairness locks . When locks get acquired by threads, there’s no guarantee of the order in which threads are granted access to a lock. A thread requesting lock access more frequently may be able to acquire the lock unfairly greater number of times than other locks. Java locks can be turned into fair locks by passing in the fair constructor parameter. However, fair locks exhibit lower throughput and are slower compared to their unfair counterparts.

• High Level Concurrency Objects — Executors define a high-level API for launching and managing threads

Other useful Java objects when working with concurrent applications.

• Immutable objects
• Concurrent Collections
• Atomic variables.

Java No No’s

• Do not start threads in Object constructors , see https://stackoverflow.com/questions/5623285/why-not-to-start-a-thread-in-the-constructor-how-to-terminate
• When constructing an object that will be shared between threads, be very careful that a reference to the object does not “leak” prematurely, from https://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html

Other related concepts.

• Amdahl’s Law. The law specifies the cap on the maximum speedup that can be achieved when parallelizing the execution of a program. SeeValidity of the single processor approach to achieving large scale computing capabilities , https://inst.eecs.berkeley.edu//~cs252/sp17/papers/amdahl-singleprocessor.pdf

References

1. What is concurrent programming? https://www.cs.rice.edu/~cork/book/node96.html
2. Mutual exclusion problem reference. Dijkstra, E.W. Solution of a problem in concurrent programming control. Comm. ACM 8, 9 (Sept.1965), 569
3. educative.io Java Multithreading for Senior Engineering Interviews
4. Good article — http://www.goldsborough.me/go/2020/12/06/12-24-24-non-blocking_parallelism_for_services_in_go/
5. Guarded blocks https://docs.oracle.com/javase/tutorial/essential/concurrency/guardmeth.html