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

Claim 2

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities, where 1≦I<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server, said starting time memory having only starting times s i which are greater than virtual time; 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, said finishing time memory having finishing times f i of the N entities whose starting times s i are less than or equal to virtual time; a virtual clock that keeps track of virtual time so the starting times s i and finishing times f i can be identified; and a controller for choosing entities to be operated upon by the server from the finishing time memory, for entering entities into the finishing time memory from the starting time memory whose starting times s i become less than or equal to virtual time, and into the starting time memory whose starting times s i are greater than the virtual time, and for deleting entities from the starting time memory whose starting times s i become less than or equal to virtual time, said controller connected to the starting time memory, finishing time memory, and virtual clock.

Claim 3

A scheduler as described in claim 1 wherein the entities having starting times s i in the starting time memory are sorted in order of descending times with the entity having the smallest starting time being first, and the controller stores entities having starting times s i greater than virtual time in the starting time memory in order of descending starting times with the entity having the smallest starting time being first.

Claim 4

A scheduler as described in claim 2 wherein the finishing times f i in the finishing time memory are sorted in order of descending times with the entity having the smallest finishing time being first, and the controller stores entities having starting times s i less than or equal to virtual time in the order of descending finishing times with the entity having the smallest finishing time being first.

Claim 5

A scheduler as described in claim 3 including a second finishing time memory which stores the corresponding finishing times f i of the entities having starting times stored in the starting time memory.

Claim 6

A scheduler as described in claim 4 wherein the controller takes the starting time s i of an entity in the starting time memory and the corresponding finishing time f i from the second finishing time memory when the entity's starting time s i becomes less than or equal to virtual time and sorts and stores the finishing time f i of the entity in the finishing time memory corresponding to its finishing time.

Claim 7

A scheduler as described in claim 5 wherein the controller provides service from the server to the entity having the smallest finishing time in the finishing time memory.

Claim 8

A scheduler as described in claim 6 wherein the controller causes the virtual clock to increase virtual time.

Claim 9

A scheduler as described in claim 7 wherein the controller causes the virtual clock to increase virtual time a unit of virtual time after a predetermined period of time.

Claim 10

A scheduler as described in claim 7 wherein the controller causes the virtual clock to increase virtual time a unit of virtual time after the server provides service to an entity, or to increase virtual time to equal virtual time of the entity having the earliest time in the starting time memory.

Claim 11

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities and the identity of at least the entity having the earliest starting time, where 1≦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 and the identity of at least the entity having the earliest finishing time, 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 starting times s i and finishing times f i can be identified; and a controller for choosing entities to be operated upon by the server from the finishing time memory and which have starting times s i less than or equal to the virtual time, said controller connected to the starting time memory, finishing time memory, and virtual clock.

Claim 12

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities and the identity of at least the entity having the earliest starting time, where 1≦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 and the identity of at least the entity having the earliest finishing time, 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 starting times s i and finishing times f i can be identified; and a controller for choosing entities to be operated upon by the server from the finishing time memory and which have starting times s i less than or equal to the virtual time, said controller connected to the starting time memory, finishing time memory, and virtual clock.

Claim 13

A scheduler as described in claim 10 wherein the controller provides service from the server to the entity having the smallest finishing time in the finishing time memory and which has an starting time less than or equal to virtual time.

Claim 14

A scheduler as described in claim 11 wherein the controller causes the virtual clock to increase virtual time.

Claim 15

A scheduler as described in claim 12 wherein the controller causes the virtual clock to increase virtual time a unit of virtual time after a predetermined period of time.

Claim 16

A scheduler as described in claim 12 wherein the controller causes the virtual clock to increase virtual time a unit of virtual time after the server provides service to an entity, or to increase virtual time to equal virtual time of the entity having the earliest time in the starting time memory.

Claim 19

A method as described in claim 15 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 20

A method as described in claim 16 including after the providing step, there is the step of increasing virtual time.

Claim 21

A method as described in claim 17 wherein the incrementing step includes the step of incrementing virtual time one unit of virtual time after a predetermined time.

Claim 22

A method as described in claim 17 wherein the incrementing step includes the step of incrementing virtual time one unit of virtual time after the server provides service to an entity, or increasing the virtual time to equal the smallest virtual time of an entity which requested service from the server.

Claim 25

A method as described in claim 20 wherein the step of storing in a starting time memory includes the step of sorting the starting times s i of entities in the starting time memory in order of descending times with the entity having the smallest starting time being first.

Claim 26

A method as described in claim 21 wherein the step of storing in a finishing time memory includes the step of sorting the finishing times f i in the finishing time memory in order of descending finishing times with the entity having the smallest finishing time being first.

