Method and system for resolving dependency among the enqueued works and/or finished works and scheduling the dependency-resolved works

A scheduling apparatus to allocate works from applications to cores so that the applications share the cores, comprising:

• a processor;
• a runnable queue, using the processor, configured to enqueue therein the works in order of execution in consideration of any dependency therebetween;
• a finish queue, using the processor, configured to enqueue therein finished works whose execution is complete;
• one or more dependency queues, using the processor, configured to temporarily enqueue the plurality of works therein until the works are enqueued into the runnable queue, wherein each application corresponds to a separate dependency queue;
• an I/O (input/output) port configured to transmit the works in the runnable queue to the cores and receive the finished works from the cores;
• and
• a scheduler configured to search the dependency queues for one or more runnable works with no dependency and enqueue the one or more runnable works with no dependency into the runnable queue, to transmit the one or more works in the runnable queue to the cores via the I/O port so that the transmitted one or more works can be executed by any idle one of the cores, and to receive the finished works from the cores via the I/O port and enqueue the received finished works in the finish queue, wherein
• the scheduler is further configured to perform dependency resolving on the works in the dependency queues in real time upon the receipt of the finished works from the cores or at regular intervals of time, and
• the scheduler is further configured to perform dependency resolving on one or more works in the dependency queues having dependency on any one of the finished works in the finish queue and to enqueue the dependency-resolved works into the runnable queue.

A scheduling method of allocating works provided by applications to cores so that the applications share the cores, the scheduling method comprising:

• searching the works for one or more runnable works with no dependency and enqueuing the runnable works;
• transmitting the runnable works to the cores so that the transmitted runnable works can be executed by any idle one of the cores;
• receiving one or more of the finished works from the cores and enqueuing the received finished works;
• and
• in response to there being one or more works in the dependency queues having dependency on the finished works, performing dependency resolving on the one or more works having dependency on the finished works and enqueuing the dependency-resolved works into the runnable queue, wherein the dependency resolving comprises performing dependency resolving on the works in the dependency queues in real time upon the receipt of the finished works from the cores or at regular intervals of time.

A scheduling method of allocating works from applications to cores using a scheduling apparatus, which includes a runnable queue configured to enqueue therein the works in order of execution in consideration of any dependency therebetween and a finish queue configured to enqueue therein finished works whose execution is complete, so that the applications share the cores, the scheduling method comprising:

• determining whether the runnable queue is empty;
• if there is one or more runnable works in the runnable queue, determining whether any one of the cores is idle;
• if one of the cores is idle, transmitting one of the runnable works in the runnable queue to the idle core;
• if the runnable queue is empty or if none of the cores are idle, determining whether the finish queue is empty;
• and
• if there is one or more finished works in the finish queue, performing dependency resolving on one or more works within a dependency queue having dependency on any one of the finished works in the finish queue, wherein
• the dependency resolving comprises performing dependency resolving on the works in the dependency queues in real time upon the receipt of the finished works from the cores or at regular intervals of time, and
• in response to there being one or more works in the dependency queues having dependency on the finished works, performing dependency resolving on the one or more works having dependency on the finished works and enqueuing the dependency-resolved works into the runnable queue.

A scheduling apparatus to allocate works to a plurality of processing cores so that the applications share the cores, comprising:

• a processor;
• a dependency queue, using the processor, configured to enqueue works of an application;
• a runnable queue, using the processor, configured to enqueue works transferred from the dependency queue;
• a finish queue, using the processor, configured to enqueue works that have been executed by the processing cores;
• and
• a scheduler, using the processor, configured to:
• transfer a work having no dependency on the execution completion of another work from the dependency queue to the runnable queue,
• transfer the work from the runnable queue to an idle one of the processing cores for execution,
• transfer the work executed by the one processing core to the finish queue, where the work is designated a finished work,
• transfer a work within the dependency queue, having a dependency upon the finished work, to the runnable queue;
• and
• perform dependency resolving on the works in the dependency queues in real time upon the receipt of the finished works from the cores or at regular intervals of time.

A scheduling method that allocates a plurality of works to a plurality of processing cores so that the applications share the cores, the method comprising:

• transferring a work having no dependency on the execution completion of another work from a dependency queue to a runnable queue;
• transferring the work from the runnable queue to an idle one of the processing cores for execution;
• transferring the work executed by the one processing core to a finish queue, where the work becomes designated a finished work;
• transferring a work within the dependency queue, having a dependency upon the execution completion of the finished work, to the runnable queue;
• and
• performing dependency resolving on the works in the dependency queues in real time upon the receipt of the finished works from the cores or at regular intervals of time.