Preemptive scheduling for Go

[Dmitry Vyukov]

Hi,

This topic come up several times recently, so I want to describe my thoughts on this FTR.

Motivation
==========

Preemptive scheduling is intended to solve 3 problems:
1. Provide more habitual environment for users (they get used to preemptive threads). Support programs that require parallelism.

2. Provide better isolation/fairness for libraries/requests (consider that a single request does not give up cpu).

3. Eliminate long stop-the-world GC pauses (issues with this are periodically reported).

Implementation Plan

===================

Decision about preemption can be made by the sysmon() background thread, or by stoptheworld() routine. Each processor P already has tick field that is incremented on each scheduling event, so sysmon() just need to watch if P stuck in Prunnning state in the same tick for too long:

static void

sysmon(void)

{

...

for(;;) {

runtime·usleep(delay);

now = runtime·nanotime();

for(i = 0; i < runtime·gomaxprocs; i++) {

p = runtime·allp[i];

if(p->status != Prunning)

continue;

if(p->lasttick != p->tick) {

p->lasttick = now)

continue;

}

if(p->lasttick + quantum < now)

preempt(p);

}

}

}

stoptheworld() sets gcwaiting flag and waits for small predefined amount of time. If all P's have not stopped by that time, it issues preemption requests for remaining P's.

Preemption

==========

Some code in current runtime assumes non-preemptive execution (memory allocator, execution on g0), to protect such code we need to add 'int32 nopreemption' field to M struct. Critical sections of code will look like:

m->nopreemption++;

// critical section

m->nopreemption--;

compiler_barrier();  // critical for gccgo

if(m->nopreemption == 0 && m->preemptionrequested)

runtime·gosched();

On Unix systems preemption can be implemented by means of signals, on Windows -- Suspend/ResumeThread, Get/SetThreadContext.

preempt() routine needs to safely derive M from P (can race with releasep()), and send a signal to the thread. The signal handler is implemented along the lines of:

void

preempthandler(int signo, siginfo_t *si, ucontext_t *uc)

{

if(m->nopreemption) {

// The thread will gosched()

// when exits from the critical section.

m->preemptionrequested = 1;

return;

}

savecontext(uc);

altercontext(uc);  // sets pc to gosched()

}

The preempted goroutine needs to be put onto the tail of global run queue, otherwise it can be scheduled over and over again (if put onto the local queue) starving other goroutines on the global run queue.

There is some chance that signals can be lost on some unix systems, in such case the preemption must be retried after some period of time.

Context Restoration

===================

There are 2 ways to restore the original context (registers) of a preempted thread:

1. Save context in G struct and set a special preempted flag. If the flag is set, scheduler restores registers from G struct and GC scans the context.

2. Create fake stack frame during preemption and save the context in the stack frame. The stack frame will restore the context and return back to the preemption pc. The advantage is that this does not require modification of scheduler/GC.

Testing

=======

Besides normal testing it's possible to create special tests that:

- test GC pause in presence of "for {}" goroutines

- require parallelism to complete, e.g. pin-pong using active spinning

- expose races between preemption and voluntary switch

- expose races between preemption and syscalls

Also it may be useful to run std tests with GOGC=1 GOMAXPROCS=64, because it will force frequent GCs that will preempt goroutines at random places.

[Jan Mercl]

On Fri, Mar 29, 2013 at 3:13 PM, Dmitry Vyukov <dvy...@google.com> wrote:

I expect to be in a minority camp on this, but I don't currently
invite the idea. I have no solid/real argument against, only
preferences/opinions, e.g.:

- I prefer writing runtime.Goshed() where _really_ necessary is
explicit. I like the explicitness in this (as in almost every other
part of Go).
- I have never ran into a problem caused by cooperative scheduling
(modulo me being stupid).
- I prefer that specs _do not_ talk about this.

IIUC, preemptive scheduling can change the semantics of a program.
Once a preemptive scheduling kicks into reality, it'll make for
programs which will behave differently, if at all correctly, on any
other implementation(s) which would not have preemptive goroutine
scheduling as well. So it probably would have to be specified,
finally. I prefer the order to be specification -> implementation, not
the other way around.

Also, there's some inevitable overhead behind preemptive scheduling. I
don't want to speculate about the amount of performance degradation,
but it cannot be a zero.

