JP2544896B2 - Scheduling method and scheduling device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a scheduling method and a scheduling device for performing task management in a stack area.

[0002]

2. Description of the Related Art Conventionally, when performing task management in a stack area, a stack area used by each task is assigned to each task, and the execution state of each task is divided into a running state under execution by a central processing unit and a central state. Scheduling is performed in three states: a runnable state waiting for the allocation of the processing device and a runnable waiting state waiting for an event such as a signal from another task.

[0003]

However, in the above-described conventional scheduling method, since all tasks have a possibility of entering a running state, it is necessary to allocate a stack area used by each task for each task. Therefore, when the stack area has a small capacity, it is not possible to secure an area for the task to be in a running state, and as a result, there is a problem that scheduling cannot be performed.

The present invention has been made in view of the above circumstances, and a scheduling method that enables scheduling even when a plurality of tasks use the same stack to reduce the stack area capacity. Another object of the present invention is to provide a scheduling device.

[0005]

According to a first aspect of the present invention, there is provided a task having at least four execution states of a runnable state, a run wait state, a runnable state and a runnable state and a unique identifier in the system. , A scheduling method in a system in which a plurality of tasks are executed by task switching, including a task information storage unit that stores an identifier and an execution state of each task, an identifier of each task, and a maximum stack capacity used by each task. In addition to storing, if the task is in the run-disabled state and no stack is allocated, the run-state is either the run-state, the run-wait state or the run-ready state, and the task-run state And the identifier of the execution protection task that is in the run-disabled state when is in the running state, the run-waiting state, or the runnable state The execution protection task storage unit that stores the maximum stack capacity used when the execution protection task is in the run-disabled state is used, and the task switching request step for generating a task switching request and the task switching request step When a switching request is generated, the task information storage unit and the execution protection task storage unit are searched, and the identifier of the task that is neither the execution protection task nor the execution state is the run-disabled state for any task. Executable task extraction step to extract the task execution state and the task execution state is the running state Change the task execution state to the runnable state and search the task information storage section to see whether the task execution state is the run waiting state or the runnable state In the running task extraction step that extracts the status task identifier and the running task extraction step When the identifier extracted as a first identifier and the identifier extracted in the executable task extraction step as a second identifier are searched, the execution protection task storage unit is searched and the task corresponding to the first identifier is searched. A stack usable task extracting step for extracting a combination of the first identifier and the second identifier, which is an execution protection task of the task corresponding to the second identifier,
When the execution protection task storage unit is searched and the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted in the stack usable task extraction step is in the unexecutable state Stack available to obtain the maximum stack capacity to be used and extract the combination of the first identifier and the second identifier whose stack capacity currently used by the task corresponding to the first identifier is smaller than that stack capacity The task selection step and the execution state of the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted in the stack usable task selection step are set to the run-disabled state, and the second identifier And a task switching step for changing the execution state of the task corresponding to to the running state.

According to a second aspect of the invention, a plurality of tasks having at least four execution states of a runnable state, a run-waiting state, a runnable state and a runnable state and a unique identifier in the system are provided by task switching. A scheduling device in a computer system to be executed, which includes a task information storage unit that stores an identifier of each task and an execution state,
It stores the identifier of each task and the maximum stack capacity used by each task, and whether the task is in the run state or the run wait state when the task is in the run-disabled state and no stack is allocated. An identifier of an execution protection task that is in a run-disabled state when the task is in either the runnable state and the task execution state is either the runnable state, the run-waiting state, or the runnable state, and The execution protection task storage unit that stores the maximum stack capacity used when the execution protection task becomes unrunnable, the task switching request unit that issues a task switching request, and the task switching request unit When the error occurs, the task information storage section and the execution protection task storage section are searched, and the execution protection task for any task is searched. The executable task extractor that extracts the identifier of a task that is not running and is in the run-disabled state, and the task running state that the task is running is changed to the runnable state, and the task information storage unit The executing task extracting unit that extracts the identifier of a task whose execution state of the task is the running waiting state or the runnable state by searching, and the identifier extracted by the executing task extracting unit
When the identifier extracted by the executable task extraction unit is used as the second identifier, the execution protection task storage unit is searched to find the task corresponding to the first identifier as the second identifier.
Which is the execution protection task of the task corresponding to the identifier of
Of the stack usable task extracting unit that extracts the combination of the identifier of the second identifier and the second identifier, and the first identifier and the second identifier that are extracted by the stack usable task extracting unit The maximum stack capacity to be used when the task corresponding to the first identifier in the combination with and is in the non-executable state is obtained, and the stack currently used by the task corresponding to the first identifier is larger than the stack capacity. A stack usable task selection unit that extracts a combination of a first identifier and a second identifier with a small capacity, and a combination of the first identifier and the second identifier extracted by the stack usable task selection unit. The execution state of the task corresponding to the identifier of 1 is set to the run-disabled state, and the second
And a task switching unit for changing the execution state of the task corresponding to the identifier of 1 to the running state.

According to a third aspect of the present invention, a plurality of tasks having at least four execution states of a runnable state, a run-waiting state, a runnable state, and a runnable state and a unique identifier in the system are provided by task switching. A scheduling method in a computer system to be executed, comprising a task information storage unit that stores an identifier and an execution state of each task,
It stores the identifier of each task and the maximum stack capacity used by each task, and whether the task is in the run state or the run wait state when the task is in the run-disabled state and no stack is allocated. An identifier of an execution protection task that is in a run-disabled state when the task is in either the runnable state and the task execution state is either the runnable state, the run-waiting state, or the runnable state, and The execution protection task storage unit that stores the maximum stack capacity used when the execution protection task is in the run-disabled state and the stack pointer storage unit that stores the execution state and stack pointer of the task are used. Task switching request step that generates a task switching request, and a task switching request is generated in the task switching request step The executable task that searches the task information storage unit and the execution protection task storage unit by using, and extracts the identifier of a task that is not an execution protection task for any task and whose execution state is in the run-disabled state The extraction step and the task execution state is the running state. The task execution state is changed to the runnable state, the task information storage is searched, and the task execution state is the task waiting state or the runnable state. When the executing task extracting step for extracting the active task and the identifier extracted in the executing task extracting step are used as the first identifier and the identifier extracted in the executable task extracting step is used as the second identifier, the execution protection task The storage is searched, and the task corresponding to the first identifier is the execution protection task of the task corresponding to the second identifier. A stack usable task extracting step for extracting a combination of the identifier and the second identifier, and an identifier that can be an execution protection task in the combination of the first identifier and the second identifier extracted in the stack usable task extracting step The execution state of the task corresponding to the above is stored in the stack pointer storage unit, the execution state of the task that can be the execution protection task is changed to the running wait state, and the data in the stack used by the task that can be the execution protection task is compressed. Then, the stack data compression step of storing the stack pointer of the task that can be the execution protection task in the stack pointer storage unit, and the first identifier extracted in the stack usable task extraction step by searching the execution protection task storage unit. Task corresponding to the first identifier in combination with the second identifier The first and second identifiers are obtained in which the maximum stack capacity to be used when the task becomes the inexecutable state is obtained, and the stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity. And a running state of a task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted in the stack-usable task selection step. A task switching step that sets the task to the disabled state and sets the execution state of the task corresponding to the second identifier to the running state, and searches the task information storage unit to extract all the identifiers of the tasks whose execution state is the running waiting state, The stack pointer storage unit is searched and the stack pointer and execution state of the task corresponding to the identifier extracted from the task information storage unit are extracted. Then, the data in the stack used by the task that extracted the stack pointer and execution state from the stack pointer storage is expanded, and the execution state of the task that extracted the stack pointer and execution state from the stack pointer storage is stacked. Execute a stack data expansion step that changes to the execution state extracted from the pointer storage unit and deletes the stack pointer and execution state of the task that extracted the stack pointer and execution state from the stack pointer storage unit from the stack pointer storage unit. It is characterized by doing.

