Scheduling unit for scheduling service requests to cyclically provide services

• US 6,453,316 B1
• Filed: 06/29/1998
• Issued: 09/17/2002
• Est. Priority Date: 10/26/1995
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Tanaka, Tsutomu, Kokado, Takeshi, Karibe, Tomoyuki, Ito, Yukiko, Tamai, Masaaki, Doi, Shinzo
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US09/106,176
• Time in Patent Office: 1,541 Days
• Field of Search: 395/287, 395/728, 707/200-206, 707/8, 707/10, 709/100-108, 709/200-203, 709/208-211
• US Class Current: 1/1
• CPC Class Codes: H04N 21/23406 involving management of server-side video buffer
• CPC Class Codes: H04N 21/234381 by altering the temporal resolution, e.g. decreasing the frame rate by frame skipping
• CPC Class Codes: H04N 21/23805 Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/2393 involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/2401 Monitoring of the client buffer
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/440281 by altering the temporal resolution, e.g. by frame skipping television signal recording using magnetic recording on tape for reproducing at a rate different from the recording rate H04N5/783
• CPC Class Codes: H04N 21/6587 Control parameters, e.g. trick play commands, viewpoint selection
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

When a get resource message arrives from an exterior, a resource allocation part reserves a resource. In case of data reading or data writing, a declared value management part checks parameters and a slot allocation part allocates the resource, thereby constructing an efficient file system guaranteeing delay quality in relation to data reading. As the result, it is possible to provide a file system providing pictures in a quick response time for requests from users and supporting users requiring various regeneration speeds.

Claims

1. A scheduling unit for use with a server and a plurality of clients and for use in scheduling service requests so that the server cyclically provides services to the plurality of clients, said scheduling unit comprising:

a first queue for queuing service requests from the plurality of clients;

registration means for registering cycles of generation of execution rights for the plurality of clients;

execution right generation means for generating the execution rights according to the cycles registered in said registration means, wherein the execution rights are rights of execution of the service requests; and

execution instruction means for instructing the server to execute service requests from clients corresponding to the execution rights generated by said execution right generation means among the service requests queued in said first queue.

2. The scheduling unit according to claim 1, wherein said execution right generation means is started in a prescribed cycle for determining, at the time of starting, based on the cycles for generating the execution rights, which are registered in said registration means, and the cycle for starting said execution right generation means, whether or not execution rights are to be generated for every client, while collectively generating the execution rights for the clients for whom it has been determined that execution rights are to be generated.

3. The scheduling unit according to claim 2, wherein said execution instruction means is started in a prescribed cycle for selecting an execution right for a client having a shorter time between a current started time to a time for generating the next execution right.

4. The scheduling unit according to claim 3, wherein said execution right generation means calculates an evaluation index indicating precedence as a function of the cycles for generating the execution rights being registered in said registration means and providing the evaluation index to the generated execution rights, and

said execution instruction means selects an execution right to be preferentially processed among the execution rights being generated by said execution right generation means.

5. The scheduling unit according to claim 4, wherein said execution right generation means calculates the evaluation index Nsft by a function Nsft=f(Treq/Tslt), where f(x) represents a minimum integer exceeding x, with respect to the cycles Treq for generating the execution rights being registered in said registration means and the cycle Tslt for starting said execution right generation means, and

said execution instruction means selects an execution right having a smaller evaluation index Nsft being provided thereto.

6. The scheduling unit according to claim 5, wherein said execution right generation means is started in a cycle being shorter than the longest one of the cycles being registered in said registration means.

7. The scheduling unit according to claim 5, wherein said execution right generation means is started in a cycle being shorter than the shortest one of the cycles being registered in said registration means.

8. The scheduling unit according to claim 5, wherein said execution instruction means recognizes a maximum number of service requests, execution of which is instructed in starting, stops the instruction of execution when the execution of the service requests is instructed by a number equal to the maximum number, and decrements the evaluation indices of the remaining execution rights.

9. The scheduling unit according to claim 4, wherein said execution instruction means includes second queue means for queuing the execution rights being generated by said execution right generation means for every provided evaluation index in order of generation, for selecting an execution right having a smaller provided evaluation index and being precedently generated among the execution rights being queued in said second queue means.

10. The scheduling unit according to claim 4, wherein said execution instruction means recognizes a maximum number of service requests, execution of which is instructed in starting, stops the instructions of execution when the execution of the service requests is instructed by a number equal to the maximum number, and changes the evaluation indices of the remaining execution rights to those having higher precedence.

11. The scheduling unit according to claim 10, wherein the maximum number of service requests, execution of which is instructed in starting, being recognized by said execution instruction means is a maximum number of service requests executable by the server in a time being equal to the cycle for starting said execution right generation means.

12. The scheduling unit according to claim 8, wherein the maximum number of the service requests, execution of which is instructed in starting, being recognized by said execution instruction means is a maximum number of service requests executable by the server in a time equal to the cycle for starting said execution right generation means.

13. The scheduling unit according to claim 10, further comprising registration instruction means for instructing said registration means to register the cycles for generating the execution rights based on declarations from the plurality of clients.

14. The scheduling unit according to claim 13, wherein said registration instruction means recognizes a maximum number of service requests, execution of which is instructed by said execution instruction means per unit time, and when registration of a further cycle is declared in addition to the already registered cycles, said registration instruction means instructs said registration means to register the cycle if said registration instruction means determines that an average number of the generated execution rights per unit time is not in excess of the maximum number even if further registration is made, while making the cycle not registered if said registration instruction means determines otherwise.

15. The scheduling unit according to claim 2, wherein said execution right generation means calculates a time from a current started time up to a time for generating a next execution right based on the cycles for generating the execution rights which are registered in said registration means and the cycle for starting the execution right generation means, and determines whether or not the execution rights are generated by comparing the time obtained by the calculation with the cycle for starting the execution right generation means.

16. The scheduling unit according to claim 15, wherein said execution right generation means generates an execution right for a client having a Tofs, which is a time between a current started time to a time for generating the next execution right, being less than a cycle Tslt for starting the execution right generation means (Tofs<

Tslt), and adds a cycle Treq for generating the execution right being registered in said registration means to the Tofs of the client, for calculating a new Tofs for the next starting from an expression Tofs=Tofs−

Tslt with respect to the Tofs if the Tofs obtained by the addition is greater than or equal to Tslt (Tofs≧

Tslt).

17. The scheduling unit according to claim 16, wherein said execution right generation means repeats an operation of further generating an execution right, adding the Treq to the Tofs and comparing the result with the Tslt if the Tofs obtained by the addition is less than Tslt (Tofs<

Tslt), and calculates a new Tofs for the next starting from an expression Tofs=Tofs−

Tslt with respect to Tofs when the Tofs obtained by the addition is greater than or equal to Tslt (Tofs≧

Tslt).

18. The scheduling unit according to claim 16, wherein said execution right generation means generates no execution right as to a client having a Tofs greater than or equal to Tslt (Tofs≧

Tslt) or having a service request being not queued in said first queue, and calculates a new Tofs for the next starting through an expression Tofs=Tofs−

Tslt with respect to the Tofs.

19. The scheduling unit according to claim 18, wherein said execution right generation means zeroes the Tofs for next starting if the new Tofs obtained by said calculation is less than zero (Tofs<

0).

20. A scheduling unit for use with a plurality of servers and a client and for use in scheduling service requests so that the plurality of servers cyclically provide services to the client respectively, said scheduling unit comprising:

first queue means for queuing service requests to the plurality of servers;

registration means for registering cycles of generation of execution rights for the plurality of servers;

execution right generation means for generating execution rights according to the cycles registered in said registration means, wherein the execution rights are rights of execution of the service requests; and

execution instruction means for instructing the servers to execute the service requests corresponding to the execution rights generated by said execution right generation means among the service requests queued in said first queue means.

21. The scheduling unit according to claim 20, wherein said execution right generation means is started in a prescribed cycle for determining, at the time of starting, based on the cycles for generating the execution rights registered in said registration means and the cycle for starting said execution right generation means, whether or not the execution rights are generated for respective servers, and collectively generating the execution rights for the servers in which the execution rights are determined to be generated.

22. The scheduling unit according to claim 21, wherein said execution right generation means calculates a time from a current started time up to a time for generating a next execution right based on the cycles for generating the execution rights being registered in said registration means and the cycle for starting the execution right generation means, and compares the time obtained by the calculation with the cycle for starting said execution right generation means to determine whether or not the execution rights are generated.

23. The scheduling unit according to claim 22, wherein said execution right generation means generates an execution right for a server having a Tofs, which is a time between a current started time to a time for generating the next execution right, being less than a cycle Tslt for starting the execution right generation means (Tofs<

Tslt), and adds a cycle Titv for generating the execution right being registered in said registration means to the Tofs of the server, for calculating a new Tofs for the next starting from an expression Tofs=Tofs−

Tslt with respect to the Tofs if the Tofs obtained by the addition is greater than or equal to Tslt (Tofs≧

Tslt).

24. The scheduling unit according to claim 23, wherein said execution right generation means repeats an operation of further generating an execution right, adding Titv to Tofs and comparing the result with Tslt if the Tofs obtained by the addition is less than Tslt (Tofs<

Tslt), and calculates a new Tofs for the next starting by an expression Tofs=Tofs−

Tslt with respect to Tofs when the Tofs obtained from the addition is greater than or equal to Tslt (Tofs≧

Tslt).

25. The scheduling unit according to claim 23, wherein said execution right generation means generates no execution right as to a server having a Tofs greater than or equal to Tslt (Tofs≧

Tslt) or having a service request being not queued in said first queue means, and calculates a new Tofs for the next starting through an expression Tofs=Tofs−

Tslt with respect to the Tofs.

26. The scheduling unit according to claim 25, wherein said execution right generation means zeroes the Tofs for the next starting if the new Tofs obtained by the calculation is less than zero (Tofs<

0).

27. The scheduling unit according to claim 21, wherein said execution instruction means is started in a prescribed cycle for selecting an execution right of a server having a shorter time between a current started time to a time for generating the next execution right.

