L'importance des composants de minuterie dans le secteur du jeu et comment les mettre en œuvre

La minuterie est un composant relativement courant. En ce qui concerne le serveur, le niveau framework doit utiliser des minuteries pour expirer les sessions, et le niveau application doit utiliser des minuteries pour gérer une logique métier liée au temps. Pour les entreprises telles que les jeux qui nécessitent un grand nombre de minuteries, un composant de minuterie simple et efficace est essentiel.

La mise en œuvre du composant timer peut être divisée en deux parties :

La première partie est relativement simple et il existe différentes méthodes de mise en œuvre, mais elles sont essentiellement liées au langage, ce n'est donc pas l'objet de cet article. Le concept dit concret semble faire référence à la manière dont les utilisateurs l’utilisent.

[Avantages de l'article] L'éditeur a mis en ligne des livres d'apprentissage et du matériel vidéo qui, à mon avis, sont meilleurs dans le fichier de groupe. Si vous en avez besoin, vous pouvez rejoindre le groupe [977878001] pour les obtenir ! ! ! Livré avec un package d'informations supplémentaires sur le noyau d'une valeur de 699 (comprenant des didacticiels vidéo, des livres électroniques, des projets pratiques et des codes)

Train direct d'informations sur le noyau : itinéraire d'apprentissage de la technologie du code source du noyau Linux + informations sur le code du didacticiel vidéo

Apprentissage du train express (inscription gratuite dans Tencent Classroom) : code source du noyau Linux/réglage de la mémoire vidéo/système de fichiers/gestion des processus/pilote de périphérique/pile de contrat réseau

La deuxième partie nécessite en réalité plus de code que la première partie, et les méthodes de mise en œuvre sont très limitées.

Le but de ces modèles est qu'ils sont simples. Trouvez un diplômé qui a étudié les structures de données pour les écrire, et il n'y aura pas de bugs. La complexité temporelle de l'ajout est n(lgn), et la complexité temporelle du délai d'attente est également n(lgn).

Cependant, supposons que notre système d'entreprise soit confronté à une telle demande : enregistrer un grand nombre de minuteries dans un court laps de temps qui expireront dans un court laps de temps. En fait, la mise en œuvre du tas minimum est un peu gênante.

Dans le texte ci-dessous, Xiaoxiao présentera comment nous implémentons un minuteur de style noyau Linux dans la couche application. Le langage est C# à titre d’exemple.

Pour comparer les performances, nous devons d'abord implémenter un gestionnaire de minuterie basé sur le tas minimum. L'interface du tas minimum est la suivante minuterie d'application Linux L'implémentation spécifique n'est pas disponible, bien qu'il s'agisse de la structure de données la plus basique.

public class PriorityQueue : IEnumerable
{
public PriorityQueue(IComparer comparer);
public void Push(T v);
public T Pop();
public T Top();
}

public interface ITimeManager
{
ITimer AddTimer(uint afterTick, OnTimerTimeout callback, params object[] userData);
FixedTick();
}

public class TrivialTimeManager : ITimeManager
{
// ...
}

Après cela, il y a l'implémentation du gestionnaire du minuteur de style noyau Linux. Il y a d’abord une prémisse de conception :

Nous devons utiliser tick pour définir la limite inférieure de précision temporelle de l'ensemble du système. Par exemple, pour les jeux, une précision inférieure à 10 ms ne nécessite aucune attention, nous pouvons donc définir la largeur de tick à 10 ms. En d'autres termes, le WaitFor (8 ms) qui raccroche en premier et le WaitFor (5 ms) qui raccroche plus tard peuvent être expirés en premier. Un tick dure 10 ms. La granularité temporelle qu'un tel tick de 32 bits peut exprimer est de près de 500 jours de formation Linux embarqué, ce qui est bien plus long que le temps d'un groupe de serveurs sans redémarrage.

虽然这些定时器实现，就是由于这个抉择，在面对之前提到的问题时，方才具有了更佳的性能表现。每次按照tick领到timeout数组，直接dispatch，领到这个数组的时间是一个常数，而最小堆方式领到这个数组须要的时间是m*lgn。

因为空间有限，我们不可能做到每位即将timeout的tick都有对应的数组。考虑到虽然80%以上的timer的时间都不会超过2.55s，我们只针对前256个tick做这些优化举措即可。

那怎么处理注册的256tick以后的timer？我们可以把时间还比较长的timer置于更粗细度的数组中，等到还剩下的tick数大于256以后再把她们取下来重新整理一下数组能够搞定。

假如我们保证每一次tick都严格的做到：

保证这两点，就须要每位tick都对所有数组做一次整理。这样就得不偿失了，所以这儿有个trade-off，就是我通过一个表针(index)，来标记我当前处理的position，每过256tick是一个cycle，才进行一次整理。而整理的成本就通过分摊在256tick中，增加了实际上的单位时间成本。

概念比较具象，接出来贴一部份代码。

常量定义：

public const int TimeNearShift = 8;
public const int TimeNearNum = 1 << TimeNearShift;// 256
public const int TimeNearMask = TimeNearNum - 1;// 0x000000ff
public const int TimeLevelShift = 6;
public const int TimeLevelNum = 1 << TimeLevelShift;// 64
public const int TimeLevelMask = TimeLevelNum - 1;// 00 00 00 (0011 1111)

基础数据结构：

using TimerNodes = LinkedList;
private readonly TimerNodes[TimeNearNum] nearTimerNodes;
private readonly TimerNodes[4][TimeLevelNum] levelTimerNodes;

相当于是256+4*64个timer数组。

tick有32位，每一个tick只会timeout掉expire与index相同的timer。

循环不变式保证near表具有这样几个性质：

level表有4个，分别对应9到14bit，15到20bit，21到26bit，27到32bit。

因为原理都类似，我这儿拿9到14bit的表来说下循环不变式：

有了数据结构和循环不变式，前面的代码也就容易理解了。主要列一下AddTimer的逻辑和Shift逻辑。

private void AddTimerNode(TimerNode node)
{
var expire = node.ExpireTick;
if (expire < index)
{
throw new Exception();
}
// expire 与 index 的高24bit相同
if ((expire | TimeNearMask) == (index | TimeNearMask))
{
nearTimerNodes[expire & TimeNearMask].AddLast(node);
}
else
{
var shift = TimeNearShift;
for (int i = 0; i < 4; i++)
{
// expire 与 index 的高bit相同
var lowerMask = (1 <> shift)&TimeLevelMask].AddLast(node);
break;
}
shift += TimeLevelShift;
}
}
}

