US5845115A — Method and a scheduler for controlling when a ser…

Claim 1

Independent Claim 284 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total<1, comprising: a starting time memory having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified, said virtual clock increments virtual time as a function of time regardless of any other considerations; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 2

Dependent Claim 284 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total<1, comprising: a starting time memory having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified, said virtual clock increments virtual time as a function of time regardless of any other considerations; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 3

Dependent Claim 19 words

An apparatus as described in claim 1 wherein the controller provides service to the entities from the server sequentially.

Claim 4

Dependent Claim 42 words

An apparatus as described in claim 1 wherein the controller causes the virtual clock to move present virtual time forward by one unit of virtual time after a predetermined time has passed if the server does not provide service to an entity.

Claim 5

Dependent Claim 29 words

An apparatus as described in claim 3 wherein the starting time memory is a starting time priority queue and the finish time memory is a finishing time priority queue.

Claim 6

Dependent Claim 97 words

A scheduler as described in claim 4 including an element pool which is connected with the N entities and receives elements from the N entities to be operated upon by the server, and wherein the arrival times s i of elements corresponds to the time an element from the i'th entity arrives in the element pool and the finishing times f i compared to the time an element from the i'th entity is to leave the element pool and be operated upon by the server and the controller transfers elements to the server from the element pool.

Claim 7

Dependent Claim 67 words

An apparatus as described in claim 5 wherein the controller is connected to the virtual clock, the element pool, the starting time memory and the finishing time memory for controlling time of the virtual clock, storing the elements in the element pool and their arrival times s i and their finishing times f i in the starting time priority queue and the finishing time priority queue, respectively.

Claim 8

Dependent Claim 113 words

An apparatus as described in claim 6 wherein the controller transfers the element out of the element pool which has the earliest finishing time f i and a starting time s i , unless there is more than one element with the earliest finishing time f i in which case the element with the earliest starting time s i is transferred out of the element pool by the controller and before its finishing time f i , unless there is no element with a starting time s i less than or equal to virtual time, in the element pool, in which case the controller does not transfer an element from the element pool.

Claim 9

Dependent Claim 30 words

An apparatus as described in claim 1 wherein the controller causes the virtual clock to increment virtual time by one unit of virtual time after a predetermined period of time.

Claim 10

Independent Claim 138 words

A method of scheduling when a server provides service to entities comprising the steps of: requesting service from the server by N entities, where N≧1 and is an integer; storing when each of the N entities first requests service from the server and when each of the N entities is to have received service from the server; and providing an entity of the N entities service which has the earliest receiving time and a request time, unless there is more than one entity with the earliest receiving time in which case the entity with the earliest request time is provided service by the server and possibly before its finishing time; unless there is no entity with a request time less than or equal to virtual time, in which case the server does not provide service to an entity.

Claim 11

Independent Claim 138 words

A method of scheduling when a server provides service to entities comprising the steps of: requesting service from the server by N entities, where N≧1 and is an integer; storing when each of the N entities first requests service from the server and when each of the N entities is to have received service from the server; and providing an entity of the N entities service which has the earliest receiving time and a request time, unless there is more than one entity with the earliest receiving time in which case the entity with the earliest request time is provided service by the server and possibly before its finishing time; unless there is no entity with a request time less than or equal to virtual time, in which case the server does not provide service to an entity.

Claim 12

Dependent Claim 33 words

A method as described in claim 9 including after the providing step, there is the step of repeating the providing step in regard to other entities who have requested service from the server.

Claim 13

Dependent Claim 232 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a starting time memory having starting times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests to be operated upon by the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to have been operated upon by the server; a virtual clock that keeps track of virtual time so present virtual time, arrival times s i and finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entity with an earliest finishing time f i and a starting time s i being operated upon first, and then the entities based on a predetermined criteria, said controller causing the virtual clock to increment present virtual time by a unit of virtual time after a predetermined period of time regardless of any other considerations.

Claim 14

Dependent Claim 232 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a starting time memory having starting times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests to be operated upon by the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to have been operated upon by the server; a virtual clock that keeps track of virtual time so present virtual time, arrival times s i and finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entity with an earliest finishing time f i and a starting time s i being operated upon first, and then the entities based on a predetermined criteria, said controller causing the virtual clock to increment present virtual time by a unit of virtual time after a predetermined period of time regardless of any other considerations.

Claim 15

Dependent Claim 196 words

