Pada bab terakhir kita mendefinisikan tugas real-time sebagai salah satu yang melibatkan beberapa konstrain waktu (time constraint) yang terkait di dalamnya. Kita akan membahas dari 3 tingkatan secara luas mengenai konstrain waktu, konstrain deadline pada serangkaian tugas adalah yang paling umum. Dari semua diskusi berikutnya maka kita secara implisit (terkandung didalamnya, tetapi tidak dinyatakan secara jelas) mengasumsikan hanya pada konstrain deadline pada serangkaian tugas real-time.
Tugas real-time bisa dihasilkan dalam menanggapi beberapa kejadian yang dapat berupa eksternal dan internal sistem. Misalnya, sebuah tugas mungkin bisa dihasilkan karena suatu kejadian internal seperti interupsi clock yang terjadi setiap beberapa milidetik untuk secara periodik mengontrol suhu sebuah pabrik kimia. Tugas lainnya mungkin bisa dihasilkan karena suatu kejadian eksternal seperti pengguna menekan tombol switch. Ketika tugas akan dihasilkan, menandakan tugas tersebut telah tiba atau dapat dirilis (dijalankan). Setiap sistem real-time biasanya terdiri dari sejumlah tugas-tugas real-time. Batas waktu pada tugas mungkin berbeda-beda. Kita sudah menunjukkan bahwa konsekuensi dari tugas yang kehilangan batas waktunya (melebihi deadline) juga dapat bervariasi dari satu tugas ke tugas yang lain. Hal ini sering dinyatakan sebagai kekritisan dari tugas.
Dalam bab terakhir, kami telah menunjukkan bahwa penjadwalan sesuai tugas adalah mekanisme dasar yang digunakan oleh sistem operasi real-time untuk mengatasi konstrain waktu (time constraint) dari sebuah tugas. Oleh karena itu, pemilihan algoritma penjadwalan tugas yang tepat adalah inti dari berfungsinya sistem real-time. Dalam Bab ini kita membahas beberapa dasar teknik penjadwalan tugas yang ada. Pemahaman tentang teknik ini akan membantu kita tidak hanya dalam merancang aplikasi real-time, tetapi juga memahami dan mengetahui fitur modern sistem operasi real-time komersial yang akan dibahas dalam bab-bab selanjutnya.
Bab ini disusun sebagai berikut. Pertama kali kami memperkenalkan beberapa konsep dasar dan istilah yang terkait dengan penjadwalan tugas. Selanjutnya, pada bagian pertama kita membahas penjadwal tugas menggunakan clock-driven.
1.1. Istilah-istilah Dasar
Pada bagian ini kami memperkenalkan beberapa konsep penting dan istilah yang akan berguna dalam memahami bab ini.
Task Instance
Setiap kali suatu kejadian terjadi, hal tersebut memicu suatu tugas yang menangani kejadian tersebut berjalan. Dengan kata lain, tugas dihasilkan ketika beberapa kejadian tertentu terjadi. Tugas real-time biasanya berulang beberapa kali pada saat waktu yang berbeda tergantung pada waktu terjadinya kejadian. Ada kemungkinan bahwa tugas real-time berulang pada saat yang acak (random). Namun, sebagian besar tugas real-time berulang dengan periode tetap tertentu. Misalnya, sebuah tugas pengontrolan suhu di pabrik kimia mungkin berulang tanpa batas dengan jangka waktu tertentu karena suhu ruangan tersebut dijadikan sampel secara berkala, sedangkan tugas penanganan interupsi perangkat mungkin berulang pada saat yang acak (random). Setiap kali tugas berulang, hal itu disebut instance dari tugas. Pertama kali tugas terjadi, hal itu disebut instance pertama dari tugas. Kejadian berikutnya pada tugas disebut instance kedua, dan seterusnya. Instance ke – j dari suatu tugas Ti akan dinyatakan sebagai Ti(j). Setiap instance dari tugas real-time dikaitkan dengan deadline dimana dibutuhkan untuk menyelesaikan dan menghasilkan suatu hasil.
Relative deadline dan Absolute deadline: absolute deadline tugas adalah nilai waktu yang absolut / mutlak (dihitung dari waktu 0) dimana hasil dari tugas yang diharapkan. Dengan demikian, absolute deadline sama dengan interval waktu antara 0 waktu dan saat sebenarnya di mana deadline terjadi diukur oleh beberapa jam fisik. Sedangkan relatif deadline adalah interval waktu antara awal tugas dan saat di mana deadline terjadi. Dengan kata lain, relatif deadline adalah interval waktu antara kedatangan tugas dan deadline yang sesuai. Response Time: waktu respon dari tugas adalah waktu yang dibutuhkan (yang diukur dari waktu kedatangan tugas) untuk tugas untuk menjalankan tugasnya. Seperti telah dikatakan, instance tugas dapat dihasilkan karena terjadinya kejadian. Kejadian ini mungkin dari internal sistem, seperti interupsi clock, atau eksternal sistem seperti robot menghadapi rintangan.
Waktu respon (waktu tanggap) adalah durasi waktu dari terjadinya kejadian yang menghasilkan tugas hingga tugas menyelesaikan tugasnya.
Task Precedence: Sebuah tugas bisa dikatakan mendahului tugas lain, jika tugas pertama harus selesai sebelum tugas kedua dapat dimulai. Ketika tugas Ti mendahului tugas Tj, maka setiap instance dari Ti mendahului instance Tj. Artinya, jika T1 mendahului T2, maka T1(1) mendahului T2(1), T1(2) mendahului T2(2), dan seterusnya. Contoh parsial order antara tugas ditunjukkan pada Gambar. 29.2. Contoh berikut ini T1 mendahului T2, tapi kita tidak dapat menghubungkan T1 dengan T3 atau T4. Kita kemudian akan menggunakan tugas prioritas relasi (precedence relation) ini dengan mengembangkan algoritma penjadwalan tugas yang sesuai.
Data Sharing: Suatu tugas berbagi data antara tugas satu dengan yang lain ketika salah satu tugas membutuhkan berbagi data yang dihasilkan oleh tugas lain, dengan jelas, tugas kedua harus mendahului tugas pertama. Bahkan, relasi antara dua tugas terkadang menunjukkan berbagi data antara dua tugas (misalnya tugas pertama melewati beberapa hasil hingga tugas kedua). Namun, hal ini tidak selalu benar. Sebuah tugas dimungkinkan untuk mendahului tugas yang lain bahkan ketika tidak ada berbagi data. Misalnya, dalam sebuah
pabrik kimia mungkin diperlukan bahwa ruangan reaksi harus diisi dengan air sebelum bahan kimia diperbolehkan.
Dalam kasus ini, penanganan tugas pengisian ruang reaksi dengan air harus diselesaikan, sebelum pengenalan penanganan tugas bahan kimia diaktifkan. Oleh karena itu tidaklah tepat untuk menunjukkan berbagi data menggunakan prioritas relasi (precedence relation). Selanjutnya, berbagi data dapat terjadi tidak hanya ketika satu tugas mendahului tugas yang lain, tetapi mungkin terjadi antar tugas-tugas yang benar-benar bersamaan, dan tugas yang saling tumpang tindih. Dengan kata lain, berbagi data antara tugas tidak selalu melakukan parsial order antar tugas. Karena itu, hubungan sharing data antara tugas-tugas harus ditunjukkan menggunakan simbol yang berbeda. Kita akan menunjukkan sharing data antara dua tugas menggunakan panah putus-putus. Dalam contoh sharing data antara tugas ditunjukkan pada Gambar. 29.2, T2 menggunakan data T3, tetapi T2 dan T3 mungkin dapat dieksekusi secara bersamaan. T2 mungkin dapat mulai dijalankan pertama, setelah menerima beberapa data dari T3, dan melanjutkan eksekusinya, dan seterusnya.
1.2. Tipe-tipe Tugas Real-time
Berdasarkan cara tugas real-time tersebut berulang selama periode waktu, hal ini memungkinkan untuk mengklasifikasikannya menjadi tiga kategori utama: tugas periodik (tetap), sporadis (random), dan aperiodik (tidak berulang secara berkala). Berikut ini, kita membahas karakteristik penting dari ketiga kategori utama dari tugas real-time.
Tugas Periodik (Periodic Task): Sebuah tugas periodik adalah salah satu yang berulang setelah interval waktu tetap tertentu. Waktu yang tepat di mana tugas periodik berulang biasanya dibatasi oleh clock interupsi. Untuk alasan ini, periodic task kadang-kadang disebut sebagai tugas clock-driven. Interval waktu yang tetap setelah tugas berulang disebut periode tugas. Jika Ti adalah tugas periodik (periodic task), maka waktu dari 0 sampai terjadinya instance pertama dari Ti (yaitu Ti(1)) dinotasikan dengan φi, dan disebut fase tugas. Instance kedua (yaitu Ti(2)) terjadi pada φi + pi. Instance ketiga (yaitu Ti(3)) terjadi pada φi + 2*pi dan seterusnya. Secara formal, periodic task Ti dapat digambarkan oleh 4 tuple (φi, pi, ei, di) mana pi adalah periode tugas, ei adalah worst case dari waktu eksekusi tugas (execution time), dan di adalah relatif deadline dari tugas.
Gambar 29.3. Tugas Monitoring Koreksi (2000 msec; pi; ei; di) dari sebuah roket
Untuk menjelaskan notasi di atas yang menggambarkan tugas periodik real-time, mari kita perhatikan tugas monitoring koreksi yang biasanya ditemukan dalam software untuk mengontrol roket. Asumsikan karakteristik dari tugas monitoring koreksi sebagai berikut. Tugas monitoring koreksi dimulai 2000 milidetik setelah peluncuran roket, dan kemudian berulang secara periodik setiap 50 milidetik. Setiap instance dari tugas membutuhkan waktu pemrosesan 8 milidetik dan relatif deadline-nya adalah 50 milidetik. Ingat kembali bahwa fase tugas didefinisikan pada saat terjadinya instance pertama dari tugas. Oleh karena itu, fase tugas ini adalah 2000 milidetik. Tugas ini secara formal dapat direpresentasikan sebagai (2000 msec, 50 msec, 8 msec, 50 msec). Tugas ini ditunjukkan pada Gambar. 29.3. Ketika deadline dari tugas sama dengan periode (yaitu pi = di), kita dapat menghilangkan tupel (nilai) keempat. Pada contoh ini, kita bisa menunjukkan tugas Ti = (2000 msec, 50 msec, 8 msec). Ini berarti pi = di = 50 msec. Demikian pula, ketika φi = 0, dapat juga dihilangkan penulisannya. Jadi, Ti = (20mSec; 100msec) akan menunjukkan sebuah tugas dengan φi = 0, pi = 100msec, ei = 20mSec, dan di = 100msec. Agar tidak terjadi kebingungan, kita dapat secara eksplisit (jelas) menulis parameter Ti = (pi = 50 msecs, ei = 8 msecs, di = 40 msecs), dll.
Sebagian besar dari tugas-tugas yang ditunjukkan dalam sistem real-time adalah secara periodik. Alasannya adalah bahwa banyak kegiatan yang dilakukan oleh sistem real-time yang periodik, misalnya memantau kondisi tertentu, menentukan informasi dari sensor pada interval waktu melakukan tindakan tertentu secara teratur (seperti mengerakkan beberapa aktuator (guna aktuator utk menggerakkan atau mengontrol sebuah mekanisme atau sistem)). Kita akan melihat contoh dari tugas-tugas seperti yang ditemukan di sebuah pabrik kimia. Dalam sebuah pabrik kimia beberapa memonitor suhu, memonitor tekanan, dan konsentrasi
kimia memonitor secara berkala sampel suhu saat ini, tekanan, dan nilai-nilai konsentrasi bahan kimia yang kemudian dikomunikasikan ke pengontrol. Contoh dari suhu, tekanan, dan tugas-tugas pemantauan konsentrasi kimia biasanya bisa dihasilkan melalui interupsi yang diterima dari timer periodik. Input ini digunakan untuk menghitung tindakan korektif yang dilakukan melalui aktuator.
Tugas Sporadik (Sporadic Task): Sebuah tugas sporadis adalah salah satu yang berulang pada saat yang acak (random). Sebuah tugas sporadis Ti dapat ditunjukkan oleh tiga tuple:
Ti = (ei, gi, di)
dimana ei adalah worst case dari waktu eksekusi sebuah instance dari tugas, gi menunjukkan pemisahan minimum antara dua instance dari tugas, di adalah deadline relatif. Pemisahan minimum (gi) antara dua instance dari tugas berarti bahwa saat instance dari tugas sporadis terjadi, instance berikutnya tidak bisa terjadi sebelum waktu unit gi sudah berlalu. Artinya, gi membatasi tingkat di mana tugas-tugas sporadis bisa muncul. Seperti yang dilakukan untuk tugas-tugas periodik, kita dapat menggunakan pernyataan bahwa instance pertama dari Ti tugas sporadis dinotasikan dengan Ti(1), Ti(2), Ti(3), dll.
Banyak tugas sporadis seperti kedatangan pesan yang bersifat darurat hal ini merupakan high kritikal (sangat kritis). Misalnya, dalam sebuah robot terdapat sebuah tugas yang dihasilkan untuk menangani rintangan yang tiba-tiba muncul ini merupakan tugas sporadis. Di sebuah pabrik, tugas yang menangani kondisi kebakaran ini merupakan tugas sporadis. Waktu terjadinya tugas tersebut tidak dapat diprediksi.
Tugas Aperiodik (Aperiodic Task): Sebuah tugas aperiodik dalam banyak hal mirip dengan tugas sporadis. Sebuah tugas aperiodik dapat muncul pada waktu yang acak (random). Namun, contoh pada tugas aperiodik, pemisah minimum gi antara dua instance dapat menjadi 0. Artinya, dua atau lebih instance (kejadian) tugas aperiodik mungkin terjadi pada saat yang bersamaan. Dan juga, deadline untuk tugas-tugas aperiodik dinyatakan sebagai nilai rata-rata atau dinyatakan secara statistik. Tugas aperiodik umumnya merupakan tugas soft real-time.
Sangat mudah untuk menyadari mengapa tugas aperiodik merupakan tugas soft real-time. Tugas aperiodik dapat berulang secara berurutan. Karena itu menjadi sangat sulit untuk memenuhi deadline dari semua instance (kejadian) tugas aperiodik. Ketika beberapa tugas aperiodik berulang secara berurutan, terdapat serangkaian instance tugas dan mungkin menyebabkan beberapa deadline terlewatkan / meleset. Seperti yang sudah dibahas, tugas soft real-time memiliki toleransi terhadap beberapa deadline yang terlewatkan/meleset. Contoh
dari tugas aperiodik adalah tugas logging (pencatatan) dalam sistem terdistribusi. Tugas logging dapat dimulai dengan tugas yang berbeda pada node yang berbeda. Permintaan logging dari tugas yang berbeda mungkin tiba di logger (pencatat) hampir pada saat yang sama, atau permintaan dapat diberi jarak waktu. Contoh lain dari tugas aperiodik mencakup permintaan operator, menekan Keyboard, gerakan mouse, dll. Bahkan, semua perintah interaktif yang dikeluarkan oleh pengguna ditangani oleh tugas aperiodik.
1.3. Task Scheduling
Penjadwalan tugas real-time pada dasarnya untuk menentukan urutan di mana berbagai tugas yang harus diambil untuk dieksekusi/dijalankan oleh sistem operasi. Setiap sistem operasi menggunakan satu atau lebih penjadwalan tugas untuk mempersiapkan jadwal eksekusi berbagai tugas yang dibutuhkan untuk dijalankan. Setiap tugas penjadwalan ditandai oleh algoritma penjadwalan yang mengaturnya.
1.3.1. Beberapa Konsep Dasar
Sebelum fokus pada pembahasan mengenai penjadwalan lebih jauh, kita akan mengenal beberapa konsep-konsep penting dan istilah-istilah yang akan digunakan pada pembelajaran selanjutnya.
Valid Schedule: Sebuah jadwal yang valid pada serangkaian tugas adalah sebanyak-banyaknya satu tugas ditugaskan untuk sebuah prosesor pada satu waktu, tidak ada tugas yang dijadwalkan sebelum waktu rilisnya (release time), dan precendence (prioritas tugas) dan konstrain resource dari semua tugas terpenuhi.
Feasible Schedule: Sebuah jadwal yang valid disebut jadwal yang feasible (layak), hanya jika serangkaian tugas memenuhi masing-masing konstrain waktu (deadline) dalam jadwal tersebut.
Proficient Scheduler: Sebuah penjadwal tugas sch1 dikatakan lebih mahir dibandingkan penjadwal sch2, jika penjadwal sch1 dapat menjadwalkan secara feasible (layak) serangkaian tugas sehingga penjadwal sch2 dapat menjadwalkan secara feasible (layak), namun tidak sebaliknya. Artinya, penjadwal sch1 dapat menjadwalkan secara feasible (layak) serangkaian tugas sehingga penjadwal sch2 bisa, tetapi setidaknya ada satu tugas penjadwal sch2 yang bukan merupakan jadwal yang feasible (layak), sedangkan penjadwal sch1 bisa. Jika penjadwal sch1 dapat menjadwalkan secara feasible (layak) serangkaian tugas sehingga penjadwal sch2 dapat menjadwalkan secara feasible (layak) dan sebaliknya, maka penjadwal sch1 dan penjadwal sch2 disebut penjadwal yang sama mahir (equally proficient schedulers).
Optimal Scheduler: Penjadwal tugas real time dikatakan optimal, jika penjadwal tersebut dapat menjadwalkan secara feasible (layak) serangkaian tugas apapun sehingga dapat secara feasible (layak) dijadwalkan oleh penjadwal apapun. Dengan kata lain, tidak akan mungkin menemukan algoritma penjadwalan yang lebih mahir (proficient) dari optimal scheduler (penjadwal yang optimal). Jika optimal scheduler (penjadwal yang optimal) tidak dapat menjadwalkan beberapa tugas, maka penjadwal lainnya tidak mampu menghasilkan jadwal yang feasible (layak) untuk serangkaian tugas.
Scheduling Points: Titik penjadwalan pada scheduler (penjadwal) adalah titik pada garis waktu di mana penjadwal membuat keputusan mengenai mana tugas yang akan dijalankan berikutnya. Penting untuk diperhatikan bahwa penjadwal tugas tidak perlu berjalan terus-menerus, penjadwal tersebut diaktifkan oleh sistem operasi hanya pada titik-titik penjadwalan untuk penjadwalan membuat keputusan tugas mana yang akan dijalankan berikutnya. Dalam penjadwal clock-driven, titik penjadwalan didefinisikan pada waktu yang ditandai dengan interupsi yang dihasilkan oleh timer periodik. Titik penjadwalan dalam event-driven ditentukan oleh terjadinya kejadian tertentu.
Preemptive Scheduler: Sebuah penjadwal preemptive adalah salah satu penjadwal yang ketika sebuah tugas dengan prioritas yang lebih tinggi tiba, maka akan menunda semua tugas dengan prioritas yang lebih rendah yang kemudian mengeksekusi dan mengambil tugas prioritas yang lebih tinggi untuk dieksekusi.
Utilization (pemanfaatan): Utilisasi prosesor (simple utilisasi) dari sebuah tugas adalah rata-rata waktu yang dijalankan per satuan interval waktu. Dalam notasi: untuk tugas periodik Ti, utilisasi ui = ei / pi, dimana ei adalah waktu eksekusi (execution time) dan pi adalah periode waktu Ti. Untuk serangkaian tugas periodik {Ti}: total utilisasi pada semua tugas Σ .
Jitter: Jitter adalah deviasi (penyimpangan) tugas periodik dari perilaku ketepatan periodik-nya. Waktu kedatangan jitter merupakan deviasi (peyimpangan) dari datangnya tugas pada waktu kedatangan periodik. Hal ini mungkin disebabkan oleh clock yang tidak tepat, atau faktor lain seperti gangguan jaringan. Demikian pula, waktu penyelesaian jitter merupakan deviasi (penyimpangan) penyelesaian tugas dari titik-titik periodik. Waktu penyelesaian jitter mungkin disebabkan algoritma penjadwalan khusus yang diterapkan yang memakan waktu sampai sebuah tugas menjadwalkan dan muatan pada suatu saat.
1.4. Klasifikasi Algoritma Penjadwalan Tugas Real Time
Beberapa skema klasifikasi algoritma penjadwalan tugas real time yang ada. Sebuah skema yang populer mengklasifikasikan algoritma penjadwalan tugas real time berdasarkan bagaimana titik-titik penjadwalan didefinisikan. Tiga jenis yang utama penjadwal menurut skema klasifikasifikasi ini adalah: clock-driven, event-driven, dan hybrid.
Penjadwal clock-driven adalah di mana titik-titik penjadwalannya ditentukan oleh iterupsi yang di terima dari clock. Pada event-driven, titik-titik penjadwalan didefinisikan oleh kejadian tertentu yang menghindarkan interupsi clock. Pada hybrid menggunakan interupsi clock dan juga terjadinya kejadian untuk menentukan titik-titik penjadwalannya.
Beberapa bagian-bagian penting dari masing-masing tigas kelas algoritma penjadwalan sebagai berikut:
1. Clock-driven
- Table-driven
- Cyclic
- Simple priority-basedRate
- Monotonic Analysis (RMA)
- Earliest Deadline First (EDF)
Bagian penting dari penjadwal clock-driven yang akan kita diskusikan kali ini adalah table-driven dan penjadwal cyclic. Penjadwal clock-driven adalah penjadwal yang sederhana dan efisien.
Contoh penting dari penjadwal event-driven adalah Earliest Deadline First (EDF) dan Rate Monotonic Analysis (RMA). Penjadwal event-driven lebih canggih dari penjadwal clock-driven dan biasanya lebih mahir dan fleksibel dari clock-driven. Lebih mahir karena penjadwal-penjadwal tersebut dapat menjadwalkan secara feasible (layak) beberapa tugas yang penjadwal clock-driven tidak bisa lakukan. Lebih fleksibel karena penjadwal-penjadwal tersebut dapat menjadwalkan secara feasible (layak) tugas sporadik dan aperiodik selain untuk tugas periodik, sedangkan penjadwal clock-driven hanya dapat menangani pada tugas periodik. Penjadwalan event-driven tugas real time pada sebuah lingkup uniprosesor merupakan bahan penelitian selama awal tahun 1970-an. Dari sejumlah besar hasil penelitian yang telah dipublikasikan, berikut dua algoritma yang populer: Earliest Deadline First (EDF)
dan Rate Monotonic Analysis (RMA). Jika kita mengerti dua algoritma penjadwalan ini dengan baik, kita akan mengerti penjadwalan tugas real time pada uniprosesor. Beberapa variasi dari dua algoritma dasar ini.
Klasifikasi yang lainnya dari algoritma penjadwalan tugas real time dapat dibuat berdasarkan uji penerimaan tugas yang penjadwal lakukan sebelum menentukan tugas yang akan dijadwalkan. Uji penerimaan digunakan untuk memutuskan apakah tugas yang baru saja tiba akan diambil untuk dilakukan penjadwalan atau ditolak. Berdasarkan uji penerimaan yang digunakan, terdapat dua kategori tugas penjadwal:
- Planning-based
- Best Effort
Tiga jenis klasifikasi tugas real time berdasarkan platform dimana tugas akan dijalankan. Perbedaan kelas algoritma penjadwalan menurut skema ini adalah:
- Uniprosesor
- Multiprosesor
- Terdistribusi
dalam merancang algoritma terdistribusi yang biasanya dianggap cocok untuk digunakan di sistem terdistribusi.
1.5. Penjadwalan Clock-driven
Penjadwal clock-driven membuat keputusan penjadwalannya terkait tugas yang akan dijalankan berikutnya hanya pada titik-titik interupsi clock. Pada penjadwal clock-driven titik-titik penjadwalannya ditentukan oleh interupsi clock. Penjadwal clock-driven disebut juga penjadwalan offline karena penjadwal menentukan penjadwalan sebelum sistem dijalankan. Artinya, penjadwal ditentukan sebelum tugas mana yang akan dijalankan. Oleh karena itu, penjadwal ini sangat sedikit menyebabkan run time overhead. Namun, kekurangan yang menonjol dari kelas penjadwal ini adalah penjadwal tersebut tidak bisa menangani tugas aperiodik dan sporadik karena waktu terjadinya tugas-tugas tersebut tidak dapat di prediksi. Karena alasan ini, penjadwal jenis ini disebut penjadwal statik.
Pada bagian ini, kita akan mempelajari fitur dasar dari dua hal penting penjadwal clock-driven: table-driven dan penjadwal cyclic.
1.5.1. Penjadwalan Table-driven
Penjadwal table-driven biasanya dihitung sebelum tugas akan dijalankan, dan menyimpan jadwal di dalam sebuah tabel pada saat sistem ini dirancang atau dikonfigurasikan. Daripada perhitungan secara otomatis jadwal dilakukan oleh penjadwal, program aplikasi dapat diberi kebebasan untuk memilih jadwal yang diinginkan untuk mengatur tugas di dalam aplikasi dan menyimpan jadwal di dalam sebuah tabel (table schedule) yang digunakan penjadwal saat run time.
Contoh dari penjadwalan menggunakan tabel ditunjukkan pada Tabel 1. Tabel 1 menunjukkan bahwa tugas T1 akan diambil untuk dijalankan waktu ke 0, T2 akan mulai dijalankan 3 milidetik setelahnya, dan seterusnya. Pertanyaan penting yang perlu diperhatikan adalah apa yang akan menjadi ukuran tabel jadwal yang diperlukan untuk beberapa kumpulan tugas periodik real time untuk dijalankan pada sebuah sistem? jawabannya dapat ditunjukkan sebagai berikut: jika satu set ST = {Ti} dari n tugas yang akan dijadwalkan, maka entri di dalam tabel akan mereplikasi diri setelah LCM (p1,p2,...,pn) unit waktu, dimana p1, p2, ..., pn adalah periode dari T1, T2, ..., Tn. Sebagai contoh, jika kita memiliki 3 tugas: (e1=5 msec, p1=20 msec), (e2=20 msec, p2=100 msec), (e3=30 msec, p3=250 msec), maka jadwal akan di ulang setiap 1000 msec. Jadi, untuk set tugas apapun, hal tersebut sudah cukup untuk
menyimpan entri hanya untuk LCM (p1, p2, ..., pn) durasi di dalam tabel jadwal. LCM (p1, p2, ...,pn) disebut major cycle dari satu set tugas ST.
Major cycle dari serangkaian tugas adalah interval waktu pada garis waktu sehingga pada setiap major circle, tugas yang berbeda terjadi secara identik.
Dari penjelasan yang kita tunjukkan diatas untuk perhitungan ukuran tabel jadwal, kita berasumsi bahwa φi = 0. Artinya, semua tugas berada di dalam fase.
Tabel 29.1. Contoh dari penjadwalan tabel-driven
1.5.2. Penjadwal Cyclic
Penjadwalan cyclic sangat populer dan sedang banyak digunakan dalam industri. Sebagian besar dari semua aplikasi sederhana embedded yang diproduksi sekarang ini didasarkan pada penjadwal cyclic. Penjadwal cyclic adalah penjadwal yang sederhana, efisien, dan mudah untuk program. Sebuah contoh aplikasi di mana scheduler cyclic biasanya digunakan adalah pengontrol suhu. Suhu mengontrol secara periodik dari sebuah ruangan dan menjaga agar tetap pada suhu tersebut. Pengendali suhu tersebut tertanam biasanya di dalam komputer untuk mengendalikan air conditioner.
Gambar 29.4. Major dan Minor Cycle pada penjadwal Cyclic.
Penjadwal cyclic mengulangi jadwal yang telah di hitung sebelumnya. Jadwal yang telah dihitung sebelumnya di simpan hanya untuk major cycle. Setiap serangkaian tugas dijadwalkan berulang secara identik dalam setiap major cycle. Major cycle dibagi ke dalam satu atau lebih minor cycle (lihat gambar 29.4). Setiap minor cycle terkadang disebut sebuah
frame. Pada contoh yang ditunjukkan pada gambar 29.4, major cycle telah dibagi-bagi ke dalam 4 minor cycle (frame). Titik-titik penjadwalan dari penjadwal cyclic terjadi pada batasan frame. Ini artinya bahwa tugas dapat mulai dijalankan hanya pada awal sebuah frame.
Batas frame didefinisikan melalui interupsi yang dihasilkan oleh timer periodik. Setiap tugas ditetapkan untuk jalan dalam satu atau lebih frame. Penentuan tugas pada frame disimpan pada tabel jadwal. Ukuran frame yang digunakan oleh penjadwal adalah parameter desain yang penting dan harus dipilih dengan cermat. Ukuran frame yang dipilih harus memenuhi tiga konstrain berikut.
1. Minimum Context Switching: Konstrain ini diberlakukan untuk meminimalkan jumlah dari konteks switch yang terjadi selama tugas dijalankan. Pemahaman sederhana dari konstrain ini adalah bahwa instance tugas harus menjalankan sampai selesai dalam frame yang ditetapkan. Kecuali tugas diselesaikan dalam frame yang dialokasikannya, tugas mungkin harus ditunda dan dimulai lagi pada frame berikutnya. Hal ini akan membutuhkan konteks switch yang melibatkan beberapa overhead pemrosesan. Untuk menghindari konteks switch yang tidak perlu, ukuran frame yang dipilih harus lebih besar dari waktu eksekusi setiap tugas, sehingga ketika tugas dimulai pada batas frame tersebut harus mampu menyelesaikan dalam frame yang sama. Secara formal, kita dapat menyatakan kondisi ini sebagai: max({ei}) < F dimana ei adalah waktu eksekusi dari tugas Ti, dan F adalah ukuran frame. Perhatikan bahwa konstrain ini membebandkan pada batas terendah pada ukuran frame, yaitu ukuran frame F harus tidak lebih kecil dari max({ei}).
2. Meminimalkan ukuran tabel: Kontrain ini mengharuskan jumlah entri pada tabel jadwal harus minimum, guna meminimalkan kebutuhan penyimpanan tabel jadwal. Ingat bahwa penjadwal cyclic digunakan pada aplikasi sederhana embedded dengan kapasitas penyimpanan yang sangat kecil. Jadi, konstrain ini adalah hal penting untuk keberhasilan suatu produk. Jumlah entri yang disimpan pada tabel jadwal dapat diminimalkan ketika
minor cycle terbagi sesuai dengan major circle. Ketika minor cycle terbagi sesuai dengan major circle, major circle berisi jumlah integral minor circle (tidak ada minor circle pecahan). Kecuali jika minor cycle terbagi sesuai dengan major circle, penyimpanan jadwal untuk satu major circle tidak akan cukup, karena jadwal dalam major circle tidak akan mengulangi dan ini akan membuat ukuran tabel menjadi besar. Kita dapat merumuskan konstrain ini sebagai berikut:
[ M/F ] = M/F (2.1)
Dengan kata lain, jika pangkat M/F sama dengan M/F, maka major circle akan berisi jumlah integral frame.
3. Pemenuhan dari Deadline Tugas: Konstrain pada ukuran frame diperlukan untuk memenuhi deadline tugas. Kendala ini mensyaratkan antara kedatangan tugas dan deadlinenya, harus ada setidaknya satu full frame. Konstrain ini diperlukan karena tugas seharusnya tidak melebihi deadlinenya, karena bisa digunakan untuk penjadwalan, yang deadlinenya sudah dekat. Petimbangkan hal ini: sebuah tugas hanya dapat diambil untuk penjadwalan pada awal frame. Jika antara kedatangan sampai tugas diselesaikan, bahkan tidak satu frame ada, seperti yang ditunjukkan pada gambar 29.6. Pada kasus seperti ini, tugas tiba terkadang setelah frame ke-(k) dan hanya diambil pada frame ke-(k+1). Tetapi, kemudian mungkin terlambat untuk memenuhi deadlinenya karena waktu eksekusi tugas dapat sampai ukuran full frame. Ini mungkin hasil pada tugas yang melebihi deadlinenya karena tugas diselesaikan hanya pada akhir frame ke-(k+1) setelah deadline (d) telah berlalu. Karena itu kita membutuhkan full frame ada diantara kedatangan tugas sampai deadlinenya seperti yang ditunjukkan pada gambar 29.7, sehingga deadline tugas dapat terpenuhi.
Gambar 29.7. Full frame berada diantara Kedatangan dan Deadline Tugas.
1.5.3. Generalisasi dari Penjadwal Tugas
Kita telah menyatakan bahwa penjadwal cyclic adalah yang sangat populer pada aplikasi real time dengan biaya murah. Namun, diskusi kita pada penjadwal cyclic sejauh ini terbatas pada penjadwalan tugas real time secara periodik. Di sisi lain, banyak aplikasi praktis biasanya terdiri dari penggabungan beberapa tugas periodik, aperiodik, dan sporadik. Pada bagian ini, kita membahas bagaimana tugas aperiodik dan sporadik dapat diterapkan pada penjadwal cyclic.
Ingatlah bahwa waktu kedatangan tugas aperiodik dan sporadik dinyatakan secara statik. Oleh karena itu, tidak ada cara untuk menetapkan tugas aperiodik dan sporadik pada frame tanpa secara signifikan menurunkan utilisasi yang bisa dicapai keseluruhan sistem. Penjadwal secara umum, pada awalnya sebuah jadwal (penetapan tugas pada frame) hanya untuk tugas periodik. Tugas sporadik dan aperiodik dijadwalkan pada waktu slack yang dimungkinkan terjadi pada frame. Waktu slack pada frame adalah waktu yang tersisa setelah tugas periodik dialokasikan pada frame untuk menyelesaikan eksekusinya. Waktu slack non-zero pada frame dapat ada hanya ketika waktu eksekusi tugas yang dialokasikan lebih kecil dari ukuran frame.
Tugas sproradik digunakan pada penjadwalan hanya jika waktu slack yang tersedia untuk tugas sporadik menyelesaikan sebelum deadlinenya. Oleh karena itu, tugas sporadik pada kedatangannya dilakukan uji penerimaan. Pemeriksaan uji penerimaan apakah kemungkinan tugas selesai pada deadlinenya ketika dijalankan pada waktu slack yang tersedia. Jika hal ini tidak mungkin memenuhi deadline tugasnya, maka penjadwal ditolak dan recovery routine tugas dijalankan. Karena tugas aperiodik tidak memiliki deadline yang ketat, tugas tersebut dapat mengambil penjadwalan tanpa uji penerimaan dan best effort dapat membuat jadwal
tugas tersebut pada waktu slack. Meskipun pada tugas aperiodik tidak ada uji penerimaan yang dilakukan, tetapi tidak ada jaminan yang diberikan waktu penyelesaian tugas dan best effort dibuat untuk menyelesaikan tugas seawal mungkin.
Implementasi yang efisien dari penggunaan skema ini adalah bahwa waktu slack disimpan pada tabel dan selama uji penerimaan tabel ini digunakan untuk memeriksa penjadwalan dari kedatangan tugas.
Alternatif lain yang populer adalah bahwa tugas aperiodik dan sporadik diterima tanpa uji penerimaan, dan best effort dibuat untuk memenuhi masing-masing deadline.
Pseduocode Generalized Scheduler: berikut pseduocode untuk penjadwal cyclic yang umum digunakan, dimana untuk penjadwal tugas periodik, aperiodik, dan sporadik. Hal ini diasumsikan bahwa jadwal precomputed dari periodik disimpan pada sebuah tabel, dan jika dibutuhkan tugas-tugas sporadik telah dilakukan uji penerimaan dan hanya yang telah dilakukan uji penerimaan yang tersedia untuk penjadwalan.
cyclic-scheduler() {
current-task T = Schedule-Table[k];
k = k + 1;
k = k mod N; //N is the total number of tasks in the schedule table
dispatch-current-task(T);
schedule-sporadic-tasks(); //Current task T completed early,
// sporadic tasks can be taken up
schedule-aperiodic-tasks(); //At the end of the frame, the running task
// is pre-empted if not complete
idle(); //No task to run, idle
}
Pada penjadwal cyclic routin cyclic-scheduler ( ) diaktifkan pada akhir setiap frame oleh timer periodik. Jika tugas saat ini tidak selesai pada akhir frame, maka akan ditangguhkan dan tugas yang akan dijalankan dalam frame berikutnya yang dikirim dengan menerapkan routin cyclic-scheduler ( ). Jika tugas yang dijadwalkan dalam frame selesai lebih awal, maka setiap tugas sporadis atau aperiodik yang ada diambil untuk eksekusi.
1.5.3. Perbandingan Penjadwalan cyclic dengan Penjadwalan Tabel – Driven
Kedua penjadwalan table-driven dan penjadwal cyclic sangat penting dalam clock- driven. Sebuah penjadwal membutuhkan pengaturan timer periodik hanya sekali pada saat inisialisasi aplikasinya. Timer ini terus memberikan interupsi di setiap batasan frame. Tapi dalam penjadwalan tabel-driven, timer harus diatur setiap kali tugas mulai berjalan. Waktu eksekusi tugas real-time biasanya berurut beberapa milidetik. Oleh karena itu, pemanggilan timer dibuat setiap beberapa detik. Hal ini merupakan overhead yang signifikan dan hasil menurunkan kinerja sistem. Oleh karena itu, penjadwal cyclic lebih efisien daripada penjadwalan tabel-driven.
Ini mungkin adalah alasan mengapa penjadwal cyclic begitu sangat populer terutama dalam aplikasi embedded. Namun, jika overhead dalam mengatur timer diabaikan, penjadwalan table-driven lebih bagus daripada penjadwalan cylic karena ukuran frame yang perlu dipilih harus setidaknya asalkan ukuran waktu eksekusi terbesar tugas pada serangkaian tugas. Hal ini adalah tidak efisien, karena hasil dari waktu prosesor yang terbuang dalam kasus ini tugas-tugas yang waktu eksekusinya lebih kecil dari ukuran frame yang dipilih.
Tidak ada komentar:
Posting Komentar