JPH05233562A - Process control system for multiprocessor - Google Patents

Abstract

(57) [Summary] [Object] The present invention provides a global run queue on a shared memory that can be accessed by all processors that temporarily store processes that move between local run queues. It is characterized by controlling the amount. [Configuration] Each processor 11-0, 1 on the shared memory 13
1-1, ... Provide a global run queue GR for temporarily placing the process MP to be moved, and local run queues LR0, LR1 ,. Means for temporarily linking the migration target process MP to the global run queue GR with the lock operation to the processors 11-0, 11-1, ..., And the migration target process MP.
Means for unlinking from the global run queue GR with a lock operation and linking to the local run queue of its own.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a process management system applied to a shared memory type multiprocessor system, and more particularly to a multiprocessor characterized by a movement processing control mechanism of a process to be processed between processors. Process management method.

[0002]

2. Description of the Related Art Conventionally, in a shared memory multiprocessor system, when a process (task, job, thread, etc.) is dispatched, a scheduler (dispatcher) of each processor has a run queue (global) accessible by all processors. The runnable process was taken out from the run queue.

In a multiprocessor system, the scheduler needs to lock the run queue when it operates, so that when one processor is performing the run queue operation, the other processor cannot perform the run queue operation. Therefore, when a plurality of processors try to operate the run queue at the same time, there is a problem that the throughput does not increase because the locks collide.

To solve this problem, [Thomas E.
Anderson, Edward D. Lazowska, Henry M. Levy "Th
e Performance Implication of Thread Management Alt
ernatives for Shared-Memory Multiprocessors ", IE
EE Transactions on Computers Vol.38], a run queue (local run queue (also called ready queue)) for each processor is set instead of the run queue (global run queue) accessible from all processors, and the scheduler of each processor can execute. It proposes to improve the throughput by operating the run queue without locking when fetching a process.

However, in this case, the number of runnable processes linked to each local run queue is not uniform, and the load balance between the processors cannot be balanced, which causes variations in the response between processes. In addition, there is a problem that a process in a waiting state occurs despite the existence of an idle processor.

[0006]

As described above, in the conventional shared memory type multiprocessor system, when a plurality of processors try to operate the global run queue at the same time, the lock does not collide, so that the throughput does not increase. There was a problem.

In order to solve this problem, it has been proposed that a local run queue is provided for each processor instead of the global run queue and the processor operates only its own local run queue to improve the throughput. There was a problem that the load balance between the processors could not be balanced.

The present invention has been made in view of the above circumstances,
In order to eliminate the above-mentioned drawbacks of the prior art, a global run queue that temporarily stores processes that move between local run queues is provided, and a process linked to the local run queue of a processor with a high load is processed through the global run queue. By moving to the local run queue of the processor with a low load, the load is balanced among the processors, which causes variations in the response between processes, and even when there is an idle processor, it is waiting for execution. It is an object of the present invention to provide a process transfer method that solves problems such as process generation.

[0009]

To achieve the above object, in the present invention, a local run queue is provided in a shared memory type multiprocessor system having a local run queue in which executable processes are linked for each processor. A global run queue accessible by all processors that temporarily stores processes that move between them is provided, and a processor having a migration source local run queue of the migration target process unlinks the migration target process from the migration source local run queue. A processor having a means for temporarily linking to the global run queue with a lock operation and a destination local run queue unlinks the migration target process from the global run queue with a lock operation, Lankyu And having a means for linking to.

[0010]

In the shared memory type multiprocessor system configured as above, when a processor with a high load dispatches a process, the processor with a heavy load unlinks the process in its own local run queue. , Link to Global Run Queue with lock operation. Also, when dispatching is performed on a processor with a low load,
Examine the above global run queue, and if there is a process in the global run queue, unlink the process from the global run queue with the lock operation,
Move the process by linking to its own local run queue.

By such process migration processing, a process is migrated from a processor with a heavy load to a processor with a light load, so that the load is balanced among the processors, the variation in the response between the processors is reduced, and the parallel processing with high throughput is achieved. Processing becomes possible.

[0012]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing an outline of the present invention.