A scheduler for scheduling when N entities, where N is an integer ≧1 are served by a server comprising: a starting time memory having starting times s i when the N entities request service, where 1≦i≦N and is an integer, and s i is the time at which the i'th entity may next get service from the server; a finishing time memory having finishing times f i when the N entities should be serviced, where f i is the time by which the i'th entity should be serviced by the server; a virtual clock that keeps track of time V k where k≧0 and is an integer and V.sub.k =V.sub.k-1 +1 where V k-1 is the virtual time when the server last served an entity; and a controller which chooses which entity is to be operated upon by the server in the order of the entity with an earliest finishing time f i and a start time s i receiving service first, and then the entities based on a predetermined criteria unless there is no entity with a starting time s i less than or equal to virtual time, in which case the server is idle.

Claim 16

Dependent Claim 196 words

A scheduler for scheduling when N entities, where N is an integer ≧1 are served by a server comprising: a starting time memory having starting times s i when the N entities request service, where 1≦i≦N and is an integer, and s i is the time at which the i'th entity may next get service from the server; a finishing time memory having finishing times f i when the N entities should be serviced, where f i is the time by which the i'th entity should be serviced by the server; a virtual clock that keeps track of time V k where k≧0 and is an integer and V.sub.k =V.sub.k-1 +1 where V k-1 is the virtual time when the server last served an entity; and a controller which chooses which entity is to be operated upon by the server in the order of the entity with an earliest finishing time f i and a start time s i receiving service first, and then the entities based on a predetermined criteria unless there is no entity with a starting time s i less than or equal to virtual time, in which case the server is idle.

Claim 17

Dependent Claim 123 words

A scheduler for controlling when a server provides service to entities, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a memory having times which are a function of when entities request service from the server; a virtual clock that keeps track of virtual time as a function of a predetermined period of time if there is no service provided to an entity; and a controller which causes an entity to receive service from the server as a function of virtual time regardless of any other considerations so the server provides service at an established rate with rate control, and no faster.

Claim 18

Dependent Claim 123 words

A scheduler for controlling when a server provides service to entities, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a memory having times which are a function of when entities request service from the server; a virtual clock that keeps track of virtual time as a function of a predetermined period of time if there is no service provided to an entity; and a controller which causes an entity to receive service from the server as a function of virtual time regardless of any other considerations so the server provides service at an established rate with rate control, and no faster.

Claim 19

Independent Claim 108 words

A method for scheduling when a server provides service to entities comprising the steps of: identifying when entities request service from the server, where each entity has a rate at which it is to receive service from the server, at least two entities having different rates, all rates total ≦1; providing service to all the entities as a function of virtual time; and incrementing virtual time by one unit of virtual time or after a predetermined period of time if there is no service provided to an entity regardless of any other considerations so the server provides service at an established rate with rate control, and no faster.

Claim 20

Independent Claim 108 words

A method for scheduling when a server provides service to entities comprising the steps of: identifying when entities request service from the server, where each entity has a rate at which it is to receive service from the server, at least two entities having different rates, all rates total ≦1; providing service to all the entities as a function of virtual time; and incrementing virtual time by one unit of virtual time or after a predetermined period of time if there is no service provided to an entity regardless of any other considerations so the server provides service at an established rate with rate control, and no faster.

Claim 21

Dependent Claim 39 words

A method as described in claim 14 wherein the incrementing step includes the step of incrementing virtual time by one unit of virtual time after a predetermined period of time if there is no service provided to an entity.

Claim 22

Dependent Claim 280 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1 comprising: a memory mechanism having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server and finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified, said virtual clock increments virtual time as a function of time regardless of any other considerations; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 23

Dependent Claim 280 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1 comprising: a memory mechanism having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server and finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified, said virtual clock increments virtual time as a function of time regardless of any other considerations; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 24

Dependent Claim 275 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a memory mechanism having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server and finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified, said virtual clock increments virtual time as a function of time; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 25

Dependent Claim 275 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a memory mechanism having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server and finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified, said virtual clock increments virtual time as a function of time; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 26

Dependent Claim 269 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a starting time memory having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 27

Dependent Claim 269 words

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total ≦1, comprising: a starting time memory having arrival times s i of the N entities, where 2≦i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the arrival times s i and finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server so the server provides service at an established rate with rate control, and no faster, in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , else if there is no entity with an arrival time less than or equal to virtual time, the server does not provide service to any entity.

Claim 28

Dependent Claim 38 words

A scheduler as described in claim 1 wherein the virtual clock keeps track of virtual time so each request for service from the server by an entity is schedulable and each entity will receive service from the server.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-11-30	2002-06-01	2002-12-01	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-11-30	2006-06-01	2006-12-01	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-11-30	2010-06-01	2010-12-01	$7700.00	Window Closed / Lapsed

Method and a scheduler for controlling when a server provides service with rate control to an entity

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag