JP3231101B2 - Task queue management method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method of managing task queues waiting to be processed in a computer system, and more particularly to a method of managing task queues suitable for reducing the overhead of queue operations such as addition or deletion of long queues. .

[0002]

2. Description of the Related Art Conventionally, a computer system has generally adopted a system in which tasks waiting for execution are generally connected to one queue in the order of execution priority, and each of them is searched to determine whether or not execution is possible. . This method does not solve the problem that the overhead of queue search for adding to and deleting from the queue according to the task execution priority is large and the system performance is degraded.

To solve this problem, for example, in Japanese Patent Laid-Open No. 2-281338, an execution queue (queue) is separately provided for each task execution priority, and the length of the execution queue of the task is reduced. It proposes a method to improve search efficiency by checking and changing the task execution order according to the length. Also, JP-A-3-24629
In Japanese Patent Application Laid-Open Publication No. H10-209, a method of forming a task management block as a double queue of a queue in a first-come-first-served order and a queue according to an execution priority order to realize a high-speed task search and a reduction in overhead of addition and deletion operations is realized. is suggesting.

[0004]

Depending on the scale of the computer system, the number of tasks increases, so that the time required for maintenance of the task queue becomes so large that it cannot be ignored compared to the execution time of the process itself. Performance will be reduced.

The method described in Japanese Patent Application Laid-Open No. 2-281338 improves the task search efficiency, but executes a task ignoring the execution priority. Not suitable. When the total number of tasks is small, a single queue structure has a small search overhead for adding to and deleting from the queue, but cannot do so.

In the method described in JP-A-3-24629, the number of tasks to be searched must be at least as many as the number of execution priorities, and additional processing requires the number of tasks having the priorities. Therefore, when there is a variation in the number of tasks for each priority, the overhead increases. This corresponds in some cases to the overhead of only one queue.

An object of the present invention is to provide a task queue management method which solves such problems and greatly reduces the time required for additional processing to a task queue.

[0008]

[MEANS FOR SOLVING THE PROBLEMS] To achieve the above object
In addition, according to the invention of claim 1, the tasks waiting to be processed are
Grouped by task with row priority and execution priority
Queuing to configure and manage task queuing
In the task queue management method, the task queue includes
Holds the number of tasks to be included and the threshold for processing separation
When adding a task to the task queue,
Compare the number of tasks in the task queue with the threshold,
Task to be added to the task queue according to the comparison result
Is characterized in that a process for obtaining an additional position is determined.

Further , the invention according to claim 2 is a program for each execution priority.
And the task with the corresponding execution priority in the task queue
Queue that manages the start and end pointers of the queue
A pointer list and each entry of the queue pointer list.
Queued in the task queue corresponding to the bird
Index list that manages the execution priority of tasks
List, and the number of tasks included in the task queue is low.
If greater than the threshold, the queue pointer list
Alternatively, the index list and the queue pointer list
Use the task to match the execution priority of the task to be added.
It is characterized in that the calculated additional position is obtained.

[0010] Further, according to the invention of claim 3, the task queue
If the number of included tasks is smaller than the threshold,
By searching the task queue from the beginning or end,
The addition position according to the execution priority of the task to be added is
It is characterized by seeking.

[0011]

[Operation] The search of the queue pointer list or the index list and the search of the task queue itself are dynamically selected based on the number of tasks in the task queue based on the number of tasks in the task queue, thereby determining an additional position . Processing overhead can be minimized.

For example, the number of tasks included in a task queue
Is larger than the threshold, if there is already a task having the same execution priority as the task to be added in the task queue, the end position of the queue of the task is obtained from the queue pointer list, and the addition position is determined. The determination can be made at high speed without searching the queue. Further , even when there is no task having the same execution priority as the addition target task in the task queue, by referring to the index list, the execution priority of the addition target task among the tasks existing in the task queue is determined. The end pointer of the queue of the task with the highest execution priority closest to
By obtaining the same queue pointer list, it is possible to determine the additional position at high speed without searching the task queue.

When a task is deleted from the task queue, if the head pointer of the task queue is obtained from the queue pointer list, it is the pointer of the task to be deleted. Can be determined quickly.

[0014]

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of a task queue management method according to the present invention.
0 is an operating system (OS), 30 is a queue pointer list, and 40 is an index list.

The task queue 10 has a configuration in which the control blocks 10a to 10f of the tasks waiting to be processed are queued in the execution priority order and, in the same execution priority order, in the order of occurrence. The control block of each task has a next control block pointer 11, a previous control block pointer 12, and an execution priority (level) 13 of the task. With the pointers 11 and 12, the control blocks 10a to 10f of the task queue 10 can be traced in both directions.
The configuration of the task queue 10 itself is the same as the conventional one.

The operating system 20 includes a head pointer 21, a tail pointer 22,
In addition to the pointer 23 to the queue pointer list 30 and the pointer 24 to the index list 40, a threshold value 25 for separating processing to be described later and a task queue 1
It has a current task number of 0.

