Preemptive Scheduling for Distributed Systems

Penjadwalan Preemptive pada Sistem Terdistribusi
Ringkasan oleh : Nurul Huda (41508110133)

Umumnya sistem operasi multitasking menggunakan penjadwalan preemptive. Banyak sistem multiprosessor juga menggunakan penjadwalan preemptive intertask ketika melakukan komputasi paralel. Namun, penjadwalan preemptive pada sistem terdistribusi sangat jarang, bahkan hampir tidak ada.

Penjadwalan Preemptive adalah kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. Melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya.

Contoh Penjadwalan Preemptive : Penjadwalan CPU yang dijalankan ketika proses dalam keadaan:

• Berubah dari running ke ready state.
• Berubah dari waiting ke ready state.

Sedangkan Sistem Terdistribusi adalah Kumpulan komputer yang terhubung melalui sistem jaringan komputer dan dilengkapi dengan sistem software terdistribusi untuk membentuk fasilitas komputer terintegrasi.
Kendala Implementasi Penjadwalan Preemptive pada sistem terdistribusi adalah dibutuhkan proses migrasi yang tepat, panjang task yang bervariasi, kecepatan dan beban kerja prosesor bervariasi, sehingga diperlukan algoritma penjadwalan yang tepat.
Pusat implementasi dari protokol penjadwalan preemptive adalah mekanisme dari migrasi proses. Mekanisme Migrasi : Anggap sebuah worker sedang mengeksekusi task T1 pada mesin M1. Sekarang penjadwal ingin memindah T1 ke mesin M2. Untuk memperoleh keadaan ini perlu migrasi proses. Jika ada sebuah worker sudah running pada M2, hanya context pada thread aplikasi (yang mewakili context pada task yang sedang dieksekusi) yang perlu di transfer dari M1 ke M2. Jadi, migrasi task mencapai penjadwalan preemptive.
Pada contoh diatas, pertama kali, penjadwal (pada manajer) memberitahukan thread asinkron (pada worker) di M1 untuk membekukan T1. Thread asinkron kemudian memberitahukan thread kontrol, yang akan mensuspend thread aplikasi yang sedang berjalan pada T1. Thread kontrol kemudian mengambil context pada thread aplikasi dan memaketkannya dan mengirimnya ke manajer. Manajer kemudian mengirim context dari T1 ke thread kontrol pada M2. Thread kontrol pada M2 mengumpulkan context dari thread aplikasinya untuk menerima context dan me-resume-nya. Sekarang T1 di-resume pada M2.
Implementasi yang kami lakukan untuk pengujian Penjadwalan Preemptive pada Sistem Terdistribusi menggunakan :

• Pemrosesan paralel menggunakan Sistem Chime
• Tiga sistem komputer Prosesor Pentium II 266, memori 128Mbyte, terkoneksi menggunakan kartu Ethernet 100Mb/s.
• Sistem operasi : Windows NT 4.0.
• Kompiler : Visual C++ 4.0.
• Menggunakan 4 algoritma penjadwalan.
• Aplikasi yang dipakai untuk menguji algoritma : Ray Tracing dan Perkalian Matrix.

4 algoritma penjadwalan yang diujicobakan untuk menjalankan aplikasi :

1. Penjadwalan optimal : penjadwalan yang diperhitungkan sebelumnya, secara teoretis waktu runtime paling pendek, dengan jumlah penjadwalan yang paling sedikit. Setiap mesin, dan setiap task harus identik. Bekerja paling baik ketika jumlah task lebih banyak daripada jumlah mesin.
2. Penjadwalan Eager Setiap mesin m mendapat satu task n. ketika satu task selesai, mesin mendapat penugasan dari task lain. Ketika satu task selesai, mesin mendapat task lain yang belum ditugaskan. Jika semua task selesai ditugaskan, task-task yang belum selesai ditugaskan kembali ke mesin ini.
3. Penjadwalan Round Robin : dari sejumlah n task, sebanyak m task akan ditugaskan ke sejumlah m mesin. Setelah satu quantum waktu, semua m task di preempt dan kemudian m task berikutnya ditugaskan (secara berulang).
4. Task Bunching : sejumlah n task dibagi (bunched) kedalam sekumpulan m mesin. Setiap mesin menjalankan satu bunch task secara sekuensial. Ketika satu bunch task selesai, setiap bunch task dipreempt lagi, task-task tersebut dibagi-bagi lagi ke mesin-mesin dan eksekusi diulang.

