Penjadwalan tugas-tugas Real-Time

Dalam sesi ini, kita akan membahas berbagai algoritma untuk penjadwalan-event. Dari pelajaran sebelumnya, kita dapat mengingat hal-hal berikut:

Clock-driven penjadwal adalah mereka di mana titik penjadwalan ditentukan oleh interupsi yang diterima dari jam. Dalam event-driven, titik penjadwalan ditentukan oleh peristiwa-peristiwa tertentu yang menghalangi clock interupsi. Yang hibrida menggunakan kedua jam interupsi serta kejadian acara menentukan titik penjadwalan mereka

Penjadwal siklik sangat efisien. Namun, kelemahan menonjol dari penjadwal siklik adalah bahwa hal itu menjadi sangat kompleks untuk menentukan ukuran frame yang sesuai serta jadwal layak jika jumlah meningkat tugas. Selanjutnya, di hampir setiap frame beberapa waktu pemrosesan yang terbuang (sebagai ukuran frame lebih besar dari setiap saat pelaksanaan tugas) yang mengakibatkan jadwal sub-optimal. Penjadwal-event mengatasi kekurangan ini. Selanjutnya, penjadwal-event dapat menangani tugas-tugas aperiodik dan sporadis lebih mahir. Di sisi lain, penjadwal-event kurang efisien karena mereka menyebarkan algoritma penjadwalan lebih kompleks. Oleh karena itu, penjadwal-event kurang cocok untuk aplikasi embedded seperti ini dituntut untuk ukuran kecil, biaya rendah, dan mengkonsumsi sejumlah kecil daya.

Sekarang harus jelas mengapa penjadwal-event yang selalu digunakan dalam semua aplikasi moderat dan berukuran besar yang memiliki banyak tugas, sedangkan penjadwal siklik yang banyak digunakan dalam aplikasi kecil. Dalam penjadwalan-event, titik penjadwalan ditentukan oleh penyelesaian tugas dan acara kedatangan tugas. Kelas ini penjadwal biasanya preemptive, yaitu, ketika sebuah tugas prioritas yang lebih tinggi menjadi siap, preempts setiap tugas prioritas yang lebih rendah yang mungkin berjalan.

1.1. Types of Event Driven Schedulers

Kita akan membahas tiga jenis penting penjadwalan berdasarkan kejadian:

·         Simple priority-based

·         Rate Monotonic Analysis (RMA)

·         Earliest Deadline First (EDF)

Yang paling sederhana di antaranya adalah latar belakang-scheduler, yang akan kita bahas selanjutnya. Pada bagian 3.4, kita membahas EDF dan dalam bagian 3.5, kita membahas RMA.

1.2. Foreground-Background Scheduler

Sebuah latar Foreground-scheduler mungkin sederhana prioritas-driven preemptive scheduler. Dalam penjadwalan foreground-background, real-time tugas dalam aplikasi dijalankan sebagai tugas kedepan tanah. Sporadis, aperiodik, dan non-real-time tugas dijalankan sebagai tugas latar belakang. Di antara tugas-tugas latar depan, di setiap titik penjadwalan tugas prioritas tertinggi diambil untuk penjadwalan. Sebuah tugas latar belakang dapat berjalan ketika tidak ada tugas latar depan siap. Dengan kata lain, tugas latar belakang dijalankan pada prioritas terendah.

Mari kita asumsikan bahwa dalam suatu sistem real-waktu tertentu, ada tugas latar depan n yang dilambangkan sebagai: T1, T2, ..., Tn. Seperti telah disebutkan, tugas latar depan semua periodik. Biarkan TB menjadi satu-satunya tugas latar belakang. Biarkan eB menjadi syarat waktu proses TB. Dalam hal ini, waktu penyelesaian (CTB) untuk tugas latar belakang diberikan oleh:

ct_{B = e}B / (1−_i=1Σ ⁿe_i / p_i) … (3.1/2.7)

Ungkapan ini mudah untuk menafsirkan. Ketika setiap tugas latar depan mengeksekusi, tugas latar belakang menunggu. Penggunaan CPU rata-rata karena latar depan tugas Ti ei / pi, sejak ei jumlah waktu pemrosesan yang diperlukan selama setiap periode pi. Ini berarti bahwa semua tugas latar depan bersama-sama akan menghasilkan utilisasi CPU dari i = nei 1Σ / pi. Oleh karena itu, rata-rata waktu yang tersedia untuk pelaksanaan tugas latar belakang di setiap unit waktu 1-i = 1Σ nei / pi. Oleh karena itu, Expr. 2.7 berikut dengan mudah. Kita sekarang menggambarkan penerapan Expr. 2,7 melalui tiga contoh sederhana berikut.

