Priority limit

The priority limit ( english priority ceiling protocol is) a method to solve the problem of priority inversion and avoid deadlocks . It is an extension of the priority inheritance , but in contrast to this it can exclude a deadlock.

Requirements for the application of the protocol

• Priority-driven preemptive scheduling with fixed priorities
• One processor system
• All resource requirements are known in advance

Protocol sequence

The priority limit of a system at a fixed point in time is determined by the maximum of the priority limits of all resources that are used at that point in time. The priority barrier of a resource corresponds to the maximum of the priorities of the processes that access this resource at all . Accordingly, the priority barrier of a system changes continuously. It switches between the priority barriers of the resources in the system and 0.

Allocation rule

If a process wants to use a resource, it is first checked whether it is available:

• if the resource has already been allocated, the request is refused and the process is blocked on this resource
• if the resource is available, the current priority limit of the system is checked:
  • if the process has a higher priority than the current priority limit, it is assigned the resource
  • if he does not have a higher priority, he only gets the resource if he already owns the resource that sets the current priority limit of the system. Otherwise he will be denied the resource.

Priority inheritance rule

If a process blocks a resource , the process that currently owns this resource inherits the (higher) priority of the requesting process. The process that already has the resource is now processed further under this priority until it has released all resources whose priority limit is greater than or equal to the inherited priority.

Example with semaphore

(smaller numbers mean higher priorities here)

3 semaphores:

• ${\displaystyle S_{1}}$
• ${\displaystyle S_{2}}$
• ${\displaystyle S_{3}}$

2 processes:

• ${\displaystyle T_{1}}$Priority 1 and uses the resources , ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$
• ${\displaystyle T_{2}}$with priority 2 and uses the resources , ${\displaystyle S_{2}}$ ${\displaystyle S_{3}}$

Priority limits of the semaphores:

• ${\displaystyle S_{1}}$: Priority 1 because of ${\displaystyle T_{1}}$
• ${\displaystyle S_{2}}$: Priority 1 because of ${\displaystyle T_{1}}$
• ${\displaystyle S_{3}}$: Priority 2 because of ${\displaystyle T_{2}}$

Procedure:

• ${\displaystyle T_{2}}$starts to work, he used immediately . This increases the priority limit of the system to the priority of the semaphore , i.e. 1. ${\displaystyle S_{2}}$ ${\displaystyle S_{2}}$
• ${\displaystyle T_{1}}$starts and displaces . ${\displaystyle T_{2}}$
• ${\displaystyle T_{1}}$now tries to prove. However, this fails initially because the priority limit of the system is 1 and the process does not have a higher priority. ${\displaystyle S_{1}}$ ${\displaystyle T_{1}}$
• ${\displaystyle T_{2}}$Now gets the priority of due to the priority inheritance . ${\displaystyle T_{1}}$
• ${\displaystyle T_{2}}$occupies now additionally . This is possible because a resource currently has the highest priority. ${\displaystyle S_{3}}$ ${\displaystyle T_{2}}$
• ${\displaystyle T_{2}}$releases and gets its starting priority again. ${\displaystyle S_{2}}$
• ${\displaystyle T_{1}}$can now prove. ${\displaystyle S_{1}}$

Modifications

OSEK Priority Ceiling Protocol

Also Immediate Priority Ceiling Protocol (English for immediate priority upper limit protocol ). With this protocol, the occupying thread immediately receives the priority of the priority limit of the resource.