According to a fourth aspect of the invention, a plurality of tasks having at least four execution states of a runnable state, a run wait state, a runnable state and a runnable state and a unique identifier in the system are provided by task switching. A scheduling device in a computer system to be executed, which includes a task information storage unit that stores an identifier of each task and an execution state,
It stores the identifier of each task and the maximum stack capacity used by each task, and whether the task is in the run state or the run wait state when the task is in the run-disabled state and no stack is allocated. An identifier of an execution protection task that is in a run-disabled state when the task is in either the runnable state and the task execution state is either the runnable state, the run-waiting state, or the runnable state, and An execution protection task storage unit that stores the maximum stack capacity used when the execution protection task is in the run-disabled state, a stack pointer storage unit that stores the execution state and stack pointer of the task, and a task switching request Task switching request part that generates a task switching request part, and when the task switching request part generates a task switching request, Executable task extraction section that searches the protected task storage section and extracts the identifier of the task whose execution status is not run-protected for any task A running task extraction unit that changes the running state of a task that is running to a runnable state, searches the task information storage unit, and extracts the identifier of a task whose task running state is the run-waiting state or runnable state. , When the identifier extracted by the running task extraction unit is the first identifier and the identifier extracted by the executable task extraction unit is the second identifier, the execution protection task storage unit is searched for the first identifier. Available task for extracting the combination of the first identifier and the second identifier, which is the execution protection task of the task corresponding to the second identifier The execution state of the task corresponding to the identifier that can be the execution protection task in the combination of the extraction unit and the first identifier and the second identifier extracted by the stack usable task extraction unit is stored in the stack pointer storage unit and executed. Change the execution state of a task that can be a protection task to the running wait state, compress the data in the stack used by the task that can be an execution protection task, and store the stack pointer of the task that can be an execution protection task in the stack pointer storage section. A task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit is searched by searching the stack data compression unit to be stored and the execution protection task storage unit. Obtain the maximum stack capacity to be used when it becomes unexecutable, and A stack usable task selection unit that extracts a combination of a first identifier and a second identifier that is currently used by a task corresponding to the identifier and has a small stack capacity, and a first unit extracted by the stack usable task selection unit Identifier and second
A task switching unit that sets the execution state of the task corresponding to the first identifier in the combination with the identifier of No. to the run-disabled state and the execution state of the task corresponding to the second identifier to the running state, and the task information storage unit. By extracting all the identifiers of the tasks whose execution state is waiting to run by searching, the stack pointer storage unit is searched, and the stack pointer and execution state of the task corresponding to the identifier extracted from the task information storage unit are extracted. Extracts the stack pointer and execution state from the stack pointer storage unit, expands the data in the stack used by the task, and stores the stack pointer and execution state from the stack pointer storage unit, and stores the execution state of the task Change to the execution state extracted from the copy section, and change the stack pointer and execution state from the stack pointer storage section. Are stack data developing unit for removing stack pointer out tasks and the execution state from the stack pointer storage portion, comprising the.

[0009]

According to the invention of claim 1, the task switching request is generated in the task switching request step, and the task switching request is generated in the task switching request step in the executable task extraction step.
The task information storage unit and the execution protection task storage unit are searched to extract an identifier of a task that is not an execution protection task and whose execution state is in a non-runnable state for any task, and an executing task extraction step Change the task execution state to the runnable state when the task is in the running state, search the task information storage section, and extract the identifier of the task that is in the run-waiting state or runnable state. Then, in the stack available task extraction step,
When the identifier extracted in the executing task extraction step is used as the first identifier and the identifier extracted in the executable task extraction step is used as the second identifier, the execution protection task storage unit is searched for the first identifier. The combination of the first identifier and the second identifier, which is the execution protection task of the task whose identifier corresponds to the second identifier, is extracted, and the execution protection task storage unit is stored in the stack usable task selection step. Maximum stack capacity used when the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted in the stack usable task extraction step is in the inexecutable state And the stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity
Of the combination of the first identifier and the second identifier, and the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted in the stack usable task selection step in the task switching step. Of the task corresponding to the second identifier is set to the running state.

In the invention of claim 2, the task information storage section stores the identifier and the execution state of each task. The execution protection task storage unit stores the identifier of each task and the maximum stack capacity used by each task, and when the execution state of the task is the run-disabled state and the stack is not allocated, the execution state is When the task is in the running state, the waiting state, or the runnable state, and the task execution state is either the running state, the runnable state, or the runnable state, the runnable state is set. The identifier of the execution protection task and the maximum stack capacity used when the execution protection task is in the run-disabled state are stored. The task switching request unit generates a task switching request. The executable task extraction unit searches the task information storage unit and the execution protection task storage unit when the task switching request unit issues a task switching request,
An identifier of a task that is not an execution protection task and whose execution state is the run-disabled state is extracted for any task. The running task extraction unit changes the running state of the task whose running state is the running state to the runnable state,
The task information storage unit is searched to extract the identifier of the task whose task execution state is the running waiting state or the runnable state. The stack usable task extraction unit, when the identifier extracted by the executing task extraction unit is the first identifier and the identifier extracted by the executable task extraction unit is the second identifier, the execution protected task storage unit Search for
A combination of the first identifier and the second identifier, which is the execution protection task of the task corresponding to the second identifier, corresponding to the first identifier is extracted. The stack usable task selection unit searches the execution protection task storage unit and finds the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit. A first identifier and a second identifier that have the maximum stack capacity to be used in the case of the non-executable state and have a smaller stack capacity currently used by the task corresponding to the first identifier than the stack capacity Extract the combination of. The task switching unit sets the execution state of the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task selection unit to the run-disabled state, and the second identifier. The execution state of the task corresponding to is set to the running state.

According to the third aspect of the present invention, the task switching request is generated in the task switching request step, and the task switching request is generated in the task switching request step in the executable task extraction step. Section and the execution protection task storage section to retrieve the identifiers of tasks that are not execution protection tasks and whose execution status is not runnable for any of the tasks. The execution state of the task is changed to the running state, the task execution state is changed to the runnable state, the task information storage unit is searched, and the identifier of the task whose execution state is the waiting state or the runnable state is extracted, In the available task extracting step, the identifier extracted in the executing task extracting step is set as the first identifier. , When the identifier extracted in executable tasks extraction step is a second identifier,
The execution protection task storage unit is searched to extract the combination of the first identifier and the second identifier, which is the execution protection task of the task corresponding to the second identifier, corresponding to the first identifier, and stacks the stack. In the data compression step, the execution state of the task corresponding to the identifier that can be the execution protection task in the combination of the first identifier and the second identifier extracted in the stack usable task extraction step is stored in the stack pointer storage unit, Change the execution state of a task that can be an execution protection task to the waiting state, compress the data in the stack used by the task that can be an execution protection task, and store the stack pointer of the task that can be an execution protection task in the stack pointer storage In the stack usable task selection step, the execution protection task storage section is searched and The maximum stack capacity to be used when the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted in the usable task extracting step is in the inexecutable state, and A combination of the first identifier and the second identifier whose stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity is extracted, and in the task switching step, in the stack usable task selecting step. In the extracted combination of the first identifier and the second identifier, the execution state of the task corresponding to the first identifier is set to the non-running state, and the execution state of the task corresponding to the second identifier is set to the running state, In the stack data expansion step, the task information storage section is searched to extract all the identifiers of the tasks whose execution status is waiting for running, Extracts the execution state and the stack pointer of the corresponding task identifier extracted from the search to the task information storage unit Kupointa storage unit,
Extracts the stack pointer and execution state from the stack pointer storage unit, expands the data in the stack used by the task, and stores the stack pointer and execution state from the stack pointer storage unit, and stores the execution state of the task The execution state extracted from the stack pointer is changed to the execution state, and the stack pointer and the execution state of the task whose stack pointer and execution state are extracted from the stack pointer storage unit are deleted from the stack pointer storage unit.

In the invention of claim 4, the task information storage section stores the identifier and the execution state of each task. The execution protection task storage unit stores the identifier of each task and the maximum stack capacity used by each task, and when the execution state of the task is the run-disabled state and the stack is not allocated, the execution state is When the task is in the running state, the waiting state, or the runnable state, and the task execution state is either the running state, the runnable state, or the runnable state, the runnable state is set. The identifier of the execution protection task and the maximum stack capacity used when the execution protection task is in the run-disabled state are stored. The stack pointer storage unit stores the task execution state and the stack pointer. The task switching request unit generates a task switching request. The executable task extraction unit searches the task information storage unit and the execution protection task storage unit when the task switching request unit issues a task switching request, and determines that neither task is an execution protection task. The identifier of the task whose execution state is the run-disabled state is extracted. The running task extraction unit changes the running state of the task whose running state is the running state to the runnable state, searches the task information storage unit, and the task running state is the run waiting state or the runnable state. Extract the task identifier. The stack usable task extraction unit, when the identifier extracted by the executing task extraction unit is the first identifier and the identifier extracted by the executable task extraction unit is the second identifier, the execution protected task storage unit By searching for a combination of the first identifier and the second identifier, which is the execution protection task of the task corresponding to the second identifier. The stack data compression unit stores, in the stack pointer storage unit, the execution state of the task corresponding to the identifier that can be the execution protection task in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit. , The execution state of a task that can be an execution protection task is changed to the running wait state, the data in the stack used by the task that can be an execution protection task is compressed, and the stack pointer of the task that can be an execution protection task is stored in the stack pointer. Store in the department. The stack usable task selection unit searches the execution protection task storage unit and finds the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit. A first identifier and a second identifier that have the maximum stack capacity to be used in the case of the non-executable state and have a smaller stack capacity currently used by the task corresponding to the first identifier than the stack capacity Extract the combination of. The task switching unit sets the execution state of the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task selection unit to the run-disabled state, and the second identifier. The execution state of the task corresponding to is set to the running state. The stack data decompression unit searches the task information storage unit to extract all the identifiers of the tasks whose execution state is in the running waiting state, and searches the stack pointer storage unit to extract the task corresponding to the identifier extracted from the task information storage unit. Extract the stack pointer and the execution state of the stack pointer, extract the stack pointer and the execution state from the stack pointer storage unit, expand the data in the stack used by the task, and extract the stack pointer and the execution state from the stack pointer storage unit. Change the execution state of the extracted task to the execution state extracted from the stack pointer storage unit, and delete the stack pointer and execution state of the task that extracted the stack pointer and execution state from the stack pointer storage unit from the stack pointer storage unit. To do.

[0013]

Embodiments of the present invention will now be described in detail with reference to the drawings. (Embodiment 1) FIG. 1 is a block diagram of a scheduling apparatus according to Embodiment 1 of the present invention. This scheduling apparatus includes a task information storage unit 1 and an execution protection task storage unit 2.
A task switching request unit 3, an executable task extraction unit 4, a running task extraction unit 5, a stack available task extraction unit 6, a stack available task selection unit 7, and a task switching unit 8. ing. Task information storage unit 1
Stores the identifier and execution status of each task. The execution protection task storage unit 2 stores the identifier of each task and the maximum stack capacity used by each task, and also stores the execution state when the task is in the run-disabled state and no stack is allocated. Is in the running state, the waiting state, or the runnable state, and the task is in the running state, the runnable state, or the runnable state, the runnable state is set. The execution protection task identifier and the maximum stack capacity used when the execution protection task is in the run-disabled state are stored. The task switching request unit 3 issues a task switching request. When the task switching request unit 3 issues a task switching request, the executable task extraction unit 4 searches the task information storage unit 1 and the execution protection task storage unit 2 to execute protection for any task. An identifier of a task which is not a task and whose execution state is the run-disabled state is extracted. The running task extraction unit 5 changes the running state of the task whose running state is the running state to the runnable state, searches the task information storage unit 1, and determines whether the task running state is the run-ready state or the runnable state. To extract the task identifier. Stack usable task extraction unit 6
Searches the execution protection task storage unit 2 when the identifier extracted by the executing task extraction unit 5 is the first identifier and the identifier extracted by the executable task extraction unit 4 is the second identifier. Then, the combination of the first identifier and the second identifier, which is the execution protection task of the task corresponding to the second identifier, corresponding to the first identifier, is extracted.
The stack usable task selection unit 7 searches the execution protection task storage unit 2 and corresponds to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit 6. The maximum stack capacity to be used when the task to be executed is in the run-disabled state is obtained, and the stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity. The combination with the identifier of is extracted. Task switching unit 8
Indicates that the execution state of the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task selection unit 7 is set to the run-disabled state and corresponds to the second identifier. Set the running state of the task to run.