Feel free to ignore me, I'm known to be a bit conservative ;-)

-j

[Dmitry Vyukov]

On Fri, Mar 29, 2013 at 9:05 PM, Jan Mercl <0xj...@gmail.com> wrote:

On Fri, Mar 29, 2013 at 3:13 PM, Dmitry Vyukov <dvy...@google.com> wrote:

I expect to be in a minority camp on this, but I don't currently
invite the idea. I have no solid/real argument against, only
preferences/opinions, e.g.:

- I prefer writing runtime.Goshed() where _really_ necessary is
explicit. I like the explicitness in this (as in almost every other
part of Go).

You do not know where it is necessary, because you do not know when GC happens.

Check out this issue:

https://code.google.com/p/go/issues/detail?id=4711

 

sleep took 1.0003939s
sleep took 1.007229564s
sleep took 1.00105351s
sleep took 1.001116228s
sleep took 3m23.461937165s

BOOM

- I have never ran into a problem caused by cooperative scheduling
(modulo me being stupid).
- I prefer that specs _do not_ talk about this.

IIUC, preemptive scheduling can change the semantics of a program.

Currently re-scheduling can happen on every malloc(), i.e. basically everywhere.

[Jan Mercl]

On Fri, Mar 29, 2013 at 6:13 PM, Dmitry Vyukov <dvy...@google.com> wrote:
> You do not know where it is necessary, because you do not know when GC
> happens.

I know where it is necessary. It is necessary where other goroutines
cannot progress w/o explicit runtime.Gosched(). Such situation can
occur only rarely and in only some very specific goroutines and in
only some very specific scenarios. But those _can_ change semantics,
IIANM.

>> IIUC, preemptive scheduling can change the semantics of a program.
>
>
> Currently re-scheduling can happen on every malloc(), i.e. basically
> everywhere.

'Basically everywhere' means 'not guaranteed everywhere'. Not every
goroutine allocates memory, for example.

Please don't see this as an argument. I really don't expect my opinion
to be the adopted one. I just wanted to let other's note that there's
at least (some)one who prefers status quo.

-j

[Daniel Morsing]

Any plans on how to identify critical sections? The runtime is getting
pretty big, and it's easy to overlook something that requires
non-preemptive execution.

> On Unix systems preemption can be implemented by means of signals, on
> Windows -- Suspend/ResumeThread, Get/SetThreadContext.
> preempt() routine needs to safely derive M from P (can race with
> releasep()), and send a signal to the thread. The signal handler is
> implemented along the lines of:
>
> void
> preempthandler(int signo, siginfo_t *si, ucontext_t *uc)
> {
> if(m->nopreemption) {
> // The thread will gosched()
> // when exits from the critical section.
> m->preemptionrequested = 1;
> return;
> }
> savecontext(uc);
> altercontext(uc); // sets pc to gosched()
> }
>
> The preempted goroutine needs to be put onto the tail of global run queue,
> otherwise it can be scheduled over and over again (if put onto the local
> queue) starving other goroutines on the global run queue.
> There is some chance that signals can be lost on some unix systems, in such
> case the preemption must be retried after some period of time.

Do realtime signals have delivery guarantees? Maybe they would be of use here.

>
> Context Restoration
> ===================
>
> There are 2 ways to restore the original context (registers) of a preempted
> thread:
> 1. Save context in G struct and set a special preempted flag. If the flag is
> set, scheduler restores registers from G struct and GC scans the context.
> 2. Create fake stack frame during preemption and save the context in the
> stack frame. The stack frame will restore the context and return back to the
> preemption pc. The advantage is that this does not require modification of
> scheduler/GC.

I'm in favor of saving the context in G. I think it will be more work
to adjust all the stack handling code to handle the fake frames, than
it is to adjust the GC to scan the context. One of the scenarios i'm
thinking about is when preemption happens when the SP is on the edge
of a stack segment. If you allocate a new segment, you have to go
through the lessstack code when returning and I'm not sure how that
function will make sure the context isn't clobbered.

>
> Testing
> =======
>
> Besides normal testing it's possible to create special tests that:
> - test GC pause in presence of "for {}" goroutines
> - require parallelism to complete, e.g. pin-pong using active spinning
> - expose races between preemption and voluntary switch
> - expose races between preemption and syscalls
>
> Also it may be useful to run std tests with GOGC=1 GOMAXPROCS=64, because it
> will force frequent GCs that will preempt goroutines at random places.
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-dev+...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

Otherwise, Good stuff.

Regards,
Daniel Morsing

[Keith Randall]

> Any plans on how to identify critical sections? The runtime is getting

> pretty big, and it's easy to overlook something that requires

> non-preemptive execution.

I would second this.  There are going to be a lot of places where data structures are in intermediate states which can't be exposed to the GC.  They either have to be fixed or wrapped as indicated.  Miss one and you've got a nasty heisenbug.

Maybe even the compiler generates unsafe code?  We'd have to check.

[Carl Shapiro]

On Fri, Mar 29, 2013 at 7:13 AM, Dmitry Vyukov <dvy...@google.com> wrote:

On Unix systems preemption can be implemented by means of signals, on Windows -- Suspend/ResumeThread, Get/SetThreadContext.

preempt() routine needs to safely derive M from P (can race with releasep()), and send a signal to the thread. The signal handler is implemented along the lines of:

Unfortunately, this mechanism for preemption is incompatible with my on-going work to provide precise roots for garbage collection.

A better mechanism would be to have the compiler emit code to poll a status flag that indicates whether it needs to perform some work on behalf of the runtime.  It is my intention to do that work once I am able to scan the stack precisely.  If you would like to start on this ahead of me, we should talk.

[Robert Griesemer]

As is the case now, GC can only happen when all goroutines are at controlled point in the code, typically called a "safepoint" (usually a call site). With pre-emptive scheduling, each goroutine that is not at a safepoint must be rolled forward to a safepoint before GC can happen - at least if a StopTheWorld event is required for the GC, which I believe is the case in our world.

A common way of doing this is to start all goroutines which are not at a safepoint (i.e., a call site) and have them run to the next call site where they suspend themselves. In Go, this could be achieved by temporarily lowering the stack limits for each of the affected goroutines so that the usual stack segment overflow check will call into the runtime and then the goroutine can suspend itself (and correct the stack frame size back). Additionally, loops that don't contain any calls may need an extra check at the backward branch (or perhaps at the loop body start since there may be only one entry point but multiple backward branches), so that GC is not blocked waiting for a long-running loop.

A word of caution: This is probably an old hat, but in 1997, the HotSpot JVM, at that point just acquired by Sun Micro, was exactly in the same situation: the VM was based on goroutines. The conversion from that model to the fully pre-emptive system everybody is accustomed to now was non-trivial and it took a very long time (almost a year) to get the system stable again because code all over the place was making implicit assumptions about the non-preemptive scheduling nature of the VM (as we do in Go, btw). When every bug is a GC bug, things move slowly...

- gri

[Ingo Oeser]

I would only like to have it to avoid the long GC pauses, if the pauses really cannot be fixed by other means.

A much easier way might be to simply allow a go-routine to be EXCLUSIVELY locked to an OS thread and let the OS handle all these upcoming issues,

because it has all the above already implemented. Details below.

On Friday, March 29, 2013 6:05:26 PM UTC+1, Jan Mercl wrote:

I expect to be in a minority camp on this, but I don't currently
invite the idea. I have no solid/real argument against, only
preferences/opinions, e.g.:

Let me join the minority camp here and maybe help with solid arguments.

 

- I prefer writing runtime.Goshed() where _really_ necessary is
explicit. I like the explicitness in this (as in almost every other
part of Go).

Me too. This explicit scheduling also helps with HPC workloads, where the scheduling noise is an issue.

Testing for monopolized CPU is pretty easy in test cases calling the code that would monopolized in N goroutines,

where N >> NumCPUs

Spreading the CPU intensive work using OpenMP-like constructs would make it easy for everyone even with the current setup.

The next problem to handle over the next months then will be getting the (already preemptive!) thread scheduler cooperate with the goroutine scheduler

and still get decent performance out of it

* on a wide range of hardware (from phones to big servers)

* on a wide range of software/system scenarios 

  * responsive gui app

  * beeing one of N background daemon tasks, so you getting lots of resources is a non-issue, you should conserve resources here.

  * core app of the machine, so your resources are the most important

  * periodically started program, where you should startup and finish fast

  * power conserving scenarios, where waking more CPUs or keeping a CPU busy beyond the main tasks is unwanted

