Am I supposed to lock this module before accessing it or is it safe without being locked? This is a question that probably all software developers have asked themselves during their careers within the context of concurrent applications.
This article addresses concurrency and its challenges using various locking strategies and explains an alternative using software transactional memory (STM) that can serve to enhance security in various applications when handling shared state. The Clojure programming language, which supports the STM functionality, was mainly designed to cope with the challenges posed by concurrent applications. From the many frameworks that support software transactional memory, Clojure is the only language with first-class STM support that offers a user-friendly interface. Therefore, this article focuses on Clojure and does not cover other frameworks that support STM.
What are the challenges posed by concurrent applications?
The challenge posed by concurrency is interleaved execution on a mutable object using threads; the same challenge is even posed by single CPUs. This issue is even greater when creating a network of mutable objects. It can be hard to understand a program containing several threads that access mutable objects and a hassle to reliably test it.
In order to coordinate the manipulation of mutable objects, synchronisation mechanisms need to be applied (e.g. mutex, semaphore, monitors). These synchronisation mechanisms make it possible to lock the mutable object so that only one thread accesses it at a time, as shown in the following image. Thread A locks the green list, whereas access from Thread B is blocked.
At first sight, locking on seems relatively easy; however, depending on the complexity of the application, software developers can encounter numerous pitfalls. Should Thread A in the above example keep the lock on the green list and require access to data from the red list, locked by Thread B, as part of its workflow, it must wait until Thread B releases the lock on the red list. Imagine if Thread B does not release the lock on the red list, but actually requires access to the green list during its execution; both threads will wait endlessly, also known as deadlock.
What locking strategies or concepts can be applied to prevent deadlocks?
The coarse-grained locking strategy locks an entire component instead of only locking the critical parts therein, changing the shared state. This strategy is simple to implement and does not entail significant lock overheads (CPU and memory resources required to handle locks). Coarse-grained locking is recommendable when the threads can quickly execute the operation on the component and immediately release it. Otherwise its use may lead to lock contention, where one process or thread attempts to acquire a lock held by another process or thread; this adversely affects performance and the responsiveness of an application.
Lock contention can be reduced by the fine-grained locking strategy; the opposite to coarse-grained locking.
The fine-grained locking strategy only locks the smallest possible critical part, where the shared state is going to be changed. This facilitates better parallel scalability and therefore leads to better performance. On the other hand, fine-grained locking can get quite complex in large concurrent applications.
Lock levelling provides a solution to enhance locking complexity management, also known as lock hierarchy or the lock-ordering concept. This concept factors all locks into numeric levels. In other words, components at a specific architectural layer in the system are only allowed to acquire locks at lower levels; otherwise, an exception is thrown. This concept helps to reduce deadlocks as it facilitates compliance with the lock order. In practice, many software systems end up with a number of locks at the same level. Whereas it is tempting to allow calls at the same level, as it is easier to handle, this directly violates the lock hierarchy, as threads could then try to take locks in the opposite order; in worst case scenario, this represents a potential deadlock risk.
What unsolved challenges remain with the above-mentioned locking strategies?
Although the lock levelling concept works for large software applications, there are still challenges it cannot cope with. For instance, the dynamic composition of software components can lead to unexpected runtime failures. This could be the case when a low-level component holds a lock and makes a call against an object that requires a higher level lock; in such an event, a lock hierarchy exception will be thrown.
Even the static composition of software components is not easy to handle. Imagine that there are two lists, as shown in the following picture, with both lists part of a component that is individually locked. Suppose new “transfer” functionality between these components must be established. The existing locks cannot be composed to fulfil the new requirement. Instead, a new lock condition must be established to increase the lock complexity.
The fact that locks are unable to compose aside, locking strategies face another challenge regarding thread priorities. Threads with a higher priority obtain more resources assigned by the scheduler. But what if a thread with a lower priority holds a common lock? The thread with the higher priority is forced to wait for a thread with lower priority, resulting in priority inversion.
Locking is quite error-prone, mainly due to the fact that software developers are fully responsible for the locking strategy and need to overcome difficult challenges.
Can the software transactional memory approach help solve the remaining challenges posed by the above-mentioned locking strategies?
Software transactional memory (STM) is based on the concept of transactions, it is a well-founded, established concept, used in database systems. The main difference: database transactions read and write database entries whereas with software transactional memory shared state is read and written.
The main advantage of using STM is that the software developer does not need to worry about a locking concept, as locking is performed implicitly by the underlying runtime environment. Instead, critical code sequences can easily be introduced in a transaction.
The basic workflow of a transaction can be seen in the following figure:
When a thread tries to manipulate a shared mutable object, a snapshot is created locally by copying the shared objects along with the current time. Afterwards, a transaction log is created containing all steps involved in the transaction. As soon as all operations as part of this transaction are completed, the thread will lock the shared memory in order to atomically transfer all changes. Prior to this transaction, the changes are rechecked against the variables on the shared memory. If there are any conflicts, the transaction is aborted and the read and write operations will be discarded and refreshed, with the transaction restarting as indicated for Thread C. This transaction workflow is known as optimistic concurrency control strategy which is also used with relational database management systems.
Summarised STM offers the following main advantages compared to lock-based synchronisation:
- Transactions can be dynamically and statically composed, meaning that software components can be glued together without carrying around a locking concept
- The developer is not responsible for the locking strategy, as explicit locking is not required - it is done implicitly
The software transactional memory system also has its limitations, especially as regards external resources (e.g. I/O operations). This is attributable to the fact that transactional operations need to be irrevocable; this is not possible with I/O operations and is therefore not possible as part of a transaction. This limitation can be overcome by creating buffers that queue up the irrevocable operations and perform them at a later time.
Another limitation comes in the form of larger transactions that represent a higher potential for conflict during commit as shorter transactions may change state in the meantime; as a result, larger transactions have to be repeated, adversely affecting performance.
The concept of software transactional memory is available as part of frameworks in libraries for many programming languages, such as Haskell, C/C++, C#, Java, Clojure; each is implemented in a unique way, with varying scales of quality and stability.
To date, Clojure is the only programming language that offers direct language support for the software transactional memory concept. Furthermore, the mature implementation of the STM algorithm in addition to the approach regarding immutable data structures create additional benefits when using STM compared to locking strategies (lock-based synchronization).
What is Clojure and how is the concurrency strategy implemented?
Clojure is a modern Lisp for functional programming, created by Rick Hickey in 2007. It is a dynamic language that compiles on-the-fly into Java code and is useful in any context in which Java is used. Clojure is hosted on the JVM, in other words, it is built on Java and therefore has access to the rich set of Java libraries. It is possible to call Java methods directly (Clojure calls are Java calls as they use the Java stack); as a result, Java can coexist within a Clojure application.
Clojure is designed for concurrent programming via STM, which was one of the main reasons behind the development of Clojure.
To understand the concurrency concept of Clojure, it is necessary to understand the notions of identity, state, reference and values.
It is typical for identity and state of an object as part of imperative programming with an object-oriented approach to be unified, implying that an object (identity) is a pointer to the memory that contains the value in its state. There is no way to obtain the state independently from the identity other than by copying it.
Clojure on the other hand separates identity and state, implying that an identity can be in different states at different times whilst the state itself does not change. In the words of Rick Hickey “If an identity appears to change, it is because it becomes associated with different state values over time”, whereas a value is an immutable piece of data that never changes. State changes are reassignments of identities to other values. The logical identity is well supported via atomic references to values, whereas changes to references are controlled or coordinated by the system.
This principle also applies to data structures with persistent data structure support. Adding a new value to a list doesn’t change the list, but instead adds the new value as an appendix to the old list; as a result, persistent data structures preserve their history and, thus, the immutability of values. One could even go further with the immutability approach of Clojure by avoiding shared mutable objects at all by for instance writing re-entrant code, which is one of the most valuable strategies to achieve thread safety and prevent race conditions.
This Clojure model simplifies multi-threaded programming as regards reading shared data structures between threads without having to synchronise them. The benefits of this can be seen in the immutability of core data structures, as described above.
The mature implementation of the software transactional memory system, visible in the four built-in concurrency primitives (ref, agent, atoms, var), represents another benefit of this model.
The following example is a basic comparison between a pure Clojure and a pure Java code snippet (no Java calls from Clojure). Let’s imagine a shared object called “officeLocation”, set to Zurich and later updated when the office moves.
However, once the “officeLocation” in Java is rewritten several times, the previous location is lost forever. Clojure Ref makes it possible to track a series of officeLocations over time. Having set a new officeLocation name in Clojure, the Ref now indicates the new location. Any thread holding on to the previous officeLocation would still retain that name until its state is updated from the Ref. This example shows just one key aspect of using references in Clojure.
The concept of software transactional memory with Clojure is an alternative to the error-prone locking strategies mentioned in this article. It provides reasonable solutions to challenges, whereas locking strategies have difficulties coping with such challenges. Clojure is responsible for consistent locking and makes it possible to compose software components headache free. The main advantage of the Clojure model with immutable data structures is that readers are no longer blocked, as they do not need to be synchronized. Applications written in Clojure are more robust, as it prevents mutable states from accidentally and unintentionally being changed. This takes a huge weight off the developer’s shoulders but comes at a price.
Not only does Clojure have a Lisp-like syntax that developers must first get used to, but they are also forced to explicitly label mutable states using one of Clojure’s concurrency primitives. Otherwise, state cannot be modified at all. Another drawback of using STM are the limitations as regards I/O operations.
Switching from familiar locking mechanisms to the software transactional memory approach in Clojure is no mean feat. It generally requires a change in mindset as regards the Clojure model, where values never change and identity is separated from state. Having adapted to this mindset, Clojure offers a good alternative to error-prone locking strategies.