The operation of the scheduling device will be described with reference to the flowchart of FIG. First, the task switching request unit 3 generates a task switching request by a conventionally known method such as timer interruption (step S1). Next executable task extractor 4
However, in response to the task switching request from the task switching requesting unit 3, neither the task information storage unit 1 nor the execution protection task storage unit 2 is an execution protection task for any task, and the execution state cannot run. The identifier of the task in the state is searched (step S2), and if the candidate identifier is not found, the process ends. Note that terminating the process when no candidate identifier is found means not returning the process to the normal scheduling device or switching the task, and this also applies to the following. If one or more candidate identifiers exist, they are extracted (step S3). Next, the running task extraction unit 5 changes the task whose running state is the running state to the runnable state, and searches the task information storage unit 1 for the identifier of the task whose running state is the runnable state or the run waiting state. If no candidate identifier is found (step S4), the process ends. If one or more candidate identifiers exist, they are extracted (step S5). Next, the stack usable task extraction unit 6 extracts from the execution protection task storage unit 2 a first identifier and a second identifier which are execution protection tasks of the task corresponding to the second identifier. The combination with the identifier is searched for (step S6), and if no candidate identifier is found, the process ends. If there are one or more candidate identifiers, they are extracted (step S7). Next, the stack usable task selection unit 7 causes the execution state of the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit 6 to not run. The maximum stack capacity used when the status is reached is acquired from the execution protection task storage unit 2, and a combination in which the stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity is searched for ( If no candidate identifier is found in step S8), the process ends. Candidate identifier is 1
If more than one exist, they are extracted (step S
9). Next, the task switching unit 8 sets the execution state of the execution protection task corresponding to the first identifier extracted by the stack usable task selection unit 7 to the run-disabled state, and the second state
The execution state of the task corresponding to the identifier is set to the running state (step S10), and the process ends.

Next, an example of a more specific operation of the scheduling device will be described. FIG. 3 is a conceptual diagram of the contents stored in the task information storage unit 1. The identifier 1
The execution state of the task is the running state, the execution state of the task with the identifier 2 is the run-disabled state, and the execution state of the task with the identifier 3 is the runnable state. The execution status stored in the task information storage unit 1 is appropriately changed as the execution status of the task changes.

FIG. 4 is a conceptual diagram of the contents stored in the execution protection task storage unit 2. The maximum stack capacity used by the task with the identifier 1 is 50, and there is no corresponding execution protection task. The maximum stack capacity used by the task with the identifier 2 is 50, and the identifier of the corresponding execution protection task is 1. In the case of the present embodiment, the fact that the identifier of the execution protection task corresponding to the task of identifier 2 is 1 means that the task of identifier 2 is in one of the runnable state, the run wait state, and the run state. Means that the stack capacity used by the task with identifier 1 must be 30 or less. The maximum stack capacity used by the task with identifier 3 is 70, and there is no corresponding execution protection task.

Now, it is assumed that the stack capacity used by the running identifier 1 is 25. First, the task switching request unit 3 generates a task switching request and passes it to the executable task extraction unit 4. As a result, the executable task extraction unit 4 does not execute the execution protection task for any task corresponding to the identifier stored in the task information storage unit 1 from the task information storage unit 1 and the execution protection task storage unit 2. An identifier of a task that is not present and whose execution state is in the run-disabled state is extracted. As a result of the extraction, the identifier 2 becomes a candidate. Next, the running task extraction unit 5 changes the task whose running state is the running state to the runnable state, and the task running state stored in the task information storage unit 1 is the run waiting state or runnable state. Extract the task identifier.
As a result of the extraction, the identifiers 1 and 3 are candidates. Next, the stack usable task extraction unit 6 extracts the identifier of the execution protection task corresponding to the identifier 1 or the identifier 3 extracted by the executing task extraction unit 5 from the execution protection task storage unit 2 and extracts the executable task. The identifier 2 extracted by the unit 4 is collated. As a result of the extraction, the combination of the identifier 1 and the identifier 2 is extracted as a candidate. Next, the stack usable task selection unit 7 uses the maximum stack that is used when the task corresponding to the identifier 1 that can be an execution protection task is in the run-disabled state based on the combination extracted by the stack usable task extraction unit 6. The capacity is extracted from the execution protection task storage unit 2 to obtain 30. Further, the stack usable task selection unit 7 extracts the stack capacity used by the task corresponding to the identifier 1 by a conventionally known method, and obtains 25. As a result, since 25 is 30 or less, the combination of identifier 1 and identifier 2 is extracted as a candidate. Next, the task switching unit 8 sets the task with the identifier 1 extracted by the stack usable task selection unit 7 in the run-disabled state, sets the task with the identifier 2 in the running state, and sets the stack used by the task with the identifier 1 Use to perform the task with identifier 2. Thus, the contents of the task information storage unit 1 are as shown in FIG. in this way,
You can select a combination of an executable task and another task that can use the stack, which makes it possible to effectively use the stack and solve the conventional problem that scheduling cannot be performed when the stack capacity is small. It can be reduced.

In the above specific example, the example in which the combination of the identifiers extracted as candidates by the stack usable task selection unit 7 is one set has been described, but a plurality of combinations may be extracted. In this case, any one of the extracted combinations of identifiers
Choose one combination. (Embodiment 2) FIG. 6 is a block diagram of a scheduling apparatus according to Embodiment 2 of the present invention. This scheduling apparatus includes a task information storage unit 11 and an execution protection task storage unit 1.
2, a task switching request unit 13, an executable task extraction unit 14, a running task extraction unit 15, a stack available task extraction unit 16, a stack available task selection unit 17, and a stack pointer storage unit 18. , A stack data compression unit 19, a stack data expansion unit 20, and a task switching unit 21. Task information storage unit 1
1 stores the identifier and execution state of each task. The execution protection task storage unit 12 stores the identifier of each task and the maximum stack capacity used by each task, and also stores the execution state when the task is in the run-disabled state and no stack is allocated. Is in the running state, the waiting state, or the runnable state, and the task is in the running state, the runnable state, or the runnable state, the runnable state is set. The execution protection task identifier and the maximum stack capacity used when the execution protection task is in the run-disabled state are stored. The task switching request unit 13 issues a task switching request. Executable task extraction unit 14
When the task switching requesting unit 13 issues a task switching request, the task switching requesting unit 13 searches the task information storage unit 11 and the execution protection task storage unit 12, and is not an execution protection task for any task and is in the execution state. Extracts the identifier of the task that is in the inoperable state. The running task extraction unit 15 changes the running state of the task whose running state is the running state to the runnable state, and the task information storage unit 11
Is extracted to extract the identifier of the task whose task execution state is the running waiting state or the runnable state. When the identifier extracted by the executing task extraction unit 15 is the first identifier and the identifier extracted by the executable task extraction unit 14 is the second identifier, the stack usable task extraction unit 16 performs execution protection. Search the task storage section 12,
A combination of the first identifier and the second identifier, which is the execution protection task of the task corresponding to the second identifier, corresponding to the first identifier is extracted. The stack usable task selection unit 17 searches the execution protection task storage unit 12,
The maximum stack capacity used when the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit 16 is in the run-disabled state, A combination of the first identifier and the second identifier whose stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity is extracted. The stack pointer storage unit 18 stores a task identifier, an execution state, and a stack pointer. The stack data compression unit 19 stores the execution state of the task corresponding to the identifier that can be the execution protection task in the combination of the first identifier and the second identifier extracted by the stack usable task extraction unit 16, into the stack pointer storage unit 18. Stored in the., Change the execution state of the task that can be the execution protection task to the running wait state, compress the data in the stack used by the task that can be the execution protection task, and It is stored in the stack pointer storage unit 18. The stack data expansion unit 20 searches the task information storage unit 11 to extract all the identifiers of the tasks whose execution states are in the running waiting state, and searches the stack pointer storage unit 18 to extract the identifiers extracted from the task information storage unit 11. The stack pointer and execution state of the task corresponding to are extracted, the stack pointer storage unit 18 extracts the stack pointer and the execution state from the data in the stack used by the task, and the stack pointer storage unit 18 extracts the data. The execution state of the task whose stack pointer and execution state are extracted is changed to the execution state extracted from the stack pointer storage unit 18, and the stack pointer and execution state of the task whose stack pointer and execution state are extracted from the stack pointer storage unit 18 And are deleted from the stack pointer storage unit 18. The task switching unit 21 sets the execution state of the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task selection unit 17 to the run-disabled state, and the second state. The execution state of the task corresponding to the identifier is set to the running state.

