Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F9/00—Arrangements for program control, e.g. control units
  • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
  • G06F9/46—Multiprogramming arrangements
  • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
  • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
  • G06F9/5011—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals
  • G06F9/5016—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals the resource being the memory
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F9/00—Arrangements for program control, e.g. control units
  • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
  • G06F9/46—Multiprogramming arrangements
  • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]

Definitions

• the present invention relates to methods and systems for reducing memory and processor usage, with particular reference to stack operations, in real-time computing applications.
• the invention is particularly, though not exclusively, directed towards operating systems that make use of static priority-based scheduling but that also permit tasks explicitly to suspend themselves and/or wait for predetermined events.
• Embodiments of the present invention are of particular relevance to the technical field of embedded devices and the control thereof, since these generally use static priority-based scheduling given the limited range of functions required.
• Certain groups of tasks may advantageously be placed into "non-preemption groups" such that their priorities are allocated in such a fashion that when any one of the tasks in a non-preemption group is executing, no other task in that group may preemptively gain control of the central processing unit (CPU) (see Figure 2).
• CPU central processing unit
• Such operating systems may be extended to permit tasks voluntarily to suspend or yield control of the CPU by way of a well-defined application programmer interface (API).
• API application programmer interface
• a task may wait for an event to occur and register an interest in being awakened when that event occurs, or may voluntarily suspend its computations in order co-operatively to permit other tasks to use the CPU.
• Examples of such systems include, but are not limited to, OSEK extended conformance classes ECC1 or ECC2 (see http://www.osek-vdx.org).
• Embodiments of the present invention seek to provide a means of allocating stack usage on a single stack for such mixed preemptive/cooperating systems.
• Embodiments of the present invention seek to provide a means of ensuring that an entire mixed preemptive/cooperating system can run on a single stack, thus saving RAM and reducing context switch overhead, particularly for pre-emptive tasks, as no switching between stacks is required.
• each task is annotated with its worst-case stack usage figures. In the simplest case, this could be a single number for each task; more advanced variants of this approach can take account of shared priorities,, non- preemption between tasks, or transient stack usage (for example during semaphore or interrupt locks), among others.
• off-line analysis of the tasks and their stack usage can be used to determine the worst case stack-usage of all tasks that can run at lower priority than any task that can voluntarily yield control of the CPU.
• Such a task can then be started with its initial stack pointer set to this value and it can be sure that it is not overwriting the stack area of any lower priority task.
• the amount of stack used from the start point to the yield point can be saved into a separate statically allocated area from where it can later be restored when the task regains control.
• a method of reducing memory and processor usage in a computer operating system utilising a processor, a memory and a single stack, the operating system comprising a plurality of tasks divided into predetermined priority categories, including preemptive tasks and at least one task that voluntarily yields control of the processor to tasks of lower priority than itself in predetermined circumstances, wherein each task has associated therewith a stack pointer, and wherein the at least one task, when started, has its stack pointer set to a precalculated worst-case value guaranteed to leave sufficient space in the stack beneath the stack pointer for any preemptive tasks of lower priority, and wherein the at least one task has allocated to it an area of memory into which its stack contents is saved, a size of the area of memory being determined by a declared precalculated worst-case stack usage of the at least one task at any point at which the at least one task may yield control of the processor.
• a configuration tool for reducing memory and processor usage in a computer operating system utilising a processor, a memory and a single stack, the operating system comprising a plurality of tasks divided into predetermined priority categories, including preemptive tasks and at least one task that voluntarily yields control of the processor to tasks of lower priority than itself in predetermined circumstances, wherein each task has associated therewith a stack pointer, and wherein the tool is adapted to calculate a worst-case stack pointer value for the at least one task guaranteed to leave sufficient space in the stack beneath the stack pointer for any preemptive tasks of lower priority than the at least one task, and wherein the tool is adapted to allocate to the at least one task an area of memory into which the stack contents of the at least one task is saved, a size of the area of memory being determined by a declared worst-case stack usage, calculated by the tool, of the at least one task at any point at which the at least one task may yield control of the processor.
• a computing device programmed with a configuration tool for reducing memory and processor usage in a computer operating system utilising a processor, a memory and a single stack, the operating system comprising a plurality of tasks divided into predetermined priority categories, including preemptive tasks and at least one task that voluntarily yields control of the processor to tasks of lower priority than itself in predetermined circumstances, wherein each task has associated therewith a stack pointer, and wherein the tool is adapted to calculate a worst-case stack pointer value for the at least one task guaranteed to leave sufficient space in the stack beneath the stack pointer for any preemptive tasks of lower priority than the at least one task, and wherein the tool is adapted to allocate to the at least one task an area of memory into which the stack contents of the at least one task is saved, a size of the area of memory being determined by a declared worst-case stack usage, calculated by the tool, of the at least one task at any point at which the at least one task may yield control of the processor.
• the configuration tool may be in the form of a software product.
• the software product may be in any appropriate form or language, and may be stored on a data carrier such as a floppy disk, optical disk, flash memory device or any other type of data carrier.
• a computer operating system utilising a processor, a memory and a single stack, the operating system comprising a plurality of tasks divided into predetermined priority categories, including preemptive tasks and at least one task that voluntarily yields control of the processor to tasks of lower priority than itself in predetermined circumstances, wherein each task has associated therewith a stack pointer, and wherein the at least one task, when started, has its stack pointer set to a precalculated worst-case value guaranteed to leave sufficient space in the stack beneath the stack pointer for any preemptive tasks of lower priority, and wherein the at least one task has allocated to it an area of memory into which its stack contents is saved, a size of the area of memory being determined by a declared precalculated worst-case stack usage of the at least one task at any point at which the at least one task may yield control of the processor.
• a computing device programmed with an operating system utilising a processor, a memory and a single stack, the operating system comprising a plurality of tasks divided into predetermined priority categories, including preemptive tasks and at least one task that voluntarily yields control of the processor to tasks of lower priority than itself in predetermined circumstances, wherein each task has associated therewith a stack pointer, and wherein the at least one task, when running, has its stack pointer set to a precalculated worst-case value guaranteed to leave sufficient space in the stack beneath the stack pointer for any preemptive tasks of lower priority, and wherein the at least one task has allocated to it an area of memory into which its stack contents is saved, a size of the area of memory being determined by a declared precalculated worst-case stack usage of the at least one task at any point at which the at least one task may yield control of the processor.
• any operating system functions that may cause a task voluntarily to yield control of the processor must be implemented in such a way that on detecting the need to yield they cause the current stack pointer and stack between the task's known base stack pointer and the current stack pointer value to be saved into this area, and on returning control to the task cause the stack to be restored from the "save area" and the stack pointer to be set to its previous value. It is also to be noted that when suspending a cooperative task and resuming a preemptive task, the stack pointer from the purely preemptive tasks running at lower priorities than the cooperative task must be restored.
• embodiments of the present invention find particular utility in the technical field of embedded devices and the control thereof, since these generally use static priority-based scheduling given the limited range of functions required.
• the various tasks and their characteristics can be predefined statically and off-line in embedded device applications, since these are generally predictable, closed systems rather than large systems requiring dynamic task definitions.
• the configuration process to calculate stack characteristics for the cooperative tasks can be carried out according to the following pseudo code, which is set forth by way of example only.
• the existence is assumed of a function to calculate the worst-case stack usage for a given set of tasks running up to a given priority level, since this is established technology.
• start_stac (t) orst_case_stack (preempt_set , priority (t) ) reserve_save_area (t , stack_on_suspend (t) ) else need_stack_adjustment (t , false) end if end for
• FIGURE 1 shows how, in a preemptive system with "single-shot” tasks, a single stack can be used:
• FIGURE 2 shows how, in such a system, information about non-preemption between tasks can be used to minimise the amount of stack needed
• FIGURE 3 shows how, for two tasks that voluntarily yield control of the processor (cooperative), each has its stack pointer uniquely determined
• FIGURE 4 shows how a task saves its stack area into its "save area”, other tasks running instead
• FIGURE 5 illustrates an embodiment of the invention in which two tasks that may yield control of the CPU exist in mutual exclusion.
• Figure 1 shows a conventional arrangement in which three single-shot tasks (Task 1, Task 2 and Task 3) are each provided with an independent stack 1, 2, 3.
• Each stack 1, 2, 3 must include enough memory to store its respective task and also to store any associated context when that task is preempted. It is possible to run all three tasks on a single stack 4 by reserving enough memory in the stack 4 for each task and its associated context to be stored one on top of the other.
• the stack 4 must reserve more RAM than will generally be required in real-life applications, because this scenario assumes a simple "worst case" scenario.
• Figure 2 shows an alternative conventional arrangement in which tasks are grouped into non-preemption groups each having a given priority. Specifically, there is a non- preemption group 5 of tasks having priority 1 ; a non-preemption group 6 of tasks having priority 2; and a non-preemption group 7 of tasks having priority 3. Because no task may preempt any other task within the same non-preemption group 5, 6 or 7, it is possible to run all of the tasks on a single stack 8 by reserving enough space for the largest task (and its associated context) in each non-preemption group 5, 6 and 7 in the stack 8 as shown.
• FIG. 3 illustrates an embodiment of the present invention where two tasks (T_ECC_1 and T_ECC_2) that voluntarily yield control of the processor (cooperative), may have their stack pointers uniquely determined.
• the calculated single stack is shown at 10, and is built up as follows. Firstly, the maximum usage of any tasks with priority lower than task T_ECC_1 is determined and space 11 is reserved therefor in the stack 10. Secondly, the stack usage for task T_ECC_1 is determined and space 12 reserved in the stack 10 on top of space 11. Thirdly, the worst-case usage of all tasks with priority lower than task T_ECC_2 is determined and space 13 is reserved therefor in the stack 10 on top of space 12.
• stack usage for task T_ECC_2 is determined and space 14 reserved in the stack 10 on top of space 13.
• stack usage for preemptive tasks running above task T_ECC_2 is calculated and space 15 reserved therefor on top of space 14. The calculations may be undertaken by the configuration tool of embodiments of the present invention.
• the stack may go over the bounds of the calculated stack pointer in space 13 to extend the stack to space 14 for another task that may voluntarily yield control of the processor, but only where the running task has higher priority than the task T_ECC_2 that may voluntarily yield control of the processor. In this case the tasks of higher priority than T_ECC_2 will run to completion and so the stack use returns to within space 13 before T_ECC_2 can run.
• the stack pointer is set to the bottom of precalculated stack space 14 and task T_ECC_2 may then run in space 14. Any further preemptive tasks that run over task T_ECC_2 will run in space 15 above space 14.
• Figure 4 shows a stack 20 with space 21 reserved for tasks running under a blocking ECC task, for which space 22 is reserved in the stack 20 above space 21.
• the ECC task When the ECC task is suspended, it is saved in a separate save area 23 so that higher priority preemptive tasks that run when the ECC task yields can extend their stack use from space 21 into space 22 because they will complete and subsequently release this space before the ECC task continues.
• the ECC task When the ECC task is restored, the contents of the save area 23 are replaced in the stack 20 in space 22.
• FIG. 5 illustrates an interesting application of an embodiment of the invention in which two tasks T_ECC_2 and T_ECC_3 that may yield control of the CPU exist in mutual exclusion.
• a stack 30 is shown in which space 31 is reserved at the bottom of the stack for the worst case stack usage of for all tasks running below tasks T_ECC_2 and T_ECC_3.
• a stack pointer for task T_ECC_2 is set at the top of space 31 and a maximum stack usage for task T_ECC_2 is defined as before to give space 32.
• space 33 for the worst case stack usage for all tasks that can preempt task T_ECC_2.
• Task T_ECC_3 is defined to be in mutual exclusion (mutex) with task T_ECC_2.
• tasks T_ECC_2 and T_ECC_3 are in mutual exclusion, they can share the same stack space 32.
• the maximum stack usage for task T_ECC_3 is less than that of task T_ECC_2, but it can be seen that the stack pointers for both of these tasks are the same.
• task T_ECC_2 yields control of the CPU, it must be saved (together with any context) in save area 34, because it may be replaced in the stack 30 in space 32 by task T_ECC_3, as shown in stack configuration 30'.
• task T_ECC_3 When task T_ECC_3 yields control of the CPU, it is saved (together with any context) in a separate save area 35, and task T_ECC_2 and its context can then be restored to the stack from the save area 34 when the task is resumed, as shown in stack configuration 30".

Landscapes

• Engineering & Computer Science (AREA)
• Software Systems (AREA)
• Theoretical Computer Science (AREA)
• Physics & Mathematics (AREA)
• General Engineering & Computer Science (AREA)
• General Physics & Mathematics (AREA)
• Memory System (AREA)
• Multi Processors (AREA)

Applications Claiming Priority (5)

Publications (1)

Family

ID=31979990

Family Applications (1)

Country Status (3)

Cited By (1)

Families Citing this family (1)

Family Cites Families (1)

• 2003
  • 2003-08-20 EP EP03791005A patent/EP1573538A2/de not_active Withdrawn
  • 2003-08-20 AU AU2003255827A patent/AU2003255827A1/en not_active Abandoned
  • 2003-08-20 WO PCT/GB2003/003640 patent/WO2004021187A2/en not_active Ceased

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events