Separating mechanism from policy: lock-free locks

Sometimes your program can have its cake and eat it too

Concurrent data structures are useful but hard. Are there general approaches that make them easier? Should we spend more time on those than on specific structures?

In the latest Fastcode Seminar, Guy Blelloch presented “Two general techniques for simple and efficient concurrent data structures,” which answered yes to the questions above. It was a great talk, and I was especially fascinated to learn about lock-free locks. (The other general technique that Guy presented was big atomics, FYI.)

Lock-free locks

The idea of lock-free locks is thirty years old, but it was long considered impractical —until now. With “Lock-Free Locks Revisited,” Guy and his co-authors showed the idea could be implemented simply and efficiently.

I am new to lock-free locks, and I’m still absorbing the thirty-year-old idea. “Lock-free” and “lock-based” may sound mutually exclusive, but they come from two different flavors of definition:

• Lock-based means using the mechanism of locks to ensure that only one process is in each critical section.

• Lock-free means the whole system conforms to a policy of “processes may not block each other’’ (e.g., with locks) thereby establishing a guarantee of progress.

Each term has its benefits, and that sets up the premise of “Lock-Free Locks Revisited”:

Can we get the ease of use of locks AND also ensure lock-freedom at the same time? Yes — and efficiently, too!

Guy Blelloch showed how “lock-based” and “lock-free” intersect with this picture.

In his talk, Guy explained how these two flavors of definition intersect in the realm of lock-free locks. The key challenge to having both “lock-based” and “lock-free” is preserving safety, and Guy explained how to do that by ensuring process idempotence. To learn more, check out the recording of Guy’s talk.

Separating mechanism from policy

Now that I’ve heard Guy’s talk, I’m eager to hear Mike Spear, the next Fastcode Seminar speaker. On June 16, Mike will present “A renewed focus on the structure of concurrent data structures.” You can register for the virtual talk here.

In his talk, Mike will discuss new performance-engineering benefits based on the the traditional systems concept of “separation of policy and mechanism.” Below is how he puts it in the abstract of “Separating policy from mechanism in STM”:

When designing concurrent data structures (CDSs), it can feel like programmers must choose between performance and convenience. On one hand, Software Transactional Memory (STM) is easy, because it allows programmers to simply mark regions of sequential code as requiring atomicity, and then the compiler ensures that no races manifest. However, this can easily lead to false conflicts that hinder scalability. On the other hand, programmers can craft custom lock-based or non-blocking protocols for operating on the CDS. This approach increases scalability, but is hard to get right.

For lock-based optimistic data structures, we identify a compelling design point that effectively unifies the two approaches. The key idea is to employ the systems concept of “separation of policy and mechanism”. This allows different operations to use the same transactional synchronization mechanism in different ways, on the same data structure, at the same time. That is, some operations can access the CDS via STM, while others use custom synchronization.

To learn more, you can listen to Mike’s virtual talk on June 16. (Register here.)