Next, the operation of the scheduling device will be described with reference to the flowchart of FIG.
First, the task switching request unit 13 issues a task switching request by a conventionally known method such as timer interruption (step S11). Next, the executable task extracting unit 14 receives the task switching request from the task switching requesting unit 13, and receives a task switching request from the task information storage unit 11 and the execution protection task storage unit 12 and determines that no task is an execution protection task. Also, the identifier of the task whose execution state is the run-disabled state is searched for (step S12), and when the candidate identifier is not found, the process ends. If there are one or more candidate identifiers, they are extracted (step S13). Next, the running task extraction unit 15 changes the task whose running state is the running state to the runnable state, and searches the task information storage unit 11 for the identifier of the task whose running state is the runnable state or the run waiting state. If no candidate identifier is found (step S14), the process ends. If there are one or more candidate identifiers, they are extracted (step S1).
5). Next, the stack usable task extraction unit 16 causes the execution protected task storage unit 12 to extract the first identifier candidate extracted by the executing task extraction unit 15 and the second identifier extracted by the executable task extraction unit 14. Of the candidates, the task corresponding to the first identifier is searched for a combination of the first identifier and the second identifier which is an execution protection task of the task corresponding to the second identifier (step S16), If no identifier is found, the process ends. If there are one or more candidate identifiers, they are extracted (step S17). Next, the stack data compression unit 19 stores, in the stack pointer storage unit 18, the execution state of the task corresponding to the identifier that can be the execution protection task among the combinations of the identifiers extracted by the stack usable task extraction unit 16, and the execution protection is performed. Corresponds to an identifier that can be an execution protection task by changing the execution state of a task that corresponds to an identifier that can be a task to a running wait state and compressing the data in the stack used by the task that corresponds to an identifier that can be an execution protection task The stack pointer of the task to be executed is stored in the stack pointer storage unit 18 (step S18). Next, the stack usable task selection unit 17
Of the combination of the first identifier and the second identifier extracted by the stack usable task extracting unit 16 and compressed by the stack data compressing unit 19, the execution state of the task corresponding to the first identifier runs. The maximum stack capacity to be used when the state becomes impossible is acquired from the execution protection task storage unit 12, and a combination in which the stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity is searched for. Then (step S19), if no candidate identifier is found, the process ends. If there are one or more candidate identifiers, they are extracted (step S20). Next, the task switching unit 21 sets the execution state of the execution protection task corresponding to the first identifier extracted as a candidate by the stack usable task selection unit 17 to the run-disabled state, and sets the task corresponding to the second identifier. The execution state is set to the traveling state, and the process is executed (step S21). When the processing of the tasks switched by the task switching unit 21 is completed, the stack data expansion unit 20 extracts from the task information storage unit 11 all the identifiers of the tasks whose execution state is the running waiting state, Stack pointer storage unit 1 for the identifier of
The stack pointer corresponding to the identifier and the execution state are extracted from 8, the data in the stack used by the task corresponding to the identifier is expanded, and the execution state of the task is extracted from the stack pointer storage unit 18 State, and the stack pointer and execution state of the task are deleted from the stack pointer storage unit 18 (step S2).
2).

Next, an example of a more specific operation of the scheduling device will be described. FIG. 8 is a conceptual diagram of the contents stored in the task information storage unit 11. The execution state of the task with the identifier 1 is the running state, the execution state of the task with the identifier 2 is the run-disabled state, and the execution state of the task with the identifier 3 is Is waiting to run. The task information storage unit 11
The execution state stored in is changed as the task execution state changes.

FIG. 9 is a conceptual diagram of the contents stored in the execution protection task storage unit 12. The maximum stack capacity used by the task with the identifier 1 is 50, and there is no corresponding execution protection task. The maximum stack capacity used by the task with the identifier 2 is 50, and the identifier of the corresponding execution protection task is 1. In the case of the present embodiment, the identifier of the execution protection task corresponding to the task of the identifier 2 is 1, which means that the task of the identifier 2 is in any of the runnable state, the run wait state, and the run state. That is, the stack capacity used by the task with identifier 1 must be 35 or less. The maximum stack capacity used by the task with identifier 3 is 70, and there is no corresponding execution protection task.

Here, an example of data compression will be shown. For example, in an 8-bit microcomputer, if the program is within 4 kilobytes, 2 bytes are used as a stack. Since 4 bits are actually used in the stack, 4 bits are unnecessary. Therefore, 4 bits are deleted. Considering that the stack has been stacked five times by the compression method described above, (12 × 5 + 4) / 16 × 5 = 0.
From the calculation of 8, the capacity is compressed to 80% of the capacity without compression.

Now, it is assumed that the stack capacity used by the running identifier 1 is 40. First, the task switching request unit 13 generates a task switching request and passes it to the executable task extraction unit 14. As a result, the executable task extraction unit 14 determines that the execution protection task does not execute any task corresponding to the identifier stored in the task information storage unit 11 from the task information storage unit 11 and the execution protection task storage unit 12. An identifier of a task that is not present and whose execution state is in the run-disabled state is extracted. As a result of the extraction, the identifier 2 becomes a candidate. Next, the executing task extraction unit 15 changes the task whose execution state is the running state to the runnable state,
An identifier of a task whose task execution state stored in the task information storage unit 11 is a running waiting state or a runnable state is extracted. As a result of the extraction, the identifiers 1 and 3 are candidates. Next, the stack usable task extraction unit 16
Extracts the identifier of the execution protection task corresponding to the identifier 1 or the identifier 3 extracted by the running task extraction unit 15 from the execution protection task storage unit 12, and the identifier 2 extracted by the executable task extraction unit 14 Collate. As a result of the extraction, the combination of the identifier 1 and the identifier 2 is extracted as a candidate. Next, the stack data compression unit 1
9 stores, in the stack pointer storage unit 18, the execution state of the task corresponding to the identifier 1 that can be the execution protection task in the combination of the identifier 1 and the identifier 2 extracted by the stack usable task extraction unit 16. The execution state of the task corresponding to the identifier is changed to the running wait state, the data in the stack used by the task corresponding to the identifier 1 is compressed, and the stack pointer of the task corresponding to the identifier 1 is stored in the stack pointer storage unit 18. Store. Thus, the contents of the task information storage unit 11 are as shown in FIG. 10, and the contents of the stack pointer storage unit 18 are as shown in FIG. That is, in the case of this embodiment, the stack pointer is 100. As a result of compressing the data in the stack, the stack capacity used by the task corresponding to the identifier 1 is compressed to 80% and becomes 32. Next, the stack usable task selection unit 17 uses the maximum stack that is used when the task corresponding to the identifier 1 that can be an execution protection task is in the run-disabled state based on the combination extracted by the stack usable task extraction unit 16. The capacity is extracted from the execution protection task storage unit 12, and 35 is obtained. Furthermore, the stack usable task selection unit extracts the stack capacity used by the task corresponding to the identifier 1 by a conventionally known method, and obtains 32. As a result, since 32 is 35 or less, the combination of identifier 1 and identifier 2 is extracted as a candidate. Next, the task switching unit 21 puts the task with the identifier 1 extracted by the stack available task selection unit 17 into the non-running state, sets the task with the identifier 2 into the running state, and sets the stack used by the task with the identifier 1 to the stack. Use to perform the task with identifier 2. Thus, the contents of the task information storage unit 11 are as shown in FIG. When the processing of the task switched by the task switching unit 21 is completed, the stack data expansion unit 20 extracts from the task information storage unit 11 all the identifiers of the tasks whose execution state is the running waiting state. The contents of the task information storage unit 11 immediately after the processing of the switched task is completed are as shown in FIG. As a result of the extraction, the identifiers 1 and 3 are candidates. For each of the extracted identifiers, the stack pointer storage unit 18 extracts the stack pointer and the execution state corresponding to the same identifier as the extracted identifier. As a result of the extraction, the stack pointer of the identifier 1 is 100, the execution state is the runnable state, and the identifier 3
Has no corresponding stack pointer and execution state.
Based on the extraction result, the data in the stack used by the task corresponding to the identifier 1 is expanded, the execution state of the task corresponding to the identifier 1 is changed to the runnable state, and the identifier 1
The stack pointer of the task corresponding to and the previous execution state are deleted from the stack pointer storage unit 18. Thus, the contents of the task information storage unit 11 are as shown in FIG.
The contents of the stack pointer storage unit 18 are as shown in FIG.

As described above, since a combination of an executable task and another task that can use the stack can be selected, the stack can be effectively used and scheduling cannot be performed when the stack capacity is small. The above-mentioned conventional problem can be favorably reduced. Also, the range of combinations of executable tasks and other tasks that can use the stack can be expanded, so that the stack can be used more effectively.

In the above specific example, an example in which the combination of the identifiers extracted as candidates by the stack usable task selection unit 17 is one set has been described, but it is also possible that a plurality of combinations are extracted. In this case, any one of the extracted combinations of identifiers
Choose one combination. The method of compressing the data in the stack is not limited to the method described in the above specific example, and other methods such as the adaptive Lempel-Jib coding method may be used.

[0026]

As described above, according to the present invention, a task having at least four execution states of a runnable state, a run wait state, a runnable state and a runnable state and a unique identifier in the system is provided. , A scheduling device in a system in which a plurality of tasks are executed by task switching, and a task information storage unit that stores an identifier and an execution state of each task, an identifier of each task, and a maximum stack capacity used by each task. In addition to storing, if the task is in the run-disabled state and no stack is allocated, the run-state is either the run-state, the run-wait state or the run-ready state, and the task-run state The identifier of the execution protection task that will be in the run-disabled state if is in the running state, the run-waiting state, or the runnable state , The execution protection task storage unit that stores the maximum stack capacity used when the execution protection task is in the run-disabled state, the task switching request unit that issues a task switching request, and the task switching request unit When a request is issued, the task information storage unit and the execution protection task storage unit are searched to extract the identifier of a task that is not an execution protection task and whose execution state is not runnable for any task. Executable task extractor to change the task's execution state to the runnable state and the task information storage section to search the task's runnable state Executable by extracting the identifier of a certain task from the running task extractor and the identifier extracted by the running task extractor as the first identifier When the identifier extracted by the task extraction unit is used as the second identifier, the execution protection task storage unit is searched and the task corresponding to the first identifier is the execution protection task of the task corresponding to the second identifier. A stack usable task extraction unit that extracts a combination of a certain first identifier and a second identifier and an execution protection task storage unit are searched, and the first identifier and the first identifier extracted by the stack usable task extraction unit are searched. The maximum stack capacity to be used when the task corresponding to the first identifier in the combination with the identifier of 2 becomes the inexecutable state, and the task corresponding to the first identifier than the stack capacity is currently used. The stack available task selection unit that extracts a combination of the first identifier and the second identifier that has a small stack capacity, and the stack available task selection unit extracts the combination. The first in the combination of the first identifier and the second identifier
The task switching unit that sets the execution state of the task corresponding to the identifier of No. 1 to the run-disabled state and the task corresponding to the second identifier to the running state, and uses the executable task and stack. Since a combination with another task that can be performed can be selected, the stack can be effectively used, and the conventional problem that scheduling cannot be performed when the stack capacity is small can be favorably reduced.