1.3. Examples

Contoh 1: Pertimbangkan sebuah sistem real-time di mana tugas-tugas yang dijadwalkan menggunakan penjadwalan latar-belakang. Hanya ada satu periodik foreground tugas Tf: (φf = 0, pf = 50 msec, ef = 100 msec, df = 100 msec) dan tugas latar belakang menjadi TB = (eB = 1000 msec). Menghitung waktu penyelesaian untuk tugas latar belakang.

Solusi: Dengan menggunakan ekspresi (2.7) untuk menghitung waktu penyelesaian tugas, kita memiliki

ct_{B = 1000 / (1−50/100) = 2000 msec}

Jadi, tugas TB background akan mengambil 2000 milidetik untuk menyelesaikan.

Contoh 2: Secara sederhana prioritas-driven preemptive scheduler, dua tugas T1 dan T2 periodik dan tugas latar belakang dijadwalkan. Periodik T1 tugas memiliki prioritas tertinggi dan mengeksekusi sekali setiap 20 milidetik dan membutuhkan 10 milidetik waktu eksekusi setiap kali. T2 membutuhkan 20 milidetik pengolahan setiap 50 milidetik. T3 merupakan tugas latar belakang dan membutuhkan 100 milidetik untuk menyelesaikan. Dengan asumsi bahwa semua tugas mulai dari waktu 0, menentukan waktu di mana T3 akan menyelesaikan.

Contoh 3: Misalkan dalam contoh 1, overhead dari 1 msec pada rekening setiap konteks saklar yang harus diperhitungkan. Hitunglah waktu penyelesaian T_B.

switching overhead dari 1 msec. Ini telah ditunjukkan sebagai persegi panjang yang diarsir pada Gambar. 30.1. Selanjutnya setiap kali tugas latar depan berjalan, preempts tugas latar belakang dan menimbulkan satu konteks switch. Setelah menyelesaikan setiap contoh tugas latar depan, tugas latar belakang berjalan dan menimbulkan lain context switch. Dengan pengamatan ini, untuk menyederhanakan perhitungan kita tentang waktu penyelesaian sebenarnya T_B, kita dapat membayangkan bahwa waktu eksekusi dari setiap tugas latar depan meningkat dua kali konteks beralih (satu karena dirinya sendiri dan yang lain karena tugas latar belakang berjalan setelah setiap waktu itu selesai). Dengan demikian, efek bersih dari konteks switch bisa dibayangkan akan menyebabkan waktu pelaksanaan tugas latar depan meningkat 2 kali konteks switch, yaitu sampai 52 milidetik dari 50 milidetik. Hal ini pictorially telah ditunjukkan dalam Gambar. 30.1.

Sekarang, dengan menggunakan Expr. 2.7, kita mendapatkan waktu yang dibutuhkan oleh tugas latar belakang untuk menyelesaikan:

1000/(1−52/100) = 2083.4 milliseconds

Dalam dua bagian berikut, kita memeriksa dua penting penjadwal-event: EDF (Earliest Deadline) dan RMA (Tingkat monotonik Algoritma). EDF adalah algoritma dinamis yang optimal prioritas real-time tugas penjadwalan dan RMA adalah algoritma statis yang optimal prioritas real-time penjadwalan tugas.

1.4. Earliest Deadline First (EDF) Scheduling

Dalam Batas Pertama (EDF) penjadwalan awal, di setiap titik penjadwalan tugas memiliki tenggat waktu terpendek diambil untuk penjadwalan. Ini prinsip dasar algoritma ini sangat intuitif dan mudah dimengerti. Tes schedulability untuk EDF juga sederhana. Satu set tugas schedulable bawah EDF, jika dan hanya jika memenuhi syarat bahwa pemanfaatan prosesor total karena ke set tugas kurang dari 1. Untuk satu set periodik tugas real-time {T1, T2, ..., Tn}, kriteria schedulability EDF dapat dinyatakan sebagai:

_i=1Σ ⁿe_i / p_i = _i=1Σ ⁿu_i ≤ 1 … (3.2/2.8)