In the figure, 11-0, 11-1, ..., 11-n
Is a processor having its own local run queues LR0, LR1, ..., LRn to which executable processes are respectively linked. Here, the processor 11-n having the local run queue LRn is set as a target process (M).
The processor 11-1 having the local run queue LR1 in P) is shown as the destination processor. 12 is each processor 11-0, 11-1, ...
The bus (BUS) interconnects system components including 1-n and a shared memory (CM) 13.

Reference numeral 13 is each of the processors 11-0, 11-1,
..., 11-n is a shared memory (CM) shared. On this shared memory (CM) 13, each processor 11-0,
11-1, ..., 11-n connect the global run queue GR for temporarily placing the migration target process (MP) and the local run queues LR0, LR1 ,. , LR
n and are provided. Here, the local run queue LRn
Becomes the source local run queue, and the local run queue LR1 becomes the destination local run queue.

In FIG. 1, each processor 11-0,
11-1, ..., 11-n respectively execute processing for process migration. In this process, processor 11-n
Scheduler checks the number of processes connected to each local run queue LR0, LR1, ... Including its own local run queue LRn, and checks its own local run queue LRn.
When the number of processes connected to is larger than the number of processes within a range that complies with a certain condition, each processor 11-0, 11-
Processes that can be processed by other processors (movement target processes) MP are self-local run queue LR so that the processing load on 1, ..., 11-n is equalized within a certain range.
It is unlinked from n and linked to the global run queue GR with a lock operation (see the symbol a in the figure).

On the other hand, the scheduler of the processor 11-1 checks the number of processes connected to each of the local run queues LR0, LR2, ... When the number of processes to be moved (MP) is less than the number of processes within the range according to a certain condition and the process to be moved (MP) is connected to the global run queue GR, the process to be moved (MP) is unlinked from the global run queue GR with a lock operation, and the local process is executed. It is linked to the run queue LR1 (see symbol b in the figure).

As described above, when a processor with a high load dispatches a process, the processor unlinks the process in its own local run queue and then links it to the global run queue while performing a lock operation. When a dispatch is performed by a low processor, the processor examines the global run queue, and when there is a process in the global run queue, the process is unlinked from the global run queue with a lock operation and linked to the local run queue. Move process.

By the process migration processing as described above, the migration target process (MP) is so arranged that the processing loads on the processors 11-0, 11-1, ..., 11-n are equalized within a certain range. Move between local run queues (LR), and parallel processing is efficiently executed in a shared memory type multiprocessor system. FIG. 2 is a block diagram showing the configuration of the first embodiment according to the present invention.

The shared memory type multiprocessor system of the embodiment shown in FIG. 2 has three processors 11-0, 1
1-1, 11-2 and the same processor 11-0, 11-1, 11-2
Each processor 11 connected to the
-Shared memory (CM) 13 shared by 0, 11-1, 11-2
Composed of and.

On the shared memory (CM) 13, each of the processors 11-0, 11-1, 11-2 is a process to be moved (M
Global run queue G for temporarily storing P)
R, the local run queues LR0, LR1, and LR2 that connect the processes executed by the respective processors to each of the processors 11-0, 11-1, and 11-2, and the local run queues LR0, LR1, and LR2. The processor 11-0 has local run queue counters LRC0, LRC1, and LRC2 for storing the number of processes, respectively. The processor 11-0 has a local run queue LR0 and a local run queue counter LRC0.
The local run queue LR1 and the local run queue counter LRC1 are provided in the processor 11-2, and the local run queue LR2 and the local run queue counter L are provided in the processor 11-2.
RC2 corresponds to each.

The above local run queue counters L
RC0, LRC1, and LRC2 change their values when their own local run queues are manipulated, such as process creation, process deletion, and movement between processors.

For example, in FIG. 2, there are five processes (P) in the local run queue LR0, eight processes (P) in the local run queue LR1, and a local run queue L.
It is assumed that two processes (P) are connected to R2.

The schedulers of the processors 11-0, 11-1, and 11-2 perform processing for moving the process, for example, every 1 second, and further, for example, once every 5 seconds, the processing moves. After executing, check whether there is a starvation process in the global run queue GR by checking whether the process is connected to the global run queue GR, and if so, lock it. While Global Rankue GR
Unlink more and link to your local run queue. The process created by each processor is linked to its own local run queue. The operation of the embodiment shown in FIG. 2 will be described with reference to FIG.

