Good day!
Recently, I peeped into courses an interesting version of working with lists in a multi-threaded environment, called this model there “fine synchronization”. The bottom line is that during the work with the list, access to the current and previous elements of the list is blocked for any operations like delete / insert, and at the same time there are no conflicts. Has anyone used this method of synchronization on real tasks?
Here is an example of adding an element to a linked list in pseudocode in courses:

Node prev = head; prev.lock(); Node curr = prev.next; curr.lock(); try{ while(curr.key < key){ prev.unlock(); prev = curr; curr = curr.next; curr.lock(); } if(key == curr.key) return false; else{ node = new Node(key,item); node.next = curr; pred.next = node; return true; } } finally{curr.unlock();pred.unlock();}

If we shift this example to C, then I have to create a list, the elements of which are instances of a certain structure containing a mutex. This is where I have the question of how to implement at least the first line of a given code without risking to catch a segfault when:

  1. the first thread received a pointer to the head element of the list,
  2. control got the second thread, and deleted the head element of the list,
  3. control returned to the first thread, it tries to capture the mutex of the head element of the list, which is no longer alive ...
    ?
  • Yeah, right noticed. I also hung on the first line, missing the question. - mega
  • @margosh, and nowhere does it say that this code should work when deleting elements. Probably for the implementation of the removal you need a couple more of your loved ones (by the way, how are they) pthread_rwlock_wrlock / pthread_rwlock_rdlock. The insertion thread (the one we are currently viewing) should do pthread_rwlock_rdlock before the first prev.lock (); - The real question here is different. All such locks are expensive operations and IMHO will simply eat them all the time. Faster will be consistent. - avp
  • Surely the authors used the idea. I would just wrap up all operations with this list in a critical section and not collect on sour cream - renegator
  • one
    @VladD, IMHO about the handling of an element is not discussed here at all. Speech about changing the container. And your comment is, apparently, about the conduct of the specified test? The point there is a detour (visit), not a change. I wanted to suggest just an easy-to-implement test, and it is possible to check on the same lists (if not laziness) that the single-threaded algorithm will be an order of magnitude faster. - avp
  • one
    @avp: I meant an algorithm that considers that while the data is locked, it has the right to read and write it. In this case, if someone wants to delete an item, he must make sure that no one has a lock to read the data — that is, to actually take the lock itself. --- Although it may be necessary here rwlock :-) r = data access (read or write), w = structure modification. - VladD

1 answer 1

As far as I understand, this code is based on the fact that the head of the list is fictitious and unchanged. This is a frequently used technique, allowing not to select a special case of an empty list.

Under such assumptions, the code seems to be correct.

The invariant of the algorithm is as follows: to work with an element, it is necessary to block both the Node itself and its predecessor. If you have a lock on a Node or on its predecessor, your Node is guaranteed to be alive.

I, however, would not use exception handling to analyze reaching the end of the list (especially since head.next not checked in this code), and left exceptions for exceptions.

  • those. head - "border" element, in other words. - mega
  • The second line is fine: as long as we have a lock on the head, the element head.next is guaranteed to be alive. - VladD
  • @mega: why? prev is simply a pointer to the previous element. - VladD
  • > as long as we have a lock on the head, the element head.next is guaranteed to be alive. Most likely, it is guaranteed not to change, and not alive :) Apparently, it is assumed that the list is non-empty. - mega
  • one
    @margosh: There are guarantees. Take a closer look at the invariant. In order for an element to die, another thread needs to lock the lock on this and the previous element. And at that moment, when we received a pointer to the current element, the previous element was blocked by us. - VladD