* on a all supported platforms including their quite different async IO frame works and there thread scheduler interactions

And I didn't start talking about scheduling priority settings for go-routines, scheduling classes, io scheduling, resource groups, etc.pp.

Do you really want to replicate all this in user space over the next years?

- I have never ran into a problem caused by cooperative scheduling
(modulo me being stupid).

Neither did I. Until now I considered it an important feature of Go and praised this good decision of its designers.

[Dmitry Vyukov]

On Fri, Mar 29, 2013 at 9:23 PM, Jan Mercl <0xj...@gmail.com> wrote:

On Fri, Mar 29, 2013 at 6:13 PM, Dmitry Vyukov <dvy...@google.com> wrote:

> You do not know where it is necessary, because you do not know when GC
> happens.

I know where it is necessary. It is necessary where other goroutines
cannot progress w/o explicit runtime.Gosched(). Such situation can
occur only rarely and in only some very specific goroutines and in
only some very specific scenarios. But those _can_ change semantics,
IIANM.

No, you don't, because you dont' know when another goroutine has requested GC.

On the other hand, rescheduling can happen on allocation of a temp variable in the code. If Gosched() changes semantics of (breaks) your code, you have bad/buggy program. Gosched() is semantical no-op.

 

>> IIUC, preemptive scheduling can change the semantics of a program.
>
>
> Currently re-scheduling can happen on every malloc(), i.e. basically
> everywhere.

'Basically everywhere' means 'not guaranteed everywhere'. Not every
goroutine allocates memory, for example.

It's not guaranteed to everywhere, but already can happen basically everywhere. So you should not be relying on where it can happen.

[Dmitry Vyukov]

On Sat, Mar 30, 2013 at 4:47 AM, Ingo Oeser <night...@googlemail.com> wrote:

I would only like to have it to avoid the long GC pauses, if the pauses really cannot be fixed by other means.

A much easier way might be to simply allow a go-routine to be EXCLUSIVELY locked to an OS thread and let the OS handle all these upcoming issues,

because it has all the above already implemented. Details below.

If you set GOMAXPROCS to infinity, it won't help with GC pauses and it will work deadly slow. That's not what users are intended to do with their Go programs to work around current runtime bugs.

On Friday, March 29, 2013 6:05:26 PM UTC+1, Jan Mercl wrote:

I expect to be in a minority camp on this, but I don't currently
invite the idea. I have no solid/real argument against, only
preferences/opinions, e.g.:

Let me join the minority camp here and maybe help with solid arguments.

 

- I prefer writing runtime.Goshed() where _really_ necessary is
explicit. I like the explicitness in this (as in almost every other
part of Go).

Me too. This explicit scheduling also helps with HPC workloads, where the scheduling noise is an issue.

Testing for monopolized CPU is pretty easy in test cases calling the code that would monopolized in N goroutines,

where N >> NumCPUs

Spreading the CPU intensive work using OpenMP-like constructs would make it easy for everyone even with the current setup.

The next problem to handle over the next months then will be getting the (already preemptive!) thread scheduler cooperate with the goroutine scheduler

and still get decent performance out of it

* on a wide range of hardware (from phones to big servers)

* on a wide range of software/system scenarios 

  * responsive gui app

  * beeing one of N background daemon tasks, so you getting lots of resources is a non-issue, you should conserve resources here.

  * core app of the machine, so your resources are the most important

  * periodically started program, where you should startup and finish fast

  * power conserving scenarios, where waking more CPUs or keeping a CPU busy beyond the main tasks is unwanted

* on a all supported platforms including their quite different async IO frame works and there thread scheduler interactions

And I didn't start talking about scheduling priority settings for go-routines, scheduling classes, io scheduling, resource groups, etc.pp.

Do you really want to replicate all this in user space over the next years?

To make it clear, I expect actual preemption to happen very infrequently in realistic Go programs. So it should not affect performance characteristics of various programs. The "nopreemption" critical section can serve as additional voluntary preemption points as well. I.e. if a goroutine runs for X ms, request voluntary preemption first. If that does not work, request involuntary preemption after 2*X ms.

