1024programmer Java About go:26-GolangGo concurrent programming timer timer

About go:26-GolangGo concurrent programming timer timer

Timers allow us to perform a certain task a certain amount of time in advance, or perform a certain task periodically at a certain time. The Linux system itself also has timer capabilities. Is the timer implemented in Go language based on system calls? In addition, isn’t the Go language multi-coroutine? When the timer is triggered, which coroutine performs the work? Create a working coroutine?

Basic operations

 Go language time package provides time/timer related APIs, such as obtaining the current system time (can reach nanosecond level), coroutine sleeping for a specified time, executing a certain task at a specified time in advance, and periodically at a certain time To perform a certain task, etc., the operations are as follows:

package main

 import (
     "fmt"
     "time"
 )

 func main() {
     //nanosecond time stamp
     t := time.Now().UnixNano()
     fmt.Println(t) //1652510180050345000
     //Second time stamp
     t = time.Now().Unix()
     fmt.Println(t) //1652510180

     //Format display time
     fmt.Println(time.Now().Format("2006-01-02 15:04:05")) //2022-05-14 14:36:20

     //Execute function after one second
     time.AfterFunc(time.Second, func() {
         fmt.Println(time.Now().Format("2006-01-02 15:04:05"))
     })

     // Trigger regularly with one second as a period
     ticker := time.NewTicker(time.Second)
     go func() {
         for {
             <- ticker.C //When the time is triggered, the pipe is readable
             fmt.Println(time.Now().Format("2006-01-02 15:04:05"))
         }
     }()

     //The coroutine sleeps for 3 seconds
     time.Sleep(10 * time.Second)
 }

Note that the formatted time displays the time year, month, day, hour, minute and second, using “2006-01-02 15:04:05”, and the Format method uses other formats such as “2022-05- 14 14:36:20″Can it? It stands to reason that the format of the two time strings is the same, but the values ​​are different, and the effect should be no different. Write a small program to test it, and you will find that the consequences are a bit strange:

package main

 import (
     "fmt"
     "time"
 )

 func main() {
     //Format display time
     fmt.Println(time.Now().Format("2022-05-14 14:36:20"))
     //Input: 141414-02-540 540:26:140
 }

 What is this? Why is it not showing the abnormal year, month, day, hour, minute and second? This requires studying the Go language Format method and supporting format marks. For example, some other languages ​​use Y to represent the year, M to represent the month, etc. The year, month, day and other identifiers defined by Go language are as follows:

const (
     stdZeroMonth // "01"
     stdZeroDay // "02"
     stdHour = iota + stdNeedClock // "15"
     stdZeroMinute // "04"
     stdZeroSecond // "05"
     stdLOngYear= iota + stdNeedDate // "2006"

     //Remaining identification definitions are omitted
 )

You see, “2006”, “01”, etc. are the time format identifiers defined by the Go language, so “2006-01-02 15:04:05& #8243; The ability to display the year, month, day, hour, minute and second is abnormal, and other results such as “2022-05-14 14:36:20” are somewhat unexpected. Of course, many other time format identifiers are omitted here, which are defined in the time/format.go file. Interested readers can study them by themselves.

 Looking back at the program below, time.AfterFunc can execute the function at a specified time, time.NewTicker can trigger the time at a certain time period, and time.Sleep can make the coroutine sleep for a certain period of time (resume the scheduling of the coroutine after expiration) , how to achieve this? You must know that timers may be used extensively in my project. How can the Go language trigger timed events at the correct time? In addition, time.AfterFunc, when executing the function, which coroutine is executed? Add a timer coroutine?

Implementation principle-heap

