Algoritma Penjadwalan pada Tinyos Yusuf Syaifudin
[email protected] Program Studi Ilmu Komputer, Jurusan Ilmu Komputer dan Elektronika Universitas Gadjah Mada April 1, 2014 Abstract TinyOS [1] merupakan sistem operasi tertanam yang ditujukan untuk perangkat dengan mobilitas tinggi yang memiliki daya rendah. Pada dasarnya, TinyOS merupakan sebuah sistem penjadwalan kerja dan sekumpulan koleksi driver untuk mikrokontroller dan IC (Integrated Circuit) yang digunakan secara umum pada perangkat wireless. Makalah ini akan membahas mengenai manajemen penjadwalan pada TinyOS, yaitu mengenai bagaimana sistem operasi ini menangani dan menyelesaikan runtutan proses yang diminta oleh pengguna. Kata kunci: TinyOS, manajemen penjadwalan, proses
1
Pendahuluan
Sistem operasi merupakan seperangkat program yang menjembatani antara hardware dan software. Silberschatz dan Galvin (1998) [2] mendefinisikan sistem operasi yang terbagi atas: • Resource allocator yaitu bagian dari sistem operasi yang memanajemen dan mengalokasikan resources. • Control program merupakan bagian yang mengontrol eksekusi dari program yang dijalankan pengguna dan operasi dari perangkat I/O (input dan output). • Kernel merupakan program yang selalu berjalan setiap saat. Disebutkan diatas bahwa salah satu definisi dari sistem operasi ialah melakukan kontrol eksekusi program. Untuk itu, bagaimanapun dan dimanapun lingkungan sistem operasi berada, untuk dapat disebut sebagai sistem operasi harus dapat melakukan kontrol tersebut. Tak terkecuali sistem operasi tertanam TinyOS.
1
Sistem penjadwalan proses di TinyOS pada dasarnya memiliki konsep yang sama dengan sistem operasi desktop. Lebih jauh, perlu diketahui bahwa TinyOS memiliki empat tipe pemanggilan dalam proses [3]: 1. Commands 2. Events atau Back calls 3. Tasks 4. C procedures Makalah ini akan membahas pada bagian Task dimana skema penjadwalan proses lebih banyak bekerja pada bagian tersebut.
2 2.1
Sistem Penjadwalan Proses pada TinyOS Penjadwalan First In First Out
Pada sistem penjadwalan ini sudah jelas task yang pertama masuk pada antrian akan diproses terlebih dahulu. Tidak ada konsep prioritas dan semua task akan memiliki kesempatan yang sama untuk diproses. Task diurutkan pada sebuah antrian melingkar, dimana task yang baru masuk akan diletakkan dibelakang antrian. Jika tidak ada antrian, maka processor akan berada pada mode SLEEP secara otomatis. [4]
2.2
Shortest Job Priority (SJP)
SJP mengimplementasikan konsep nilai pada waktu untuk memberikan prioritas kepada pekerjaan [5]. SJP membagi pekerjaan berdasarkan hard real time dan soft real time. Hard real time jobs merupakan pekerjaan yang harus selesai pada batas waktu tertentu, sedangkan soft real time jobs merupakan pekerjaan yang dapat dilakukan setelah hard real time jobs selesai. [4] Mekanisme penjadwalan tipe ini ialah dengan mengetahui estimate time (waktu perkiraan) kapan pekerjaan tersebut akan selesai. Setelah diketahui, maka job atau pekerjaan tersebut akan dimasukkan dilokasi yang sesuai dalam daftar antrian. Ini tidak seperti FIFO yang akan selalu memasukkan pekerjaan pada antrian terbelakang meskipun waktu untuk selesainya lebih cepat.
2.3
Deadline Scheduler
Deadline scheduler merupakan ekstensi dari FIFO yang menggunakan konsep deadline pada sistem penjadwalan. Thread akan dieksekusi berdasarkan deadline. Penjadwal akan menerima thread dengan deadline sebagai parameter. Kemudian akan diperbandingkan deadline yang telah ada dalam antrian dan memasukkan thread tersebut pada tempat yang sesuai dalam antrian 2
penjadwal. Namun, untuk menghindari terjadinya “starvation” akibat lamanya proses thread, maka deadline dari semua task yang ada diantrian penjadwal akan dikurangi secara simultan (decremented). [4]
2.4
Earliest Deadline First (EDF) Scheduler
Algoritma EDF mempertimbangkan bahwa setiap real-time task memiliki deadline dalam waktu eksekusi. Dan prioritas dari suatu task ditentukan berdasarkan nilai deadline time yang diberikan kepadanya. Semakin kecil deadline time, semakin besar prioritasnya. [4]
2.5
Flexible Power Scheduling (FPS)
FPS mengenalkan sebuah pendekatan yang mengurangi konsumsi daya pada radio dengan tetap mendukung pada fluktuasi hard dan soft real-time jobs. Operasi yang terjadi pada FPS ialah [4]: 1. Parent memilih slot S yang sedang tidak digunakan dan memberitahukan slot tersebut 2. Child menerima pemberitahuan dari parent dan mengirimkan permintaan ke slot S 3. Parent menerima permintaan dan memberi pengakuan terhadap child
3
Kesimpulan
Diatas telah dijelaskan bahwa TinyOS memiliki berbagai macam tipe penjadwalan. Masingmasing memiliki kelebihan dan kekurangannya, yang dirangkum dalam bentuk tabel sebagai berikut:
3
Scheduler FIFO
Tipe Nonpreemptive
SJP
Preemptive
FPS
–
EDF
Nonpreemtive
Deadline
Preemptive
Konsep pertama datang, pertama dilayani prioritas pada pekerjaan paling cepat: berdasarkan batasan waktu pendekatan terpusat berdasarkan pembagian waktu prioritas: berdasarkan deadline eksekusi dari suatu task thread dieksekusi berdasarkan deadline
Keunggulan sederhana
menaikkan keluaran, memecahkan masalah beban berlebih (overload)
penghematan daya secara signifikan, mengurangi anggapan, menaikkan keluaran multi-hop dan keadilan pemilihan prioritas menjadi dinamis
Kelemahan beban berlebih, “starvation” untuk pekerjaan yang darurat, menurunkan keluaran pekerjaan dengan prioritas tinggi tidak boleh critical
kemungkinan terjadinya benturan dan pesan hilang
tidak dapat memastikan penjadwalan secara real-time
mencegah “starvation” – dari thread memiliki deadline yang lebih lama
Preeemptive: Keputusan penjadwalan CPU dilakukan apabila proses berpindah dari keadaan running ke ready atau proses berpindah dari waiting ke ready. Non-preemptive: Keputusan penjadwalan CPU dilakukan apabila proses berpindah dari running ke waiting atau apabila proses berhenti.
4
References [1] htt p : //tinyos.stan f ord.edu/tinyos − wiki/index.php/TinyOSO verview [2] Silberschatz, A., Galvin, P. B., Gagne, G., and Silberschatz, A. (1998). Operating system concepts (Vol. 4). Reading: Addison-Wesley. [3] Bassam, Ayman Al. TinyOS Scheduler, Boot sequence And concurrency model. King Fahd University of Petroleum and Minerals: Computer Engineering Department, COE 499. [4] Borges, V., Raikar, O., Desai, V., and Dalvi, P. A Comparative Study of TinyOS Scheduling Strategies and Future Scope. [5] Liu, J. (2010, October). Research on TinyOS Scheduling Strategy Based on SJP. In Computational Intelligence and Design (ISCID), 2010 International Symposium on (Vol. 1, pp. 144-146). IEEE.
5