dimana ui rata-rata utilisasi karena tugas Ti dan n adalah jumlah tugas di set tugas. Expr. 3.2 merupakan sebuah kondisi yang cukup untuk satu set tugas yang diperlukan dan menjadi EDF schedulable.

set tugas tidak schedulable bawah EDF, maka tidak ada algoritma penjadwalan lainnya feasibly dapat menjadwalkan tugas ini ditetapkan. Pada uji schedulability sederhana untuk EDF (Expr. 3.2), kita mengasumsikan bahwa periode tugas masing-masing adalah sama dengan tenggat waktu. Namun, dalam masalah-masalah praktis masa tugas terkadang berbeda dari tenggat waktu. Dalam kasus tersebut, tes schedulability perlu diubah. Jika pi> di, maka setiap tugas yang perlu ei jumlah waktu komputasi setiap menit (pi, di) durasi waktu. Oleh karena itu, kita dapat menulis ulang Expr. 3.2 sebagai:

_i=1Σ ⁿe_i / min(p_i, d_i) ≤ 1 … (3.3/2.9)

Namun, jika pi <di, adalah mungkin bahwa satu set tugas adalah EDF schedulable, bahkan ketika set tugas gagal memenuhi Expr 3.3. Oleh karena itu, Expr 3.3 adalah konservatif ketika pi <di, dan bukan merupakan kondisi yang diperlukan, tetapi hanya kondisi yang cukup untuk tugas yang diberikan ditetapkan menjadi EDF schedulable.

Meskipun EDF adalah sederhana serta algoritma yang optimal, ia memiliki beberapa kekurangan yang membuat hampir tidak dapat digunakan dalam aplikasi praktis. Masalah utama dengan EDF dibahas dalam Sec. 3.4.3. Selanjutnya, kita membahas konsep tugas prioritas di EDF dan kemudian mendiskusikan bagaimana EDF dapat praktis dilaksanakan.

1.4.1. Is EDF Really a Dynamic Priority Scheduling Algorithm?

Kami menyatakan di Sec 3.3 bahwa EDF algoritma penjadwalan prioritas dinamis. Apakah setelah semua benar pada bagian kita untuk menegaskan bahwa EDF merupakan algoritma penjadwalan tugas prioritas dinamis? Jika EDF itu harus dianggap sebagai prioritas algoritma yang dinamis , kita harus bisa menentukan nilai prioritas yang tepat dari tugas pada setiap titik waktu dan juga dapat menunjukkan bagaimana perubahan dengan waktu . Jika kita merenungkan diskusi kami EDF dalam bagian ini , penjadwalan EDF tidak memerlukan nilai prioritas harus dihitung untuk setiap tugas setiap saat . Bahkan , EDF tidak memiliki gagasan tentang nilai prioritas untuk suatu tugas . Tugas dijadwalkan hanya berdasarkan kedekatan tenggat waktu mereka . Namun, semakin lama tugas menunggu dalam antrian siap, semakin tinggi adalah kesempatan ( probabilitas ) yang diambil untuk penjadwalan . Jadi , kita dapat membayangkan bahwa nilai prioritas maya terkait dengan tugas terus meningkat dengan waktu sampai tugas diambil untuk penjadwalan . Namun, penting untuk memahami bahwa di EDF tugas tidak memiliki nilai prioritas yang terkait dengan mereka , juga tidak scheduler melakukan salah perhitungan prioritas untuk menentukan schedulability dari tugas baik di waktu berjalan atau waktu kompilasi .

1.4.2. Implementation of EDF

Implementasi yang naif EDF akan mempertahankan semua tugas yang siap untuk dieksekusi dalam antrian. Setiap tugas baru tiba akan dimasukkan pada akhir antrian. Setiap node dalam antrian akan berisi batas waktu mutlak tugas. Pada setiap titik preemption, seluruh antrian akan dipindai dari awal untuk menentukan tugas memiliki tenggat waktu terpendek. Namun, implementasi ini akan sangat tidak efisien. Mari kita menganalisis kompleksitas skema ini. Setiap penyisipan tugas akan dicapai dalam O (1) atau waktu konstan, tapi seleksi tugas (untuk menjalankan berikutnya) dan penghapusan yang akan membutuhkan O (n) waktu, dimana n adalah jumlah tugas dalam antrian.

