Method and system for allocating CPU bandwidth by prioritizing competing processes

• US 6,067,557 A
• Filed: 09/06/1996
• Issued: 05/23/2000
• Est. Priority Date: 09/06/1996
• Status: Expired due to Term

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Hegde, Dinesh
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/709,124
• Time in Patent Office: 1,355 Days
• Field of Search: 395/673, 395/674, 395/732, 709/100-108
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method and system of allocating bandwidth between a plurality of competing processes, the method comprising the steps of (a) registering, within a computer, the plurality of processes, each having an assigned priority from highest priority to lowest priority; (b) assigning to each of the plurality of processes a count value relative to each of the process'"'"' priority, wherein the lowest priority process is assigned a base count value, and each higher priority process is assigned a count value which is determined based on the ratio of its priority to the process with the lowest priority; (c) determining the process having the highest count value; (d) executing the process having the highest count value, wherein if more than one process has the same highest count value, the currently executing process continues to be executed if it is one of the processes having the highest count value, otherwise, one of the processes having the same highest count value is selected based on a predetermined criteria; (e) decrementing the count value of the currently executing process; (f) repeating steps (c)-(e) until the count value of each process is zero; (g) reassigning the initial respective count values to processes which are not complete; and (h) repeating steps (c)-(g) until each process is complete.

Claims

1. A method of prioritizing an allocation of bandwidth between a plurality of competing processes, the method comprising the steps of:

a). registering, within a computer, said plurality of processes each having a prioritized count value from highest to lowest priority, wherein the priority is based on the percentage of bandwidth assigned to each of said plurality of processes;

b). determining the process having the highest priority count value;

c). executing the process having the highest priority count value on a preemptive priority basis, wherein if more than one process has the same highest priority count value, the currently executing process continues to be executed if it is one of the processes having the highest priority count value, otherwise, one of the processes having the same highest priority count value is selected based on a predetermined criteria;

d). decrementing the count value of the currently executing process;

e). repeating steps (b)-(d) until the count value of each process is zero;

f). reassigning the initial respective count values to processes which are not complete;

g). repeating steps (b)-(f) until each process is complete.

2. The method of claim 1 wherein, in step (a), said plurality of processes is registered in a table in a memory of the computer.

3. The method of claim 2, wherein step (b) is reiterated at regular intervals in order to continuously determine which process has the highest priority count value by referring to said table.

4. A system for allocating bandwidth between a plurality of competing processes comprising:

management means for assigning a count value to each of said plurality of competing processes, each competing process having a respective required bandwidth, wherein a base count value of lowest priority is assigned to the competing process having a lowest required bandwidth percentage, and a higher priority count value is determined for each other process based on a ratio of the required bandwidth of the process to the required bandwidth of the process with the lowest priority,

means for executing the one of said plurality of processes having the determined highest priority count value; and

system timer means for interrupting said management means to cause said management means to reiteratively determine which of said plurality of processes should be currently executed based on the determined highest priority count value.

5. The system of claim 4 wherein said management means determines which of said plurality of processes should be currently executed by referring to a table stored in computer memory which lists each of said plurality of processes and their respective count values.

6. The system of claim 5 wherein said management means executes the process currently assigned the highest count value.

7. The system of claim 5 wherein said management means refers to said table to determine which of said plurality of processes should be currently executed at regularly timed intervals as dictated by said system timer means.

8. The system of claim 7 wherein said management means decrements the count value of the process which is being currently executed, reevaluates said count values and executes the process which then has the highest count value.

9. A method for allocating bandwidth between a plurality of competing processes the method comprising the steps of:

a) registering in a table within a computer, each of said plurality of competing processes and an associated bandwidth requirement;

b) ranking said plurality of processes based only on each process'"'"' bandwidth requirement;

c) determining which process should be executed based on said ranking; and

d) executing the process determined in step (c).

10. The method of claim 9, wherein step (b) comprises assigning a count value to each of said plurality of processes, said count value being determined relative to each process'"'"' bandwidth requirement, in which the process which requires the lowest bandwidth is assigned a base count value and the remaining processes are assigned a count value between the base count value and a highest count value in relative correspondence to each process'"'"' bandwidth requirement.

11. The method of claim 10 wherein step (c) comprises referring to said table to find the process with the highest count value.

12. A method for prioritizing an allocation of bandwidth of a bandwidth-limited resource between competing devices comprising the steps of:

interrupting the bandwidth-limited resource on a pre-emptive priority basis in order to allow a reassignment of the bandwidth;

providing a requested bandwidth for each competing device;

determining a count value for each competing device wherein the count values are ordered for priority of execution based on the required bandwidth of the corresponding competing device; and

decrementing the count value of the competing device executing prior to the interrupting step.

13. The method of claim 12, wherein the competing device having the highest priority count value is selected for execution.

14. The method of claim 13, wherein the competing device executing prior to the interrupting step is selected to continue execution if its count value is equal to the highest priority count value.

15. The method of claim 12, wherein the steps are repeated until the count value of each competing device is zero.

16. The method of claim 15, wherein after the repeated steps the count values are redetermined for the competing devices having required bandwidth.

17. The method of claim 12, wherein the count value of the competing device having the lowest required bandwidth is assigned a base count value and the remaining competing devices are assigned count values between the base count value and a highest count value in relative correspondence to their required bandwidth.

18. The method of claim 17, wherein the highest count value has the highest priority.

19. The method of claim 12, wherein the count value for each competing device is a ratio of its required bandwidth divided by the lowest required bandwidth of all competing devices.

20. The method claim 12, wherein the bandwidth-limited resource comprises CPU bandwidth.

21. The method of claim 20, wherein the competing devices comprise competing processes.

22. The method of claim 12, wherein the bandwidth-limited resource comprises a network backplane link and the connecting devices comprise ports requiring access to the link.

23. The method of claim 12, wherein the interrupting step is caused by a system timer.

24. The method of claim 23, wherein the system timer manages the bandwidth allocation.

25. The method of claim 12, wherein the bandwidth-limited resource comprises a network switch and the competing devices include network management and connection processes.

26. A system for prioritizing an allocation of bandwidth among a plurality of competing devices to a bandwidth-limited resource comprising:

the bandwidth-limited resource being subject to interruption by a system timer on a pre-emptive priority basis in order to pre-empt a currently executing one of the plurality of competing devices and determine an updated allocation of bandwidth between the competing devices;

a data structure including, for each of the plurality of competing devices, a required bandwidth, and a count value having a priority based on its required bandwidth; and

an execute process causing execution of the competing device having the highest priority count value.

27. The bandwidth allocation system of claim 26, wherein the competing devices comprise competing processes.

28. The bandwidth allocation system of claim 27, wherein the bandwidth-limited resource comprises CPU bandwidth.