Brief Announcement-From Sequential to Concurrent: Correctness and Relative Efficiency

摘要

How to turn a sequential implementation of a data structure (a hash table, a list, a tree, etc.) into a correct and, preferably, efficient concurrent one? What if we provide an environment in which a user can locally run the sequential code so that the resulting execution is globally correct. One way to do this is to use locks to make sure that critical parts of a sequential program can only be accessed in an exclusive mode. An implementation that grabs a lock on the whole data structure before executing a sequential operation imposes a serial order but ignores all the benefits provided by the multiprocessing power of modern machines. Efficient fine-grained locking requires lots of intelligence, since it must be based on good understanding of which parts of the sequential code to protect at what: time.