JPH04101233A - Task controlling method by two-hierarchy queue structure - Google Patents

Abstract

PURPOSE:To realize easy and high-speed retrieval through simple constitution by making a queue into two-hierarch structure, and executing scheduling by inserting tasks into only the queue of priority order when there are two or more tasks of the same priority. CONSTITUTION:The control block 12 of the task stores a pointer 121 to constitute an exclusive queue to connect only a head task in the case that there are plural tasks in priority order and of the same priority and the pointer 122 to constitute the exclusive queue to connect plural tasks in the priority order and of the same priority in the order of arrival and the value 123 of the priority of the task. Accordingly, when there are two or more tasks of the same priority, by inserting them into only the queue of the priority order, only one task is allowed always to be located on the exclusive queue, and the high-speed retrieval of the queue can be executed. Thus, the high-speed retrieval of the queue is realized, and simultaneously, effect that the insertion and the removal of the task to the queue are remarkably simplified is obtained.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to a task management method using a two-layer queue structure used in multitasking operating systems and the like.

Conventional technology A conventional task management method is disclosed in Japanese Patent Application Laid-Open No. 6319123, for example.
The configuration described in Publication No. 6 is known.

FIG. 5 is a block diagram showing operating system management items, a stack control block, and a pseudo stack control block for explaining the conventional task management method disclosed in this publication.

In FIG. 5, 10 is an operating system management item, 101 is an executable queue, 51 is a task control block, 511 is a priority queue 512 is a task priority, 52 is a pseudo control block, 521 is a priority, and 522 is the same The priority queue 523 is the priority of tasks.

Next, the operation of the above conventional example will be explained. When scheduling executable tasks in priority order, individual task control blocks 51 that manage task control information are connected to executable queue 101 in order of task priority.

At this time, if a plurality of task control blocks with the same priority become executable, a pseudo control block 52 is provided, and the plurality of task control blocks 51 with the same priority are connected to this pseudo control block 52. , this pseudo control block 52 is connected as a representative block of the corresponding priority.

When searching the executable queue 101, the pseudo control block 5
Task control block 5 with the same priority connected to 2
When there is no need to search for 1, a skip signal is issued to perform a high-speed search.

Problems to be Solved by the Invention However, in the conventional task management method described above, when the number of task control blocks with the same priority decreases from a plurality to one by removing the task control block 51 from the queue, or when a task control block is When the number of task control blocks with the same priority increases from one to a plurality of task control blocks due to insertion, it is necessary to generate and delete the pseudo control block 52, which poses a problem in that the processing takes time.

The present invention solves these conventional problems,
It is an object of the present invention to provide a task management method using a two-layer queue structure that has a simple configuration and allows easy and high-speed searching.

Means for Solving the Problems In order to achieve the above object, the present invention executes a control block that manages control information of each task in an executable state in order of priority of the tasks managed by this control block. A queue that connects tasks with the same priority to the control block of this task on a first-come, first-served basis, and a queue that connects only the first task with the corresponding priority if there is a task with the same priority are established. A two-layer queue structure is adopted, and when two or more tasks with the same priority exist, scheduling is performed by inserting them only into the queue in order of priority.

Therefore, according to the present invention, when there are two or more tasks with the same priority, only one task is always present on the dedicated queue by inserting them only into the queue in order of priority. First, it has the effect that it is possible to search a queue at high speed, and insertion and removal from the queue are extremely easy.

Embodiment FIG. 1 is a block diagram of operating system management items and task control blocks for explaining one embodiment of the present invention. In FIG. 1, 10 is an operating system management item, and 12 is a task control block.

The management item 10 of the operating system points to the control block 12 of the highest priority task in the executable state using the executable queue 101.

The task control block 12 includes a pointer 121 that configures a dedicated queue to which only the first task is connected when there are multiple tasks in priority order and with the same priority, and a pointer 121 that configures a dedicated queue to which only the first task is connected when there are multiple tasks in priority order and with the same priority. is a pointer 122 that configures a dedicated queue on a first-come, first-served basis and a task priority value of 1
23 is stored.

Next, the operation of the above embodiment will be explained with reference to FIGS. 2 and 3. FIG. 2 shows the above example.
12 is a flowchart for searching for an insertion position when inserting a new task into a two-layer queue.

First, in FIG. 2, when it becomes necessary to insert a new task into the queue in step 21, the operating system sets the priority of the task to be inserted into a variable X.

Next, in step 22, a search position for determining the task insertion position is set to the beginning, and in step 23, the priority at this search position is set to Y.

Next, in step 24, the priority of the task inserted into the variable X is compared with the priority at the search position set to Y, and if Since the priority of the task to be inserted is higher than the priority, the process moves from the YES side of step 24 to step 25, and the task is inserted immediately before the set search position.

