PENJADWALAN TUGAS-TUGAS REAL- TIME Bagian 2

1. Penjadwalan event-driven
Penjadwalan event-driven merupakan proses penjadwalan berdasarkan kejadian.
Kelas penjadwalan ini biasanya preemptive, yaitu, ketika sebuah tugas prioritas yang lebih
tinggi dapat menghentikan proses dengan perioritas yang lebih rendah.

1.1. Tipe penjadwalan event-driven
Tiga jenis penting penjadwalan berdsarkan kejadian:
1. Simple priority-based
2. Rate Monotonic Analysis (RMA)
3. Earliest Deadline First (EDF)
1.2. Foreground-Background
Penjadwalan foreground-background merupakan proses penjadwalan dengan
perioritas tinggi (preemptive). Dalam penjadwalan foreground-background, real-time task
dalam aplikasi dijalankan pada foreground. Sporadis, aperiodik, dan non-real-time tugas
dijalankan di background. Pada penjadwalan foreground-background, proses dapat berjalan
bersama-sama namun task dengan perioritas yang lebih tinggi dijalankan pada foreground
dan task dengan perioritas rendah dijalankan pada background.

1.3. Earliest Deadline First (EDF)
Penjadwalan dilakukan berdasarkan deadline, yaitu semakin dekat deadline-nya maka
semakin tinggi prioritasnya, dan demikian pula sebaliknya. Ketentuan yang berlaku, ketika
proses akan mulai jalan, maka proses akan mengumumkan syarat deadline-nya pada sistem.
Prioritas harus ditentukan untuk menggambarkan deadline dari proses yang baru dapat
berjalan.
Contoh penjadwalan mengunakan Earliest Deadline First: P1 memiliki p1=50 dan
t1=25 dan P2 memiliki p2=80 dan t2=35. P1 akan mendapat prioritas awal lebih tinggi karena
P1 lebih mendekatideadline daripada P2. Kemudian dilanjutkan oleh P2 di akhir burst
time dari P1. Apabila pada penjadwalan rate monotonic membiarkan P1 untuk melanjutkan
kembali, maka pada EDF, P2 (deadline pada 80) yang melanjutkan karena lebih
dekat deadline daripada P1 (deadline pada 100). Jadi, P1 dan P2 telah
menemui deadline pertama-nya. Proses P1 mulai jalan lagi di waktu 60 dan
menyelesaikan CPU burst time keduanya di waktu 85, juga menemui deadline keduanya di
waktu 100. P2 mulai jalan di titik ini, hanya dapat di preempted oleh P1 diawal periode
selanjutnya di waktu 100. P2 di preemptedkarena P1 memiliki deadline lebih awal (waktu
150) dari pada P2 (pada waktu 160). Di waktu 125, P1 menyelesaikan CPU burst-nya dan P2
melanjutkan eksekusinya, selesai di waktu 145 dan menemui deadline-nya.
Sistem idle sampai waktu 150, kemudian P1 dijadwalkan untuk dijalankan lagi.
Berbeda dengan algoritma rate-monotonic, penjadwalan EDF tidak membutuhkan
proses periodik, dan tidak juga membutuhkan jumlah waktu CPU per-burst yang konstan.
Syarat satu-satunya dari penjadwalan EDF adalah proses mengumumkan deadlinenya pada
penjadwal ketika dapat jalan. Secara teoritis, algoritma ini optimal, yaitu dapat memenuhi
semua deadline dari proses dan juga dapat menjadikan utilisasi CPU menjadi 100%. Namun
dalam kenyataannya hal tersebut sulit terjadi karena biaya dari context switching antara
proses dan interrupt handler.

1.3.1. EDF merupakan dynamic priority
Earliest deadline first (EDF) merupakan algoritma penjadwalan dinamis yang
digunakan dalam sistem operasi real-time untuk menempatkan proses dalam antrian prioritas.
Setiap kali acara penjadwalan terjadi (selesai tugas, tugas baru dirilis, dll) antrian akan dicari
untuk proses yang paling dekat dengan tenggat waktu. Proses ini adalah berikutnya yang akan
dijadwalkan untuk eksekusi. Dikatakan dinamis berarti sangat dimungkinkan untuk
menentukan nilai prioritas yang tepat untuk suatu task pada suatu waktu dan bias juga
menunjukkan bagaimana bias berubah sepanjang waktu.

1.3.2. Implementasi EDF
Implementasi yang masih lebih efisien dari EDF dapat dicapai sebagai berikut dengan
asumsi bahwa jumlah tenggat waktu yang berbeda bahwa tugas-tugas dalam sebuah aplikasi
dapat memiliki dibatasi. Dalam pendekatan ini, setiap kali tugas tiba, batas waktu mutlak
dihitung dari waktu rilis dan batas waktu relatif. Sebuah antrian FIFO terpisah dipertahankan
untuk setiap tenggat waktu relatif berbeda bahwa tugas-tugas dapat dimiliki. Scheduler
menyisipkan tugas baru yang tiba pada akhir sesuai antrian tenggat waktu yang relatif. Jelas,
tugas di setiap antrian yang dipesan sesuai tenggat waktu mutlak.

1.3.3. Kekurangan EDF
Beberapa kekurangan penting EDF bila digunakan untuk penjadwalan tugas real-time
Transient Overload Problem : Kelebihan Transient menunjukkan kelebihan dari sistem
untuk waktu yang sangat singkat. Kelebihan Transient terjadi ketika beberapa tugas
membutuhkan waktu lebih lama untuk menyelesaikan daripada apa yang awalnya
direncanakan selama waktu desain . Sebuah tugas mungkin memakan waktu lebih lama untuk
menyelesaikan karena berbagai alasan . Sebagai contoh, mungkin memasuki infinite loop
atau menemukan sebuah kondisi yang tidak biasa dan masukkan cabang jarang digunakan
karena beberapa nilai input abnormal. Ketika EDF digunakan untuk menjadwalkan satu set
periodik tugas real-time , sebuah overshoot waktu tugas selesai dapat menyebabkan beberapa
tugas lain ( s ) untuk melewatkan tenggat waktu. Hal ini biasanya sangat sulit untuk
memprediksi selama desain program dimana tugas mungkin akan kehilangan tenggat waktu
ketika kelebihan beban transien terjadi pada sistem karena prioritas rendah tugas overshoot
batas waktunya . Satu-satunya prediksi yang dapat dibuat adalah bahwa tugas (tasks) yang
akan segera berjalan setelah tugas yang menyebabkan overload sementara akan tertunda dan
mungkin kehilangan batas waktu masing-masing (s). Namun, pada waktu yang berbeda tugas
mungkin diikuti dengan tugas yang berbeda dalam pelaksanaan. Namun, hal ini
menyebabkan tidak membantu kita untuk menemukan mana tugas mungkin akan kehilangan
batas waktunya. Bahkan tugas yang paling penting mungkin akan kehilangan batas waktunya
karena tugas prioritas yang sangat rendah overshooting waktu penyelesaian yang
direncanakan. Jadi, itu harus jelas bahwa di bawah EDF setiap jumlah desain yang cermat
tidak akan menjamin bahwa tugas yang paling penting tidak akan melewatkan batas waktu di
bawah overload sementara. Ini adalah kelemahan serius dari algoritma penjadwalan EDF.
Resource Sharing Problem: Ketika EDF digunakan untuk menjadwalkan satu set tugas realtime,
biaya overhead yang sangat tinggi mungkin harus dikeluarkan untuk mendukung
berbagi sumber daya antara tugas-tugas tanpa membuat tugas untuk melewatkan tenggat
waktu masing-masing.
Efficient Implementation Problem: Implementasi yang efisien yang mencapai O (1) biaya
overhead mengasumsikan bahwa jumlah tenggat waktu relatif dibatasi. Hal ini mungkin tidak
dapat diterima dalam beberapa situasi. Untuk algoritma EDF lebih fleksibel, kita perlu
menjaga tugas dalam hal tenggat waktu mereka menggunakan antrian prioritas. Setiap kali
tugas tiba, itu dimasukkan ke dalam antrian prioritas. Kompleksitas penyisipan elemen ke
dalam antrian prioritas adalah urutan log2 n, di mana n adalah jumlah tugas yang harus
dijadwalkan. Ini merupakan overhead runtime tinggi, karena sebagian besar tugas-tugas realtime
adalah periodik dengan periode kecil dan tenggat waktu yang ketat.
Tugas Kelompok

1.4 Get an overview of Rate Monotonic Algorithm (RMA)
RMA adalah algoritma prioritas statis dan secara luas digunakan dalam aplikasi
praktis. RMA memberikan prioritas pekerjaan berdasarkan tarif mereka kejadian. Semakin
rendah tingkat kejadian tugas, semakin rendah adalah prioritas yang ditugaskan untuk itu.
Sebuah tugas yang memiliki tingkat kejadian tertinggi (periode terendah) yang diberikan
prioritas tertinggi dalam artian pada periode task yang dengan perioritasnya yang paling
tinggi itu yang akan di kerjakan terlebih dahulu dan di lihat dari seberapah banyak task
tersebut di munculkan

1.5 Know the necessary and sufficient conditions for a set of real-time tasks to be RMAschedulable
Necessary Condition: Satu set periodik tugas real-time tidak akan RMA
schedulable kecuali mereka memenuhi kondisi yang diperlukan dalam arti apabilah ada task
yang tidak memenuhi kodisi yang di butuhkan dalam RTOS maka task tersebut tidak akan di
gunakan
Sufficient Condition: Jika satu set tugas memenuhi kondisi yang cukup, maka
dijamin bahwa set tugas akan RMA schedulable. Dalam artian apabilah tasknya memenuhi
syarat untuk RMA maka task tersebut akan di proses

1.6 Work out solutions to problems based on RMA
Bahwa prioritas tugas ditentukan oleh periodenya. Kadang-kadang, kita harus
mengubah prioritas tugas agar semua tugas kritis dapat terselesaikan. Solusinya adalah
dengan meningkatkan prioritas tugas kritis dengan mengurangi periodenya. Alternatif lain
adalah dengan mengurangi periode tugas kritis dan menambah periode tugas yang non-kritis.

1.7 Infer the maximum achievable CPU utilization
Utilisasi pada cpu akan terjadi apabilah semua task yang berjalan di lakukan dengan
cara mengoptimalkan RMA diamana pada periode task yang dengan perioritasnya yang
paling tinggi itu yang akan di kerjakan terlebih dahulu dan di lihat dari seberapah banyak task
tersebut di munculkan

1.8 Understand the Advantages and Disadvantages of RMA
Keuntungan:
RMA sangat umum digunakan untuk penjadwalan tugas real-time dalam aplikasi praktis dan
pada RMA tidak terdapat deadline
Kelemahan :
RMA tidak optimal ketika periode tugas dan tenggat waktu berbeda.

1.9 Get an overview of Deadline Monotonic Algorithm (DMA)
DMA pada dasarnya adalah sebuah varian dari RMA dan memberikan prioritas tugas
berdasarkan tenggat waktu daripada prioritas menugaskan berdasarkan periode tugas seperti
yang dilakukan di RMA

1.10 Understand the phenomenon of Context-Switching and Self-Suspension
Suatu proses perpindahan task dimana task dengan prioritas yang lebih besar yang akan di
laksanakan terlebih dahulu dengan asumsi task yang lebih rendah juga akan di laksanakan
tapi setelah task dengan periotas yang lebih besar telah selesai di jalankan