Stack Resource Policy

Short description: Resource allocation policy used in real-time computing

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 [math]\displaystyle{ D(T_i) }[/math] denotes the deadline of task [math]\displaystyle{ i }[/math] and [math]\displaystyle{ \pi_i(T_i) }[/math] denotes the preemption level of task i:

[math]\displaystyle{ D(T_i) \lt D(T_j) \iff \pi_i(T_i) \gt \pi_i(T_j) }[/math]

Each resource R has a current ceiling [math]\displaystyle{ C_R(V_R) }[/math] that represents the maximum of the preemption levels of the tasks that may be blocked, when there are [math]\displaystyle{ V }[/math] units of [math]\displaystyle{ R }[/math] available and [math]\displaystyle{ \mu_R(J) }[/math] is the maximum units of [math]\displaystyle{ R }[/math] that [math]\displaystyle{ T_i }[/math] may require at any one time. [math]\displaystyle{ C_R(V_R) }[/math] is assigned as follows:

[math]\displaystyle{ C_R(V_R) = max(\\{0\\} \cup \\{\pi(J) | V_R \lt \mu_R(J)\\}) }[/math]

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

[math]\displaystyle{ \pi' = max(\\{C_R(i) | i = 1,...,m\\} \cup \\{\pi(J_c)\\}) }[/math]

Any task [math]\displaystyle{ T_i }[/math] that wishes to preempt the system must first satisfy the following constraint:

[math]\displaystyle{ \pi' \lt P_i(T_i) }[/math]

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

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Stack_Resource_Policy&oldid=2637702"