Implementasi yang lebih efisien EDF akan menjadi sebagai berikut. EDF dapat diimplementasikan dengan mempertahankan semua tugas siap dalam antrian prioritas diurutkan. Sebuah prioritas antrian diurutkan secara efisien dapat diimplementasikan dengan menggunakan struktur data heap. Dalam antrian prioritas, tugas selalu disimpan diurutkan sesuai dengan kedekatan tenggat waktu mereka. Ketika tugas tiba, sebuah rekor untuk dapat dimasukkan ke dalam tumpukan di O (log2 n) waktu di mana n adalah jumlah tugas dalam antrian prioritas. Pada setiap titik penjadwalan, tugas berikutnya yang akan dijalankan dapat ditemukan di bagian atas tumpukan. Ketika tugas diambil untuk penjadwalan, perlu dihapus dari antrian prioritas. Hal ini dapat dicapai dalam O (1) waktu.

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

Untuk menemukan tugas dengan tenggat waktu mutlak awal, scheduler hanya perlu mencari di antara benang-benang semua antrian FIFO. Jika jumlah antrian prioritas dikelola oleh scheduler adalah Q, maka urutan pencarian akan menjadi O (1). Waktu untuk memasukkan tugas juga akan menjadi O (1).

1.4.3. Shortcomings of EDF

Dalam subbagian ini, kami menyoroti beberapa kekurangan penting EDF bila digunakan untuk penjadwalan tugas real-time dalam aplikasi praktis.

Transient Overload Soal : 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 mereka . Hal ini biasanya sangat sulit untuk memprediksi selama desain program mana 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 ( tugas ) yang akan segera berjalan setelah tugas menyebabkan kelebihan beban transien akan mendapatkan ditunda dan mungkin kehilangan ( mereka) 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 kehilangan tenggat waktu . Bahkan tugas yang paling penting mungkin akan kehilangan tenggat waktu karena prioritas yang sangat rendah tugas overshoot waktu penyelesaian yang direncanakan . Jadi , itu harus jelas bahwa di bawah EDF setiap jumlah desain hati-hati tidak akan menjamin bahwa tugas yang paling penting tidak akan melewatkan batas waktu di bawah berlebihan sementara. Ini adalah kelemahan serius dari algoritma penjadwalan EDF .

Sumber Sharing Masalah: Saat EDF digunakan untuk menjadwalkan satu set tugas real-time, tidak dapat diterima overhead tinggi mungkin harus dikeluarkan untuk mendukung berbagi sumber daya antara tugas-tugas tanpa membuat tugas untuk melewatkan tenggat waktu masing-masing. Kami memeriksa masalah ini secara rinci dalam pelajaran berikutnya.

Efisien Pelaksanaan Masalah: efisien implementasi yang kita bahas dalam Sec. 3.4.2 sering tidak praktis karena sulit untuk membatasi jumlah tugas dengan tenggat waktu yang berbeda ke nomor yang wajar. Yang efisien implementasi yang mencapai O (1) biaya overhead mengasumsikan bahwa jumlah tenggat waktu relatif dibatasi. Ini mungkin tidak dapat diterima dalam beberapa situasi. Untuk algoritma EDF lebih fleksibel, kita perlu menjaga tugas memerintahkan 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, dimana n adalah jumlah tugas yang harus dijadwalkan. Ini merupakan overhead runtime tinggi, karena sebagian besar tugas real-time yang periodik dengan periode kecil dan tenggat waktu yang ketat.

1.5. Rate Monotonic Algorithm(RMA)

Kami sudah menunjukkan bahwa RMA merupakan algoritma penjadwalan-event penting. Ini 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. RMA telah terbukti menjadi algoritma statis yang optimal prioritas real-time penjadwalan tugas.

Di RMA, prioritas tugas berbanding lurus dengan laju (atau, berbanding terbalik dengan periodenya). Artinya, prioritas setiap tugas Ti dihitung sebagai: prioritas = k / pi, dimana pi adalah periode tugas Ti dan k adalah konstanta. Menggunakan ungkapan sederhana ini, plot nilai prioritas tugas di bawah RMA untuk tugas-tugas dari periode yang berbeda dapat dengan mudah diperoleh. Plot ini telah ditunjukkan pada Gambar. 30.10 (a) dan Gambar. 30.10 (b). Hal ini dapat dilihat dari angka-angka yang prioritas tugas meningkat secara linear dengan tingkat kedatangan tugas dan berbanding terbalik dengan jangka waktunya.

