1. Jurang Fundamental Antara “Cepat” dan “Waktu-Nyata (Real-Time)”

Dalam percakapan sehari-hari, “pemrosesan waktu-nyata” sering disalahartikan sebagai “eksekusi super cepat”. Namun, bahkan server dengan prosesor superskalar multi-inti bergigahertz yang rata-rata merespons dalam satu milidetik tidak akan pernah diizinkan mengendalikan sistem Fly-by-Wire pesawat komersial, pemicu kantung udara (airbag) mobil, atau alat pacu jantung. Mengapa? Karena sistem tujuan umum mengoptimalkan throughput rata-rata (Average Throughput): jika perhitungan selesai dalam $0,5\,\text{ms}$ pada $99,999\,\%$ kasus, tetapi sekali dalam sejuta panggilan tertunda $200\,\text{ms}$ akibat cache miss, page fault, atau Garbage Collection (GC), pesawat akan jatuh atau kantung udara baru meledak setelah benturan.

Menurut formulasi klasik Donald Gillies dan Hermann Kopetz, aksioma komputasi waktu-nyata menyatakan bahwa kebenaran suatu sistem tidak hanya bergantung pada kebenaran logis dan aritmetis hasilnya, tetapi juga pada waktu fisik $t$ saat hasil tersebut diberikan relatif terhadap tenggat waktunya (deadline $d_i$). Berdasarkan fungsi utilitas waktu $U(t)$, sistem dibagi menjadi tiga kelas:

• Hard Real-Time: Melewatkan satu tenggat waktu ($t > d$) menyebabkan kegagalan katastropik ($U = -\infty$, mis. kendali penerbangan, rem ABS). Wajib dibuktikan secara matematis sebelum dijalankan.
• Firm Real-Time: Hasil yang terlambat bernilai nol ($U = 0$) dan langsung dibuang (mis. penyortiran visual di ban berjalan cepat, pembatalan order HFT).
• Soft Real-Time: Utilitas menurun secara kontinu setelah $d$ (mis. video 60 fps, panggilan VoIP).

2. Mimpi Buruk Analisis Waktu Eksekusi Terburuk (WCET)

Semua teori penjadwalan waktu-nyata mengasumsikan bahwa kita mengetahui Waktu Eksekusi Terburuk (Worst-Case Execution Time, $C_i$) dari setiap tugas $\tau_i$. Di sinilah muncul paradoks besar arsitektur komputer modern: hampir semua mekanisme perangkat keras yang dirancang untuk mempercepat rata-rata CPU (cache L1/L2/L3, prediksi percabangan, eksekusi Out-of-Order, TLB, DVFS, dan interupsi manajemen sistem SMI yang tak dapat ditutup) menghancurkan prediktabilitas WCET.

Pada pipa Out-of-Order dengan cache bahkan terjadi anomali waktu (Timing Anomalies): sebuah cache hit lokal justru dapat membuat jalur spekulatif merebut bus bersama lebih awal, sehingga total waktu eksekusi program menjadi lebih lama daripada saat terjadi cache miss! Oleh karena itu, sistem kritis (DO-178C Level A, ISO 26262 ASIL-D) menggunakan memori Scratchpad SRAM / TCM deterministik serta penguncian cache (Cache Locking), dan menghitung batas atas WCET secara statis melalui interpretasi abstrak dan Implicit Path Enumeration Technique (IPET) sebagai masalah pemrograman linier bulat (ILP) pada graf aliran kendali (CFG):

3. Liu & Layland (1973): Penjadwalan Periodik (RMS vs. EDF)

Misalkan terdapat $n$ tugas periodik independen $\Gamma = \{\tau_1, \dots, \tau_n\}$ dengan $\tau_i = (C_i, T_i, D_i)$ (WCET $C_i$, periode $T_i$, tenggat implisit $D_i = T_i$). Total utilisasi prosesor adalah:

Pada tahun 1973, C. L. Liu dan James W. Layland membuktikan teorema fundamental yang membandingkan prioritas statis dan dinamis:

3.1 Rate Monotonic Scheduling (RMS) dan Batas $\ln 2 \approx 69,3\,\%$

Dalam penjadwalan preemptif prioritas tetap, aturan Rate Monotonic (RMS) memberikan prioritas statis berbanding terbalik dengan periode: semakin pendek periode $T_i$ (semakin tinggi frekuensi $1/T_i$), semakin tinggi prioritas statisnya. Liu & Layland membuktikan teorema instan kritis (waktu respons terburuk $\tau_i$ terjadi saat ia dirilis bersamaan dengan semua tugas berprioritas lebih tinggi pada $t=0$) serta keoptimalan RMS di antara semua algoritma prioritas tetap, dengan batas atas utilisasi terkecil:

Penting: $69,3\,\%$ hanyalah syarat cukup, bukan syarat perlu! Jika periode bersifat harmonis (setiap periode merupakan kelipatan bulat dari periode yang lebih kecil, mis. $5\,\text{ms}, 10\,\text{ms}, 20\,\text{ms}$), RMS mampu mencapai 100% utilisasi. Untuk himpunan tugas umum, analisis waktu respons (RTA) dari Joseph & Pandya (1986) memberikan syarat perlu dan cukup yang eksak melalui iterasi titik tetap ($R_i \le D_i$):

3.2 Earliest Deadline First (EDF) dan Keoptimalan $100\,\%$

Dalam penjadwalan preemptif prioritas dinamis, Earliest Deadline First (EDF) setiap saat memberikan prioritas tertinggi kepada pekerjaan siap yang tenggat absolutnya $d_{i,k} = r_{i,k} + D_i$ paling dekat. Pada prosesor tunggal, syarat perlu dan cukup agar EDF dapat dijadwalkan mencapai batas fisik:

Contoh: Dengan $\tau_1 = (C_1=2, T_1=5)$ dan $\tau_2 = (C_2=4, T_2=7)$, utilisasinya adalah $U = 97,14\,\%$. Di bawah RMS, kedatangan $\tau_{1,2}$ pada $t=5$ ($d=10$) secara membabi buta menyela $\tau_{2,1}$ ($d=7$, yang tinggal menyisakan $1\,\text{ms}$), menyebabkan $R_2 = 8 > 7$ (gagal tenggat!). Di bawah EDF, pada $t=5$, karena $d_{2,1}=7 < d_{1,2}=10$, EDF mencegah penyelaan sehingga $\tau_{2,1}$ selesai tepat waktu pada $t=6 \le 7$.

Meski demikian, industri (VxWorks, FreeRTOS, QNX, AUTOSAR) tetap memilih RMS/DMS karena saat terjadi bebanไฟ lebih transien ($U > 1,0$), EDF mengalami efek domino katastropik di mana satu tugas yang terlambat memonopoli CPU dan menggagalkan seluruh tugas berikutnya secara beruntun, sedangkan RMS melindungi $100\,\%$ tugas kritis berprioritas tinggi dan dapat diimplementasikan dalam $O(1)$ menggunakan bitmap serta instruksi CLZ.

4. Insiden NASA Mars Pathfinder (1997) dan Inversi Prioritas

Pada Juli 1997, setelah mendarat di Mars, wahana Mars Pathfinder milik NASA (CPU IBM RAD6000 dengan RTOS VxWorks) tiba-tiba mengalami reset sistem berulang kali yang dipicu oleh watchdog timer, menghilangkan data ilmiah berharga.

Penyebabnya adalah inversi prioritas tak terbatas (Unbounded Priority Inversion) antara tiga tugas di sekitar mutex $M$ yang melindungi “bus informasi” bersama:

• Tugas meteorologi berprioritas rendah $\tau_L$ (ASI/MET) mengunci mutex $M$;
• Tugas distribusi bus kritis berprioritas tinggi $\tau_H$ (bc_dist) bangun, meminta $M$, dan terblokir;
• Sebelum $\tau_L$ sempat melepas $M$, datang tugas komunikasi berprioritas menengah $\tau_M$ (yang sama sekali tidak memakai $M$!). Karena $\text{Priority}(\tau_M) > \text{Priority}(\tau_L)$, $\tau_M$ menyela $\tau_L$ dalam waktu lama, mencegah $\tau_L$ membuka kunci $M$ dan menahan $\tau_H$ tetap terblokir hingga watchdog me-reset wahana antariksa tersebut!

  flowchart TD
    subgraph Bug["Inversi Prioritas Tak Terbatas pada Mars Pathfinder (1997)"]
        B1["1. Tugas prioritas rendah τ_L mengunci mutex M"] --> B2["2. Tugas prioritas tinggi τ_H meminta M dan masuk status BLOCKED"]
        B2 --> B3["3. Tugas prioritas menengah τ_M (tidak butuh M) datang!<br/>Karena Priority(τ_M) > Priority(τ_L), τ_M menyela τ_L dan menguasai CPU"]
        B3 --> B4["4. τ_L tidak bisa melepas M -> τ_H terblokir tanpa batas waktu<br/>Watchdog habis waktu dan memaksa reset total wahana di Mars!"]
    end

  flowchart TD
    subgraph Fix["Protokol Sinkronisasi Sha, Rajkumar & Lehoczky (1990)"]
        F1["Solusi A: Priority Inheritance Protocol (PIP)<br/>Saat τ_H terblokir di M, kernel langsung menaikkan prioritas efektif τ_L<br/>setara τ_H! τ_M tidak bisa menyela dan τ_L segera melepas M"]
        F2["Solusi B: Immediate Priority Ceiling Protocol (ICPP)<br/>Setiap mutex M diberi batas atas Ceil(M) = prioritas tertinggi penggunanya.<br/>Promosi instan saat mengunci: bebas deadlock & maksimal 1 blokir (B_i)!"]
        F1 --> F2
    end

Solusi matematisnya telah dibuktikan oleh Sha, Rajkumar, dan Lehoczky pada tahun 1990:

1. Priority Inheritance Protocol (PIP): Ketika $\tau_H$ terblokir pada mutex $M$ yang dipegang oleh $\tau_L$, kernel untuk sementara menaikkan prioritas efektif $\tau_L$ ke tingkat $\tau_H$, mencegah $\tau_M$ menyela. Setelah mereproduksi bug tersebut di Bumi, para insinyur JPL mengirimkan perintah C sejauh 190 juta kilometer ke shell VxWorks di Mars untuk mengubah variabel global SEM_INVERSION_SAFE dari 0 menjadi 1 langsung di RAM, menyelamatkan misi tersebut!
2. Priority Ceiling Protocol (PCP / ICPP: Immediate Priority Ceiling Protocol): Karena PIP masih memungkinkan blokir berantai (Chained Blocking) dan deadlock, ICPP (standar POSIX PTHREAD_PRIO_PROTECT dan AUTOSAR OS) menetapkan batas atas statis $\text{Ceil}(M_k) = \max\{\text{Priority}(\tau_i) \mid \tau_i \text{ memakai } M_k\}$ untuk setiap mutex $M_k$ dan menaikkan prioritas tugas tepat pada saat ia mengunci $M_k$. Ini menjamin 100% bebas deadlock dan membatasi penundaan maksimal setiap tugas menjadi paling banyak satu bagian kritis tunggal ($B_i$):