The queue pointer list 30 stores the execution priority of tasks defined in the system (01 in this embodiment).
FF), and each entry points to the first and last control blocks of the control blocks of the tasks having the same execution priority in the task queue 10. If there is no control block for the task with the corresponding execution priority, “0” is set in the entry. For example, the entry 301 corresponds to the execution priority "01", and since the control block of the task having the execution priority in the task queue 10 is only 10a, both the start pointer 301a and the end pointer 301b point to the control block 10a. . Entry 302
Corresponds to the execution priority "02", but the task queue 1
Since there is no corresponding task at 0, “0” is set to the start and end pointers 302a and 302b.
The entry 303 corresponds to the execution priority "03", and the control blocks of the task having the execution priority in the task queue 10 are 10b, 10c, and 10d in the order of occurrence, the head pointer 303a indicates the control block 10b, and the end pointer 30
3b points to the control block 10d. Similarly, entry 3FF corresponds to execution priority “FF”,
The start pointer 3FFa points to the control block 10e in the task queue 10, and the end pointer 3FFb points to the control block 10f.

The index list 40 also has entries corresponding one-to-one with the execution priorities of the tasks defined in the system. Each entry indicates whether or not the task of the execution priority exists in the task queue 10. This indicates that the value of the execution priority is set if it exists, and "0" is set if it does not exist. That is, the entries 401 to 4FF of the index list 40 are the same as the entries 301 to 3FF of the queue pointer list 30.
From the configuration of the task queue 10, the entry 401 is "01", the entry 402 is "00", the entry 403 is "03", and the entry 404 is "0".
"0" and "FF" are set in the entry 4FF.

FIG. 2 shows a processing procedure for adding a control block of a task for which a processing request has newly occurred to the task queue 10 in the configuration of FIG.

When adding (queuing) a control block of a task for which a processing request has newly occurred to the task queue 10, first, an entry corresponding to the execution priority of the task to be added in the queue pointer list 30 is obtained. The contents of the entry are read (step 101).
The corresponding entry in the queue pointer list 30 obtains the head address of the queue pointer list 30 by the queue pointer list pointer 23 set in the operation system 20, and determines the next address from the value of the execution priority of the task to be added. Such address calculation, that is, (start address of queue pointer list) + (length of one entry of pointer list) × (task execution priority value−
Determined by 1). For example, if the execution priority of the task to be added is “03” in FIG.
Is found.

Next, it is checked whether the contents of the entry corresponding to the execution priority of the task to be added in the queue pointer list 30 is "0" (step 10).
2). If it is not “0”, that is, if a control block of a task having the same execution priority as the task to be added already exists in the task queue 10, refer to the queue end pointer set in the entry, Immediately, additional processing (queuing) is executed (step 106).
For example, when the execution priority of the task to be added is “0”
3 ”, the entry 30 in the queue pointer list 30
The control block of the task is added immediately after the control block 10d indicated by the queue end pointer 303b set to 3, and the pointers 11 and 12 of the control blocks 10d and 10e are updated accordingly. This additional processing itself is the same as in the related art. Thereafter, the number of tasks 26 in the operation system 20 is incremented by 1, and the queue end pointer of the corresponding entry in the queue pointer list 30 is updated to the pointer value to the control block of the added task (step 107). If the content of the entry in the queue pointer list 30 is not “0”, the execution priority is already set for the corresponding entry in the index list 40, so that the update process for the index list 40 is not performed. .

FIG. 3 shows the post-queuing task queue 10 and queue pointer list 30 when the execution priority of the task to be newly added is “03” in the example of FIG.
Is shown. In FIG. 3, 10 g is a control block of the newly added task.

Returning to FIG. 2, if the content of the entry in the queue pointer list 30 is determined to be "0" in step 102, that is, if the control block of the task having the same execution priority as the task to be added is a task block, If not present in the queue 10, an additional position (queuing position) on the task queue 10 needs to be newly obtained. In this case, in this embodiment, the current task number 26 of the task queue 10 set in the operation system 20 is compared with the threshold value 25, and the processing is separated based on the result (step 103). Hereinafter, each process will be described.

If the number of tasks ≦ the threshold value, that is, if the number of tasks in the queue is small, the task pointer 10 or the end pointer 22 of the task queue 10 set in the operation system 20 is referred to, The addition position is determined by searching the queue 10 from the beginning or end (step 104). This is because when the number of tasks in the queue is small, even if the task queue 10 is searched in order from the beginning to the end, the time required for the search is short. It should be noted that the threshold for processing separation is determined by the index list 40 or the queue pointer list 5.
The number is determined in consideration of the number of steps required for a search of zero.

The process of searching the task queue 10 in order from the beginning or end to find an additional position is the same as the conventional process. For example, if the execution priority of the task to be added is “02” in FIG. 1, the task queue 10 is searched in order from the first control block 10a, and the execution priority 1
By comparing No. 3 with the execution priority “02” of the task to be added, it is found that the additional position should be between the control blocks 10a and 10b.

On the other hand, when the number of tasks> the threshold value, that is,
If the number of tasks in the queue is large, an addition position is determined from the index list 40 and the queue pointer list 30 (step 105). This is performed as follows. First, the index list 40 is searched by referring to the index list pointer 24 set in the operation system 20, and the lowest execution priority among the execution priorities higher than the execution priority of the task to be added is set. Ask for the entry that has been. For example, when the execution priority of the task to be added is “02”, the entry 401 in the index list 40 in which the execution priority of “01” is set corresponds to this.
Next, based on the pointer list pointer 23 set in the operation system 20 and the execution priority set in the above entry of the index list 40, the same address calculation as in the case of step 101 is performed, so that the queue pointer list 30 The corresponding entry is obtained, and the addition position is determined from the task queue end pointer set in the entry. For example, when the execution priority of the task to be added is “02”, the entry in the queue pointer list 30 corresponding to the execution priority “01” obtained by searching the index list 40 becomes 301 in the address calculation. From the value of the task queue end pointer 301b of the entry 301, the addition position is immediately after the control block 10a.

As described above, by using the index list 40 and the queue pointer list 30, an additional position can be obtained at high speed without searching the task queue 10. This is more advantageous than searching the task queue 10 sequentially from the beginning or end as the number of tasks in the queue increases.

When the addition position is determined in step 104 or 105, the control block of the task to be added is added to the addition position in the task queue 10 (step 106). Thereafter, the number of tasks 26 in the operation system 20 is incremented by 1, and the pointer to the control block of the added task is set in the queue head / end pointer of the entry corresponding to the execution priority of the added task in the queue pointer list 30. Then, the execution priority of the added task is registered in the corresponding entry of the index list 40 (step 107).

FIG. 4 shows the task queue 10 and the queue pointer list 3 after queuing when the execution priority of the task to be newly added is “02” in the example of FIG.
0 shows the structure of the index list 40. In FIG. 4, 10h is a control block of the newly added task.

Next, a case where a task is executed and its control block is deleted from the task queue 10 will be briefly described.

An address is calculated from the queue pointer list pointer 23 set in the operation system 20 and the execution priority value of the task to be deleted, and an entry corresponding to the execution priority of the task to be deleted in the queue pointer list 30 is calculated. Is the same as in the case of the additional processing. This queue pointer list 30
The control block pointed to by the task queue head pointer set in the corresponding entry is the control block of the task to be deleted. Therefore, the deletion process can be immediately executed by referring to the task queue head pointer of the corresponding entry of the queue pointer list 30 obtained by the address calculation. Thereafter, the number of tasks 26 in the operation system 20 is decremented by one, the queue pointer list 30 is updated, and in some cases, the index list 40 is also updated. In updating the corresponding entry of the queue pointer list 30, if a task having the same execution priority as the deleted task remains, the task next to the deleted task and the control block pointer are set as the task head pointer. , The task queue start pointer and the end pointer are set to “0”. Similarly, when there is no remaining entry, the corresponding entry of the index list 40 is set to “0”.

[0033]

As is clear from the above description, the present invention
According to this, when adding a new task to the task queue,
Processing is dynamically switched based on the current number of tasks in the task queue
To perform optimal processing according to the system status
It is possible to process the additional position of the task
Overhead can be minimized.

[Brief description of the drawings]

FIG. 1 is a diagram showing a configuration example of a task queue, an operation system, a queue pointer list, and an index list of the present invention.

FIG. 2 is a diagram showing an example of a procedure of a process of adding to a task queue according to the present invention.

FIG. 3 is a diagram showing a configuration example of a task queue and a queue pointer list after an addition process when tasks having the same execution priority exist in FIG. 1;

FIG. 4 is a diagram illustrating a configuration example of a task queue, a queue pointer list, and an index list after addition processing when there is no task having the same execution priority in FIG. 1;

[Explanation of symbols]

 Reference Signs List 10 task queue 10a to 10f task control block 20 operation system 26 number of tasks in task queue 30 queue pointer list 301a to 3FFa queue head pointer 301b to 3FFb queue end pointer 40 index list

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-4-101233 (JP, A) JP-A-4-199431 (JP, A) JP-A-2-281338 (JP, A) JP-A-3-301 157733 (JP, A) JP-A-62-276653 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G06F 9/46 G06F 17/30

Claims (3)

(57) [Claims] A task waiting to be processed is assigned an equal execution priority.
Grouped by priority task and queued in execution priority order
Task queue management to configure and manage task queues
A physical method, the number of the processing segmentation tasks included in the task queue
For adding tasks to the task queue.
Compare the number of tasks included in the queue with the threshold and compare
Depending on the result, add a task to be added to the task queue.
A task characterized by determining a process for obtaining an additional position
Queue management method. 2. The task queue management method according to claim 1, wherein
For each execution priority , the corresponding
Point at top and bottom of queue for row-priority tasks
A queue pointer list for managing data, and the queue pointer
Task queue corresponding to each entry of the
Manages the execution priority of tasks queued in
An index list is set up, and the number of tasks included in the task queue is larger than a threshold.
, The queue pointer list or the
Use index list and queue pointer list
The additional task according to the execution priority of the task to be added.
A task queue management method, wherein 3. The task queue management method according to claim 1,
The number of tasks included in the task queue is smaller than a threshold value.
If the task queue is at the beginning or end
From the execution priority of the task to be added
Task queue characterized by finding an additional position according to
-Management method.