1.5.1. Schedulability Test for RMA

Masalah penting yang dibahas selama desain sistem real-time berbasis prosesor tunggal adalah untuk memeriksa apakah suatu set periodik tugas real-time feasibly bisa dijadwalkan di bawah RMA. Schedulability dari tugas yang ditetapkan dalam RMA dapat ditentukan dari pengetahuan tentang eksekusi kali terburuk dan periode tugas. Sebuah pertanyaan yang bersangkutan pada saat ini adalah bagaimana bisa seorang pengembang sistem menentukan kasus terburuk waktu pelaksanaan tugas bahkan sebelum sistem ini dikembangkan. Yang terburuk kali eksekusi biasanya ditentukan secara eksperimental atau melalui simulasi.

Berikut ini adalah beberapa kriteria penting yang dapat digunakan untuk memeriksa schedulability dari satu set tugas yang ditetapkan di bawah RMA.

1.5.1.1 Necessary Condition

Satu set periodik tugas real-time tidak akan RMA schedulable kecuali mereka memenuhi kondisi yang diperlukan sebagai berikut:

_i=1Σ ⁿe_i / p_i = _i=1Σ ⁿu_i ≤ 1

dimana ei adalah yang terburuk waktu eksekusi kasus dan pi adalah periode tugas Ti, n adalah jumlah tugas yang akan dijadwalkan, dan ui adalah utilisasi CPU karena tugas Ti. Tes ini hanya mengungkapkan fakta bahwa penggunaan CPU total karena untuk semua tugas di set tugas harus kurang dari 1.

1.5.1.2 Sufficient Condition

Penurunan kondisi kecukupan untuk RMA schedulability adalah hasil yang penting dan diperoleh oleh Liu dan Layland pada tahun 1973. Sebuah derivasi formal Liu dan hasil Layland dari prinsip pertama adalah di luar cakupan diskusi ini. Kami kemudian akan mengacu pada kecukupan sebagai kondisi Layland Liu dan. Satu set n tugas periodik real-time schedulable bawah RMA, jika

_i=1Σ ⁿu_i ≤ n(2^1/n − 1) (3.4/2.10)

dimana ui adalah pemanfaatan karena tugas Ti. Mari kita memeriksa implikasi dari hasil ini. Jika satu set tugas memenuhi kondisi yang cukup, maka dijamin bahwa set tugas akan RMA schedulable.

Pertimbangkan kasus di mana hanya ada satu tugas dalam sistem, yaitu n = 1.

Substituting n = 1 in Expr. 3.4, we get,

_i=1Σ ¹u_i ≤ 1(2^1/1 − 1) or _i=1Σ ¹u_i ≤ 1

Similarly for n = 2, we get,

_i=1Σ ²u_i ≤ 2(2^1/2 − 1) or _i=1Σ ²u_i ≤ 0.828

For n = 3, we get,

_i=1Σ ³u_i ≤ 3(2^1/3 − 1) or _i=1Σ ³u_i ≤ 0.78

For n → ∞, we get,

_i=1Σ ^∞u_i ≤ 3(2^1/∞ − 1) or _i=1Σ ^∞u_i ≤ ∞.0

Evaluasi Expr. 3,4 ketika n → ∞ melibatkan ekspresi tak tentu dari jenis ∞ .0. Dengan menerapkan aturan L'Hospital, kita dapat memverifikasi bahwa sisi kanan ekspresi bernilai loge2 = 0,692. Dari perhitungan di atas, jelaslah bahwa penggunaan CPU maksimum yang dapat dicapai di bawah RMA adalah 1. Hal ini dicapai ketika hanya ada satu tugas dalam sistem. Karena jumlah meningkat tugas, penggunaan CPU dicapai jatuh dan sebagai n → ∞, pemanfaatan dicapai stabil pada loge2, yang sekitar 0.692. Hal ini pictorially ditunjukkan pada Gambar. 30.3. Kita sekarang menggambarkan penerapan kriteria schedulability RMA melalui beberapa contoh.

1.5.2. Examples

Contoh 5: Periksa apakah set berikut periodik tugas real-time schedulable bawah RMA pada uniprocessor sebuah:

T₁ = (e₁=20, p₁=100), T₂ = (e₂=30, p₂=150), T₃ = (e₃=60, p₃=200).

