US5999963A — Move-to-rear list scheduling

Claim 1

Independent Claim 204 words

Apparatus for providing a desired quality of service to a plurality of processes by at least one server comprising an admission control element for assigning to each process, P j , of selected ones of said plurality of processes a respective initial value for a time, left j ≧0, for use of each of said servers, a memory storing for each server an ordered list of entries, said list having a front and a back, each said entry corresponding to a respective one, P j , of said selected ones of said processes, said entries for said selected ones of said processes comprising information about the status of said selected processes and an indication of the time remaining of the time assigned to said each of said selected processes, and a process control element granting the services of a server to P j when P j has an entry in said list comprising an indication that said process has a first status, and which entry is nearer to the front of said ordered list than an entry in said list corresponding to any other process having said first status, said granting of said services being for a period not greater than said time remaining.

Claim 2

Dependent Claim 204 words

Apparatus for providing a desired quality of service to a plurality of processes by at least one server comprising an admission control element for assigning to each process, P j , of selected ones of said plurality of processes a respective initial value for a time, left j ≧0, for use of each of said servers, a memory storing for each server an ordered list of entries, said list having a front and a back, each said entry corresponding to a respective one, P j , of said selected ones of said processes, said entries for said selected ones of said processes comprising information about the status of said selected processes and an indication of the time remaining of the time assigned to said each of said selected processes, and a process control element granting the services of a server to P j when P j has an entry in said list comprising an indication that said process has a first status, and which entry is nearer to the front of said ordered list than an entry in said list corresponding to any other process having said first status, said granting of said services being for a period not greater than said time remaining.

Claim 3

Dependent Claim 80 words

The apparatus of claim 1 wherein said admission control element comprises means for receiving for each of said plurality of processes a request for a service fraction 0≧α sj ≧1 of the services of each server to said plurality of processes, and wherein said assigning by said admission control element to each of said selected processes of an initial time left j for use of each of said servers is based on the respective ones of said requested service fractions.

Claim 4

Dependent Claim 38 words

The apparatus of claim 1, wherein said stored information about the status of said selected processes comprises information relating to the readiness of each of said selected processes to currently use the services of each of said servers.

Claim 5

Dependent Claim 73 words

The apparatus of claim 1 wherein said admission control element further comprises means for receiving for each of said plurality of processes a request for a service fraction of the services of each server to said plurality of processes, and means for selecting said selected ones of said selected processes only if the sum of all service fractions for all of said selected processes is less than unity for each of said servers.

Claim 6

Dependent Claim 28 words

The apparatus of claim 2, wherein said assigning by said admission control element of said left j is based on the respective one of said requested service fractions.

Claim 7

Dependent Claim 30 words

The apparatus of claim 1 further comprising means for decrementing left j for use of a server by the amount of time said process used the services of said server.

Claim 8

Dependent Claim 36 words

The apparatus of claim 1, wherein said process control element places the entry for a process Pj at the end of the list for a server s when left j has a value equal to zero.

Claim 9

Dependent Claim 17 words

The apparatus of claim 1 wherein at least one of said servers is a central processing unit.

Claim 10

Dependent Claim 16 words

The apparatus of claim 1, wherein at least one of said servers is a memory unit.

Claim 11

Dependent Claim 35 words

The apparatus of claim 1 wherein each server s has a respective preemption interval Δt s ≧0, and wherein said initial time left j for each server is at least equal to Δt s .

Claim 12

Dependent Claim 44 words

The apparatus of claim 1, wherein each of said plurality of processes corresponds to a respective collection of received data signals, each collection of data signals including address information about a respective output to which said collection of data signals is to be delivered.

Claim 13

Dependent Claim 30 words

The apparatus of claim 11, wherein each collection of data signals comprises at least one packet, and said address information comprises an address field in said at least one packet.

Claim 14

Dependent Claim 30 words

The apparatus of claim 11, wherein each collection of data signals comprises at least one cell, and said address information comprises an address field in said at least one cell.

Claim 15

Independent Claim 168 words

A method for providing a desired quality of service to a plurality of processes by at least one server comprising assigning to each of selected ones P j of said plurality of processes an initial value for a time left j ≧0 for use of each of said servers, storing for each server an ordered list of entries having a front and a back, said entries each corresponding to respective ones of selected ones of said processes, said entries comprising information about the status of said selected processes and an indication of the time remaining of the time assigned to said each of said selected processes, and granting the services of a server to a process, which process has a corresponding entry comprising an indication that said process has a first status, and which corresponding entry is nearer to the front of said ordered list than an entry corresponding to any other process, said granting of said services being for a period not greater than said time remaining.

Claim 16

Independent Claim 168 words