Now, for example, when the processor 11-1 starts processing for process migration, the scheduler of the processor 11-1 causes the local run queue counters LRC0, LRC1 of the processors 11-0, 11-1, 11-2 to be executed. , LR
The value of C2 is read and each local run queue LR0 is currently read.
, LR1, LR2, the number of processes connected is checked (step 301 in FIG. 3).

The scheduler moves a process to the global run queue GR, or derives a condition to take out a process from the global run queue GR.
In this example, the other local run queues LR0, LR2
The number of processes connected to its own local run queue LR1 is subtracted from the number of processes connected to each other to obtain the minimum and maximum values of the calculation results (step 30 in FIG. 3).
2).

If the maximum value is larger than a certain value, the global run queue GR is checked, and if there is a process, the process is linked to its own local run queue LR1 (steps 303, 304, 306, 30 in FIG. 3).
7, 308).

When the minimum value is a positive value, this processor 11-1 is all processors 11-0, 11-1, 11
-The number of processes is the smallest among -2, so the global run queue G is the same as when the maximum value is larger than a certain value.
R is checked, and if there is a process, the process is linked to its own local run queue LR1.

When the minimum value is a negative value and the absolute value of the minimum value is larger than a certain value, the process to be moved (MP) is selected from among the processes connected to the local run queue LR1. , The migration target process (MP) is migrated to the global run queue GR (FIG. 3).
Steps 305, 309, 310).

However, when both of the above two conditions are satisfied,
That is, when the minimum value is a negative value, and the absolute value of the minimum value is larger than a certain fixed value and the maximum value is larger than a certain fixed value, this processor 11-1 sends
Since the process is moved alternately between the local run queue LR1 and the global run queue GR, in order to avoid such a phenomenon, the process moving process is terminated without doing anything (step 303 in FIG. 3). If the above conditions are not satisfied, nothing is done and the process movement process ends.

By the process migration control described above, for example, when the threshold value (a certain number of processes) is set to "4", the values of the local run queues LR0, LR1 and LR2 read by the processor 11-1 are used as the basis. When the process migration condition is calculated, the local run queue counter LRC
The value of 0 is "5", the local run queue counter LRC1
Is 8 and the value of the local run queue counter LRC2 is 2, so LRC0-LRC1 = -3 LRC2-LRC1 = -6 Therefore, the minimum value is "-6" and the maximum value is "-3". (Step 302 in FIG. 3).

As a result, the scheduler of the processor 11-1 unlinks one of the processes connected to the local run queue LR1 from the queue as the process to be moved (MP), and the local run queue counter LRC
After changing the value of 1 to "7", move the process (MP) to be moved to the global run queue GR while performing the lock operation.
To end the series of processing (step 30 in FIG. 3).
3, 304, 305, 309, 310).

Next, when the process for moving the process starts in the processor 11-0, the scheduler of the processor 11-0 causes the local run queue counters LRC0, LRC1 of the processors 11-0, 11-1, 11-2 to operate. , LRC2
After reading the value of, the difference between the local run queue counters LRC1 and LRC2 of the other processors 11-1 and 11-2 and the local run queue counter LRC0 is calculated, and the minimum value and the maximum value are calculated (step 301 in FIG. 3, FIG. 3). Thirty
2). As a result, the minimum value is "-3" and the maximum value is "2", so that the process is terminated without doing anything.

Next, when the processor 11-2 starts the process for process migration, the scheduler of the processor 11-2 causes the local run queue counters LRC0, LRC1 of the processors 11-0, 11-1, 11-2 to be executed. , LRC2
After the value of is read out, the difference between the local run queue counters LRC0 and LRC1 of the other processors 11-0 and 11-1 and the local run queue counter LRC2 is calculated, and the minimum value and the maximum value are calculated (step 301 in FIG. 3). , 30
2).

As a result, since the minimum value is "3" and the maximum value is "5", the scheduler of the processor 11-2 checks whether or not there is a process in the global run queue GR (step 304 in FIG. 3, FIG. 3). 306).

