Task execution device and method

[0001] (1) Field of the Invention

[0002] The present invention relates to a task execution device which allocates execution time to tasks to be executed in a Central Processing Unit (CPU), in other words, relates to an Operating System (OS).

[0003] (2) Description of the Related Art

[0004] The main functions of the OS are “hardware management”, “task management”, “data management” and “input/output management”. Above all, “task management” refers to the management of the task execution sequence, and is an important function for making a CPU, a memory, an input/output device, and so on, operate effectively. Here, a “task” is a unit of control which manages a series of flows, such as the start-up, execution and completion of a program, as a batch. A program which operates under the OS's management is handled as a task. The tasks in every OS operation related to the execution of a program are performed as units.

[0005] The time-sharing scheduling method is well-known as an example of an algorithm which determines a task execution sequence. The time-sharing scheduling method is a task scheduling method which allocates an execution time for each task, applies the allocated times to tasks in the CPU which have execution permission, and when the times allocated for the tasks elapse, transfers execution permission to other tasks. By doing so, execution permission is assigned for every task by an equal and determined time.

[0006] There are methods for the determination of the allocated time such as a method of fixed allocation according to a task's properties, and a method of dynamic determination according to the task's execution conditions, and for instance, methods such as adjusting the allocated time for the execution permission, based on task priority, are well known (see for example, Japanese Laid-Open Patent Application No. 2005-18560 Publication).

[0007] However, in the case where a task is shifted to a waiting state when it must wait for an event, conventional OSs will transfer execution permission to a subsequent task, or execute no processes until the allocated time has expired for the task shifted to the waiting state. Also, in an execution environment where tasks which need a guarantee of process performance, and tasks for which processes are generated asynchronously, such as an event driven process, co-exist, asynchronous processes must be executed while continuously distributing process performance and maintaining the cycle for the entire process is maintained. As a result there are the problems that overhead occurs, and processing power drops due to the continuous adjustment and execution of the allocated time.

[0008] The present invention is conceived in order to achieve the objects above, and aims to provide a task execution device and method which can reduce a load accompanying the allocated adjustments for the allocated time of a task while preserving a fixed processing power.

[0009] In order to achieve the objects above, the task execution device in the present invention is a task execution device for executing a plurality of tasks while switching the tasks from one to another by time-sharing, wherein an allocated time is allocated for each of the plurality of tasks, and the plurality of tasks includes a plurality of first-type tasks and a single second-type task. The task execution device including: a cycle time storage unit which stores a cycle time, which is a total time of the allocated times for the plurality of tasks; a task selection unit which selects a task from among the plurality of tasks according to a predetermined sequence; a correction unit which, when the selected task is the second-type task, corrects an allocated time for the selected second-type task so that execution of the plurality of tasks completes within the cycle time; and a task execution control unit which causes the selected task to be executed so that execution of the task completes within one of the allocated time and the corrected allocated time.

[0010] According to this configuration, the tasks which are executed in the processor are divided into first-type tasks and a second-type task, and corrections to the allocated time are performed for only the second-type task, such that the plurality of tasks are executed within the cycle time. As a result, while a fixed processing power is preserved, a task scheduling device can be provided which can reduce the load accompanying the allocated adjustments for the task execution time. Note that corrections to the allocated time for the second type task do not have to be performed in the case where all of the first type tasks are shifted into a waiting state.

[0011] Preferably the allocated time for the second-type task is one of a first allocated time, which is the minimum time which must be executed for the execution time of the task, and a second allocated time, which is a sum of a predetermined margin time and the first allocated time, and the correction unit further includes: a total consumed time calculation unit which calculates a total consumed time consumed in the execution of the plurality of first-type tasks; and an allocated time correction unit which corrects the allocated time for the second-type by subtracting from the margin time a difference between the total consumed time and the total allocated time for the plurality of first-type tasks, and by adding the result of the subtraction to the first allocated time. More specifically, in the case where the difference between the total consumed time and the total allocated time for the second-type task is larger than the margin time, the allocated time correction unit which corrects the allocated time by adding a time, which is a result of subtracting the margin time from the difference between the total consumed time and the total allocated time, to the first allocated time for a second-type task to be executed in a subsequent cycle, so that a result of the addition does not exceed the cycle time where the cycle is an interval during which each of the plurality of tasks are executed once.

[0012] By assuming a configuration like this, the first allocated time is reserved for the second-type task and the second-type task can be reliably executed.

