Control process for allocating services in communications systems

• US 5,381,546 A
• Filed: 03/11/1993
• Issued: 01/10/1995
• Est. Priority Date: 04/13/1987
• Status: Expired due to Term

• Current Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Original Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Inventors: Servi, Leslie D., Keilson, Julian
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/031,081
• Time in Patent Office: 670 Days
• Field of Search: 395/650, 395/DIG. 1, 395/DIG. 2
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A process for scheduling a processor, in a stored program digital switch of a telecommunications network having heterogeneous types of task, utilizes preassigned probability parameters to schedule the tasks for the processor to serve to meet a system objective. For n types of tasks, each having one of n probability parameters P_i where 0<P_i <1, the system first serves a type i task, then if queue i is empty, it serves a type i+1 modulus (n) task. If queue i is not empty, with a probability P_i it serves another type i task and with a probability 1-p_i it serves a type i+1 task modulus (n) until a type i+1 task modulus (n) until a type i+1 task is served. Thus the processor continually cycles through all types of tasks.

Claims

1. A process executed by a computer for selecting by said computer a next sequential task to be allocation service of a computer processor while scheduling the allocation of services of the computer processor among two or more queues of tasks wherein said queues Q_i are sequentially numbered for i equal to 0, 1, 2, . . . , n-1, comprising the steps of:

receiving by said computer probability parameters p₀, . . . p_n-1, where 0≦

pⁱ ≦

1 for indicating the relative priorities of said queues 0_i ;

assigning by said computer each of said probability parameters p_i to a respective queue Q_i ;

selecting by said computer a task from queue Q_i for allocation of service of said computer processor

determining by said computer if there is at least another task in queue Q_i ;

selecting by said computer a task from queue Q_i+1 modulus (n) for allocation of service of said computer processor, having no other task in queue Q_i ;

performing the following steps if there is at least another task in queue Q_i ;

generating by said computer a random number M where 0≦

M≦

1;

comparing by said computer said random number M to said probability parameter p_i ;

selecting by said computer the next sequential task to be allocated service of the computer processor, from said tasks in the next sequential queue Q_i+1 modulus (n) if M>

p_i and selecting by said computer the next sequential task to be allocated service of the computer processor, from said tasks in queue Q_i if M<

p_i.

2. A computer for selecting a next sequential task to be allocated service of a computer processor while scheduling the allocated of services of the computer processor among two or more queues of tasks wherein said queues Q_i are sequentially numbered for i equal to 0, 1, 2, . . . , n-1, comprising the steps of:

means for receiving by said computer probability parameters p₀, . . . , p_n-1, where 023 pⁱ ≦

1 for indicating the relative priorities of said queues Q_i ;

means for assigning by said computer each of said probability parameters p_i to a respective queue Q_i ;

means for selecting by said computer a task from queue Q_i for allocation of service of said computer processor;

means for determining by said computer if there is at least another task in queue Q_i ;

means for selecting by said computer a task from queue Q_i+1 modulus (n) for allocation of service of said computer processor, having no other task in queue Qⁱ ;

means for generating by said computer a random number M where 0≦

M ≦

1;

means for comparing by said computer said random number M to said probability parameter p_i if there is at least another task in queue Q_i ;

means for selecting by said computer the next sequential task to be allocated the computer processor if there is at least another task in queue Q_i, from said tasks in the next sequential queue Q_i+1 modulus (n) If M>

p_i, and means for selecting by said computer the next sequential task to be allocated service of the computer processor, from said tasks in queue Q_i if M<

p_i.