用一个物理定时器模拟多个虚拟定时器
Simulate Multiple Virtual Timers with one Physical Timer
我正在尝试使用 C 实现选择性重复协议以进行网络分配，但对如何为每个单独的数据包模拟计时器感到困惑。我只能访问一个计时器，并且只能调用如下所述的函数。
/* start timer at A or B (int), increment in time*/
extern void starttimer(int, double);
/* stop timer at A or B (int) */
extern void stoptimer(int);
Kurose 和 Ross 在他们的网络教科书中提到
A single hardware timer can be used to mimic the
operation of multiple logical timers [Varghese 1997].
而且我发现了类似的提示 assignment
You can simulate multiple virtual timers using a single physical timer. The basic idea is that you keep a chain of virtual timers ordered in their expiration time and the physical timer will go off at the first virtual timer expiration.
但是，除了 RTT 之外，我无法访问任何时间变量，因为模拟器位于另一抽象层上。在这种情况下，如何为单个数据包实施计时器？
您可以按照在内核级别实现的相同方式来执行此操作。您需要有一个 "timers" 的链接列表，其中每个计时器都有相对于前一个计时器的超时。它会是这样的：
Timer1：从 t0 起 500 ms，Timer2：从 t0 起 400 ms，Timer3 从 t0 起 1000 ms。
然后你将有一个链表，其中每个元素都有相对于前一个元素的超时，如下所示：
HEAD->Timer2(400ms)->Timer1(100ms)->Timer3(500ms)
每个元素包含最小值：timerID、相对超时、绝对初始化时间（来自纪元的时间戳）。您可以为每个计时器添加一个回调指针。
您使用唯一的计时器并将超时设置为列表中第一个元素的相对超时：400 毫秒（Timer2）
超时后您将删除第一个元素，可能会执行与 Timer2 相关的回调，理想情况下此回调由另一个工作线程执行。然后您将新的超时设置为下一个元素的相对超时，Timer1：100ms。
现在，当您需要创建一个新计时器时，比如在 3,000 毫秒时，从 t0 开始 300 毫秒后，您需要将它插入导航计时器链接列表的正确位置。 Timer4 中的相对超时将为 2,300。这是用 (Timer2.RelativeTimeout - (now - Timer2.AbsoluteTimeout)) 计算的，并通过链表找到相应的位置，添加每个先前元素的相对超时。您的链接列表将变为：
HEAD->Timer2(400ms)->Timer1(100ms)->Timer3(500ms)->Timer4(2,300)
通过这种方式，您可以使用一个物理计时器实现多个逻辑计时器。您的计时器创建和查找时间将为 O(n)，但您可以为插入性能添加各种改进。最重要的是定时器超时处理和更新是 O(1)。删除复杂度将是 O(n) 用于查找计时器和 O(1) 用于删除。
您必须注意控制计时器的线程与插入或删除计时器的线程之间可能存在的竞争条件。在用户 space 中实现此计时器的一种方法是使用条件变量和等待超时。
我正在尝试使用 C 实现选择性重复协议以进行网络分配，但对如何为每个单独的数据包模拟计时器感到困惑。我只能访问一个计时器，并且只能调用如下所述的函数。
/* start timer at A or B (int), increment in time*/
extern void starttimer(int, double);
/* stop timer at A or B (int) */
extern void stoptimer(int);
Kurose 和 Ross 在他们的网络教科书中提到
A single hardware timer can be used to mimic the operation of multiple logical timers [Varghese 1997].
而且我发现了类似的提示 assignment
You can simulate multiple virtual timers using a single physical timer. The basic idea is that you keep a chain of virtual timers ordered in their expiration time and the physical timer will go off at the first virtual timer expiration.
但是，除了 RTT 之外，我无法访问任何时间变量，因为模拟器位于另一抽象层上。在这种情况下，如何为单个数据包实施计时器？
您可以按照在内核级别实现的相同方式来执行此操作。您需要有一个 "timers" 的链接列表，其中每个计时器都有相对于前一个计时器的超时。它会是这样的： Timer1：从 t0 起 500 ms，Timer2：从 t0 起 400 ms，Timer3 从 t0 起 1000 ms。
然后你将有一个链表，其中每个元素都有相对于前一个元素的超时，如下所示：
HEAD->Timer2(400ms)->Timer1(100ms)->Timer3(500ms)
每个元素包含最小值：timerID、相对超时、绝对初始化时间（来自纪元的时间戳）。您可以为每个计时器添加一个回调指针。
您使用唯一的计时器并将超时设置为列表中第一个元素的相对超时：400 毫秒（Timer2）
超时后您将删除第一个元素，可能会执行与 Timer2 相关的回调，理想情况下此回调由另一个工作线程执行。然后您将新的超时设置为下一个元素的相对超时，Timer1：100ms。
现在，当您需要创建一个新计时器时，比如在 3,000 毫秒时，从 t0 开始 300 毫秒后，您需要将它插入导航计时器链接列表的正确位置。 Timer4 中的相对超时将为 2,300。这是用 (Timer2.RelativeTimeout - (now - Timer2.AbsoluteTimeout)) 计算的，并通过链表找到相应的位置，添加每个先前元素的相对超时。您的链接列表将变为：
HEAD->Timer2(400ms)->Timer1(100ms)->Timer3(500ms)->Timer4(2,300)
通过这种方式，您可以使用一个物理计时器实现多个逻辑计时器。您的计时器创建和查找时间将为 O(n)，但您可以为插入性能添加各种改进。最重要的是定时器超时处理和更新是 O(1)。删除复杂度将是 O(n) 用于查找计时器和 O(1) 用于删除。
您必须注意控制计时器的线程与插入或删除计时器的线程之间可能存在的竞争条件。在用户 space 中实现此计时器的一种方法是使用条件变量和等待超时。