Further, in a system in which a plurality of tasks having at least four execution states of a runnable state, a run wait state, a runnable state and a runnable state and a unique identifier in the system are executed by task switching. A scheduling device, which stores a task information storage unit that stores an identifier and an execution state of each task, stores an identifier of each task and a maximum stack capacity used by each task, and stores the execution state of the task. If the task is in the runnable state and no stack is allocated, the execution state is either the running state, the run-waiting state, or the runnable state, and the task execution state is the runnable state, the run-waiting state, or the runnable state. If either of the above states is set, the identifier of the execution protection task that cannot run and the execution protection task cannot run State, the execution protection task storage unit that stores the maximum stack capacity that is used when the status becomes a state, the stack pointer storage unit that stores the task identifier, the execution status, and the stack pointer, and the task switching that generates the task switching request. When the request part and the task switching request part generate a task switching request, the task information storage part and the execution protection task storage part are searched, and neither of the tasks is an execution protection task and the execution status is Executable task extraction unit that extracts the identifier of the task that is in the non-runnable state, and the execution state of the task whose running state is the running state is changed to the runnable state, and the task information storage unit is searched to search for the task An executing task extracting unit that extracts an identifier of a task whose execution state is a running waiting state or a runnable state, and an executing task extracting unit When the extracted identifier is used as the first identifier and the identifier extracted by the executable task extraction unit is used as the second identifier, the execution protection task storage unit is searched and the task corresponding to the first identifier is searched. Is a stack usable task extraction unit that extracts a combination of the first identifier and the second identifier that is the execution protection task of the task corresponding to the second identifier, and the first task extracted by the stack usable task extraction unit The execution state of the task corresponding to the identifier that can be the execution protection task in the combination of the identifier of No. 2 and the second identifier is stored in the stack pointer storage unit, and the execution state of the task that can be the execution protection task is changed to the running waiting state The data in the stack used by the task that can be the execution protection task is compressed, and the stack pointer of the task that can be the execution protection task is saved. A first identifier in a combination of the first identifier and the second identifier extracted by the stack usable task extraction unit by searching the stack data compression unit to be stored in the tack pointer storage unit and the execution protection task storage unit. The maximum stack capacity used when the task corresponding to is in the non-executable state, and the stack capacity currently used by the task corresponding to the first identifier is smaller than that stack capacity A stack usable task selection unit that extracts a combination with the second identifier, and a task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task selection unit A task switching unit that sets the execution state to the run-disabled state and sets the execution state of the task corresponding to the second identifier to the run state;
The task information storage unit is searched to extract all the identifiers of the tasks whose execution status is waiting to run, the stack pointer storage unit is searched, and the stack pointer and execution status of the task corresponding to the identifier extracted from the task information storage unit Extract the and extract the stack pointer and execution state from the stack pointer storage, expand the data in the stack used by the task, and execute the task that extracted the stack pointer and execution state from the stack pointer storage. Change the state to the execution state extracted from the stack pointer storage,
Since a stack data decompression unit that deletes the stack pointer and execution state of a task that has extracted the stack pointer and execution state from the stack pointer storage unit from the stack pointer storage unit, an executable task and stack are used. Since you can select a combination with another task that can
The conventional problem that scheduling is not possible when the stack capacity is small can be reduced satisfactorily. Further, since the range of combinations of executable tasks and other tasks that can use the stack can be expanded, the stack can be used more effectively.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a scheduling device according to a first embodiment of the present invention.

FIG. 2 is a flowchart illustrating an operation of the scheduling device according to the first exemplary embodiment of the present invention.

FIG. 3 is a conceptual diagram of contents of a task information storage unit before task switching.

FIG. 4 is a conceptual diagram of contents of an execution protection task storage unit.

FIG. 5 is a conceptual diagram of contents of a task information storage unit after task switching.

FIG. 6 is a configuration diagram of a scheduling device according to a second embodiment of the present invention.

FIG. 7 is a flowchart illustrating an operation of the scheduling device according to the second exemplary embodiment of the present invention.

FIG. 8 is a conceptual diagram of contents of a task information storage unit before task switching.

FIG. 9 is a conceptual diagram of contents of an execution protection task storage unit.

FIG. 10 is a conceptual diagram of contents of a task information storage unit before task switching.

FIG. 11 is a conceptual diagram of contents of a stack pointer storage unit.

FIG. 12 is a conceptual diagram of contents of a task information storage unit after task switching.

FIG. 13 is a conceptual diagram of contents of a task information storage unit immediately after processing of a switched task is completed.

FIG. 14 is a conceptual diagram of contents of a task information storage unit after processing is completed.

FIG. 15 is a conceptual diagram of contents of a stack pointer storage unit after processing is completed.

[Explanation of symbols]

 1 task information storage unit 2 execution protection task storage unit 3 task switching request unit 4 executable task extraction unit 5 running task extraction unit 6 stack available task extraction unit 7 stack available task selection unit 8 task switching unit 11 task information storage Part 12 Execution protection task storage part 13 Task switching request part 14 Executable task extraction part 15 Executing task extraction part 16 Stack available task extraction part 17 Stack available task selection part 18 Stack pointer storage part 19 Stack data compression part 20 Stack Data development unit 21 Task switching unit

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Goichi Anbu 1006 Kadoma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd. (72) Kenji Ito, 1006 Kadoma, Kadoma City, Osaka Matsushita Electric Industrial Co., Ltd. (72) Inventor Shuji Abe 1006 Kadoma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd.

Claims (4)

