7 ms·
Look ma, no locks
- gok 8y agoSounds like libdispatch
- thealistra 8y agoYep, working in iOS/OS X for 9 years now. The primitives are queues not mutexes.
- tyingq 8y agoInteresting that a 101 style explanation wouldn't tell you that mutex is derived from "mutually exclusive". Otherwise, a pretty nice overview. The bar charts are helpful.
- ludston 8y agoLikely because the target audience is programmers whom use mutexes rather than programmers whom do not write threaded code.
- swift532 8y agoPlease don't be mad as I'm not trying to provoke, but I believe 'who' goes here, not 'whom', as from what I understand, whom is used when something is being done/given to something. Perhaps I'm simplifying, but it's just like nouns etc. in the accusative case work in languages which have grammatical cases.
- insomniac_chan 8y agogood bot
- usefulcat 8y agoTL;DR: 'whom' is to 'him' as 'who' is to 'he'. For whom does the bell toll? It tolls for him (not 'he'). Who is there? He (not 'him') is there.
- rlucas 8y agoOoh, now do the predicate nominative!
- Noumenon72 8y agoI'm expecting someone to come denigrate your approach in the comments, but the fact you made this readable and kept me with you to the end is a real feat of communication. Thanks for putting in all the effort to re-explain, color-code, and consider objections.
- cyphar 8y agoI'm not entirely sure that I agree with the section comparing mutexes and task dispatch. It appears that the comparison is actually between a spinlock and task dispatch -- most other kinds of mutexes put a process into an interruptible state that allow the scheduler to run a different process. So I would contend that they act in a very similar fashion in practice. At least, that's how locking works within the Linux kernel (and I think pthreads locks work the same way on Linux). However, I do quite like this way of thinking about synchronisation. I wonder how many other kinds of synchronisation primitives (I'm thinking about RCU and seqlocks) can be re-thought using this method.
- barbegal 8y agoThis is a confusing article. The main content is a description of how to implement a simple operating system scheduler which effectively is implementing locks using instruction level primitives. The author has completely neglected the most common cases where either "tasks" require multiple resources (e.g. when copying between two files) or where the ordering of tasks is important. It is these two conditions that lead to deadlocks and livelocks.
- sterlind 8y agoMost (though not all, see Midori) OSes use preemptive multitasking and threads. These tasks are cooperating coroutines - a different beast. Of course you can use tasks to implement a thread scheduler, but this machinery would probably live in a user-mode runtime. As for the neglected cases, you can build those out of these primitives: canonical ordering of tasks for multiple resource acquisition; work stealing and/or a DAG executor where ordering is important. My only criticism is that it's a little redundant to implement both mutexes and semaphores - a mutex is just a semaphore of 1. But the rest is wonderful.
- plasticchris 8y agoMutex is for resource locking, semaphore is for signaling. This means they have some differences in implementation extending beyond simply limiting semaphore to get a mutex.
- jamescostian 8y agoAFAIK, the only difference between "semaphore of 1" and "mutex" is that a semaphore is definitely able to be signaled by someone who isn't holding a lock, whereas a mutex is sometimes only able to be signaled/unlocked by whoever acquired the lock. As long as you trust the code running on your machine (if you don't, you have bigger issues to worry about), you'll be fine - nobody signals a semaphore before waiting on it if they're hoping to achieve mutual exclusion
- SlowRobotAhead 8y ago
- djcapelis 8y agoThis is kinda the type of model I use my little lock-free SPSC workqueues for: https://github.com/djcapelis/atomic-ring https://github.com/djcapelis/atomic-ring You just have things do stuff and then toss pointers to threads on the other side of the workqueue. Most things I do this with I basically keep each thread in a different part of the pipeline and they pass the task to the next one. Sometimes this means each thread has a warm cache for the part of the task it's working on, assuming the majority of the working set of each task is more correlated with the stage of the pipeline than the specific data moving through it.
- Gupie 8y agoWhat does he mean by "static world", "static task"?
- lucozade 8y agoThey mean that, if you know upfront how long every task takes and the order they need to run in, it's straightforward to lay out a schedule that has no resource contention. I'm not sure that that's true in general but it's true that it's easier than when you don't know those things.
- Annatar 8y agoEnqueuing tasks per resource is a very old concept in computer science; this is nothing new and anyone with a computer science degree should have come out of the university with having written such a task scheduler under their belt.
- antoinevg 8y agoYet, most people with a computer science degree have not come out of the university with having written such a task scheduler under their belt.
- yellowapple 8y agoAlso, not all of us have computer science degrees.
- Annatar 8y agoThen it's high time to get one, otherwise those people have no business being in the IT industry.
- yellowapple 8y agoCool, so I guess my career is meaningless, then. :) Getting a degree is something I very much want to do, but it's something I haven't been able to do (due to the time and money required to do it). I ended up jumping straight into the workforce in the hopes that at some point I'll have saved up enough to actually enroll (since my high school grades left much to be desired; it's a miracle I even got my HS diploma). Really, though, 99.995% of IT (in my experience at least) doesn't actually require a degree (obviously, since I'm doing it right this very moment without a degree and have been doing so for more than half a decade). It does require a lot of background knowledge that, sure, might've come to me faster had I received a formal education in IT, but I've been able to acquire it just fine through real-world work experience (and have been paid for it, to boot). My interest in getting a degree has more to do with my interest in a lot of the more theoretical concepts. I'm able to stumble through a lot of things via self teaching, but I do feel like I'm missing various critical pieces, so I'd like to fix that. None of those pieces are getting in the way of me doing my current job, but I do feel like my career is prone to stagnation if I don't have those pieces.
- ericnyamu 8y agoWhy do you use faint font like that.the article is unreadable.what did black font ever do to you ?
- kettlecorn 8y agoI believe a number of video game engines use this approach. There’s a talk about this approach in the game Destiny: https://www.gdcvault.com/play/1022164/Multithreading-the-Entire-Destiny https://www.gdcvault.com/play/1022164/Multithreading-the-Ent... And also in the Uncharted engine: http://twvideo01.ubm-us.net/o1/vault/gdc2015/presentations/Gyrling_Christian_Parallelizing_The_Naughty.pdf http://twvideo01.ubm-us.net/o1/vault/gdc2015/presentations/G... They go a step further by allowing threads to pause and resume their state by changing the stack pointer. These sort of systems are useful in games where you basically want to be using all of the cpu all of the time and there’s no reason to ever give control back to the operating system’s scheduler (with mutexes).
- tirumaraiselvan 8y agoI would like to compare this with Haskell's STM.
- throwaway487550 8y agoLook ma, communicating sequence processes
- gpderetta 8y agoNice article. A few high performance C++ systems use variants of the dispatcher approach. For example ScyllaDB and I know of a few HFT systems like that. Boost.asio is similar (the serializer is, or used to be, called strand) and so is the dispatcher proposal in C++. A few systems I have seen strictly map each dispatcher to a thread (which is in turn exclusively pinned to an hardware core), so the serialization is implicit. "Active" objects expose their home dispatcher and to interact with the object one would post a lambda to that object dispatcher. In practice this is a form of async message passing. To get the answer back either a response callback is posted to the original thread or some future/promise abstraction is used.
- proneb1rd 8y agoI think the author eventually came up with what libdispatch already does using queues.
- al2o3cr 8y agoThe skeleton of the approach suggested reminds me of how the BEAM runs processes: one OS thread per CPU, scheduling many lightweight tasks listening to message queues.
- contravariant 8y agoLooks like a reinvention of async/await.
- kahlonel 8y ago> Here, instead of blocking on the second thread when executing the blue task, the scheduler picks up a yellow task; This only works if the second thread's yellow task is independent of its blue task's results. Which is, unfortunately, only 1% of the cases.
- joantune 8y agoThis sounds a lot like going from the Lock/Mutexes/Semaphores paradigm into an Actor system. OP - i.e. @ingve - it might be interesting to take a look into some strategies - like the pull one - on Actor systems like AKKA
- bullen 8y agoIf you want to see a practical working implementation of what this article describes: https://github.com/tinspin/rupy https://github.com/tinspin/rupy (Java HTTP Server)