28. The scheduling unit according to claim 27, wherein said execution right generation means calculates an evaluation index indicating precedence as a function of the cycles for generating the execution rights being registered in said registration means and providing the evaluation index to the generated execution rights, and

said execution instruction means selects an execution right to be preferentially processed among the execution rights being generated by said execution right generation means based on the provided evaluation index.

29. The scheduling unit according to claim 28, wherein said execution right generation means calculates the evaluation index Nsft by a function Nsft=f(Titv/Tslt), where f(x) represents a minimum integer exceeding x, with respect to the cycles Titv for generating the execution rights being registered in said registration means and the cycle Tslt for starting said execution right generation means, and

said execution instruction means selects an execution right having a smaller evaluation index Nsft being provided thereto.

30. The scheduling unit according to claim 29, wherein said execution right generation means is started in a cycle being shorter than the longest one of the cycles being registered in said registration means.

31. The scheduling unit according to claim 29, wherein said execution right generation means is started in a cycle being shorter than the shortest one of the cycles being registered in said registration means.

32. The scheduling unit according to claim 29, wherein said execution instruction means recognizes a maximum number of service requests, execution of which is instructed at the time of starting, stops instruction of execution when execution of the service requests is instructed by a number equal to the maximum number, and decrements the evaluation indices of the remaining execution rights.

33. The scheduling unit according to claim 32, wherein the maximum number of service requests, execution of which is instructed at the time of starting, being recognized by said execution instruction means is a number of service requests corresponding to a maximum quantity of information being transmittable from all of the servers to the client in a time being equal to the cycle for starting said execution instruction means.

34. The scheduling unit according to claim 28, wherein said execution instruction means includes second queue means for queuing the execution rights being generated by said execution right generation means for every provided evaluation index in order of generation, for selecting an execution right having a smaller provided evaluation index and being precedently generated among the execution rights being queued in said second queue means.

35. The scheduling unit according to claim 28, wherein said execution instruction means recognizes a maximum number of service requests, execution of which is instructed at the time of starting, stops instruction of execution when execution of the service requests is instructed by a number equal to the maximum number, and changes the evaluation indices of the remaining execution rights to those having higher precedence.

36. The scheduling unit according to claim 35, wherein the maximum number of service requests, execution of which is instructed at the time of starting, being recognized by said execution instruction means is a number of service requests corresponding to a maximum quantity of information being transmittable from all of the servers to the client in a time being equal to the cycle for starting said execution instruction means.

37. The scheduling unit according to claim 35, further comprising registration instruction means for instructing said registration means to register/update the cycles for generating execution rights based on a declaration from the client.

38. The scheduling unit according to claim 37, wherein said registration instruction means recognizes a maximum number of service requests, execution of which is instructed by said execution instruction means to all of the servers per unit time, and when registration of a cycle of a further server is declared in addition to already registered cycles, said registration instruction means instructs said registration means to register the cycle if said registration instruction means determines that an average number of generated execution rights of all of the servers per unit time is not in excess of the maximum number even if further registration is made, while making the cycle not registered if said registration instruction means determines otherwise.

39. The scheduling unit according to claim 37, wherein said registration instruction means recognizes a maximum number of service requests, execution of which is instructed by said execution instruction means to each server per unit time, and when registration of a cycle of a further server is declared in addition to already registered cycles, said registration instruction means instructs said registration means to register the cycle if said registration instruction means determines that an average number of generated execution rights of each server per unit time is not in excess of the maximum number of service requests, execution of which is instructed by said execution instruction means to the server per unit time, even if further registration is made, while making the cycle not registered if said registration instruction means determines otherwise.

40. The scheduling unit according to claim 39, wherein the maximum number of service requests, execution of which is instructed by said execution instruction means to each server per unit time, is a maximum number of service requests being executable by the each server per unit time.

41. The scheduling unit according to claim 37, wherein said registration instruction means recognizes a maximum number of service requests, execution of which is instructed by said execution instruction means to all of the servers per unit time, and a maximum number of service requests, execution of which is instructed by said execution instruction means to each server per unit time, and when a declaration is made to update a cycle Titv for generating an execution right for a prescribed server being already registered to a cycle for generating an execution right with further addition of a cycle Treq, said registration instruction means instructs said registration means to update said cycle Titv to a new Titv being calculated by an expression Titv=1/(1/Titv+1/Treq) in case of determining that an average number of generated execution rights of all of the servers per unit time is not in excess of a maximum number of service requests, execution of which is instructed by said execution instruction means to all of the servers per unit time and in case of determining that an average number of generated execution rights of each server per unit time is not in excess of the maximum number of service requests, execution of which is instructed by said execution instruction means to each server per unit time, while not updating said Titv in case of determining otherwise.

42. The scheduling unit according to claim 37, wherein when a declaration is made to update an already registered cycle Titv for generating an execution right of a prescribed server to a cycle for generating an execution right while excluding a cycle Treq, said registration instruction means instructs said registration means to update the Titv to a new Titv being calculated by an expression Titv=1/(1/Titv−

1/Treq).