In this case, since the process to be moved (MP) exists, the scheduler of the processor 11-2 unlinks the process to be moved (MP) from the queue while performing a lock operation on the global run queue GR, It links to the local run queue LR2 and changes the value of the local run queue counter LRC2 to "3" (steps 307 and 308 in FIG. 3).

By these operations, it is possible to move a process in a high-load processor to a low-load processor without a lock operation for the local run queue. Further, in this example, one process is moved, but it is also possible to move a plurality of processes at the same time.

In the above embodiment, in order to move the process to the global run queue GR or to derive the condition for taking out the process from the global run queue GR,
Calculate the difference between the number of processes connected to other local run queues and the number of processes in your local run queue,
By calculating the minimum and maximum values of the calculation results, we are investigating how much the number of processes varies among processors. However, this is not the only option, and in addition to this, for example, the value of each local run queue counter Calculate the average value, and the number of processes in the local run queue is (average value) +
If it is equal to or larger than (a certain fixed number of processes), the process of connecting the process in the local local run queue to the global run queue GR is performed, and the number of processes in the local local run queue is (average value)-(a certain fixed number of processes). If it is equal to or smaller than), the process can be moved by operating to acquire the process from the global run queue GR.

For example, the threshold value (a certain number of processes) which is a part of the process movement conditions is set to "3", and the decimal point of the average value is rounded up, and the processor 11-1 in FIG. If you start the process for moving,
The scheduler of the processor 11-1 is the processor 11-
Local run queue counters LR for 0, 11-1, 11-2
After reading the values of C0, LRC1 and LRC2, the average value is calculated.

The average value at this time is (5 + 8 + 2) / 3 =
Therefore, the condition value for passing the process to the global run queue GR is “8”, and the condition for receiving the process from the global run queue GR is “2”. Comparing these values with the value "8" of the local run queue LR1,
Since the condition for passing the process to the global run queue GR is satisfied, the processor 11-1 unlinks one of the processes (P) connected to its own local run queue LR1 from the queue as the process to be moved (MP), and then the local run queue The counter LRC1 is updated to "7" and linked to the global run queue (GR) with a lock operation.

Next, when the process for moving the process starts in the processor 11-0, the scheduler of the processor 11-0 causes the local run queue counters LRC0, LRC1 of the processors 11-0, 11-1, 11-2 to operate. , LRC2
After reading the value of, the average value is calculated and the process movement condition is obtained.

In this case, the average value is (5 + 7 + 2) / 3 =
Since it is 4.67, if it is rounded up to "5", the condition value for passing the process to the global run queue GR is "8", and the condition for receiving the process from the global run queue GR is "2". Since the value of the local run queue counter LRC0 is "5", the process is ended without performing anything.

Next, when the processor 11-2 starts processing for process migration, the scheduler of the processor 11-2 causes the local run queue counters LRC0 and LRC1 of the processors 11-0, 11-1, and 11-2 to be executed. , LRC2
After reading the value of, the average value is calculated and the process movement condition is obtained.

In this case, the average value is (5 + 7 + 2) / 3 =
Since it is 4.67, if it is rounded up to "5", the condition value for passing the process to the global run queue GR is "8", and the condition for receiving the process from the global run queue GR is "2". Comparing these values with the value "2" of the local run queue counter LRC2, the condition for receiving the process from the global run queue GR is satisfied, so the processor 11-2 moves from the global run queue GR with the lock operation from the process to be moved ( MP), and then local run queue L
Linked to R2, own local run queue counter LRC
Update the value of 2 to "3". Therefore, as in the above-described example, it is possible to move a process from a process with a high load to a process with a low load.

In the above embodiment, a processor (1
1-i) created the process (P), the process (P) was linked to its own local run queue (LRi), but the created process (P) is regarded as the migration target process (MP). , Process migration is performed before linking to the local local run queue (LRi), and if the load on the local processor (11-i) is low, the process created in the local local run queue (LRi) is linked to the local processor. When the load of (11-i) is high, the process created in the global run queue GR is linked to prevent an increase in the load of the processor due to the linking of the newly created process to the processor having a high load. The load can be equalized by moving the process to a processor with lower load.

