由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - Full story of GO's three level scheduler
相关主题
写backend的朋友还是可以关注一下golanggolang的问题是channel, goroutine里面magic太多,
wdong你可以把event和thread拆开来感觉并发模型上go可以秒vertx
coroutine or thread从coffee,scala等到golang效率下降了好几倍
why do we need to map user threads to kernel threads?August 2015 go 1.5 跳票了
有没有人玩 go lang啊?go channel和clojure core.async哪个好
我来说说go的目标对手吧yield和goroutine啥区别?
上scala有一个直接的好处好了,现在可以发布我的发明之一了,物联网App Engine
Scala和Go都没啥戏。Go的并发和channel看上去非常厉害啊
相关话题的讨论汇总
话题: gs话题: go话题: scheduler话题: ms话题: run
进入Programming版参与讨论
1 (共1页)
c*******v
发帖数: 2599
1
From hacker news. 2016.
https://news.ycombinator.com/item?id=12459841
The author's signature: I wrote and maintain the Go arm64, sparc64, and
Solaris ports.
Yes, the kernel scheduler works with threads. But the purpose of a scheduler
(both the kernel's and Go's) is to be invisible to the user. Since Go
programs are user-level programs, the kernel scheduler is invisible to Go,
and this is a very good thing.
The kernel provides an abstraction, independently-executed threads of
execution. These threads are managed by the kernel scheduler to implement
parallelism, guarantee fairness, and do many other things, but all this is
not relevant to Go. What matters is that these threads are concurrent,
independent, and carry their own state.
The Go runtime also provides the user with independently-executed threads of
execution. For various reasons I won't get into it does all this in
userspace rather than transparently using kernel threads (note that gccgo on
some platforms just uses kernel threads). So how does it do it?
Well, for once, forget about Ps. They are an optimization. Let's think how
you can do this without Ps; we'll add them later. And forget about
parallelism too. We're making a toy, strictly GOMAXPROCS=1 implementation
for now.
The runtime has to account for all the goroutines the user has to run. These
exist in the runtime as Gs. There are as many Gs as there are goroutines,
but more than the number the user asked for, since the runtime creates its
own.
Like all programs, Go programs start their life as single-threaded programs.
So we have an arbitrary number of Gs that somehow have to all run on this
single thread. This implementation of Go is cooperativelly-scheduled. That
means that the Go code is never preempted, but code must yield.
But where does it yield? The programmer surely doesn't call runtime.Gosched(
), and yet goroutuines seem to yield somehow. Well the compiler inserts call
into the runtime in various places, e.g. channel send and channel receive
will call into the runtime. In fact they will end up in the scheduler. which
looks at the list of runnable Gs, and if there are any, saves the current
context and it reschedules another on top of the running thread.
How does it reschedule? It changes the execution context, which for Go code
means setting a program counter, a stack pointer, a g in the TLS slot (more
on this later), and some other miscellaneous things.
So this works, but there are some problems. The program eventually ends up
doing system calls like read and write, and these system calls can block for
an unbounded period of time. The programs has many runnable Gs. It would be
good if somehow we could run all this code while some other part of the
program is waiting for the kernel.
So we introduce threads now. We're still at GOMAXPROCS=1 level, but we start
using kernel threads.
In this variant of the implementation, the runtime will check the list of
runnable Gs before issuing a system call. If there are Gs to run, it will
start a new thread. The current thread will do the system calls, as before,
but there will be a new thread that will run the scheduler code (because
this is how we set it up when we started it) that will pick a runnable G,
and execute it.
In the original thread, we block in the system call. Once that completes, we
save the result somewhere, the we exit, and the thread disappears.
This works but it's really wastful. All that thread creation and destruction
. It would be better if we reused threads, and only create new ones if
needed. So to do that, we need to do some accouting, and we need to manage
these threads in some data structure. So we introduce Ms. M stands for
machine -- a machine that will execute Go code. We now have both a list of
Gs, and a list of Ms. Now when we need a thread we first search the Ms, we
might have one available already. Only if we don't we will create another M.
When a system calls resumes, the thread will park itself (parked means it's
not runnable, and the kernel will not schedule it) and insert itself in the
list of available Ms.
The relation between all Gs and Ms is n:m, but we only have one runnable G,
many Gs blocked in system calls, and some Ms that do nothing. We can do
better. We want to run multiple Gs in parallel.
For that, we need to introduce a scheduler lock. Multiple Gs will now enter
the scheduler at the same time, so we need a lock.
It works pretty much the same as before, just concurrent. And this
concurrency will enable parallelism if the hardware has multiple core or
CPUs. Now the relation between Gs and Ms trully is m:n.
But there is a problem now. If we set GOMAXPROCS too high, performance is
bad. We don't get the speed-up we expect. The problem is that many
goroutines now compete for the same scheduler lock. Lock contention is bad
and prevents scalability.
So we introduce Ps, and split up the G:M relation into G:P:M. P stands for
processor.
There is a n:1 relation between Gs and Ps. When a Go program starts, it
creates exactly GOMAXPROCS Ps.
When Go code wants to run, it first has to acquire a P. You can think of
this as "G needs to acquire processor time". When a new goroutine is created
, it's placed in a per-P run queue.
Most of the scheduling is done through per-P run queues. There is still a
global run queue, but the idea is that is seldom used, in general, the per-P
run queue is prefered, and this allows to use a per-P lock instead of a
global lock.
Ms uses these Ps to get their workload. All Ms that run user code have a P,
and use its runqueue and locks to schedule the work. There are more Ms,
however. Ms that don't execute user code, for example when doing a system
call (then you are stuck in the kernel, so you don't run user code) hand off
their P before issuing the system call. Since this P is now free, another M
can grab it and schedule Gs from its run queue.
Now we finally discovered the real Go implementation used today. This design
allows both simple accouting of resources, and it is scalable and
performant.
Hope this clear it up.
Oh, yes, and the g in the TLS slot? The current G is always stored in a
register or a TLS slot. In the function preamble, this G is inspected.
Originally it was done to check for stack overflow, but now it has a dual
purpose. Some other concurrent part of the scheduler measures time spent by
running Gs, and if they run too long, it will set some state in the
corresponding G, so that the next time that G will do a function call, the
function call prolog will detect this and will jump into the scheduler,
descheduling the current goroutine and allowing others to run.
h*i
发帖数: 3446
2
Sounds like to me it is implementing JVM?
LOL, it's all reinventing the wheel over and over again.

scheduler

【在 c*******v 的大作中提到】
: From hacker news. 2016.
: https://news.ycombinator.com/item?id=12459841
: The author's signature: I wrote and maintain the Go arm64, sparc64, and
: Solaris ports.
: Yes, the kernel scheduler works with threads. But the purpose of a scheduler
: (both the kernel's and Go's) is to be invisible to the user. Since Go
: programs are user-level programs, the kernel scheduler is invisible to Go,
: and this is a very good thing.
: The kernel provides an abstraction, independently-executed threads of
: execution. These threads are managed by the kernel scheduler to implement

l******n
发帖数: 62
3
This is just like thread pools.

scheduler

【在 c*******v 的大作中提到】
: From hacker news. 2016.
: https://news.ycombinator.com/item?id=12459841
: The author's signature: I wrote and maintain the Go arm64, sparc64, and
: Solaris ports.
: Yes, the kernel scheduler works with threads. But the purpose of a scheduler
: (both the kernel's and Go's) is to be invisible to the user. Since Go
: programs are user-level programs, the kernel scheduler is invisible to Go,
: and this is a very good thing.
: The kernel provides an abstraction, independently-executed threads of
: execution. These threads are managed by the kernel scheduler to implement

1 (共1页)
进入Programming版参与讨论
相关主题
[bssd] Go 的大并发处理网络碰到两个个问题有没有人玩 go lang啊?
go里面channel和wait group用法比较我来说说go的目标对手吧
golang為什麼語法和關鍵詞這麼冷門?上scala有一个直接的好处
thread, semaphore, 问题。Scala和Go都没啥戏。
写backend的朋友还是可以关注一下golanggolang的问题是channel, goroutine里面magic太多,
wdong你可以把event和thread拆开来感觉并发模型上go可以秒vertx
coroutine or thread从coffee,scala等到golang效率下降了好几倍
why do we need to map user threads to kernel threads?August 2015 go 1.5 跳票了
相关话题的讨论汇总
话题: gs话题: go话题: scheduler话题: ms话题: run