I have been working on a fascinating, I think, problem that pushes the limits of language and runtime, and raises some interesting questions. These questions have to do with implementing "synthetic time" and its applications to real-time control (think robotics or Internet congestion control e.g.) algorithms.
First, and briefly: How this problem came to be.
I have been working on a user-space version of the IETF congestion control protocol DCCP, authored by Eddie Kohler. My project itself is found at github.com/petar/GoDCCP
At a high-level, the core functionality of this project is the "control logic" whose job it is to listen for exeternal network events (like reads) and create responses (like writes), which (and this is the twist) are scheduled to be executed at some future point in time.
In order to decouple the control logic from the details of networking and OS, the control logic is implemented as an object (a struct, say, called ControlLogic) which interacts with the outside world through a narrow interface, which is passed to it upon initialization:
type OutsideWorld interface { Sleep(nanoseconds int64) // Block for the duration of nanoseconds Now() (nanoseconds int64) // Tell me the time now
Read() (packet []byte) // Block until a packet is available for reading Write(packet []byte) // Block until you can write this packet
}
ControlLogic itself has no public methods.
Internally, the control logic is allowed to use the facilities of the Go Language. In particular, it can us the go-operator and it can create and manipulate channels. However, it does not use any packages whatsoever.
The interesting problem arises, when we attempt to write tests for the control logic.
Our goal is to test the control logic as a black box. This means we want to test whether it _responds_ as expected to its _input_.
Observe that the _input_ to the control logic is implicit in the behavior of the OutsideWorld interface. There is no other point of interaction with the outside world.
Furthermore, observe that the _response_ of the control logic is implicit in what calls it makes to the methods of OutsideWorld (and in what order and with what timing).
The obvious way to design a test is to implement OutsideWorld, so that Now and Sleep simply invoke their respective functions from the time package, while Read and Write can be implemented to simulate whatever network blocking behavior we like.
This works. But there is an issue with it.
Typically, we would want to run a test that spans minutes of real time, so that multiple corners of the ControlLogic can be tested.
In a typical long-lasting execution of the ControlLogic, most of the time is spend just waiting on Sleep or I/O operations.
And here comes the crux:
We would like to design a testing environment which runs instantaneously, while faithfully simulating a long-running test in real time.
Intuitively, we would like to implement a "synthetic time" version of OutsideWorld, where Sleeps return immediately, while the Nows account for the passing of time correctly.
It turns out (and this is not hard to check), that we can simplify the problem, by assuming that the interaction with the outside world is given by this simpler interface:
type SimpleOutsideWorld interface { Sleep(nanoseconds int64) Now() (nanoseconds int64)
}
Is it possible to come up with an implementation SyntheticTime of SimpleOutsideWorld in a manner so that executing ControlLogic with SyntheticTime as its argument is functionally equivalent to an execution where SimpleOutsideWorld is implemented by RealTime, given below:
So, to prove that this is not a hopeless problem, I am inclusing below an implementation of SyntheticTime that does work, however it relies on a non-existent (imaginary) function that would be provided by the Go runtime. This function is called
// YieldUntilAllOtherBlock blocks the execution of the current Go routine and // yields to other goroutines. It returns when all other goroutines have blocked. func YieldUntilAllOtherBlock()
With this imaginary function under our belt, we can implement SyntheticTime and the implementation is shown below.
I do not think that a semantically correct implementation of SyntheticTime is possible in Go without circumventing the language in an unsafe manner, or without adding some additional interface into the runtime similar to YieldUntilAllOtherBlock.
Furthermore, even if you require that ControlLogic does not call the go-operator directly, but rather goes through the outside world interface:
SyntheticTime is still impossible. In fact, SyntheticTime is impossible even if outside world captures the channel operations of ControlLogic as well.
If you prove me wrong, I will be amazed. The more likely outcome of this discussion, I think, is that the runtime package of Go needs to include some additional access to the underlying runtime.
PS: Note that runtime.Gosched() feels very similar to our imaginary YieldUntilAllOtherBlock, but it does not carry the desired semantics and does not work as a replacement for YieldUntilAllOtherBlock.
PSS: I am not suggesting that YieldUntilAllOtherBlock is the function that should be added to the runtime package. For one, it is not clear what its behavior should be if called from multiple goroutines. This exposition is supposed to demonstrate that if we believe that synthetic time is something we should be able to implement, than _some_ addition has to made to the runtime package of Go.
__________________________________________________________________________ Here goes the code for SyntheticTime: __________________________________________________________________________
type SyntheticTime struct { reqch chan interface{} donech chan int
type requestSleep struct { duration int64 resp chan int
}
type requestNow struct { resp chan int64
}
type scheduledToSleep struct { wake int64 resp chan int
}
func (x *SyntheticTime) loop() { var now int64 var sleepers sleeperQueue ForLoop: for { YieldUntilAllOtherBlock() var req interface{} select { case req = <-x.reqch: default:
}
if req != nil { switch t := req.(type) { case requestSleep: sleepers.Add(&scheduledToSleep{ wake: now + t.duration, resp: t.resp }) case requestNow: t.resp <- now default: panic("unknown request")
If you'll be happy with just the loop functions yielding to each other,
sync.Cond may do the job. Keep a counter for the total number of goroutines
you've launched, and another counter for the number of goroutines that are
yielding. If they become equal, you signal.
On Sat, Apr 28, 2012 at 11:39 AM, Petar Maymounkov <pet...@gmail.com> wrote:
> Hi all,
> I have been working on a fascinating, I think, problem
> that pushes the limits of language and runtime, and
> raises some interesting questions. These questions
> have to do with implementing "synthetic time" and
> its applications to real-time control (think robotics
> or Internet congestion control e.g.) algorithms.
> First, and briefly: How this problem came to be.
> I have been working on a user-space version of the IETF
> congestion control protocol DCCP, authored by Eddie Kohler.
> My project itself is found at github.com/petar/GoDCCP
> At a high-level, the core functionality of this project is
> the "control logic" whose job it is to listen for exeternal
> network events (like reads) and create responses (like writes),
> which (and this is the twist) are scheduled to be executed
> at some future point in time.
> In order to decouple the control logic from the details of
> networking and OS, the control logic is implemented as an
> object (a struct, say, called ControlLogic) which interacts
> with the outside world through a narrow interface, which is
> passed to it upon initialization:
> type OutsideWorld interface {
> Sleep(nanoseconds int64) // Block for the duration of nanoseconds
> Now() (nanoseconds int64) // Tell me the time now
> Read() (packet []byte) // Block until a packet is available for reading
> Write(packet []byte) // Block until you can write this packet
> }
> ControlLogic itself has no public methods.
> Internally, the control logic is allowed to use the
> facilities of the Go Language. In particular, it can
> us the go-operator and it can create and manipulate channels.
> However, it does not use any packages whatsoever.
> The interesting problem arises, when we attempt to write
> tests for the control logic.
> Our goal is to test the control logic as a black box. This means
> we want to test whether it _responds_ as expected to its _input_.
> Observe that the _input_ to the control logic is implicit in the
> behavior of the OutsideWorld interface. There is no other point
> of interaction with the outside world.
> Furthermore, observe that the _response_ of the control logic is
> implicit in what calls it makes to the methods of OutsideWorld
> (and in what order and with what timing).
> The obvious way to design a test is to implement OutsideWorld,
> so that Now and Sleep simply invoke their respective functions
> from the time package, while Read and Write can be implemented
> to simulate whatever network blocking behavior we like.
> This works. But there is an issue with it.
> Typically, we would want to run a test that spans minutes
> of real time, so that multiple corners of the ControlLogic
> can be tested.
> In a typical long-lasting execution of the ControlLogic,
> most of the time is spend just waiting on Sleep or I/O
> operations.
> And here comes the crux:
> We would like to design a testing environment which runs
> instantaneously, while faithfully simulating a long-running
> test in real time.
> Intuitively, we would like to implement a "synthetic time"
> version of OutsideWorld, where Sleeps return immediately,
> while the Nows account for the passing of time correctly.
> It turns out (and this is not hard to check), that we
> can simplify the problem, by assuming that the interaction
> with the outside world is given by this simpler interface:
> Is it possible to come up with an implementation SyntheticTime of
> SimpleOutsideWorld in a manner so that executing ControlLogic with
> SyntheticTime as its argument is functionally equivalent to
> an execution where SimpleOutsideWorld is implemented by RealTime,
> given below:
> So, to prove that this is not a hopeless problem, I am inclusing below
> an implementation of SyntheticTime that does work, however it relies
> on a non-existent (imaginary) function that would be provided by the
> Go runtime. This function is called
> // YieldUntilAllOtherBlock blocks the execution of the current Go routine
> and
> // yields to other goroutines. It returns when all other goroutines have
> blocked.
> func YieldUntilAllOtherBlock()
> With this imaginary function under our belt, we can implement SyntheticTime
> and the implementation is shown below.
> I do not think that a semantically correct implementation of SyntheticTime
> is
> possible in Go without circumventing the language in an unsafe manner, or
> without adding some additional interface into the runtime similar to
> YieldUntilAllOtherBlock.
> Furthermore, even if you require that ControlLogic does not
> call the go-operator directly, but rather goes through the outside world
> interface:
> SyntheticTime is still impossible. In fact, SyntheticTime is impossible
> even if outside world captures the channel operations of ControlLogic as
> well.
> If you prove me wrong, I will be amazed. The more likely outcome of this
> discussion, I think, is that the runtime package of Go needs to include
> some additional access to the underlying runtime.
> PS: Note that runtime.Gosched() feels very similar to our imaginary
> YieldUntilAllOtherBlock, but it does not carry the desired semantics
> and does not work as a replacement for YieldUntilAllOtherBlock.
> PSS: I am not suggesting that YieldUntilAllOtherBlock is the function that
> should be added to the runtime package. For one, it is not clear what
> its behavior should be if called from multiple goroutines.
> This exposition is supposed to demonstrate that if we believe that
> synthetic time is something we should be able to implement, than
> _some_ addition has to made to the runtime package of Go.
> __________________________________________________________________________
> Here goes the code for SyntheticTime:
> __________________________________________________________________________
> type SyntheticTime struct {
> reqch chan interface{}
> donech chan int
> }
> func NewSyntheticTime() *SyntheticTime {
> s := &SyntheticTime{
> reqch: make(chan interface{}, 1),
> donech: make(chan int),
> }
> go s.loop()
> return s
> }
> type requestSleep struct {
> duration int64
> resp chan int
> }
> type requestNow struct {
> resp chan int64
> }
> type scheduledToSleep struct {
> wake int64
> resp chan int
> }
> func (x *SyntheticTime) loop() {
> var now int64
> var sleepers sleeperQueue
> ForLoop:
> for {
> YieldUntilAllOtherBlock()
> var req interface{}
> select {
> case req = <-x.reqch:
> default:
> }
> if req != nil {
> switch t := req.(type) {
> case requestSleep:
> sleepers.Add(&scheduledToSleep{ wake: now + t.duration, resp: t.resp })
> case requestNow:
> t.resp <- now
> default:
> panic("unknown request")
> }
> continue ForLoop
> }
> nextToWake := sleepers.DeleteMin()
> if nextToWake == nil {
> break
> }
> now = nextToWake.wake
> close(nextToWake.resp)
> }
> }
On Saturday, April 28, 2012 4:12:39 PM UTC-4, Sugu Sougoumarane wrote:
> If you'll be happy with just the loop functions yielding to each other, > sync.Cond may do the job. Keep a counter for the total number of goroutines > you've launched, and another counter for the number of goroutines that are > yielding. If they become equal, you signal.
> On Sat, Apr 28, 2012 at 11:39 AM, Petar Maymounkov <pet...@gmail.com>wrote:
>> Hi all,
>> I have been working on a fascinating, I think, problem >> that pushes the limits of language and runtime, and >> raises some interesting questions. These questions >> have to do with implementing "synthetic time" and >> its applications to real-time control (think robotics >> or Internet congestion control e.g.) algorithms.
>> First, and briefly: How this problem came to be.
>> I have been working on a user-space version of the IETF >> congestion control protocol DCCP, authored by Eddie Kohler. >> My project itself is found at github.com/petar/GoDCCP
>> At a high-level, the core functionality of this project is >> the "control logic" whose job it is to listen for exeternal >> network events (like reads) and create responses (like writes), >> which (and this is the twist) are scheduled to be executed >> at some future point in time.
>> In order to decouple the control logic from the details of >> networking and OS, the control logic is implemented as an >> object (a struct, say, called ControlLogic) which interacts >> with the outside world through a narrow interface, which is >> passed to it upon initialization:
>> type OutsideWorld interface { >> Sleep(nanoseconds int64) // Block for the duration of nanoseconds >> Now() (nanoseconds int64) // Tell me the time now
>> Read() (packet []byte) // Block until a packet is available for reading >> Write(packet []byte) // Block until you can write this packet >> }
>> ControlLogic itself has no public methods.
>> Internally, the control logic is allowed to use the >> facilities of the Go Language. In particular, it can >> us the go-operator and it can create and manipulate channels. >> However, it does not use any packages whatsoever.
>> The interesting problem arises, when we attempt to write >> tests for the control logic.
>> Our goal is to test the control logic as a black box. This means >> we want to test whether it _responds_ as expected to its _input_.
>> Observe that the _input_ to the control logic is implicit in the >> behavior of the OutsideWorld interface. There is no other point >> of interaction with the outside world.
>> Furthermore, observe that the _response_ of the control logic is >> implicit in what calls it makes to the methods of OutsideWorld >> (and in what order and with what timing).
>> The obvious way to design a test is to implement OutsideWorld, >> so that Now and Sleep simply invoke their respective functions >> from the time package, while Read and Write can be implemented >> to simulate whatever network blocking behavior we like.
>> This works. But there is an issue with it.
>> Typically, we would want to run a test that spans minutes >> of real time, so that multiple corners of the ControlLogic >> can be tested.
>> In a typical long-lasting execution of the ControlLogic, >> most of the time is spend just waiting on Sleep or I/O >> operations.
>> And here comes the crux:
>> We would like to design a testing environment which runs >> instantaneously, while faithfully simulating a long-running >> test in real time.
>> Intuitively, we would like to implement a "synthetic time" >> version of OutsideWorld, where Sleeps return immediately, >> while the Nows account for the passing of time correctly.
>> It turns out (and this is not hard to check), that we >> can simplify the problem, by assuming that the interaction >> with the outside world is given by this simpler interface:
>> Is it possible to come up with an implementation SyntheticTime of >> SimpleOutsideWorld in a manner so that executing ControlLogic with >> SyntheticTime as its argument is functionally equivalent to >> an execution where SimpleOutsideWorld is implemented by RealTime, >> given below:
>> So, to prove that this is not a hopeless problem, I am inclusing below >> an implementation of SyntheticTime that does work, however it relies >> on a non-existent (imaginary) function that would be provided by the >> Go runtime. This function is called
>> // YieldUntilAllOtherBlock blocks the execution of the current Go routine >> and >> // yields to other goroutines. It returns when all other goroutines have >> blocked. >> func YieldUntilAllOtherBlock()
>> With this imaginary function under our belt, we can implement >> SyntheticTime >> and the implementation is shown below.
>> I do not think that a semantically correct implementation of >> SyntheticTime is >> possible in Go without circumventing the language in an unsafe manner, or >> without adding some additional interface into the runtime similar to >> YieldUntilAllOtherBlock.
>> Furthermore, even if you require that ControlLogic does not >> call the go-operator directly, but rather goes through the outside world >> interface:
>> SyntheticTime is still impossible. In fact, SyntheticTime is impossible >> even if outside world captures the channel operations of ControlLogic as >> well.
>> If you prove me wrong, I will be amazed. The more likely outcome of this >> discussion, I think, is that the runtime package of Go needs to include >> some additional access to the underlying runtime.
>> PS: Note that runtime.Gosched() feels very similar to our imaginary >> YieldUntilAllOtherBlock, but it does not carry the desired semantics >> and does not work as a replacement for YieldUntilAllOtherBlock.
>> PSS: I am not suggesting that YieldUntilAllOtherBlock is the function that >> should be added to the runtime package. For one, it is not clear what >> its behavior should be if called from multiple goroutines. >> This exposition is supposed to demonstrate that if we believe that >> synthetic time is something we should be able to implement, than >> _some_ addition has to made to the runtime package of Go.
>> __________________________________________________________________________ >> Here goes the code for SyntheticTime: >> __________________________________________________________________________
>> type SyntheticTime struct { >> reqch chan interface{} >> donech chan int >> }
>> func NewSyntheticTime() *SyntheticTime { >> s := &SyntheticTime{ >> reqch: make(chan interface{}, 1), >> donech: make(chan int), >> } >> go s.loop() >> return s >> }
>> type requestSleep struct { >> duration int64 >> resp chan int >> }
Yeah, it won't work if any of your functions blocked on other stuff.
However, I think your particular case can still be made to work by using
buffered channels (which you already are), adding explicit waits, and
signaling any time you sent a message. I had to do similar tricks for a
round robin resource pool for vitess.
I guess a global yield is still a very different thing, but I think it's a
feature that could get misused. Personally, I prefer the clarity of waiting
for specific things.
Yeah, I do believe that if I capture channel make/send/receive operations as well, then it can be done.
Perhaps, if the goal is not to encumber the developer of ControlLogic with having to use specialized Go and Chan functions, one can achieve this with a source-to-source transform of the ControlLogic code.
If I understand your problem correctly then I think the SyntheticTime in
the code below should suffice. If it doesn't then I think I have
misunderstood your problem.
package main
import (
"fmt"
"sync"
)
type SimpleOutsideWorld interface {
Sleep(ns int64)
Now() int64
}
type syntheticTimeHandle struct {
t *SyntheticTime
}
func (s *syntheticTimeHandle) sleep(ns int64) {
m := s.t.wait(s, ns)
m.Lock() // When this lock is available ns will have passed
}
type waiter struct {
t int64
m *sync.Mutex
}
type SyntheticTime struct {
now int64
now_chan chan int64
update_chan chan int64
// map from handle to a waiter which indicates when it should be woken,
and
// a mutex for waking it
waiting map[*syntheticTimeHandle]waiter
}
func MakeSyntheticTime() *SyntheticTime {
var s SyntheticTime
s.now_chan = make(chan int64)
s.update_chan = make(chan int64)
s.waiting = make(map[*syntheticTimeHandle]waiter)
go func() {
var now int64
for {
select {
case s.now_chan <- now:
case now = <-s.update_chan:
}
}
} ()
return &s
}
func (s *SyntheticTime) GetHandle() *syntheticTimeHandle {
return &syntheticTimeHandle{s}
}
func (s *SyntheticTime) wait(h *syntheticTimeHandle, ns int64) *sync.Mutex {
var m sync.Mutex
s.waiting[h] = waiter{s.now + ns, &m}
m.Lock()
return &m
}
func (s *SyntheticTime) Sleep(ns int64) {
h := s.GetHandle()
h.sleep(ns)
}
func (s *SyntheticTime) Now() int64 {
return <-s.now_chan
}
// Increment now, then check for anyone sleeping that should be woken up.
// If there is anyone waiting, unlock their locks and remove them from the
// list of waiters.
func (s *SyntheticTime) IncrementTime(ns int64) {
s.now += ns
s.update_chan <- s.now
var done []*syntheticTimeHandle
for h, waiter := range s.waiting {
if waiter.t <= s.now {
waiter.m.Unlock()
done = append(done, h)
}
}
for _, h := range done {
delete(s.waiting, h)
}
}
On Sat, Apr 28, 2012 at 4:08 PM, Petar Maymounkov <pet...@gmail.com> wrote:
> Yeah, I do believe that if I capture channel make/send/receive operations
> as well, then it can be done.
> Perhaps, if the goal is not to encumber the developer of ControlLogic with
> having to use
> specialized Go and Chan functions, one can achieve this with a
> source-to-source transform
> of the ControlLogic code.
The easy way is to not make a completely synthetic time, but make some
accelerated time like 1000x real-time. The problem with
WaitUntilOthersBlock is that you shouldn't care about other concurrent
processes other than the ones with which you communicate.
On Sat, Apr 28, 2012 at 11:39 AM, Petar Maymounkov <pet...@gmail.com> wrote:
> Hi all,
> I have been working on a fascinating, I think, problem
> that pushes the limits of language and runtime, and
> raises some interesting questions. These questions
> have to do with implementing "synthetic time" and
> its applications to real-time control (think robotics
> or Internet congestion control e.g.) algorithms.
> First, and briefly: How this problem came to be.
> I have been working on a user-space version of the IETF
> congestion control protocol DCCP, authored by Eddie Kohler.
> My project itself is found at github.com/petar/GoDCCP
> At a high-level, the core functionality of this project is
> the "control logic" whose job it is to listen for exeternal
> network events (like reads) and create responses (like writes),
> which (and this is the twist) are scheduled to be executed
> at some future point in time.
> In order to decouple the control logic from the details of
> networking and OS, the control logic is implemented as an
> object (a struct, say, called ControlLogic) which interacts
> with the outside world through a narrow interface, which is
> passed to it upon initialization:
> type OutsideWorld interface {
> Sleep(nanoseconds int64) // Block for the duration of nanoseconds
> Now() (nanoseconds int64) // Tell me the time now
> Read() (packet []byte) // Block until a packet is available for reading
> Write(packet []byte) // Block until you can write this packet
> }
> ControlLogic itself has no public methods.
> Internally, the control logic is allowed to use the
> facilities of the Go Language. In particular, it can
> us the go-operator and it can create and manipulate channels.
> However, it does not use any packages whatsoever.
> The interesting problem arises, when we attempt to write
> tests for the control logic.
> Our goal is to test the control logic as a black box. This means
> we want to test whether it _responds_ as expected to its _input_.
> Observe that the _input_ to the control logic is implicit in the
> behavior of the OutsideWorld interface. There is no other point
> of interaction with the outside world.
> Furthermore, observe that the _response_ of the control logic is
> implicit in what calls it makes to the methods of OutsideWorld
> (and in what order and with what timing).
> The obvious way to design a test is to implement OutsideWorld,
> so that Now and Sleep simply invoke their respective functions
> from the time package, while Read and Write can be implemented
> to simulate whatever network blocking behavior we like.
> This works. But there is an issue with it.
> Typically, we would want to run a test that spans minutes
> of real time, so that multiple corners of the ControlLogic
> can be tested.
> In a typical long-lasting execution of the ControlLogic,
> most of the time is spend just waiting on Sleep or I/O
> operations.
> And here comes the crux:
> We would like to design a testing environment which runs
> instantaneously, while faithfully simulating a long-running
> test in real time.
> Intuitively, we would like to implement a "synthetic time"
> version of OutsideWorld, where Sleeps return immediately,
> while the Nows account for the passing of time correctly.
> It turns out (and this is not hard to check), that we
> can simplify the problem, by assuming that the interaction
> with the outside world is given by this simpler interface:
> Is it possible to come up with an implementation SyntheticTime of
> SimpleOutsideWorld in a manner so that executing ControlLogic with
> SyntheticTime as its argument is functionally equivalent to
> an execution where SimpleOutsideWorld is implemented by RealTime,
> given below:
> So, to prove that this is not a hopeless problem, I am inclusing below
> an implementation of SyntheticTime that does work, however it relies
> on a non-existent (imaginary) function that would be provided by the
> Go runtime. This function is called
> // YieldUntilAllOtherBlock blocks the execution of the current Go routine
> and
> // yields to other goroutines. It returns when all other goroutines have
> blocked.
> func YieldUntilAllOtherBlock()
> With this imaginary function under our belt, we can implement SyntheticTime
> and the implementation is shown below.
> I do not think that a semantically correct implementation of SyntheticTime
> is
> possible in Go without circumventing the language in an unsafe manner, or
> without adding some additional interface into the runtime similar to
> YieldUntilAllOtherBlock.
> Furthermore, even if you require that ControlLogic does not
> call the go-operator directly, but rather goes through the outside world
> interface:
> SyntheticTime is still impossible. In fact, SyntheticTime is impossible
> even if outside world captures the channel operations of ControlLogic as
> well.
> If you prove me wrong, I will be amazed. The more likely outcome of this
> discussion, I think, is that the runtime package of Go needs to include
> some additional access to the underlying runtime.
> PS: Note that runtime.Gosched() feels very similar to our imaginary
> YieldUntilAllOtherBlock, but it does not carry the desired semantics
> and does not work as a replacement for YieldUntilAllOtherBlock.
> PSS: I am not suggesting that YieldUntilAllOtherBlock is the function that
> should be added to the runtime package. For one, it is not clear what
> its behavior should be if called from multiple goroutines.
> This exposition is supposed to demonstrate that if we believe that
> synthetic time is something we should be able to implement, than
> _some_ addition has to made to the runtime package of Go.
> __________________________________________________________________________
> Here goes the code for SyntheticTime:
> __________________________________________________________________________
> type SyntheticTime struct {
> reqch chan interface{}
> donech chan int
> }
> func NewSyntheticTime() *SyntheticTime {
> s := &SyntheticTime{
> reqch: make(chan interface{}, 1),
> donech: make(chan int),
> }
> go s.loop()
> return s
> }
> type requestSleep struct {
> duration int64
> resp chan int
> }
> type requestNow struct {
> resp chan int64
> }
> type scheduledToSleep struct {
> wake int64
> resp chan int
> }
> func (x *SyntheticTime) loop() {
> var now int64
> var sleepers sleeperQueue
> ForLoop:
> for {
> YieldUntilAllOtherBlock()
> var req interface{}
> select {
> case req = <-x.reqch:
> default:
> }
> if req != nil {
> switch t := req.(type) {
> case requestSleep:
> sleepers.Add(&scheduledToSleep{ wake: now + t.duration, resp: t.resp })
> case requestNow:
> t.resp <- now
> default:
> panic("unknown request")
> }
> continue ForLoop
> }
> nextToWake := sleepers.DeleteMin()
> if nextToWake == nil {
> break
> }
> now = nextToWake.wake
> close(nextToWake.resp)
> }
> }
On Tuesday, 1 May 2012 11:39:14 UTC+8, Russ Cox wrote:
> I don't believe that you can implement this without > hacking the runtime package, and I think that's just fine.
Could you just have YieldUntilAllOtherBlock call LockOSThread, and then wait until all other threads are in the S(leep) state? This picks up blocking on channels, but won't help for racy things like blocking I/O, which might unblock soon after you check the state.
On Tuesday, 1 May 2012 15:29:50 UTC+8, Andrew Wilkins wrote:
> Could you just have YieldUntilAllOtherBlock call LockOSThread, > and then wait until all other threads are in the S(leep) state? This > picks up blocking on channels, but won't help for racy things > like blocking I/O, which might unblock soon after you check the > state.
On second thought, this won't necessarily work for channels either. A thread yet to be checked could easily wake a thread already found to be sleeping. Perhaps you could do two passes, checking context switches to see if they woke up and went back to sleep? But I'd better not think about this any more until I get some sleep.
It seems that the two main alternatives are:
(a) changing the runtime a bit
(b) transforming the source of the program that needs to run in
synthetic time
So, I decided to go with (b). I am writing a source-to-source
transformer that slightly rewrites go, chan and time operations.
I will put the result up on github when ready.
On 1 May 2012 03:29, Andrew Wilkins <axw...@gmail.com> wrote:
> On Tuesday, 1 May 2012 11:39:14 UTC+8, Russ Cox wrote:
>> I don't believe that you can implement this without
>> hacking the runtime package, and I think that's just fine.
> Could you just have YieldUntilAllOtherBlock call LockOSThread,
> and then wait until all other threads are in the S(leep) state? This
> picks up blocking on channels, but won't help for racy things
> like blocking I/O, which might unblock soon after you check the
> state.
> So, I decided to go with (b). I am writing a source-to-source
> transformer that slightly rewrites go, chan and time operations.
> I will put the result up on github when ready.
> On 1 May 2012 03:29, Andrew Wilkins <axw...@gmail.com> wrote:
> > On Tuesday, 1 May 2012 11:39:14 UTC+8, Russ Cox wrote:
> >> I don't believe that you can implement this without
> >> hacking the runtime package, and I think that's just fine.
> > Could you just have YieldUntilAllOtherBlock call LockOSThread,
> > and then wait until all other threads are in the S(leep) state? This
> > picks up blocking on channels, but won't help for racy things
> > like blocking I/O, which might unblock soon after you check the
> > state.
On Tue, May 1, 2012 at 8:34 AM, Petar Maymounkov <pet...@gmail.com> wrote:
> (a) changing the runtime a bit
> (b) transforming the source of the program that needs to run in
> synthetic time
For what it's worth, I think (a) is significantly easier than (b).
Here is a patch to runtime:
Note stopped; // one g can set waitstop and wait here for m's to stop
+ + G *idler;
};
// The atomic word in sched is an atomic uint32 that
@@ -613,6 +615,11 @@
if((scvg == nil && runtime·sched.grunning == 0) ||
(scvg != nil && runtime·sched.grunning == 1 && runtime·sched.gwait == 0 &&
(scvg->status == Grunning || scvg->status == Gsyscall))) {
+ if(runtime·sched.idler != nil) {
+ readylocked(runtime·sched.idler);
+ runtime·sched.idler = nil;
+ goto top;
+ }
runtime·throw("all goroutines are asleep - deadlock!");
}
@@ -1612,6 +1619,18 @@
runtime·gosched();
}
+void
+runtime·WaitIdle(void)
+{
+ schedlock();
+ if(runtime·sched.idler != nil)
+ runtime·throw("runtime: multiple goroutines using WaitIdle");
+ runtime·sched.idler = g;
+ g->status = Gwaiting;
+ schedunlock();
+ runtime·gosched();
+}
+
// Implementation of runtime.GOMAXPROCS.
// delete when scheduler is stronger
int32
and here is a program to test it:
package main
import "runtime"
func main() {
go idler()
go timer()
go fizz()
go buzz()
sleep(20)
}
func fizz() {
for t := 0; t < 100; t += 3 {
sleep(t)
println(t, "fizz")
}
}
func buzz() {
for t := 0; t < 100; t += 5 {
sleep(t)
println(t, "buzz")
}
}
var idle = make(chan bool)
var sleepc = make(chan request)
type request struct {
t int
c chan int
}
func sleep(t int) int {
c := make(chan int, 1)
sleepc <- request{t, c}
return <-c
}
func idler() {
for {
runtime.WaitIdle()
idle <- true
}
}
func timer() {
now := 0
var reqs []request
for {
select {
case <-idle:
min := -1
for _, req := range reqs {
if min < 0 || req.t < min {
min = req.t
}
}
if min < 0 {
panic("deadlock")
}
if min <= now {
panic("broken")
}
now = min
w := reqs[:0]
for _, req := range reqs {
if req.t <= now {
req.c <- now
} else {
w = append(w, req)
}
}
reqs = w
case req := <-sleepc:
if req.t <= now {
req.c <- now
break
}
reqs = append(reqs, req)
}
}
> On Tue, May 1, 2012 at 8:34 AM, Petar Maymounkov <pet...@gmail.com> wrote:
>> (a) changing the runtime a bit
>> (b) transforming the source of the program that needs to run in
>> synthetic time
> For what it's worth, I think (a) is significantly easier than (b).
> Here is a patch to runtime:
> func timer() {
> now := 0
> var reqs []request
> for {
> select {
> case <-idle:
> min := -1
> for _, req := range reqs {
> if min < 0 || req.t < min {
> min = req.t
> }
> }
> if min < 0 {
> panic("deadlock")
> }
> if min <= now {
> panic("broken")
> }
> now = min
> w := reqs[:0]
> for _, req := range reqs {
> if req.t <= now {
> req.c <- now
> } else {
> w = append(w, req)
> }
> }
> reqs = w
> case req := <-sleepc:
> if req.t <= now {
> req.c <- now
> break
> }
> reqs = append(reqs, req)
> }
> }
> }