For example, in the case of using the process migration procedure of FIG. 3 in the embodiment of FIG. 2, when the processor 11-1 creates a process, the processor 11-1 executes the process migration process, Check whether the conditions for movement are met.

In this case, since the minimum value is "-6" and the maximum value is "-2", the processor 11-1 performs the global run queue G while locking the generated process.
Link to R.

After that, when the process migration process is executed by the processor 11-2 having a low load, the process linked to the global run queue GR is linked to the local run queue LR2, so that the load is high. It is possible to move a process to a lightly loaded processor without increasing the processor load.

In the above embodiment, the global run queue G
The migration target process connected to R is the migration target process when the processor performs the process migration process and satisfies the condition for acquiring the process from the global run queue GR, and when the global run queue GR is checked at a certain interval. It was moved to the processor's local run queue if it existed. For this reason, the processes connected to the global run queue GR are executed for a long time.
The process may be delayed or moved to a heavily loaded processor.

Therefore, the processor that has moved the process to the global run queue GR issues an interrupt to the processor to which the process to be transferred is to be transferred, and the processor that has received the interrupt transfers the process to be moved in the global run queue GR to its own local run queue. By moving, it becomes possible to equalize the load on each processor without waiting for the execution of the process in the global run queue GR for a long time. FIG. 4 shows a second embodiment of the present invention.

In FIG. 4, priority counters PC0, PC1 and PC2 for storing the total sum of priorities of the respective processes (P) in FIG. 2 are newly added to the shared memory (CM).
Each processor 11-provides a condition for moving a process provided above.
The case where the migration condition of the process is derived from the average value of the priorities of the processes connected to the local run queues 0, 11-1, 11-2 is shown.

For example, the priority value of the process with the highest priority is "1", the priority value of the process with the lowest priority is "10", and the process to be moved has a high priority in a processor with a small average priority value. It is assumed that the process of (3) is moved to a process having a high average priority value, and the local run queue LR0 has three processes (P), the local run queue LR1 has five processes (P), and the local run queue LR2 has four processes (P). Suppose that they were connected.

The number in the process (P) indicates the priority value, and the priority counter PC0
Is (8 + 10 + 9) = 27, the priority counter PC1 is (2 + 1 + 4 + 1 + 2) = 10, and the priority counter PC2 is (3 + 7 + 4 + 6) = 20.
Are stored respectively.

Now, when the process migration processing is started in the processor 11-1, the scheduler of the processor 11-1 has the local run queue counters LRC0, LRC1, LRC2 in the processors 11-0, 11-1, 11-2.
After reading the values of the priority counters PC0, PC1 and PC2, the average value of the priority for each processor is calculated, and the minimum and maximum values of the average value are obtained.

In this example, the average priority value of the processor 11-0 is 27/3 = 9, the average priority value of the processor 11-1 is 10/5 = 2,
The average value of the priority of -2 is 20/4 = 5, so the minimum value is "2" and the maximum value is "9".

When this result is compared with the average value "2" of the priorities of the own processor 11-1, it is the minimum value. Therefore, the scheduler of the own processor 11-1 is in the process (P) in the own local run queue LR1. After unlinking the process with the highest priority (here, the process with priority 1) from the queue as the process to be moved (MP), the value of the local run queue counter LRC1 is set to "4" and the priority counter PC
The value of 1 is updated to "9", the global run queue GR is linked with the lock operation, and the processing ends.

Next, when the process migration process is started by the processor 11-2, the scheduler of the processor 11-2 causes the local run queue counters LRC0, LRC1, respectively in the processors 11-0, 11-1, 11-2. LRC2
After reading the values of the priority counters PC0, PC1 and PC2, the average value of the priority for each processor is calculated, and the minimum and maximum values of the average value are obtained.

The average priority value of the processor 11-0 is 27 ÷ 3 = 9, the average priority value of the processor 11-1 is 9 ÷ 4 = 2.25, and the average priority value of the processor 11-2 is 20 ÷ 4. = 5, so the minimum value is "2.25" and the maximum value is "7". When this result is compared with the average value "5" of the priorities of the own processor 11-2, since neither of them corresponds, the process ends without performing anything.

