Method and device for scheduling tasks in multi-core processor
An electronic device includes: a plurality of processing cores and a memory including a plurality of task queues respectively corresponding to the plurality of processing cores and a plurality of task relation tables respectively corresponding to a plurality of tasks. Each of the plurality of task relation tables includes: one or more entries representing a mapping relationship between an identifier of a waker task that wakes up a wakee task, and an occurrence count that is a number of times the wakee task is woken up by the waker task. At least one of the plurality of processing cores is configured to: execute a scheduler, search for a task set includes related tasks, based on the plurality of task relation tables, store a subset of tasks of the task set in at least one of the plurality of task queues, and schedule the task set.
1 . An electronic device comprising:
a plurality of processing cores; and
a memory comprising a plurality of task queues respectively corresponding to the plurality of processing cores, a plurality of task relation tables corresponding to a plurality of tasks, and a scheduler, wherein:
each of the plurality of task relation tables comprises a first number of entries representing a mapping relationship between an identifier of a waker task that wakes up a wakee task, and an occurrence count that is a number of times the wakee task is woken up by the waker task,
a first processing core among the plurality of processing cores is configured to execute the scheduler to
store a subset of tasks of a task set comprising related tasks in a first task queue among the plurality of task queues,
the task set is based on the plurality of task relation tables,
the first processing core is configured to sequentially execute the subset of tasks of the task set stored in the first task queue, and
at least one processing core among the plurality of processing cores is configured to execute the scheduler to
store at least one updated task relation table of a plurality of updated task relation tables in the memory when the first processing core executes a first waker task waking up a first wakee task, wherein:
each of the plurality of updated task relation tables includes a second number of entries less than the first number of entries,
each of the second number of entries corresponds to an occurrence count that is not less than a reference count,
the occurrence count of each entry included in the plurality of updated task relation tables is less than an initial occurrence count in response to an update event, and
the occurrence count in a first updated task relation table among the plurality of updated task relation tables corresponding to the first wakee task is greater than the occurrence count in the other updated task relation tables.
2 . The electronic device of claim 1 , wherein:
at least one key task among the plurality of tasks is based on attributes of the plurality of tasks,
a Markov chain representing a probability of a state transition between an edge corresponding to the waker task and an edge corresponding to the wakee task is based on the plurality of task relation tables, and
the task set includes the at least one key task and tasks in which a state transition to an edge corresponding to the at least one key task is to be performed in the Markov chain.
3 . The electronic device of claim 2 , wherein at least one of the tasks in the task set has a probability that is higher than or equal to a reference probability of the tasks in which the state transition to the edge corresponding to the at least one key task is to be performed.
4 . The electronic device of claim 2 , wherein at least one of the tasks in the task set has a maximum occurrence count among the tasks in which the state transition to the edge corresponding to the at least one key task is to be performed, with reference to occurrence counts in the plurality of task relation tables.
5 . The electronic device of claim 2 , wherein the subset of tasks comprise a key task corresponding to a final edge in which a state transition is lastly performed and a task corresponding to an edge in which a state transition to the final edge is performed, and wherein a first task is scheduled prior to the key task.
6 . The electronic device of claim 1 , wherein:
at least one key task among the plurality of tasks is based on attributes of the plurality of tasks,
a valid entry of at least one of the first number of entries and the second number of entries has a ratio that is higher than or equal to a reference ratio and an occurrence count that is greater than or equal to a reference count in each task relation table,
the reference ratio is a ratio of at least one occurrence count to a total occurrence count in each of the plurality of task relation tables, and
the task set is based on the valid entry and the at least one key task.
7 . The electronic device of claim 6 , wherein:
the task set is based on the at least one key task and tasks in which a state transition to the edge corresponding to the at least one key task is to be performed in a Markov chain, and
the Markov chain is based on the valid entry and the at least one key task.
8 . The electronic device of claim 1 , wherein an initialized occurrence count of each entry is included in the plurality of task relation tables.
9 . The electronic device of claim 1 , wherein a divided occurrence count of each entry is included in the plurality of task relation tables based on a division value.
10 . The electronic device of claim 1 , wherein an adjusted occurrence count of each entry is included in the plurality of task relation tables based on an integer that is less than the occurrence count.
11 . The electronic device of claim 1 , further comprising a dynamic voltage frequency scaling (DVFS) adjuster configured to adjust a level of a DVFS including adjusting supply power and a frequency of a clock signal of a corresponding processing core based on a scheduling state of the task set.
12 . A method comprising:
storing a subset of tasks in at least one task queue of a plurality of task queues respectively corresponding to a plurality of processing cores; and
storing at least one updated task relation table of a plurality of updated task relation tables in a memory when a first processing core of the plurality of processing cores executes a first waker task waking up a first wakee task, wherein:
the stored subset of tasks comprises at least one key task of a plurality of tasks and at least one interactive task of a plurality of interactive tasks,
the at least one key task is based on attributes of the plurality of tasks,
the plurality of interactive tasks interacts with the at least one key task in a Markov chain representing a probability that a state transition between edges corresponding to the plurality of tasks is performed based on a plurality of task relation tables respectively corresponding to the plurality of tasks,
each of the plurality of task relation tables comprises a first number of entries representing a mapping relationship between an identifier of a waker task that wakes up a wakee task, and an occurrence count that is a number of times the wakee task is woken up by the waker task,
each of the plurality of updated task relation tables includes a second number of entries less than the first number of entries,
each of the second number of entries corresponds to an occurrence count that is not less than a reference count,
the occurrence count of each entry included in the plurality of updated task relation tables is less than an initial occurrence count in response to an update event, and
the occurrence count in a first updated task relation table among the plurality of updated task relation tables corresponding to the first wakee task is greater than the occurrence count in the other updated task relation tables.
13 . The method of claim 12 , wherein the Markov chain is further based on:
a ratio of at least one occurrence count to a total occurrence count in each of the plurality of task relation tables;
a valid entry in each task relation table, wherein the valid entry has a ratio that is higher than or equal to a reference ratio and an occurrence count that is greater than or equal to a reference count; and
the at least one key task, wherein the Markov chain further represents a probability that a state transition between edges respectively corresponding to a wakee task, a waker task, and the at least one key task is performed.
14 . The method of claim 12 , wherein the at least one key task in the Markov chain has a probability that is higher than or equal to a reference probability.
15 . The method of claim 12 , wherein the at least one key task having has a maximum occurrence count in the Markov chain with reference to occurrence counts in the plurality of task relation tables based on the plurality of interactive tasks interacting with the at least one key task in the Markov chain.
16 . The method of claim 12 , further comprising adjusting a level of dynamic voltage frequency scaling (DVFS) including adjusting supply power and a frequency of a clock signal of a corresponding processing core based on a scheduling state of the subset of tasks.
17 . A non-transitory computer-readable storage medium storing instructions executed by at least one of a plurality of processing cores classified into at least two core groups based on performance, the instructions comprising:
storing a subset of tasks in at least one task queue of a plurality of task queues respectively corresponding to a core group of the at least two core groups; and
storing at least one updated task relation table of a plurality of updated task relation tables in a memory when a first processing core of the plurality of processing cores executes a first waker task waking up a first wakee task, wherein:
the stored subset of tasks comprises at least one key task of a plurality of tasks and at least one interactive task of a plurality of interactive tasks,
the at least one task queue has performance that is higher than or equal to a reference performance,
the at least one key task is based on attributes of the plurality of tasks,
the plurality of interactive tasks interacts with the at least one key task in a Markov chain representing a probability that a state transition between edges corresponding to the plurality of tasks is performed based on a plurality of task relation tables respectively corresponding to the plurality of tasks,
each of the plurality of task relation tables comprises a first number of entries representing a mapping relationship between an identifier of a waker task that wakes up a wakee task, and an occurrence count that is a number of times the wakee task is woken up by the waker task
each of the plurality of updated task relation tables includes a second number of entries less than the first number of entries,
each of the second number of entries corresponds to an occurrence count that is not less than a reference count,
the occurrence count of each entry included in the plurality of updated task relation tables is less than an initial occurrence count in response to an update event, and
the occurrence count in a first updated task relation table among the plurality of updated task relation tables corresponding to the first wakee task is greater than the occurrence count in the other updated task relation tables.
18 . The non-transitory computer-readable storage medium of claim 17 , wherein the Markov chain is further based on:
a ratio of at least one occurrence count to a total occurrence count in each of the plurality of task relation tables;
a valid entry in each task relation table, wherein the valid entry has a ratio that is higher than or equal to a reference ratio and an occurrence count that is greater than or equal to a reference count; and
the at least one key task, wherein the Markov chain further represents a probability that a state transition between edges respectively corresponding to a wakee task, a waker task, and the at least one key task is performed.
19 . The non-transitory computer-readable storage medium of claim 17 , wherein the at least one key task in the Markov chain has a probability which is higher than or equal to a reference probability in the Markov chain based on the plurality of interactive tasks interacting with the at least one key task in the Markov chain.
20 . The non-transitory computer-readable storage medium of claim 17 , wherein the at least one key task is based on a significance of each of the plurality of tasks.