Comment implémenter la roue temporelle en utilisant le langage Go

Dans le domaine de la programmation informatique, la roue temporelle est une structure de données couramment utilisée qui peut être utilisée pour mettre en œuvre des tâches liées au temps. En raison de son efficacité et de sa portabilité, la roue temporelle est largement utilisée dans des domaines tels que la planification de tâches planifiées, les retards réseau et la mise en cache expirée. Cet article explique comment implémenter une roue temporelle à l'aide du langage Go.

1. Aperçu de la roue du temps

La roue du temps est un tampon circulaire basé sur le concept de temps, qui peut être considéré comme un tampon circulaire d'une taille de m (puissance de 2). Chaque fois que la roue du temps tourne d'une unité, par exemple 1 milliseconde, le contenu pointé par tous les tampons change également. Dans la roue du temps, il y a de nombreuses marques, fentes, pointeurs, etc.

La fonction de la roue du temps est de mettre en œuvre la planification des tâches planifiées. Essentiellement, une tâche planifiée est une structure qui contient des informations telles que l'heure d'exécution de la tâche et la fonction d'exécution de la tâche. Nous pouvons accrocher ces tâches planifiées dans les emplacements correspondants de la roue du temps et effectuer la planification planifiée de la roue du temps.

2. Le langage Go implémente la roue temporelle

Nous utilisons le langage Go pour implémenter la roue temporelle, qui peut être implémentée via les trois structures suivantes :

type TimerTask struct {
    expires   int64            //任务的到期时间
    callback  func()          //任务需要执行的函数
}

type Timer struct {
    interval  int64            //时间轮转动的间隔
    slots     []*list.List    //所有的槽位
    curPos    int             //当前槽位指针
    tickCount int64           //时间轮当前tick
}

type Timewheel struct {
    timer     *Timer          //指向Timer结构体的指针
    quit      chan struct{}   //停止时间轮信号
    waitGroup sync.WaitGroup  //同步等待
}

Nous économisons le temps d'exécution de la tâche, la fonction d'exécution de la tâche et d'autres informations dans la structure TimerTask. Dans la structure Timer, l'intervalle de temps de rotation de la roue temporelle, la liste de tous les emplacements, le pointeur d'emplacement actuel et le nombre actuel de ticks sont enregistrés. Dans la structure Timewheel, le pointeur de la roue temporelle, le signal d'arrêt de la roue temporelle et l'attente de synchronisation sont stockés.

Le flux de travail de la roue du temps est le suivant :

1) Initialisez la structure de la minuterie et créez une liste de temps.

2) Utilisez la fonction addTimer pour ajouter la tâche planifiée spécifiée à l'emplacement.

3) Démarrez la roue du temps, et les tâches ajoutées au slot seront exécutées dans le tick correspondant en fonction du temps d'exécution spécifié.

Ci-dessous, nous expliquons en détail comment mettre en œuvre chaque étape.

2.1 Initialiser la structure du minuteur

Afin d'initialiser la roue du temps, nous devons créer une liste contenant m (multiples de deux) emplacements dans la structure du minuteur et accrocher toutes les tâches dans les emplacements correspondants. Afin d'implémenter une liste dans le langage Go, nous pouvons utiliser le type de liste chaînée fourni par le package conteneur/list. Cette liste chaînée prend en charge les opérations d'ajout et de suppression en temps O(1), ce qui est très approprié pour les roues temporelles.

type Timer struct {
    interval  int64
    slots     []*list.List
    curPos    int
    tickCount int64
}

func newTimer(interval int64, m int) *Timer {
    l := make([]*list.List, m)
    for i := 0; i < m; i++ {
        l[i] = list.New()
    }
    return &Timer{
        interval:  interval,
        slots:     l,
        curPos:    0,
        tickCount: 0,
    }
}

2.2 Ajouter des tâches planifiées

Nous utilisons la fonction addTimer pour ajouter des tâches planifiées. Cette fonction accepte une structure TimerTask en paramètre et l'ajoute au créneau horaire correspondant de la roue temporelle. Afin de garantir que la tâche planifiée peut être planifiée dans le bon créneau, nous devons calculer la position de la tâche en fonction du temps et ajouter la tâche à la liste des créneaux.

func (tw *TimerWheel) AddTimer(task *TimerTask) {
    if task.expires <= 0 {
        return
    }

    pos, round := tw.timer.getPosAndRound(task.expires)
    tw.timer.slots[pos].PushBack(task)
    task.position = &Element{
        round:       round,
        position:    pos,
        task:        task,
        nextElement: nil,
    }
}

2.3 Démarrez la roue du temps

Utilisez la fonction Démarrer pour démarrer la roue du temps. La fonction Start utilise une goroutine dans le processus en cours. La goroutine exécutera l'opération de tick de la roue temporelle à chaque fois. L'ensemble du processus de boucle est complété par l'instruction for-select. Dans le tick de chaque roue temporelle, nous pointons le tick actuel vers l'emplacement suivant et parcourons l'emplacement actuel, en exécutant toutes les tâches qui y sont enregistrées.

func (tw *TimerWheel) Start() {
    defer close(tw.quit)
    tw.timer.resetTickCount()

    ticker := time.NewTicker(time.Duration(tw.timer.interval) * time.Millisecond)
    defer ticker.Stop()

    for {
        select {
        case <-tw.quit:
            log.Println("time wheel is stop.")
            return
        case <-ticker.C:
            tw.timer.curPos = (tw.timer.curPos + 1) & (tw.timer.slotNum() - 1)
            tw.timer.tickCount++
            l := tw.timer.slots[tw.timer.curPos]
            tw.exec(l)
        }
    }
}

3. Résumé

Le langage Go est un langage de programmation rapide et efficace, très adapté à l'implémentation de roues temporelles. La planification des tâches dans les roues temporelles peut être facilement gérée à l'aide des packages de conteneurs de Go (tels que conteneur/heap et conteneur/list). Afin de rendre la roue temporelle plus flexible et fiable, différents types de tâches peuvent être classés en plusieurs niveaux, les tâches de faible priorité peuvent être planifiées et réessayées, et les tâches de haute priorité peuvent être rapidement planifiées via des files d'attente prioritaires. Bien entendu, au cours du processus de mise en œuvre, nous devons également prendre en compte des problèmes détaillés tels que la simultanéité des tâches et la gestion de la mémoire pour garantir le fonctionnement efficace de la roue temporelle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!