A method for providing a desired quality of service to a plurality of processes by at least one server comprising assigning to each of selected ones P j of said plurality of processes an initial value for a time left j ≧0 for use of each of said servers, storing for each server an ordered list of entries having a front and a back, said entries each corresponding to respective ones of selected ones of said processes, said entries comprising information about the status of said selected processes and an indication of the time remaining of the time assigned to said each of said selected processes, and granting the services of a server to a process, which process has a corresponding entry comprising an indication that said process has a first status, and which corresponding entry is nearer to the front of said ordered list than an entry corresponding to any other process, said granting of said services being for a period not greater than said time remaining.

Claim 17

Dependent Claim 63 words

The method of claim 14 further comprising the step of receiving for each of said plurality of processes a request for a service fraction 0≧α sj ≧1 of the services of each server to said plurality of processes, wherein said assigning to each of said selected processes a time for use of each of said servers is based on said requested service fraction.

Claim 18

Dependent Claim 36 words

The method of claim 14 wherein said information about the status of said selected processes comprises information about the readiness of each of said selected processes to currently use the services of each of said servers.

Claim 19

Dependent Claim 73 words

The method of claim 14 further comprising the steps of receiving for each of said plurality of processes a request for a service fraction 0≧α sj ≧1 of the services that can be provided by each server to said plurality of processes, wherein selecting said selected ones of said processes only if the sum of all service fractions for all of said selected processes is less than unity for each of said servers.

Claim 20

Dependent Claim 34 words

The method of claim 17 wherein said assigning to each of said selected processes of a time, left j ≧0, for each server s is based on said requested service fraction, α sj .

Claim 21

Dependent Claim 23 words

The method of claim 14, further comprising decrementing left j by an amount reflecting the use by process P j of server s.

Claim 22

Dependent Claim 49 words

The method of claim 19, further comprising the steps of, when left j is equal to zero, placing Pj at the end of the list for server s and setting the value of left j to a non-zero value not greater than the initial value for left j .

Claim 23

Dependent Claim 17 words

The method of claim 14, wherein at least one of said servers is a central processing unit.

Claim 24

Dependent Claim 16 words

The method of claim 14, wherein at least one of said servers is a memory unit.

Claim 25

Dependent Claim 33 words

The method of claim 14, wherein each of said servers has a preemption interval Δt s ≧0, and said granting of said services is for a period not less than Δt s .

Claim 26

Dependent Claim 44 words

The method of claim 14, wherein each of said plurality of processes corresponds to a respective collection of received data signals, each collection of data signals including address information about a respective destination to which said collection of data signals is to be delivered.

Claim 27

Dependent Claim 30 words

The method of claim 24, wherein each collection of data signals comprises at least one packet, and said address information comprises an address field in said at least one packet.

Claim 28

Dependent Claim 30 words

The method of claim 24, wherein each collection of data signals comprises at least one cell, and said address information comprises an address field in said at least one cell.

Claim 29

Dependent Claim 54 words

The method of claim 14, wherein access to said server by a process, P j , to which access has been granted is preempted if another process, P i , has an entry which appears in said list in a position nearer the front of said list than the entry for P j .

Claim 30

Dependent Claim 50 words

The method of claim 14, wherein a process, P j , to which access to a server has been granted is preempted if another process, P i , has an entry in a position nearer the front of said list than the entry for P j assumes said first status.

Claim 31

Independent Claim 112 words

A method for assuring a specified cumulative quality of service for a plurality of processes seeking service by one or more servers comprising the steps of receiving, for each said process, service fraction signals reflecting the fraction of the services of each of said servers required by each said process, selecting a set of said processes which, when granted service by servers in accordance with said received service fractions, do not cause the sum of service fractions for each server to exceed unity, said sum being determined without regard to conflicting requests by said processes, granting services to each of said selected processes by said services in accordance with said service fractions.

Claim 32

Independent Claim 112 words

A method for assuring a specified cumulative quality of service for a plurality of processes seeking service by one or more servers comprising the steps of receiving, for each said process, service fraction signals reflecting the fraction of the services of each of said servers required by each said process, selecting a set of said processes which, when granted service by servers in accordance with said received service fractions, do not cause the sum of service fractions for each server to exceed unity, said sum being determined without regard to conflicting requests by said processes, granting services to each of said selected processes by said services in accordance with said service fractions.

Claim 33

Dependent Claim 39 words

The method of claim 29, wherein at least one of said servers has a preemption interval during which service by said at least one server cannot be preempted in the course of providing service to one of said processes.

Claim 34

Dependent Claim 49 words

The method of claim 29 wherein the order of said granting of services is in accordance with proximity to the front of a list of entries, each of which entries corresponds to one of said processes, said entries each including a field indicating the status of said corresponding process.

Claim 35

Dependent Claim 17 words

The method of claim 31 wherein said field indicating status indicates the runability of said corresponding process.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-12-06	2003-06-07	2003-12-07	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-12-06	2007-06-07	2007-12-07	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-12-06	2011-06-07	2011-12-07	$7700.00	Window Closed / Lapsed

Move-to-rear list scheduling

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag