Load balancing method and apparatus in symmetric multi-processor system

• US 20090019449A1
• Filed: 10/26/2007
• Published: 01/15/2009
• Est. Priority Date: 07/10/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Im, Chae-seok, Choi, Gyu-sang, Lee, Si-hwa
• Granted Patent: US 8,875,151 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

Provided are a load balancing method and a load balancing apparatus in a symmetric multi-processor system. The load balancing method includes selecting at least two processors based on a load between a plurality of processors, from among the plurality of processors, migrating a predetermined task stored in a run queue of a first processor to a migration queue of a second processor, and migrating the predetermined task stored in the migration queue of the second processor to a run queue of the second processor. Accordingly, a run queue of a processor is not blocked while migrating a task, an immediate response of the run queue is possible, and a waiting time of a scheduler is reduced. Consequently, the scheduler can speedily perform context switching, and thus performance of the entire operating system is improved.

Claims

1. A load balancing method, comprising:

(a) selecting at least two processors based on a load between a plurality of processors;

(b) migrating a predetermined task stored in a run queue of a first processor to a migration queue of a second processor, from among the selected processors; and

(c) migrating the predetermined task stored in the migration queue of the second processor to a run queue of the second processor.

2. The load balancing method of claim 1, further comprising

(d) acquiring a lock of the run queue of the second processor,

wherein, when the lock of the run queue of the second processor is acquired, operation (c) migrates all tasks stored in the migration queue of the second processor to the run queue of the second processor, and

when operation (c) is completed, the method further comprising (e) releasing the lock of the run queue of the second processor.

3. The load balancing method of claim 2, further comprising

(f) acquiring a lock of the migration queue of the second processor,

wherein when the locks of operations (d) and (f) are acquired, operation (c) migrates all tasks stored in the migration queue of the second processor to the run queue of the second processor, and

when operation (c) is completed, the method further comprising (g) releasing the lock of the migration queue of the second processor.

4. The load balancing method of claim 1, further comprising

(h) acquiring a lock of the migration queue of the second processor,

wherein when the lock of the migration queue of the second processor is acquired in operation (h), operation (b) migrates the predetermined task stored in the run queue of the first processor to the migration queue of the second processor, and when operation (b) is completed, the method further comprising (i) releasing the lock of the migration queue of the second processor.

5. The load balancing method of claim 4, further comprising

(j) acquiring a lock of the run queue of the first processor,

wherein when the locks of operations (h) and A) are acquired, operation (b) migrates the predetermined task stored in the run queue of the first processor to the migration queue of the second processor, and

when operation (b) is completed, the method further comprising (k) releasing the lock of the run queue of the first processor.

6. The load balancing method of claim 1, further comprising checking whether there is a task stored in the migration queue of the second processor, wherein operation (c) selectively migrates the task stored in the migration queue of the second processor to the run queue of the second processor according to a result of the checking.

7. The load balancing method of claim 1, further comprising checking whether a lock of the migration queue of the second processor, wherein operation (c) selectively migrates the task stored in the migration queue of the second processor to the run queue of the second processor according to a result of the checking.

8. A computer readable recording medium having recorded thereon a program for executing the method of any one of claims 1 through 7.

9. A symmetric multi-processor system, comprising:

a plurality of processors;

a scheduler, which selects at least two processors based on loads of the plurality of processors;

a run queue of a first processor from among the selected two processors, which stores tasks to be performed by the first processor;

a run queue of a second processor, from among the selected two processors, which stores tasks to be performed by the second processor; and

a migration queue of the second processor, which stores tasks migrated from the run queue of a processor other than the second processor,

wherein the scheduler migrates a predetermined task stored in the run queue of the first processor to the migration queue of the second processor, and migrates the task stored in the migration queue of the second processor to the run queue of the second processor.

10. The symmetric multi-processor system of claim 9, wherein the scheduler acquires a lock of the run queue of the second processor, migrates all tasks stored in the migration queue of the second processor to the run queue of the second processor when the lock of the run queue of the second processor is acquired, and releases the lock of the run queue of the second processor when all the tasks are migrated from the migration queue of the second processor to the run queue of the second processor.

11. The symmetric multi-processor system of claim 10, wherein the scheduler acquires a lock of the migration queue of the second processor, migrates all tasks stored in the migration queue of the second processor to the run queue of the second processor when the lock of the migration queue of the second processor is acquired, and releases the lock of the migration queue of the second processor when all the tasks are migrated from the migration queue of the second processor to the run queue of the second processor.

12. The symmetric multi-processor system of claim 9, wherein the scheduler acquires a lock of the migration queue of the second processor, migrates the predetermined task stored in the run queue of the first processor when the lock of the migration queue of the second processor is acquired, and releases the lock of the migration queue of the second processor when the task is migrated from the run queue of the first processor to the migration queue of the second processor.

13. The symmetric multi-processor system of claim 12, wherein the scheduler acquires a lock of the run queue of the first processor, migrates the task stored in the run queue of the first processor to the migration queue of the second processor when the locks of the run queue of the first processor and the migration queue of the second processor are acquired, and releases the lock of the run queue of the first processor when the task is migrated from the run queue of the first processor to the migration queue of the second processor.

14. The symmetric multi-processor system of claim 9, wherein the scheduler checks whether there is a task stored in the migration queue of the second processor, and selectively migrates the task stored in the migration queue of the second processor to the run queue of the second processor based on a result of the checking.

15. The symmetric multi-processor system of claim 9, wherein the scheduler checks whether a lock of the migration queue of the second processor can be acquired, and selectively migrates the task stored in the migration queue of the second processor to the run queue of the second processor based on a result of the checking.