Page 130 - DCAP103_Principle of operating system

Unit 4: Process Management-III

Notes
Figure 4.7: Priority Inheritance

H

M

L

A weakness of the priority inheritance protocol is that it does not prevent chained blocking.
Suppose a medium priority thread attempts to take a mutex owned by a low priority thread,
but while the low priority thread’s priority is elevated to medium by priority inheritance, a
high priority thread becomes runnable and attempts to take another mutex already owned by
the medium priority thread. The medium priority thread’s priority is increased to high, but the
high priority thread now must wait for both the low priority thread and the medium priority
thread to complete before it can run again.
The chain of blocking critical sections can extend to include the critical sections of any threads
that might access the same mutex. Not only does this make it much more difficult for the system
designer to compute overhead, but since the system designer must compute the worst case
overhead, the chained blocking phenomenon may result in a much less efficient system. These
blocking factors are added into the computation time for tasks in the RMA analysis, potentially
rendering the system unschedulable. This may force the designer to resort to a faster CPU or to
remove functionality from the system.

Differentiate between Priority inheritance and Priority inversion.

Figure 4.8: Chained Blocking caused by Priority Inheritance

Overhead

(S2) S2
H
rS2
(S1) rS1
M
S2
L
S1

A solution called the priority ceiling protocol not only solves the priority inversion problem but
also prevents chained blocking. In one implementation scheme (called the highest locker), each
semaphore has an associated priority, which is assigned by the system designer to be the priority
of the highest priority thread that might ever try to acquire that object. When a thread takes such
a semaphore, it is immediately elevated to the priority of the semaphore. When the semaphore
is released, the thread reverts back to its original priority. Because of this priority elevation,

LOVELY PROFESSIONAL UNIVERSITY 123