We've made the decision about replicating everything necessary in Go runtime, when we've moved the scheduler into user space. It's similar for memory allocator, once you move it into user space you have to go to the bitter end of thread caches, coalescing, defragmentation, optimization, etc.

Yes, I have some plans for basic priority scheduling. In fact, it's partially already there, e.g. a gorotuine that executes Gosched() intentionally has lower priority than a new goroutine.

[Dmitry Vyukov]

I do not have any secret magic plan. I am thinking about just carefully reviewing runtime, gc, reflect, etc, and then fixing remaining issues if any.

 

> On Unix systems preemption can be implemented by means of signals, on
> Windows -- Suspend/ResumeThread, Get/SetThreadContext.
> preempt() routine needs to safely derive M from P (can race with
> releasep()), and send a signal to the thread. The signal handler is
> implemented along the lines of:
>
> void
> preempthandler(int signo, siginfo_t *si, ucontext_t *uc)
> {
> if(m->nopreemption) {
> // The thread will gosched()
> // when exits from the critical section.
> m->preemptionrequested = 1;
> return;
> }
> savecontext(uc);
> altercontext(uc);  // sets pc to gosched()
> }
>
> The preempted goroutine needs to be put onto the tail of global run queue,
> otherwise it can be scheduled over and over again (if put onto the local
> queue) starving other goroutines on the global run queue.
> There is some chance that signals can be lost on some unix systems, in such
> case the preemption must be retried after some period of time.

Do realtime signals have delivery guarantees? Maybe they would be of use here.

Yes, they can be better.

> Context Restoration
> ===================
>
> There are 2 ways to restore the original context (registers) of a preempted
> thread:
> 1. Save context in G struct and set a special preempted flag. If the flag is
> set, scheduler restores registers from G struct and GC scans the context.
> 2. Create fake stack frame during preemption and save the context in the
> stack frame. The stack frame will restore the context and return back to the
> preemption pc. The advantage is that this does not require modification of
> scheduler/GC.

I'm in favor of saving the context in G. I think it will be more work
to adjust all the stack handling code to handle the fake frames, than
it is to adjust the GC to scan the context.

The idea is that the fake frame looks *exactly* as normal frame. So no need to adjust anything.

 

One of the scenarios i'm
thinking about is when preemption happens when the SP is on the edge
of a stack segment. If you allocate a new segment, you have to go
through the lessstack code when returning and I'm not sure how that
function will make sure the context isn't clobbered.

I think current signal handling code should already deal with this.

[Dmitry Vyukov]

Sure, let's talk. I will stop by your desk on Mon.

But the general idea is that this should be handled as if the code uses unsafe.Pointer's in this place. In fact, it can be implemented as:

type ucontext struct {

  rax, rbx, ... unsafe.Pointer

}

func restoreAfterPreemption(uc *ucontext) {

  mov rax, uc.rax

  mov rbx, uc.rbx

  ...

  ret

}

If you want safe points, you can emit one in the beginning of the function.

[Jan Mercl]

On Sun, Mar 31, 2013 at 10:41 PM, Dmitry Vyukov <dvy...@google.com> wrote:
> On Fri, Mar 29, 2013 at 9:23 PM, Jan Mercl <0xj...@gmail.com> wrote:
>>
>> On Fri, Mar 29, 2013 at 6:13 PM, Dmitry Vyukov <dvy...@google.com> wrote:
>> > You do not know where it is necessary, because you do not know when GC
>> > happens.
>>
>> I know where it is necessary. It is necessary where other goroutines
>> cannot progress w/o explicit runtime.Gosched(). Such situation can
>> occur only rarely and in only some very specific goroutines and in
>> only some very specific scenarios. But those _can_ change semantics,
>> IIANM.
>
>
> No, you don't, because you dont' know when another goroutine has requested
> GC.

Yes I do, b/c what you wrote and my "It is necessary where other
goroutines cannot progress w/o explicit runtime.Gosched()." are in no
conflict AFAICS. Let me expand: If I write some code where some
goroutine makes no progress whatsover and makes progress after
inserting Goshed in the appropriate place then I know I needed to
insert Goshed.

> On the other hand, rescheduling can happen on allocation of a temp variable
> in the code. If Gosched() changes semantics of (breaks) your code, you have
> bad/buggy program. Gosched() is semantical no-op.

