JPH07302246A - Scheduling system - Google Patents

Abstract

PURPOSE:To effectively utilize a cache provided in a processor by considering a process to which a thread belongs in the case of dispatching the thread and dispatching the plural threads altogether. CONSTITUTION:An executable thread recognition means 62 recognizes the number of executable threads connected to an executable thread queue and a thread belonging process recognition means 63 most preferentially recognizes the thread belonging to the same process as the thread of a dispatching object among the executable threads recognized in the executable thread recognition means 62. When the plural threads are recognized in the thread belonging process recognition means 63 and the number of the threads connected to the executable thread queue is larger than a certain specified value, a dispatching means 66 dispatches the plural threads recognized in the thread belonging process recognition means 63 altogether to a prescribed processor. Thus, the cache provided in the processor is effectively utilized.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a scheduling method in an operating system having a multithread structure.

[0002]

2. Description of the Related Art Currently, in many multiprocessor computer systems, each processor has a cache to reduce the number of accesses to a memory and improve the processing speed.

By the way, recently, an operating system having a multi-thread structure capable of defining a plurality of threads in one process has become common. The advantage of this operating system is that threads in the same process can share the same address space, so there is no need to switch the address space when switching threads running on the processor,
The point is that the cache and TLB (table look-up buffer) can be effectively used.

By the way, when a thread processed by a certain processor is switched by preemption or block, the scheduler, which is the process management function of the operating system, selects the thread with the highest priority from the queue of executable threads. Dispatch to the processor.

Here, if there are a plurality of threads belonging to the same process in the queue of executable threads, the probability that these threads will be assigned to the same processor decreases as the number of processors increases.

When a thread is assigned to a processor and a thread in the same process is assigned to the same processor, shared data is likely to remain in the cache of the processor. in this case,
When executing a thread, it is not necessary to bring shared data into the cache from another processor's cache or shared memory. In such cases, the processing time is shortened,
Further, it is efficient in that bus transactions are reduced.

On the other hand, when threads in the same process are assigned to different processors, shared data must be fetched in the cache by each processor, which is inefficient compared to the case of being assigned to the same processor. is there.

In the current multithreaded operating system, when a thread is assigned to a processor, it does not consider which process the thread belongs to. That is, the probability that threads in the same process are executed by the same processor is low, so the cache is not effectively used.

[0009]

Thus, in the current multithreaded operating system operating on the conventional multiprocessor computer system,
When assigning a thread to a processor, we did not consider what process the thread belonged to. As a result, the probability that threads in the same process are executed by the same processor will be low, shared data will be read into the cache by each processor, and the cache equipped in the processor will not be used effectively. There was a problem.

The present invention has been made in consideration of the above circumstances, and when a thread is dispatched, the cache is effectively used by considering the process to which the thread belongs and the processor to be executed. It is an object of the present invention to provide a scheduling method capable of performing.

[0011]

SUMMARY OF THE INVENTION The present invention is a multiprocessor computer system provided with a cache for each processor, which is operated by an operating system having a multithread structure capable of defining a plurality of threads in one process. In the above, in the executable thread recognition means for recognizing the number of the executable threads connected to the queue of the executable threads and the executable thread recognized by the executable thread recognition means, the dispatch target is given the highest priority. There is a certain number of belonging processes recognizing means for recognizing threads belonging to the same process as the thread, and a plurality of threads recognized by the belonging process recognizing means, and the number of threads connected to the queue of the executable threads is a certain value. If there are more than Together multiple threads that are recognized by identification means, characterized by comprising a dispatch unit for dispatching to a predetermined processor.

[0012] Further, each thread dispatched by the dispatch means further comprises a last-execution processor recognition means for recognizing on which processor the thread was last executed, and the dispatch means dispatches the thread on the same processor as the last time. As described above, the dispatch time is adjusted.

[0013]

According to such a configuration, in a multithreaded operating system operating on a multiprocessor computer system, when dispatching a thread, the process to which the thread belongs is taken into consideration, and a plurality of threads are considered. The cache provided in the processor is effectively used by dispatching all the.

