Browse Prior Art Database

Fair queue algorithm for sharing resources among disparate prioritized groups, yet providing optimal overall utilization level

IP.com Disclosure Number: IPCOM000031026D
Original Publication Date: 2004-Sep-07
Included in the Prior Art Database: 2004-Sep-07
Document File: 2 page(s) / 44K

Publishing Venue

IBM

Abstract

The queue algorithm presented here guarantees optimal usage of overall resources while complying with the priority policy set by management.. Each group is guaranteed to get its resources when it needs them. However, if the resources are not used by their "owners", then others are allowed to use them. The algorithm also ensures that, over time, one cannot "hog" the system and take more than one's fair share of the resources.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Fair queue algorithm for sharing resources among disparate prioritized groups, yet providing optimal overall utilization level

Allocating valuable resources to a homogeneous group of users can be handled with relative ease with a FIFO queue. One complication that has to be addressed, though, is the fairness. There has to be a way to prevent a single user or a small group of users from "hogging" and take more than their fair share of the resources. Another level of complexity is added when the queue has to manage disparate groups. For example, each of the groups may be granted a priority access to a certain number units out of the general resource pool, but if and when the privileged groups don't utilize their share, then their under-utilized resources can be made available to the other, less favored groups. Another requirement of resource management is flexibility, i.e. it should allow for "urgent" jobs to overtake the queue and be executed immediately. The most common method of dealing with the above described problem is, first of all, a strict allocation of resources (such as computers of various configurations and performances) among the groups, and then ad-hoc negotiations (over the phone or face to face) to permit a temporary or urgent use of the resources. Strict allocation along with the frequent phone-calls or meetings can waste a lot of managerial time, and these methods do not respond well to dynamic situations, resulting in misuse, if not abuse, of expensive resources.

    The queue algorithm presented here guarantees optimal usage of overall resources while complying with the priority policy set by management.. Each group is guaranteed to get its resources when it needs them. However, if the resources are not used by their "owners", then others are allowed to use them. The algorithm also ensures that, over time, one cannot hog the system and take more than one's fair share of the resources.

Note: The DEFAULT_PRIORITY used in this description is 1024 (but can be set to any other value).

There are generally three different classes of jobs that enter the queue:

A job that has a pre-set PRIORITY set to either a level different than


1.


2.


3.

(DEFAULT_PRIORITY-1) or whose pre-set priority is BIGGER than the DEFAULT_PRIORITY. In most cases, the pre-set PRIORITY is of the latter type,
i.e of a higher priority than the DEFAULT_PRIORITY (those jobs are also called UR...