Untuk menjamin perbandingan yang adil, pertama kali kami menjalankan program paralel ini secara sekuensial menggunakan C++ . Program sekuensial membutuhkan 540 detik pada single prosesor. Hasil performa ditampilkan pada gambar 1.
Program menjalankan program paralel very coarse grained, dimana perkalian matrix dikerjakan oleh 5 task. Sebuah coarse grain mengeksekusi 10 task, medium grained mengeksekusi 20 task dan very fine grain mengeksekusi 1500 task. Quantum waktu Round Robin diset 15 detik.
Ketika melibatkan perhitungan 5 task pada 3 mesin. Penjadwalan Eager bekerja sangat buruk. Namun, penjadwalan Optimal dan Round Robin berjalan dengan baik. Task bunching tidak berjalan, karena tidak ada yang bisa di bunch. Pada pengujian selanjutnya Penjadwalan Optimal tidak dipakai karena tidak sesuai untuk jumlah task yang jauh lebih besar daripada jumlah mesin.
Untuk coarse grain, digunakan 10 task. Bagus pada Round Robin dan Task Bunching namun sedikit buruk pada penjadwalan Eager karena penjadwalan Eager adalah non-preemptive dan jumlah task bukan perkalian dari jumlah mesin.
Untuk level lapangan, digunakan 21 task. Penjadwalan Eager bekerja dengan baik seperti yang lain – namun Round Robin agak sedikit buruk, karena mempunyai lebih banyak overhead preemption dibanding yang lain.

Gambar 1. Performa penjadwalan preemptive

Pada task fine grained – menggunakan 1500 task. Round Robin dan Eager menjadi sama, dimana quantum waktu tidak pernah expired. Namun, overhead dari penugasan task pada worker mendominasi waktu komputasi, sehingga performa menjadi buruk. Tetapi total waktu yang didapat masih lebih pendek daripada waktu sekuensial (540 detik). Untuk komputasi fine-grained, task bunching digunakan bersama preemption menghasilkan performa yang bagus pada beberapa range ukuran.

Kesimpulan : Optimal bekerja bagus jika informasi waktu eksekusi diketahui terlebih dahulu, dan jumlah task tidak jauh lebih banyak daripada jumlah mesin. Round Robin bagus pada jumlah task yang tidak terlalu besar. Task Bunching memberikan performa paling baik pada beberapa ukuran komputasi.

SPINE: An Operating System for Intelligent Network Adapters

Ringkasan Jurnal 6
(gabungan)

SPINE adalah sebuah system operasi yang diterapkan pada intelligent network adaptor, dimana di dalam intelligent network adapter tersebut memiliki Processor. Sistem ini memanfaatkan kelebihan yang pada network adapter.

Contoh dari network adapter itu sendiri adalah: Router.

Pada gambar diatas dapat dilihat bahwa sebuah SPINE yang di terapkan pada Intelligent network adapter.Sebagian job yang ada pada aplikasi akan di kirim ke dalam Intelligent network adapter dan job tersebut akan diproses oleh SPINE Extention untuk kemudian hasil pemrosesan tersebut akan dikirim ke host / users. Sama dengan halnya sebagian job yang ada pada host juga (terutama yang behubungan dengan network ) akan di limpahkan ke SPINE Extention.

VIDEO CLIENT EXTENTION

Dengan menggunakan SPINE kita dapat membuat video client application

