Thread
Thread (singkatan dari "thread of execution") Thread adalah alur kontrol dari suatu proses. Dalam ilmu komputer diartikan sebagai sekumpulan perintah yang dapat dilaksanakan (dieksekusi) secara sejajar dengan ulir lainnya, dengan menggunakan cara time slice (ketika satu CPU melakukan perpindahan antara satu ulir ke ulir lainnya) atau multiprocess (ketika ulir-ulir tersebut dilaksanakan oleh CPU yang berbeda dalam satu sistem). Ulir sebenarnya mirip dengan proses, tapi cara berbagi sumber daya antara proses dengan ulir sangat berbeda. Multiplethread dapat dilaksanakan secara sejajar pada sistem computer.
Setiap thread mempunyai :
· Status eksekusi (running, ready, dll.)
· Konteks thread tersimpan saat tidak berjalan (not running)
· Stack eksekusi
· Beberapa storage statis per-thread bagi variabel local
· Akses terhadap memory & sumber daya dari prosesnya (semua thread dari proses saling berbagi pakai)
Gambar 12.1. Status Thread
 |
Suatu thread bisa berada pada salah satu dari status berikut:
- New . Thread yang berada di status ini adalah objek dari kelas Thread yang baru dibuat, yaitu saat instansiasi objek dengan statement new. Saat thread berada di status new, belum ada sumber daya yang dialokasikan, sehingga thread belum bisa menjalankan perintah apapun.
- Runnable . Agar thread bisa menjalankan tugasnya, method start() dari kelas Thread harus dipanggil. Ada dua hal yang terjadi saat pemanggilan method start(), yaitu alokasi memori untuk thread yang dibuat dan pemanggilan method run(). Saat method run() dipanggil, status thread berubah menjadi runnable, artinya thread tersebut sudah memenuhi syarat untuk dijalankan oleh JVM. Thread yang sedang berjalan juga berada di status runnable.
- Blocked . Sebuah thread dikatakan berstatus blocked atau terhalang jika terjadi blocking statement, misalnya pemanggilan method sleep(). sleep() adalah suatu method yang menerima argumen bertipe integer dalam bentuk milisekon. Argumen tersebut menunjukkan seberapa lama thread akan "tidur". Selain sleep(), dulunya dikenal method suspend(), tetapi sudah disarankan untuk tidak digunakan lagi karena mengakibatkan terjadinya deadlock. Di samping blocking statement, adanya interupsi M/K juga dapat menyebabkan thread menjadi blocked. Thread akan menjadi runnable kembali jika interval method sleep()-nya sudah berakhir, atau pemanggilan method resume() jika untuk menghalangi thread tadi digunakan method suspend() atau M/K sudah tersedia lagi.
- Dead . Sebuah thread berada di status dead bila telah keluar dari method run(). Hal ini bisa terjadi karena thread tersebut memang telah menyelesaikan pekerjaannya di method run(), maupun karena adanya pembatalan thread. Status jelas dari sebuah thread tidak dapat diketahui, tetapi method isAlive() mengembalikan nilai boolean untuk mengetahui apakah thread tersebut dead atau tidak.
Keuntungan dari Thread :
· Pembuatan thread baru lebih cepat dari pada proses baru. Akan susah mengukur perbedaan waktu antara thread dan switch, tetapi secara umum pembuatan dan pengaturan proses akan memakan waktu lebih lama dibandingkan dengan thread. Pada Solaris, pembuatan proses memakan waktu 30 kali lebih lama dibandingkan pembuatan thread sedangkan proses context switch 5 kali lebih lama dibandingkan context switching thread.
· Penghentian thread lebih singkat daripada penghentian proses.
· Switching antara dua thread lebih singkat daripada switching antar proses.
· Thread dapat berkomunikasi satu sama lain tanpa memanggil kernel.
· Aplikasi interaktif menjadi tetap responsif meskipun sebagian dari program sedang diblok atau melakukan operasi lain yang panjang. Umpamanya, sebuah thread dari web browser dapat melayani permintaan pengguna sementara thread yang lain berusaha menampilkan gambar.
· Beberapa thread yang melakukan proses yang sama akan berbagi sumber daya. Keuntungannya adalah mengizinkan sebuah aplikasi untuk mempunyai beberapa thread yang berbeda dalam lokasi memori yang sama.
· Keuntungann dari multithreading dapat ditingkatkan dengan arsitektur multiprosesor, dimana setiap thread dapat jalan secara parallel pada prosesor yang berbeda. Pada arsitektur prosesor tunggal, CPU biasanya berpindah-pindah antara setiap thread dengan cepat, sehingga terdapat ilusi paralelisme, tetapi pada kenyataannya hanya satu thread yang berjalan di setiap waktu.
User Thread (Thread pengguna): Thread yang pengaturannya dilakukan oleh pustaka thread pada tingkatan pengguna. Karena pustaka yang menyediakan fasilitas untuk pembuatan dan penjadwalan thread, thread pengguna cepat dibuat dan dikendalikan.
Kernel Thread: Thread yang didukung langsung oleh kernel. Pembuatan, penjadwalan dan manajemen thread dilakukan oleh kernel pada kernel space. Karena dilakukan oleh sistem operasi, proses pembuatannya akan lebih lambat jika dibandingkan dengan thread pengguna.
User Threads
Gambar 2-17. User dan Kernel Thread.
Kernel Threads
Kernel thread didukung secara langsung oleh sistem operasi: pembentukan thread, penjadualan, dan managemen dilakukan oleh kernel dalam ruang kernel. Karena managemen thread telah dilakukan oleh sistem operasi, kernel thread biasanya lebih lambat untuk membuat dan mengelola daripada pengguna thread. Bagaimana pun, selama kernel mengelola thread, jika suatu thread di block tehadap sistem pemanggilan, kernel dapat menjadualkan thread yang lain dalam aplikasi untuk dieksekusi. Juga, di dalam lingkungan multiprosesor, kernel dapat menjadualkan thread dalam prosesor yang berbeda. Windows NT, Solaris, dan Digital UNIX adalah sistem operasi yang mendukung kernel thread.
Multithreading Model:
a. Model One to One
Model one-to-one memetakan setiap thread pengguna ke dalam satu kernel thread. Hal ini membuat model one-to-one lebih sinkron daripada model many-to-one dengan mengizinkan thread lain untuk berjalan ketika suatu thread membuat pemblokingan terhadap sistem pemanggilan; hal ini juga mengizinkan multiple thread untuk berjalan secara parallel dalam multiprosesor. Kelemahan model ini adalah dalam pembuatan thread pengguna dibutuhkan pembuatan korespondensi thread pengguna. Karena dalam proses pembuatan kernel thread dapat mempengaruhi kinerja dari aplikasi maka kebanyakan dari implementasi model ini membatasi jumlah thread yang didukung oleh sistem. Model one-to-one diimplementasikan oleh Windows NT dan OS/2.
Gambar Model One to One
b. Model Many to One
Model many-to-one ini memetakan beberapa tingkatan pengguna thread hanya ke satu buah kernel thread. Managemen proses thread dilakukan oleh (di ruang) pengguna, sehingga menjadi efisien, tetapi apabila sebuah thread melakukan sebuah pemblokingan terhadap sistem pemanggilan, maka seluruh proses akan berhenti (blocked). Kelemahan dari model ini adalah multihreads tidak dapat berjalan atau bekerja secara paralel di dalam multiprosesor dikarenakan hanya satu thread saja yang bisa mengakses kernel dalam suatu waktu.
Gambar Model Many to One
c. Model Many to Many
Beberapa tingkatan thread pengguna dapat menggunakan jumlah kernel thread yang lebih kecil atau sama dengan jumlah thread pengguna. Jumlah dari kernel thread dapat dispesifikasikan untuk beberapa aplikasi dan beberapa mesin (suatu aplikasi dapat dialokasikan lebih dari beberapa kernel thread dalam multiprosesor daripada dalam uniprosesor) dimana model many-to-one mengizinkan pengembang untuk membuat thread pengguna sebanyak mungkin, konkurensi tidak dapat tercapai karena hanya satu thread yang dapat dijadualkan oleh kernel dalam satu waktu. Model one-to-one mempunyai konkurensi yang lebih tinggi, tetapi pengembang harus hati-hati untuk tidak membuat terlalu banyak thread tanpa aplikasi dan dalam kasus tertentu mungkin jumlah thread yang dapat dibuat dibatasi.
Gambar Model Many to Many
Thread Cancellation
Thread Cancellation ialah pembatalan thread sebelum tugasnya selesai. Umpamanya, jika dalam program Java hendak mematikan Java Virtual Machine (JVM). Sebelum JVM dimatikan, maka seluruh thread yang berjalan harus dibatalkan terlebih dahulu. Contoh lain adalah di masalah search. Apabila sebuah thread mencari sesuatu dalam database dan menemukan serta mengembalikan hasilnya, thread sisanya akan dibatalkan. Thread yang akan diberhentikan biasa disebut target thread.
Pemberhentian target Thread dapat dilakukan dengan 2 cara:
a. Asynchronous cancellation. Suatu thread seketika itu juga membatalkan target thread.
b. Deferred cancellation . Suatu thread secara periodik memeriksa apakah ia harus batal, cara ini memperbolehkan target thread untuk membatalkan dirinya secara terurut.
Hal yang sulit dari pembatalan thread ini adalah ketika terjadi situasi dimana sumber daya sudah dialokasikan untuk thread yang akan dibatalkan. Selain itu kesulitan lain adalah ketika thread yang dibatalkan sedang meng- update data yang ia bagi dengan thread lain. Hal ini akan menjadi masalah yang sulit apabila digunakan asynchronous cancellation. Sistem operasi akan mengambil kembali sumber daya dari thread yang dibatalkan tetapi seringkali sistem operasi tidak mengambil kembali semua sumber daya dari thread yang dibatalkan.
Alternatifnya adalah dengan menggunakan deffered cancellation. Cara kerja dari deffered cancellation adalah dengan menggunakan satu thread yang berfungsi sebagai pengindikasi bahwa target thread hendak dibatalkan. Tetapi pembatalan hanya akan terjadi jika target thread memeriksa apakah ia harus batal atau tidak. Hal ini memperbolehkan thread untuk memeriksa apakah ia harus batal pada waktu dimana ia dapat dibatalkan secara aman yang aman. Pthread merujuk sebagai cancellation points.
Pada umumnya sistem operasi memperbolehkan proses atau thread untuk dibatalkan secara asynchronous. Tetapi Pthread API menyediakan deferred cancellation. Hal ini berarti sistem operasi yang mengimplementasikan Pthread API akan mengizinkan deferred cancellation.
Thread Pools
Thread Pools digunakan sebagai solusi pada web server yang multithreading dari dua masalah yang timbul, yaitu:
a. Ukuran waktu yang diperlukan untuk menciptakan thread yang melayani permintaan yang diajukan pada kenyataannya thread dibuang seketika sesudah ia menyelesaikan tugasnya.
b. Pembuatan thread yang tidak terbatas jumlahnya dapat menurunkan performa dari sistem.
Cara kerjanya adalah dengan membuat beberapa thread pada proses startup dan menempatkan mereka ke pools, dimana mereka duduk diam dan menunggu untuk bekerja. Jadi, ketika server menerima permintaan, ia akan membangunkan thread dari pool dan jika thread tersedia maka permintaan tersebut akan dilayani. Ketika thread sudah selesai mengerjakan tugasnya maka ia kembali ke pool dan menunggu pekerjaan lainnya. Bila tidak ada thread yang tersedia pada saat dibutuhkan maka server menunggu sampai ada satu thread yang bebas.
Keuntungan thread pool adalah:
a. Biasanya lebih cepat untuk melayani permintaan dengan thread yang ada dibandingkan menunggu thread baru dibuat.
b. Thread pool membatasi jumlah thread yang ada pada suatu waktu. Hal ini penting pada sistem yang tidak dapat mendukung banyak thread yang berjalan secara concurrent. Jumlah thread dalam pool dapat tergantung dari jumlah CPU dalam sistem, jumlah memori fisik, dan jumlah permintaan klien yang concurrent.
Thread dengan Linux
Ketika pertama kali dikembangkan, Linux tidak didukung dengan threading di dalam kernelnya, tetapi dia mendukung proses-proses sebagai entitas yang dapat dijadwalkan melalui clone() system calls. Sekarang Linux mendukung penduplikasian proses menggunakan system call clone() dan fork(). Clone() mempunyai sifat mirip dengan fork(), kecuali dalam hal pembuatan copy dari proses yang dipanggil dimana ia membuat sebuah proses yang terpisah yang berbagi address space dengan proses yang dipanggil. Pembagian address space dari parent process memungkinkan cloned task bersifat mirip dengan thread yang terpisah. Pembagian address space ini dimungkinkan karena proses direpresentasikan di dalam Kernel Linux. Di dalam Kernel Linux setiap proses direpresentasikan sebagai sebuah struktur data yang unik. Jadi, daripada menciptakan yang baru maka struktur data yang baru mengandung pointer yang menunjuk ke tempat dimana data berada. Jadi ketika fork() dipanggil, proses yang baru akan tercipta beserta duplikasi dari segala isi di struktur data di parent process, namun ketika clone() dipanggil, ia tidak menduplikasi parent processnya tetapi menciptakan pointer ke struktur data pada parent process yang memungkinkan child process untuk berbagi memori dan sumber daya dari parent processnya. Project LinuxThread menggunakan system call ini untuk mensimulasi thread di user space. Sayangnya, pendekatan ini mempunyai beberapa kekurangan, khusunya di area signal handling, scheduling, dan interprocess synchronization primitive.
Untuk meningkatkan kemampuan Thread Linux, dukungan kernel dan penulisan ulang pustaka thread sangat diperlukan. Dua project yang saling bersaing menjawab tantangan ini. Sebuah tim yang terdiri dari pengembang dari IBM membuat NGPT (Next Generation POSIX Threads). Sementara pengembang dari Red Hat membuat NPTL (Native POSIX Thread Library).Sebenarnya Linux tidak membedakan antara proses dan thread. Dalam kenyataannya, Linux lebih menggunakan istilah task dibandingkan proses dan thread ketika merujuk kepada pengaturan alur pengontrolan di dalam program.
Thread dengan Java
Setiap program Java memiliki paling sedikit satu thread. Bahasa pemrograman Java memungkinkan adanya pembuatan dan manajemen thread tambahan oleh JVM. Sebuah thread bisa berada di salah satu dari 4 status, yaitu new, runnable, blocked, dan dead. Ada dua cara untuk membuat thread dalam Java, yaitu dengan meng- extends kelas
Thread dan dengan meng- implements interface Runnable.Dalam beberapa kondisi, thread yang dibuat dapat digabungkan dengan parent thread-nya. Method
join() berfungsi agar suatu thread menunggu thread yang dibuatnya menyelesaikan tugasnya terlebih dahulu, baru mulai mengeksekusi perintah selanjutnya.Pembatalan thread secara asynchronous dilakukan dengan pemanggilan method
stop(). Akan tetapi, cara ini terbukti tidak aman, sehingga untuk menterminasi thread digunakanlah deferred cancellation. Pembatalan dilakukan dengan pemanggilan method interrupt() untuk mengeset status interupsi, serta isInterrupted() atau interrupted() untuk memeriksa status interupsi tersebut.Program Java dapat dijalankan di berbagai platform selama platform tersebut mendukung JVM. Pemetaan thread Java ke host operating system tergantung pada implementasi JVM di sistem operasi tersebut.
Semua program java mempunyai paling sedikit satu kontrol thread. Bahkan program java yang sederhana mempunyai hanya satu main() method yang berjalan dalam thread tunggal dalam JVM. Java menyediakan perintah-perintah yang mendukung pengembang untuk membuat dan memanipulasi kontrol thread pada program.
Satu cara untuk membuat thread secara eksplisit adalah dengan membuat kelas baru yang diturunkan dari kelas thread, dan menimpa run() method dari kelas Thread tersebut.
Object yang diturunkan dari kelas tersebut akan menjalankan sebagian thread control dalam JVM. Bagaimana pun, membuat suatu objek yang diturunkan dari kelas Thread tidak secara spesifik membuat thread baru, tetapi start() method lah yang sebenarnya membuat thread baru.
Memanggil start() method untuk objek baru mengalokasikan memori dan menginisialisasikan thread baru dalam JVM dan memanggil run() method membuat thread pantas untuk dijalankan oleh JVM. (Catatan: jangan pernah memanggil run() method secara langsung. Panggil start() method dan ini secara langsung akan memanggil run() method).
Ketika program ini dijalankan, dua thread akan dibuat oleh JVM. Yang pertama dibuat adalah thread yang berasosiasi dengan aplikasi-thread tersebut mulai dieksekusi pada main() method. Thread kedua adalah runner thread secara ekspilisit dibuat dengan start() method. Runner thread memulai eksekusinya dengan run() method.
Pilihan lain untuk membuat sebuah thread yang terpisah adalah dengan mendefinisikan suatu kelas yang mengimplementasikan runnable interface. Runnable interface tersebut didefinisikan sebagai berikut:
Gambar 2-23. Runnable.
| Public interface Runnable { Public abstract void run(); } |
Sehingga, ketika sebuah kelas diimplementasikan dengan runnable, kelas tersebut harus mendefinisikan run() method. Kelas thread yang berfungsi untuk mendefinisikan static dan instance method, juga mengimplementasikan runnable interface. Itu menerangkan bahwa mengapa sebuah kelas diturunkan dari thread harus mendefinisikan run() method.
Gambar 2-24. Class Worker2.
| Class worker2 implements Runnable { Public void run() { System. Out. Println ("I am a worker thread. "); } } |
Membuat sebuah thread dari kelas yang diimplementasikan oleh runnable berbeda dengan membuat thread dari kelas yang mengekstend thread. Selama kelas baru tersebut tidak mengekstend thread, dia tidak mempunyai akses ke objek static atau instance method — seperti start() method — dari kelas thread. Bagaimana pun, sebuah objek dari kelas thread adalah tetap dibutuhkan, karena yang membuat sebuah thread baru dari kontrol adalah start() method.
Penjadualan CPU
Penjadualan CPU adalah pemilihan proses dari antrian ready untuk dapat dieksekusi.
Kriteria Penjadual
Algoritma penjadual CPU yang berbeda mempunyai property yang berbeda. Dalam memilih algoritma yang digunakan untuk situasi tertentu, kita harus memikirkan properti yang berbeda untuk algoritma yang berbeda. Banyak kriteria yang dianjurkan utnuk membandingkan penjadual CPU algoritma. Kritria yang biasanya digunakan dalam memilih adalah:
1. CPU utilization: kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0 ke 100 persen. Di sistem yang sebenarnya seharusnya ia mempunyai range dari 40 persen samapi 90 persen.
2. Throughput: jika CPU sibuk mengeksekusi proses, jika begitu kerja telah dilaksanakan. Salah satu ukuran kerja adalah banyak proses yang diselesaikan per unit waktu, disebut througput. Untuk proses yang lama mungkin 1 proses per jam; untuk proses yang sebentar mungkin 10 proses perdetik.
3. Turnaround time: dari sudur pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut. Interval dari waktu yang diizinkan dengan waktu yang dibutuhkan untuk menyelesaikan sebuah prose disebut turn-around time. Trun around time adalah jumlah periode untuk menunggu untuk bisa ke memori, menunggu di ready queue, eksekusi di CPU, dan melakukan I/O.
4. Waiting time: algoritma penjadual CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut atau I/O; itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian ready. Waiting time adalah jumlah periode menghabiskan di antrian ready.
5. Response time: di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria. Sering sebuah proses bisa memproduksi output diawal, dan bisa meneruskan hasil yang baru sementara hasil yang sebelumnya telah diberikan ke user. Ukuran yang lain adalah waktu dari pengiriamn permintaan sampai respon yang pertama di berikan. Ini disebut response time, yaitu waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output untu respon tersebut.
Biasanya yang dilakukan adalah memaksimalkan CPU utilization dan throughput, dan minimalkan turnaround time, waiting time, dan response time dalam kasus tertentu kita mengambil rata-rata.
Kriteria Penjadwalan
Suatu algoritma penjadwalan CPU yang berbeda dapat mempunyai nilai yang berbeda untuk sistem yang berbeda. Banyak kriteria yang bisa dipakai untuk menilai algoritma penjadwalan CPU.
Kriteria yang digunakan dalam menilai adalah:
1. CPU Utilization . Kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0 sampai 100 persen. Di sistem yang sebenarnya ia mempunyai range dari 40 sampai 100 persen.
2. Throughput . Salah satu ukuran kerja adalah banyaknya proses yang diselesaikan per satuan waktu. Jika kita mempunyai beberapa proses yang sama dan memiliki beberapa algoritma penjadwalan yang berbeda, throughput bisa menjadi salah satu kriteria penilaian, dimana algoritma yang menyelesaikan proses terbanyak mungkin yang terbaik.
3. Turnaround Time . Dari sudut pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut. Memang, lama pengeksekusian sebuah proses sangat tergantung dari hardware yang dipakai, namun kontribusi algoritma penjadwalan tetap ada dalam lama waktu yang dipakai untuk menyelesaikan sebuah proses. Misal kita memiliki sistem komputer yang identik dan proses-proses yang identik pula, namun kita memakai algoritma yang berbeda, algoritma yang mampu menyelesaikan proses yang sama dengan waktu yang lebih singkat mungkin lebih baik dari algoritma yang lain. Interval waktu yang diijinkan dengan waktu yang dibutuhkan untuk menyelesaikan sebuah proses disebut turnaround time. Turnaround time adalah jumlah periode untuk menunggu untuk dapat ke memori, menunggu di ready queue, eksekusi CPU, dan melakukan operasi M/K.
4. Waiting Time . Algoritma penjadwalan CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut atau M/K, itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian ready. Waiting time adalah jumlah waktu yang dibutuhkan proses di antrian ready.
5. Response Time . Di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria. Sering sebuah proses dapat memproduksi output di awal, dan dapat meneruskan hasil yang baru sementara hasil yang sebelumnya telah diberikan ke pengguna. Ukuran lain adalah waktu dari pengiriman permintaan sampai respon yang pertama diberikan. Ini disebut response time, yaitu waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output untuk respon tersebut.
6. Fairness . Suatu algoritma harus memperhatikan pengawasan nilai prioritas dari suatu proses (menghindari terjadinya starvation CPU time).
7. Efisiensi. Rendahnya overhead dalam context switching, penghitungan prioritas dan sebagainya menentukan apakah suatu algoritma efisien atau tidak.
Sebaiknya ketika kita akan membuat algoritma penjadwalan yang dilakukan adalah memaksimalkan CPU utilization dan throughput, dan meminimalkan turnaround time, waiting time, dan response time.
Dispatcher
Komponen yang lain yang terlibat dalam penjadwalan CPU adalah dispatcher. Dispatcher adalah modul yang memberikan kontrol CPU kepada proses yang sedang terjadwal. Fungsinya adalah:
1. Context switching . Mengganti state dari suatu proses dan mengembalikannya untuk menghindari monopoli CPU time. Context switching dilakukan untuk menangani suatu interrupt(misalnya menunggu waktu M/K). Untuk menyimpan state dari proses-proses yang terjadwal sebuah Process Control Block harus dibuat untuk mengingat proses-proses yang sedang diatur scheduler. Selain state suatu proses, PCB juga menyimpan process ID, program counter(posisi saat ini pada program), prioritas proses dan data-data tambahan lainnya.
2. Switching to user mode dari kernel mode.
3. Lompat dari suatu bagian di progam user untuk mengulang program.
Dispatcher seharusnya dapat dilakukan secepat mungkin. Dispatch Latency adalah waktu yang diperlukan dispatcher untuk menghentikan suatu proses dan memulai proses yang lain.
Algoritma Penjadualan
Algoritma yang digunakan dalam penjadulan CPU ada bermacam-macam. Diantaranya adalah First Come First Serve (FCFS), Penjadual Shortest Job First, Penjadual Priority, Penjadual Round Robin.
a. Algoritma Penjadual First Come, First Served
Penjadual CPU berurusan dengan permasalahan memutuskan proses mana yang akan dillaksanakan, oleh karena itu banyak bermacam algoritma penjadual, di seksi ini kita akan mendiskripsikan beberapa algoritma.
Ini merupakan algoritma yang paling sederhana, dengan skema proses yang meminta CPU mendapat prioritas. Implementasi dari FCFS mudah diatasi dengan FIFO queue.
Contoh:
Gambar Kedatangan Proses
Gambar Gannt Chart Kedatangan Proses I
Gambar Gannt Chart Kedatangan Proses II
misal proses dibalik sehingga urutan kedatangan adalah P3, P2, P1.
Gambar Gannt Chart Kedatangan Proses III
Gambar Gannt Chart Kedatangan Proses IV
Dari dua contoh diatas bahwa kasus kedua lebih baik dari kasus pertama, karena pengaruh kedatangan disamping itu FCFS mempunyai kelemahan yaitu convoy effect dimana seandainya ada sebuah proses yang kecil tetapi dia mengantri dengan proses yang membutuhkan waktu yang lama mengakibatkan proses tersebut akan lama dieksekusi.
b. Penjadual Shortest Job First
Salah satu algoritma yang lain adalah Shortest Job First. Algoritma ini berkaitan dengan waktu setiap proses. Ketika CPU bebas proses yang mempunyai waktu terpendek untuk menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut.
Ada dua skema dalam SJFS ini yaitu:
1. nonpremptive — ketika CPU memberikan kepada proses itu tidak bisa ditunda hingga selesai.
2. premptive — bila sebuah proses datang dengan waktu prose lebih rendah dibandingkan dengan waktu proses yang sedang dieksekusi oleh CPU maka proses yang waktunya lebih rendah mendapatkan prioritas. Skema ini disebut juga Short - Remaining Time First (SRTF).
Contoh:
Gambar Kedatangan Proses
Gambar Gannt Chart SJF Non-Preemtive
Gambar Rata-rata Menunggu
SJF algoritma mungkin adalah yang paling optimal, karena ia memberikan rata-rata minimum waiting untuk kumpulan dari proses yang mengantri. Dengan mengeksekusi waktu yang paling pendek baru yang paling lama. Akibatnya rata-rata waktu mnenuggu menurun.
Hal yang sulit dengan SJF algoritma adalah mengethaui waku dari proses berikutnya. Untuk penjadual long term (lama) di sistem batch, kita bisa menggunakan panjang batas waktu proses yang user sebutkan ketika dia mengirim pekerjaan. Oleh karena itu sjf sering digunakan di penjadual long term.
Walau pun SJF optimal tetapi ia tidak bisa digunakan untuk penjadual CPU short term. Tidak ada jalan untuk mengetahui panjang dari CPU burst berikutnya. Salah satu cara untuk mengimplementasikannya adalah dengan memprediksikan CPU burst berikutnya.
Contoh SJF premptive:
Gambar Gannt Chart SJF Preemtive
Gambar 2-37. Rata-rata Menunggu. Sumber: . . .
c. Penjadual Prioritas
Penjadualan SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadual Prioritas. Prioritas dapat diasosiasikan masing-masing proses dan CPU dialokasikan untuk proses dengan prioritas tertinggi. Untuk proritas yang sama dilakukan dengan FCFS.
Ada pun algoritma penjadual prioritas adalah sebagai berikut:
· Setiap proses akan mempunyai prioritas (bilangan integer). Beberapa sistem menggunakan integer dengan urutan kecil untuk proses dengan prioritas rendah, dan sistem lain juga bisa menggunakan integer urutan kecil untuk proses dengan prioritas tinggi. Tetapi dalam teks ini diasumsikan bahwa integer kecil merupakan prioritas tertinggi.
· CPU diberikan ke proses dengan prioritas tertinggi (integer kecil adalah prioritas tertinggi).
· Dalam algoritma ini ada dua skema yaitu:
1. Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU.
2. Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis.
· SJF adalah contoh penjadual prioritas dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya. Permasalahan yang muncul dalam penjadualan prioritas adalah indefinite blocking atau starvation.
· Kadang-kadang untuk kasus dengan prioritas rendah mungkin tidak pernah dieksekusi. Solusi untuk algoritma penjadual prioritas adalah aging
· Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU.
d. Penjadual Round Robin
Algoritma Round Robin (RR) dirancang untuk sistem time sharing. Algoritma ini mirip dengan penjadual FCFS, namun preemption ditambahkan untuk switch antara proses. Antrian ready diperlakukan atau dianggap sebagai antrian sirkular. CPU menglilingi antrian ready dan mengalokasikan masing-masing proses untuk interval waktu tertentu sampai satu time slice/ quantum.
Berikut algritma untuk penjadual Round Robin:
· Setiap proses mendapat jatah waktu CPU (time slice/ quantum) tertentu Time slice/quantum umumnya antara 10 - 100 milidetik.
1. Setelah time slice/ quantum maka proses akan di-preempt dan dipindahkan ke antrian ready.
2. Proses ini adil dan sangat sederhana.
· Jika terdapat n proses di "antrian ready" dan waktu quantum q (milidetik), maka:
1. Maka setiap proses akan mendapatkan 1/n dari waktu CPU.
2. Proses tidak akan menunggu lebih lama dari: (n-1)q time units.
· Kinerja dari algoritma ini tergantung dari ukuran time quantum
1. Time Quantum dengan ukuran yang besar maka akan sama dengan FCFS
2. Time Quantum dengan ukuran yang kecil maka time quantum harus diubah ukurannya lebih besar dengan respek pada alih konteks sebaliknya akan memerlukan ongkos yang besar.
Gambar 2-38. Round Robin. Sumber: . . .
Tipikal: lebih lama waktu rata-rata turnaround dibandingkan SJF, tapi mempunyai response terhadap user lebih cepat.
Gambar 2-39. Time Quantum dan Alih Konteks. Sumber: . . .
Penjadualan Real Time
Dalam bab ini, kita akan mendeskripsikan fasilitas penjadualan yang dibutuhkan untuk mendukung real time computing dengan bantuan sistem komputer.
Terdapat dua jenis real time computing: sistem hard real time dibutuhkan untuk menyelesaikan critical task dengan jaminan waktu tertentu. Secara umum, sebuah proses di kirim dengan sebuah pernyataan jumlah waktu dimana dibutuhkan untuk menyelesaikan atau menjalankan I/O. Kemudian penjadual bisa menjamin proses untuk selesai atau menolak permintaan karena tidak mungkin dilakukan. Karena itu setiap operasi harus dijamin dengan waktu maksimum.
Soft real time computing lebih tidak ketat. Itu membutuhkan bahwa proses yang kritis menerima prioritas dari yang lain. Walau pun menambah fungsi soft real time ke sistem time sharing mungkin akan mengakibatkan pembagian sumber yang tidak adildan mengakibatkan delay yang lebih lama, atau mungkin pembatalan bagi proses tertentu, Hasilnya adalah tujuan secara umum sistem yang bisa mendukung multimedia, graphic berkecepatan tinggi, dan variasi tugas yang tidak bisa diterima di lingkungan yang tidak mendukunng soft real time computing
Mengimplementasikan fungsi soft real time membutuhkan design yang hati-hati dan aspek yang berkaitan dengan sistem operasi. Pertama, sistem harus punya prioritas penjadualan, dan proses real time harus tidak melampaui waktu, walau pun prioritas non real time bisa terjadi. Kedua, dispatch latency harus lebih kecil. Semakin kecil latency, semakin cepat real time proses mengeksekusi.
Untuk menjaga dispatch tetap rendah. Kita butuh agar system call untuk preemptible. Ada beberapa cara untuk mencapai tujuan ini. Satu untuk memasukkan preemption points di durasi yang lama system call, yang mana memeriksa apakah prioritas yang utama butuh untuk dieksekusi. Jika satu sudah, maka alih konteks mengambil alih; ketika high priority proses selesai, proses yang diinterupsi meneruskan dengan system call. Points premption bisa diganti hanya di lokasi yang aman di kernel — hanya kernel struktur tidak bisa dimodifikasi walau pun dengan preemption points, dispatch latency bisa besar, karena pada prakteknya untuk menambah beberapa preemption points untuk kernel.
Metoda yang lain untuk berurusan dengan preemption untuk membuat semua kernel preemptible. Karena operasi yang benar bisa dijamin, semua data kernel struktur dengan di proteksi. Dengan metode ini, kernel bisa selalu di preemptible, karena semua kernel bisa diupdate di proteksi.
Apa yang bisa diproteksi jika prioritas yang utama butuh untuk dibaca atau dimodifisikasi yang bisa dibutuhkan oleh yang lain, prioritas yang rendah? Prioritas yang tinggi harus menunggu menunggu untuk menyelesaikan prioritas yang rendah.
Fase konflik dari dispatch latency mempunyai dua komponen:
1. Preemption semua proses yang berjalan di kernel.
2. Lepas prioritas yang rendah untuk prioritas yang tinggi.
Penjadwalan ASMP
Pada model ASMP, ide dasarnya adalah master/slave, yaitu kernel selalu berjalan di prosesor tertentu, sedangkan prosesor-prosesor lainnya menjalankan utiliti yang ada di sistem operasi atau mengerjakan tugas-tugas tertentu. Prosesor master bertugas menjadwal proses atau thread. Ketika suatu proses/thread aktif, dan prosesor slave membutuhkan layanan (misal untuk I/O), maka dia harus mengirim permintaan ke prosesor master dan menunggu hingga permintaanya dilaksanakan. Model ini adalah sederhana, karena hanya satu prosesor yang mengatur sumber daya memori dan I/O.
Sayangnya, model ini memiliki beberapa kelemahan seperti:
· Kegagalan prosesor utama bisa menyebabkan kegagalan keseluruhan sistem.
· Bisa terjadi penururan performa, yaitu terjadi bottleneck di prosesor utama karena dialah yang bertanggung jawab atas penjadwalan dan manajenem proses.
Penjadwalan SMP
Penjadwalan SMP ( Symmetric multiprocessing) adalah pendekatan kedua untuk penjadwalan prosesor jamak. Dimana setiap prosesor menjadwalkan dirinya sendiri ( self scheduling). Semua proses mungkin berada pada antrian ready yang biasa, atau mungkin setiap prosesor memiliki antrian ready tersendiri. Bagaimanapun juga, penjadwalan terlaksana dengan menjadwalkan setiap prosesor untuk memeriksa antrian ready dan memilih suatu proses untuk dieksekusi. Jika suatu sistem prosesor jamak mencoba untuk mengakses dan meng- update suatu struktur data, penjadwal dari prosesor-prosesor tersebut harus diprogram dengan hati-hati; kita harus yakin bahwa dua prosesor tidak memilih proses yang sama dan proses tersebut tidak hilang dari antrian. Secara virtual, semua sistem operasi modern mendukung SMP, termasuk Windows XP, Windows 2000, Solaris, Linux, dan Mac OS X.
a. Load Balancing
Dalam sistem SMP, sangat penting untuk menjaga keseimbangan workload antara semua prosesor untuk memaksimalkan keuntungan memiliki multiprocessor. Jika tidak, mungkin satu atau lebih prosesor idle disaat prosesor lain harus bekerja keras dengan workload yang tinggi. Load balancing adalah usaha untuk menjaga workload terdistribusi sama rata untuk semua prosesor dalam sistem SMP. Perlu diperhatikan bahwa load balancing hanya perlu dilakukan pada sistem dimana setiap prosesor memiliki antrian tersendiri( private queue) untuk proses-proses yang berstatus ready. Pada sistem dengan antrian yang biasa ( common queue), load balancing tidak diperlukan karena sekali prosesor menjadi idle, prosesor tersebut segera mengerjakan proses yang dapat dilaksanakan dari antrian biasa tersebut. Perlu juga diperhatikan bahwa pada sebagian besar sistem operasi kontemporer mendukung SMP, jadi setiap prosesor bisa memiliki private queue.
Ada dua jenis load balancing, yakni:
- Push migration, pada kondisi ini ada suatu task spesifik yang secara berkala memeriksa load dari tiap-tiap prosesor. Jika terdapat ketidakseimbangan, maka dilakukan perataan dengan memindahkan( pushing) proses dari yang kelebihan muatan ke prosesor yang idle atau yang memiliki muatan lebih sedikit.
- Pull migration, kondisi ini terjadi saat prosesor yang idle menarik( pulling) proses yang sedang menunggu dari prosesor yang sibuk.
Kedua pendekatan tersebut tidak harus mutually exclusive dan dalam kenyataannya sering diimplementasikan secara paralel pada sistem load-balancing.
b. Symetric Multithreading
Sistem SMP mengizinkan beberapa thread untuk berjalan secara bersamaan dengan menyediakan banyak physical processor. Ada sebuah strategi alternatif yang lebih cenderung untuk menyediakan logical processor daripada physical processor. Strategi ini dikenal sebagai SMT ( Symetric Multithreading). SMT juga biasa disebut teknologi hyperthreading dalam prosesor intel.
Ide dari SMT adalah untuk menciptakan banyak logical processor dalam suatu physical processor yang sama dan mempresentasikan beberapa prosesor kepada sistem operasi. Setiap logical processor mempunyai state arsitekturnya sendiri yang mencangkup general purpose dan machine state register. Lebih jauh lagi, setiap logical prosesor bertanggung jawab pada penanganan interupsinya sendiri, yang berarti bahwa interupsi cenderung dikirimkan ke logical processor dan ditangani oleh logical processor bukan physical processor. Dengan kata lain, setiap logical processor men- share resource dari physical processor-nya, seperti chace dan bus.
Gambar Symetric Multithreading
 |
Gambar di atas mengilustrasikan suatu tipe arsitektur SMT dengan dua physical processor dengan masing-masing punya dua logical processor. Dari sudut pandang sistem operasi, pada sistem ini terdapat empat prosesor.
Perlu diketahui bahwa SMT adalah fitur yang disediakan dalam hardware, bukan software, sehingga hardware harus menyediakan representasi state arsitektur dari setiap logical processor sebagaimana representasi dari penanganan interupsinya. Sistem operasi tidak perlu didesain khusus jika berjalan pada sistem SMT, akan tetapi performa yang diharapkan tidak selalu terjadi pada sistem operasi yang berjalan pada SMT. Misalnya, suatu sistem memiliki 2 physical processor, keduanya idle, penjadwal pertama kali akan lebih memilih untuk membagi thread ke physical processor daripada membaginya ke logical processor dalam physical processor yang sama, sehingga logical processor pada satu physical processor bisa menjadi sibuk sedangkan physical processor yang lain menjadi idle.
