Preemptive multi-tasking with cooperative groups of tasks
AssigneeMicrosoft Corporation
InventorDavid D'Souza
Life of this patent
Estimating the term…
Abstract
An operating system combines preemptive scheduling with cooperative or non-preemptive scheduling. In particular, tasks are divided into groups of interdependent tasks. Each group includes tasks that should not be run a synchronously relative to each other. The scheduler in the operating system provides each group with a time slot of processor time. The tasks within the group are cooperatively scheduled to exploit the time slot assigned to the group. Dependencies between modules and tasks are maintained to assure that no difficulties arise amongst preemptively scheduled groups.
Claims14
In a data processing system having at least one processor for running tasks, wherein running each task involves running at least one module of code, said processor running an operating systems, a method performed by the operating system comprising the steps of:
- logically partitioning tasks into groups of interdependent tasks, the interdependency of two tasks being based on whether the two tasks call a common module of code;
- preemptively scheduling the groups of interdependent tasks to be run such that each group of interdependent tasks is allocated a time slot in a cycle in which its tasks may run on the processor;
- for each group, non-preemptively scheduling the tasks in the group to be run during the time slot allocated to the group;
- dynamically updating the partitioning of tasks into groups of interdependent tasks to reflect a change in the interdependency of the tasks in the groups;
- updating the preemptive scheduling of groups;
- and
- updating the cooperative scheduling of tasks within each group.
In a data processing system having at least one storage device for storing modules of code and at least one processor for running tasks wherein running each task involves running at least one module of code, a method comprising the steps of:
- providing a task dependency list for each task, said task dependency list listing modules that are called when the task is run on the processor;
- dynamically updating the task dependency list based on a change in which modules are called by the task associated with the task dependency list;
- during execution of the tasks, dynamically partitioning the tasks into groups of interdependent tasks based on the task dependency list for each task, the partitioning being based on dependencies between one module of code called by one task and another module of code called by another task;
- preemptively scheduling the groups of tasks to be run such that each group of tasks is given a time slot in a cycle in which its tasks may run on the processor;
- and
- for each group of tasks, non-preemptively scheduling tasks to be run within each group during the time slot allocated to the group.
In a data processing system having at least one storage device for storing modules of code and at least one processor for running tasks, wherein running each task involves running at least one module of code, a method comprising the steps of:
- providing a module dependency list for each associated module of code, wherein each module dependency list lists interdependent modules of code of the associated module of code;
- generating a task dependency list for each task by taking a logical union of modules listed in the module dependency lists of modules that are loaded or exported when the task is run on the processor;
- examining the task dependency lists to logically partition the tasks into groups of interdependent tasks;
- and
- preemptively scheduling the groups of tasks to be run such that each group of tasks is given a time slot in a cycle in which its tasks may run on the processor;
- and
- for each group of tasks, non-preemptively scheduling tasks to be run within each group during the time slot allocated to the group.
In a data processing system having at least one processor for running tasks, wherein running each task involves running at least one module of code, wherein said processor runs an operating system, a computer-readable storage medium holding the operating system, said operating system performing the steps of:
- logically partitioning tasks into groups of interdependent tasks based on modules of code called by the tasks;
- preemptively scheduling the groups of interdependent tasks to be run such that each group of interdependent tasks is given a time slot in a cycle in which its tasks may run on the processor;
- for each group, non-preemptively scheduling tasks to be run within each group during the time slot allocated to the group;
- dynamically updating the partitioning of tasks into groups of interdependent tasks to reflect changes in the modules of code called by the tasks;
- updating the preemptive scheduling of groups;
- and
- updating the non-preemptive scheduling of tasks within each group.
In a data processing system having at least one storage device for storing modules of code and at least one processor for running tasks wherein running each task involves running at least one module of code, a computer-readable storage medium holding an operating system for performing the steps of:
- providing a task dependency list for each task, said task dependency list listing modules that are loaded or exported when the task is run on the processor;
- dynamically updating and examining the task dependent lists;
- during execution of the tasks, dynamically partitioning the tasks into groups of interdependent tasks based on the examination of the task dependent list;
- preemptively scheduling the groups of tasks to be run such that each group of tasks is given a time slot in a cycle in which its tasks may run on the processor;
- and
- for each group of tasks, non-preemptively scheduling tasks to be run within each group during the time slot allocated to the group.
In a data processing system having at least one storage device for storing modules of code and at least one processor for running tasks wherein running each task involves running at least one module of code, a computer-readable storage medium holding an operating system for performing the steps of:
- providing a module dependency list for each associated module of code, wherein each module dependency list lists interdependent modules of code of the associated module of code;
- generating a task dependency list for each task by taking a logical union of modules listed in the module dependency lists of modules that are loaded or exported when the task is run on the processor;
- examining the task dependency lists;
- logically partitioning the tasks into groups of interdependent tasks based on the examination of the task dependency list;
- preemptively scheduling the groups of tasks to be run such that each group of tasks is given a time slot in a cycle in which its tasks may run on the processor;
- and
- for each group of tasks, non-preemptively scheduling tasks to be run within each group during the time slot allocated to the group.
Dependencies are inferred from the claim text.