Aplikasi menentukan sebuah aplikasi spesifik untuk video extention yang mentransfer data video yang datang dari network dan langsung menuju ke frame buffer. Video client berjalan pada aplikasi regular pada Windows NT. Ini bertanggung jawab untuk membuat framing window yang menampilkan video dan menginformasikan video extention dari window coordinates.

Video Extention pada network adapter menjaga window coordinate dan ukuran informasinya, Serta DMA mentransfer data video yang datang dari network, ke bagian dari frame buffer memori yang merepresentasikan ke dalam application window.

Aplikasi video menangkap setiap pergerakan dari window, dan menginformasikan kepada video extention tentang window coordinate yang baru.

Implementasi dari jalannya video extention pada network adapter sangatlah mudah. Kasarnya terdapat 250 baris kode, yang terdiri dari fungsi untuk :

• Instantiate per window metadata untuk window coordinate,ukuran / size,dll.
• Mengupdate metadata setelah apa yang terjadi pada window ( pergerakan window )
• DMA mentransfer data ke dalam frame budffer.

Fungsi ini teregistrasi sebagai active message handler dengan SPINE I/O runtime dan akan meminta bila pesan tiba pada salah satu dari host atau network.

Video Ekstention mentransfer data dari network adapter langsung menuju ke frame buffer, yang mana dapat mengurangi I/O channel load, frees host resource, dan juga mengurangi keterlambatan untuk menampilkan video dari saat waktu pertama datang dari network.

Figure 2 diatas melukiskan keseluruhan struktur yang lebih detail. Untuk angka yang ada pada tanda panah di atas mempunyai arti sebagai berikut :

1. Video Application mengirim extention ke dalam card.
2. Paket berisi video yang datang dari network.
3. SPINE mnegirimkan paket ke dalam video extention.
4. Video Extention mentransfer data secara langsung ke frame buffer, dan video image akan ditampilkan kepada user.

MANTIS OS : an Embedded Multithreaded Operating System for Wirelss Microsensors Platform

Apa itu MANTIS OS ?

MANTIS : MultimodAl system for NeTworks of In-situ wireless Sensors.

Multimodal system -> system kompleks / kombinasi ( Sistem Operasi )
Networks of in-situ Wireless Sensors ->
jaringan sensor nirkabel yang bersifat in-situ, yaitu operasi yang terjadi tanpa menyela (interrupt) system dalam keadaan normal.

MANTIS OS : an Embedded Multithreaded Operating System for Wirelss Microsensors Platform

(MANTIS OS : Penggunaan MANTIS OS sebagai sistem operasi multithread untuk perangkat wireless microsensors)

Apa itu Multithread OS ?

Multithread : dalam satu proses terjadi eksekusi thread / proses lebih dari satu pada waktu yang sama.

Wireless Sensor Network (WSN)

Sensor jaringan nirkabel (WSN) adalah jaringan nirkabel yang terdiri dari perangkat khusus yang menggunakan sensor untuk memantau kondisi fisik atau lingkungan, seperti suhu, suara, getaran, tekanan, gerakan atau polusi, di lokasi yang berbeda. Pengembangan WSN pada awalnya dipakai oleh aplikasi militer seperti survey medan perang. Sekarang banyak digunakan dalam aplikasi umum, termasuk pemantauan di bidang lingkungan hidup dan habitat, aplikasi kesehatan, dan kontrol lalu lintas.


Lightweight MANTIS OS design (MOS)


Jurnal ini menjelaskan MANTIS OS, OS multithreaded yang ringan dan efisien energi untuk perangkat WSN. Saat ini, MOS kernel dapat menjalankan eksekusi penjadwalan secara preemptive multithreaded dengan standar I / O sinkronisasi dan stack protokol jaringan, kurang dari 500 byte RAM, belum termasuk ukuran thread stack individu. Selain itu, MANTIS dirancang untuk memberikan dukungan cross-platform di PC, PDA, sebaik platform perangkat keras mikro Sensor.

Kernel and scheduler
Layanan/service yang diberikan adalah subset dari POSIX (Portable Operating System Interface for UNIX, adalah sebuah standar yang dicetuskan oleh Institute of Electical and Electronics Engineers (IEEE) yang mendefinisikan sekumpulan layanan dalam sistem operasi ) threads, terutama prioritas berdasarkan urutan penjadwalan dengan round-robin semantik dalam prioritas tinggi. Binary (mutex) dan menghitung semaphores juga didukung. Tujuan dari MOS kernel desain adalah untuk mengimplementasikan service-service diatas agar dapat bekerja di perangkat sensor yang terbatas.


Thread and events

2 model ekskusi pada sistem sensor.

Untuk mengilustrasikan bounded buffer produsen-konsumen sebagai masalah Sensor ini berlaku untuk jaringan, Gambar di atas menggambarkan dua tugas yang berpasangan, yaitu produsen dan konsumen, dimana biasanya berbagi buffer antara keduanya. Sebagai produsen menghasilkan data, data ini ditempatkan di buffer antara keduanya. Konsumen mengosongkan buffer kapanpun ketika memiliki kesempatan untuk eksekusi. Jika konsumen tidak dapat dijalankan , dan beberapa produsen terus menambahkan data ke buffer, maka akhirnya akan overflow. hal ini menunjukkan bahwa sistem dengan model thread dapat mencapai kinerja tinggi pada sistem berbasis event untuk aplikasi konkurensi (yaitu proses-proses yang ada pada waktu bersamaan, bisa bersifat independen atau saling berinteraksi). TinyOS adalah standar OS yang berbasis event untuk perangkat jaringan sensor. Perancang TinyOS yakin bahwa pendekatan berbasis event mampu menciptakan sistem yang hemat energy selama proses blocking dan polling (pengambilan sampel status perangkat eksternal oleh sebuah program klien sebagai kegiatan sinkronisasi) dilakukan oleh event tersebut. OS MANTIS multithreaded berusaha untuk memberikan jalan untuk mengembangkan Sensor sistem untuk mendukung tugas-tugas yang semakin kompleks, dimana pada saat yang sama terdapat kendala sumber daya dan energi memori pada jaringan sensor. Time-slice multithreading menawarkan preemption otomatis, yang memiliki keuntungan dimana satu segmen kode aplikasi tidak dapat memblokir eksekusi proses yang lain. Hal ini penting dalam sistem Sensor, dimana ketika memblokir seksi kritis tertentu, seperti pengolahan paket jaringan, dapat mengakibatkan overflow jaringan buffer ketika mengerjakan tugas-tugas yang cukup lama sedangkan RAM buffer sensor yang tersedia cukup kecil.


Kesimpulan

MANTIS system menyediakan kemampuan baru
- Ringan, multithreaded, cross-platform OS dan network
- Flexible single-board hardware platform
- Mudah mengintegrasikan jaringan sensor dengan aplikasi lain.

MANTIS adalah sistem operasi WSN yang mudah digunakan
- Penggunaan Bahasa dan API yang familiar
- Power management tools

Task Scheduling for Multiprocessor Systems Using Memetic Algorithm

RINGKASAN
(MHS GABUNGAN)

Introduksi

Penjadwalan proses-proses pararel yang dapat meminimalkan waktu ekseskusi oleh prosesor sangatlah penting untuk mencapai performansi yang tinggi pada sistem multiprosesor. Permasalahan dalam penjadwalan pada sistem multiprosesor adalah seperti penjadwalan untuk mengeksekusi general task dalam bentuk graph, dengan demikian panjangnya waktu penjadwalan dapat diminimalkan. Beberapa teknik yang dapat digunakan pada penjadwalan multiprosesor adalah Genetic Algorithm (GA), Simulated Annealing (SA) dan Memetic Algorithm (MA) yang merupakan perpaduan dari GA dan SA.

Genetic Algorithm merupakan algoritma pencarian yang berdasarkan dari mekanisme penyeleksian dan penurunan yang umum. Tujuan utama dari algoritma ini adalah keseimbangan antara efisiensi dan keampuhannya.

Simulated Annealing (SA) merupakan suatu keterkaitan teknik optimasi global yang melakukan pencarian dengan menguji mutasi secara acak. Suatu mutasi yang meningkatkan kemampuan selalu diperbolehkan, namun mutasi dengan kemampuan yang lebih rendah juga dimungkinkan. SA juga dapat digunakan bersama GA yang dimulai dengan mutasi yang tinggi, dimana mengurangi over time yang diberikan untuk masing-masing proses dalam penjadwalan. Penggabungan kedua algoritma ini disebut sebagai Memetic Algorithm. meminimalkan keseluruhan waktu ekseskusi dari sekumpulan sub proses.

Syarat-syarat penjadwalan

• Relasi prioritas antara proses-proses yang ada. Hal ini menentukan urutan waktu ekseskusi.
• Waktu komunikasi (waktu yang dihabiskan untuk mengirim pesan oleh suatu proses pada suatu prosesor untuk menggantikan proses pada prosesor yang berbeda). Waktu yang dihabiskan untuk komunikasi antar prosesor diasumsikan Nol.
• Duplikasi proses diperbolehkan. Misalkan suatu proses yang sama bisa ditempatkan pada prosesor yang berdeba untuk mengurangi waktu komunikasi dan panjangnya penjadwalan.
• Sistem multiprosesor terdiri dari prosesor yang terbatas dan saling terhubung.

Task Graph




Populasi Awal

Merupakan daftar task yang dijadwalkan untuk setiap prosesor diurutkan secara menaik (ascending) berdasarkan tinggi task tersebut.


Algoritma untuk menghasilkan inisialisasi populasi

1. [Inisialisasi] Menghitung tinggi untuk setiap task dalam TG
2. [Pisahkan task berdasarkan ketinggiannya]
3. [Loop p-1 kali] Untuk setiap prosesor pertama p-1, lakukan langkah 4
4. [Buat penjadwalan untuk suatu prosesor]
5. [Prosesor terakhir] Tempatkan sisa task dalam daftar kepada prosesor terakhir

Algoritma dengan menggunakan GA

1. [Inisialisasi]
2. Ulangi langkah 3 sampai 8 sampai algoritma memusat
3. Hitung fitness value untuk tiap string pada inisialisasi populasi
4. Lakukan reproduksi. Simpan string dengan fitness value tertinggi pada BEST_STRING
5. Lakukan crossover
6. Lakukan mutasi
7. Pertahankan string terbaik pada BEST_STRING

Algoritma Reproduksi

1. [Inisialisasi] NPOP  Nomor string dalam POP
2. [Buat roulette wheel] NSUM  Jumlahkan semua fitness value dari string dalam POP; Bentuk slot NSUM dan tempatkan string ke dalam slot sesuai fitness value-nya
3. [Loop NPOP - I kali] Lakukan langkah 4 NPOP - I kali
4. [Ambil sebuah string] Menghasilkan nomor acak antara I dan NSUM dan gunakan untuk meng-indeks ke dalam slot untuk menemukan string terkait; Tambahkan string ke NEWPOP
5. [Tambahkan best string] Tambahkan string dengan fitness value tertinggi dari POP ke NEWPOP

Penggabungan dari GA dan SA disebut algoritma memetic sbb:

1. [Inisialisasi]
2. Ulangi langkah 3 sampai 8 sampai algoritma memusat
3. Hitung fitness value untuk tiap string pada inisialisasi populasi
4. Susun berdasarkan chromosome untuk mengurangi urutan fitness value-nya
5. Buang p chromosome paling rendah
6. Lakukan reproduksi pada sisa chromosome. Simpan string dengan fitness value tertinggi pada BEST_STRING
7. Lakukan crossover
8. Lakukan mutasi
9. Pertahankan string terbaik pada BEST_STRING

Kesimpulan