[0013] Preferably, the task execution device mentioned above further includes a power supply reduction unit which reduces supply of electric power to a processor in which the second-type task is executed, during the allocated time for the second type task, in the case where the second-type task is shifted into a waiting state. In addition, the task execution device mentioned above further includes a power supply stopping unit which stops supply of electric power to a processor in which the plurality of tasks is executed, in the case where all of the plurality of tasks is shifted into a waiting state.

[0014] The execution situation of each task is detected, and by changing the task to a state of providing power to the processor, the power that must be consumed for the execution of the task can be reduced.

[0015] Note that the present invention may be realized not only as the task execution device above but also as a task execution method which includes the characteristic units included in the task execution device as steps, and as an operating system for causing a computer to execute these steps. It goes without saying that this sort of program can be distributed through a recording medium such as a CD-ROM and a transmission medium such as the Internet.

[0016] According to the present invention, a task scheduling device can be provided which can reduce the load accompanying the allocated adjustments for the task execution time while preserving a fixed processing power.

[0017] The disclosure of Japanese Patent Application No. 2005-243417 filed on Aug. 24, 2005 including specification, drawings and claims is incorporated herein by reference in its entirety.

[0025] Overall Structure

[0026] FIG. 1 is a block diagram which shows a structure of the principal part of a task execution device which switches tasks in the embodiment of the present invention. In the figure is shown a typical functions realized by executing software which switches tasks as a function of a part of the OS in a processor. The hardware structure of the processor may be a standard structure.

[0027] The task execution device is configured to handle every plurality of tasks which have an “allocated time” designation in one processor, and to execute the program while maintaining the performance necessary for each task.

[0028] The task execution device is configured, as shown in the figure, from a task scheduling unit 10, a program storage unit 20, a timer control unit 30 and an execution control unit 40.

[0029] The task scheduling unit 10 allocates a time-slot to each task which has an “allocated time” designation and performs time division scheduling, which selects each task at least once within a cycle that has been designated in advance. Here, the “time slot” is a slot delimited by the program execution time in the processor for every allocated time within a cycle T, which has been predetermined.

[0030] The program storage unit 20 stores the program, which is a concatenation of tasks, and which is targeted for scheduling by the task scheduling unit 10, and also stores data related to the program.

[0031] The timer control unit 30 starts a time count for each allocated time set by the task scheduling unit 10, and outputs a time-out signal when the allocated time has been reached. This time-out signal notifies the task scheduling unit 10 of the timing for the time slot's switching.

[0032] The execution control unit 40 executes a task selected by the task scheduling unit 10. The execution control unit 40 corresponds to the hardware which executes the task, such as a CPU.

[0033] (Configuration of task scheduling unit 10)

[0034] The task scheduling unit 10 is configured from a task acceptance unit 11, a time slot storage unit 12, a task storage unit 13, a time slot switching unit 14 and a task selection unit 15.

[0035] <1. Task acceptance unit 11>

[0036] The task acceptance unit 11 accepts a task addition request according to an instruction from a user operation, a user program and so on, and reads out “task data” and “allocated time” from the program storage unit 20 as data related to the task. In addition, the task acceptance unit 11 generates a time slot data 100 (110) and a task management block 200 (210) from the task data and the allocated time so that the task is targeted for scheduling, and configures the time slot data 100 (110) and the task management block 200 (210) in the time slot storage unit 12 and the task storage unit 13, respectively.

[0037] Here, “task data” includes a “program start address” and a “stack pointer”. The “program start address” is the initial address into which the task is written. The “stack pointer” is position data which shows the holding location, which temporarily saves the task state when task switching has occurred.

[0038] The tasks are assigned in one to one correspondence with a time slot by the task scheduling unit 10, and are executed securely within the allocated times of the time slot.

[0039] The tasks are classified into two types, according to their execution properties (type A and type B). Tasks which need a fixed process performance are included under “type A”. Tasks which are called time-driven tasks should be included under type A. For example, it is preferable to include a task under type A which requires a constant process performance and maintains a decoding and encoding process for video data and a decoding and encoding process for audio.

[0040] On the other hand, tasks which do not need a constant process performance are included under “type B”. Tasks which are called event-driven tasks should be included in type B. For example, tasks which maintain and do not need a constant process performance, but occur irregularly and occasionally, such as a process which carries out a menu display, of text and still images, displaying a user's operation as an event, are preferably included under type B.

