Stack resource policy

<h2 id="function">Function</h2>
Each task is assigned a preemption level based upon the following formula where 
 
 
 
 D
 (
 
 T
 
 i
 
 
 )
 
 
 {\displaystyle D(T_{i})}
 
 denotes the deadline of task 
 
 
 
 i
 
 
 {\displaystyle i}
 
 and 
 
 
 
 
 π
 
 i
 
 
 (
 
 T
 
 i
 
 
 )
 
 
 {\displaystyle \pi _{i}(T_{i})}
 
 denotes the preemption level of task i:

 
 
 
 D
 (
 
 T
 
 i
 
 
 )
 <
 D
 (
 
 T
 
 j
 
 
 )
 
 ⟺
 
 
 π
 
 i
 
 
 (
 
 T
 
 i
 
 
 )
 >
 
 π
 
 i
 
 
 (
 
 T
 
 j
 
 
 )
 
 
 {\displaystyle D(T_{i})<D(T_{j})\iff \pi _{i}(T_{i})>\pi _{i}(T_{j})}

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

 
 
 
 
 C
 
 R
 
 
 (
 
 V
 
 R
 
 
 )
 =
 m
 a
 x
 (
 {
 0
 }
 ∪
 {
 π
 (
 J
 )
 
 |
 
 
 V
 
 R
 
 
 <
 
 μ
 
 R
 
 
 (
 J
 )
 }
 )
 
 
 {\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.

 
 
 
 
 π
 ′
 
 =
 m
 a
 x
 (
 {
 
 C
 
 R
 
 
 (
 i
 )
 
 |
 
 i
 =
 1
 ,
 .
 .
 .
 ,
 m
 }
 ∪
 {
 π
 (
 
 J
 
 c
 
 
 )
 }
 )
 
 
 {\displaystyle \pi '=max(\{C_{R}(i)|i=1,...,m\}\cup \{\pi (J_{c})\})}

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

 
 
 
 
 π
 ′
 
 <
 
 P
 
 i
 
 
 (
 
 T
 
 i
 
 
 )
 
 
 {\displaystyle \pi '<P_{i}(T_{i})}

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

<ul><li>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.</li>
<li>Each shared resource has an associated ceiling level, which is the maximum preemption level of all the tasks that access this protected object.</li>
<li>The system ceiling, at any instant in time, is the maximum active priority of all the tasks that are currently executing within the system.</li>
<li>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.</li></ul>
<h2 id="relevancy">Relevancy</h2>
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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Baker, T. P. (1990). "A Stack-Based Resource Allocation Policy for Realtime Processes". IEEE Real-Time Systems Symposium: 191–200. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Giorgio C. Buttazzo, 2011 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">T.P. Baker, "Stack-Based Scheduling of Realtime Processes", The Real-Time Systems Journal 3,1 (March 1991)67-100 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Stack resource policy open-in-new

Stack resource policy