使用一个物理定时器模拟多个虚拟定时器

Question

我正在尝试使用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在他们的网络教科书中提到过

单个硬件定时器可用于模拟多个逻辑定时器的操作[Varghese 1997].

我发现了类似任务的以下提示

您可以使用单个物理计时器模拟多个虚拟计时器.基本思想是在一个到期时间内保留一系列虚拟定时器,物理定时器将在第一个虚拟定时器到期时关闭.

但是,我无法访问除RTT之外的任何时间变量,因为模拟器位于另一个抽象层上.在这种情况下,如何为单个数据包实现计时器？

Answer 1

您可以像在内核级别实现的那样执行此操作.您需要有一个"定时器"的链接列表,其中每个定时器相对于前一个定时器具有超时.它类似于:Timer1:从t0开始500 ms,Timer2:从t0开始400 ms,Timer3从t0开始1000 ms.

然后你将有一个链表,其中每个元素都有相对于前一个元素的超时,如下所示:

头戴式>定时器(400毫秒) - >的Timer1(100毫秒) - >定时器3(500毫秒)

每个元素都包含minimum:timerID,相对超时,绝对初始化时间(来自epoch的时间戳).您可以为每个计时器添加一个回调指针.

您使用唯一的计时器并将超时设置为列表中第一个元素的相对超时:400ms(Timer2)

超时后你将删除第一个元素,可能执行与Timer2相关的回调,理想情况下,这个回调是用另一个工作线程执行的.然后将新超时设置为下一个元素Timer1的相对超时:100ms.

现在,当你需要创建一个新的计时器,比如说在3000毫秒后,从t0开始300毫秒后,你需要将它插入导航链接计时器列表的正确位置.Timer4中的相对超时为2,300.这是通过(Timer2.RelativeTimeout - (now - Timer2.AbsoluteTimeout))计算并通过链表查找相应的位置,添加每个前一个元素的相对超时.您的链接列表将变为:

头戴式>定时器(400毫秒) - >的Timer1(100毫秒) - >定时器3(500毫秒) - >定时器4(2300)

这样,您可以使用一个物理计时器实现许多逻辑计时器.您的计时器创建和查找时间将为O(n),但您可以为插入性能添加各种改进.最重要的是定时器超时处理和更新是O(1).删除复杂度将是O(n)用于查找定时器和O(1)用于删除.

您必须在控制计时器的线程和插入或删除计时器的线程之间处理可能的竞争条件.在用户空间中实现此计时器的一种方法是使用条件变量和等待超时.