JPH0782444B2 - Task schedule method - Google Patents

Description

TECHNICAL FIELD The present invention relates to a task scheduling method in a multiprocessor system sharing a memory.

[Conventional technology]

Conventional task scheduling methods include first-in first-out method, priority method, method that prioritizes tasks with more I / O than tasks that use a long processor time, and method that changes the processing order to keep the target value of processing time. . These methods did not consider task resource usage and request status. Also, as shown in Japanese Patent Application No. 61-133641, when the task switching overhead is sufficiently small, priority is ignored and tasks that use resources are always processed by one of the processors, so that a future resource bottleneck will occur. It can be prevented to improve the throughput.

[Problems to be solved by the invention]

In the conventional method, the task is rescheduled every time the task releases the resource. With this method, the maximum throughput can be realized when the overhead of task switching is small, but the processing capacity decreases when the overhead is large.

[Means for solving problems]

For the above purpose, the present invention adds a resource waiting queue in addition to the conventional task queue. When resources compete, put the task in the resource waiting queue. When a task is scheduled, it is checked whether the resource is in use. If the resource is not used, the task in the resource waiting queue is scheduled first. Further, when a task releases a resource, whether or not there is another task waiting for the resource is determined by a preset flag. It has a means for setting this flag by comparing the task switching overhead with the overhead of one cycle of resource occupation release of the task.

[Action]

The effect of the present invention is that when a task uses a plurality of exclusive resources at a high ratio in a task scheduler on a processor that shares memory, when there are tasks waiting for these resources, the resources are released when the task releases the resources. By deciding whether or not to switch to the waiting task in consideration of the task switching overhead, it is possible to prevent the processor from being idle in the future and to prevent the performance from being deteriorated due to the task switching overhead.

〔Example〕

An embodiment of the present invention will be described below. FIG. 1 is a schematic diagram of a task scheduler of the present invention. The task scheduler 1. is activated to select and activate the next task to be processed when each task ends, when the resource is released and when an input / output is requested. In this embodiment, it is assumed that resources satisfy the following conditions. Request resources only from tasks that have processors assigned to them. Whenever a task goes into a state where the processor cannot be assigned, such as when a task I / O is requested, the resource is released so that the task is occupied only by the task that is currently assigned the processor or is available and suspended. ing.

The task state transition is performed as shown in FIG. When a task is created, it enters the ready state 10. and ends in the resource unoccupied execution state 11. (this process is not shown). The task in the ready state 10. enters the resource non-occupancy execution state 11. by the task scheduler. When a task in resource non-occupied execution state 11. uses a resource, it enters resource occupation execution state 12 if resource occupation processing succeeds, and enters resource wait state 13. if resource occupation processing fails. When the resources are released in the resource occupation execution state 12. and there is another resource waiting task that can be used by the resource release process, and the dispatch flag 20 is on, the ready state 10.
Otherwise, enter resource unoccupied execution state 11. A task in resource wait state 13. becomes resource exclusive execution state 12 when selected by the task scheduler. When a task is interrupted in the resource non-occupancy execution state 11. and the resource occupation execution state 12., the ready state 10. and the resource occupation interruption state 14. are entered by the interruption processing, respectively. When the task in resource occupation suspended state 14. is selected in the task scheduler, it returns to resource occupation execution state 12. In FIG. 1, the task in the resource occupancy suspended state is placed at the head of the resource waiting queue.

As shown in the processing flow in Fig. 3, the task scheduler
In 1., first, seeing the resource in-use flag 2. If another processor is not using the resource, the task at the head of the resource wait queue 3. is fetched and scheduled. If there is no task to schedule, schedule the task from Ready Queue 4.

When releasing the exclusive use of the resource from the task: As shown in FIG. 4, when the resource in-use flag is ON at the time of occupation request, the resource wait queue 3 is entered. Then go to the task scheduler.

When released, the dispatch flag 20.
If is on and there is another task in the resource waiting queue, the current task is interrupted and the task scheduler is started to activate the task.

As shown in FIG. 6, the task suspension processing puts the task at the head of the resource waiting queue if the task is using the resource, or puts it in the ready queue otherwise.

FIG. 7 shows the setting process of the dispatch flag 20. If the ratio of the number of dynamic steps per dispatch given in advance and the number of resource occupation processing steps per task + resource non-occupancy processing steps is larger than a predetermined proportional constant, the dispatch flag is set. Set it to OFF, and if it is smaller, set it to ON.

〔The invention's effect〕

According to the present invention, when the dispatch overhead is small, it is possible to prevent the performance from deteriorating due to contention of resources, and when the dispatch overhead is large, on the contrary, to prevent the dispatch, thereby maximizing the task processing capacity of the system. I chose

[Brief description of drawings]

FIG. 1 is a schematic diagram of a task scheduler process according to an embodiment of the present invention, FIG. 2 is a task state transition diagram, FIG. 3 is a task scheduler process flow diagram, and FIG. 4 is a process flow diagram when a resource is occupied. 5, FIG. 5 is a flow chart of processing when releasing resources, FIG. 6 is a flow chart of task interruption processing, and FIG. 7 is a flow chart of processing of dispatch flag setting. [Explanation of reference symbols] 1. Task scheduler, 2. Resource in-use flag, 3. Resource waiting queue, 4. Ready queue, 5. Resource table, 10. Ready state, 11. Unoccupied resource execution state, 12.
Resource occupancy execution status, 13. Resource wait status, 14. Resource occupancy suspended status, 20. Dispatch flag.

Claims (2)

[Claims] 1. A task scheduling method for scheduling a plurality of tasks alternately using a common resource on a multiprocessor system having a plurality of processors sharing a main memory, the tasks being executed on the processor. Determines that the ratio of the overhead of task switching to the resource occupation of the task and the overhead of processing of one cycle of release exceeds a predetermined value in response to the termination of the use of the resource, and the determination is made. As a result, when the ratio of the overhead is larger than the predetermined ratio, the task releasing the resource is continuously executed on the processor, and the ratio of the overhead is larger than the predetermined ratio. If it is small, the task schedule is characterized in that the execution of the task is interrupted and another task is executed. Yuru system. 2. The task according to claim 1, wherein when there is a task in the resource waiting state, the task waiting for the resource is preferentially assigned as the other task. Task scheduling method.