The problem on my mind now is trying to find a definition similar to lock-freedom for synchronous channels. The real problem I want to describe is the concept of implementing synchronous channels with choice-composition without using a global lock.
Herlihy's definition of lock-freedom is nice, because it eliminates the capacity for blocking synchronization generally, by stating the property that you really want: at least one thread is guaranteed to finish. Unfortunately, it doesn't quite work for synchronous channels, which are inherently blocking.
There are three approaches I've considered:
1) Try to define the exact properties that global locks have. This is near impossible, and I can actually visualize Herlihy's original thinking through the papers about linearizability and lock-freedom (he was my advisor afterall). Trying to state what is forbidden is near impossible. It's better to go for what you want.
2) Try to define some sort of synchronization operation which can only synchronize two threads. I'm pretty sure this is impossible.
3) Expand lock-freedom to accomodate synchronous channel operations. This seems most promising. My thoughts are something like "assuming there is a possible solution, one thread completes in a finite amount of time".
The third will probably be the one that I end up selecting.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment