RTC Magazine

Deployment on multicore CPUs should make software faster by enabling tasks to run in parallel rather than waiting for a time slice on a single core. But in practice, parallel processing on multiple cores can introduce contention for system resources, making an application slower than when it is deployed on a single core. Achieving multicore’s hoped-for linear performance gains hinges on resolving this issue. By examining two examples of such a conflict and the proven solutions to them, we can get to the conceptual starting point for solutions to similar resource contention bottlenecks.

Database Contention

The first conflict is contention in updating a shared data store, and its solution is called multi-version concurrency control (MVCC). Until recently, nearly all database management solutions for embedded systems used a pessimistic concurrency model that locked all or portions of the database while a single task updated it, thereby blocking all other tasks from writing to the database (or portions of it) during the modification. In contrast, MVCC is an optimistic concurrency model in which no task or thread is ever blocked by another because each is given its own copy (version) of objects in the database to work with during a transaction. When a transaction is committed, its copy of the objects it has modified replaces the objects in the database. Because no explicit locks are ever required, and no task is ever blocked by another task with locks, MVCC can provide significantly faster performance in write-intensive applications where data must be changed often and where many tasks are running on multiple cores.

Under MVCC, when tasks want to update the same data at the same time, a conflict does arise and a retry will be required by one or more tasks. However, an occasional retry is far better, in performance terms, than the guaranteed blocking caused by pessimistic locking. Further, in most systems conflicts under MVCC are assumed to be infrequent because of the logically separate duties among tasks, that is, task A tends to work with a different set of data than tasks B, C and D, etc. 

Figure 1 compares MVCC to pessimistic locking, in operation. The diagram shows three tables in a database, each with five rows, and three tasks that are reading and/or modifying certain rows of certain tables. Task 1 is modifying Table 1’s row 3 (T1R3) and Table 2’s row 5 (T2R5).  Task 2 is modifying T3R1, T3R3 and T3R5. Task 3 is reading T3R3 and modifying T1R5 and T3R2. Note that there are two copies (versions) of T3R3: a copy in Task 2 and Task 3.  

For purposes of this discussion, assume that all three tasks are started as close together in time as possible, but in the order Task 1, Task 2, Task 3. With MVCC, the three tasks run in parallel. With pessimistic locking, there are three possibilities: database locking, table locking and row locking. Each will exhibit different degrees of parallelism (but all less than MVCC).

Database locking: Task 1, Task 2 and Task 3 will be serialized. In other words, Task 1 will be granted access to the database while Task 2 and Task 3 are blocked as they “wait their turn.” When Task 1 completes its transaction, Task 2 will run while Task 3 continues to wait. Finally, Task 3 will run after Task 2 completes its transaction.

Table locking: Task 1 and Task 2 will run in parallel because Task 1 acquires locks on Table 1 and Table 2, while Task 2 acquires locks only on Table 3. Task 3 will block until Task 1 and Task 2 complete because it also needs a lock on Table 1 (which is locked by Task 1) and Table 3 (which is locked by Task 2). Task 3 will be blocked for the length of time required by Task 1 or Task 2, whichever is greater.

Row locking: Again, Task 1 and Task 2 will run in parallel because they operate on different tables, (hence on different rows). Task 3 will again block because Task 2 has a write lock on T3R3, which Task 3 wants to read. 

Any serialization effectively defeats a multicore system; all but one core will be idle with respect to the utilization of the shared resource (in this instance the database). However, strategies to maximize parallelism, such as MVCC or fine-grained locking, impose their own overhead. In the case of fine-grained locking (row locking) there is lock arbitration, which can be complex. In the case of MVCC, there is version management—creating object versions, merging them and discarding them. So for MVCC to be justified, the gain in parallelism has to outweigh the additional processing overhead. To illustrate, the graphs in Figures 2, 3 and 4 show the relative performance of McObject’s eXtremeDB in-memory database system on identical multithreaded tests executed on a multicore system, using a multiple-reader, single-writer (MURSIW, or database-locking) transaction manager, and its multi-version concurrency control (MVCC) transaction manager.