Priority Inheritance and Priority Ceiling Protocols

Priority Inheritance and
Priority Ceiling Protocols
L. Sha, R. Rajkumar, and J. P. Lehoczky,

"Priority Inheritance Protocols: An
Approach to Real-Time Synchronization",
IEEE Transactions on Computers, Vol. 39,
No. 9, Sept. 1990.
Priority Inversion
 A high priority task is blocked due to a low

priority task
 How can it happen?
 Mutex for shared resource access
 Non-preemptive subsystem access
 Network
 System bus
 Secondary storage
Mutual Exclusion via Semaphores
 Ensure only one task/process is in the critical section
 wait(S) to get access to semaphore S
 signal(S) to release S
 Example: producer consumer

Producer()
{
.
.
wait(S)
critical section /* create data & increment pointer */
signal(S)
.
.
}
Priority Inversion
Source of the figure: Chenyang Lu, Washington University Saint Louis

Unbounded Priority Inversion
What really happened on Mars?
 Repeatedresets in the Mars

Pathfinder
 The Mars Pathfinder mission was widely proclaimed as
"flawless" in the early days after its July 4th, 1997 landing
on the Martian surface.... But a few days into the mission,
not long after Pathfinder started gathering meteorological
data, the spacecraft began experiencing total system
resets, each resulting in losses of data. The press
reported these failures in terms such as "software
glitches" and "the computer was trying to do too many
things at once"....
 For a full story, visit
http://research.microsoft.com/%7Embj/Mars_Pathfinder/Mars_
Pathfinder.html
Pathfinder Incident
 Classical priority
inversion problem
due to shared
system bus!
Source of the figure: Damir Isovic, Malardaren University, Sweden

Priority Inheritance
 Inherit the priority of the blocked high priority

task
Priority Inheritance Protocol (PIP)
 If TL blocks a higher proirity task TH,

priority(TL) ← priority(TH)
 When TL releases a semaphore:
 Return to its normal priority if it doesn’t block any
task
 Otherwise, set priority(PL) ← highest priority of the
tasks blocking on a semaphore held by TL
 Transitive
 T1 blocked by T2: priority(T2) ← priority(T1)
 T2 blocked by T3: priority(T3) ← priority(T1)
Chained Blocking: Problem of PIP
In the worst case, the highest priority task T1 can be blocked by N lower
priority tasks in the system when T1 has to access N semaphores to finish
the execution!

Response Time Analysis of RMS with PIP
 For RMS schedulability test, ensure that:

 ∑ i=1, N (Ci/Ti + Bi/Ti) ≤ n(21/n - 1) , 1 ≤ i ≤ n
 Bi is the the longest priority inversion time
that could be experienced by Ti
 Bi= CSi + CSi+1+ ...+ CSk where CSi, CSi+1, ...,
CSk are the critical sections by which lower
priority tasks could block Ti
 Sufficient but not necessary because the
priority due to contention for CS may not
happen in reality
Priority Ceiling Protocol (PCP)
 Avoid chained blocking

 Guarantee a task is blocked by at most one lower
priority task
 No deadlock
 Assumptions
 Each task is associated with a fixed priority
PCP
 Each semaphore has the fixed priority ceiling

 ceiling(S) = highest priority among all the tasks
that will request S
 How it works:
 Ti can access a semaphore S if
 S is not already allocated to any other task; and
 Priority of Ti is higher than the current processor
ceiling = max(priority ceilings of all the semaphores
allocated to tasks other than Ti)
PCP
Ceiling(S1) = 1 (high)
Ceiling(S2) = 2 (medium)
Ceiling(S3) = 2 (medium)
No chained blocking!

Schedulability of RMS with PCP
 Consider blocking time:
 ∑ i=1, N (Ci/Ti + Bi/Ti) ≤ n(21/n - 1) , 1 ≤ i ≤ n
 Bi = max(CSi, CSi+1, ..., CSk) where CSi, CSi+1, ..., CSk are
the critical sections that can block Ti
Scheduling Aperiodic +
Periodic Tasks
Task Arrival Patterns
 Periodic
 Sporadic
 Aperiodic but minimum interarrival time is known
 Worst case
 Every sporadic job always arrives at its minimum