[0041] The “allocated time” is a value which designates the allocated time for the time-slot which corresponds to the task. This allocated time is a time designated by the program.

[0042] Note that the total allocated time for the tasks executed in one cycle is held in a cycle resistor 16 as the cycle T.

[0043] <2. Time-slot storage unit 12>

[0044] The time-slot storage unit 12 stores time slot data for generating time slots, which serve as the basis for task switching.

[0045] FIG. 2 is a diagram which shows a specific example of time slot data in the time slot storage unit 12, and task management blocks in the task storage unit 13. As shown in the figure, the time slot storage unit 12 stores a plurality of time slot data 100, 110, . . . 120, 130. The time slot data from 100 to 120 indicate time slots to which type A tasks have been assigned. Additionally, the remaining time slot data 130 indicates a time slot to which a type B task has been assigned.

[0046] The time slot data 100 corresponds to one time slot and is made up of an allocated time 100a, an execution flag 100b and a pointer 100c; this is the same for other time slot data.

[0047] The allocated time 100a indicates a time in which a task corresponding to a time slot can be executed. When the time that the task has actually taken to execute reaches the allocated time, the task corresponding to the subsequent time slot is executed. The allocated times from 100a to 120a, which correspond to type A tasks, are set respectively by timer control unit 30, at the same time that the time slot data from 100 to 120 are generated. The allocated time 130a, which corresponds to a plurality of type B tasks is assumed to be the remaining time after subtracting the total of the allocated times for the other time slots from 100a to 120a from a time T of one cycle, held in the cycle resistor 16. This remaining time is a value that changes according to the task scheduling. Note that the calculation method for the allocated time 130a is an example, and other calculation methods are elaborated below.

[0048] The “execution flag” indicates whether the time slot is valid or invalid. The execution flag is set as valid when the time slot data is generated, is set as invalid when the resources of the access destination enter a locked state during the execution of the task and the task has entered a waiting state; afterwards, the execution flag is set as valid when the task returns from the waiting state to the execution permitted state. When the execution flag indicates that it is invalid, the time slot data from the time slot switching unit 14 regards the execution flag as not existing.

[0049] The “pointer” indicates a task management block which corresponds to the time slot. These time slot data 100, 110, 120, 130 compose an array, and the sequence of this array expresses the generation sequence for the time slots.

[0050] <3. Task storage unit 13>

[0051] The task storage unit 13 stores the task management blocks 200, 210, . . . , 220 and 230, which correspond to the tasks assigned to the time slots. The task management blocks 200, 210, . . . , 220 and 230 correspond to each task respectively, and are data for managing the tasks.

[0052] The task management block 200 is made with the task data 200a. The task data 200a includes a program start address (or an address at which execute of a program resumes) and a stack pointer. When the task management block 200 is generated, the task data 200a is the task data itself inputted by the task acceptance unit 11. When switching tasks, the task data 200a indicates the execution address and the value of the stack pointer at the point in time at which a task has been interrupted.

[0053] <4. Time slot switching unit 14>

[0054] The time slot switching unit 14 performs time slot switching when the execution time for a task in the present time slot has reached the allocated time. The timer control unit 30 notifies the time slot switching unit 14, by a time-out signal, whether or not the allocated time has been reached. The time slot switching unit 14 which has received the notification selects the subsequent time slot data.

[0055] In the present embodiment, the subsequent time slot data is selected according to the sequence of time slot data in the array. In other words, the time slot data is selected in the sequence of the time slot data 100, 110, . . . , 120, 130, and after the last time slot data 130 is selected, it is assumed that the first time slot data 100 is re-selected.

[0056] The time slot switching unit 14 acquires the allocated time from the time slot data selected, and sets this in the timer control unit 30. By doing so, a time count for the allocated time for the subsequent time slot is started.

[0057] <5. Task selection unit 15>

[0058] The task selection unit 15 saves the execution address, the stack pointer and so on for the program that is currently being executed, as task data, into the task's task management block, when the time slot has been switched by the time slot switching unit 14, or when there has been an instruction from the program that is currently being executed. The task selection unit 15 extracts task data from the task management block of the task which must be executed subsequently and outputs the task data to the execution control unit 40. Simultaneously, the task selection unit 15 saves the context (resistor data, and so on) of the task currently being executed and resets the context of the task which must be executed subsequently. By doing so, the task which must be executed subsequently enters an execution state.

