Resource Access Protocol

Mutual Exclusion: to reserve data consistency, shared resources must be accessed in mutual exclusion

Priority inversion: high priority task is blocked by low priority task for unbounded interval of time

Resource Access Protocol:

1. non preemptive protocol - NPP
2. highest locker priority - HLP
3. priority inheritance protocol - PIP
4. priority ceiling protocol - PCP

NPP

• Pcs = max{P1...Pn}
• when a task enters CS, its priority increased at the max value
• problem: high priority task that do not use the same cs can't preempt it

HLP

• Pcs = max{Pk | Tk usese CS}
• a task in a cs gets the highest priority among the tasks that use it
• problem: t1 have a condition test that may enter cs that uses by t2, t2 will get t1 priority when enter cs and block t1 even t1 may not be using the cs

PIP

• Pcs = max{Pk | Tk blocked on CS}
• a task in a CS increases its priority only if it blocks other tasks
• a task in a CS inherits the highest priority among those tasks it blocks
• Blocking : a delay caused by a lower priority task
• Direct blocking : a task blocks on a locked resource
• Push through blocking : a task blocks because a lower priority task inherited a higher priority
• Ti can be blocked at most once by each of such resources
• Ti can be blocked at most for the duration of min(n,m) critical sections
• advantage: transparent, bounds priority inversion
• problem: does not avoid deadlocks and chained blocking
• chain blocking: Ti can be blocked at most once by each lower priority task

PCP

• PIP+ access test
• a task can enter a CS only if its is free and there is no risk of chained blocking
• a task may stop at the entrance of a free CS
• C(rk) = max{pj:Tj uses rk}
• a task tj can enter a CS only if
• Pi > max{C(rk): rk locked by tasks != Ti}
• advantage: blocking reduced to one CS, prevent deadlocks
• problems: not transparent to programmer, resource need ceilings

source : lecture notes