Shulou(Shulou.com)05/31 Report--

This article mainly explains "what is the internal implementation principle of Go timer". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is the internal implementation principle of Go timer"?

Preface

In this section, we focus on how the system collaboration process manages these fixers, including the following issues:

What data structure does the timer use to store? How does a timer trigger an event? How do timers be added to the system collaboration? How do timers be removed from system collaborators?

Timer stores timer data structure

Timer and Ticker data structures are exactly the same except for their names, and both contain a member of type runtimeTimer, which is the object maintained by the system co-program. The runtimeTimer type is the name of the time package, and in the runtime package, this type is called timer.

The timer data structure is as follows:

Type timer struct {tb * timersBucket / / the bucket the timer lives in / / address where the current timer is stored in the system timer heap I int / / heap index / / the current timer is stored in the system timer heap subscript when int64 / / current timer next trigger time period int64 / / current timer cycle trigger interval (in the case of Timer, the interval is 0 For non-repetitive triggering) f func (interface {}, uintptr) / / function arg interface {} / / function passed when timer is triggered-parameter passed by function when seq uintptr / / timer is triggered (this parameter is only used in network transceiver scenarios)}

TimersBucket is the container where the system cooperates to store timer, in which there is a slice to store timer, and I is the subscript of the slice where timer is located.

TimersBucket data structure

Let's look at the timersBucket data structure:

Type timersBucket struct {lock mutexgp * g / / event handling protocol created bool / / whether the event handling protocol has been created, defaults to false, and is set to true sleeping bool / / event handling protocol (gp) when the first timer is added. (if there is a timer in t, then gp will go to sleep before the trigger time is reached.) whether rescheduling bool / / event handling protocol (gp) has been paused (if all timers in t have been deleted Then gp will pause) sleepUntil int64 / / event processing co-program sleep time waitnote note / event processing co-program sleep event (accordingly wake up co-program) t [] * timer / / timer slice}

"Bucket" translates into Chinese to mean "bucket". As the name implies, TimersBucket means a container for storing timer.

Lock: mutex, which is needed when timer is added or deleted; gp: event handling protocol, which is what we call a system protocol, which is generated when the Timer or Ticker is first created; create: a status value indicating whether the system protocol is created; sleeping: whether the system protocol is asleep; rescheduling: whether the system protocol has been paused SleepUntil: the system cooperatively sleeps to a specified time (if there is a new scheduled task, it may wake up in advance); waitnote: the notification used when waking up in advance; t: save the slice of timer, and when NewTimer () or NewTicker () is called, a new timer will be saved in this slice.

As you can see here, the system co-program is created when the timer is first created, which is stored in the slice, and the system co-program is responsible for timing and maintaining the slice.

Storage topology

Taking Ticker as an example, let's review the relationship between Ticker, timer, and timersBucket. Assuming that we have created three Ticker, the relationship between them is as follows:

When a user creates a Ticker, a timer is generated, which points to a pointer to the timersBucket,timersBucket record timer.

TimersBucket array

Through the timersBucket data structure, we can see that the system co-program is responsible for timing and maintaining multiple timer, and a timersBucket contains a system co-program.

When there are too many timers in the system, a system co-program may not be able to keep up with its processing capacity, so Go actually provides multiple timersBucket when it is implemented, that is, there are multiple system co-programs to handle timers.

Ideally, GOMAXPROCS timersBucket should be reserved to make full use of CPU resources, but need to be dynamically allocated according to the actual environment. For simplicity, Go reserves 64 timersBucket in its implementation, which is sufficient for most scenarios.

Whenever the co-program creates a timer, the ProcessID%64 to which the co-program belongs is used to calculate the timersBucket stored in the timer.

When the following three coprograms create timers, the timers are distributed as shown in the following figure:

For the convenience of description, the three cooperators in the above figure are all distributed in three Process.

In general, timers created by co-programs of the same Process are distributed in the same timersBucket, and only when the GOMAXPROCS is greater than 64 will multiple Process be distributed in the same timersBucket.

Timer operation mechanism

After looking at the data structure above, you can see how timer is stored. Now begin to explore the internal operation mechanism of the timer.

Create a timer

Reviewing the timer creation process, creating a Timer or Ticker is actually a two-step process:

Create a pipe create a timer and start it. (note that this timer is not a Timer, but a timer managed by the system coordinator. )

The section on creating pipes has been described earlier, and here we focus on the startup part of timer.

First of all, each timer must belong to a timersBucket, so the first step is to select a timersBucket. The algorithm chosen is very simple. The length of the Processor ID and timersBucket array to which the current protocol belongs is calculated, and the result is the subscript of the timersBucket array.

Const timersLen = 64 var timers [timersLen] struct {/ / timersBucket array with a length of 64 timersBucket} func (t * timer) assignBucket () * timersBucket {id: = uint8 (getg (). M.p.ptr (). Id)% timersLen / / Processor ID is modeled with the array length to get the subscript t.tb = & timers [id] .timersBucket return t.tb}

At this point, the first step is to select a timersBucket for the current timer.

Second, each timer must be added to the timersBucket. As we know earlier, the pointer to the timer is stored in the slice of the timersBucket, and the newly added timer is not stored in the order in which it was added, but a small heap that sorts the timer by the time it was triggered. Then the process of adding timer to timersBucket is actually a process of heap sorting, except that this sort refers to the process of heap adjustment after the addition of new elements.

The source code src/runtime/time.go:addtimerLocked () function is responsible for adding timer:

Func (tb * timersBucket) addtimerLocked (t * timer) bool {if t.when < 0 {t.when = 1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.