FlexiGran: Flexible Granularity Locking in Hierarchies

Locking continues to be a primary technique used to achieve thread synchronization. Especially in the case of rooted hierarchies, semantic locking can be achieved with physical locks at various granularity levels. Such a multi-granularity locking (MGL) provides interesting trade-off between the locking cost and the size of the locked sub-hierarchy. At one extreme, fine-grained locking precisely locks the nodes of interest, but incurs a high locking cost. In contrast, a coarse-grained lock may lock the root of the hierarchy minimizing the locking cost, but locking many more nodes than required. Existing approaches to MGL (i) do not work well with non-tree hierarchies such as DAGs, (ii) disallow structural updates to the hierarchy, (iii) do not support the co-existence of fine-grained and coarse-grained locks, or (iv) are rigid towards their underlying memory usage. In this work, we propose a versatile technique named FlexiGran, which does not have any of these issues. It allows co-existence of hierarchical and fine-grained locks in an arbitrarily shaped hierarchy which can undergo structural alterations at run time, while allowing a user to control its memory usage by adding optional approximations. We illustrate the effectiveness of FlexiGran using STMBench7, and compare it empirically with two recent locking techniques, DomLock and HiFi. On a static hierarchy with more than 1 million nodes, FlexiGran shows an improvement in throughput of around 159% and 374% on an average, compared to HiFi and DomLock respectively.