[0059] FIG. 3 is an explanatory diagram which shows a description of the task switching performed by the time slot switching unit 14 and the task selection unit 15.

[0060] In the figure, the cycle T indicates a cycle that is held by the cycle resistor 16. The time slots from t1 to tn correspond to n time slot data 100, 110, . . . , 120, which in turn correspond to n type A tasks, and the length (from t1 to tn) indicates the allocated time for n tasks respectively. Additionally, t0 is a time slot which corresponds to the time slot data 130, which in turn corresponds to a type B task, and the length (t0) indicates the type B task's allocated time.

[0061] S indicates the scheduling process in which task switching is performed by the time slot switching unit 14 and the task selection unit 15.

[0062] In the figure, the type A task A1 which corresponds to the time slot data 100 is selected and executed in the scheduling process S when the time slot t1 is started. Type A tasks are executed in the same way for any of the time slots from t2 to tn. Also, a type B task is selected and executed in the scheduling process S for the final time slot t0. In this way, each task will definitely be executed at least once within one cycle T. In addition, a type B task B will be executed only once within one cycle T.

[0063] Details of the Process

[0064] Below, the scheduling process executed by the task execution device in the present embodiment is described.

[0065] <1. Scheduling process>

[0066] The scheduling process is described based on the flowchart in FIG. 4. When the time set by the timer control unit 30 elapses, a time-out signal is transmitted to the time slot switching unit 14 and the scheduling process starts. First, the task state currently being executed is saved in the task data (S301). Next, the time slot switching unit 14 performs a time slot selection process (S302). In other words, the content following the content currently selected in the time slot data array becomes the time slot data to be subsequently selected. In the case where there is not a subsequent content, the initial content in the time slot data array is selected. In other words, the time slot switching unit 14 performs selection sequentially from the time slot data 100 of the time slot t1 to the time slot data 130 of the time slot t0, and afterwards performs selection again sequentially, starting from the time slot data 100 of the time slot t1.

[0067] The handling of the allocated time and the operations differ when the task in the time slot is invalid, or in a waiting state, according to whether or not the time slot t0 be subsequently selected is the time slot t0 (S303).

[0068] In the case where a time slot other than the time slot t0 has been selected (No in S303), the time slot switching unit 14 extracts the allocated time included in the time slot data of the selected time slot and outputs this allocated time to the timer control unit 30 (S304). After a time has elapsed from this point in time equal to the allocated time, a time-out signal is transmitted again from the timer control unit 30.

[0069] When an execution flag, held by the time slot data of the selected time slot, is invalid (No in S305), this indicates that there is no task to be executed, or the task is in a waiting state. As a result, the time slot switching unit 14 switches the time slot to the subsequent time slot and performs the same process until a valid time slot is found.

[0070] If there is a valid time slot (Yes in S305), the task selection unit 15 resets the state of the interrupted task corresponding to the time slot, and the execution control unit 40 resumes the execution of the task (S306).

[0071] When the time slot switching unit 14 selects the time slot t0 (Yes in S303), the time slot switching unit 14 begins by calculating the allocated time for the time slot t0 (S307). Since the process covers a broad spectrum, the details are described afterward. The time slot switching unit 14 outputs the allocated time calculated in the process to the timer control unit 30 (S308).

[0072] When the execution flag held by the time slot is valid (Yes in S309), in the same way as above when the time slot selected is a time slot other than t0, the task selection unit 15 resets the state of the interrupted task corresponding to the time slot t0, and the execution control unit 40 resumes the task (S306).

[0073] When the execution flag held by the time slot is invalid (No in S309), the time slot switching unit 14 checks to see whether all of the execution flags in the time slots other than the time slot t0 are invalid (S310). When all of the execution flags are invalid (Yes in S310), the task selection unit 15 shifts the CPU into a stopped state since there is not a valid execution process for every task in the time slot. In order to perform a reset from the stopped state, an outside signal such as an interrupt is used.

[0074] If there is even one valid time slot (No in S310), the CPU is made to operate, however since there is no need to make the CPU operate during the allocated time for the time slot t0, the CPU is shifted into a power-saving state.

<2. Process for calculating the allocated time for the time slot t0>

[0075] Next, the process for calculating the allocated time for the time slot t0 (S307 in FIG. 4) is described based on the flowcharts in FIG. 5 and FIG. 6. There are three variations to the process which are described respectively.

