Priority ceiling protocol

The priority limit (english priority ceiling protocol) is a method to resolve the problem of priority inversion, and the avoidance of deadlocks. It is an extension of the priority inheritance, but can this rule out a deadlock in contrast.

Conditions for the application of the Protocol

  • Priority -driven preemptive scheduling with fixed priorities
  • A processor system
  • All requests for resources are known in advance

Protocol sequence

The priority of a barrier system to a fixed point in time is determined by the maximum of the priority lists of all resources that are used at this time. The priority limit of a resource corresponding to the maximum of the priorities of processes that access at all to this resource. Accordingly, the priority limit of a system is constantly changing. She alternates between the priority barriers of resources in the system and 0

Allocation rule

Want a process use a resource, so it is first checked whether it is available:

  • The resource is already in use, so the request is denied and the process blocked on this resource
  • The resource is available, the current priority limit of the system is tested: the process has a higher priority than the current priority limit, it gets allocated the resource
  • He has no higher priority so it gets the resource only if he is already the resource that establishes the current priority limit of the system possesses. Otherwise, the resource will be denied.

Priority inheritance rule

Blocks a process to a resource inherits the process that owns this resource currently, the (higher ) priority of the requesting process. The process that the resource has already will now be further processed under this priority until it has cleared all the resources, the priority of which is greater than or equal to the barrier inherited priority.

Example with semaphore

(smaller numbers indicate higher priorities here )

3 semaphores:

Two processes:

  • Priority 1 and uses the resources,
  • Priority 2, and uses the resource,

Priority limits of semaphores:

  • : Priority 1 for
  • : Priority 1 for
  • : Priority 2 because

Procedure:

  • Begins to work, he used immediately. Thus, the priority limit of the system rises to the priority of the semaphore, ie 1
  • Starts and displaced.
  • Is now trying to prove. However, this fails first, because the priority of the system is bound in one and the process has no higher priority.
  • Now gets the priority of on the basis of priority inheritance.
  • Is now additionally. This is possible, because at the moment has an operating means having the highest priority.
  • Are free and gets back to its original priority.
  • Can now prove.

Modifications

OSEK Priority Ceiling Protocol

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

  • Operating system theory
661543
de