Browse Prior Art Database

Smoothed Powers of Two Servicing of Work Requests

IP.com Disclosure Number: IPCOM000086125D
Original Publication Date: 1976-Jul-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 46K

Publishing Venue

IBM

Related People

Norton, HT: AUTHOR

Abstract

For many application environments, it may be possible to assign work requests to a set of work queues whose service frequencies differ by powers of two. That is, the service intervals are 2, 4, 8, 16,...times the service interval of the most frequently served queue. In this way, a large range of service demand intervals can be satisfied with a minimum number of work queues; and work requests are subjected to delays proportional to their service intervals. A unit of work would be placed on the predefined queue that best satisfies its requirements.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Smoothed Powers of Two Servicing of Work Requests

For many application environments, it may be possible to assign work requests to a set of work queues whose service frequencies differ by powers of two. That is, the service intervals are 2, 4, 8, 16,...times the service interval of the most frequently served queue. In this way, a large range of service demand intervals can be satisfied with a minimum number of work queues; and work requests are subjected to delays proportional to their service intervals. A unit of work would be placed on the predefined queue that best satisfies its requirements.

Assuming that such a queue structure exists, a simple algorithm is needed to identify the appropriate queues for serving so that each queue is served at the proper frequency. In addition, it is desirable to minimize peaks of service demands. This description presents a solution to these problems.

To implement this method, a basic service timer must provide a signal at twice the rate of the most frequently served queue. Based on the logic of the flow chart, a single queue is served each time a signal is received from the basic service timer; yet each queue is served at its proper rate.

The technique is based on incrementing a service counter (SC) having as many binary positions as there are queues to be served. Each queue corresponds to one binary digit of the SC. The most frequently served queue is associated with the low-order binary digit of the SC. Successive queues, each served half as often as the preceding queue, are...