In addition, in step 24, if X is larger than Y (X>Y), in step 24, the process moves from the No side to step 26, where it is checked whether the current search position is at the end, and if it is at the end. If not, the process moves to step 28 from the No side of step 26, the search position is shifted to the next position in the priority queue, and the processes from steps 23 to 28 are repeated.

In addition, in step 26, if the current search position is the end, the process moves from the YES side of step 26 to step 27, and since the task has the lowest priority, it is inserted at the end, and the execution process ends in step 29. do.

FIG. 3 is a flowchart showing step 25 of FIG. 2 in detail. When the insertion position of the task can be found, in step 31 the priority queue in the control block of the previous task is updated to point to the control block of the task to be inserted.

Next, in step 32, the priority queue in the control block of the task to be inserted and the dedicated queue are updated to point to the control block of the task at the search position.

Furthermore, the operating system sets the priority of the task before the search position in the variable Z in step 33, moves to step 34, determines whether the variables X and 2 are equal or not, and determines the result of the determination. , if variables X and Z are the same, the process moves to step 36 from the YES side of step 34, ends the insertion process, and returns to step 24 in FIG.

Further, in step 34, if the variables X and 2 are not equal, the process moves from the No side of step 34 to step 35,
The previous task's private queue is updated to point to the inserting task's control block, and the process ends at step 36.

FIG. 4 shows a flowchart for deleting tasks from the queue. In step 41, the operating system sets the priority of the task to be deleted in variable X, and in step 42 sets the priority of the previous task in the priority queue in variable Y.

Next, in step 43, variables X and Y are compared, and if X and Y are different, the process moves from the YES side of step 43 to step 44, and the task is deleted from the priority queue in the dedicated queue in the control block of the previous task. Assigns the contents of the priority queue of the task's control block.

The operating system then sets variable 2 at step 45 to the priority of the task at the back of the priority queue.

Next, in step 46, it is determined whether the variables X and Z are equal or not. If the variables Assign the contents of the private queue of the control block of the task to be deleted to .

In step 46, if variables X and Z are not equal,
If the result of step 46 is No, the process moves to step 48 and step 47 is skipped.

If the variables X and Y are equal in step 43, the process moves to step 48 from the No side of step 43, and steps 44 to 47 are skipped.

Finally, in step 48, the contents of the priority queue of the task to be deleted are substituted into the priority queue in the control block of the task before the priority queue, and the process ends in step 4.

In this way, according to the above embodiment, by providing a dedicated queue for the control block of a task, multiple tasks with the same priority can be queued using only the original control block, without using a pseudo control block. can be inserted.

Furthermore, since tasks with the same priority are not searched at the same time, high-speed searches can be performed.

Effects of the Invention As is clear from the above embodiments, the present invention includes a control block that manages control information of each task in an executable state.
The tasks managed by this control block are connected to the executable queue in priority order, and tasks with the same priority are connected to the side block of the second task on a first-come, first-served basis.If there is a task with the same priority as the queue, creates a two-layered queue structure by creating a queue that connects only the first task with the corresponding priority, and when there are two or more tasks with the same priority, scheduling is performed by inserting them only into the queue in order of priority. Therefore, when two or more tasks with the same priority exist, by inserting them only into the priority queue, only one task always exists on the dedicated queue, resulting in high-speed processing. This has the effect of not only making it possible to search for a queue, but also making insertion and removal from the queue extremely easy.

[Brief explanation of drawings]

FIG. 1 is a block diagram of a task management method using a two-layer queue structure according to an embodiment of the present invention, and FIG. Figure 3 is a flowchart for inserting a new task into a two-layer queue to explain the method, and Figure 4 is a flowchart for deleting a task from a two-layer queue to explain the method. Flowchart FIG. 5 is a flowchart of a conventional task management method. 10...Operating system management items, 1o1
...Executable queue 12...Task control block, 121...Pointer configuring dedicated queue, 12
2... Pointer configuring a queue on a first-come, first-served basis, 123.
...Task priority value. Name of agent: Patent attorney Shige Awano Takahaka 1
Figure 11 Pointers configuring the flock-only queue for tasks Priority values of pointer tasks configuring the priority queue Figure 2 Figure 4

Claims (1)

[Claims] A control block that manages the control information of each task in the executable state is connected to an executable queue in order of the priority of the tasks managed by this control block, and tasks with the same priority are placed in the control block of this task first. If there are queues that are connected in order and tasks with the same priority, a queue that connects only the first task with the corresponding priority is created, creating a two-layer queue structure, and two or more tasks with the same priority exist. A task management method using a two-layer queue structure in which when a task is scheduled, it is inserted only into a queue in order of priority and scheduling is performed.