The search-insert-delete problem

I pushed back the publication of this entry because I wasn’t so happy with the implementation I had.

It’s a new chapter in the “The Little Book of Semaphores”: not so-classical problems. The first problem there is called “search-insert-delete” and it deals with linked lists.

Three kinds of threads share access to a singly-linked list: searchers, inserters and deleters. Searchers merely examine the list; hence they can execute concurrently with each other. Inserters add new items to the end of the list; insertions must be mutually ex- clusive to preclude two inserters from inserting new items at about the same time. However, one insert can proceed in parallel with any number of searches. Finally, deleters remove items from any- where in the list. At most one deleter process can access the list at a time, and deletion must also be mutually exclusive with searches and insertions.

What the problem is calling for is categorical mutexes, just like the readers-writers problem from a while ago. Back then I argued that while it’s possible to implement categorical mutexes without using the standard library’s sync.RWMutex you also have to keep in mind that just because in Go you can use other primitives to build up synchronization constructions, that doesn’t mean that you shouldn’t reach for what is the simplest solution to a problem.

In this case, the simplest solution happens to be using the built-in categorical mutexes. Instead of going for container/list, I chose to implement my own (limited) linked list in order to favor the exposition over quantity of code. We can start by looking at the List type:

type List struct {
	searchMutex sync.RWMutex
	insertMutex sync.Mutex
	root        Element
	n           int32
}

There are two sync.RWMutex fields in this struct: one protects search operations and the other protects insertions. The mutexes are acquired like this:

Why?

The goal of searchMutex is to exclude deleters when either a search or an insert operation is active. Since searchers and inserters can operate concurrently, Insert does not need to acquire a read-write mutex to exclude searchers. On the other hand, the goal of insertMutex is to prevent multiple inserters from running concurrently, since this cannot be done using the searchMutex alone.

Both inserters and deleters try to acquire insertMutex first and then they try to acquire searchMutex. In this way only one inserter or one deleter can operate on the list at a time. When a deleter acquires insertMutex it proceeds to request searchMutex. In this way it prevents any more searchers from acquiring it and starve the deleters.

func (l *List) Delete(v interface{}) bool {
	l.insertMutex.Lock()
	l.searchMutex.Lock()

	// ...

	l.searchMutex.Unlock()
	l.insertMutex.Unlock()

	// ...
}

In practical terms inserters do not need to acquire the searchMutex because by the point where they try to acquire it they have already excluded the deleters, but I think the logic in the implementation is easier to understand if they do.

func (l *List) Insert(v interface{}) {
	l.insertMutex.Lock()
	l.searchMutex.RLock()

	// ...

	l.searchMutex.RUnlock()
	l.insertMutex.Unlock()
}

The full source is here.

The next problem is another categorical exclusion problem, with a twist.