Documentation/locking/rt-mutex-design.rst

Source file repositories/reference/linux-study-clean/Documentation/locking/rt-mutex-design.rst

File Facts

System
Linux kernel
Corpus path
Documentation/locking/rt-mutex-design.rst
Extension
.rst
Size
22102 bytes
Lines
575
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

==============================
RT-mutex implementation design
==============================

Copyright (c) 2006 Steven Rostedt

Licensed under the GNU Free Documentation License, Version 1.2


This document tries to describe the design of the rtmutex.c implementation.
It doesn't describe the reasons why rtmutex.c exists. For that please see
Documentation/locking/rt-mutex.rst.  Although this document does explain problems
that happen without this code, but that is in the concept to understand
what the code actually is doing.

The goal of this document is to help others understand the priority
inheritance (PI) algorithm that is used, as well as reasons for the
decisions that were made to implement PI in the manner that was done.


Unbounded Priority Inversion
----------------------------

Priority inversion is when a lower priority process executes while a higher
priority process wants to run.  This happens for several reasons, and
most of the time it can't be helped.  Anytime a high priority process wants
to use a resource that a lower priority process has (a mutex for example),
the high priority process must wait until the lower priority process is done
with the resource.  This is a priority inversion.  What we want to prevent
is something called unbounded priority inversion.  That is when the high
priority process is prevented from running by a lower priority process for
an undetermined amount of time.

The classic example of unbounded priority inversion is where you have three
processes, let's call them processes A, B, and C, where A is the highest
priority process, C is the lowest, and B is in between. A tries to grab a lock
that C owns and must wait and lets C run to release the lock. But in the
meantime, B executes, and since B is of a higher priority than C, it preempts C,
but by doing so, it is in fact preempting A which is a higher priority process.
Now there's no way of knowing how long A will be sleeping waiting for C
to release the lock, because for all we know, B is a CPU hog and will
never give C a chance to release the lock.  This is called unbounded priority
inversion.

Here's a little ASCII art to show the problem::

     grab lock L1 (owned by C)
       |
  A ---+
          C preempted by B
            |
  C    +----+

  B         +-------->
                  B now keeps A from running.


Priority Inheritance (PI)
-------------------------

There are several ways to solve this issue, but other ways are out of scope
for this document.  Here we only discuss PI.

PI is where a process inherits the priority of another process if the other
process blocks on a lock owned by the current process.  To make this easier
to understand, let's use the previous example, with processes A, B, and C again.

This time, when A blocks on the lock owned by C, C would inherit the priority
of A.  So now if B becomes runnable, it would not preempt C, since C now has
the high priority of A.  As soon as C releases the lock, it loses its

Annotation

Implementation Notes