Solusi: Mari kita menghitung total penggunaan CPU dicapai karena tiga tugas yang diberikan.

_i=1Σ ³u_i = 20/100 + 30/150 + 60/200 = 0.7

Ini adalah kurang dari 1, sehingga kondisi yang diperlukan untuk schedulability tugas puas. Sekarang memeriksa kondisi kecukupan, set tugas yang schedulable bawah RMA jika kondisi Liu dan Layland yang diberikan oleh Expr. 3.4 puas Memeriksa kepuasan Expr. 3.4, pemanfaatan dicapai maksimum diberikan oleh:

3(2^1/3 − 1) = 0.78

Total utilisasi telah ditemukan untuk menjadi 0,7. Sekarang mengganti ini di Liu dan kriteria Layland ini:

Jika satu set tugas lulus uji Liu dan Layland, maka dijamin akan RMA schedulable. Di sisi lain, bahkan jika satu set tugas gagal tes Liu dan Layland, masih dapat RMA schedulable.

Memang benar bahwa bahkan ketika satu set tugas gagal tes Liu dan Layland, kita tidak harus menyimpulkan bahwa tidak schedulable bawah RMA. Kita perlu menguji lebih lanjut untuk memeriksa apakah set tugas RMA schedulable. Sebuah tes yang dapat per-dibentuk untuk memeriksa apakah suatu set tugas RMA schedulable ketika gagal tes Liu dan Layland adalah tes Lehoczky itu. Uji Lehoczky telah dinyatakan sebagai Teorema 3.

1.5.3. Theorem 3

Satu set periodik tugas real-time RMA schedulable bawah setiap tugas pentahapan, dari semua tugas memenuhi tenggat waktu masing-masing pertama mereka di bawah nol pentahapan.

Sebuah bukti formal Teorema ini adalah di luar cakupan diskusi ini. Namun, kami memberikan penalaran intuitif seperti mengapa Teorema 3 harus benar. Secara intuitif, kita dapat memahami hasil ini dari penalaran berikut. Pertama mari kita mencoba untuk memahami fakta berikut.

Yang terburuk waktu respon kasus untuk tugas terjadi bila dalam fase dengan yang lebih tinggi

Untuk melihat mengapa pernyataan ini pasti benar, menganggap pernyataan berikut. Di bawah RMA setiap kali tugas prioritas yang lebih tinggi siap, tugas prioritas yang lebih rendah tidak bisa mengeksekusi dan harus menunggu. Ini berarti bahwa, tugas prioritas yang lebih rendah akan harus menunggu untuk seluruh durasi pelaksanaan setiap tugas prioritas yang lebih tinggi yang timbul selama pelaksanaan tugas prioritas yang lebih rendah. Lebih banyak jumlah kasus dari tugas prioritas yang lebih tinggi akan terjadi, ketika tugas dalam fase dengan itu, bila dalam fase dengan itu daripada keluar dari fase dengan itu. Ini telah digambarkan melalui contoh sederhana pada Gambar. 30,4. Dalam Gambar. 30,4 (a), tugas prioritas yang lebih tinggi T1 = (10,30) dalam fase dengan tugas prioritas yang lebih rendah T2 = (60.120), waktu respon dari T2 adalah 90 msec. Namun, pada Gambar. 30,4 (b), ketika T1 memiliki 20 msec fase, waktu respon dari T2 menjadi 80. Oleh karena itu, jika tugas memenuhi tenggat waktu pertama di bawah nol pentahapan, maka mereka akan memenuhi semua tenggat waktu tersebut.

1.5.4. Achievable CPU Utilization

Liu dan hasil Layland ini (Expr. 3.4) dibatasi penggunaan CPU di bawah ini yang satu set tugas akan schedulable. Hal ini jelas dari Expr. 3.4 dan Gambar. 30.10 bahwa kriteria schedulability Liu dan Layland adalah konservatif dan membatasi pemanfaatan dicapai maksimal karena setiap set tugas yang dapat feasibly dijadwalkan bawah RMA 0,69 ketika jumlah tugas di set tugas besar. Namun, (seperti yang mungkin Anda sudah menebak) ini adalah tokoh pesimis. Bahkan, telah ditemukan bahwa eksperimen untuk koleksi besar tugas dengan periode independen, pemanfaatan maksimum di bawah ini yang satu set tugas dapat feasibly dijadwalkan pada rata-rata mendekati 88%.

