-
Notifications
You must be signed in to change notification settings - Fork 1.8k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Read-write Mutex #94
Comments
It is on my to-do list, but not for the short-term. It is really up for grabs. This is a great feature for someone, who wants to figure how to write low-level lock-free implementations for |
Here's a basic implementation of the 80% case for https://gist.github.com/bobvawter/4ff642d5996dfccb228425909f303306 |
The proposed implementation misses of support for "select" clause. |
Adding "select" in not a critical problem. I have a different concern here -- |
@elizarov If you agree with the general design of that ReadWriteMutex API, I can work on making the implementation more like Two questions before I start:
I can see arguments for |
@elizarov, I don't understand your statement:
How is it possible to guarantee that there will never be a write-lock and a read-lock open at the same time without locking something when we acquire a read-lock ? I am not aware of other algorithms than theses two: https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock#Implementation And neither of them alow to acquire a readlock in a lock-free manner. Here my current read-write mutex implementation: https://gist.github.com/jcornaz/e94ee6a3a139ddd33c20554b0380d30f |
After a second thought I think I now understand how it can be lock free to acquire a read-lock (if there is no write-lock open).
This implementation still suffer some problems that I'll address before creating a PR. But, could you tell me what interface you prefer? Choice 1: interface ReadWriteMutex {
val isReadLocked: Boolean
val isWriteLocked: Boolean
fun tryLockRead(): Boolean
fun tryLockWrite(): Boolean
suspend fun lockRead()
fun unlockRead()
suspend fun lockWrite()
fun unlockWrite()
} Choice 2: interface Lock {
fun unlock()
}
interface ReadWriteMutex {
val isReadLocked: Boolean
val isWriteLocked: Boolean
fun tryLockRead(): Lock?
fun tryLockWrite(): Lock?
suspend fun lockRead(): Lock
suspend fun lockWrite(): Lock
} The first interface looks more like the Note 1: I know there is no select clause yet. I will try to add them. |
Here would be my implementation using the second interface: If you agree with the concept, I'll try to implement select clauses, add comments and prepare a pull request. |
Regardless of final choice I consider better to unify interfaces. I like solution 2 but I suspect it requires some extra allocation. I suggest a "Choice 3" opposite to the first. Choice 3:
comparison:
Plus: choice 3 is compatible with regular mutex. |
Thanks @fvasco, this is a very good proposition and would be my preferred choice too. I'll try do it that way |
I like @fvasco API proposal, too. Please, send PR when you are done. As a side note, we are considering to move "stack overflow prevention" logic that is currently complicating implementation of a regular (exlusive) |
@fvasco please clarify whether you are working on it. Since this issue is still with "up for grabs" label, and it is not clear, whether it make sense to work on it. |
Hi @Dmitry-Borodin
Any news? |
Well hmm... I'd say don't wait for me. The implementation is harder than I thought. Even if I am actually still trying to do it (at least for my own practice and learning of the subject), I think it's better if you don't wait for my implementation. @Dmitry-Borodin, feel free to work on it, if you're interested. |
Thank you. |
Let me clarify for people googling up this thread. We are not focused on implementation of RW mutex right-now. We are more focused on CSP/actor-based programming paradigms. However, if there is PR with a high-quality/high-performance RW-mutex implementation, then we'll accept it into the library. |
Hi, did you mean actor programming can eliminate RW mutex? |
Actor-style programming eliminates the need for all kinds of synchronization primitives, including (but not limited to) locks and RW locks. The whole idea of actor-style programming is that mutable state is never shared, but is encapsulated into an actor. |
Could you please give me some hint how to use actor-style programming avoiding RW lock in such situation: |
Here are efficient read-write lock and semaphore implementations that I would like to contribute. I've been using them for a while without any problems but I would appreciate review for correctness. Let me know what needs to be fixed/cleaned up/tested for a successful PR. |
Hi @btwilk interface ReadWriteMutex {
val read: Mutex
val write: Mutex
} in such case the implementation can be private. |
I think tracking multiple owners is too much overhead for a low-level primitive, which is the main reason I didn't consider it. Also, the Mutex interface is pretty heavy. I haven't thought about:
I hope there is a way forward that allows for incremental progress. |
I just updated my branch with the proposed interface, except using a lighter-weight Lock interface instead of Mutex. |
Any input on the new PR for this? |
Sorry. We're currently concentrated on flows, so the mutex stuff is on a back-burner. However, we also in the process of introducing an efficient implementation of semaphore (see #1101, paper on the algorithm is to be published, too) and plan to reimplement a regular mutex on top of this efficient semaphore. The architecture of this semaphore actually scales to other synchronization primitives like R/W mutexes. |
The "up for grabs" tag was removed, but there seems to be no progress on the issue. Does someone actively work on this? |
It is not an "easy" issue that you can just go and fix, but locks are not that much useful with coroutines as with threads, so no short-terms plans to fix it. |
Do I understand correctly, that the new efficient Semaphore has already been implemented and merged? Is it all that is supposedly required for an efficient implementation of the R/W mutex or there are more infrastructural changes on the way? |
Yes. Semaphore is implemented and merged, yet R/W mutex is quote a non-trivial extension of that algorithm. |
Quoting @elizarov from over 4 years ago:
Looks like there are not a lot of folks that feel good enough to take up that learning opportunity 😅 I personally wanted to make one a few months ago as I finally had the use case, and even with all the interesting discussion here and several links, I didn't succeed nor make encouraging progress in the one day time box I set myself, so I ended up giving up and using a catch-all |
Writing your own RW-mutex or, even more, extending our Semaphore algorithm may be quite a hard task. Semaphore is quite versatile primitive and the rest of the synchronization primitives can be built on top of it.
NB: these implementations are good enough for any project-specific uses, but not for |
Without any redirections below is my full implementation of a read/write mutex based on RWMutex implementation (go lang)
|
I've been working on a semaphore-backed implementation of this, it's not super clean at the moment but I think I've got a basic iteration working over here. I'm gonna do some polishing before submitting a PR though, make sure it's working as intended. |
We still haven't decided whether we are going to provide our own RW-mutex (though we have a working prototype here: #2045), and we are not ready to accept a PR with that either. Writing your own might be a tricky task, so for your own use I suggest using a wrapper over |
It's been a few years. Any chance we can get this re-looked at? In just the past few months several people have been redirected to this Github issue, including myself.
|
task has been created in 2017, |
@kevincianfarini thanks for the comprehensive list! It indeed helps |
Is it in the roadmap?
The text was updated successfully, but these errors were encountered: