Priority Inheritance Membatasi Priority Inversion di Sekitar Mutex

Priority scheduling tidak menjamin task runnable dengan priority tertinggi selalu dapat maju. Task ber-priority tinggi dapat terblokir pada mutex yang dimiliki task ber-priority rendah. Jika pekerjaan ber-priority menengah kemudian melakukan preemption terhadap pemilik mutex, task ber-priority tinggi tetap terblokir walaupun pekerjaan menengah itu tidak memiliki dependency langsung terhadap mutex.

Kondisi ini disebut priority inversion. Inversion dimulai dari dependency biasa: task ber-priority tinggi memerlukan resource yang sedang dimiliki task ber-priority rendah. Bagian yang merugikan adalah interference dari task di antara kedua priority tersebut, karena interference itu dapat menunda pemilik mutex dan memperpanjang interval blocking.

Priority inheritance adalah salah satu protokol untuk membatasi interference tersebut.

Mutex membentuk dependency scheduling tidak langsung

Pertimbangkan tiga task:

L: priority rendah
M: priority menengah
H: priority tinggi

Misalkan L memperoleh mutex m. Sebelum L melepaskannya, H menjadi runnable dan mencoba memperoleh m. H terblokir karena mutex masih dimiliki L.

Tanpa protokol khusus, L tetap memiliki scheduling priority rendah. Jika M menjadi runnable, scheduler dapat menjalankan M sebelum L. Keputusan itu normal dalam fixed-priority scheduling, tetapi menunda satu-satunya task yang dapat melepaskan resource yang dibutuhkan H.

Dependency efektifnya menjadi:

H menunggu L
L bersaing dengan M
M secara tidak langsung menunda H

Scheduler melihat priority; mutex menghadirkan dependency yang melintasi priority tersebut.

Inheritance menaikkan priority pemilik untuk sementara

Dengan priority inheritance, pemilik mutex dapat sementara berjalan pada priority task lebih tinggi yang sedang terblokir pada mutex tersebut. Pada contoh ini, ketika H terblokir pada m, L mewarisi priority milik H.

M tidak lagi dapat melakukan preemption terhadap L hanya karena base priority miliknya lebih tinggi daripada L. Pemilik mutex dapat berjalan, menyelesaikan protected work, lalu melepaskan m. Setelah inherited priority tidak lagi diperlukan, L kembali ke priority yang ditentukan protokol dan dependency yang masih tersisa.

Protokol ini tidak membuat critical section menjadi lebih cepat. Perubahannya ada pada scheduling, sehingga pekerjaan lain dengan priority di tengah tidak mudah memperpanjang interval blocking.

Inheritance dapat merambat melalui rantai lock

Sistem nyata dapat memiliki dependency bertingkat. Misalkan H menunggu mutex milik L, sedangkan L sendiri terblokir pada mutex lain yang dimiliki task X.

Implementasi yang memadai perlu memperhitungkan rantai tersebut. Menaikkan priority L saja tidak cukup jika L belum dapat berjalan sampai X melepaskan mutex kedua. Inherited priority mungkin perlu diteruskan ke X, sehingga task di ujung rantai dependency dapat berjalan dan melepaskan resource.

Secara konseptual:

H -> menunggu m1 -> L
L -> menunggu m2 -> X

Tekanan scheduling yang berasal dari H mengikuti relasi blocking menuju X.

Propagasi ini juga membuat bookkeeping implementasi lebih kompleks. Satu task dapat memiliki beberapa mutex, menerima inherited priority dari beberapa waiter, lalu melepaskan mutex tersebut dalam urutan berbeda. Effective priority harus mencerminkan dependency yang masih aktif, bukan di-reset begitu saja setelah satu operasi unlock.

Priority inheritance membatasi interference, bukan seluruh blocking

Task ber-priority tinggi masih dapat menunggu pemilik resource yang ber-priority lebih rendah. Pemilik mungkin sudah berada di dalam critical section ketika task ber-priority tinggi datang, dan mutual exclusion tetap mengharuskan section tersebut selesai.

Priority inheritance terutama menangani preemption oleh task yang tidak terkait saat pemilik mutex sedang memblokir pekerjaan ber-priority lebih tinggi. Protokol ini tidak menghapus resource dependency, tidak mempersingkat code arbitrer di dalam critical section, dan tidak mengubah mutex menjadi primitive nonblocking.

Critical section yang panjang tetap menjadi masalah. Hal yang sama berlaku untuk blocking operation saat mutex masih dipegang. Jika pemilik yang priority-nya dinaikkan menunggu I/O atau resource lain, CPU scheduling priority yang diwariskan tidak dapat membuat operasi eksternal itu selesai seketika.

Protokol memiliki biaya dan batas

Priority inheritance memerlukan kerja sama antara synchronization primitive dan scheduler. Sistem perlu melacak waiter, owner, effective priority, serta perubahan akibat operasi lock dan unlock. Chained blocking dapat memerlukan propagasi melewati beberapa task.

Biaya tersebut masuk akal pada workload yang memerlukan batas terhadap priority interference. Untuk aplikasi biasa yang berorientasi throughput dan tidak memakai kontrak real-time priority, mekanisme ini bisa saja tidak diperlukan.

Semantik detail bergantung pada platform. POSIX, real-time operating system, dan language runtime dapat berbeda dalam dukungan mutex protocol, scheduling policy, privilege requirement, nesting behavior, dan failure case. Code yang bergantung pada priority inheritance perlu memakai primitive yang didokumentasikan, bukan menganggap setiap mutex menyediakan perilaku tersebut.

Priority ceiling adalah protokol yang berbeda

Priority inheritance bereaksi setelah task ber-priority lebih tinggi terblokir. Priority-ceiling protocol memakai pendekatan berbeda dengan mengaitkan ceiling pada protected resource dan membatasi eksekusi berdasarkan ceiling tersebut.

Keduanya bukan label yang dapat dipertukarkan. Admission rule, blocking property, configuration requirement, dan interaksi dengan scheduler berbeda. Desain real-time perlu memilih protokol berdasarkan timing model dan jaminan platform, bukan sekadar karena keduanya menangani blocking yang berkaitan dengan priority.

Jaga dependency graph tetap kecil

Priority inheritance paling efektif ketika ownership mutex singkat dan relasi resource terkendali. Protokol ini bukan pengganti pengurangan shared state yang tidak diperlukan.

Critical section yang kecil mengurangi interval blocking langsung. Lock order yang konsisten mengurangi rantai dependency bermasalah. Menghindari blocking work yang tidak terkait selama mutex dipegang membuat pemilik yang priority-nya dinaikkan tetap berfokus pada operasi yang dapat melepaskan task yang menunggu.

Intinya spesifik: ketika task ber-priority tinggi terblokir oleh pemilik mutex ber-priority rendah, menjadwalkan pemilik itu seolah tetap ber-priority rendah dapat memberi pekerjaan lain kesempatan memperpanjang inversion. Priority inheritance membawa urgensi task yang terblokir ke pemilik resource, dan melalui lock chain yang didukung, sampai dependency terkait selesai.