[0076] (a) Case where the allocated time for a time slot in the waiting state is allocated for the time slot t0

[0077] As shown in FIG. 5, the total time consumed in the execution of tasks in a previous cycle (total time consumed) and the total allocated time for the time slots with invalid execution flags (non-execution time) are calculated for the time slots from the time slot t1 to tn (from S401 to S404).

[0078] When the total consumed time is larger than the total allocated time for the time slots from t1 to tn, the influence of an external cause such as an interruption is interpreted to be the cause. Because of this, the result of (total consumed time—total allocated time) is subtracted from the total allocated time for the time slots with invalid execution flags, i.e. from the non-execution time. In other words, the result of (total consumed time—total allocated time), which is the time exceeded on account of an external cause, is subtracted from the time in which the task assigned for the time slot is not being executed (non-execution time).

[0079] Adding the allocated time for the time slot t0 to this value gives the allocated time for the time slot t0 after calculation (S406).

[0080] Note that even if the total consumed time is smaller than the total allocated time, the allocated time for the time slot t0 can be calculated by using the same equation.

[0081] (b) Case where the margin time is set, and from it is decremented the portion of consumed time exceeding the allocated time

[0082] As shown in FIG. 6, a margin value 17 is set in advance by the task acceptance unit 11 and the value is acquired from the acceptance unit 11 (S411). The margin value 17 is a margin time (margin time) M, allocated to the allocated time for the time slot t0. In other words, there are assumed to be two stages for the allocated time for the time slot t0, t0 and (t0+M).

[0083] First, the total for the time consumed in execution for a previous cycle (total consumed time) is calculated for the time slots from t1 to tn (S412, S413).

[0084] Next, when the total consumed time is more than the total allocated time, the result of (total consumed time—total allocated time) is subtracted from the margin time M (S414). Here, the total allocated time refers to the total allocated time for the time slots from t1 to tn.

[0085] The time result after adding the allocated time for the time slot t0 to the value after subtraction gives the allocated time after calculation for the time slot t0 (S415).

[0086] Note that when the margin M<the result of (total consumed time−total allocated time), in other words, when the value sought at S414 is negative, the margin time M is set to 0 and the result of ((total consumed time−total allocated time)−the margin M) is time-adjusted for execution in the time slot t0 of the subsequent cycle. This way, the tasks can be executed while keeping the allocated time for the time slot t0 in this cycle T.

[0087] (c) Instead of the margin value, the value given by acquiring a cycle 15 from the task acceptance unit 11, and subtracting the total consumed time from the cycle T (the total allocated time), may be set as the allocated time for the time slot t0 after calculation.

[0088] As described above, according to the task execution device in the present embodiment, performance can be retained by calculating and setting only the allocated time for a particular time slot, without re-calculating the allocated time for another time slot. As a result, it becomes possible to reduce the overhead necessary for re-setting the allocated time in the case where the situation has changed.

[0089] Also, by detecting the execution situation of the time slot and changing the CPU state, the present invention can contribute to reducing electricity consumption related to program execution.

[0090] Note that in the above embodiment, the case was described where one allocated time was designated for every task data as a fixed value for the time slots with type A tasks, however the task execution device may be realized as a configuration in which the task execution device retains two fixed values which indicate the largest and smallest values of the allocated times for every time slot, takes the total of the largest values of the allocated times for all of the time slots as a cycle, and operates while each time slot selects one of the allocated times according to the execution situation.

[0091] In addition, in the case where it is detected that the smallest value is selected in each time slot, the process will conclude in a short amount of time. Because of this, the operation frequency of the CPU may be lowered in order to execute a task within a range before one cycle's worth of process concludes in the set cycle T. As a result, it is possible to further contribute to a reduction in electricity consumption necessary for the execution of the task. Note that it is determined on a program, whether the largest values or the smallest values of the allocated times are used.

[0092] The task execution device in the present invention has (a) function(s) for adjusting all of the allocated time by time allocation which does not depend on process performance, while performing a fixed time allocation which ensures process performance. Because of this, it is possible to reduce the process load in allocated time adjustment for processes which ensure process performance; for example image reproduction processes can be carried out without being affected by noise or disturbance of image output caused by access from outside. In particular, the present invention can be applied as a device which performs audio/visual processes and non-synchronous control processes in real-time, as well as a development environment for such a device.