Stack resource policy

(Redirected from Stack Resource Policy)

The Stack Resource Policy (SRP) is a resource allocation policy used in real-time computing, used for accessing shared resources when using earliest deadline first scheduling. It was defined by T. P. Baker.[1] SRP is not the same as the Priority ceiling protocol which is for fixed priority tasks (FP).

Function

edit

Each task is assigned a preemption level based upon the following formula where   denotes the deadline of task   and   denotes the preemption level of task i:

 

Each resource R has a current ceiling   that represents the maximum of the preemption levels of the tasks that may be blocked, when there are   units of   available and   is the maximum units of   that   may require at any one time.   is assigned as follows:

 

There is also a system ceiling   which is the maximum of all current ceilings of the resources.

 

Any task   that wishes to preempt the system must first satisfy the following constraint:

 

This can be refined for Operating System implementation (as in MarteOS) by removing the multi-unit resources and defining the stack resource policy as follows

  • All tasks are assigned a preemption level, in order to preserve the ordering of tasks in relation to each other when locking resources. The lowest relative deadline tasks are assigned the highest preemption level.
  • Each shared resource has an associated ceiling level, which is the maximum preemption level of all the tasks that access this protected object.
  • The system ceiling, at any instant in time, is the maximum active priority of all the tasks that are currently executing within the system.
  • A task is only allowed to preempt the system when its absolute deadline is less than the currently executing task and its preemption level is higher than the current system ceiling.

Relevancy

edit

The 2011 book Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications by Giorgio C. Buttazzo featured a dedicated section to reviewing SRP from Baker 1991 work.[2][3]

References

edit
  1. ^ Baker, T. P. (1990). "A Stack-Based Resource Allocation Policy for Realtime Processes". IEEE Real-Time Systems Symposium: 191–200.
  2. ^ Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Giorgio C. Buttazzo, 2011
  3. ^ T.P. Baker, "Stack-Based Scheduling of Realtime Processes", The Real-Time Systems Journal 3,1 (March 1991)67-100