JPH07200314A - Cooperative scheduling system for parallel job - Google Patents

Abstract

PURPOSE:To attain the two-layer scheduling with cooperation and the scheduling intended by the user and to reduce the execution time by allowing a task scheduler to recognize thread information managed by the operating system. CONSTITUTION:A task scheduler 101 requests thread generation to an operating system 102 based on divided tasks and a means 110 making generation request in the standby state when an optimum thread number 106 is exceeded. Furthermore, when a thread enters a sleep state, a means 112 uses to set a thread 103 in the standby state to an executionable state 104 so that number of executionable threads 104 is not less than an optimum thread number 106. In the switching state of tasks, the task scheduler 101 compares an executionable thread number 105 and the optimum thread number 106 and a thread standby processing means 111 is used to set the executionable not so as to exceed the optimum thread number 106 to the utmost.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a collaborative scheduling method for parallel jobs, for example, in the processing of a parallel program that frequently generates IOs, etc. Related to the cooperative scheduling method of.

[0002]

2. Description of the Related Art A conventional job scheduling method will be described. Here, a job is a program or command submitted by the user.

Traditional operating system scheduling concepts have evolved from machines with a single processor. A management unit called a process is prepared for assigning a job to a processor. Jobs are made to appear to be multi-processed by using one physical processor in a time division manner and alternately processing a plurality of processes.

On the other hand, the basic idea is the same in a parallel operating system employing a multi-thread mechanism, and a management unit called a thread is set as a processor allocation unit. It is possible to process one process in parallel by preparing a plurality of threads in one process and independently scheduling them in the physical processor.

Further, an interface for a user to use parallel processing is realized by a parallel library. This parallel library will be called the task scheduler. By inserting a parallel processing instruction into the program, the user can divide the program into tasks, which are the processing units of the parallel processing, and instruct scheduling such as synchronization and exclusion of individual tasks.

A conventional parallel job scheduling method will be described with reference to FIG.

In the user program 203, instructions regarding the number of threads 205 used by the program and scheduling of the tasks 204 are written. The task scheduler 201 selects and moves a task according to the scheduling instructed by the user. If the number of threads 206 generated is smaller than the instructed number of threads 205, the operating system 202 is requested to generate, but when the number of threads 206 equals the instructed number of threads 205, no further generation request is made. Physical processor 2
Since the operating system 202 allocates the thread 206 to 07, the configuration has a two-tier scheduling of the operating system 202 and the task scheduler 201. In the conventional two-layer scheduling, the task scheduler 201 has a structure in which scheduling by the operating system 202 is not taken into consideration.

[0008]

In the conventional parallel job scheduling method, although the mechanism for the user to use the parallel processing is realized by the task scheduler, the assignment of the work to the physical processor is all done by the operating system. It depends on the system scheduling. The user regards the thread as a physical processor and instructs the scheduling of the stack, but the task scheduler does not actually recognize on which physical processor the thread is processed. In the two-level scheduling by the task scheduler and the operating system, there is the following problem because there is almost no information exchange and there is no cooperation.

1. Usually, the number of threads instructed by the user is fixed, and the user considers threads = physical processors to instruct the operation of tasks. At this time, one of the running tasks
When one issues an IO, the thread goes to sleep in the operating system waiting for IO completion.
Then, the number of threads that can be used is reduced by one, and even if there is another executable task, it cannot be processed.

2. When the number of threads to be instructed is increased, even if one of the threads enters the sleep state with IO, the operating system can move the remaining threads. Therefore, 1. The problem of can be avoided to some extent.
However, since the thread scheduling is performed by the operating system, there are cases where the timing at which the task operates differs from the timing intended by the user, and the scheduling intended by the user may not be possible.

An object of the present invention is to propose a cooperative scheduling method for causing a task scheduler to recognize information on threads managed by an operating system in a conventional parallel job scheduling method, thereby providing a two-layer scheduling with cooperation. It is possible to realize the desired scheduling, to enable the user's intended scheduling, and to further reduce the execution time.

[0012]

In order to solve the above problems, the cooperative scheduling method for parallel jobs of the present invention is an operating system that arranges a multi-thread mechanism and each task of parallel jobs is scheduled on a thread. The scheduling method realized by the two layers of the task scheduler is composed of the following means.

1. 1. A means for creating a thread in a waiting state that is not a scheduling target in the operating system. 2. A means for putting a thread in a waiting state into a runnable state which is a scheduling target; 3. A means for putting a thread in a ready state into a waiting state, 4. A means for confirming the number of ready-state threads managed in the operating system in the library layer, A means of terminating a waiting thread.

[0014]

The operation will be described using the overall configuration of the present invention shown in FIG.

In the task scheduler 101, the operating system 102 is requested to create a thread in accordance with the task division, and when the optimum number of threads 106 is exceeded, the thread is switched to a means 110 for requesting a thread to be created in a standby state. Further, when the thread enters a sleep state such as waiting for IO, the thread 103 in the standby state is placed in the ready state 104
It is possible to prevent the number of executable threads 104 from falling below the optimum number of threads 106 by using the means 112.

The number of threads 105 in the ready state may become larger than the optimum number of threads 106 due to the threads such as IO waiting returning from the sleep state to the ready state 104. In this case, when the task is switched, the task scheduler 101 compares the number of executable threads 105 and the optimum number of threads 106, and the thread waiting unit 111
By using, the number of executable threads 105 is prevented from exceeding the optimum number of threads 106 as much as possible.
As a result, the number of executable threads 104 can be controlled so as not to increase too much, the unnecessary scheduling of the operating system 102 can be minimized, and the task scheduler 101 can perform the scheduling intended by the user.

At the end of the process, the thread 103 in the waiting state is placed in the running state and the termination process is performed, so that the complete termination process of the process is guaranteed.

[0018]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The operation and effect of the present invention will be described step by step, taking a simple program that operates according to the flow shown in FIG. 3 as an example. In the program shown in FIG. 3, the root task 301 is divided into a task 1 (302) including IO and a task 2 (303) including only calculation processing, and finally the processing is ended in synchronization.

The operation of each means constituting the present invention will be described with reference to the examples of FIGS.

FIG. 4 shows an example of a state in which threads are created in a waiting state according to task division. Task 401 is 3
Although the number of processors 403 is two, the conventional method can generate only two threads. In the present invention, instead of creating the third thread, it is created as a wait state 404 that is not the scheduling target of the operating system.

FIG. 5 shows an example in which the thread in the waiting state is set to the runnable state. Task 501 that was running
When one of them enters the sleep state 505 such as waiting for IO, the thread stops while it remains paired with the task. At this time, by setting the threads in the waiting state 504 to the READY state 502, the number of READY threads 502 corresponding to the number of the processors 503 can be secured and the task 501 can be processed.

FIG. 6 shows means for confirming the number of executable threads from the task scheduler. At the start of the program, the operating system 602 is requested for the address of the area 604 in which the number of executable threads fits. In the system space, there is an area 603 that can be seen from the user space, and the operating system creates an area 604 that stores the number of executable threads in this area and returns the address to the task scheduler. By tracing this address from the task scheduler 601, the number of executable threads can be confirmed freely.

FIG. 7 shows an example of a case where a thread in the ready state is placed in the waiting state. When the thread 705 that has been in the sleep state waiting for IO returns to the executable state due to the completion of the IO, the state in which the executable thread 702 is redundant by one is temporarily generated. When one of the tasks 701 switches in the user space in this state, the operating system sets the thread of the task to the waiting state 704 after confirming that the number of executable threads is excessive. To request.

FIG. 8 shows an example of terminating a thread in a waiting state. Thread 80 in wait state at process end
Instead of leaving 4 as it is, the thread is terminated by sending the KILL signal 805 after once setting the ready state 802.

[0025]

As described above, according to the present invention,
Tasks can be scheduled by always securing the optimum number of threads. As a result, the scheduling intended by the user becomes possible and the execution time can be shortened.

[Brief description of drawings]

FIG. 1 is an overall configuration of the present invention

FIG. 2 Conventional scheduling method

FIG. 3 is a program flow of an embodiment of the present invention.

FIG. 4 is an example of a state in which threads are created in a waiting state according to task division.

FIG. 5 is an example of setting a thread in a waiting state to a ready state

FIG. 6 A method for checking the number of executable threads in user space

FIG. 7 is an example of putting a thread in an executable state into a waiting state

FIG. 8 is an example of terminating a thread in a waiting state.

[Explanation of symbols]

 101 Task Scheduler 102 Operating System 103 Standby State Thread 104 Executable State Thread 105 Executable State Thread Number 106 Processor Number 107 Processor 201 Task Scheduler 202 Operating System 203 User Program 204 Task 205 Processor Number 206 Thread 207 Processor 301 Root Task 302 IO Child task including 303 303 Child task including only calculation 401 Executable thread 402 task 403 Processor 404 Waiting thread 501 task 502 Executable thread 503 Processor 504 Waiting thread 505 Dormant thread 601 Task scheduler 602 Operating system 603 User space Visible system Region 604 executable accommodate the number of threads region 701 Task 702 runnable thread 703 processor 704 wait state thread 705 dormant thread 801 task 802 runnable thread 803 processor 804 wait state thread 805 KILL signal during

Claims (1)

[Claims] 1. In a scheduling method realized by two layers of an operating system having a multi-thread mechanism and a parallel library for scheduling parallel jobs on threads, threads are generated in a waiting state that is not a scheduling target in the operating system. The number of ready-state threads managed by the operating system at the library layer. A parallel job cooperative scheduling method characterized by comprising a means for confirming and a means for terminating a waiting thread.