Masalah penjadwalan task yang akan dieksekusi dalam sistem multiprosesor merupakan masalah yang sangat menantang dalam komputasi paralel. Algoritma genetik baik untuk diadaptasi dalam masalah penjadwalan multiprosesor. Beberapa algoritma genetik telah dibangun untuk penjadwalan task. Struktur dan pembatasan tempat atas representasi chromosome secara berpengaruh kuat terhadap kompleksitas genetic operator sebagaimana memungkinkan penggabungan algoritma untuk menemukan solusi optimal. Masih terdapat beberapa kekurangan pada algoritma genetik dan oleh karena itu dikombinasikan dengan simulated annealing untuk meningkatkan kemampuan sistem secara keseluruhan. Penggabungan ini dinamakan Algoritma Memetic.

A Comparison of the RTU Hardware RTOS with a Hardware/Software RTOS

Ringkasan

( Gabungan )

Suatu sistem komputasi dinamakan real-time jika sistem tersebut dapat mendukung eksekusi program/aplikasi dengan waktu yang memiliki batasan. Dengan kata lain, sistem real-time harus memenuhi kondisi berikut:

1. Batasan waktu: memenuhi deadline, artinya bahwa aplikasi harus menyelesaikan tugasnya dalam waktu yang telah dibatasi.
2. Dapat diprediksi: artinya bahwa sistem harus bereaksi terhadap semua kemungkinan kejadian selama kejadian tersebut bisa diprediksi.
3. Proses bersamaan: artinya jika ada beberapa proses yang terjadi bersamaan, maka semua deadline nya harus terpenuhi.

Dalam jurnal ini, kita akan membandingkan 3 buah RTOS, yaitu :

• Pure Software RTOS
  Yaitu Jenis Real Time Operationg System (RTOS) yang dalam implementasinya menggunakkan suatu software system operasi murni. Artinya, bahwa ketika proses-proses akan dijalankan maka paket-paket yang dibutuhkan untuk menjalankan proses tersebut di install terlebih dahulu. Semua proses akan dieksekusi di dalam processor

• Real Time Unit (RTU)
  Merupakan kombinasi dari soft-hard RTOS. Dalam Operating System ini, software dirubah menjadi sebuah chip dengan logika yang sama, sehingga dapat langsung bekerja serta tidak membutuhkan processor karena proses dieksekusi didalam chip tersebut.

• System On A Chip Lock Cache(SoCLC)
  Merupakan RTOS yang tidak murni menggunakan software. Pada RTOS ini menggunakan chip khusus untuk menangani switching proses. Ada beberapa bagian yang terdiri dari chip khusus.

KINERJA YANG DIUKUR

Kinerja yang diukur dalam perbandingan 3 RTOS ini adalah :

• 1. Total waktu eksekusi, yaitu waktu yang dibutuhkan pada saat job datang, job eksekusi, sampai job complete.

• 2. Waktu yang dibutuhkan untuk : a. Komunikasi antar job, jika terjadi komunikasi. b. Pengalihan konteks job
  • Contohnya : Job A menghasilkan suatu message, kemudian job B mengambilnya dan menjalankan perintah di message tersebut.

• 3. Pengendalian proses-proses konkuren (statis).

HASIL PENGUKURAN

a. Waktu Eksekusi (basis pengukuran adalah Pure SW 0 %)

(satuan = siklus mesin)

b. Banyaknya Interaksi pada Mesin


c. Rata-rata waktu yang dibutuhkan untuk :

(satuan = siklus mesin)

KESIMPULAN

Dari hasil pengukuran diatas dapat disimpulkan bahwa untuk pengukuran total waktu eksekusi & rata-rata waktu yang dibutuhkan untuk komunikasi, contrxt switch, dan komputasi yang terbaik adalah dengan menggunakan RTU. Karena dengan RTU, sebagian task bisa dieksekusi pada chip, sedangkan pada Pure SW, semua proses harus dikerjakan di processor. Akan tetapi jika perintah-perintah pada RTOS akan diubah, maka pada RTU harus dibuat ulang, sebaliknya untuk Pure SW hanya mengubah source code dari program aplikasi kemudian di generate ulang

Berikut adalah detil data perbandingan yang didapatkan :

.