Method and system for executing multiple tasks at adaptively controlled resource utilization rates to achieve equal QoS levels

• US 20050182747A1
• Filed: 01/21/2005
• Published: 08/18/2005
• Est. Priority Date: 02/18/2004
• Status: Abandoned Application

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Nakamoto, Yukikazu, Harada, Fumiko, Ushio, Toshimitsu
• Application Number:
  US11/038,690
• Publication Number:
  US 20050182747A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The QoS levels of multiple tasks are maintained at equal levels by executing items of the tasks stored in a queue during a given time interval at respectively adaptively controlled CPU utilization rates. The QoS levels of the executed items are detected and evaluated. The CPU utilization rates are updated with respective differences between a target value and the evaluated QoS levels. A difference is detected between each of the evaluated QoS levels obtained during a previous time interval and each of the evaluated QoS levels obtained during a current time interval and the detected difference is compared to a predetermined value. During a subsequent time interval, the previously stored items of the queue are replaced with new items of the tasks if the difference is smaller than the predetermined value and the previously stored items are executed again with the updated CPU utilization rates if the difference is greater than predetermined value.

Claims

1. A method of controlling QoS levels of a plurality of tasks, comprising the steps:

a) during a time interval, storing items of the tasks in a queue;

b) executing the items at respective resource utilization rates;

c) detecting QoS levels of the executed items;

d) evaluating the detected QoS levels of the executed items;

e) updating the resource utilization rates with respective differences between a target value and the evaluated QoS levels;

f) determining, from the evaluated QoS levels, whether the detected QoS levels are converging to said target value or diverging from said target value; and

g) during a subsequent time interval, replacing the previously stored items of the queue with new items of the tasks and repeating steps (b) to (f) on the new items if the QoS levels are converging to said target value, and repeating steps (b) to (f) on the previously stored items if QoS levels are diverging from said target value.

2. The method of claim 1, wherein step (f) comprises the steps of:

detecting a difference between each of the evaluated QoS levels obtained during a previous time interval and each of the evaluated QoS levels obtained during a most recent time interval; and

comparing the detected difference to a predetermined value, wherein step (g) comprises the steps of;

during said subsequent time interval, replacing the previously stored items of the queue with new items of the tasks and repeating steps (b) to (f) on the new items if the difference is smaller than the predetermined value, and repeating steps (b) to (f) on the previously stored items if the difference is greater than the predetermined value.

3. The method of claim 1, wherein step (d) comprises the steps of:

d₁) detecting differences between the detected QoS levels and a QoS lower limit;

d₂) detecting a difference between a QoS upper limit and the QoS lower limit; and

d₃) calculating ratios by dividing the differences of step (d₁) by the difference of step (d₂) to represent the evaluated QoS levels.

4. The method of claim 1, wherein step (e) comprises the steps of:

calculating an average value of the evaluated QoS levels;

detecting respective differences between the average value and the evaluated QoS levels; and

updating the resource utilization rates of the first memory with the respective differences.

5. The method of claim 1, wherein the differences between the target value and the evaluated QoS levels are weighted differences between the target value and the evaluated QoS levels.

6. The method of claim 4, wherein the differences between the average value and the evaluated QoS levels are weighted differences between the average value and the evaluated QoS levels.

7. The method of claim 1, wherein the resource utilization rates are utilization rates of a central processing unit.

8. The method of claim 1, wherein the items stored in the queue are temporal service items for which contention arises among the tasks.

9. The method of claim 1, wherein the items stored in the queue are spatial service items for which request is issued from the tasks.

10. A computer system having a plurality of tasks, comprising:

a queue for holding a plurality of items of the tasks during a time interval;

a first memory for storing resource utilization rates associated respectively with the stored items;

means for executing the items at the associated resource utilization rates respectively; and

adaptive control mechanism for detecting QoS levels of the executed items, evaluating the detected QoS levels of the executed items, storing the evaluated QoS levels in the second memory, and updating the resource utilization rates of the first memory with respective differences between a target value and the evaluated QoS levels; and

decision mechanism for determining, from the evaluated QoS levels, whether the detected QoS levels are converging to said target value or diverging from said target value, replacing the stored items of the queue with new items of the tasks if the evaluated QoS levels are converging to said target value, and causing the previously stored items to be executed again by the executing means if the evaluated QoS levels are diverging from said target value.

11. The computer system of claim 10, further comprising a second memory, and wherein said adaptive control mechanism stores the evaluated QoS levels in said second memory, and said decision mechanism compares a difference between each of the evaluated QoS levels stored in the second memory during a previous time interval and each of the evaluated QoS levels stored in the second memory during a current time interval to a predetermined value, replaces the stored items of the queue with new items of the tasks if the difference is smaller than the predetermined value, and causes the previously stored items to be executed again by the executing means if the difference is greater than the predetermined value.

12. The computer system of claim 10, wherein the adaptive control mechanism detects differences between the detected QoS levels and a QoS lower limit, detects a difference between a QoS upper limit and the QoS lower limit, and calculates ratios by dividing the detected differences by the detected difference to represent the evaluated QoS levels.

13. The computer system of claim 10, wherein the adaptive control mechanism calculates an average value of the evaluated QoS levels, detects respective differences between the average value and the evaluated QoS levels, and updates the resource utilization rates of the first memory with the respective differences.

14. The computer system of claim 10, wherein the differences between the target value and the evaluated QoS levels are weighted differences between the target value and the evaluated QoS levels.

15. The computer system of claim 13, wherein the differences between the average value and the evaluated QoS levels are weighted differences between the average value and the evaluated QoS levels.

16. The computer system of claim 10, wherein the resource utilization rates are utilization rates of a central processing unit.

17. The computer system of claim 10, wherein the items stored in the queue are temporal service items for which contention arises among the tasks.

18. The computer system of claim 10, wherein the items stored in the queue are spatial service items for which request is issued from the tasks.

19. A computer-readable storage medium containing a program for controlling QoS levels of a plurality of tasks, the program comprising the steps:

a) during a time interval, storing items of the tasks in a queue;

b) executing the items at respective resource utilization rates;

c) detecting QoS levels of the executed items;

d) evaluating the detected QoS levels of the executed items;

e) updating the resource utilization rates with respective differences between a target value and the evaluated QoS levels;

f) determining, from the evaluated QoS levels, whether the detected QoS levels are converging to said target value or diverging from said target value; and

g) during a subsequent time interval, replacing the previously stored items of the queue with new items of the tasks and repeating steps (b) to (f) on the new items if the QoS levels are converging to said target value, and repeating steps (b) to (f) on the previously stored items if QoS levels are diverging from said target value.

20. The computer-readable storage medium of claim 19, wherein step (f) comprises the steps of:

detecting a difference between each of the evaluated QoS levels obtained during a previous time interval and each of the evaluated QoS levels obtained during a most recent time interval; and

comparing the detected difference to a predetermined value, wherein step (g) comprises the steps of;

during said subsequent time interval, replacing the previously stored items of the queue with new items of the tasks and repeating steps (b) to (f) on the new items if the difference is smaller than the predetermined value, and repeating steps (b) to (f) on the previously stored items if the difference is greater than the predetermined value.

21. The computer-readable storage medium of claim 19, wherein step (d) comprises the steps of:

d₁) detecting differences between the detected QoS levels and a QoS lower limit;

d₂) detecting a difference between a QoS upper limit and the QoS lower limit; and

d₃) calculating ratios by dividing the differences of step (d₁) by the difference of step (d₂) to represent the evaluated QoS levels.

22. The computer-readable storage medium of claim 19, wherein step (e) comprises the steps of:

calculating an average value of the evaluated QoS levels;

detecting respective differences between the average value and the evaluated QoS levels; and

updating the resource utilization rates of the first memory with the respective differences.

23. The computer-readable storage medium of claim 19, wherein the differences between the target value and the evaluated QoS levels are weighted differences between the target value and the evaluated QoS levels.

24. The computer-readable storage medium of claim 22, wherein the differences between the average value and the evaluated QoS levels are weighted differences between the average value and the evaluated QoS levels.

25. The computer-readable storage medium of claim 19, wherein the resource utilization rates are utilization rates of a central processing unit.

26. The computer-readable storage medium of claim 19, wherein the items stored in the queue are temporal service items for which contention arises among the tasks.

27. The computer-readable storage medium of claim 19, wherein the items stored in the queue are spatial service items for which request is issued from the tasks.