(57) [Claims] 1. A system in which a plurality of tasks having at least four execution states of a runnable state, a run waiting state, a runnable state and a runnable state and a unique identifier in the system are executed by task switching A scheduling method, in which a task information storage unit that stores an identifier and an execution state of each task, an identifier of each task and the maximum stack capacity used by each task are stored, and the execution state of the task is not run. If the task is in the runnable state and no stack is allocated, the execution state is either the running state, the run-waiting state, or the runnable state, and the task execution state is the runnable state, the run-waiting state, or the runnable state. Of the execution protection task that is in the run-disabled state when either of the A task switching request step for issuing a task switching request, and a task switching request is generated in the task switching request step, using the execution protection task storage unit that stores the maximum stack capacity used when By doing so, the task information storage unit and the execution protection task storage unit are searched, and an identifier of a task which is not an execution protection task and whose execution state is in the run-disabled state for any task is executed. Available task extraction step and task execution state is running state Change the task running state to runnable state, search the task information storage unit, and the task execution state is run waiting state or runnable state An executing task extracting step of extracting a task identifier, and extracting in the executing task extracting step When the generated identifier is used as the first identifier and the identifier extracted in the executable task extraction step is used as the second identifier, the execution protection task storage unit is searched to correspond to the first identifier. A stack usable task extracting step of extracting a combination of a first identifier and a second identifier, which is an execution protection task of a task corresponding to the second identifier, and searching the execution protection task storage unit. , Obtaining the maximum stack capacity used when the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted in the stack usable task extraction step is in the inexecutable state A first identifier and a second identifier whose stack capacity currently used by the task corresponding to the first identifier is smaller than the stack capacity. A stack usable task selecting step for extracting a combination of the first and second identifiers in the stack usable task selecting step, and the task execution state corresponding to the first identifier in the combination of the first identifier and the second identifier extracted. And a task switching step of changing the execution state of the task corresponding to the second identifier to the running state, and executing the task switching step. 2. A computer system in which a plurality of tasks having at least four execution states of a runnable state, a run waiting state, a runnable state and a runnable state and a unique identifier in the system are executed by task switching. And a task information storage unit that stores an identifier and an execution state of each task, an identifier of each task and a maximum stack capacity used by each task, and a running state of the task. If the task is in the impossible state and the stack is not allocated, the execution state is either the running state, the waiting state or the runnable state, and the task execution state is the running state, the waiting state, or the runnable state. The identifier of the execution protection task that is in the run-disabled state if any of the states and the execution protection task is running. The execution protection task storage unit that stores the maximum stack capacity used when the status becomes ready, the task switching request unit that issues a task switching request, and the task switching request unit when the task switching request is issued. An executable task that searches the task information storage unit and the execution protection task storage unit and extracts an identifier of a task that is not an execution protection task for any task and whose execution state is a non-runnable state The extraction unit and the task execution state is the running state. The task execution state is changed to the runnable state, the task information storage unit is searched, and the task execution state of the task waiting state or runnable state is searched. A running task extracting unit that extracts an identifier, and an identifier extracted by the running task extracting unit
And the identifier extracted by the executable task extraction unit is used as the second identifier, the execution protection task storage unit is searched to find the task corresponding to the first identifier as the second identifier. A stack usable task extraction unit that extracts a combination of a first identifier and a second identifier that is an execution protection task of the task corresponding to the identifier; and a stack usable task that searches the execution protection task storage unit The maximum stack capacity used when the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the extraction unit is in the inexecutable state is obtained, and is larger than that stack capacity. A stack usable task for extracting a combination of the first identifier and the second identifier, which is currently used by the task corresponding to the first identifier and has a small stack capacity And a second identifier, in which the execution state of the task corresponding to the first identifier in the combination of the first identifier and the second identifier extracted by the stack usable task selector is set to the run-disabled state. And a task switching unit for changing the execution state of the task corresponding to the running state to a running state. 3. A computer system in which a plurality of tasks having at least four execution states of a runnable state, a run-waiting state, a runnable state and a runnable state and a unique identifier in the system are executed by task switching. In the scheduling method, the task information storage unit that stores the identifier and execution state of each task, the identifier of each task and the maximum stack capacity used by each task are stored, and the execution state of the task is run. If the task is in the impossible state and the stack is not allocated, the execution state is either the running state, the waiting state or the runnable state, and the task execution state is the running state, the waiting state, or the runnable state. The identifier of the execution protection task that is in the run-disabled state if any of the states is Execution protection task storage unit that stores the maximum stack capacity used when it becomes ready,
A task switching request step for generating a task switching request using a stack pointer storage unit that stores a task identifier, an execution state, and a stack pointer, and a task switching request generated in the task switching request step. An executable task that searches the task information storage unit and the execution protection task storage unit and extracts an identifier of a task that is not an execution protection task for any task and whose execution state is a non-runnable state The extraction step and the task execution state is the running state. The task execution state is changed to the runnable state, the task information storage unit is searched, and the task execution state of the task waiting state or runnable state is searched. In the executing task extracting step for extracting the identifier, and in the executing task extracting step, When the extracted identifier is used as the first identifier and the identifier extracted in the executable task extraction step is used as the second identifier, the execution protection task storage unit is searched and the first identifier is used as the first identifier. A stack available task extracting step of extracting a combination of a first identifier and a second identifier, the corresponding task being an execution protection task of a task corresponding to the second identifier, and the stack available task extracting step The execution state of the task corresponding to the identifier that can be the execution protection task in the combination of the extracted first identifier and second identifier is stored in the stack pointer storage unit, and the execution state of the task that can be the execution protection task is stored. Change to the running wait state, compress the data in the stack used by the task that can be the execution protection task, A stack data compression step of storing a stack pointer of a task that can be the execution protection task in the stack pointer storage unit; and a first data extracted in the stack usable task extraction step by searching the execution protection task storage unit. The maximum stack capacity used when the task corresponding to the first identifier in the combination of the identifier and the second identifier is in the inexecutable state is obtained, and the task corresponding to the first identifier is obtained from the stack capacity. A stack usable task selecting step for extracting a combination of the first identifier and the second identifier having a small stack capacity currently used by the first identifier and the first identifier extracted in the stack usable task selecting step; Runs the task execution state corresponding to the first identifier in combination with the second identifier A task switching step in which the task is enabled and the execution state of the task corresponding to the second identifier is in the running state; and the task information storage unit is searched to extract all the task identifiers whose execution state is in the running waiting state, A task that retrieves the stack pointer storage unit and extracts the stack pointer and execution state of the task corresponding to the identifier extracted from the task information storage unit, and extracts the stack pointer and execution state from the stack pointer storage unit The data in the stack being used is expanded, and the execution state of the task in which the stack pointer and the execution state are extracted from the stack pointer storage unit is changed to the execution state extracted from the stack pointer storage unit. Task stack pointer and execution status extracted from the stack pointer and execution status Scheduling method and executes a stack data expansion step to remove the door from the stack pointer storage portion. 4. A computer system in which a plurality of tasks having at least four execution states of a runnable state, a run-waiting state, a runnable state and a runnable state and a unique identifier in the system are executed by task switching. And a task information storage unit that stores an identifier and an execution state of each task, an identifier of each task and a maximum stack capacity used by each task, and a running state of the task. If the task is in the impossible state and the stack is not allocated, the execution state is either the running state, the waiting state or the runnable state, and the task execution state is the running state, the waiting state, or the runnable state. The identifier of the execution protection task that is in the run-disabled state if any of the states and the execution protection task is running. Execution protection task storage that stores the maximum stack capacity used when the status becomes ready, a stack pointer storage that stores the task identifier, execution status, and stack pointer, and a task that issues a task switching request A switching request unit, and when the task switching request unit issues a task switching request, the task information storage unit and the execution protection task storage unit are searched for And the executable task extraction unit that extracts the identifier of the task whose execution state is the non-runnable state, and the execution state of the task whose task execution state is the running state is changed to the runnable state, and the task information storage unit is Task ID extraction that searches and extracts the identifier of the task whose task execution status is the RUNNING state or RUNNABLE state If the identifier extracted by the executing task extractor first
And the identifier extracted by the executable task extraction unit is used as the second identifier, the execution protection task storage unit is searched to find the task corresponding to the first identifier as the second identifier. A stack usable task extraction unit that extracts a combination of a first identifier and a second identifier, which is an execution protection task of a task corresponding to the identifier, and a first identifier extracted by the stack usable task extraction unit The execution state of the task corresponding to the identifier that can be the execution protection task in combination with the second identifier is stored in the stack pointer storage unit, and the execution state of the task that can be the execution protection task is changed to the running wait state, The data in the stack used by the task that can be an execution protection task is compressed, and the stack port of the task that can be the execution protection task is compressed. A stack data compression unit that stores an interface in the stack pointer storage unit; and a combination of the first identifier and the second identifier extracted by the stack usable task extraction unit by searching the execution protection task storage unit. The maximum stack capacity to be used when the task corresponding to the first identifier becomes in the non-executable state, and the stack capacity currently used by the task corresponding to the first identifier is larger than the stack capacity. A stack usable task selection unit that extracts a combination of a small first identifier and a second identifier, and a first combination of the first identifier and the second identifier extracted by the stack usable task selection unit. Of the task corresponding to the second identifier is set to the running state, and the execution state of the task corresponding to the second identifier is set to the running state. The switching unit and the task information storage unit are searched to extract all the identifiers of the tasks whose execution state is the running waiting state, and the stack pointer storage unit is searched to correspond to the identifier extracted from the task information storage unit. The stack pointer and the execution state of the task are extracted, the stack pointer and the execution state are extracted from the stack pointer storage unit, and the data in the stack used by the task is expanded. The execution state and the execution state of the extracted task are changed to the execution state extracted from the stack pointer storage unit, and the stack pointer and the execution state of the task whose stack pointer and execution state are extracted from the stack pointer storage unit are stored in the stack. A stack data expansion unit that deletes from the pointer storage unit is provided. Scheduling apparatus according to claim.