how do I handle a million timers ...
Irvine Dude
Return-Path: <ne...@google.com>
Received: from horus.isnic.is (ro...@horus.isnic.is [193.4.58.12])
by ftp.cse.ucsc.edu (8.12.2/8.12.2) with ESMTP id gA73uVgw003972
for <o...@ftp.cse.ucsc.edu>; Wed, 6 Nov 2002 19:56:32 -0800 (PST)
Received: from proxy.google.com (proxy.google.com [216.239.35.5])
by horus.isnic.is (8.12.3/8.12.3/isnic) with ESMTP id gA73uTZf056520
for <comp-os-...@moderators.isc.org>; Thu, 7 Nov 2002 03:56:30 GMT
(envelope-from ne...@google.com)
Received: from sjmm36.sj.google.com (sjmm36.prod.google.com [10.6.39.36])
by proxy.google.com (8.12.3/8.12.3) with ESMTP id gA73uKru010002
for <comp-os-...@moderators.isc.org>; Wed, 6 Nov 2002 19:56:24 -0800
Received: (from news@localhost)
by sjmm36.sj.google.com (8.12.6/8.12.3) id gA73uJI8029027
for comp-os-...@moderators.isc.org; Wed, 6 Nov 2002 19:56:19 -0800
To: comp-os-...@moderators.isc.org
Path: not-for-mail
From: irvin...@yahoo.com (Irvine Dude)
Newsgroups: comp.os.research
Subject: how do I handle a million timers ...
Date: 6 Nov 2002 19:56:19 -0800
Organization: http://groups.google.com/
Lines: 23
Message-ID: <7d728651.02110...@posting.google.com>
NNTP-Posting-Host: 64.6.182.226
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1036641379 29026 127.0.0.1 (7 Nov 2002 03:56:19 GMT)
X-Complaints-To: groups...@google.com
NNTP-Posting-Date: 7 Nov 2002 03:56:19 GMT
Status: R
Content-Length: 1086
Hi! I am investigating ways in which over 1000000 timers can be
processed easily at user-level (running on top of say NetBSD or Linux
like operating systems). All of these timers are owned by a single
process. In certain situations, there could be multiple instances of
this million-timer process, but for now, we can assume that there is
only a single instance of the process running at any given point in
time.
I don't expect absolute accuracy. I would say about 10000 timers must
fire when they are told to fire. The rest can fire within +/- 2 units
of the specified timeout. NOTE: the smallest unit for timeout can be
in milli-seconds. The longest timeout we have would be about 180
minutes. The 10K "must-fire-at-specified-time" timers have millisecond
timeout specifications.
As always most timers would be recurring. A few would be one-shot.
I was wondering if any of you can point me to papers, implementations,
etc that already solve this problem. Also, is anyone currently
exploring this issue? If you are, would you be interested in sharing
what you have found?
Thanks!
Dick Wesseling
irvin...@yahoo.com (Irvine Dude) writes:
>
> Hi! I am investigating ways in which over 1000000 timers can be
> processed easily at user-level (running on top of say NetBSD or Linux
> like operating systems).
> ..
> I was wondering if any of you can point me to papers, implementations,
> etc that already solve this problem. Also, is anyone currently
> exploring this issue? If you are, would you be interested in sharing
> what you have found?
>
If you want to learn more about efficient implementation of timers - and
if you are going to use that many timers it better be efficient - you
should read George Varghese papers on timer wheels, the data structure
used in BSD OSes.
You can use a timer wheel to implement multiple timers at the user level
and a single timer at the OS level (1) that corresponds to the earliest
user level timer. Your signal handler - or whatever the OS uses for
timer events - can then scan (2) the wheel for the next lowest timer and
re-arm the OS timer.
(1) Assuming that the granularity of the OS timer is sufficient for your
needs.
(2) Varghese's algorithm assumes that the event rate of the wheel
equals the granularity of the clock, i.e. the next timer event is always
one timer unit in the future and can therefore be found in the current
slot of the least significant wheel. This is true for the BSD kernel,
but it may not be true for your application, in that case you may have
to scan multiple slots/wheels for the next timer. However, if you have
lots of short timers it seems reasonable to assume that the next timer
can be found in a small number of steps.