[HN Gopher] Scheduling Internals
___________________________________________________________________
Scheduling Internals
Author : signa11
Score : 163 points
Date : 2024-02-28 06:19 UTC (1 days ago)
(HTM) web link (tontinton.com)
(TXT) w3m dump (tontinton.com)
| IvyMike wrote:
| > Running a thread per client is famously known as The C10K
| Problem.
|
| Gonna have to be that guy: the C10K problem was "how to serve
| 10000 clients from a single server" specifically in the 2000ish
| time-frame. The article links to the C10K problem page, which
| discusses the tradeoffs involved in at least five high-level
| strategies[1], only one of which is the strategy of running a
| thread per client [2].
|
| [1] http://kegel.com/c10k.html#strategies [2]
| http://kegel.com/c10k.html#threaded
| signa11 wrote:
| i think, it is time already to go from C10k -> C10m or
| somesuch.
| monocasa wrote:
| Yeah, there was talk of the C10M problem. Just like C10K was
| considered solved with event loops like epoll, kqueue, and
| IOCP, C10M is generally been considered solved with
| techniques that colocate your network stack and your business
| layer code.
|
| So DPDK on one side keeping everything in user space talking
| directly to the NIC, or for static resources Netflix style
| techniques of optimized pathways for KTLS+sendfile to keep
| the dataplane all in kernel space. With that you can avoid
| the copies from a buffer in a socket call to into the network
| device packet buffers.
| throwawaaarrgh wrote:
| This is a fantastic article, bravo. Required reading for all SW
| developers
| matheusmoreira wrote:
| This is great information. Especially the libuv internals.
|
| The article uses longjmp to explain coroutines. The native stack
| is doing a lot of heavy lifting there... What would the
| implementation look like if you reified the stack?
|
| This aside also left me wanting more:
|
| > Rust's async transforms a block of code into a state machine
| that is not run until you await it.
|
| Would be interesting to read about the internals of _that_!
|
| I recently asked a question related to all this on the new
| language implementation stack exchange.
|
| https://langdev.stackexchange.com/q/3547
| supriyo-biswas wrote:
| There is a 1:1 correspondence between a generator/coroutine and
| an iterator with internal state. I suggest looking at the PHP
| generator RFC[1] and Concurrency from the Ground Up[2] talk.
|
| [1] https://wiki.php.net/rfc/generators
|
| [2] https://m.youtube.com/watch?v=MCs5OvhV9S4
| kitd wrote:
| Indeed. The fundamental concept is "Algebraic Effects"
|
| https://stackoverflow.com/questions/49626714/what-does-
| algeb...
| tpoacher wrote:
| I wonder if I can use this for scheduling my inbox tasks.
|
| (probably not ... they all have the same deadline: "yesterday!")
| orangepanda wrote:
| My priorities are named: Immediate, Very immediate, Extremely
| immediate. This way clients dont know they're asking for a low
| (immediate) priority.
| samsquire wrote:
| Love these kind of animations
|
| I have my own animation here - if you scroll down. You can see
| the parsing I do for an async syntax (scroll to the hearing named
| Definition) - you can edit the syntax and it reparses and
| displays the parsed output. Sorry for the mess it's kind of a
| place I work on ideas. Further down is my graph renderer.
|
| https://processes3.replit.app/
|
| I want to auto parallelize async tasks.
|
| I am working on a multithreaded runtime in C which is incomplete
| but can communicate between threads in roughly 60 nanoseconds at
| 6 million requests per second or closer to LMAX throughout of 20
| million requests per second at a latency of 90-120 nanoseconds.
|
| In my learnings Mutexes do not scale.
|
| I am inspired by bulk synchronous parallel which means threads
| synchronize in a rhythm without Mutexes and a lock free algorithm
| to do with semaphores and observation rather than mutability.
|
| I run two io_urings in different threads - one thread does send
| and another thread does recv. One ioring is talking to an epoll
| instance for network buffer readiness with EPOLLOUT.This means
| sending and receiving is full duplex - you can send and receive
| to different clients in parallel. I call it split IO.
|
| I plan to write up all my learnings soon.
|
| My adapted HTTP server from the loti examples gets a throughout
| that scales with the number of connections I am at 7000 requests
| per second. I am not nginx.
|
| I use mailboxes and double buffering for thread safe
| communication. Each thread can communicate with another thread
| through its mailbox. This is like Erlang.
|
| I plan to add coroutines based on Marce Colls coroutines. I can
| deschedule a coroutine when there is an await.
| jvanderbot wrote:
| Nice article.
|
| Every time I said "But wait you can just ... " the author went on
| to do that thing. Much appreciated!
| usefulcat wrote:
| I like the animation at the top, except that it's meaningless
| unless you know what the different parts represent. If you scroll
| down far enough, you will eventually find this:
| Each circle is a task. The white progress circle around tasks is
| the time left to run until the task is blocked. Purple
| box - The queue holding tasks ready to run. Green box -
| The CPU. Gray box - Tasks blocked on something (e.g.
| I/O).
|
| It would be great to have that description right at the top with
| the first animation.
| deathanatos wrote:
| I think the schedulers have a few bugs. The multi-core one under:
|
| > _The simplest way to achieve multi-core scheduling, is to do
| exactly as before. Having a global queue of tasks that are ready
| to run, and run them once a core is ready:_
|
| The second core, in that example, for me, eventually stopped
| doing anything at all: https://i.imgur.com/9RtfkSG.mp4
|
| I also think the deadline scheduler has a bug, too: sometimes the
| pink blob will just skip the queue entirely; it seems like its
| deadline is "0s away" until it has moved _all_ the way to the
| queue, so if it is mid move & the CPU becomes available, it
| seems like the most runnable. (It happens with the other colors
| too, under the same conditions, but you'll see it with pink more
| often, since it spends far more time in that state -- moving from
| I/O to waiting to run --, but I did catch other colors doing it
| too.)
|
| And the one at the top would occasionally double-schedule a core.
| (Multiple dots would animate onto a single core.)
| https://i.imgur.com/bPHgPJ0.mp4
| rdtsc wrote:
| Excellent overview of scheduling with code examples and
| animations.
|
| One minor correction about Erlang is that that scheduler doesn't
| get invoked just on function calls. It will be invoked as soon as
| the lightweight process consumes a certain number of allowed
| operations. So even if you have one huge function that never
| calls others, just computes something, it will still consume
| operations and will be preempted. Some internal C utility
| functions also consume some virtual number of ops as well and may
| yield.
___________________________________________________________________
(page generated 2024-02-29 23:02 UTC)