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 D(Ti) denotes the deadline of task i and πi(Ti) denotes the preemption level of task i:

D(Ti)<D(Tj)⟺πi(Ti)>πi(Tj)

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

CR(VR)=max({0}∪{π(J)|VR<μR(J)})

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

π′=max({CR(i)|i=1,...,m}∪{π(Jc)})

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

π′<Pi(Ti)

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=243158"