[0014]

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 system configuration diagram showing a schematic configuration of a multiprocessor computer system according to this embodiment. As shown in FIG. 1, the multiprocessor computer system is provided with a plurality of CPUs 31, 32, 33. Each CPU 31, 32, 33 is equipped with a cache 34, 35, 36, respectively. CPU31,3
2, 33 are connected to the shared memory 38 via the bus 37.

The shared memory 38 includes CPUs 31, 32,
33 stores an operating system including a function of a scheduler for executing the scheduling method according to the present invention. In the shared memory 38, a queue of executable threads (executable thread queue 3
9) are connected and stored, and the sleep queue 40 is also stored.

FIG. 2 is a functional block diagram showing a configuration for realizing the function of the scheduling system according to the present invention. As shown in FIG. 2, the scheduler 56 of the present invention includes a processor number recognition unit 61, an executable thread recognition unit 62,
Thread belonging process recognition means 63, in-process thread number recognition means 64, previously executed processor recognition means 65,
And the function of the dispatch means 66 is provided.

The processor number recognition means 61 recognizes the number (P) of processors existing in the multiprocessor computer system when the scheduler 56 performs scheduling.

The executable thread recognition means 62 is currently
It recognizes the number (T) of threads that can be simultaneously executed in a multiprocessor computer system. When the number (T) of threads connected to the executable thread queue recognized by the executable thread recognition unit 62 exceeds a specific value (N), the thread belonging process recognition unit 63 determines the number of in-process threads to be described later. If the number of threads recognized by the recognition unit 64 is plural, the threads belonging to the same process as the thread having the highest priority are recognized from the executable thread queue and are collectively removed from the executable thread queue.

The in-process thread number recognition means 64 recognizes the number of threads recognized by the executable thread recognition means 62. When the thread recognized by the executable thread recognition unit 62 is dispatched to any of the plurality of CPUs 31, 32, 33 by the dispatch unit 66, the last-execution processor recognition unit 65 returns to the processor that executed the thread again. The dispatch timing is adjusted so as to be dispatched.

The dispatch means 66 recognizes the plurality of threads recognized by the executable thread recognition means 62 and removed by the thread belonging process recognition means 63 according to the adjustment of the previously executed processor recognition means 65.
Any of the CPUs 31, 32, 33 (the CP that was previously executed
U) is to be collectively dispatched.

Next, the operation of the scheduler 56 of this embodiment will be described with reference to the flow chart shown in FIG. First, when the scheduler 56 receives a schedule request, the processor number recognition unit 11 recognizes the number (P) of processors existing in the multiprocessor computer system (steps S1 and S2).

At the same time, the scheduler 56 uses the executable thread recognition means 62 to recognize the number (T) of currently executable threads connected to the executable thread queue in the shared memory 38 (step S3). ).

For example, here, as shown in FIG. 4, there are two processes P1 and P2 in the system, and a plurality of threads belonging to the respective processes P1 and P2 (T11, T12, It is assumed that T13 and process P2 have T21 and T22).

In the shared memory 38, there are an executable thread queue for connecting the threads in the executable state and a sleep queue for connecting the threads in the sleep state. As shown in FIG. 1, threads belonging to different processes are mixed in each queue.

Number of threads that can be executed in the system (T)
If the number of threads (T) that can be executed in the multiprocessor computer system exceeds a certain value (N) as a result of recognizing the above, the scheduler 56 collects a plurality of (M) executable threads. Remove from the runnable thread queue.

That is, if the number of threads (T) is larger than a certain value (N), the scheduler 56 first sets the thread having the highest priority, that is, the head of the executable thread queue 17, based on the priority control. Remove the thread (T11) located.

It should be noted that the certain value (N) is a reference value for determining whether or not the number of threads is sufficiently effective by applying the scheduling method according to the present invention. That is, when the number of threads is smaller than the specific value (N), this method may not be used because it does not cause a big problem. However, when the number of threads is larger than the specific value (N), this method is used. A large effect can be obtained by performing the scheduling used.

The scheduler 56 recognizes the threads belonging to the same process as the thread T11 from the executable thread queue, that is, the threads T12 and T13 in the example shown in FIG. The belonging threads T11, T12, T13 are collectively removed from the executable thread queue (steps S5, S6).