Quoting http://golang.org/pkg/runtime/#Gosched

> Gosched yields the processor, allowing other goroutines to run.
> It does not suspend the current goroutine, so execution resumes automatically.

This is not a semantic no-op - the documentation could be empty then
(but for GOMAXPROCS == 1 it's a guaranteed yield). Go programs can
legitimately change behavior depending on what goroutines make
progress vs no progress and even the order of that is important.
(Recall all the questions in the mailing lists where, for example, the
problem is solved by setting non zero GOMAXPROCS or non zero channel
buffer). If there's precisely determined behavior derivable for those
cases, dependent on deterministic execution order, then I don't know
how to distinguish it from semantics.

-j

PS: Once again, I'm not even trying to convince you to abandon the
plan. Yet my wish is like that. I still value the non-preemptivenes of
goroutines doing no alloc or I/O. There is IMHO some valuable power in
yielding explicitly in those cases.

[Dmitry Vyukov]

On Fri, Mar 29, 2013 at 10:52 PM, Robert Griesemer <g...@golang.org> wrote:

As is the case now, GC can only happen when all goroutines are at controlled point in the code

Why is that required?

Currently GC does not care where goroutines are stopped as long as it knows all roots.

 

, typically called a "safepoint" (usually a call site). With pre-emptive scheduling, each goroutine that is not at a safepoint must be rolled forward to a safepoint before GC can happen - at least if a StopTheWorld event is required for the GC, which I believe is the case in our world.

A common way of doing this is to start all goroutines which are not at a safepoint (i.e., a call site) and have them run to the next call site where they suspend themselves. In Go, this could be achieved by temporarily lowering the stack limits for each of the affected goroutines so that the usual stack segment overflow check will call into the runtime and then the goroutine can suspend itself (and correct the stack frame size back). Additionally, loops that don't contain any calls may need an extra check at the backward branch (or perhaps at the loop body start since there may be only one entry point but multiple backward branches), so that GC is not blocked waiting for a long-running loop.

A word of caution: This is probably an old hat, but in 1997, the HotSpot JVM, at that point just acquired by Sun Micro, was exactly in the same situation: the VM was based on goroutines. The conversion from that model to the fully pre-emptive system everybody is accustomed to now was non-trivial and it took a very long time (almost a year) to get the system stable again because code all over the place was making implicit assumptions about the non-preemptive scheduling nature of the VM (as we do in Go, btw). When every bug is a GC bug, things move slowly...

I never implemented preemptive scheduling in GC system, so at least I want to educate myself as a result of this discussion :)

What can be potential pitfalls for Go?

As I see it:

Due to race-free property we do not care about intermediate states of objects as observed by other goroutines.

We care about runtime per-thread state (G, M, P) and we care about intermediate states of objects that GC has intimate knowledge about (maps, slices).

So we need to mark as nopreemption:

- most of the runtime in coarse-grained style, e.g. hasmaps, slices, memory allocator, scheduler, everything that takes mutexes (incl chans).

- probably gc emitted code for slice manipulation.

- probably reflect if it manipulates maps/slices.

What can cause the long tail of bugs?

[Dmitry Vyukov]

On Mon, Apr 1, 2013 at 1:10 AM, Jan Mercl <0xj...@gmail.com> wrote:

>> > You do not know where it is necessary, because you do not know when GC
>> > happens.
>>
>> I know where it is necessary. It is necessary where other goroutines
>> cannot progress w/o explicit runtime.Gosched(). Such situation can
>> occur only rarely and in only some very specific goroutines and in
>> only some very specific scenarios. But those _can_ change semantics,
>> IIANM.
>
>
> No, you don't, because you dont' know when another goroutine has requested
> GC.

Yes I do, b/c what you wrote and my "It is necessary where other
goroutines cannot progress w/o explicit runtime.Gosched()." are in no
conflict AFAICS. Let me expand: If I write some code where some
goroutine makes no progress whatsover and makes progress after
inserting Goshed in the appropriate place then I know I needed to
insert Goshed.

It's not a property of the code, it's a property of the whole system running under particular workload in a particular environment. You can hg sync std lib, and you conclusions do not stand anymore. As a consequence, the question is impossible to answer for a library code (incl std lib).