Next, when the process migration is started by the processor 11-0, the scheduler of the processor 11-0 sets the local run queue counters LRC0, LRC1, LRC2 of the processors 11-0, 11-1, 11-2 to the local run queue counters LRC0, LRC1, LRC2. After reading the values of the priority counters PC0, PC1 and PC2, the average value of the priority for each processor is calculated, and the minimum value and the maximum value of the average value are obtained.

The average priority value of the processor 11-0 is 27 ÷ 3 = 9, the average priority value of the processor 11-1 is 9 ÷ 4 = 2.25, and the average priority value of the processor 11-2 is 20 ÷ 4. = 5, so the minimum value is "2.25" and the maximum value is "9".

When this result is compared with the average value "9" of the priorities of the own processor 11-0, the result matches the maximum value, so the scheduler of the own processor 11-0 causes the global run queue GR to perform a lock operation from the process to be moved. After unlinking (MP), it is linked to its own local run queue LR0, the value of its own local run queue counter LRC0 is set to "4", and its own priority counter P
The value of C0 is updated to "28", and the process ends.

Therefore, by moving a high-priority process from a processor having many high-priority processes to a processor having many low-priority processes, the load balance among the processors is balanced and the variation in the response between the processors is reduced. It will be possible. FIG. 5 shows a third embodiment of the present invention.

In a shared memory type multiprocessor system as shown in FIG. 2, when the number of processors increases,
When the variation among the processors becomes large, the global run queue is frequently accessed, so that the lock requests from the respective processors to the global run queue collide with each other, which may reduce the processing capability of the entire system.

In order to solve this, in the embodiment of FIG. 5, eight processors (11-0, 11-1, ..., 11-7) are used.
, Two global run queues GR0 and GR1 are provided for the processors 11-0, 11-1, 11-2 and 11-3.
Global run queue GR1 for 1-5, 11-6, 11-7
By allocating each of them to distribute access to the global run queue, it becomes difficult for the access to the global run queue to become a bottleneck, and it is possible to prevent a decrease in the processing capacity of the entire system.

Therefore, by combining the above embodiments and moving the process from the processor with a high load to the processor with a low load, the load of each processor can be balanced, the variation of the response between the processors is small, and the parallel processing with high throughput is achieved. Processing can be realized.

[0065]

As described in detail above, according to the present invention,
In a shared memory type multi-processor system having a local run queue in which processes that can be executed for each processor are linked, a global run queue that temporarily stores processes that move between local run queues and that can be accessed by all processors is provided. By moving from a processor with a high load to a processor with a low load via the global run queue, the load of each processor can be balanced, and the variation in the response between the processors is small, and parallel processing with high throughput can be realized.

[Brief description of drawings]

FIG. 1 is a block diagram showing a system configuration for explaining an outline of the present invention.

FIG. 2 is a block diagram showing the configuration of the first embodiment of the present invention.

FIG. 3 is a flowchart showing a process movement processing procedure in the embodiment of the present invention.

FIG. 4 is a block diagram showing the configuration of a second embodiment of the present invention.

FIG. 5 is a block diagram showing the configuration of a third embodiment of the present invention.

[Explanation of symbols]

11 (11-0, 11-1, ...) ... Processor, 12 ... Bus (BUS), 13 ... Shared memory (CM), LR (LR0
, LR1, ...) ... Local run queue, GR (GR0
, GR1) ... Global run queue, LRC (LRC0
, LRC1, ...) ... Local run queue counter, P
C (PC0, PC1, ...) ... Priority counter,
P ... Process, MP ... Process to be moved.

Claims (1)

[Claims] 1. In a shared memory multiprocessor system having a local run queue in which processes executable for each processor are linked, a global run queue accessible from all processors for temporarily storing a process moving between local run queues. Unlink the process to be moved from its own local run queue and temporarily link it to the global run queue while performing a lock operation, and unlink the process to be moved from the global run queue while performing a lock operation. , A process management system in a multiprocessor, comprising: a processing means of a processor linked to its own local run queue.