private void TimerShift()
{
// TODO index回绕到0的情况暂时不考虑
index++;
var ct = index;// mask0 : 8bit
// mask1 : 14bit
// mask2 : 20bit
// mask3 : 26bit
// mask4 : 32bit
var partialIndex = ct & TimeNearMask;
if (partialIndex != 0)
{
return;
}
ct >>= TimeNearShift;
for (int i = 0; i >= TimeLevelShift;
continue;
}
ReAddAll(levelTimerNodes[i], partialIndex);
break;
}
}

以上代码用c/c++重画后尝尝鲜味更佳。

实现大约就是这种了，接出来我们测一下究竟linux内核风格定时器比最小堆实现的定时器快了多少。

建立的测试用例和测试方式：

static IEnumerable BuildTestCases(uint first, uint second)
{
var rand = new Random();
for (int i = 0; i < first; i++)
{
yield return new TestCase()
{
Tick = (uint)rand.Next(256),
};
}
for (int i = 0; i < 4; i++)
{
var begin = 1U << (8 + 6*i);
var end = 1U << (14 + 6*i);
for (int j = 0; j < rand.Next((int)second * (4 - i)); j++)
{
yield return new TestCase()
{
Tick = (uint)rand.Next((int)(begin+end)/2),
};
}
}
}

{
var maxTick = cases.Max(c => c.Tick);
var results = new HashSet();
foreach (var c in cases)
{
TestCase c1 = c;
mgr.AddTimer(c.Tick, (timer, data) =>
{
if (mgr.FixedTicks == c1.Tick)
results.Add((uint) data[0]);
}, c.Id);
}
var begin = DateTime.Now;
for (int i = 0; i < maxTick+1; i++)
{
mgr.FixedTick();
}
var end = DateTime.Now;
}

建立测试用例时的参数first指大于等于256tick的timer数目，second是指小于256tick的timer数目。

first固定为一千万的测试结果：

La fluctuation du taux d'accélération n'est pas très significative, et si la seconde continue de diminuer, le taux d'accélération du timer du noyau Linux augmentera en fait progressivement en raison de l'augmentation de la fréquence de changement de vitesse.

La seconde est fixée à 1000 :

Semblable à l'inférence du premier test, plus la proportion de timers dans les 256 ticks est élevée, plus l'avantage par rapport au timer minimum du tas est grand.

Conclusion finale : les avantages du timer du noyau Linux par rapport au timer minimum du tas sont toujours très significatifs. Dans la plupart des cas, les performances sont plus de 2 fois, et il est fortement recommandé de l'utiliser.

Cette fois, le code est mis sur githubLinux application timer, et comme il n'y a aucun moyen de mettre le lien vers le logiciel Linux dans l'article du compte d'abonnement, tant que le backend envoie un message "timer" à Novel Jun, le lien github recevra une réponse manuelle. Ce projet contient non seulement un code d'implémentation de minuterie de style Linux de qualité industrielle, mais également un ensemble de coroutines de style Unity3D basées sur cette minuterie implémentée par Xiaoxiaojun.

--Kernel Technology English Network - Établir le sommet d'échange et de partage de technologie de noyau le plus faisant autorité dans la province

Adresse originale : Comprendre l'implémentation de la minuterie de style noyau Linux - système d'exploitation - Kernel Technology English Network - établissement du sommet d'échange et de partage de technologie de noyau le plus faisant autorité dans la province (le droit d'auteur appartient à l'auteur original, violation et suppression)

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!