> On the other hand, rescheduling can happen on allocation of a temp variable
> in the code. If Gosched() changes semantics of (breaks) your code, you have
> bad/buggy program. Gosched() is semantical no-op.

Quoting http://golang.org/pkg/runtime/#Gosched

> Gosched yields the processor, allowing other goroutines to run.
> It does not suspend the current goroutine, so execution resumes automatically.

This is not a semantic no-op - the documentation could be empty then

Documentation is not only about semantics, it can be about performance hints for example.

(but for GOMAXPROCS == 1 it's a guaranteed yield)

No... it is not.

For example, it can yield every N-th call to 1 random goroutine. Or it may not yield at all if it knowns that another goroutine yielded recently. Don't make assumptions about its behavior.

 

Go programs can
legitimately change behavior depending on what goroutines make
progress vs no progress and even the order of that is important.

Can you provide an example? It's all unspecified and are implementation details.

Of course, Gosched() can change one possible execution to another possible execution. But that's all unspecified and it's not specified how exaclty it will change the behavior, and the behavior can change after 'hg sync' or depending on day of the week. So I do not see your point.

Put it this way, Go program yields one of the allowed executions. Which exactly is unspecified and can change depending on anything. Adding/removing Gosched's adds nothing to the picture.

[Ingo Oeser]

Hi Dmitry,

I think you got me wrong. Sorry for the bad communication skills of mine. Will now try to explain more deeply what I mean with exclusive to OS thread.

Basic idea: Tasks that are busy map 1:1 to threads, other still N:M.

Algorithm would be like this triggered only if running G in a M using a P for at least time T:

given a busy M, called Mbusy

look for a new M, called Mnew

steal away all waiting Gs from the M, so that only the "too busy" G is left.

/* note that this the classic work stealing scheduler already implemented until above */

mark Mbusy as "overloaded"

an M marked as "overloaded", will not be considered again in preemption and will not considered as a target or source in work stealing on voluntary preemption.

"overloaded" can only be cleared by voluntary preemption of the sole running G. Then M is available as a work stealing target again.

/* end of new stuff */

If you like to localize the effect, you can make Mnew and Mold compete for the same P.

Advantage here is, you leverage the powerful OS schedulers tuned for busy tasks, due to system global view of things and architectural knowledge (e.g. topology).

You also leverage the powerful Go scheduler, which excels in lots of waiting tasks, due to cheaper wakeup and less state to manage.

This way you also don't need to handle:

* priorities

* time slices

* cache buddies (decision of same CPU beneficial, even if both busy)

* topology

* resource management and limits

* cooperation with global state (e.g. your process as a whole was starved and you are measuring it wrong)

* power management (e.g. your thread was on a CPU that was powered low for a while and made not enough progress)

* many more than I forgot now :-)

as the OS handles it already for you perfectly, if you communicate your busy tasks as  threads:

Disadvantage: You need more threads in the overloaded case.

But I don't consider this a big problem, as you now communicate clearly to the OS and it can apply all the usual rules of resource management on programs that behave badly,

since it cannot hide that fact anymore. Also the system administrator can now (automatically) detect, report and act on this condition with his normal tooling.

If you have any more questions on the suggested algorithm, please ask!

Best Regards

Ingo

[Carl Shapiro]

On Sun, Mar 31, 2013 at 2:05 PM, Dmitry Vyukov <dvy...@google.com> wrote:

Sure, let's talk. I will stop by your desk on Mon.

But the general idea is that this should be handled as if the code uses unsafe.Pointer's in this place. In fact, it can be implemented as:

I am not sure I follow your analogy to unsafe.Pointer.  I understand that the raw contents of the register file can be made available to the garbage collector.  However, without information to describe the types of values in registers and stack slots, precise garbage collection is not possible.

It is known that generating dsecriptions for the types of values in all registers and stack slots at every PC location is very costly in terms of time and space.  This is further complicated by code that is not inheirently interruptable.  While the interruptability issue might be mitigated by judicious use of fences and atomic operations, it increases the cost of operations that are otherwise extremely cheap.

If you want safe points, you can emit one in the beginning of the function.

We might not be referring to the same concept.  Let us talk about this more in person.  I am at my desk today.