Browse Prior Art Database

Efficient Computer Timer Request Queue Using a Hash Table

IP.com Disclosure Number: IPCOM000103229D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 1 page(s) / 48K

Publishing Venue

IBM

Related People

Davison, GA: AUTHOR

Abstract

Timer Request Queue Using a Table improves the efficiency of computer program management of requests for notification of timer events. The increased efficiency is achieved by using a hash table to anchor a large number of short chains (queues) of timer requests, with a mechanism to reorganize the hash table to adjust to changing workload conditions. The use of a hash table and short chains avoids the overhead of searching a long chain of timer requests. The size of the hash table is increased as users log onto the system to maintain a roughly constant and small average length of each individual queue, typically less than 10 items, so that minimal queue searching occurs. For a system with 5000 users, this additional use of storage for a hash table requires at most 4 pages, each 4K.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 78% of the total text.

Efficient Computer Timer Request Queue Using a Hash Table

      Timer Request Queue Using a Table improves the efficiency of
computer program management of requests for notification of timer
events.  The increased efficiency is achieved by using a hash table
to anchor a large number of short chains (queues) of timer requests,
with a mechanism to reorganize the hash table to adjust to changing
workload conditions. The use of a hash table and short chains avoids
the overhead of searching a long chain of timer requests.  The size
of the hash table is increased as users log onto the system to
maintain a roughly constant and small average length of each
individual queue, typically less than 10 items, so that minimal queue
searching occurs.  For a system with 5000 users, this additional use
of storage for a hash table requires at most 4 pages, each 4K.

      Each queue of timer requests is ordered by time of expiration,
earliest to last, using the 64-bit Time-of-Day (TOD) value, and are
anchored in a slot in the hash table. All queues have the same
defined "window width", typically one second or one-half second.  A
"window width" of one second corresponds to using bits 24-31 of the
TOD as the hash table index.  A "time cursor" tracks the current TOD,
moving from slot to slot in the hash table.  All timer requests in
the queue of the current slot which are expiring in the current TOD
"window" are dequeued.

      The hash table and its queues are reorganized whe...