Claim 27

A method as described in claim 22 including after the step of storing in a starting time memory, there is the step of storing in a second finishing time memory corresponding finishing times f i of the entities having starting times stored in the starting time memory.

Claim 28

A method as described in claim 23 including after the step of storing in the second finishing time memory, there are the steps of taking the starting time s i of an entity in the starting time memory and the corresponding finishing time f i from the second finishing time memory when the entity starting time s i becomes less than or equal to virtual time, sorting the finishing time f i from the second finishing time memory with the finishing times f i in the finishing time memory, and storing the finishing time f i from the second finishing time memory in the finishing time memory.

Claim 29

A method as described in claim 24 wherein the providing step includes the step of providing service from the server to the entity whose finishing time f i has the smallest finishing time in the finishing memory.

Claim 30

A method as described in claim 25 including after the providing service step, there is the step of increasing virtual time.

Claim 31

A method as described in claim 26 wherein the increasing step includes the step of increasing virtual time a unit of virtual time after a predetermined period of time.

Claim 32

A method as described in claim 26 wherein the increasing step includes the step of increasing virtual time a unit of virtual time after the server provides service to an entity, or increasing virtual time to equal virtual time of the entity having the earliest time in the starting time memory.

Claim 33

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities and the identity of at least the entity having the earliest starting time, where 1≦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 and the identity of at least the entity having the earliest finishing time, 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 starting times s i and finishing times f i can be identified; and a controller for choosing the entity having the earliest finishing time from the N entities in the finishing time memory to be operated upon by the server and which has an starting time less than or equal to the virtual time, said controller connected to the starting time memory, finishing time memory, and virtual clock.

Claim 34

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities and the identity of at least the entity having the earliest starting time, where 1≦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 and the identity of at least the entity having the earliest finishing time, 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 starting times s i and finishing times f i can be identified; and a controller for choosing the entity having the earliest finishing time from the N entities in the finishing time memory to be operated upon by the server and which has an starting time less than or equal to the virtual time, said controller connected to the starting time memory, finishing time memory, and virtual clock.

Claim 35

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities, where 1≦I<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server, said starting time memory having only starting times s i which are greater than virtual time; 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, said finishing time memory having finishing times f i of the N entities whose starting times s i are less than or equal to virtual time; a virtual clock that keeps track of virtual time so the starting times s i and finishing times f i can be identified; and a controller for choosing the entity having the smallest finishing time in the finishing time memory of the entities in the finishing time memory to be operated upon by the server, for entering entities into the finishing time memory from the starting time memory whose starting times s i become less than or equal to virtual time and into the starting time memory whose starting times s i are greater than the virtual time, and for deleting entities from the starting time memory whose starting times s i become less than or equal to virtual time, said controller connected to the starting time memory, finishing time memory, and virtual clock.

Claim 36

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities, where 1≦I<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server, said starting time memory having only starting times s i which are greater than virtual time; 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, said finishing time memory having finishing times f i of the N entities whose starting times s i are less than or equal to virtual time; a virtual clock that keeps track of virtual time so the starting times s i and finishing times f i can be identified; and a controller for choosing the entity having the smallest finishing time in the finishing time memory of the entities in the finishing time memory to be operated upon by the server, for entering entities into the finishing time memory from the starting time memory whose starting times s i become less than or equal to virtual time and into the starting time memory whose starting times s i are greater than the virtual time, and for deleting entities from the starting time memory whose starting times s i become less than or equal to virtual time, said controller connected to the starting time memory, finishing time memory, and virtual clock.

Claim 37

A scheduler as described in claim 29 wherein the controller causes the virtual clock to decrease virtual time.

Claim 38

A scheduler as described in claim 30 wherein the controller causes the virtual clock to decrease virtual time.

Claim 41

The method as described in claim 33 wherein after the providing step, there are the steps of deleting the identity, starting time, and finishing time of the entity from the starting time memory and finishing time memory if the entity is provided with service; providing service by the server to the entity having the earliest finishing time in the finishing time memory if the entity also has a starting time earlier than virtual time.

Claim 42

The method as described in claim 34 wherein after the second providing step, there is the step of incrementing virtual time to equal the earliest starting time in the starting time memory.

Claim 43

A method as described in claim 34 wherein after the second providing step, there is the step of incrementing virtual time by a unit of virtual time.

Claim 44

A method as described in claim 33 wherein after the providing step, there is the step of providing service to the entity having the earliest starting time that is also earlier than virtual time if the entity with the earliest finishing time has a starting time later than virtual time.