Untuk tugas-tugas harmonik, pemanfaatan dicapai maksimum (untuk tugas diatur untuk memiliki jadwal feasible) masih bisa lebih tinggi. Bahkan, jika semua periode tugas yang harmonik berhubungan, maka bahkan satu set tugas yang memiliki utilisasi 100% dapat feasibly dijadwalkan. Mari kita memahami kapan periode satu set tugas dikatakan harmonik berhubungan. Periode tugas dalam satu set tugas dikatakan harmonik berhubungan, IFF untuk setiap dua tugas sewenang-wenang Ti dan Tk di set tugas, setiap kali pi> pk, harus menyiratkan bahwa pi merupakan multiple integral dari pk. Artinya, setiap kali pi> pk, itu harus mungkin untuk mengekspresikan pi sebagai n * pk untuk beberapa bilangan bulat n> 1. Dengan kata lain, harus tepat pk membagi pi. Sebuah contoh dari serangkaian tugas harmonis terkait adalah sebagai berikut: T1 = (5, 30), T2 = (8, 120), T3 = (12, 60).

1.5.5. Theorem 4

For a set of harmonically related tasks HS = {T_i}, the RMA schedulability criterion is given by _i=1Σ ⁿu_i ≤ 1.

Bukti: Mari kita asumsikan bahwa T1, T2, ..., Tn menjadi tugas dalam himpunan tugas. Mari kita lebih lanjut mengasumsikan bahwa tugas dalam tugas mengatur T1, T2, ..., Tn telah diatur dalam rangka meningkatkan periode mereka. Artinya, untuk setiap i dan j, pi <pj setiap kali i <j. Jika hubungan ini tidak puas, maka mengubah nama sederhana dari tugas dapat mencapai hal ini. Sekarang, menurut Expr. 3.6, tugas Ti memenuhi tenggat waktu,

if e_i + _k=1Σ ^i-1 ⎡p_i / p_k⎤ ∗ e_k ≤ p_i.

Namun, sejak set tugas yang harmonik berhubungan, pi dapat ditulis sebagai m * pk untuk beberapa m.

Using this, ⎡p_i / p_k⎤ = p_i / p_k. Now, Expr. 3.6 can be written as:

e_i + _k=1Σ ^i-1 (p_i / p_k)∗ e_k ≤ p_i

For T_i = T_n, we can write, e_n + _k=1Σ ^n-1 (p_n / p_k)∗ e_k ≤ p_n.

Dividing both sides of this expression by p_n, we get the required result.

Hence, the task set would be schedulable iff _k=1Σ ⁿ e_k / p_k ≤ 1 or _i=1Σ ⁿ u_i ≤ 1.

1.5.6. Advantages and Disadvantages of RMA

Pada bagian ini, pertama-tama kita membahas keuntungan penting dari RMA atas EDF. Kami kemudian menunjukkan beberapa kelemahan menggunakan RMA. Seperti yang kita telah dijelaskan sebelumnya, RMA sangat umum digunakan untuk penjadwalan tugas real-time dalam aplikasi praktis. Dukungan dasar yang tersedia di hampir semua sistem operasi komersial real-time untuk mengembangkan aplikasi menggunakan RMA. RMA sederhana dan efisien. RMA juga algoritma yang optimal statis prioritas tugas penjadwalan. Tidak seperti EDF, memerlukan sangat sedikit struktur data khusus. Sistem operasi real-time yang paling komersial mendukung tingkat prioritas real-time (statis) untuk tugas-tugas. Tugas yang memiliki tingkat prioritas real-time diatur dalam antrian umpan balik bertingkat (lihat Gambar. 30,7). Di antara tugas-tugas di tingkat satu, sistem operasi real-time komersial umumnya memberikan pilihan untuk waktu mengiris dan penjadwalan round-robin atau penjadwalan FIFO.

RMA Transient Penanganan Overload: RMA memiliki sementara kemampuan penanganan yang berlebihan baik. Baik sementara kemampuan penanganan yang berlebihan pada dasarnya berarti bahwa, ketika sebuah tugas prioritas yang lebih rendah tidak selesai dalam waktu penyelesaian yang direncanakan, tidak dapat membuat tugas prioritas yang lebih tinggi untuk melewatkan tenggat waktu. Mari kita memeriksa bagaimana kelebihan transien akan mempengaruhi satu set tugas yang dijadwalkan di bawah RMA. Apakah penundaan dalam penyelesaian oleh tugas prioritas yang lebih rendah mempengaruhi tugas prioritas yang lebih tinggi? Jawabannya adalah: 'Tidak'. Sebuah tugas prioritas yang lebih rendah bahkan ketika itu melebihi waktu eksekusi yang direncanakan tidak dapat membuat tugas prioritas yang lebih tinggi menunggu sesuai dengan prinsip-prinsip dasar RMA - setiap kali tugas prioritas yang lebih tinggi siap, preempts setiap melaksanakan tugas prioritas yang lebih rendah. Dengan demikian, RMA stabil di bawah berlebihan sementara dan prioritas yang lebih rendah tugas overshoot waktu penyelesaian yang tidak bisa membuat tugas prioritas yang lebih tinggi untuk melewatkan tenggat waktu.

Kelemahan dari RMA meliputi berikut ini: Hal ini sangat sulit untuk mendukung tugas-tugas aperiodik dan sporadis bawah RMA. Selanjutnya, RMA tidak optimal ketika periode tugas dan tenggat waktu berbeda.

1.6. Deadline Monotonic Algorithm (DMA)

RMA tidak ada lagi algoritma penjadwalan yang optimal untuk tugas real-time periodik, ketika tenggat waktu tugas dan periode berbeda (yaitu di ≠ pi) untuk beberapa tugas dalam tugas diatur untuk dijadwalkan. Untuk set tugas tersebut, Tenggat monotonik Algoritma (DMA) ternyata lebih mahir dibandingkan RMA. DMA pada dasarnya adalah sebuah varian dari RMA dan memberikan prioritas tugas berdasarkan tenggat waktu mereka, daripada prioritas menugaskan berdasarkan periode tugas seperti yang dilakukan di RMA. DMA memberikan prioritas yang lebih tinggi untuk tugas-tugas dengan tenggat waktu pendek. Ketika batas waktu relatif setiap tugas sebanding dengan periodenya, RMA dan DMA menghasilkan solusi yang identik. Ketika tenggat waktu relatif sewenang-wenang, DMA lebih mahir dibandingkan RMA dalam arti bahwa kadang-kadang dapat menghasilkan jadwal layak bila RMA gagal. Di sisi lain, RMA selalu gagal ketika DMA gagal. Kita sekarang menggambarkan diskusi kami menggunakan contoh tugas set yang DMA schedulable tetapi tidak RMA schedulable.

1.7. Context Switching Overhead

Sejauh ini, sementara menentukan schedulability satu set tugas, kita telah mengabaikan overhead yang dikeluarkan karena konteks switching. Mari kita sekarang meneliti efek dari konteks switching overhead pada schedulability tugas di bawah RMA.

Sangat mudah untuk menyadari bahwa dalam RMA, setiap kali tugas tiba, itu preempts paling banyak satu tugas - tugas yang sedang berjalan. Dari pengamatan ini, dapat disimpulkan bahwa dalam kasus terburuk, setiap tugas menimbulkan paling banyak dua konteks switch bawah RMA. Satu ketika preempts tugas yang sedang berjalan. Dan yang lain ketika itu selesai mungkin tugas yang mendahului atau beberapa tugas lain yang dikirim untuk menjalankan. Tentu saja, tugas mungkin dikenakan hanya satu switching konteks kepala, jika tidak mendahului tugas apapun. Misalnya, tiba saat prosesor idle atau saat tugas prioritas yang lebih tinggi berjalan. Namun, kita perlu mempertimbangkan dua switch konteks untuk setiap tugas, jika kita mencoba untuk menentukan terburuk konteks kepala switching.

Untuk kesederhanaan kita dapat mengasumsikan bahwa waktu beralih konteks konstan, dan sama milidetik 'c' dimana 'c' adalah sebuah konstanta. Dari hal ini, maka bahwa efek bersih dari konteks switch adalah untuk meningkatkan waktu eksekusi ei tugas masing-masing untuk Ti paling ei + 2 * c. Oleh karena itu jelas bahwa untuk mengambil konteks waktu beralih menjadi pertimbangan, dalam semua perhitungan schedulability, kita perlu mengganti ei ei oleh + 2 * c untuk setiap Ti.