Task scheduling method and apparatus
A task scheduling method and apparatus are provided to execute periodic tasks together with an aperiodic real-time task in a single system, to perform scheduling while satisfying a precedence relation between periodic tasks, and to perform scheduling so that an aperiodic real-time task may be efficiently executed for a residual time left after scheduling of the periodic tasks. Additionally, a component scheduling method and apparatus in robot software are provided.
1. A method of performing a scheduling algorithm in a system used to execute a plurality of periodic tasks and at least one aperiodic real-time task, the method comprising:
scheduling the periodic tasks based on a precedence relation between the periodic tasks; and
scheduling the aperiodic real-time task for a residual time, when a request to schedule the aperiodic real-time task is received from the system, the residual time being left after the scheduling of the periodic tasks, wherein the scheduling of the periodic tasks comprises:
repeatedly deleting periodic tasks corresponding to vertices with an indegree of 0 in a graph structure, from among the periodic tasks;
topologically sorting the deleted periodic tasks in an order in which the periodic tasks are deleted, and assigning priorities to the periodic tasks; and
scheduling the periodic tasks based on the assigned priorities.
2. The method of claim 1 , wherein the repeatedly deleting comprises, when a plurality of periodic tasks correspond to the vertices with the indegree of 0, comparing periods of the plurality of periodic tasks, and deleting a periodic task with a shorter period than the other periods, based on a result of the comparing.
3. The method of claim 1 , further comprising:
allowing an execution of the aperiodic real-time task requested to be scheduled, depending on whether the residual time is longer than an execution time of the aperiodic real-time task.
4. The method of claim 3 , further comprising:
assigning a highest priority to the aperiodic real-time task, when the execution of the aperiodic real-time task is allowed;
updating critical times of the periodic tasks; and
when a critical time of a periodic task among the periodic tasks is approaching due to the updating, executing the periodic task earlier than the aperiodic real-time task.
5. The method of claim 3 , wherein the executing of the periodic task comprises:
assigning a lowest priority to the aperiodic real-time task;
executing the periodic task; and
re-assigning the highest priority to the aperiodic real-time task, when the executing of the periodic task is completed.
6. A scheduling apparatus in a system used to execute a plurality of periodic tasks and at least one aperiodic real-time task, the scheduling apparatus comprising:
a processor;
a periodic task scheduler to schedule, using the processor, the periodic tasks based on a precedence relation between the periodic tasks;
a scheduling request receiver to receive, from the system, a request to schedule the aperiodic real-time task; and
an aperiodic real-time task scheduler to schedule, using the processor, the aperiodic real-time task for a residual time left after the scheduling of the periodic tasks,
wherein the periodic task scheduler repeatedly deletes periodic tasks corresponding to vertices with an indegree of 0 in a graph structure, from among the periodic tasks, topologically sorts the deleted periodic tasks in an order in which the periodic tasks are deleted, assigns priorities to the periodic tasks, and schedules the periodic tasks based on the assigned priorities.