interarrival time
 Treat as periodic tasks
 Utilization bound or response time analysis
 If schedulable for the worst case, schedulable for all the
other cases
 Aperiodic
 No limitations on interarrival times
 Scheduling algorithms we have seen so far do not apply
Aperiodic Deadlines
 Soft: Not much to do in terms of scheduling

 Firm
 Deadline & WCET are given
 Start a firm deadline task only if it will finish by the
deadline
 Let’s discuss several hybrid scheduling
algorithms that use RMS for periodic task
scheduling
 Several approaches to scheduling aperiodic tasks
Background Scheduling
 Schedule periodic tasks first

 Schedule aperiodic tasks only if there’s no
periodic task
Periodic tasks RMS
High priority queue

CPU
Aperiodic tasks
FCFS, EDF, etc.

Low priority queue
Background Scheduling with RMS
 Task set: T1(2, 6), T2(4,10) where Ti=(Ci, Pi)

 Schedulable since 2/6 + 4/10 = 0.73 < 2(21/2-
1) = 0.82
T1 T1,1 T1,2
Schedule
2 4 6 Idle aperiodic
tasks here
T2 T2,1
2 4 6 8 10
Polling Server
 Use a periodic task to serve aperiodic tasks

 Period: Ps
 Capacity: Cs
 Algorithm
 Release the server at every period Ps
 Serve any pending aperiodic task
 Suspend itself, i.e., capacity = 0, if
 It consumed Cs; or
 There no pending aperiodic request
 Replenish capacity, i.e., capacity = Cs, at the next period

Schedulability of Polling Server
 Aperiodic tasks have no impact on periodic

ones
 There can be multiple servers
 n periodic tasks & m polling servers are
schedulable if Up + Us ≤ U(m+n)
 Problem: If an aperiodic request arrives right
after the server period, it has to wait until the
next period → Long response time
 Response time of an aperiodic request with execution
time Ca is Ps + Ca/Cs Ps
Deferrable Server (DS)
 Preserve the unused capacity until the end

of the current period
 Reduce response time to aperiodic requests
 DS affects the schedulability of periodic
tasks
 DS schedulability ≠ RM
Priority Exchange Server
 Server has the highest priority at the

beginning
 If there’s no aperiodic request to serve
right now, preserve capacity for lower
priority task’s execution time
 Replenish the capacity at the next period
Optimal?
 No optimal algorithm exists to minimize the

response time!
 Other servers with RMS
 Sporadic server: Replinish capacity only after
aperiodic request execution
 Slack stealing: No periodic server, but slack
stealer tries to steal time from periodic tasks

Priority Inheritance and Priority Ceiling Protocols

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Priority Inheritance and Priority Ceiling Protocols

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Priority Inheritance and Priority Ceiling Protocols

Uploaded by

Copyright:

Available Formats

Priority Inheritance and

Priority Ceiling Protocols

L. Sha, R. Rajkumar, and J. P. Lehoczky,

 A high priority task is blocked due to a low

 Example: producer consumer

Source of the figure: Chenyang Lu, Washington University Saint Louis

 Repeatedresets in the Mars

Source of the figure: Damir Isovic, Malardaren University, Sweden

 Inherit the priority of the blocked high priority

 If TL blocks a higher proirity task TH,

Source of the figure: Damir Isovic, Malardaren University, Sweden

 For RMS schedulability test, ensure that:

 Avoid chained blocking

 Each semaphore has the fixed priority ceiling

Source of the figure: Damir Isovic, Malardaren University, Sweden

 Consider blocking time:

 ∑ i=1, N (Ci/Ti + Bi/Ti) ≤ n(21/n - 1) , 1 ≤ i ≤ n

 Soft: Not much to do in terms of scheduling

 Schedule periodic tasks first

High priority queue

FCFS, EDF, etc.

 Task set: T1(2, 6), T2(4,10) where Ti=(Ci, Pi)

 Use a periodic task to serve aperiodic tasks

 There no pending aperiodic request

 Replenish capacity, i.e., capacity = Cs, at the next period

 Aperiodic tasks have no impact on periodic

 Preserve the unused capacity until the end

 Server has the highest priority at the

 No optimal algorithm exists to minimize the

You might also like