Next, the scheduler 56 dispatches M (three in the example) threads removed from the executable thread queue to, for example, the CPU 31 (41 in FIG. 1).
Yes (step S8).

At this time, the scheduler 56 adjusts the dispatch timing by the last-execution processor recognition means 18 of the thread so that the thread is re-dispatched to the last-executed processor as much as possible.

The CPU 31 sequentially executes the M threads dispatched collectively. At this time, the dispatched M threads do not return to the queue until all the executions are completed, and remain allocated to the CPU 31 (step S9). At this time, if shared data handled by a plurality of allocated threads is stored once in the cache 34, the shared memory 38 and the caches 35, 36 of the other CPUs 32, 33 are executed each time each thread is executed. There is no need to read the data stored in.

When the execution of all the M threads is completed, the scheduler 56 returns the M threads to the executable thread queue or the sleep queue collectively (42 in FIG. 1, step S10).

In this way, the threads belonging to the same process are collectively C from the plurality of threads connected to the executable thread queue stored in the shared memory 38.
By dispatching to the PU 31, it is possible to use shared data stored in the cache 34 and shared by a plurality of threads when executing each thread.
That is, there is a low possibility that data will need to be read into the cache 34, processing time will be shortened, and the bus 37
It is possible to reduce the transaction amount of.

By returning the threads executed by the CPU 31 collectively instead of returning them one by one, it is possible to prevent the threads belonging to the same process from being distributed again. As a result, threads belonging to the same process can be prevented from being scheduled to different CPUs one by one, and the cost can be reduced.

Further, when dispatching threads collectively, by adjusting so that they are dispatched to the same CPU as the previous time, it is unspecified that the data stored at the time of the previous dispatch in the cache may remain. C
Higher than when dispatching to PU, so each CPU
Caches 34, 35 provided in 31, 32, 33,
36 can be effectively used.

[0036]

As described above, according to the present invention, when a thread is dispatched in an operating system having a multi-thread structure, a cache can be created by considering a process to which the thread belongs and a processor to execute the thread. It can be effectively used.

[Brief description of drawings]

FIG. 1 is a system configuration diagram showing a schematic configuration of a multiprocessor computer system according to an embodiment of the present invention.

FIG. 2 is a functional block diagram showing a configuration for realizing the function of the scheduling system according to the present invention.

FIG. 3 is a flowchart for explaining an operation procedure of the scheduling method according to the present embodiment.

FIG. 4 is a diagram showing an example of a process in this embodiment.

[Explanation of symbols]

31, 32, 33 ... CPU, 34, 35, 36 ... Cache, 37 ... Bus, 38 ... Shared memory, 36 ... Scheduler, 61 ... Processor number recognition means, 62 ... Executable thread recognition means, 63 ... Thread belonging process recognition Means, 64 ... In-process thread number recognition means, 65 ... Previously executed processor recognition means, 66 ... Dispatch means

Claims (3)

[Claims] 1. In a multiprocessor computer system provided with a cache for each processor, which is operated by a multithread structure operating system capable of defining a plurality of threads in one process, a queue of executable threads is provided. An executable thread recognition unit that recognizes the number of connected executable threads, and among the executable threads recognized by the executable thread recognition unit, belongs to the same process as the thread that is the dispatch target with the highest priority. If a plurality of threads are recognized by the belonging process recognition means for recognizing threads and the belonging process recognition means, and the number of threads connected to the queue of the executable threads is larger than a certain specific value, Recognized by belonging process recognition means A scheduling method comprising: a dispatching unit that dispatches a plurality of threads together to a predetermined processor. 2. The scheduling method according to claim 1, wherein the plurality of threads dispatched by the dispatching unit are collectively executed by a processor and then returned to the queue of executable threads collectively. 3. The previously executed processor recognition means for recognizing on which processor each thread dispatched by the dispatch means was executed last time, the dispatch means dispatches the thread on the same processor as the last time. The scheduling method according to claim 1, wherein the dispatch timing is adjusted so as to do so.