Efficient Online Schedulability Tests for Real-Time Systems

Title
Efficient Online Schedulability Tests for Real-Time Systems
Authors
Tei-Wei Kuo, Li-Pin Chang, Yu-Hua Liu and Kwei-Jay Lin.
Abstract
Penjadwalanpengetesansistemtelahbanyakdiusulkansebelumnya.Akan tetapi, penjadwalanpengetesansistemtersebuttidakjarangmengalamikegagalan, terutamabilasistemsedangmenanganibeban yang berat.Makalahinimembahasmengenaipenjadwalanpengetesanuntuksistemonline yang lebihefisien.
Introduction
Dewasainiserverkomputerdengankemampuan real-time banyakdibutuhkangunaberbagaimacamkebutuhan, untukmendukungberbagaikeperluanseperti video conference, distant learning, hiburanonline, permainanonline, dan lain-lain.
Olehsebabitu, dibutuhkansuatupengetesanserver yang terjadwal agar serverkomputertersebutdapatberjalandenganmaksimal.
Telahbanyakdikembangkan model pengetesanserverdengansistempenjadwalan yang memilikikemampuan yang tidakdiragukan[1][2][3], akantetapiketepatanpengetesantersebutharusdibayardenganbanyaknyawaktu yang diperlukanuntukmengetessistem. Hal inikurangcocokterutamauntuksistemonlinedimanawaktuadalahunsurpenting yang tidakbisadiacuhkan.
Methods and Materials
Alokasisumberdayasecaraonlinesebelumnyapernahdibahasoleh Liu and Layland[4]denganmengenalkankonsepfaktorutilisasi (U), yaitudenganmengadakansuatupengetesancepat (quick test) untukmenentukanpenjadwalan proses periodikdenganwaktueksekusidanperiodetertentu.
Faktorutilisasitersebutdidefinisikansebagaiberikut :

Dimana c_i = kebutuhankomputasi
p_i = periode proses Ti
Penjadwalansejumlah n proses dijaminbilafaktorutilisasidari proses tersebuttidaklebihdari U, dimanaU(n) = n (2^1/n – 1) darialgoritma [4].
Akan tetapi, algoritma [4] gagaluntukmenangani proses yang banyak di-load di sistem.
Selainalgoritma [4] masihbanyakalgoritmalaindenganteknik-teknik yang berbeda yang diterapkandalampenjadwalanpengetesansistem. Namun, penjadwalantersebutdinilaikurangtepatkhususnyabilasistemsedangmengalamioverloaded.
Berikutadalahalgoritma yang diterapkandalamsistemini, khususnyauntuksistemuniprosesor :

Berikutadalahalgoritma yang diterapkanuntukpengetesansistemonlinedenganuniprosesor :

Langkah 1 dan 2 menurunkanjumlah root yang berkorespondensidanakumulasidariutilisasi CPU untuk proses-proses denganperiodetidaklebihdari p. Kemudian loop antaralangkah 5 dan 11 menurunkanjumlah root yang berkorespondensidanakumulasidariutilisasi CPU untuk proses-proses denganperiodetidaklebihdari p_i.
Sedangkanalgoritmauntukpenjadwalanpengetesansistemonlinedenganmultiframe :

Algoritmainihampirsamadenganalgoritmasebelumnya, yang berbedahanyapadaperlunya proses menjaganilai RSR-nya.
Results
Dari hasilpenelitiandiperolehhasilbahwauntuksistemuniprosesordiketahuibahwaadanyarasiojaminanmengenaipenjadwalanpengetesan yang lebihbaikdaripadaalgoritma-algoritma yang pernahdikemukakansebelumnya, terutamamenyangkutmasalahjumlahfrekuensikemunculan proses saatsistemsedangmengalamioverload.
Hasil yang samajugaditunjukkanpadaalgoritmapenjadwalanuntuksistemdenganmultiframe. Banyak proses yang berhasildiidentifikasiuntukdijadwalkanpengetesannyaberdasarpadaalgoritmapenjadwalan RMS.
Kesimpulanperbandinganpenjadwalantesdapatdilihatpadatabel di bawahini :

References
[1]   A.K. Mok and D. Chen, “A Multiframe Model for Real-Time Tasks,” IEEE Trans. Software Eng., 1997.
[2]   A. Burchard, J. Liebeherr, Y. Oh, and S.H. Son, “New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems,” IEEE Trans. Computers, 1995.
[3]   C.C. Han and H.Y. Tyan, “A Better Polynomial-Time Schedulability Test for Real-Time Fixed Priority Scheduling Algorithms,” Proc. IEEE 18th Real-Time Systems Symp., 1997.
[4]   C.L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” J. ACM, vol. 20, no. 1, 1973.