요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
Boost 전파와 제거
rt-mutex.rst:13-33Boost된 owner가 다시 다른 rt_mutex에서 막히면 그 두 번째 owner에게도 priority가 chain을 따라 전파됩니다. 각 lock이 해제되거나 top waiter가 빠지는 즉시 해당 inheritance를 다시 계산하고 불필요한 boost를 제거합니다.
PI는 잘못 설계된 긴 critical section을 고치지 않습니다. 하지만 bounded critical section을 가진 application에서 관계없는 medium-priority task가 owner 실행을 무기한 지연하는 문제를 막아 latency 결정성을 높입니다.
Priority와 FIFO로 정렬되는 두 tree
rt-mutex.rst:34-47각 rt_mutex waiter tree는 priority 순서로 정렬하고 같은 priority에서는 FIFO를 사용합니다. 그 mutex의 top waiter만 owner task의 pi_waiters tree에 들어갑니다. Owner가 여러 mutex를 보유해도 pi_waiters root 하나만 보면 상속할 가장 높은 priority를 찾을 수 있습니다.
owner pointer와 bit 0 상태표
rt-mutex.rst:48-78| owner pointer | bit 0 | 상태 |
|---|---|---|
| NULL | 0 | free, fast acquire 가능 |
| NULL | 1 | free지만 top waiter가 깨어나 획득 예정 또는 slowpath 전이 중 |
| task pointer | 0 | held, waiter 없음, fast release 가능 |
| task pointer | 1 | held, waiter 있음 |
Cmpxchg fast acquire와 release는 bit 0이 0일 때만 가능합니다. Slowpath가 wait_lock 아래에서 상태를 조사하기 전에 bit를 먼저 세워 다른 CPU의 fastpath가 owner를 바꾸지 못하게 합니다. Owner가 NULL이고 bit가 1인 짧은 전이 상태도 이 규칙 때문에 합법적입니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
==================================
RT-mutex subsystem with PI support
==================================
RT-mutexes with priority inheritance are used to support PI-futexes,
which enable pthread_mutex_t priority inheritance attributes
(PTHREAD_PRIO_INHERIT). [See Documentation/locking/pi-futex.rst for more details
about PI-futexes.]
This technology was developed in the -rt tree and streamlined for
pthread_mutex support.
Basic principles:
-----------------
RT-mutexes extend the semantics of simple mutexes by the priority
inheritance protocol.
A low priority owner of a rt-mutex inherits the priority of a higher
priority waiter until the rt-mutex is released. If the temporarily
boosted owner blocks on a rt-mutex itself it propagates the priority
boosting to the owner of the other rt_mutex it gets blocked on. The
priority boosting is immediately removed once the rt_mutex has been
unlocked.
This approach allows us to shorten the block of high-prio tasks on
mutexes which protect shared resources. Priority inheritance is not a
magic bullet for poorly designed applications, but it allows
well-designed applications to use userspace locks in critical parts of
an high priority thread, without losing determinism.
The enqueueing of the waiters into the rtmutex waiter tree is done in
priority order. For same priorities FIFO order is chosen. For each
rtmutex, only the top priority waiter is enqueued into the owner's
priority waiters tree. This tree too queues in priority order. Whenever
the top priority waiter of a task changes (for example it timed out or
got a signal), the priority of the owner task is readjusted. The
priority enqueueing is handled by "pi_waiters".
RT-mutexes are optimized for fastpath operations and have no internal
locking overhead when locking an uncontended mutex or unlocking a mutex
without waiters. The optimized fastpath operations require cmpxchg
support. [If that is not available then the rt-mutex internal spinlock
is used]
The state of the rt-mutex is tracked via the owner field of the rt-mutex
structure:
lock->owner holds the task_struct pointer of the owner. Bit 0 is used to
keep track of the "lock has waiters" state:
============ ======= ================================================
owner bit0 Notes
============ ======= ================================================
NULL 0 lock is free (fast acquire possible)
NULL 1 lock is free and has waiters and the top waiter
is going to take the lock [1]_
taskpointer 0 lock is held (fast release possible)
taskpointer 1 lock is held and has waiters [2]_
============ ======= ================================================
The fast atomic compare exchange based acquire and release is only
possible when bit 0 of lock->owner is 0.
.. [1] It also can be a transitional state when grabbing the lock
with ->wait_lock is held. To prevent any fast path cmpxchg to the lock,
we need to set the bit0 before looking at the lock, and the owner may
be NULL in this small time, hence this can be a transitional state.
.. [2] There is a small time when bit 0 is set but there are no
waiters. This can happen when grabbing the lock in the slow path.
To prevent a cmpxchg of the owner releasing the lock, we need to
set this bit before looking at the lock.
BTW, there is still technically a "Pending Owner", it's just not called
that anymore. The pending owner happens to be the top_waiter of a lock
that has no owner and has been woken up to grab the lock.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
Priority inheritance를 지원하는 RT-mutex subsystem
1-12Priority inheritance를 지원하는 RT-mutex는 PI-futex를 구현하는 데 사용된다. PI-futex를 통해 pthread_mutex_t의 PTHREAD_PRIO_INHERIT priority inheritance attribute를 지원할 수 있다. 자세한 내용은 Documentation/locking/pi-futex.rst를 참조한다.
이 기술은 -rt tree에서 개발되었고 pthread_mutex 지원을 위해 간결하게 다듬어졌다.
기본 원리
14-44RT-mutex는 단순 mutex의 semantics를 priority inheritance protocol로 확장한다.
낮은 priority의 RT-mutex owner는 RT-mutex를 해제할 때까지 더 높은 priority waiter의 priority를 상속한다. 일시적으로 priority가 올라간 owner가 다른 RT-mutex에서 다시 block되면 priority boost가 그 mutex의 owner에게 전파된다. RT-mutex가 unlock되는 즉시 boost는 제거된다.
이 방식은 shared resource를 보호하는 mutex 때문에 high-priority task가 block되는 시간을 줄인다. Priority inheritance가 잘못 설계된 application을 자동으로 고치는 수단은 아니지만, 잘 설계된 application이 determinism을 잃지 않으면서 high-priority thread의 중요한 부분에서 userspace lock을 사용할 수 있게 한다.
Waiter는 priority 순서로 RT-mutex waiter tree에 enqueue되며 priority가 같으면 FIFO 순서를 사용한다. 각 RT-mutex에서는 최상위 priority waiter만 owner의 priority waiter tree에 enqueue된다. 이 tree 역시 priority 순서로 정렬된다.
Task의 최상위 priority waiter가 timeout이나 signal 등으로 바뀌면 owner task의 priority를 다시 조정한다. Priority enqueueing은 pi_waiters가 처리한다.
Fast path와 owner field
46-77RT-mutex는 fast-path operation에 맞춰 최적화되어 있다. Contention이 없는 mutex를 lock하거나 waiter가 없는 mutex를 unlock할 때 내부 locking overhead가 없다. 최적화된 fast path에는 cmpxchg 지원이 필요하며, 지원하지 않는 platform에서는 RT-mutex 내부 spinlock을 사용한다.
RT-mutex 상태는 구조체의 owner field로 추적한다. lock->owner에는 owner의 task_struct pointer가 저장되고 bit 0은 lock에 waiter가 있는지를 나타낸다.
| owner | bit 0 | 의미 |
|---|---|---|
| NULL | 0 | Lock이 free이며 fast acquire 가능 |
| NULL | 1 | Lock은 free지만 waiter가 있고 top waiter가 lock을 획득하려는 중 |
| task pointer | 0 | Lock이 held이며 fast release 가능 |
| task pointer | 1 | Lock이 held이며 waiter가 있음 |
Atomic compare-exchange 기반 fast acquire와 release는 lock->owner의 bit 0이 0일 때만 가능하다.
전이 상태와 pending owner
79-95Owner가 NULL이고 bit 0이 1인 상태는 ->wait_lock을 보유한 채 lock을 획득하는 동안의 전이 상태일 수도 있다. Fast path cmpxchg가 lock에 접근하지 못하게 하려면 lock 상태를 조사하기 전에 bit 0을 set해야 한다. 이 짧은 구간에는 owner가 NULL일 수 있다.
Slow path에서 lock을 획득할 때는 waiter가 실제로 없는데 bit 0이 set된 짧은 구간도 존재한다. Owner가 lock을 release하는 cmpxchg를 막기 위해 lock을 조사하기 전에 bit를 먼저 set해야 하기 때문이다.
기술적으로 pending owner 개념은 여전히 존재하지만 더 이상 그 이름으로 부르지 않는다. Owner가 없는 lock의 top_waiter가 wakeup되어 lock을 획득하려는 상태가 pending owner에 해당한다.
PI futex의 kernel primitive
rt-mutex.rst:1-12RT-mutex는 pthread_mutex_t의 PTHREAD_PRIO_INHERIT attribute를 구현하는 PI futex의 기반입니다. 단순 mutex에 priority inheritance protocol을 추가하여 high-priority waiter가 low-priority owner 때문에 막힐 때 owner를 임시 boost합니다.