# 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

Each task is assigned a preemption level based upon the following formula where ${\displaystyle D(T_{i})}$ denotes the deadline of task ${\displaystyle i}$ and ${\displaystyle \pi _{i}(T_{i})}$ denotes the preemption level of task i:

${\displaystyle D(T_{i})\pi _{i}(T_{j})}$

Each resource R has a current ceiling ${\displaystyle C_{R}(V_{R})}$ that represents the maximum of the preemption levels of the tasks that may be blocked, when there are ${\displaystyle V}$ units of ${\displaystyle R}$ available and ${\displaystyle \mu _{R}(J)}$ is the maximum units of ${\displaystyle R}$ that ${\displaystyle T_{i}}$ may require at any one time. ${\displaystyle C_{R}(V_{R})}$ is assigned as follows:

${\displaystyle C_{R}(V_{R})=max(\{0\}\cup \{\pi (J)|V_{R}<\mu _{R}(J)\})}$

There is also a system ceiling ${\displaystyle \pi '}$ which is the maximum of all current ceilings of the resources.

${\displaystyle \pi '=max(\{C_{R}(i)|i=1,...,m\}\cup \{\pi (J_{c})\})}$

Any task ${\displaystyle T_{i}}$ that wishes to preempt the system must first satisfy the following constraint:

${\displaystyle \pi '

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

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

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