Die Bedeutung von Timer-Komponenten im Spielegeschäft und wie man sie implementiert

Timer ist eine relativ häufige Komponente. Was den Server betrifft, muss die Framework-Ebene Timer verwenden, um Sitzungen das Zeitlimit zu setzen, und die Anwendungsebene muss Timer verwenden, um einige zeitbezogene Geschäftslogiken zu verarbeiten. Für Unternehmen wie Spiele, die eine große Anzahl von Timern benötigen, ist eine einfache und effiziente Timer-Komponente unerlässlich.

Die Implementierung der Timer-Komponente kann in zwei Teile unterteilt werden:

Der erste Teil ist relativ einfach und es gibt verschiedene Implementierungsmethoden, die jedoch im Wesentlichen mit der Sprache zusammenhängen und daher nicht im Mittelpunkt dieses Artikels stehen. Das sogenannte konkrete Konzept scheint sich auf die Art und Weise zu beziehen, wie Benutzer es verwenden.

[Artikelvorteile] Der Herausgeber hat einige meiner Meinung nach bessere Lernbücher und Videomaterialien in die Gruppendatei hochgeladen. Wenn Sie sie benötigen, können Sie der Gruppe [977878001] beitreten, um sie zu erhalten! ! ! Kommt mit einem zusätzlichen Kernel-Informationspaket im Wert von 699 (einschließlich Video-Tutorials, E-Books, praktischen Projekten und Codes)

Kernel-Informationen-Direktzug: Lernroute zur Linux-Kernel-Quellcode-Technologie + Video-Tutorial-Code-Informationen

Expresszug lernen (kostenlose Registrierung im Tencent Classroom): Linux-Kernel-Quellcode/Videospeicheroptimierung/Dateisystem/Prozessverwaltung/Gerätetreiber/Netzwerkvertragsstapel

Der zweite Teil erfordert tatsächlich mehr Code als der erste Teil und die Implementierungsmethoden sind sehr begrenzt.

Der Zweck dieser Modelle besteht darin, dass sie einfach sind. Finden Sie einen Absolventen, der Datenstrukturen studiert hat, und es wird keine Fehler geben. Die zeitliche Komplexität von add beträgt n(lgn) und die zeitliche Komplexität von timeout beträgt ebenfalls n(lgn).

Angenommen, unser Geschäftssystem steht vor einer solchen Anforderung: Es muss in kurzer Zeit eine große Anzahl von Timern registriert werden, die in kurzer Zeit ablaufen. Tatsächlich ist die Implementierung des minimalen Heaps etwas peinlich.

Im folgenden Text stellt Xiaoxiao vor, wie wir einen Timer im Linux-Kernel-Stil in der Anwendungsschicht implementieren. Die Sprache ist beispielsweise C#.

Um einen Leistungsvergleich durchzuführen, müssen wir zunächst einen Timer-Manager basierend auf dem minimalen Heap implementieren. Die Schnittstelle des minimalen Heaps lautet wie folgt: Linux-Anwendungs-Timer Die spezifische Implementierung ist nicht verfügbar, obwohl sie die grundlegendste ist Datenstruktur.

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
{
// ...
}

Danach folgt die Manager-Implementierung des Timers im Linux-Kernel-Stil. Zunächst gibt es eine Designprämisse:

Wir müssen Tick verwenden, um die Untergrenze der Zeitgenauigkeit des gesamten Systems zu definieren. Bei Spielen ist beispielsweise eine Genauigkeit unter 10 ms nicht erforderlich, sodass wir die Tick-Breite auf 10 ms festlegen können. Mit anderen Worten: Beim WaitFor(8ms), der zuerst auflegt, und beim WaitFor(5ms), der später auflegt, kann es sein, dass zuerst das Zeitlimit überschritten wird. Ein Tick beträgt 10 ms. Die Zeitgranularität, die ein solcher 32-Bit-Tick ausdrücken kann, beträgt fast 500 Tage eingebettetes Linux-Training, was weitaus länger ist als die Zeit einer Servergruppe ohne Neustart.

虽然这些定时器实现，就是由于这个抉择，在面对之前提到的问题时，方才具有了更佳的性能表现。每次按照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固定为一千万的测试结果：

Die Schwankung des Beschleunigungsverhältnisses ist nicht sehr signifikant, und wenn die Sekunde weiter abnimmt, wird das Beschleunigungsverhältnis des Linux-Kernel-Timers aufgrund der Erhöhung der Schaltfrequenz tatsächlich allmählich ansteigen.

Sekunde ist auf 1000 festgelegt:

Ähnlich wie bei der Schlussfolgerung aus dem ersten Test ist der Vorteil gegenüber dem Minimum-Heap-Timer umso größer, je höher der Anteil der Timer innerhalb von 256 Ticks ist.

Abschließendes Fazit: Die Vorteile des Linux-Kernel-Timers im Vergleich zum Minimum-Heap-Timer sind immer noch sehr groß. In den meisten Fällen ist die Leistung mehr als doppelt so hoch, und es wird dringend empfohlen, ihn zu verwenden.

Dieses Mal wird der Code auf Github platziertLinux-Anwendungs-Timer, und da es keine Möglichkeit gibt, den Link zur Linux-Software in den Artikel zum Abonnementkonto einzufügen, solange das Backend eine Nachricht „Timer“ an Novel Jun sendet, Auf den Github-Link wird manuell geantwortet. Dieses Projekt enthält nicht nur einen Timer-Implementierungscode im Linux-Stil in Industriequalität, sondern auch eine Reihe von Coroutinen im Unity3D-Stil, die auf diesem von Xiaoxiaojun implementierten Timer basieren.

--Kernel Technology English Network – Richten Sie das maßgeblichste Kernel-Technologie-Austausch- und Sharing-Gipfeltreffen in der Provinz ein

Ursprüngliche Adresse: Verständnis der Timer-Implementierung im Linux-Kernel-Stil – Betriebssystem – Kernel Technology English Network – Einrichtung des maßgeblichsten Kernel-Technologie-Austausch- und Sharing-Gipfels in der Provinz (Urheberrecht liegt beim ursprünglichen Autor, Verletzung und Löschung)

Das obige ist der detaillierte Inhalt vonDie Bedeutung von Timer-Komponenten im Spielegeschäft und wie man sie implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!