How can the Go language trigger timed events at the exact time? This means that the efficiency of adding, deleting, modifying, and checking timers must be high. Otherwise, would it be necessary to traverse all timers every time to determine which ones should be triggered? What if all timers are protected in order? You only need to search for the first timer, trigger it if it expires, and continue searching; if it has not expired, there is no need to continue searching, because the previous expiration time must be greater than the expiration time of the first timer. However, in order to maintain order, the efficiency of adding timers, modifying timers, and deleting timers is too low.

 It needs to have a certain orderliness, and the performance of addition, deletion, modification and query should be high. What data structure is suitable? There is a data structure called a heap (max heap, min heap). Take the min heap as an example. It is essentially a complete binary tree. It just requires that the value of any node is smaller than the value of the two left and right child nodes, so the root node The value must be the smallest. In this way, if the timer applies the minimum heap, it only needs to determine whether the root node has expired. If it expires, the root node will be triggered and deleted. During the deletion process, it is also necessary to ensure that the remaining nodes still meet the conditions of the minimum heap; in this way , the time complexity of obtaining the next recently expired timer is still O(1). So, what is the minimum heap, node deletion and added time complexity? It is also relatively low, O(logn).

 General binary tree nodes usually require left and rightht pointer, and the heap is a complete binary tree, which can be implemented based on arrays. Why? Because the indexes of parent and child nodes are related, as shown below:

 When inserting a node into the heap, it is usually added to the beginning of the array and then compared with the parent node. If it meets the definition of the heap, it is completed; otherwise, it is replaced with the parent node. Continue to compare and replace until the root node, this process is called floating. A complete binary tree with N nodes has a height of logn, which means that the replacement needs to be performed at most logn times, that is, the insertion time complexity of the heap is O(logn).

 When the heap deletes the root node, it usually replaces the root node and the last node first, and then directly deletes the last node (that is, the root node); at this time, the root node may not meet the definition of the heap, so it needs to be replaced with the left and right nodes. Compare two child nodes. Continue comparing and replacing until the last node, this process is called sinking. The time complexity of deletion is also O(logn). The deletion process logic is as follows:

 Generally, the heap is a complete binary tree, but the Go language uses a quadtree. Why? The tree is lower and the technical complexity is lower. Combined with the insertion and deletion logic of the heap we introduced, let’s take a look at the insertion and floating logic of the Go language quad heap:

func siftupTimer(t []*timer, i int) int {
    
     tmp := t[i]
     for i > 0 {
         //Quadtree, the parent node index is (i - 1) / 4
         p := (i - 1) / 4 // parent
         if when >= t[p].when { //The parent node is less than the following nodes, break
             break
         }
         t[i] = t[p] //replacement
         i = p
     }
     if tmp != t[i] { //replacement
         t[i] = tmp
     }
     return i
 }

 //Add timer
 func doaddtimer(pp *p, t *timer) {
     i := len(pp.timers)
     pp.timers = append(pp.timers, t)
     siftupTimer(pp.timers, i)
 
      //If it is the root node, record the expiration time (minimum)
     if t == pp.timers[0] {
         atomic.Store64(&pp.timer0When, uint64(t.when))
     }
 }

 The deletion and sinking logic of the Go language quad heap is very similar, so I won’t go into details here. You can refer to the runtime/time.go file and the two functions dodeltimer0 andsiftdownTimer.

 In addition, you can see that constructing timer represents a timer, including the timer’s expiration time, execution cycle, execution method, etc., which are defined as follows:

type timer struct {
     // Timer wakes up at when, and then at when+period, ... (period > 0 only)
     when int64
     period int64

     //Execution method + parameters
     f func(any, uintptr)
     arg any
     seq uintptr
 }

Think about it, the Go language is a multi-thread + multi-coroutine program. What if multiple coroutines add timers concurrently? If there is only one timer heap globally, does every operation need to be locked? This is how the lower version of the Go language is implemented. At first, each P protected a timer heap, which can be seen from the doaddtimer function. The P bound to the thread M in the future was passed in, and the timer was also added to the timer heap of the P. Take a look at the timer related fields defined by the P structure:

type p struct {
     //Timer heap
     timers[]*timer

     // The when field of the first entry on the timer heap.
     // This is updated using atomic functions.
     // This is 0 if the timer heap is empty.
     //Expiration time of the timer heap root node (minimum)
     timer0When uint64
 }

 The first thing readers should pay attention to is that the time package defines many timer-related functions, but the specific implementation of these functions is often in the runtime package, such as

func Sleep(d Duration) //The implementation function is timeSleep
 func startTimer(*runtimeTimer) //time.NewTicker, time.After, etc. are all timers added based on the startTimer function
 func stopTimer(*runtimeTimer) bool
 func resetTimer(*runtimeTimer, int64) bool //timeSleep is implemented based on resetTimer

 You can take a brief look at the implementation of the time.AfterFunc function:

func AfterFunc(d Duration, f func()) *Timer {
     t := &Timer{
         r: runtimeTimer{
             when: when(d),
             f: goFunc, //Start a coroutine to execute function f
             arg: f,
         },
     }
     startTimer(&t.r)
     return t
 }

Timer and scheduler

 Each P protects a timer quad heap, so when does the Go language detect whether the timer needs to expire? This must have nothing to do with the scheduler:

func schedule() {
     //Detect timer and execute
     checkTimers(pp, 0)

     //Find executable coroutines
 }

 func checkTimers(pp *p, now int64) (rnow, pollUntil int64, ran bool) {
     //The most recently expired timer
     next := int64(atomic.Load64(&pp.timer0When))
     if next == 0 {
         // No timers to run or adjust.
         return now, 0, false
     }
     if now == 0 {
         now = nanotime()
     }
     //The first timer has not expired, return
     if now  0 {
         adjusttimers(pp, now)
         for len(pp.timers) > 0 {
            
             //Run the timer (get the first timer, execute it if it expires, otherwise return the time difference)
             if tw := runtimer(pp, now); tw != 0 {
                 //The first timer has not expired, complete the loop
                 break
             }
             ran = true
         }
     }
 }
 

 It is now clear that when the scheduler is looking for runnable coroutines, it first checks whether the timer has expired through checkTimers and executes it. In other words, the timer function f is executed in the scheduling stack; moreover, if a coroutine runs for a long time (if it is not preempted), it may also cause the timer to be triggered delayed.

sporadic time

 Finally, let’s think about another question. The Go language can even obtain time stamps accurately to the nanosecond level. Logically speaking, obtaining time usually requires system calls, and system calls will lead to low performance of the program. So how does the Go language achieve high-performance acquisition of system time?

 There is a concept that needs to be understood here, Linux VDSO (virtual dynamic shared object), which is to optimize the frequent system calls of user programs and change system calls to user-mode function calls. Gettimeofday is one of them.

 For an introduction to VDSO, please refer to the article: https://zhuanlan.zhihu.com/p/…

Summary

 This article mainly introduces the basic application and implementation principles of timers in Go language. The heap (maximum heap/minimum heap) has many usage scenarios, such as timers, priority queues, etc. The user program may add a lot of scheduled work, and the scheduler will detect whether any scheduled work has expired before scheduling the coroutine, and if so, execute the scheduled work.

timer(pp, now); tw != 0 {
//The first timer has not expired, complete the loop
break
}
ran = true
}
}
}

 It is now clear that when the scheduler is looking for runnable coroutines, it first checks whether the timer has expired through checkTimers and executes it. In other words, the timer function f is executed in the scheduling stack; moreover, if a coroutine runs for a long time (if it is not preempted), it may also cause the timer to be triggered delayed.

sporadic time

 Finally, let’s think about another question. The Go language can even obtain time stamps accurately to the nanosecond level. Logically speaking, obtaining time usually requires system calls, and system calls will lead to low performance of the program. So how does the Go language achieve high-performance acquisition of system time?

 There is a concept that needs to be understood here, Linux VDSO (virtual dynamic shared object), which is to optimize the frequent system calls of user programs and change system calls to user-mode function calls. Gettimeofday is one of them.

 For an introduction to VDSO, please refer to the article: https://zhuanlan.zhihu.com/p/…

Summary

 This article mainly introduces the basic application and implementation principles of timers in Go language. The heap (maximum heap/minimum heap) has many usage scenarios, such as timers, priority queues, etc. The user program may add a lot of scheduled work, and the scheduler will detect whether any scheduled work has expired before scheduling the coroutine, and if so, execute the scheduled work.

This article is from the internet and does not represent1024programmerPosition, please indicate the source when reprinting:https://www.1024programmer.com/754390

author: admin

Previous article
Next article

Leave a Reply

Your email address will not be published. Required fields are marked *

Contact Us

Contact us

181-3619-1160

Online consultation: QQ交谈

E-mail: [email protected]

Working hours: Monday to Friday, 9:00-17:30, holidays off

Follow wechat
Scan wechat and follow us

Scan wechat and follow us

Follow Weibo
Back to top
首页
微信
电话
搜索